# direct proof of propositional logic $B \vdash \neg(B \rightarrow (A \& \neg B))$

I got a tutorial question that I cant solve it...

the argument is this : $B \vdash \neg(B \rightarrow (A \& \neg B))$ I have to use direct proof...

any help would be appreciated.

• have you tried using $p\rightarrow q$ is equivalent to $\neg p \vee q$? May 28, 2017 at 8:02
• Follow the hint above; then Distributivity, and De Morgan. May 28, 2017 at 10:25
• Does direct proof mean truth table? Otherwise there is no such thing. May 28, 2017 at 12:28
• What rules do you have? May 28, 2017 at 13:12
• Intuitionistically, if $X \to Y$ cannot be proven, then $X \to (Y \land Z)$ cannot be proven. Further, $X \to \lnot X$ cannot be proven. @JackKim There isn't a standard / universal set of laws for logic, regardless of any impression your instructor may have given you to the contrary. Describe your logic or no one can help you. May 28, 2017 at 15:26

It helps to first put the conclusion in a form that's easier to prove:

\begin{array}{l} & \neg (B \to (A \land \neg B)) & \text{ Given }\\ & \neg (\neg B \lor (A \land \neg B)) & \text{ Material Imp. }\\ & B \land \neg (A \land \neg B) & \text{ DeMorgan }\\ & B \land (\neg A \lor B) & \text{ DeMorgan }\\ \end{array}

Then it can be proved as follows:

\begin{array}{l} & \{1\} & 1. & B & \text{ Prem. }\\ & \{1\} & 2. & \neg A \lor B & \text{ 1 $\lor$I }\\ & \{1\} & 3. & B \land (\neg A \lor B) & \text{ 1,2 $\land$I }\\ & \{1\} & 4. & B \land \neg (A \land \neg B) & \text{ 3 DM }\\ & \{1\} & 5. & \neg (\neg B \lor (A \land \neg B)) & \text{ 4 DM }\\ & \{1\} & 6. & \neg (B \to (A \land \neg B)) & \text{ 5 MI }\\ \end{array}

Here's the proof by natural deduction:

\begin{array}{l} & \{1\} & 1. & B & \text{ Prem. }\\ & \{2\} & 2. & A \land \neg B & \text{ Assum. }\\ & \{2\} & 3. & \neg B & \text{ 3 $\land$E }\\ & - & 4. & (A \land \neg B) \to \neg B & \text{ 2,3 CI }\\ & \{1\} & 5. & \neg (A \land \neg B) & \text{ 1,4 MT }\\ & \{6\} & 6. & B \to (A \land \neg B) & \text{ Assum. }\\ & \{1,6\} & 7. & A \land \neg B & \text{ 1,6 MP }\\ & \{1\} & 8. & (B \to (A \land \neg B)) \to (A \land \neg B) & \text{ 6,7 CI }\\ & \{1\} & 9. & \neg (B \to (A \land \neg B)) & \text{ 5,8 MT }\\ \end{array}

Before proceeding with the interference I would like to mention one handy tautological equivalence $$A \land (A \lor (X)) \leftrightarrow A \lor (A \land (X)) \leftrightarrow A$$ , where $X$ can be any atomic or compound sentence which results in true or false.

$$\begin{array}{l} & 1. & B & \text {Given}\\ & 2. & B \land (B \lor \neg A) & \text {Using the tautological equivalence asserted above}\\ & 3. & \neg \neg B \land \neg \neg (B \lor \neg A) & \text {Double negation}\\ & 4. & \neg (\neg B \lor \neg (B \lor \neg A)) & \text {De Morgan's Law}\\ & 5. & \neg (\neg B \lor (\neg B \land A)) & \text {Applying De Morgan's Law to \neg (B \lor \neg A)}\\ & 6. &\neg (B \to (\neg B \land A)) & \text {Equivalence for Implication and Disjunction } \end{array}$$