# needs help with logic Homework

1. Philosophy Forum
2. » Logic
3. » needs help with logic Homework

Wed 10 Dec, 2008 10:32 pm
I got the following proof wrong in class and I could use some help solving it:

-(-P v -Q) therefore (P & Q)

(Moderator edit: post moved to more appropriate forum.jgw)

kennethamy

Thu 11 Dec, 2008 10:51 am
@bettydlgc,
bettydlgc wrote:
I got the following proof wrong in class and I could use some help solving it:

-(-P v -Q) therefore (P & Q)

(Moderator edit: post moved to more appropriate forum.jgw)

It follows by De Morgan's Law.

VideCorSpoon

Thu 11 Dec, 2008 12:34 pm
@kennethamy,
Kennethamy is right in that it is a replacement rule for DeMorgans. But there is a little problem with it.

Your translation of DeMorans looks like this;
-(-P v -Q) therefore (P & Q)

The ~(~P v ~Q) is correct, this is an acceptable starting point for DeMorgans. However the issue lies in the replacement formula that follows.

DeMogans goes as follows.

~(P v Q) may replace or be replaced by ~P & ~Q
~(P & Q) may replace or be replaced by ~P v ~Q

So whenever you want to use DeMorgans law, you have to exchange the ampersand with the wedge or the wedge with the ampersand, negate each side of of the ampersand or wedge, and negate the formula as a whole.

So the correct replacement should have been:
-(-P v -Q), therefore -P & -Q

kennethamy

Thu 11 Dec, 2008 01:34 pm
@VideCorSpoon,
VideCorSpoon wrote:
Kennethamy is right in that it is a replacement rule for DeMorgans. But there is a little problem with it.

Your translation of DeMorans looks like this;
-(-P v -Q) therefore (P & Q)

The ~(~P v ~Q) is correct, this is an acceptable starting point for DeMorgans. However the issue lies in the replacement formula that follows.

DeMogans goes as follows.

~(P v Q) may replace or be replaced by ~P & ~Q
~(P & Q) may replace or be replaced by ~P v ~Q

So whenever you want to use DeMorgans law, you have to exchange the ampersand with the wedge or the wedge with the ampersand, negate each side of of the ampersand or wedge, and negate the formula as a whole.

So the correct replacement should have been:
-(-P v -Q, )therefore -P & -Q

I have not done this stuff for a long time, but either you are mistaken, or I have forgotten De Morgan's. To use De Morgan's on -(-P v -Q, ) we change the sign, and remove all the negations. De Morgan's allows us to move the negation through the parenthesis as long as we change the sign.

VideCorSpoon

Thu 11 Dec, 2008 03:25 pm
@kennethamy,
DeMorgans allows us to derive something bi-equivalent with what has been replaced, hence it is a replacement rule. DeMorgans is basically the same thing as saying something which is the same topic, but in a different way.

So take what I had said was DeMorgans rule, namely ~(P&Q) is equivalent to ~Pv~Q. Translated into syntactics, "Alan and Bill are both not at home" [i.e. ~(P&Q)] is the same as saying "Either Alan is not home or Bill is not at home" [i.e. ~P v ~Q].

If we do change it the way you suggest, namely change the sign and remove all the negations, we will end up with a non-equivalent replacement. When translated, we come up with P v Q, the same as saying "Either Alan or Bill are not at home."

Is "Alan and Bill are both not at home" the same as saying "Either Alan or Bill are not at home?"

jknilinux

Wed 24 Dec, 2008 08:15 pm
@bettydlgc,
bettydlgc wrote:
I got the following proof wrong in class and I could use some help solving it:

-(-P v -Q) therefore (P & Q)

(Moderator edit: post moved to more appropriate forum.jgw)

I'm pretty sure applying DeM to ~(~P*~Q) will give you ~~P*~~Q, not P*Q, so you need to do a little extra work:

1: ~(~Pv~Q)
2: ~~P * ~~Q 1, DeM
3: ~~P 2, Simp
4: ~~Q 2, Simp
5: P 3, DN
6: Q 4, DN
7: P*Q 5,6 Conj

