Закон двойственности

Зако́н двойственности — закон математической логики, который гласит: «если формулы А и В равносильны, то и двойственные им формулы равносильны».

Американский логик А. Чёрч называет закон двойственности принципом дуальности (лат. dualis — двойной, двойственный) и выражает его символически следующим образом:

Если ⊢ A и если А1 — дуальная формула к правильно построенной формуле А, то ⊢ ~ А1, где ⊢ — знак выводимости, ~ — знак отрицания. Читается эта запись так:

«Если выводится А и если А1 двойственна правильно построенной формуле А, то выводится и не-А»

• специальный принцип дуальности для импликации: Если ⊢ A → В и если А1 и В1 — дуальные к правильно построенным формулам А и В соответственно, то

⊢ В1 → А1, где → — знак импликации («если…, то…»);

• специальный принцип дуальности для эквивалентности: Если ⊢ A ≡ В и если А1 и В1 — дуальные к правильно построенным формулам А и В соответственно, то ⊢ А1 ≡ В1, где ≡ — знак эквивалентности («если…, и только если»)

Двойственность — термин математической логики, применяемый в случае таких пар понятий, как конъюнкция и дизъюнкция, квантор общности, и квантор существования.

Двойственные формулы — в алгебре логики — это такие формулы, которые получаются одна из другой путём замены в них каждого знака конъюнкции на знаки дизъюнкции и наоборот. При этом предполагается, что формулы построены лишь с помощью операций ∧, ∨, ~.

Например, формулы: ((А ∨ ${\overline {B}}$) ∧ С) и ((А ∧ ${\overline {B}}$) ∨ С) являются двойственными, где ∨ — связка «или» (знак дизъюнкции), ∧ — связка «и» (знак конъюнкции), «—» — знак отрицания,

${\overline {B}}$ — отрицание В, то есть не-В.

Литература

• Введение в математическую логику. М., Издательство иностранной литературы, 1960.
• Church, Alonzo. An Unsolvable Problem of Elementary Number Theory