Duality (logic)

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

No further literature is given and there is no individual reference. Lecture slides are not sufficient.

Two statements of classical propositional logic are referred to as dual to each other if they have opposite truth values for each assignment of the atomic statements that occur in them . Conversely, dual statements have exactly the same truth value when the atomic statements that occur in them are assigned opposite truth values.

${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\land B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\lor B}$ W. W. W. F. F. F. W. F. F. F. W. W. F. W. F. W. F. W. F. F. F. W. W. W.

Example: If one replaces the truth values ​​of and by their opposite in each line of the truth value table of the conjunction , then one obtains the truth value table of the disjunction . See also De Morgan's Laws . ${\displaystyle A}$ ${\displaystyle B}$

Syntactic definition

For statements in negation normal form , i.e. for statements in which only conjunctions , disjunctions and negations occur as connectives and in which only atomic statements are negated, a simple syntactic definition for duality can be given:

Two statements and are dual if and only if every occurrence of the join (conjunction) is replaced by (disjunction) and if every occurrence of the join is replaced by. ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \lor }$ ${\displaystyle \land }$

Since a normal negation form can be formed for every statement, this definition provides a syntactic procedure for creating a dual statement for every statement : A normal negative form is created and every one that occurs is replaced with and vice versa. ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \land }$ ${\displaystyle \lor }$

For example, in order to form a statement that is too dual, it is first transformed into a negation normal form, such as . After replacing by and vice versa, the statement arises , and this is dual to the original statement. ${\displaystyle A\rightarrow (B\vee C)}$ ${\displaystyle (\neg A\lor B)\lor C}$ ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle (\neg A\land B)\land C}$

Elementary dualities

1. ${\displaystyle A}$is dual to  ; is dual to  ; ${\displaystyle A}$ ${\displaystyle {\overline {A}}}$ ${\displaystyle {\overline {A}}}$
2. ${\displaystyle ~A~\land ~B}$is dual to  ; ${\displaystyle A~\lor ~B}$
3. ${\displaystyle ~A~\rightarrow ~B}$is dual to  ; ${\displaystyle ~{\overline {B~\rightarrow ~A}}}$
4. ${\displaystyle ~A~\leftrightarrow ~B}$is dual to (exclusive disjunction); ${\displaystyle A~{\dot {\lor }}~B}$

Five sets of duality

Hasse diagram showing all combinations made from two elementary statements. A black “connecting line” between two statements indicates that the lower statement implies the upper statement. These connecting lines should be thought of as going beyond the interim statements.
The blue arrows mark the transition to the dual element. You can see that this transition "flips" all implications.

Duality of conjunction and disjunction

${\displaystyle V_{1}}$be a compound statement that only consists of conjunctions, disjunctions and negations (but does not have to be a negation normal form). The connection that arises from the fact that the conjunctions with the disjunctions and vice versa are exchanged everywhere is then dual to . ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$ ${\displaystyle V_{1}}$

Example: is dual to ${\displaystyle (A\land \neg B)\lor C}$ ${\displaystyle (A\lor \neg B)\land C}$

Duality and negation

If there is a statement, a dual connection is obtained if all variables and the entire connection itself are negated. ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$

Examples: is dual to ; is dual to . ${\displaystyle A\leftrightarrow B}$ ${\displaystyle {\overline {{\overline {A}}\leftrightarrow {\overline {B}}}}}$ ${\displaystyle A\land (B\lor C)}$ ${\displaystyle {\overline {{\overline {A}}\land ({\overline {B}}\lor {\overline {C}})}}}$

Duality in tautology and contradiction

If a proposition is a tautology , the proposition dual to it is a contradiction and vice versa.

Example: is a contradiction (always false), so the dual is a tautology (always true). ${\displaystyle A\land B\land {\overline {A}}}$ ${\displaystyle A\lor B\lor {\overline {A}}}$

Duality and implication

A statement implies a statement if and only if a (and therefore every) statement that is too dual implies a (and therefore every) statement that is too dual. ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$

Example: if and only if dual applies: . ${\displaystyle (A\land B)\Rightarrow A}$ ${\displaystyle A\Rightarrow (A\lor B)}$

Duality and equivalence

A statement is equivalent to a statement if and only if a (and therefore every) statement that is too dual is also equivalent to a (and therefore every) statement that is too dual. ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$

Example: if and only if dual applies: . ${\displaystyle (A\land B)\Leftrightarrow (B\land A)}$ ${\displaystyle (A\lor B)\Leftrightarrow (B\lor A)}$

See also

• Duality (disambiguation)
• Boolean algebra

Web links

• Principle of duality in the script Introduction to computer engineering and digital technology (Helmut Dispert, Kiel University of Applied Sciences)
• Lecture slides propositional logic and gates (chapter "Duality" on page 9; PDF; 663 kB) in the documents for the lecture "Digital Circuit Technology" (Peter Fischer, University of Mannheim, summer semester 2006)