This page does not represent the most current semester of this course; it is present merely as an archive.
For any expressions P and Q, the expression \lnot(P \land Q) is equivalent to the expression (\lnot P) \lor (\lnot Q)
This is one of two De Morgan’s laws
, named after Augustus De Morgan who died in 1871; however, its use and expression is roughly as old as formal logic itself.
A truth table that shows the two expressions are equivalent is an exhaustive analysis, the most tedious kind of proof by cases. We might thus categorize it as a form of whiteboard proof, though it is often treated as its own special thing.
P  Q    \lnot  (P \land Q)    (\lnot P)  \lor  (\lnot Q) 

false  false    true  false    true  true  true 
false  true    true  false    true  true  false 
true  false    true  false    false  true  true 
true  true    false  true    false  false  false 
Let N represent the expression \lnot(P \land Q) and O represent the expression (\lnot P) \lor (\lnot Q).
The proof is by case analysis. There are two cases: either P is true or it is false.
Because the theorem holds in all cases, it is true.
In small step logics, such as machinecheckable proofs, a proof by cases works by introducing a subproof for each case.
1  \lnot(P \land Q)  
2 


3 


4  \lnot P \lor \lnot Q  LEM 2, 3 
TFL proofs by cases help demonstrate two important principles: