# Law of Excluded Middle in Logic Proof

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. – 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

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. – yunone Apr 2 '11 at 0:19
show 2 more comments

## 2 Answers

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.

-
yunone, can you please teach me how you used those characters to post this answer? Thanks! – KerxPhilo Apr 2 '11 at 0:17

2
– 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

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. – 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 6, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.915499746799469, "perplexity_flag": "middle"}