Двойственность конъюнкции/дизъюнкции
Свойства, связывающие логическую конъюнкцию и дизъюнкцию
Логические связки
НЕТ ¬ А , − А , А ¯ , ∼ А {\displaystyle \neg A,-A,{\overline {A}},\sim A}
И А ∧ Б , А ⋅ Б , А Б , А   &   Б , А   & &   Б {\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}
НЕ-И А ∧ ¯ Б , А ↑ Б , А ∣ Б , А ⋅ Б ¯ {\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}
ИЛИ А ∨ Б , А + Б , А ∣ Б , А ∥ Б {\displaystyle A\or B,A+B,A\mid B,A\parallel B}
НИ А ∨ ¯ Б , А ↓ Б , А + Б ¯ {\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}
X-NOR-не А ⊙ Б , А ∨ ¯ Б ¯ {\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}
└ эквивалент А ≡ Б , А ⇔ Б , А ⇋ Б {\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}
XOR А ∨ _ Б , А ⊕ Б {\displaystyle A{\underline {\lor }}B,A\oplus B}
└неэквивалентный А ≢ Б , А ⇎ Б , А ↮ Б {\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}
подразумевает А ⇒ Б , А ⊃ Б , А → Б {\displaystyle A\Стрелка вправо B,A\supset B,A\Стрелка вправо B}
неподразумеваемый (NIMPLY) А ⇏ Б , А ⊅ Б , А ↛ Б {\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}
общаться А ⇐ Б , А ⊂ Б , А ← Б {\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}
converse nonimplication A ⇍ B , A ⊄ B , A ↚ B {\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}
Related concepts
Applications
Category

В пропозициональной логике и булевой алгебре существует двойственность между конъюнкцией и дизъюнкцией , [1] [2] [3] также называемая принципом двойственности . [4] [5] [6] Это наиболее широко известный пример двойственности в логике. [1] Двойственность заключается в следующих металогических теоремах:

  • В классической пропозициональной логике связки для конъюнкции и дизъюнкции могут быть определены в терминах друг друга, и, следовательно, только одну из них нужно рассматривать как примитивную. [4] [1]
  • Если используется как обозначение для обозначения результата замены каждого экземпляра конъюнкции на дизъюнкцию и каждого экземпляра дизъюнкции на конъюнкцию (например , на или наоборот) в данной формуле , и если используется как обозначение для замены каждой буквы предложения в на ее отрицание (например, на ), и если символ используется для семантического следствия, а ⟚ для семантической эквивалентности между логическими формулами, то можно продемонстрировать, что  ⟚  , [4] [7] [6] а также, что тогда и только тогда, когда , [7] и, кроме того, что если  ⟚  то  ⟚  . [7] (В этом контексте называется двойственной формуле .) [4] [5] φ D {\displaystyle \varphi ^{D}} p ∧ q {\displaystyle p\land q} q ∨ p {\displaystyle q\lor p} φ {\displaystyle \varphi } φ ¯ {\displaystyle {\overline {\varphi }}} φ {\displaystyle \varphi } p {\displaystyle p} ¬ p {\displaystyle \neg p} ⊨ {\displaystyle \models } φ D {\displaystyle \varphi ^{D}} ¬ φ ¯ {\displaystyle \neg {\overline {\varphi }}} φ ⊨ ψ {\displaystyle \varphi \models \psi } ψ D ⊨ φ D {\displaystyle \psi ^{D}\models \varphi ^{D}} φ {\displaystyle \varphi } ψ {\displaystyle \psi } φ D {\displaystyle \varphi ^{D}} ψ D {\displaystyle \psi ^{D}} φ ¯ D {\displaystyle {\overline {\varphi }}^{D}} φ {\displaystyle \varphi }

Взаимная определяемость

Связки можно определить относительно друг друга следующим образом:

