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.

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.

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.

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.