# Equivalences, So Far

- When discussing \(\oplus\), I showed a truth table of \(p\oplus q\) and \((p\vee q) \wedge \neg(p\wedge q)\) and conclude that they were equivalent.
- Why was the truth table enough to conclude that the two propositions are equivalent? (We haven't defined “equivalent” yet, but we can guess what it means.)
- Since the truth table lists every possible value for the components, it is a complete list of every way to evaluate that compound proposition.
- … and we found out that \(p\oplus q\) and \((p\vee q) \wedge \neg(p\wedge q)\) were the same everywhere.
- Imagine trying to prove that \(-(n+1)=-n-1\) like that (for every integer). It's easy: just evaluate both for every possible value of \(n\): \(0, 1, -1, 2, -2, 3, -3, 4, -4, \ldots\).
- The only difference is that with \(\mathrm{T}\) and \(\mathrm{F}\) being the only values, drawing the table is practical.

# Tautologies and Contradictions

- Definitions:
- A proposition that is always true is called a tautology.
- A proposition that is always false is called a contradiction.
- A proposition that is neither a tautology or a contracition is a contingency.

- Examples:
- \(p\vee\neg p\) is a tautology.
- \(p\wedge\neg p\) is a contradiction.
- \(\neg p \vee (p\rightarrow q)\) is which?
- How do we know? So far: draw a truth table.

# Logical Equivalences

- Informally, what we mean by “equivalent” should be obvious: equivalent propositions are the same.
- But we need to be a little more careful about definitions.

- Propositions \(p\) and \(q\) are logically equivalent if \(p\leftrightarrow q\) is a tautology.
- We will write \(p\equiv q\) for an equivalence. (Some people also write \(p\Leftrightarrow q\).)

- The only way we have so far to prove that two propositions are equivalent is a truth table.
- We used truth tables to show that \(\oplus\) and \(\rightarrow\) propositions are equivalent to others written using only \(\vee\), \(\wedge\), and \(\neg\).
- Wecan establish some more basic equivalences this way.

# Important Equivalences

- Informally, what we mean by “equivalent” should be obvious: equivalent propositions are the same.
- But we need to be a little more careful about definitions.

- Propositions \(p\) and \(q\) are logically equivalent if \(p\leftrightarrow q\) is a tautology.
- We will write \(p\equiv q\) for an equivalence. (Some people also write \(p\Leftrightarrow q\).)

- The only way we have so far to prove that two propositions are equivalent is a truth table.
- We used truth tables to show that \(\oplus\) and \(\rightarrow\) propositions are equivalent to others written using only \(\vee\), \(\wedge\), and \(\neg\).
- We can establish some more basic equivalences this way.
- … and use those to show things are equivalent in a nicer way.

- Some equivalences important enough to have names: (If these are different than Table 6, it's right.)
Name Equivalences Identity \(p\wedge\mathrm{T}\equiv p\\p\vee\mathrm{F}\equiv p\) Domination \(p\vee\mathrm{T}\equiv \mathrm{T}\\p\wedge\mathrm{F}\equiv \mathrm{F}\) Idempotent \(p\wedge p\equiv p\\p\vee p\equiv p\) Double Negation \(\neg(\neg p)\equiv p\) Commutative \(p\vee q \equiv q\vee p\\p\wedge q \equiv q\wedge p\) Associative \((p\vee q)\vee r \equiv p\vee(q\vee r)\\(p\wedge q)\wedge r \equiv p\wedge(q\wedge r)\) Distributive \(p\vee(q\wedge r) \equiv (p\vee q)\wedge(p\vee r)\\p\wedge(q\vee r) \equiv (p\wedge q)\vee(p\wedge r)\) De Morgan's Law \(\neg(p\wedge q)\equiv \neg p \vee \neg q\\\neg(p\vee q)\equiv \neg p \wedge \neg q\) Absorption \(p\vee(p\wedge q) \equiv p \\ p\wedge(p\vee q) \equiv p\) Negation \(p\vee\neg p \equiv \mathrm{T}\\p\wedge\neg p \equiv \mathrm{F}\) - Pick a couple of those and prove them with a truth table.
- See tables 7 and 8 in the text (page 25) for some equivalences with conditionals and biconditionals.

# Proving Equivalences

- We can use these equivalences to finally do mathematical proofs.
- That is, we can show that equivalences are correct, without drawing a truth table.
- For example, we can show that \(\neg(p\rightarrow q)\) is equivalent to \(p\wedge\neg q\) like this: \[\begin{align*} \neg(p\rightarrow q) &\equiv \neg(\neg p \vee q) & \mbox{[a conditional equivalence shown earlier]} \\ &\equiv \neg(\neg p) \wedge \neg q & \mbox{[De Morgan's Law]} \\ &\equiv p \wedge \neg q\,. & \mbox{[double negation]} \end{align*}\]
- When we do logical proofs in this course, they should be in that form: exactly one know equivalence applied in each line, with the reason noted.
- Another example: that \(q\wedge\neg(p\rightarrow q)\) is a contradiction: \[\begin{align*} q\wedge\neg(p\rightarrow q) &\equiv q\wedge\neg(\neg p \vee q) & \mbox{[conditional equivalence]} \\ &\equiv q\wedge(\neg\neg p \wedge \neg q) & \mbox{[De Morgan's]} \\ &\equiv q\wedge(\neg q\wedge \neg\neg p ) & \mbox{[commutative]} \\ &\equiv (q\wedge\neg q)\wedge \neg\neg p & \mbox{[associative]} \\ &\equiv \mbox{F}\wedge \neg\neg p & \mbox{[negation]} \\ &\equiv \mbox{F}\,. & \mbox{[domination]} \end{align*}\]
- Aren't truth tables easier?
- For equivalences with only two propositions, probably. Maybe for three.
- For more complex equivalences, you have abandon truth tables and start thinking.