Day 57 – Proofs with Truth Tables

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\;\;
pq
xx
yy

Examples:

Is\;(p\;\wedge\;q)\;\iff\;\neg\;(p\;\vee\;q)?
pqp∧qp∨q¬(p∨q)
11110
10010
01010
00001
The answer is No.

Therefore, they’re not logically equivalent.


Is\;\neg(p\;\wedge\;q)\;\iff\;(\neg p\;\vee\;\neg q)?
pqp∧q¬(p∧q)¬p¬q¬p ∨ ¬q
1110000
1001011
0101101
0001111
The answer is Yes.

Therefore, they’re logically equivalent.

Tautology – always true.

Show that (p ∨¬p) is a tautology.

p¬pp ∨¬p
101
011
The answer is always true.

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¬pp ¬p
100
010
The answer is always false.

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.

pqp⊕q
110
101
011
000
pp⊕p(p⊕p)⊕p
101
000
P is always going to be the same value as itself.
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)

pqp⊕q
(x)
¬qp⊕¬q
(y)
(p⊕q)(p⊕¬q)
(x y)
110011
101101
011001
000111
(p⊕q)∨(p⊕¬q) is a tautology.

Sheffer Stroke Examples

p↑q is to be read as “p nand q”, and is equivalent to ¬(pq). 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)
pqpq¬(pq)
p↑q
pp
¬(pp)
p↑p
111010
1001
010101
0001
¬(pp) = p↑p = ¬p

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 (pq).

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 (pq).

(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)

Leave a Reply