Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was reading the following from a book of probability theory:

A contradiction $\bar{A}A$ implies all propositions, true and false. (Given any two propostions $A$ and $B$, we have $A\Rightarrow(A+B)$, therefore $\bar{A}A\Rightarrow\bar{A}(A+B)=\bar{A}A+\bar{A}B\Rightarrow B$.)

I understand these deductions except the last one. If $\bar{A}A$ is assumed to be true, then the validity of $\bar{A}B$ should be undetermined merely from $\bar{A}A+\bar{A}B$. Because whether $\bar{A}B$ is true or not, $\bar{A}A+\bar{A}B$ is true anyways. Am I right?

share|cite|improve this question
up vote 2 down vote accepted

Where do you get "If $\bar A A$ is assumed to be true" from?

The reasoning must be something like: Assume $\bar A A + \bar A B$, that is, at least one of $\bar A A$ and $\bar A B$ is true. But $\bar A A$ is never true, so it must be $\bar A B$ that is true. Then, in particular, $B$ is true.

This feels slightly circular, but that depends on exactly which logical axioms one already has (and it sounds vaguely like the book you quote from doesn't bother to present which logical axioms it starts from in the first place). However, if you already know "$\bar A A$ is always false", then this is a valid way of concluding $\bar A A \Rightarrow B$.

On the other hand, how do you know that $\bar A A$ is always false? If that is by truth tables, it would have been simpler to use truth tables to show that $\bar A A\Rightarrow B$ is a tautology.

On the other other hand, a "book of probability theory" is likely not intending to be a self-contained account of logic in general. I imagine that the history of the remark you quote must be that an early draft of the book just used the known fact that a contradiction implies everything, but that some readers in the test audience were confused because they didn't already know that. So the author inserted the briefest explanation that he had a reasonable expectation would satisfy those readers. A sceptical but non-sophisticated reader will probably agree that $\bar A A$ is always false, and will probably be accept reasoning about implication in the "assume such-and-such, then this-and-that" style. However, non-sophisticated readers have been known to balk and require extended explanations if presented with the actual truth table for $\Rightarrow$.

share|cite|improve this answer
But the author begin the deduction with "$\bar{A}A\Rightarrow...$", isn't that implying $\bar{A}A$ is assumed to be true? (Even though it cannot be in common sense.) – Voldemort Mar 24 '12 at 14:19
Oh, I counted that as the next-to-last step. Sorry for the confusion. It's a general rule that $X\Rightarrow Y$ implies $ZX\Rightarrow ZY$; this is being applied to $Z=\bar A$, $X=A$, $Y=A+B$. My answer was concerned with the final step $\bar A(A+B)\Rightarrow B$. – Henning Makholm Mar 24 '12 at 15:25
@Voldemort, Consider the (true) sentence "if you have a child, then your mother has a grandchild". This doesn't assert that you have a child; it only asserts the truth of the implication as a whole, i.e., a certain relationship between you having a child and your mother having a grandchild. The author must be using "$\Rightarrow$" in a similar way. As you note, it isn't technically possible for $\bar{A}A$ to be true, so you have to think in slightly different terms -- either syntactically (in terms of deductions) or in terms of sets of models. – Rachel Mar 25 '12 at 7:56

Maybe the following helps: try using the disjunctive syllogism. The law of non-contradiction tells us that $\overline{\overline{A}A}$ holds. Therefore we have $\overline{\overline{A}A}$ and $\overline{A}A+\overline{A}B$, so by the disjunctive syllogism we can conclude $\overline{A}B$. From this $B$ follows.

The thing is that in a theory where $\overline{A}A$ holds, we cannot reasonably assign truth values to statements, since each of them would have to be both true and false. Thus, reasoning about $\overline{A}A$ being "true" and deducing that $\overline{A}A+\overline{A}B$ must therefore be "true" independently of $B$ will become meaningless.

share|cite|improve this answer

It may be easier to see this in terms of semantic implication.

A semantic implication $A \models B$ means that in any model in which $A$ holds, so also must $B$.

Now, if $A$ is a contradiction, then there are no models in which $A$ holds. So, vacuously, in all such models $B$ holds.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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