Proofs using Truth Tables
Formulas p and q are logically equivalent iff the truth conditions of p are the same as the truth conditions of q.
p\;\iff\;q\\iff\;\;
| p | q |
| x | x |
| y | y |
Examples:
Is\;(p\;\wedge\;q)\;\iff\;\neg\;(p\;\vee\;q)?
| p | q | p∧q | p∨q | ¬(p∨q) |
| 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
Therefore, they’re not logically equivalent.
Is\;\neg(p\;\wedge\;q)\;\iff\;(\neg p\;\vee\;\neg q)?
| p | q | p∧q | ¬(p∧q) | ¬p | ¬q | ¬p ∨ ¬q |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Therefore, they’re logically equivalent.
Tautology – always true.
Show that (p ∨¬p) is a tautology.
| p | ¬p | p ∨¬p |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
They can be represented in different ways, but pay attention to the pattern.
It’s the same as:
(a\wedge b)\;\vee\;\neg(a\wedge b)
Contradiction – always false
Show that (p ∧¬p) is always false.
| p | ¬p | p ∧¬p |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
Exclusive Or (xor) Example
Write the truth table for exclusive or (xor), (p ⊕ q), then state whether (p⊕p)⊕p is a tautology, contradiction, or neither.
| p | q | p⊕q |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| p | p⊕p | (p⊕p)⊕p | |
| 1 | 0 | 1 | |
| 0 | 0 | 0 |
Then (p⊕p)⊕p was (p⊕p) compared from p.
Therefore this is neither tautology nor contradiction.
Give the truth table for (p⊕q)∨(p⊕¬q)
| p | q | p⊕q (x) | ¬q | p⊕¬q (y) | (p⊕q)∨(p⊕¬q) (x ∨ y) |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 |
Sheffer Stroke Examples
p↑q is to be read as “p nand q”, and is equivalent to ¬(p∧q). Provide the truth table for (p↑q) and (p↑p).
sheffer stroke – ↑
Also read as “nand” or not and (¬∧)
p\uparrow q\;=\;\neg(p\wedge q)
| p | q | p∧q | ¬(p∧q) p↑q | p∧p | ¬(p∧p) p↑p |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | ||
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 |
This idea above can be used in the well-formed formula Phi. And say we want the negation of it, this is similar with taking Phi and Phi, and combining the two with Sheffer Stroke.
\neg \phi\;\iff\;\phi\uparrow\phi
Following the concept above for Phi, using the sheffer stroke, provide a definition for (p∧q).
p\uparrow q\;\iff\;\neg(p\wedge q)\\We\;know \;that\;(p\wedge q)\;\iff\;\neg\neg(p\wedge q)\;=\;\neg(p\uparrow q)\\Which\;is\;similar\;to\;our\;Phi\;above:\\\neg\phi\iff\phi\uparrow\phi\\Therefore:\\\neg(p\uparrow q)\;=\;(p\uparrow q)\uparrow(p\uparrow q)
I have to remember that p∧q means both p and q must be true. I always forget this.
Following the same concept above, using the sheffer stroke, provide a definition for (p∨q).
(p\vee q)\iff \neg\neg p\;\vee\;\neg\neg q\\\neg(\neg p\;\wedge\;\neg q)\;=\;\neg(p\wedge q)\\\neg p\;=\;\neg(p\wedge p)\;=(p\uparrow p)\\=\;\neg((p\uparrow p)\;\wedge(q\uparrow q))\\Therefore:\\(p\;\vee\;q)\;\iff\;(p\uparrow p)\uparrow (q\uparrow q)
