Determine whether (¬p ∧ (p → q)) → ¬q is a tautology.

Question

The answer is not a tautology. I know the answer based on the true table, however I wanna try another method.

Here is my method: (¬p ∧ (p → q)) → ¬q ≡ ¬(¬p∧(¬p∨q))∨¬q ≡p∨(p∧¬q)∨¬q ≡((p∨p)∧(p∨¬q))∨¬q

Which part am I wrong?Thanks for your explanation!

Answer 1

Since you have an answer from a truth table, you know an assignment of truth values to $p$ and $q$ that makes the entire formula false.

You can use this to discover at least one error in your computation: Plug the truth assignment you have found into each of your rewritten formulas, and compute the overall truth value of each step. When the truth value changes (which it must because it starts at something you know to be false and ends at $T$), you have found a rewriting step that's not valid.

Answer 2

Another simple method to determine tautology without truth table is: If it's a tautology, when you write it in "$\vee$connection" form, you can always find, at least two statements that are negations of each other, in other hand, if all pairs of statements are not negation of each other, that implies it's not a tautology.

Answer 3

In all cases if you set $p \equiv F$ and $q \equiv T$, the whole statement is FALSE.

Answer 4

A statement that is a tautology is by definition a statement that is always true, and there are several approaches one could take to evaluate whether this is the case:

(1) Truth Tables - For one, we may construct a truth table and evaluate whether every line in the table is in fact true. This is fine when the statement is relatively short. As one adds more distinct component propositions to the statement, the length of the truth table grows exponentially, and as a result this approach becomes less practical.

(2) Application of Rules of Replacement - Secondly, we may apply the rules of replacement to this statement over and over until it simplifies to T, which would mean the statement is true. This approach is preferred when the statement is "longer" or "more complicated," that is, it contains more distinct component propositions. However, there is a significant drawback to this approach: if you are unable to simplify the statement to T, this does not necessarily mean the statement is not a tautology; rather, it's only if you ARE able to simplify the statement to T, then the statement must be a tautology.

(3) Backwards (Indirect) Reasoning - Third, we may observe the operator(s) of least precedence and determine under what conditions the statement is true. We can then impose these conditions and reason backwards to see if the remainder of the statement, which includes the operators of greater importance, supports these conditions.

Note that the list of approaches I've outlined is not necessarily comprehensive, but it does include those that are most common. You can also use them in tandem as you see fit, which is what I will do with your example.

I will begin by using the rules of replacement to simplify the statement:

$(\neg p \wedge (p \rightarrow q)) \rightarrow \neg q$

$\Leftrightarrow (\neg p \wedge (\neg p \vee q)) \rightarrow \neg q$ by the implication rule

$\Leftrightarrow ((\neg p \wedge \neg p) \vee (\neg p \wedge q)) \rightarrow \neg q$ by the distribution rule

$\Leftrightarrow (\neg p \vee (\neg p \wedge q)) \rightarrow \neg q$ by the idempotence rule

$\Leftrightarrow \neg p \rightarrow \neg q$ by the absorption rule

$\Leftrightarrow q \rightarrow p$ by the contrapositive rule

Notice that I have not simplified the statement to T, but I have simplified it into a form with less operators that would be easier to evaluate via some other means. You could easily finish examining this statement with a truth table. I assume you know how to do this, so I will use approach number (3) instead.

When we examine $q \rightarrow p$, note the operator of least precedence is $\rightarrow$. In fact, it's the only operator. It returns false only when the antecedent, in this case $q$, is true, and the consequent, in this case $p$, is false. Is this possible? Well, $q$ can certainly be true, and there nothing preventing $p$ from being false, so yes it is in fact possible for the statement $q \rightarrow p$ to return false. Hence, the statement cannot be a tautology.