Lecture on Logical Equivalences

Definition of Logical Equivalence

• Logical Equivalence: Compound propositions P and Q are logically equivalent if P biconditional Q is a tautology.
  • P true -> Q true, P false -> Q false.
• Denoted using specific symbols.

Example

• Example: P and True is equivalent to P.
  • Truth Table: Shows P and True have the same truth values as P.

Common Logical Equivalences

Identity Laws

1. P and True is equivalent to P.
2. P or False is equivalent to P.

Domination Laws

1. P or True is equivalent to True.
2. P and False is equivalent to False.

Idempotent Laws

1. P or P is equivalent to P.
2. P and P is equivalent to P.

Double Negation Law

• Not Not P is equivalent to P.

Commutative Laws

1. P or Q is equivalent to Q or P.
2. P and Q is equivalent to Q and P.

Associative Laws

• P or Q or R and P and Q and R: Order of calculation doesn't matter.

Distributive Laws

1. P or (Q and R) is equivalent to (P or Q) and (P or R).
2. P and (Q or R) is equivalent to (P and Q) or (P and R).

De Morgan's Laws

1. Not (P and Q) is equivalent to Not P or Not Q.
2. Not (P or Q) is equivalent to Not P and Not Q.

Absorption Laws

1. P or (P and Q) is equivalent to P.
2. P and (P or Q) is equivalent to P.

Negation Laws

1. P or Not P is equivalent to True.
2. P and Not P is equivalent to False.

Logical Equivalences Involving Conditional Statements

1. P implies Q is equivalent to Not P or Q.
2. P implies Q is equivalent to Not Q implies Not P (contrapositive).
3. Not P implies Q is equivalent to P or Q.
4. P and Q is equivalent to Not (Q implies Not P).
5. Not P implies Q is equivalent to P and Not Q (homework).
6. P implies (Q and R) is equivalent to (P implies Q) and (P implies R).

Logical Equivalences Involving Biconditional Statements

1. P biconditional Q is equivalent to (P implies Q) and (Q implies P).
2. P biconditional Q is equivalent to Not P biconditional Not Q.
3. P biconditional Q is equivalent to (P and Q) or (Not P and Not Q).
4. Not (P biconditional Q) is equivalent to P biconditional Not Q (homework).

Homework Assignments

• Prove certain logical equivalences as homework.