Naural deduction, rule for negated conjunction

427 Views Asked by At

Can

$$\neg B$$

Be directly deduced from $$\neg(A \wedge B) $$

By using the conjunction elimination rule? There does not seem to be any information on how to deal with the negation in the rules I have seen, but I can't figure any other way to derive the result than by directly applying the conjunction elimination rule.

4

There are 4 best solutions below

0
On

No, it cannot. $\neg (A \wedge B)$ is equivalent (by DeMorgan's law) to $\neg A \vee \neg B$. And you cannot deduce $\neg B$ from $\neg A \vee \neg B$. For instance, if $A$ is "$x$ is prime" and $B$ is "$x$ is even" then $\neg (A \wedge B)$ is the statement "it is not the case that both $x$ is prime and $x$ is even." We cannot deduce from this $\neg B$, which is the statement "$x$ is not even" i.e. "$x$ is odd" because, for instance, $x$ could be $4$.

2
On

Since $\lnot(A\land B) \Leftrightarrow \lnot A \lor \lnot B$, the conjunction elimination rule is not applicable.

0
On

No. You have $\lnot(A \land B)$. I.e., not both $(A \land B)$.

$$\lnot(A\land B) \not\equiv (\lnot A \land \lnot B)$$

You can prove $\lnot B$ from $(\lnot A \land \lnot B)$, but you do not have $(\lnot A \land \lnot B)$.

In fact you have $\lnot (A\land B) \equiv (\lnot A \lor \lnot B)\tag{by DeMorgan's rule}$

That is, you have a disjunction of two negated propositions.

You cannot directly deduce $\lnot B$ from $(\lnot A \lor \lnot B)$; all you know from that statement is that at least one of the disjuncts, (but NOT NECESSARILY both disjuncts) in $(\lnot A \lor \lnot B)$ is true.

In order to deduce $\lnot B$ from $(\lnot A \lor \lnot B)$, you'd need to have other information; for example, if you were also given a premise stating $A$, noting that $A \equiv \lnot\lnot A$, then you would be able to work your way to deducing $\lnot B$

(Note: See the Wikipedia entry for DeMorgan's Rules

0
On

No. Just fill in something for $A$ and $B$, for example take:

$A$: I am blue

$B$: I am a cube

Then $\neg(A \wedge B)$ means that it is not true that I am a blue cube. But does that mean that I am not a cube at all (which would be $\neg B$)? No, I could be a red cube, for example.

It is always a good idea to try and find counterexamples like this to any kind of logical inference: see if you can come up with a scenario that makes the givens true, but the inferred statement false. If you can find such a counterexample, then the inference is not valid. (if you can't find a counterexample, well, ... then either the inference is correct ... or you just didn't try hard enough in finding a counterexample!)

My point is: just because you are dealing with logical symbols and logical inference rules defined over those symbols should not mean that you can just stop thinking about what the statements mean informally.