Двойственность конъюнкции/дизъюнкции

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

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

В этой статье будут доказаны эти результаты в § Взаимная определимость и § Отрицание семантически эквивалентно двойственным разделам соответственно.

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

Благодаря своей семантике , т. е. тому, как они обычно интерпретируются в классической логике высказываний, конъюнкцию и дизъюнкцию можно определить в терминах друг друга с помощью отрицания , так что, следовательно, только один из них нужно считать примитивным. ^[4]^[1] Например, если конъюнкция (∧) и отрицание (¬) взяты в качестве примитивов, то дизъюнкция (∨) может быть определена следующим образом: ^[1]^[8]

\varphi \lor \psi :\equiv \neg (\neg \varphi \land \neg \psi ).

(1)

Альтернативно, если дизъюнкция считается примитивной, то конъюнкцию можно определить следующим образом: ^[1]^[9]^[8]

\varphi \land \psi :\equiv \neg (\neg \varphi \lor \neg \psi ).

(2)

Кроме того, каждая из этих эквивалентностей может быть выведена из другой; например, если (1) взять примитивным, то (2) получается следующим образом: ^[1]

\neg (\neg \varphi \lor \neg \psi )\equiv \neg \neg (\neg \varphi \land \neg \psi )\equiv \varphi \land \psi .

(3)

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

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

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

Законы де Моргана также следуют из определений этих связок друг относительно друга, какое бы направление при этом ни было выбрано. ^[1] Если конъюнкцию считать примитивной, то (4) следует непосредственно из (1), а (5) следует из (1) через (3): ^[1]

\neg (\varphi \lor \psi )\equiv \neg \varphi \land \neg \psi .

(4)

\neg (\varphi \land \psi )\equiv \neg \varphi \lor \neg \psi .

(5)

Отрицание семантически эквивалентно двойственному

Теорема: ^[4]^[7] Позволять $X$ быть любым предложением в ${\mathcal {L}}[A_{1},\ldots ,A_{n};\land ,\lor ,\neg ]$ . (То есть язык с пропозициональными переменными $A_{1},\ldots ,A_{n}$ и связи $\{\land ,\lor ,\neg \}$ .) Позволять ${\overline {X}}^{D}$ быть получено от $X$ путем замены каждого вхождения $\land$ в $X$ к $\lor$ , каждое появление $\lor$ к $\land$ , и каждое появление $A_{i}$ к $\neg A_{i}$ . Затем $X$ ⟚ $\neg {\overline {X}}^{D}$ . ( ${\overline {X}}^{D}$ называется двойственным $X$ .)

Доказательство: ^[4]^[7] Предложение $X$ из ${\mathcal {L}}$ , где ${\mathcal {L}}$ как в теореме, будем говорить, что он обладает свойством $P$ если $X$ ⟚ $\neg {\overline {X}}^{D}$ . Докажем индукцией по непосредственным предшественникам, что все предложения ${\mathcal {L}}$ иметь $P$ . ( Непосредственным предшественником является правильно построенной формулы любая из формул, соединенных ее доминантной связкой ; отсюда следует, что буквы предложения не имеют непосредственных предшественников.) Итак, мы должны установить, что выполняются следующие два условия: (1) каждый $A_{i}$ имеет $P$ ; и (2) для любого неатомного $X$ , из индуктивной гипотезы, что непосредственные предшественники $X$ иметь $P$ , отсюда следует, что $X$ делает также.

