Skip to content
EN ES
Sign in Open the app

Lesson 6: De Morgan’s laws (intermediate, 12 min)

How to move a NOT through AND and OR without changing the meaning: negating a conjunction gives a disjunction of negations, and the other way round. Four steps, intermediate level, about twelve minutes, ending in negation normal form.

Level: intermediate12 min11 claims in this lesson were confirmed by the exact checker at build time

Push NOT through AND and OR correctly: negating a conjunction gives a disjunction of negations, and vice versa.

The first step negates a door rule: NOT (has_key AND knows_code) is NOT has_key OR NOT knows_code, the door stays shut when either is missing. The second negates an OR: NOT (member OR invited) is NOT member AND NOT invited, neither one nor the other. The third step is the classic slip, NOT A AND NOT B offered as the negation of A AND B, shown wrong on a specific row. The fourth applies the laws repeatedly to NOT ((A OR B) AND C), reaching NOT (A OR B) OR NOT C and then (NOT A AND NOT B) OR NOT C, where every NOT sits on an input.

The lesson carries five verified claims: both laws, the slip's non-equivalence, and the two rewriting steps of the nested example. The exercises ask you to push NOT inward in two expressions, to find the assignment that exposes the slip, and to classify NOT (A OR B) <-> (NOT A AND NOT B), which is a tautology because the law holds on every row.

Negation normal form, the end point of the fourth step, is the first stage of the engine's normal-form converter and of its NAND-only and NOR-only constructions; the De Morgan law page proves both identities and the pitfall pages on “not over AND” and “neither nor” are the two halves in isolation.

Do this lesson interactively in the app

Steps

1. NOT over AND

A door opens with the key and the code. It stays shut when that is not the case: NOT (has_key AND knows_code).

By De Morgan, this is the same as NOT has_key OR NOT knows_code: the door stays shut if either part is missing. The AND becomes an OR when the NOT moves inside.

stays_shut := NOT (has_key AND knows_code) · outputrewritten := NOT has_key OR NOT knows_code · output

has_key: the person has the key; knows_code: the person knows the code;

NOT over AND
#has_keyknows_codestays_shutrewritten
0FALSEFALSETRUETRUE
1FALSETRUETRUETRUE
2TRUEFALSETRUETRUE
3TRUETRUEFALSEFALSE

Compare stays_shut with rewritten: the checker proves them equivalent.

equivalent stays_shut / rewritten · holds

2. NOT over OR

“Neither a member nor invited” is NOT (member OR invited).

De Morgan’s second law: this equals NOT member AND NOT invited. The OR becomes an AND: neither … nor means that both are missing.

neither := NOT (member OR invited) · outputboth_missing := NOT member AND NOT invited · output

member: the person is a member; invited: the person has an invitation;

NOT over OR
#memberinvitedneitherboth_missing
0FALSEFALSETRUETRUE
1FALSETRUEFALSEFALSE
2TRUEFALSEFALSEFALSE
3TRUETRUEFALSEFALSE

Make neither TRUE. In how many of the four rows is it TRUE?

equivalent neither / both_missing · holds

3. The classic slip

It is tempting to “distribute” the NOT without flipping the operator, but NOT (A AND B) is not NOT A AND NOT B.

They disagree, for example, when A=TRUE, B=FALSE: the first gives TRUE, the slip gives FALSE. Whenever you move a NOT inside, swap AND and OR.

correct := NOT (A AND B) · outputslip := NOT A AND NOT B · output
The classic slip
#ABcorrectslip
0FALSEFALSETRUETRUE
1FALSETRUETRUEFALSE
2TRUEFALSETRUEFALSE
3TRUETRUEFALSEFALSE

Set A=TRUE, B=FALSE and compare correct with slip.

not-equivalent correct / slip · holds

4. Pushing NOT all the way in

Apply the laws repeatedly to reach negation normal form, where NOT sits directly on inputs:

NOT ((A OR B) AND C) → NOT (A OR B) OR NOT C → (NOT A AND NOT B) OR NOT C.

Each step is an equivalence, so the result is equivalent to the original, and Tangibool confirms it with an exact check.

original := NOT ((A OR B) AND C) · outputmiddle := NOT (A OR B) OR NOT C · outputpushed_in := (NOT A AND NOT B) OR NOT C · output
Pushing NOT all the way in
#ABCoriginalmiddlepushed_in
0FALSEFALSEFALSETRUETRUETRUE
1FALSEFALSETRUETRUETRUETRUE
2FALSETRUEFALSETRUETRUETRUE
3FALSETRUETRUEFALSEFALSEFALSE
4TRUEFALSEFALSETRUETRUETRUE
5TRUEFALSETRUEFALSEFALSEFALSE
6TRUETRUEFALSETRUETRUETRUE
7TRUETRUETRUEFALSEFALSEFALSE

Compare original with pushed_in, then try an intermediate step of your own.

equivalent original / middle · holdsequivalent original / pushed_in · holds

Exercises

  1. Rewrite NOT (member OR invited) so that NOT applies only to single inputs. (write-equivalent)
  2. Push the NOT in NOT (A AND (B OR NOT C)) all the way to the inputs. (write-equivalent)
  3. Show that the slip really is wrong: find an assignment where correct and slip differ. (find-assignment)
  4. Classify NOT (A OR B) <-> (NOT A AND NOT B). (classify)

Do this lesson interactively in the app

Questions

Do the laws work on three or more operands?

Yes: NOT (A AND B AND C) is NOT A OR NOT B OR NOT C, the whole chain flips at once. The engine applies the law to the n-ary gate in one step.

What is negation normal form for?

It is the shape every normal-form conversion starts from, and the shape in which a formula is easiest to read aloud: each NOT applies to one input. The fourth step produces it by hand; the converter does it for you.

Related

Laws

Tools

Practice

See also

Lessons

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build . Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.