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

• 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.)
• 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.