1.3 Propositional Equivalences

What is a tautology?

a compound proposition that is always true

What is a contradiction?

a compound proposition that is always false

What is a contingency?

a compound proposition that is neither a tautology nor a contradiction

Is p∨¬p a tautology, contradiction, or contingency?

tautology

Is p∧¬p a tautology, contradiction, or contingency?

contradiction

What does it mean when two compound propositions are logically equivalent?

they have the same truth values in all possible cases;
p↔q is a tautology

What does p≡q mean? (it is not a logical connective)

p and q are logically equivalent

Use De Morgan's Laws to simplify ¬(p∧q)

¬p∨¬q

Use De Morgan's Laws to simplify ¬(p∨q)

¬p∧¬q

How do you prove two compound propositions are logically equivalent?

See if they have the same truth values

What are the identity laws?

p∧T ≡ p
p∨F ≡ p

What are the domination laws?

p∨T ≡ T
p∧F ≡ F

What are the idempotent laws?

p∨p ≡ p
p∧p ≡ p

What is the double negation law?

¬(¬p) ≡ p

What are the commutative laws?

p∨q ≡ q∨p
p∧q ≡ q∧p

What are the associative laws?

(p∨q)∨r ≡ p∨(q∨r)
(p∧q)∧r ≡ p∧(q∧r)

What are the distributive laws?

p∨(q ∧ r) ≡ (p ∨ q)∧(p ∨ r)
p∧(q ∨ r) ≡ (p ∧ q)∨(p ∧ r)

What are De Morgan's laws?

¬(p∧q) ≡ ¬p∨¬q
¬(p∨q) = ¬p∧¬q

What are the absorption laws?

p∨(p∧q) ≡ p
p∧(p∨q) ≡ p

What are the negation laws?

p∨¬p ≡ T
p∧¬p ≡ F

How do you rewrite p→q?

¬p∨q

What is the contrapositive of p→q?

¬q→¬p

How do you rewrite ¬p→q?

p∨q

How do you rewrite ¬(p→¬q)?

p∧q

How do you rewrite ¬(p→q)?

p∧¬q

How do you rewrite (p→q)∧(p→r)?

p→(q∧r)

How do you rewrite (p→r)∧(q→r)?

(p∨q)→r

How do you rewrite (p→q)∨(p→r)

p→(q∨r)

How do you rewrite (p→r)∨(q→r)?

(p∧q)→r

How do you rewrite p↔q? (using → and ∧)

(p→q)∧(q→p)

How do you rewrite p↔q? (using ↔ and ¬)

¬p↔¬q

How do you rewrite p↔q? (using ¬, ∨, ∧)

(p∧q)∨(¬p∧-q)

How do you rewrite ¬(p↔q)

p↔¬q

Use De Morgan's laws to express the negation of "Miguel has a cellphone and he has a laptop computer."

Miguel does not have a cellphone or a laptop computer.

Use De Morgan's laws to express the negation of "Heather will go to the concert or Steven will go to the concert"

Heather and Steve will not go to the concert.

Show that ¬(p→q) ≡ p∧¬q without using a truth table

¬(p→q) ≡ ¬(¬p∨q)
≡ ¬(¬p)∧¬q
≡ p∧¬q
≡ ¬(¬p∨q)
≡ ¬(p→q)

What does it mean when a compound proposition is satisfiable?

there is an assignment of truth values to its variables that makes it true

What does it mean when a compound proposition is unsatisfiable?

it is never true

What does it mean when a particular assignment of truth values is a solution to a compound proposition?

it makes the compound proposition true

P∧Q

P and Q, both P and Q are true

P∨Q

P or Q, At least one of P or Q is true (possibly both)

P⇒Q

If P, then Q, whenever P is true, Q is also true

P⇔Q

P if and only if Q, P is true exactly when Q is true; they have the same truth value.

∀x:P(x)

For all x, ( P(x) ), P(x) is true for every element x in the domain.

∃x:P(x)

There exists an x such that ( P(x) ), There is at least one xxx for which P(x) is true.

¬∀x:P(x)

For all x, P(x) is false

¬∃x:P(x)

There exists an x such that P(x) is false

∀x:P(x)⇒Q(x)

For all x, if P(x) is true, then Q(x) is true

∃x:P(x)∧Q(x)

There exists an x such that both P(x) and Q(x) are true

∃x:P(x)∨Q(x)

There exists an x such that P(x) is true or Q(x) is true (or both)

P⇒Q≡¬P∨Q

If P is false or Q is true, then the implication P⇒Q holds

¬(P⇒Q)

P is true and Q is false

∀x:P(x)∨Q(x)

For all x, either P(x) is true or Q(x) is true (or both)

∀x:(P(x)∨Q(x))⇒R(x)

For all x, if P(x) or Q(x) is true, then R(x) is true