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.