---
name: De Morgan transformations
---
# De Morgan's laws

Two identities, due to Augustus De Morgan, written for over a
century in every textbook of formal logic, and the single most
useful pair of equations a working programmer can know.

> **¬(a ∧ b) ≡ ¬a ∨ ¬b**
>
> **¬(a ∨ b) ≡ ¬a ∧ ¬b**

In words: pushing a `not` through a parenthesised expression flips
every operator inside (`∧` becomes `∨`, `∨` becomes `∧`) and
negates each operand. Equivalently: pulling a `not` out flips
every operator and removes the negations on the operands.

## Why this matters in Perl

`unless` is the canonical case. `unless (X)` is `if (!X)` — and the
moment `X` is itself a compound, you have a leading `not` over a
parenthesised expression: exactly the De Morgan setup.

```perl
unless ($a == $x && $b == $y) { ... }
```

The condition under the `unless` is `!($a == $x && $b == $y)`.
Apply De Morgan: this is `!($a == $x) || !($b == $y)`. Each `!=`
is the negation of the corresponding `==`, so the clean form is:

```perl
if ($a != $x || $b != $y) { ... }
```

Three transformations happened, each mechanical:

1. `unless` flipped to `if` (the outer `not`).
2. `&&` flipped to `||` (De Morgan, inside).
3. `==` flipped to `!=` on each operand (the negations De Morgan
   placed on the operands cancel into the opposite comparison).

This is *not* a stylistic preference. Every programmer who has
debugged a wrong condition has stared at `unless (! ... && ...)` for
a minute too long; the flat `if` reads in one pass.

## A worked example

A real shape, slightly tangled:

```perl
unless ($x !~ /^\d+$/ && $y !~ /^[a-z]+$/) {
    print "at least one of \$x and \$y looks valid\n";
}
```

This says: *unless* `$x` is non-numeric and `$y` is non-alphabetic,
print. Five negations stacked across two lines. Walk through it:

The condition under the `unless` is

```
!( $x !~ /^\d+$/  &&  $y !~ /^[a-z]+$/ )
```

De Morgan flips the `&&` to `||` and negates each side:

```
!($x !~ /^\d+$/)  ||  !($y !~ /^[a-z]+$/)
```

`!($x !~ ...)` is just `$x =~ ...` (double negation of a regex
match). Same for the right side:

```
$x =~ /^\d+$/  ||  $y =~ /^[a-z]+$/
```

So the cleaned-up version is:

```perl
if ($x =~ /^\d+$/ || $y =~ /^[a-z]+$/) {
    print "at least one of \$x and \$y looks valid\n";
}
```

Five negations down to zero. The condition now reads exactly the
way the comment said it: *if `$x` is numeric or `$y` is alphabetic*.

## The same trick for OR

The second form of the law is the symmetric case:

```perl
unless ($a == 0 || $b == 0) { divide($a, $b) }
```

becomes

```perl
if ($a != 0 && $b != 0) { divide($a, $b) }
```

— same mechanical steps, only this time the inner operator is `||`
flipping to `&&`.

## NAND, NOR — same identity, read the other way

The NAND row in the truth table from the previous chapter has two
entries in the "Perl idiomatic" column:

```
14  NAND   !($a && $b)   /   !$a || !$b
```

These are equal *because of De Morgan's first law*. NAND is exactly
the negation of AND, and pushing the negation in flips the operator
and negates the operands. The NOR row works the same way for the
second law:

```
8   NOR    !($a || $b)   /   !$a && !$b
```

So De Morgan is not a separate fact you have to remember alongside
NAND and NOR — it *is* the identity that turns one spelling into
the other.

## Mechanics, in one paragraph

Negation distributes over `∧` and `∨` by flipping the connective
and negating each operand. Negation also self-cancels: `¬¬x ≡ x`.
The two rules together let you push a `not` arbitrarily deep, or
pull it arbitrarily out, of any expression built from `∧`, `∨`, and
`¬`. That is the whole content of De Morgan's laws — every
"convoluted unless" you ever rewrite is one application of those
two rules plus double-negation cancellation.

## Practical procedure

When you stare at a condition you don't like:

1. If the outer keyword is `unless`, prepend a `not` mentally and
   make it `if`.
2. If the leading `not` is over a parenthesised `&&` or `||`,
   distribute it: flip the connective, negate each operand.
3. If a subexpression is `!(x == y)`, replace with `x != y`. Same
   for `!~` ↔ `=~`, `!defined` ↔ `defined`, etc.
4. Stop when there are no more leading negations to push or no
   more double-negations to cancel.

In practice you will do all four steps in your head in a single
pass. The point of the procedure is that there is one — you are
not searching for the right form, you are deriving it.

## What you should remember from this chapter

- Two identities: pushing `¬` through `∧` flips it to `∨` (and
  vice versa) and negates each operand.
- Most "ugly `unless`" is one mechanical De Morgan flip away from a
  clean `if`.
- NAND and NOR are not extra facts; they are De Morgan's laws read
  as a pair of equivalent spellings.