Каждый $A_{i}$ явно не имеет появления $\lor$ или $\land$ , и так ${\overline {A_{i}}}^{D}$ это просто $\neg A_{i}$ . Итак, показывая это $A_{i}$ имеет $P$ просто требуется показать, что $A_{i}\Leftrightarrow \neg \neg A_{i}$ , что, как мы знаем, так и есть .
Шаг индукции – это рассуждение по случаям. Если $X$ $X$ не является $A_{i}$ $A_{i}$ затем $X$ $X$ должен иметь одну из следующих трех форм: (i) $X=Y\lor Z$ $X=Y\lor Z$ , (ii) $X=Y\land Z$ $X=Y\land Z$ , или (iii) $X=\neg Y$ $X=\neg Y$ где $Y$ $Y$ и $Z$ $Z$ являются предложениями ${\mathcal {L}}$ ${\mathcal {L}}$ . Если $X$ $X$ имеет форму (i) или (ii) имеет непосредственных предшественников $Y$ $Y$ и $Z$ $Z$ , а если он имеет форму (iii), он имеет одного непосредственного предшественника $Y$ $Y$ . Проверим, что шаг индукции выполняется в каждом из случаев.
1. Предположим, что $Y$ и $Z$ у каждого есть $P$ , то есть это $Y$ ⟚ $\neg {\overline {Y}}^{D}$ и $Z$ ⟚ $\neg {\overline {Z}}^{D}$ . Напомним, что это предположение является индуктивной гипотезой . Из этого мы делаем вывод, что $Y\lor Z$ ⟚ $\neg {\overline {Y}}^{D}\lor \neg {\overline {Z}}^{D}$ . По законам де Моргана $\neg {\overline {Y}}^{D}\land \neg {\overline {Z}}^{D}$ ⟚ $({\overline {Y}}^{D}\land {\overline {Z}}^{D})$ . Но ${\overline {Y}}^{D}\land {\overline {Z}}^{D}={\overline {(Y\lor Z)}}^{D}$ , и $Y\lor Z=X$ . Итак, было показано, что из индуктивной гипотезы следует, что $X$ ⟚ $\neg {\overline {X}}^{D}$ , то есть $X$ имеет $P$ по мере необходимости.
2. У нас та же индуктивная гипотеза, что и в (i). Итак, еще раз $Y$ ⟚ $\neg {\overline {Y}}^{D}$ и $Z$ ⟚ $\neg {\overline {Z}}^{D}$ . Следовательно $Y\land Z\Leftrightarrow \neg {\overline {Y}}^{D}\land \neg {\overline {Z}}^{D}$ . И снова де Морган, $\neg {\overline {Y}}^{D}\land \neg {\overline {Z}}^{D}$ ⟚ $\neg ({\overline {Y}}^{D}\land {\overline {Z}}^{D})$ . Но ${\overline {Y}}^{D}\lor {\overline {Z}}^{D}={\overline {(Y\land Z)}}^{D}={\overline {X}}^{D}$ . Так $X$ ⟚ $\neg {\overline {X}}^{D}$ и в этом случае тоже.
3. Здесь индуктивная гипотеза заключается просто в том, что $Y$ ⟚ $\neg {\overline {Y}}^{D}$ . Следовательно $\neg Y$ ⟚ $\neg \neg {\overline {Y}}^{D}$ . Но $\neg {\overline {Y}}^{D}={\overline {\neg Y}}^{D}={\overline {X}}^{D}$ . Следовательно $X$ ⟚ ${\overline {X}}^{D}$ . КЭД

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

Предполагать $\phi \models \psi$ . Затем ${\overline {\phi }}\models {\overline {\psi }}$ путем равномерной замены $\neg P_{i}$ для $P_{i}$ . Следовательно, $\neg \psi \models \neg \phi$ , по противопоставлению ; итак, наконец, $\psi ^{D}\models \phi ^{D}$ , по свойству, которое $\varphi ^{D}$ ⟚ $\neg {\overline {\varphi }}$ , что только что было доказано выше. ^[7] И поскольку $\varphi ^{DD}=\phi$ , это также правда, что $\varphi \models \psi$ тогда и только тогда, когда $\psi ^{D}\models \phi ^{D}$ . ^[7] Отсюда следует, как следствие, что если $\phi \models \neg \psi$ , затем $\phi ^{D}\models \neg \psi ^{D}$ . ^[7]

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

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

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я «Двойственность в логике и языке | Интернет-энциклопедия философии» . Проверено 10 июня 2024 г.
^ «1.1 Логические операции» . www.whitman.edu . Проверено 10 июня 2024 г.
^ Посмотрите, Брэндон С. (25 сентября 2014 г.). Блумсберийский компаньон Лейбница . Издательство Блумсбери. п. 127. ИСБН 978-1-4725-2485-0 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. стр. 41, 44–45. ISBN 978-0-415-13342-5 .
^ Перейти обратно: ^а ^б «Булева алгебра, часть 1 | Обзор ICS 241» . курсы.ics.hawaii.edu . Проверено 10 июня 2024 г.
^ Перейти обратно: ^а ^б Курки-Суонио, Р. (20 июля 2005 г.). Практическая теория реактивных систем: поэтапное моделирование динамического поведения . Springer Science & Business Media. стр. 80–81. ISBN 978-3-540-27348-6 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Босток, Дэвид (1997). Промежуточная логика . Оксфорд: Нью-Йорк: Clarendon Press; Издательство Оксфордского университета. стр. 62–65. ISBN 978-0-19-875141-0 .
^ Перейти обратно: ^а ^б Макридис, Одиссей (2022). Символическая логика . Филгрейвская философия сегодня. Чам, Швейцария: Пэлгрейв Макмиллан. п. 133. ИСБН 978-3-030-67395-6 .
^ Лайонс, Джон (2 июня 1977 г.). Семантика: Том 1 . Издательство Кембриджского университета. п. 145. ИСБН 978-0-521-29165-1 .
^ Робинсон, Алан Дж.А.; Воронков, Андрей (21 июня 2001 г.). Справочник по автоматизированному рассуждению . Профессиональное издательство Персидского залива. п. 306. ИСБН 978-0-444-82949-8 .
^ Перейти обратно: ^а ^б Полковски, Лех Т. (03 октября 2023 г.). Логика: Справочник для специалистов по информатике: 2-е переработанное, модифицированное и расширенное издание «Логики для компьютерных наук, наук о данных и искусственного интеллекта» . Спрингер Природа. п. 70. ИСБН 978-3-031-42034-4 .
^ Багдасар, Овидиу (28 октября 2013 г.). Краткая компьютерная математика: учебники по теории и задачам . Springer Science & Business Media. п. 36. ISBN 978-3-319-01751-8 .

