Good day, I'm currently studying for an exam and need to learn about propositional logic. Well, since I'm not good at English I'll just write what I've done so far:

$(A \land (B \rightarrow \neg A)) \rightarrow \neg B$

I started like this:

$(A \land (\neg B \lor \neg A)) \rightarrow \neg B$

$\neg (A \land (\neg B \lor \neg A)) \lor \neg B$

$\neg A \lor \neg (\neg B \lor \neg A)) \lor \neg B$

$\neg A \lor (B \land A) \lor \neg B$

$\neg A \lor \neg B \lor (B \land A) $

And I think it is the same as:

$( \neg A \lor A) \land (\neg B \lor B) $

Am I on the right road? Because I'm really not sure anymore. However, I think this is a tautology.

  • 1
    $\begingroup$ You are definitely on the right road, but you missed the first exit, namely to rewrite the third line as $(\neg A \lor \neg B) \lor \neg(\neg A \lor \neg B)$. $\endgroup$ – Lord_Farin Jun 27 '13 at 9:41

Well, in this style of argument, why not proceed from your fourth line

$$\neg A \lor (B \land A) \lor \neg B$$

by rearranging

$$(B \land A) \lor \neg B \lor \neg A$$


$$(B \land A) \lor \neg(B \land A)$$

which is of the form

$$\varphi \lor \neg\varphi$$

and hence a tautology. So the original wff is a tautology as you wanted to show.

| cite | improve this answer | |
  • $\begingroup$ I didn't really understand how the step from your 2nd line to the 3rd line was done, because I think the second line doesn't already show it is a tautology (e.g. if A or B is true and one isn't). But when rearranging it to line #3 it makes sense since it's either true or false then and hence a tautology. Accepted since I got it now, I think. $\endgroup$ – beta Jun 27 '13 at 9:48
  • 3
    $\begingroup$ @beta He just used $\neg B\lor \neg A\equiv \neg (B\land A)$, which is something you know. $\endgroup$ – Git Gud Jun 27 '13 at 9:49

You’re approaching it in a reasonable way. Essentially the same approach can be organized a bit more clearly. I’ll start by simplifying part of the expression:

$$\begin{align*} A\land(B\to\neg A)&\equiv A\land(\neg B\lor\neg A)\\ &\equiv(A\land\neg B)\lor(A\land\neg A)\\ &\equiv(A\land\neg B)\lor\bot\\ &\equiv A\land\neg B\;, \end{align*}$$

where $\bot$ is a symbol for a contradiction, something that’s always false; you may be accustomed to writing F or the like instead. Then

$$\begin{align*} \big(A\land(B\to\neg A)\big)\to\neg B&\equiv(A\land\neg B)\to\neg B\\ &\equiv\neg(A\land\neg B)\lor\neg B\\ &\equiv(\neg A\lor\neg\neg B)\lor\neg B\\ &\equiv(\neg A\lor B)\lor\neg B\\ &\equiv\neg A\lor(B\lor\neg B)\\ &\equiv\neg A\lor\top\\ &\equiv\top\;, \end{align*}$$

where $\top$ is a symbol for a tautology, something that is always true.

Note that you can always determine whether a propositional expression is a tautology by using a truth table; this can be a useful check even when you’re required to produce an algebraic argument.

| cite | improve this answer | |
  • $\begingroup$ Hm this sounds clear too, but is (the symbol T) a valid mathematical description? Because it looks easier to explain it that way. Many thanks already for the elegant solution. $\endgroup$ – beta Jun 27 '13 at 9:50
  • 1
    $\begingroup$ Actually you could even have omitted the step from $\lnot\lnot B$ to $B$, because without it you'd just get the tautology $(\lnot B)\lor\lnot(\lnot B)$. $\endgroup$ – celtschk Jun 27 '13 at 10:04
  • 1
    $\begingroup$ @beta: It depends on your formalism, but it's certainly one very common way to do it. $\endgroup$ – Brian M. Scott Jun 27 '13 at 10:45
  • 1
    $\begingroup$ @celtschk: I could have done, but in practice I'd have gone straight to $B$ anyway, and years of watching students get themselves into trouble because they wouldn't simplify anything until the end of a computation have left their mark! $\endgroup$ – Brian M. Scott Jun 27 '13 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.