φ ∨ ψ :≡ ¬ ( ¬ φ ∧ ¬ ψ ) . {\displaystyle \varphi \lor \psi :\equiv \neg (\neg \varphi \land \neg \psi ).} (1)
φ ∧ ψ :≡ ¬ ( ¬ φ ∨ ¬ ψ ) . {\displaystyle \varphi \land \psi :\equiv \neg (\neg \varphi \lor \neg \psi ).} (2)
¬ ( ¬ φ ∨ ¬ ψ ) ≡ ¬ ¬ ( ¬ φ ∧ ¬ ψ ) ≡ φ ∧ ψ . {\displaystyle \neg (\neg \varphi \lor \neg \psi )\equiv \neg \neg (\neg \varphi \land \neg \psi )\equiv \varphi \land \psi .} (3)

Функциональная полнота

Поскольку теорема о дизъюнктивной нормальной форме показывает, что множество связок является функционально полным , эти результаты показывают, что множества связок и сами по себе также являются функционально полными. { ∧ , ∨ , ¬ } {\displaystyle \{\land ,\lor ,\neg \}} { ∧ , ¬ } {\displaystyle \{\land ,\neg \}} { ∨ , ¬ } {\displaystyle \{\lor ,\neg \}}

Законы де Моргана

Законы де Моргана также следуют из определений этих связок относительно друг друга, какое бы направление ни было выбрано для этого. [1]

¬ ( φ ∨ ψ ) ≡ ¬ φ ∧ ¬ ψ . {\displaystyle \neg (\varphi \lor \psi )\equiv \neg \varphi \land \neg \psi .} (4)
¬ ( φ ∧ ψ ) ≡ ¬ φ ∨ ¬ ψ . {\displaystyle \neg (\varphi \land \psi )\equiv \neg \varphi \lor \neg \psi .} (5)

Свойства двойственности

Двойственное предложение — это то , что вы получаете, меняя местами все вхождения ∨ и &, а также отрицая все пропозициональные константы. Например, двойственное предложение (A & B ∨ C) будет (¬A ∨ ¬B & ¬C). Двойственное предложение формулы φ обозначается как φ*. Принцип двойственности гласит, что в классической пропозициональной логике любое предложение эквивалентно отрицанию его двойственного предложения. [4] [7]

Принцип двойственности: Для всех φ имеем φ = ¬(φ*). [4] [7]
Доказательство: Индукция по сложности. Для базового случая мы рассматриваем произвольное атомарное предложение A. Поскольку его двойственное предложение — ¬A, отрицание его двойственного предложения будет ¬¬A, что действительно эквивалентно A. Для шага индукции мы рассматриваем произвольное φ и предполагаем, что результат справедлив для всех предложений меньшей сложности. Три случая:
  1. Если φ имеет вид ¬ψ для некоторого ψ, то его дуальным будет ¬(ψ*), а отрицание его дуального элемента будет ¬¬(ψ*). Теперь, поскольку ψ менее сложно, чем φ, предположение индукции дает нам, что ψ = ¬(ψ*). Подстановкой это дает нам, что φ = ¬¬(ψ*), то есть φ эквивалентно отрицанию своего дуального элемента.
  2. Если φ имеет вид (ψ ∨ χ) для некоторых ψ и χ, то его дуальным будет (ψ* & χ*), и отрицание его дуального будет, следовательно, ¬(ψ* & χ*). Теперь, поскольку ψ и χ менее сложны, чем φ, предположение индукции дает нам, что ψ = ¬(ψ*) и χ = ¬(χ*). Подстановкой это дает нам, что φ = ¬(ψ*) ∨ ¬(χ*), что, в свою очередь, дает нам, что φ = ¬(ψ* & χ*) по закону ДеМоргана . И это еще раз просто для того, чтобы сказать, что φ эквивалентно отрицанию своего дуального .
  3. Если φ имеет вид ψ ∨ χ, то результат следует из аналогичных рассуждений.

Дальнейшие теоремы двойственности

