Disjunctive Infer. (XOR)
5-step or more
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
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."
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
~P ^ ~Q: "The book is not boring and the newspaper is
Links to Relevant Problems
These are links to validity proof problems whose solutions contain DeMorgan's law.