Algorithmic Foundations 2

Question 1

Identity Laws

P ∧ true ≡

P ∨ false ≡

Answer 1

P ∧ true ≡ P

P ∨ false ≡ P

Question 2

Domination Laws

P ∨ true ≡

P ∧ false ≡

Answer 2

P ∨ true ≡ true

P ∧ false ≡ true

Question 3

Idempotent Laws

P ∧ P ≡

P ∨ P ≡

Answer 3

P ∧ P ≡ P

P ∨ P ≡ P

Question 4

Double Negation Law

¬(¬P) ≡ P

Question 5

Commutative laws

P ∧ Q ≡

P ∨ Q ≡

Answer 5

P ∧ Q ≡ Q ∧ P

P ∨ Q ≡ Q ∨ P

Question 6

Associative laws

(P ∧ Q) ∧ R ≡

(P ∨ Q) ∨ R ≡

Answer 6

(P ∧ Q ) ∧ R ≡ P ∧ (Q ∧ R)

(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)

Question 7

Distributive Laws

P ∨ (Q ∧ R) ≡

P ∧ (Q ∨ R) ≡

Answer 7

P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

Question 8

De Morgan Laws

¬ (P ∧ Q) ≡

¬ (P ∨ Q) ≡

Answer 8

¬ (P ∧ Q) ≡ ¬P ∨ ¬Q

¬ (P ∨ Q) ≡ ¬P ∧ ¬Q

Question 9

Contradiction and Tautology Laws

P ∧ ¬P ≡

P ∨ ¬P ≡

Answer 9

P ∧ ¬P ≡ false

P ∨ ¬P ≡ true

Question 10

Implication Law

P → Q ≡

Answer 10

P → Q ≡ ¬P ∨ Q

Question 11

Exclusive or and Biconditional Laws

P ⊕ Q ≡

P ≡ Q ≡

Answer 11

P ⊕ Q ≡ (P ∨ Q) ∧ ¬(P ∧ Q)

P ≡ Q ≡ (P → Q) ∧ (Q → P)

Question 12

Quantifier L​aw One

∀x. ∀y. Q(x, y) ≡

Answer 12

∀x. ∀y. Q(x, y) ≡ ∀y. ∀x. Q(x, y)

Question 13

Quantifier Law Two

∃x. ∃y. Q(x, y) ≡

Answer 13

∃x. ∃y. Q(x, y) ≡ ∃y. ∃x. Q(x, y)

Question 14

Quantifier Law Three

¬(∃x. ¬P(x)) ≡

Answer 14

¬(∃x. ¬P(x)) ≡ ∀x. P(x)

Question 15

Quantifier Law Four

¬(∀x. ¬P(x)) ≡

Answer 15

¬(∀x. ¬P(x)) ≡ ∃x. P(x)

Question 16

Quantifier Law Five

∀x. (P(x) ∧ Q(x)) ≡

Answer 16

∀x. (P(x) ∧ Q(x)) ≡ ∀x. P(x) ∧ ∀x. Q(x)

Question 17

Quantifier Law Six

∃x. (P(x) ∨ Q(x)) ≡

Answer 17

∃x. (P(x) ∨ Q(x)) ≡ ∃x. P(x) ∨ ∃x. Q(x)

Question 18

P ∨ Q means?

Answer 18

P or Q

Question 19

P ∧ Q means?

Answer 19

P and Q

Question 20

A fucntion is injective or ‘one-to-one’ if?

Answer 20

|X| ≤ |Y|

informally f maps different elements of X to different elements of Y

Question 21

A fucntion is surjective or onto if?

Answer 21

|Y| ≤ |X|

informally each value in the codomain has a preimage

∀y. ∃x. (f(x) = y)

Question 22

If a fucntion is bijecitve then?

Answer 22

Both injective and surjective

|X| = |Y|

Question 23

Describe what it means for a graph to be connected?

Answer 23

A graph is connected if every pair of vertices is joined by a path.

Question 24

Describe what it means when a graph is a clique (complete) ?

Answer 24

A graph is complete (a clique) if every pair of vertices is joined by an edge.

Question 25

A binary relation is **reflexive** if...

Answer 25

if a ∈ A then (a,a) ∈ R every element is related to itself

Question 26

A binary relation is **symmetric** if...

Answer 26

if (a,b) ∈ R and a ≠ b then (b,a) ∈ R a is related to b if and only if b is related to a

Question 27

A binary relation is **anti-symmetric** if...

Answer 27

if (a,b) ∈ R and a ≠ b then (b,a) ∉ R if a is related to b, then b is not related to a

Question 28

A binary relation is **transitive** if...

Answer 28

if (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R if a is related to b and b related to c, then a is related to c

Question 29

A relation R is a **partial order** on S if it is...

Answer 29

Reflexive Anti-Symmetric Transitive

Question 30

A relation R is called an **equivalence reltaion** if it is...

Answer 30

Reflexive Symmetric Transitive

Question 31

What is the Handshaking theorem?

Answer 31

The handshaking theorem states that the sum of the degrees is equal to **2·|E|** (two multiplied by the number of edges).

Question 32

Describe what it means for a **simple graph** to be **connected**

Answer 32

A simple graph is connected if every pair of vertices is joined by a path. (A path from vertex u to vertex v is a sequence of edges that take us from u to v).

Question 33

A **simple** graph is **bipartite** if?

Answer 33

A simple graph is bipartite if the vertices can be divided into two disjoint sets U and W such that every edge joins a vertex in U and a vertex in W.