DeMorgan's Rule

created by Tem42
(idea) by Tem42 (9.1 hr) (print)   (I like it!) Sat Nov 13 1999 at 14:55:37
DeM for short. Yet another rule uv inference in propositional logic. It's a rather complicated one.

~(P*Q) = (~P^~Q)
And
~(P^Q) = (~P*~Q)

"It is not the case that I have an apple and an orange" is the same as "I don't have an apple, or I don't have an orange"

And...

"It is not the case that I have an apple or and orange" is the same as "I don't have an apple, and I don't have an orange".

(These also work the other way around.)

See Everything Logic Symbols if you can't understand all this.

See also: DeMorgan's rule, Modus Ponens, commutativity

(idea) by Betsumei (2 wk) (print)   (I like it!) Fri Sep 19 2003 at 2:08:43

A handy way of remembering this rule is thus: "Break the line, change the sign"

You'll have to use your imagination on this. If I have ¬(A∧B), imagine that that is AB with a line over it. That is equivalent to ¬A∨¬B, which would be A with an overline and B with a separate overline. When the line is broken, the sign is switched. So if you had ¬(¬C∨D), the two overlines attached to C would counteract each other, breaking the line, and the result would be C∧¬D.

References: my Digital Systems teacher

Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.