Мобильная версия== Взаимная определимость ==
Из-за своей семантики логики | семантики, то есть того, как они обычно интерпретируются в классической логике высказываний, конъюнкцию и дизъюнкцию можно определить в терминах друг друга с помощью отрицания, так что, следовательно, нужно взять только один из них. как примитив. Например, если конъюнкция (∧) и отрицание (¬) взяты в качестве примитивов, то дизъюнкция (∨) может быть определена как следует:
:\varphi \lor \psi :\equiv \neg (\neg \varphi \land \neg \psi). (1)
В качестве альтернативы, если дизъюнкция рассматривается как примитив, то конъюнкцию можно определить следующим образом:
:\varphi \land \psi :\equiv \neg (\neg \varphi \lor \neg \psi). (2)
Кроме того, каждая из этих эквивалентностей может быть выведена из другой; например, если (1) принять за примитив, то (2) получится следующим образом:
:\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\} сами по себе также функционально завершены.
=== Законы де Моргана ===
Законы де Моргана также следуют из определений этих связок друг относительно друга, какое бы направление ни было выбрано для этого. Если союз считать примитивным, то (4) следует непосредственно из ( 1), а (5) следует из (1) через (3):
:\neg (\varphi \lor \psi) \equiv \neg \varphi \land \neg \psi. (4)
:\neg (\varphi \land \psi) \equiv \neg \varphi \lor \neg \psi. (5)
== Отрицание семантически эквивалентно двойственному ==
'''Теорема:'''Пусть X будет любым предложением из \mathcal{L}[A_1, \ldots, A_n; \land, \lor, \neg]. (То есть язык с пропозициональной переменной|пропозициональными переменными A, B, C, \ldots и логической связкой|связками \{\land, \lor, \neg\}< /math>.) Пусть \overline{X}^{D} получен из X путем замены каждого вхождения \land в X на \lor, каждое вхождение \lor на \land и каждое вхождение A_i от \neg A_i. Затем X \Leftrightarrow \overline{X}^{D}. (\overline{X}^{D} называется двойственным к X.)
'''Доказательство:''' Предложение X из \mathcal{L}, где \mathcal{L} соответствует теореме, будет называться обладающим свойством P, если X \Leftrightarrow \overline{X}^{ D. Мы будем математической индукцией|доказывать индукцией по непосредственным предшественникам, что все предложения \mathcal{L} имеют P. («Непосредственным предшественником» Правильно составленной формулы|правильно составленной формулы является любая из формул, находящихся в
[*]Каждый A_i явно не имеет вхождения \lor или \land, поэтому \overline{A_i}^{D — это просто \neg A_i. Таким образом, чтобы показать, что A_i имеет P, нужно просто показать, что A_i \Leftrightarrow \neg \neg A_i, что, как мы знаем, имеет место. .
[*]Шаг индукции — это рассуждение по прецедентам. Если X не является A_i, то X должен иметь одну из следующих трех форм: (i) X = Y \lor Z , (ii) X = Y \land Z или (iii) X = \neg Y, где Y и Z — это предложения из \mathcal{L}. Если X имеет форму (i) или (ii), он имеет непосредственных предшественников Y и Z, а если он имеет форму (iii) у него есть один непосредственный предшественник Y. Проверим, что шаг индукции выполняется в каждом из случаев.
- Предположим, что Y и Z имеют P, т. е. что Y \Leftrightarrow \overline{Y}^{D} и Z \Leftrightarrow \overline{Z}^{D}. Напомним, что это предположение является индуктивной гипотезой. Из этого мы делаем вывод, что Y \lor Z \Leftrightarrow \overline{Y}^{D} \lor \overline{Z}^{D}. По законам де Моргана|Законы де Моргана \neg \overline{Y}^{D} \land \neg \overline{Z}^{D} \Leftrightarrow \neg (\overline{Y}^{D} \ земля \overline{Z}^{D}). Но \overline{Y}^{D} \land \overline{Z}^{D} = \overline{(Y \lor Z)}^{D} и Y \ или Z = X. Итак, было показано, что индуктивная гипотеза подразумевает, что X \Leftrightarrow \overline{X}^{D}, т. е. X имеет P как требуется.
- У нас та же индуктивная гипотеза, что и в (i). Итак, снова Y \Leftrightarrow \overline{Y}^{D} и Z \Leftrightarrow \overline{Z}^{D}. Следовательно, Y \land Z \Leftrightarrow \overline{Y}^{D} \land \overline{Z}^{D}. И снова де Морган, \neg \overline{Y}^{D} \land \neg \overline{Z}^{D} \Leftrightarrow \neg (\overline{Y}^{D} \land \overline {Z}^{D}). Но \overline{Y}^{D} \land \overline{Z}^{D} = \overline{(Y \land Z)}^{D}. Итак, X \Leftrightarrow \overline{X}^{D} и в этом случае.
- Здесь индуктивная гипотеза заключается в том, что Y \Leftrightarrow \overline{Y}^{D}. Следовательно, \neg Y \Leftrightarrow \neg \overline{Y}^{D}. Но \neg \overline{Y}^{D} = \neg (\neg Y) = \overline{Y}^{D}. Следовательно, X \Leftrightarrow \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} , что было только что доказано выше. А поскольку \varphi^{DD} = \phi, верно также и то, что \varphi \models \psi тогда и только тогда, когда \psi^D \models \phi^D. Отсюда следует, как следствие, что \phi \models \neg \psi, затем \phi^D \models \neg \psi^D.
== Конъюнктивная и дизъюнктивная нормальные формы ==
Для формулы \varphi в дизъюнктивной нормальной форме формула \overline{\varphi}^{D} будет в конъюнктивной нормальной форме и с учетом результата, который
Подробнее: https://en.wikipedia.org/wiki/Conjuncti ... on_duality