Duality (mathematics)#Duality in logic and set theory

Two statements of classical propositional logic are referred as dual to each other if they have opposite truth values ​​for each assignment of atomic propositions occurring in them. Conversely, dual statements accurately then the same truth- value as the atomic propositions occurring in them are occupied with opposite truth values.

Syntactic definition

For statements in negation normal form, ie for statements in which as connectives only conjunctions, disjunctions and negations occur and in which only atomic propositions are negated, can be a simple syntactic definition of duality specify:

Since it can form a negation normal form for each statement, this definition provides a syntactic method to each statement to form a dual statement: It is a negation normal form and to replace any occurring therein by, and vice versa.

For example, to form a dual to statement is molded first in a normal form of the negation, such as. After replacing by and, conversely, the statement is created, and this is the dual of the original statement.

Elementary dualities

Five duality theorems

Duality of conjunction and disjunction

Is a compound statement consisting only of conjunctions, disjunctions and negations (but need not be a negation normal form ). The one link that arises because in all the conjunctions are swapped with the disjunctions and vice versa, then dual.

Example: is dual to

Duality and negation

If a statement is, we obtain a dual link when all the variables and all the link itself negated.

Examples: must be dual; must be dual.

Duality in tautology and contradiction

If a statement is a tautology, then the dual to her statement is a contradiction, and vice versa.

Example: is a contradiction ( always false ), so the dual tautology (always true).

Duality and implication

A statement if and only implies a statement if one (and hence any ) to a dual statement (and thus any ) implied to dual statement.

Example: if and only if dual applies.

Duality and equivalence

A statement is then exactly equivalent to a statement if one (and hence any ) to dual statement is also equivalent to (and therefore any ) to the dual statement.

Example: if and only if dual applies.