De Morgan’s laws
In propositional logic and boolean algebra, De Morgan’s laws are a pair of transformation rules that are both valid rules of inference.
The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.
The rules can be expressed in English as:
The negation of a conjunction is the disjunction of the negations.
The negation of a disjunction is the conjunction of the negations.
or informally as:
“not (A and B)” is the same as “(not A) or (not B)”
“not (A or B)” is the same as “(not A) and (not B)”
The rules can be expressed in formal language with two propositions P and Q as:
De Morgan’s laws commonly apply to text searching using Boolean operators AND, OR, and NOT.
Consider a set of documents containing the words “cars” or “trucks”.
De Morgan’s laws hold that these two searches will return the same set of documents:
Search A: NOT (cars OR trucks)
Search B: (NOT cars) AND (NOT trucks)