How to solve tautology without using truth table?

Question

How do I determine that (¬a ∧ (a → b)) → ¬b is a tautology without a truth table. Ive tried switching a → b to ¬a or b but then I can't seem to do anything else to do after that.

Answer 1

The statement you're trying to prove is false, so cannot be proven.

Take for example a = It's Saturday b = It's the weekend

Then your LHS suggests 1) it's not Saturday and 2) if it's Saturday then it's the weekend

This does not imply that it's not the weekend! It could be Sunday.

Answer 2

$\neg a \wedge (\neg a \vee b) $ can be rewritten as $(\neg a \vee \neg a) \wedge (\neg a \vee b)$. Now for the implication in question to be false, $\neg b$ needs to be false, so $b$ is true. Assuming $b$ is true, we can get $(\neg a \vee \neg a) \wedge (\neg a \vee b)$ to be true when $a$ is false. So when $a$ is false and $b$ is true, we get that the overall implication in question is false. Thus, we find that your statement is not a tautology.

Answer 3

Since $a\to b$ is equivalent to $\neg a\lor b$, your statement is $\neg a\to\neg b$ or equivalently $b\to a$, which is clearly not a tautology.

Answer 4

Your formula must be wrong as it is showing not to be a tautology, are you sure you coped it correct?

Answer 5

There is a simple way of checking if an implication is a tautology. We have to establish that the given proposition is false.

If we have $A\to B $, then this is false only when $B$ is false and $A$ is true.

$ (¬a ∧ (a → b)) \to ¬b\;$can be re-interpreted in the above manner by assuming

• $B$ is equivalent to $¬b$. We want to consider the case when B is false. If B is false, then b must be true.
• $A$ is equivalent to $ (¬a ∧ (a → b))$. We want to prove that A is true.

We know that $b$ is true from $B$. So for $a\to b$ is always true. Just by considering $a$ to be true, we get $T∧T$ which evaluates to True.

So we have the case where $A\to B$ is false when $a$ is true and $b$ is true. Hence we can prove by contradiction that $ (¬a ∧ (a → b)) \to ¬b\;$ is not a tautology.