## 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 |

*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.

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 | pq∧ | ¬(pq)∧p↑q | pp∧ | ¬(pp)∧p↑p |
---|---|---|---|---|---|

1 | 1 | 1 | 0 | 1 | 0 |

1 | 0 | 0 | 1 | ||

0 | 1 | 0 | 1 | 0 | 1 |

0 | 0 | 0 | 1 |

**¬**(p

**p) = 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 (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)