Law of Excluded Middle in Logic Proof

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.


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.

Tags:

Logic

Philosophy

Related

Finite field, every element is a square implies char equal 2 Fast algorithm for solving system of linear equations Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice? A question about cyclic groups Is there an intuitionist (i.e., constructive) proof of the infinitude of primes? Limits: How to evaluate $\lim\limits_{x\rightarrow \infty}\sqrt[n]{x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}}-x$ Sum of independent Binomial random variables with different probabilities Evaluating $\int P(\sin x, \cos x) \text{d}x$ Dijkstra's algorithm using heap Does repeated activity increase the probability of a specific event happening? Prove that the given set is bounded above in $\mathbb{Q}$ but does not have a Supremum in $\mathbb{Q}$ Direct proof that the wedge product preserves integral cohomology classes?

Recent Posts