Предположим . Тогда путем равномерной замены на . Следовательно, , по контрапозиции ; и, наконец, , по свойству  ⟚  , которое было только что доказано выше. [7] И поскольку , также верно , что тогда и только тогда, когда . [7] И отсюда следует, как следствие, что если , то . [7] ϕ ⊨ ψ {\displaystyle \phi \models \psi } ϕ ¯ ⊨ ψ ¯ {\displaystyle {\overline {\phi }}\models {\overline {\psi }}} ¬ P i {\displaystyle \neg P_{i}} P i {\displaystyle P_{i}} ¬ ψ ⊨ ¬ ϕ {\displaystyle \neg \psi \models \neg \phi } ψ D ⊨ ϕ D {\displaystyle \psi ^{D}\models \phi ^{D}} φ D {\displaystyle \varphi ^{D}} ¬ φ ¯ {\displaystyle \neg {\overline {\varphi }}} φ D D = ϕ {\displaystyle \varphi ^{DD}=\phi } φ ⊨ ψ {\displaystyle \varphi \models \psi } ψ D ⊨ ϕ D {\displaystyle \psi ^{D}\models \phi ^{D}} ϕ ⊨ ¬ ψ {\displaystyle \phi \models \neg \psi } ϕ D ⊨ ¬ ψ D {\displaystyle \phi ^{D}\models \neg \psi ^{D}}

Конъюнктивные и дизъюнктивные нормальные формы

Для формулы в дизъюнктивной нормальной форме формула будет в конъюнктивной нормальной форме , и, учитывая результат, что § Отрицание семантически эквивалентно двойственной, она будет семантически эквивалентна . [8] [9] Это обеспечивает процедуру преобразования между конъюнктивной нормальной формой и дизъюнктивной нормальной формой. [10] Поскольку теорема о дизъюнктивной нормальной форме показывает, что каждая формула пропозициональной логики выразима в дизъюнктивной нормальной форме, каждая формула также выразима в конъюнктивной нормальной форме посредством осуществления преобразования в ее двойственную форму. [9] φ {\displaystyle \varphi } φ ¯ D {\displaystyle {\overline {\varphi }}^{D}} ¬ φ {\displaystyle \neg \varphi }

Ссылки

[11] [12]

  1. ^ abcd "Двойственность в логике и языке | Интернет-энциклопедия философии" . Получено 2024-06-10 .
  2. ^ "1.1 Логические операции". www.whitman.edu . Получено 2024-06-10 .
  3. ^ Посмотрите, Брэндон С. (2014-09-25). Bloomsbury Companion to Leibniz. Bloomsbury Publishing. стр. 127. ISBN 978-1-4725-2485-0.
  4. ^ abcdef Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. С. 41, 44– 45. ISBN 978-0-415-13342-5.
  5. ^ ab "Булева алгебра, часть 1 | Обзор ICS 241". courses.ics.hawaii.edu . Получено 10.06.2024 .
  6. ^ ab Курки-Суонио, Р. (2005-07-20). Практическая теория реактивных систем: инкрементальное моделирование динамического поведения. Springer Science & Business Media. стр.  80–81 . ISBN 978-3-540-27348-6.
  7. ^ abcdefgh Bostock, David (1997). Промежуточная логика . Oxford: New York: Clarendon Press; Oxford University Press. стр.  62–65 . ISBN 978-0-19-875141-0.
  8. ^ Робинсон, Алан JA; Воронков, Андрей (2001-06-21). Справочник по автоматизированному рассуждению. Gulf Professional Publishing. стр. 306. ISBN 978-0-444-82949-8.
  9. ^ ab Polkowski, Lech T. (2023-10-03). Логика: Справочник для компьютерных специалистов: 2-е пересмотренное, измененное и расширенное издание «Логики для компьютерных наук, наук о данных и искусственного интеллекта». Springer Nature. стр. 70. ISBN 978-3-031-42034-4.
  10. ^ Багдасар, Овидиу (2013-10-28). Краткая компьютерная математика: Учебники по теории и проблемам. Springer Science & Business Media. стр. 36. ISBN 978-3-319-01751-8.
  11. ^ Makridis, Odysseus (2022). Символическая логика . Философия Palgrave сегодня. Cham, Швейцария: Palgrave Macmillan. стр. 133. ISBN 978-3-030-67395-6.
  12. ^ Лайонс, Джон (1977-06-02). Семантика: Том 1. Cambridge University Press. стр. 145. ISBN 978-0-521-29165-1.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Conjunction/disjunction_duality&oldid=1253401030"