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'm having some difficulty doing a proof for the following:

$$\neg A \vee \neg(\neg B \wedge (\neg A \vee B))$$

It is said that you could use the law of excluded middles.

Any help or guidance would be appreciated. Thanks in advance!

share|cite|improve this question
Are you just trying to simplify the expression given? Otherwise, I don't see what to prove. – yunone Apr 2 '11 at 0:05
@yunone: I think you have to prove that the expression is a tautology. – alejopelaez Apr 2 '11 at 0:09
I think you can just apply De Morgan's laws and the distributive laws, and arrive at a tautology of the form $A \vee \sim A$ – alejopelaez Apr 2 '11 at 0:10
@Pel, ah ok, thanks for the explanation. – yunone Apr 2 '11 at 0:14
@Kerx, you can right click on the characters and click show source. This will show you the typesetting code. Enclose these in $ to get them to format. For example, $\neg A \vee \neg(\neg B \wedge (\neg A \vee B))$ is what is written above. – yunone Apr 2 '11 at 0:19
up vote 6 down vote accepted

Consider this: $$ \begin{align*} \neg A\lor\neg(\neg B\land(\neg A\lor B)) &\equiv \neg A\lor(B\lor\neg(\neg A\lor B))\\ &\equiv \neg A\lor(B\lor (A\land\neg B)) \\ &\equiv \neg A\lor((B\lor A)\land(B\lor\neg B)) \\ &\equiv \neg A\lor((B\lor A)\land \top) \\ &\equiv \neg A\lor(B\lor A) \end{align*} $$ where $B\lor\neg B\equiv\top$ by the law of excluded middle. Applying it again should show the original expression is a tautology, which I believe is what you want to prove.

share|cite|improve this answer
yunone, can you please teach me how you used those characters to post this answer? Thanks! – KerxPhilo Apr 2 '11 at 0:17
@Kerx, see my comment on the original question. AOPS has a good reference for common symbols used in $\LaTeX$, I suggest googling it to see the basics. They are not hard to pick up as you go. Viewing the source for the math here is a good way to pick it up too. – yunone Apr 2 '11 at 0:22
thanks again! – KerxPhilo Apr 2 '11 at 0:24
I understand your proof. I guess the weird part is that in my logic course, we are using special ways to do our proofs. We use tools such as Conjunction Introduction, Elimination; Disjunction Introduction, Elimination; Contradiction Introduction, etc. And we have to cite the lines associated with them. – KerxPhilo Apr 2 '11 at 0:26
@kerx, I hope you can fill it in, as I've never really explicitly listed the tools I'm using, and I'm not too familiar with their names. I guess I first use De Morgan's laws, and double negative elimination in the first and second lines, distributivity of disjunction in the third, and eventually the domination laws. – yunone Apr 2 '11 at 0:32

Using distributivity,

$\neg A \bigvee \neg((\neg B \bigwedge \neg A) \bigvee (\neg B \bigwedge B))$ $\equiv \neg A \bigvee \neg (\neg B \bigwedge \neg A)$ $\equiv \neg A \bigvee (B \bigvee A)$ $\equiv \neg A \bigvee A$

as required.

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.