LOGIC MAIN PAGE

LOGICAL OPERATORS

Sample sentences
AND operator
IF/THEN operator
NOT operator
OR operator
XOR operator

RULES OF LOGIC

Chain Rule
Contrapositive
DeMorgan's Law
Disjunctive Inference
Disjunctive Infer. (XOR)
Double Negation
Modus Ponens
Modus Tollens
Mutual Exclusion
Simplification

VALIDITY PROOFS

2-step
3-step
4-step
5-step or more

DeMorgan's Law

DeMorgan's law is a rule of inference pertaining to the NOT, AND, and OR operators.

DeMorgan's law is used to distribute a negative to a conjunction or disjunction.

Let us consider the following statement: "It is not true that he took both Core 5 and Physics 1." Formally, we would write:

~(C ^ P): "It is not true that he took both Core 5 and Physics 1."

In this expression, C refers to the phrase "He took Core 5" and P refers to the phrase "He took Physics 1."

DeMorgan's law states that this expression can be converted into another expression, completely equivalent to the original:

~C v ~P: "He did not take Core 5 or he did not take Physics 1."

To understand why, let's first see what the original statement "It is not true that he took both Core 5 and Physics 1" means. It can mean three things:

1. He took Core 5 but not Physics 1. (C is true and P is false, or ~P is true).

2. He took Physics 1 but not Core 5. (P is true and C is false, or ~C is true).

3. He did not take either Core 5 or Physics 1. (C is false and P is false, or ~P and ~C are true).

If we look closely at these three conclusions, we see that in all of them either ~P is true, or ~C is true, or both ~P and ~C are true. This is an example of a disjunction. Formally, we would write the following, together with the original statement:

~(C ^ P): "It is not true that he took both Core 5 and Physics 1."
----------
~C v ~P: "He did not take Core 5 or he did not take Physics 1."

That is exactly what DeMorgan's law means. The given expression ~(C ^ P) is above the line of dashes, and the new expression ~C v ~P formed by applying DeMorgan's law is below the line.

In our example, DeMorgan's law takes an expression with a conjunction and transforms it into a disjunction, negating each member of the expression. It also works in a similar way with a disjunction: A disjunction is converted into a conjunction with the negation of each member in the expression. Here is an example of a disjunction transformed into a conjunction:

~(P v Q): "It is not true that the book is boring or the newspaper is interesting."
----------
~P ^ ~Q: "The book is not boring and the newspaper is not interesting."

Furthermore, DeMorgan's law works both ways: We can convert an expression we just obtained by applying DeMorgan's law into the original one by the same law. Here are examples:

~C v ~P: "He did not take Core 5 or he did not take Physics 1."
----------
~(C ^ P): "It is not true that he took both Core 5 and Physics 1."

~P ^ ~Q: "The book is not boring and the newspaper is not interesting."
----------
~(P v Q): "It is not true that the book is boring or the newspaper is interesting."