Thread: de morgan's laws

1. de morgan's laws

I was looking through my old notes, trying to refresh my memory and I can't prove ~(A ^ B) -> (~A v ~B). Can anyone help? The rules I'm letting myself use are conjunctive addition, simplification, disjunctive addition, disjunctive syllogism, modus ponens, double negation. I can use indirect proof and conditional proof.

2. Originally Posted by jdc4
I was looking through my old notes, trying to refresh my memory and I can't prove ~(A ^ B) -> (~A v ~B). Can anyone help? The rules I'm letting myself use are conjunctive addition, simplification, disjunctive addition, disjunctive syllogism, modus ponens, double negation. I can use indirect proof and conditional proof.
You should not be asking for us to give a tutorial is logic. That is not what the forum is about.
If you have a specific question, then post it. We will try to help.

Having said that, here is some remarks on your first question.
$\displaystyle A \wedge B$ is true if and only if both A & B are true.
So if we negate that statement, $\displaystyle \neg \left( {A \wedge B} \right)$, then that means that at least one of the conjuncts is false.
That is $\displaystyle \neg A \vee \neg B$.
The converse relies upon $\displaystyle \neg (\neg A) \equiv A$.

3. Hi Plato, I wasn't asking for a tutorial. I was asking for someone to help me prove that theorem. I apologize if I wasn't clear. Thanks for the help, but I can tell that it's valid. I want to prove it with those rules and I can't seem to do it tho I'm sure it can be done. Thats what I need help with.

4. Originally Posted by jdc4
Hi Plato, I wasn't asking for a tutorial. I was asking for someone to help me prove that theorem. I apologize if I wasn't clear. Thanks for the help, but I can tell that it's valid. I want to prove it with those rules and I can't seem to do it tho I'm sure it can be done. Thats what I need help with.
Then I must ask you: "What Rules?"

5. Modus ponens: from P and P -> Q, infer Q l Conjunctive addition: from P and Q, infer (P ^ Q) l Simplification: from (P ^ Q), infer P; from (P ^ Q) infer Q l Disjunctive addition: from P, infer (P v Q); from P, infer (Q v P) l Disjunctive syllogism: from (P v Q) and ~ P, infer Q; from (P v Q) and ~Q infer P l Double negation: from P, infer ~~P I can use both conditional proof and indirect proof.

6. Originally Posted by jdc4
Modus ponens: from P and P -> Q, infer Q l Conjunctive addition: from P and Q, infer (P ^ Q) l Simplification: from (P ^ Q), infer P; from (P ^ Q) infer Q l Disjunctive addition: from P, infer (P v Q); from P, infer (Q v P) l Disjunctive syllogism: from (P v Q) and ~ P, infer Q; from (P v Q) and ~Q infer P l Double negation: from P, infer ~~P I can use both conditional proof and indirect proof.
I am sorry to say, "What is the point of all of that?"
It seems that you know that. I certainly know it, having taught Symbolic Logic for years.
So what is you point or your question?

7. Well I tried proving it with those rules and I couldn't, and now it's kind of an obsession. It's hard to explain. When I try solving a problem and I can't, I want to know how it can be done. I'm sure it's actually very simple but for some reason I'm not getting it. I'd be surprised if it took more than 7-10 lines.

8. Originally Posted by jdc4
I was looking through my old notes, trying to refresh my memory and I can't prove ~(A ^ B) -> (~A v ~B). Can anyone help? The rules I'm letting myself use are conjunctive addition, simplification, disjunctive addition, disjunctive syllogism, modus ponens, double negation. I can use indirect proof and conditional proof.

Assume ~(A^B)............................................ .............................1

Assume A................................................. .................................2

Assume B for contradiction..................................... ........................3

A & B .....from (1) and (2) and using conjunctive addition , or differently called addition introduction...................................... .............................4

~(A^B) & (A^B) ......from (1) and (4) and using again conjunctive addition.......................................... .......................................5

~B...... BY applying contradiction from (3) to (5)............................6

A------>~B......BY applying the conditional proof rule from (2) to (6)............................................... ................................................7

Now by material implication rule ( pvq <-----> ~p---->q) we can convert

A------>~B INTO ~AV~B