# Duality principle

Jump to: navigation, search

The duality principle in mathematical logic is a theorem on the acceptability of mutual substitution (in a certain sense) of logical operations in the formulas of formal logical and logical-objective languages. Let $A$ be a formula in the language of propositional or predicate logic not containing the implication symbol $\supset$; a formula $A ^ {*}$ is said to be dual to a formula $A$ if it may be obtained from $A$ by replacing in $A$ each occurrence (cf. Imbedded word) of the symbols $\&$, $\lor$, $\forall$, $\exists$ by their dual operations, i.e. by the symbols $\lor$, $\&$, $\exists$, and $\forall$, respectively. The duality principle states that if $A \supset B$ is true, then $B ^ {*} \supset A ^ {*}$ is true as well. In particular, if two formulas $A$ and $B$ are equivalent, their dual formulas $A ^ {*}$ and $B ^ {*}$ are equivalent too. The duality principle is valid for classical systems, and the equivalence and the truth of the formulas involved in its formulation may be understood both in terms of interpretations and in the sense of being deducible in the corresponding classical calculus. The duality principle is no longer valid if the formulas are understood in their constructive sense. For instance, in the language of propositional logic the implication $\neg A \& \neg B \supset \neg ( A \lor B )$ is constructively true, and is even deducible in a Heyting formal system, but the converse implication of the dual formula $\neg ( A \& B ) \supset \neg A \lor \neg B$ is constructively untrue (it is not Kleene-realizable).

The following theorem is closely connected with the duality principle: If $F ^ { * } ( A _ {1} \dots A _ {n} )$ is a formula dual to a propositional or predicate formula $F ( A _ {1} \dots A _ {n} )$ constructed without making use of implications from the elementary propositions $A _ {1} \dots A _ {n}$, then the formula $\neg F ( A _ {1} \dots A _ {n} )$ is equivalent to the formula $F ^ { * } ( \neg A _ {1} \dots \neg A _ {n} )$ in the classical propositional or predicate calculus, respectively.

## Contents

How to Cite This Entry:
Duality principle. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Duality_principle&oldid=46779
This article was adapted from an original article by F.A. Kabakov, A.S. Parkhomenko, M.I. Voitsekhovskii, T.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article