Algorithmic Foundations 2 Flashcards Preview

Computing > Algorithmic Foundations 2 > Flashcards

Flashcards in Algorithmic Foundations 2 Deck (33)
Loading flashcards...
1

Identity Laws

P ∧ true ≡

P ∨ false ≡

P ∧ true ≡ P

P ∨ false ≡ P

2

Domination Laws

P ∨ true ≡

P ∧ false ≡

P ∨ true ≡ true

P ∧ false ≡ true

3

Idempotent Laws

P ∧ P ≡

P ∨ P ≡

P ∧ P ≡ P

P ∨ P ≡ P

4

Double Negation Law

¬(¬P) ≡ P

5

Commutative laws

P ∧ Q ≡ 

P ∨ Q ≡ 

P ∧ Q ≡ Q ∧ P

P ∨ Q ≡ Q ∨ P

6

Associative laws

(P ∧ Q) ∧ R ≡

(P ∨ Q) ∨ R ≡

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

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

7

Distributive Laws

P ∨ (Q ∧ R) ≡

P ∧ (Q ∨ R) ≡ 

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

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

8

De Morgan Laws 

¬ (P ∧ Q) ≡

¬ (P ∨ Q) ≡ 

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

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

9

Contradiction and Tautology Laws

P ∧ ¬P ≡

P ∨ ¬P ≡

P ∧ ¬P ≡ false

P ∨ ¬P ≡ true

10

Implication Law

P → Q ≡ 

P → Q ≡ ¬P ∨ Q

11

Exclusive or and Biconditional Laws

P ⊕ Q ≡

P ≡ Q ≡

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

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

12

Quantifier L​aw One

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

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

13

Quantifier Law Two

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

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

14

Quantifier Law Three

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

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

15

Quantifier Law Four

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

 

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

16

Quantifier Law Five

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

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

17

Quantifier Law Six

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

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

18

P ∨ Q means?

P or Q

19

P ∧ Q means?

and Q

20

A fucntion is injective or 'one-to-one' if?

|X| ≤ |Y|

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

21

A fucntion is surjective or onto if?

|Y| ≤ |X|

informally each value in the codomain has a preimage

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

22

If a fucntion is bijecitve then?

Both injective and surjective

|X| = |Y|

23

Describe what it means for a graph to be connected?

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

24

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

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

25

A binary relation is reflexive if...

if a ∈ A then (a,a) ∈ R

every element is related to itself 

26

A binary relation is symmetric if...

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 

27

A binary relation is anti-symmetric if...

if (a,b) ∈ R and a ≠ b then (b,a) ∉ R 

if a is related to b, then b is not related to a 

28

A binary relation is transitive if...

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

29

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

Reflexive

Anti-Symmetric

Transitive

30

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

Reflexive

Symmetric

Transitive