[:0-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я «Двойственность в логике и языке | Интернет-энциклопедия философии» . Проверено 10 июня 2024 г.

[2] «1.1 Логические операции» . www.whitman.edu . Проверено 10 июня 2024 г.

[3] Посмотрите, Брэндон С. (25 сентября 2014 г.). Блумсберийский компаньон Лейбница . Издательство Блумсбери. п. 127. ИСБН 978-1-4725-2485-0 .

[:13-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. стр. 41, 44–45. ISBN 978-0-415-13342-5 .

[:1-5] Перейти обратно: ^а ^б «Булева алгебра, часть 1 | Обзор ICS 241» . курсы.ics.hawaii.edu . Проверено 10 июня 2024 г.

[:2-6] Перейти обратно: ^а ^б Курки-Суонио, Р. (20 июля 2005 г.). Практическая теория реактивных систем: поэтапное моделирование динамического поведения . Springer Science & Business Media. стр. 80–81. ISBN 978-3-540-27348-6 .

[:17-7] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Босток, Дэвид (1997). Промежуточная логика . Оксфорд: Нью-Йорк: Clarendon Press; Издательство Оксфордского университета. стр. 62–65. ISBN 978-0-19-875141-0 .

[:3-8] Перейти обратно: ^а ^б Макридис, Одиссей (2022). Символическая логика . Филгрейвская философия сегодня. Чам, Швейцария: Пэлгрейв Макмиллан. п. 133. ИСБН 978-3-030-67395-6 .

[9] Лайонс, Джон (2 июня 1977 г.). Семантика: Том 1 . Издательство Кембриджского университета. п. 145. ИСБН 978-0-521-29165-1 .

[10] Робинсон, Алан Дж.А.; Воронков, Андрей (21 июня 2001 г.). Справочник по автоматизированному рассуждению . Профессиональное издательство Персидского залива. п. 306. ИСБН 978-0-444-82949-8 .

[:4-11] Перейти обратно: ^а ^б Полковски, Лех Т. (03 октября 2023 г.). Логика: Справочник для специалистов по информатике: 2-е переработанное, модифицированное и расширенное издание «Логики для компьютерных наук, наук о данных и искусственного интеллекта» . Спрингер Природа. п. 70. ИСБН 978-3-031-42034-4 .

[12] Багдасар, Овидиу (28 октября 2013 г.). Краткая компьютерная математика: учебники по теории и задачам . Springer Science & Business Media. п. 36. ISBN 978-3-319-01751-8 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Общие логические связи
Тавтология / Правда $\top$
Альтернативное отрицание ( ворота NAND ) $\uparrow$ Обратная импликация $\leftarrow$ Импликация ( ворота IMPLY ) $\rightarrow$ Дизъюнкция ( ворота ИЛИ ) $\lor$
Отрицание ( НЕ ворота ) $\neg$ Эксклюзивное или ( ворота XOR ) $\not \leftrightarrow$ Двуусловный ( ворота XNOR ) $\leftrightarrow$ Оператор ( цифровой буфер )
Совместное отрицание ( ворота NOR ) $\downarrow$ Неимпликация ( ворота NIMPLY ) $\nrightarrow$ Обратная неимпликация $\nleftarrow$ Соединение ( ворота И ) $\land$
Противоречие / Ложь $\bot$
Философский портал