kennethamy

Thu 25 Dec, 2008 02:31 am
@VideCorSpoon,
VideCorSpoon wrote:
DeMorgans allows us to derive something bi-equivalent with what has been replaced, hence it is a replacement rule. DeMorgans is basically the same thing as saying something which is the same topic, but in a different way.

So take what I had said was DeMorgans rule, namely ~(P&Q) is equivalent to ~Pv~Q. Translated into syntactics, "Alan and Bill are both not at home" [i.e. ~(P&Q)] is the same as saying "Either Alan is not home or Bill is not at home" [i.e. ~P v ~Q]

If we do change it the way you suggest, namely change the sign and remove all the negations, we will end up with a non-equivalent replacement. When translated, we come up with P v Q, the same as saying "Either Alan or Bill are not at home."

Is "Alan and Bill are both not at home" the same as saying "Either Alan or Bill are not at home?"

Sorry. You are right. I am wrong. I miswrote.

jknilinux

Thu 25 Dec, 2008 10:40 pm
@kennethamy,
Do you guys think we need the extra steps I added?

Theaetetus

Fri 26 Dec, 2008 07:07 am
@VideCorSpoon,
VideCorSpoon wrote:

Is "Alan and Bill are both not at home" the same as saying "Either Alan or Bill are not at home?"

Isn't that saying two different things? In the first sentence both Alan and Bill are not home, but in the second it suggests that either one of the two are not home, leaving open the option that Alan or Bill could be potentially at home.

kennethamy

Fri 26 Dec, 2008 07:28 am
@Theaetetus,
Theaetetus wrote:
Isn't that saying two different things? In the first sentence both Alan and Bill are not home, but in the second it suggests that either one of the two are not home, leaving open the option that Alan or Bill could be potentially at home.

Yes it is. That's why what I posted is a mistake.

kata

Wed 21 Jan, 2009 10:01 pm
@bettydlgc,
typos are dangerous when doing logic
Quote:

DeMogans goes as follows.

~(P v Q) may replace or be replaced by ~P & ~Q
~(P & Q) may replace or be replaced by ~P v ~Q

So whenever you want to use DeMorgans law, you have to exchange the ampersand with the wedge or the wedge with the ampersand, negate each side of of the ampersand or wedge, and negate the formula as a whole

So the correct replacement should have been:
-(-P v -Q, )therefore -P & -Q

