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.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ have you tried using $p\rightarrow q$ is equivalent to $\neg p \vee q$? $\endgroup$– mathmaMay 28, 2017 at 8:02
-
$\begingroup$ Follow the hint above; then Distributivity, and De Morgan. $\endgroup$– Mauro ALLEGRANZAMay 28, 2017 at 10:25
-
$\begingroup$ Does direct proof mean truth table? Otherwise there is no such thing. $\endgroup$– DanielVMay 28, 2017 at 12:28
-
$\begingroup$ What rules do you have? $\endgroup$– Bram28May 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$– DanielVMay 28, 2017 at 15:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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}
$\begingroup$
$\endgroup$
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}$$
