Complicated Logic Proof involving Tautology and Law of Excluded Middle

Question

I'm having great difficulty solving the following problem, and even figuring out where to start with the proof. $$ \neg A\lor\neg(\neg B\land(\neg A\lor B)) $$ Please see the following examples of how to do proofs, I would appreciate it if you could attempt to give me guidance using the tools and the line numbers that it cites similar to those below:

This is a sample proof:

This is another sample proof (law of excluded middles):

Answer 1

first of all the statement is true (checking truth values for $A$ and $B$), even though ive now given two incorrect answers... here we go again!

$\begin{align} & \neg A \lor \neg (\neg B \land (\neg A \lor B))\\ & =\neg A \lor \neg [(\neg B \land \neg A) \lor (\neg B \land B)]\\ & =\neg A \lor \neg [(\neg B \land \neg A) \lor FALSE]\\ & =\neg A \lor \neg(\neg B\land\neg A)\\ & =\neg A\lor(B\lor A) \text{ using } \neg(X\land Y)=\neg X\lor\neg Y\\ & =TRUE \end{align}$

formalize this in whatever system youre using, you might have to prove a few things beforehand...

Answer 2

Boolean logic brings back fond memories in undergraduate classes in circuit theory. Anyway, using key terms: not, or, and, false, and true. I'll start by rewriting your assumption (and providing the logical justification for every step in parentheses).

1. not-A or not-(not-B and (not-A or B)) (assumption)
2. not-A or not-[(not-B and not-A) or (not-B and B)] (distribution and over or)
3. not-A or not-[(not-B and not-A) or (false)] (complementation over and)
4. not-A or not-(not-B and not-A) (complementation over or)
5. not-A or not-(not-(B or A)) (De Morgan's theorem)
6. not-A or (B or A) (double negation)
7. (not-A or A) or B (association over or)
8. (true) or B (complementation over or)
9. B (identity over or)

Sorry if this is badly formatted. I'm new here!

Answer 3

Seems like assuming the negation would give you a contradiction:

use ~ for 'negation', and & for 'and'; then your negated assumption becomes:

A&(~B&(~A\/B)) (Assumption)

From which you get:

~B&(~A\/B) (By & elimination)

I think you can show from here that your (negated) assumption leads to a contradiction, by arguing by cases, from ~A\/B, and showing neither case is possible.

Now, ~A\/B follows using a second & elimination. Show neither ~A nor B is possible from the premises in your negated statement. Then from ~A\/B and ~(~A) and ~B, a contradiction to your negated assumption follows.

Edit: this may be much simpler, tho yoyo's answer may be better than mine in that he gives a direct proof, and mine is by contradiction:

Assume the negation of your statement:

i)A& (~B&(~A\/B))

ii)Conclude A, by detachment.

iii)Conclude ~A by detachment inside of parenthesis.

iv)Negation of 'i)' follows by contradiction A&~A

Where detachment--more precisely, &-detachment-- is the rule that allows us to conclude either A, or B, from a statement A&B. To show it is a valid rule, you can either use a truth table to show it is a tautology/logical truth, derive it from the empty set of premises (this is the definition of theorem I am more familiar with), or,equivalently, show that the negation of either of :(A&B-->A) or of (A&B-->A), is a contradiction.For the second approach, assume A&B, and just conclude A (seems tautological, but it works; many of these arguments in sentence logic seem tautological anyway), or transform the implication A&B->A into the equivalent statement ~(A&B)\/A == ~A\/~B\/A== ~A\/A\/B==(~A\/A)\/B (I'm using here the result that A->B is truth-functionally equiv. to ~A\/B), which is a tautology.