I need to prove that the following is a tautology:
[(P -> Q) ∧ ¬ Q ] -> ¬P
so my solution was:
[(¬P V Q) ∧ ¬Q] -> ¬P]
[¬((¬P V Q) ∧ ¬Q)] V ¬P]
[(¬¬P ∧ ¬Q V ¬¬ Q) V ¬P]
[(P ∧ ¬Q V Q) V ¬P]
The way i see the final line is that: ¬Q V Q will always hold true and if P is not true, then (P ∧ ¬Q V Q) is not true. But if P is not satisfied, then ¬P is satisfied so it's always true. Is my logic correct?
$$\begin{array}{c|c|c|c|c|c|c} P & Q& \lnot P &P\rightarrow Q& \lnot Q & ( P\rightarrow Q) \wedge \lnot Q & [(P\rightarrow Q) \wedge \lnot Q ]\rightarrow \lnot P \\ \hline T & T& F & T & F & F & T\\ T & F& F & F & T & F & T\\ F & T& F & T & F & F & T\\ F & F& T & T & T & T & T \end{array}$$
So in all cases you got T = true so it is a tautology ! Look at the last column it contains only T's.
Might be easier to do:
$[(P \rightarrow Q) \wedge \lnot Q] \rightarrow \lnot P \\ [(\lnot P \vee Q) \wedge \lnot Q] \rightarrow \lnot P \\ [(\lnot P \wedge \lnot Q) \vee (Q \wedge \lnot Q)] \rightarrow \lnot P \\ (\lnot P \wedge \lnot Q) \rightarrow \lnot P \\ \lnot (\lnot P \wedge \lnot Q) \vee \lnot P \\ (P \vee Q) \vee \lnot P \\ P \vee\lnot P \vee Q \\ T \vee Q \\ T $
Due to the simple structure of the formula :
$[(P \rightarrow Q) \land \lnot Q ] \rightarrow \lnot P$
you can try with a "menmonic" truth-table :
Case 1) : if $P$ is False, then $\lnot P$ is True, so in this case, by property of truth-functional implication, the formula is True
Case 2) : $P$ is True
Case 2a) : if $Q$ is True, then $\lnot Q$ is False, so the LHS conjunction is False and the complete formula is $False \rightarrow False$, so is again True
Case 2b) : if $Q$ is False, then (because $P$ is True) $(P \rightarrow Q)$ is False, so that the LHS conjunction is False. Again, the complete formula is $False \rightarrow False$, i.e. True
All cases give us True, so the formula is a tautology.
