1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ have you tried using $p\rightarrow q$ is equivalent to $\neg p \vee q$? $\endgroup$
    – mathma
    May 28, 2017 at 8:02
  • $\begingroup$ Follow the hint above; then Distributivity, and De Morgan. $\endgroup$ May 28, 2017 at 10:25
  • $\begingroup$ Does direct proof mean truth table? Otherwise there is no such thing. $\endgroup$
    – DanielV
    May 28, 2017 at 12:28
  • $\begingroup$ What rules do you have? $\endgroup$
    – Bram28
    May 28, 2017 at 13:12
  • $\begingroup$ 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. $\endgroup$
    – DanielV
    May 28, 2017 at 15:26

2 Answers 2

1
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.