17.7 De Morgan’s Laws

A contemporary of Boole’s, Augustus De Morgan, formalized two rules of logic that had previously been known informally. They allow us to rewrite the negation of a conjunction as a disjunction, and vice-versa.

For example, suppose you want to schedule a meeting with two colleagues at $4: 30 P M$ on Friday, and you need both of them to be available at that time. What situation would make it impossible to have the meeting? It is NOT the case that colleague $a$ is available AND colleague $b$ is available: $~ open parenthesis a ∧ b close parenthesis.$ /This situation is equivalent to either colleague $a$ NOT being available OR colleague $b$ NOT being available: $~ a ∨ ~ b$

Note

De Morgan's Laws

The negation of a conjunction is equivalent to the disjunction of the negation of the statements making up the conjunction. To negate an “and” statement, negate each part and change the “and” to “or”.

import itertools

def rows(expr, variables):
    # ~ is not, ^ is and, v is or.  eval runs with __builtins__ stripped and only the
    # variable names listed in `variables` in scope, so no other code can run.
    py = expr.replace("~", " not ").replace("^", " and ").replace(" v ", " or ")
    out = []
    for combo in itertools.product([True, False], repeat=len(variables)):
        out.append(eval(py, {"__builtins__": {}}, dict(zip(variables, combo))))
    return out

def compare(left, right, variables=("p", "q")):
    a, b = rows(left, variables), rows(right, variables)
    verdict = "EQUIVALENT" if a == b else "NOT equivalent"
    print(f"{left:<14} vs {right:<14}  {verdict}")
    head = "".join(f"{v:>4}" for v in variables) + f"{left:>16}{right:>16}"
    print("   " + head)
    for i, combo in enumerate(itertools.product([True, False], repeat=len(variables))):
        mark = "" if a[i] == b[i] else "   <- they disagree here"
        print("   " + "".join(f"{'T' if c else 'F':>4}" for c in combo)
              + f"{'T' if a[i] else 'F':>16}{'T' if b[i] else 'F':>16}{mark}")
    print()

# EDIT these pairs and re-run.
compare("~(p ^ q)", "~p v ~q")     # De Morgan, first law
compare("~(p v q)", "~p ^ ~q")     # De Morgan, second law
compare("~(p ^ q)", "~p ^ ~q")     # the tempting WRONG version
compare("~(p v q)", "~p v ~q")     # the other tempting wrong version

print("the meeting example: you need BOTH colleagues free.")
print("   the meeting is impossible when ~(a ^ b), i.e. when ~a v ~b:")
print("   one of them being busy is enough.\n")

print("three conditions to be President: born in the US (b), 35 or older (o), "
       "14 years resident (r)")
print("   qualified:   b ^ o ^ r")
print("   disqualified: ~(b ^ o ^ r) which is ~b v ~o v ~r - failing ANY ONE does it")
for combo in itertools.product([True, False], repeat=3):
    b, o, r = combo
    print(f"   born={str(b):<5} age={str(o):<5} resident={str(r):<5}  ->  "
          + ("qualified" if b and o and r else "disqualified"))

$~ open parenthesis p ∧ q close parenthesis$ is equivalent to $~ p ∨ ~ q$

The negation of a disjunction is equivalent to the conjunction of the negation of the statements making up the disjunction. To negate an “or” statement, negate each part and change the “or” to “and”.

$~ open parenthesis p ∨ q close parenthesis$ is equivalent to $~ p ∧ ~ q$

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.