3

I have to prove that $(¬q \wedge (p \rightarrow q)) \rightarrow ¬p$ is a tautology.

I have done the following:

$$\begin{align}&¬(¬q \wedge (p \rightarrow q)) \vee ¬p \\ &\implies ¬¬q \vee ¬(p \rightarrow q) \vee ¬p \\ &\implies q \vee ¬¬p \wedge \vee ¬p \\ &\implies q \wedge ¬q \vee p \vee ¬p \\ &\implies F \vee T \\ &\implies T \end{align}$$

I am wondering if the last three steps are correct or not? If there are several $\wedge$ or $\vee$ in a expression, can they all be considered commutatively?

amWhy
  • 209,954
null
  • 355

1 Answers1

6

No, you cannot commute as you did. You can commute when the operation is all disjunction or all conjunction. E.g.: $$a \lor b \lor c \equiv c \lor a\lor b$$ $$a\land b \land c\equiv a \land c \land b$$ You cannot commute mixed operations. E.g.: $$(a \land b) \lor c\not\equiv (a \lor c) \land b$$

You need to keep parentheses as in the third and fourth row below. For mixed operators, you'll want to use the distributive properties.

$$\begin{align}¬(¬q \wedge (p \rightarrow q)) \vee ¬p &\equiv ¬¬q \vee ¬(p \rightarrow q) \vee ¬p \\\\ &\equiv q \lor \lnot(\lnot p \lor q) \lor \lnot p\\\\ &\equiv q \vee (¬¬p \wedge \lnot q) \vee ¬p \\\\ &\equiv q \lor (p \land \lnot q) \lor \lnot p\\\\ &\equiv [(q\lor p) \land (q\lor \lnot q)] \lor \lnot p\\\\ &\equiv [(q \lor p) \land T]\lor \lnot p\\\\ &\equiv (q \lor p \lor \lnot p) \land (T\lor \lnot p)\\\\ &\equiv(q \lor T) \land T\\\\ &\equiv T\land T\\\\ &\equiv T \end{align}$$

Remark on your proof-style: As you note, in my proof above, I indicate that each line on the right of the $\equiv$ is equivalent to the left-hand side of the first line. You use only right-implication between your lines. While it is true that each line is implied by the former, it is also true that each line below the first implies the preceding line, and in fact, logical equivalence holds. Your proof method claims only forward implication. I used $\equiv$ to establish that the original proposition is identically true: i.e., a tautology.

amWhy
  • 209,954