2
$\begingroup$

Given, $(A \lor B) \implies C$, prove $A \implies C$

My Proof:

1 By Conditional Exchange,

$$\neg(A \lor B) \lor C$$

2 By DeMorgan's Law,

$$(\neg A \land \neg B) \lor C$$

3 By Simplification,

$$\neg A \lor C$$

4 By Conditional Exchange,

$$A \implies C$$

My question pertains to steps 2 and 3. I used Demorgan's and Simplification on a subformula of a premise -- can I do that? Usually, I would separate the subformulas, but I don't think I could do so in this case.

Thanks.

$\endgroup$
  • $\begingroup$ Your steps look valid $\endgroup$ – J. W. Tanner Jul 26 '19 at 4:13
  • 1
    $\begingroup$ Alternative Proof: By disjunction, $A \implies A \vee B$. Since $A \vee B \implies C$, and since $A \implies A \vee B$, then $A \implies C$ by hypothetical syllogism. $\endgroup$ – JavaMan Jul 26 '19 at 4:24
  • $\begingroup$ My logic is rusty, so take this with a grain of salt: but I do not see the problem. You are asked to prove "If A, then C." so I do not see why you can't start by assuming $A$ is true. In math, to prove a statement of the form $P \implies Q$, it is perfectly valid to assume $P$ is true, since if $P$ is false, then $P \implies Q$ vacuously. If this is a rigorous (philosophical) logic course, then maybe I'm missing some details in logical formalism, so you could/should ask your teacher (or others here). $\endgroup$ – JavaMan Jul 26 '19 at 4:31
  • $\begingroup$ This isn't circular reasoning. Circular reasoning would be assuming that "$A \implies C$ is true to prove that $A \implies C$ is true. Here, you are really proving that $A \implies C$ using cases: whether $A$ is true or not. $\endgroup$ – JavaMan Jul 26 '19 at 4:35
3
$\begingroup$

No, you need to apply Distribution before Simplification. Simplification is not an equivalence, so cannot safely be applied to only part of a statement.

$$\begin{align} &(A\lor B)\to C &&\text{Premise} \\ \iff & \lnot(A \lor B)\lor C&& \text{Conditional Exchange}\\\iff & (\lnot A\land\lnot B)\lor C&&\text{de Morgan's}\\\iff &(\lnot A\lor C)\land(\lnot B\lor C)&&\text{Distribution}\\\implies &\lnot A\lor C&&\text{Simplification}\\ \iff & A\to C&&\text{Conditional Exchange} \end{align}$$

$\endgroup$
  • $\begingroup$ Thanks, it makes sense. Do you think you could give me a counterexample about directly applying simplification to a subformula? $\endgroup$ – N. Bar Jul 26 '19 at 4:22
  • 1
    $\begingroup$ The obvious case where substituting a weakening does not work is when the phrase is in an antecedent. $~~(A\land B)\to B$ does not imply $A\to B$. $\endgroup$ – Graham Kemp Jul 26 '19 at 4:34
1
$\begingroup$

DeMorgan's yes, since it is an equivalence. Simplification, not necessarily since it takes something to a weaker statement. (It is justified here since weakening a disjunct leads to a weaker statement, but it won't be true in general that weakening a subformula leads to a weaker statement.)

Instead, use distribution to get $(\lnot A\lor C)\land (\lnot B\lor C),$ and then use simplification to get $\lnot A\lor C.$

$\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.