2.6 Logical Equivalence

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-10-09 Teacher: Prof. Musacchio

Sets

DeMorgan’s Laws

1. ∼ (P ∧ Q) = (∼ P) ∨ (∼ Q)
2. ∼ (P ∨ Q) = (∼ P) ∧ (∼ Q

P $\to$ Q === ~ P $\vee$ Q === ~ P or ( Q) === ( Q) $\vee$ (~ P) === ~ Q $\to$ (~ P)

1. Contrapositive

$P\to Q=/Q\to /P$

• If P is true then Q is true
• If Q is false then P is false
• E.g.
  • If x is rational(P) then x is real(Q)
  • If x is not real(~Q) then x is not rational(~P)

2. Commutative

$P\wedge Q=Q\vee P$