4
$\begingroup$

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!

  • 1
    Are you just trying to simplify the expression given? Otherwise, I don't see what to prove.2011-04-02
  • 0
    @yunone: I think you have to prove that the expression is a tautology.2011-04-02
  • 0
    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$2011-04-02
  • 0
    @Pel, ah ok, thanks for the explanation.2011-04-02
  • 0
    Can someone please teach me how you edited my post to use those characters instead of the ones I was using?2011-04-02
  • 2
    @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.2011-04-02
  • 0
    yunone, thank you very much.2011-04-02

2 Answers 2

6

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.

  • 0
    yunone, can you please teach me how you used those characters to post this answer? Thanks!2011-04-02
  • 2
    @Kerx, see my comment on the original question. [AOPS has a good reference for common symbols](http://www.artofproblemsolving.com/Wiki/index.php/LaTeX: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.2011-04-02
  • 0
    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.2011-04-02
  • 1
    @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.2011-04-02
1

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.