the stated rules are correct and his verbal explication also makes sense, but I don't see how he concludes that -(-P v -Q), therefore -P&-Q is the right replacement, following your own procedure(I use ~ instead of - because it's clearer):
1)exchange wedge with ampersand ~(~P v ~Q) -> ~(~P & ~Q)
2)negate each side of the ampersand -> ~(~~P & ~~Q)
3)negate the formula as a whole -> ~~(~~P & ~~Q)
the double negations cancel and you have (P & Q)
[of course saying that the double negations cancel is not enough for a complete PROOF which is what the OP was originally asking for]
[because demorgans law is a replacement rule you wouldn't show 1) and 2) in your proof, that is just the procedure for replacement]
so after 3) you would have to simplify in steps
4)~~P & ~~Q
5)~~P
6)P
7)~~Q & ~~P
8)~~Q
9)Q
finally conjoin 6) and 9) into
10) P & Q
(this replaces by taking the right side of the demorgans law and replacing it with the left, which in this case is rather unwieldy; to go from left to right in the relation rule, which is cleaner, see jknilinux's proof, note where he writes "~(~P*~Q) will give you ~~P*~~Q, not P*Q", he must have meant "~(~Pv~Q) will give you ~~P*~~Q, not P*Q"

VideCorSpoon

Wed 21 Jan, 2009 11:28 pm
@kata,
I completely agree, typos are dangerous when doing logic. Mistakes can hamper an entire proof if they are careless enough.

Unfortunately, I do not agree with your inference of DeMorgans at all. DeMorgans is non-negotiable. In propositional logic, there are a set inference and replacement rules. There are 8 standard (truth functional) inference rules, 10 truth-functional replacement rules, and 2 standard truth functional assertive proofs (i.e. indirect and conditional proofs). DeMorgans law (syntactical bi-equivalence in the formula) has, is, and forever will be ~(P v Q) may replace or be replaced by ~P & ~Q (OR) ~(P & Q) may replace or be replaced by ~P v ~Q. This is how it has always been in propositional logic. All websites dealing with replacement rules will have this law down as such in one way or another. Propositional books by Herrick, Prospesel, and Bergmann all have the same formula.

Demorgans is not DeMorgans shares the same arena with replacement rules such as Distribution, Exportation, and Tautology.

There is no reason to go through your proof, which lacks a heading premise(s) and a conclusion at the beginning to set up the proof, because one of possible matching combinations of DeMorgans automatically implies (for all intensive purposes) the bi-equivalent combination.

Also, in your proof when you double negation replacement rule, you double negate everything, not simply negate it. Line 2 is incorrect. Think about it. ~~P is the same as saying P. This is double negation. The simple single negation inference does not exist.

kata

Thu 22 Jan, 2009 12:48 am
@VideCorSpoon,
as you wrote in your post for the correct replacement:
Quote:
-(-P v -Q, )therefore -P & -Q

let's just test this using a truth table:

~P ~Q (~P v ~Q) ~(~P v ~Q) ~P&~Q P Q P&Q
T T T F T F F F
T F T F F F T F
F T T F F T F F
F F F T F T T T

how can we replace ~(~P v ~Q) with ~P&~Q if they have different truth values?

kennethamy

Thu 22 Jan, 2009 04:28 am
@kata,
kata wrote:
as you wrote in your post for the correct replacement:

let's just test this using a truth table:

~P ~Q (~P v ~Q) ~(~P v ~Q) ~P&~Q P Q P&Q
T T T F T F F F
T F T F F F T F
F T T F F T F F
F F F T F T T T

how can we replace ~(~P v ~Q) with ~P&~Q if they have different truth values?

Right. Try (P & Q) as a replacement.

VideCorSpoon

Thu 22 Jan, 2009 06:45 am
@kennethamy,
Kata,

The truth table that you are formulating is not correct. Individual truth tables have to be developed in order find the truth value of each permutation of DeMorgans. When they are done correctly, they look something like this.

In the ~(PvQ) truth table, all of the formal truth value translations have been done. The negation is the primary symbol to base our general truth value for the table. The rule for a disjunction states that a "disjunction is false when both disjuncts are false." With this done and then negated, the general truth value is F,F,F,T. In the ~P&~Q, we extrapolate the truth values and apply the law "a conjunction is true only if both conjuncts are true" and come up with exactly the same truth values as the bi-equivalent translation ~(PvQ).

So in response to your question... we can replace them becuase they have the same truth value.

Kennethamy,

At what point are you using P&Q as a replacement?

kennethamy

Thu 22 Jan, 2009 09:21 am
@VideCorSpoon,
VideCorSpoon wrote:
Kata,

The truth table that you are formulating is not correct. Individual truth tables have to be developed in order find the truth value of each permutation of DeMorgans. When they are done correctly, they look something like this.

In the ~(PvQ) truth table, all of the formal truth value translations have been done. The negation is the primary symbol to base our general truth value for the table. The rule for a disjunction states that a "disjunction is false when both disjuncts are false." With this done and then negated, the general truth value is F,F,F,T. In the ~P&~Q, we extrapolate the truth values and apply the law "a conjunction is true only if both conjuncts are true" and come up with exactly the same truth values as the bi-equivalent translation ~(PvQ).

So in response to your question... we can replace them becuase they have the same truth value.

Kennethamy,

At what point are you using P&Q as a replacement?

Before I negated the whole expression. Sorry.

1. Philosophy Forum
2. » Logic
3. » needs help with logic Homework