Week 3

This past week focussed on conjunction, disjunction, negation, and implication. 

While I find conjunction and disjunction pretty straightforward, implication, in this context, doesn't come as readily. I learn best by writing things out and working through them, so that's what I'm going to do for implication.

The truth table for the implication $P \Rightarrow Q$ is:
$$\begin{array}{ r  r | c } P & Q & P \Rightarrow Q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array}$$ As given in class, we also have $$P \Rightarrow Q \;\Leftrightarrow\; \neg P \vee  Q$$
With the above we can check that the contrapositive is the same as the regular implication:
$$\begin{align*} \neg Q \Rightarrow \neg P &\;\Leftrightarrow\; \neg \neg Q \vee \neg P \\ &\;\Leftrightarrow\; Q \vee \neg P \\ &\;\Leftrightarrow\; \neg P \vee Q \end{align*}$$
Next, let's translate an equivalence into conjunction and disjunction, starting by splitting the bi-implication into two implications:
$$\begin{align*} P \Leftrightarrow Q &\;\Leftrightarrow\; ( P \Rightarrow Q ) \wedge (Q \Rightarrow P \\ &\;\Leftrightarrow\; (\neg P \vee Q) \wedge (\neg Q \vee P)\\ &\;\Leftrightarrow\; (\neg P \wedge \neg Q) \vee (\neg P \wedge P) \vee (Q \wedge \neg Q) \vee (Q \wedge P)\\ &\;\Leftrightarrow\; (\neg P \wedge \neg Q) \vee (P \wedge Q) \end{align*}$$ What about the transitive property?
$$\begin{align*} ((P \Rightarrow Q) \wedge (Q \Rightarrow R)) &\;\Rightarrow\; (P\Rightarrow R)\\ (\neg P \vee Q) \wedge (\neg Q \vee R) &\;\Rightarrow\; (\neg P \vee R)\\ \neg ((\neg P\vee Q) \wedge (\neg Q \vee R) &\;\,\vee\; (\neg P \vee R)\\ \neg(\neg P\vee Q) \vee \neg(\neg Q \vee R) &\;\,\vee\; (\neg P \vee R)\\ (P \wedge \neg Q) \vee (Q \wedge \neg R) &\;\,\vee\; (\neg P \vee R)\\ \end{align*}$$
as a truth table:
$$\begin{array}{c c c | c c c | c } P & Q & R & (P \wedge \neg Q) & (Q \wedge \neg R) & (\neg P \vee R) & (P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)\\\hline T & T & T & F & F & T & T \\ T & T & F & F & T & F & T \\ T & F & T & T & F & T & T \\ T & F & F & T & F & F & T \\ F & T & T & F & F & T & T \\ F & T & F & F & T & T & T \\ F & F & T & F & F & T & T \\ F & F & F & F & F & T & T \\ \end{array}$$ So it's a tautology. Great. (It would have been easier to just go straight to a truth table, but let's call it "good practice").

Finally, how does it look for $P\Rightarrow (Q\Rightarrow R)$?
$$\begin{align*} P\Rightarrow (Q\Rightarrow R) &\;\Leftrightarrow\; \neg P \vee (\neg Q \vee R) \\ &\;\Leftrightarrow\; (\neg P \vee \neg Q) \vee R \\ &\;\Leftrightarrow\; \neg (P \wedge Q) \vee R \\ &\;\Leftrightarrow\; (P \wedge Q) \Rightarrow R\\ \end{align*}$$
That's all I can really think of right now. A lot of this stuff is easier to show by just writing up a truth table, but I learn better if I can think about things multiple ways. Also, a truth table would show that $$P \Rightarrow (Q \Rightarrow R)) \;\Leftrightarrow\; (P\Rightarrow R) \vee (Q\Rightarrow R)$$ but I haven't figured out how to get there by manipulating terms.