Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Принцип двойственности




Пусть U=U(X,Y,…,Z) – формула алгебры высказываний. Формула

U* = U(X,Y,…,Z)

называется двойственной к формуле U.

Из закона двойного отрицания следует, что (U*)*≅U. Между таблицами истинности исходной формулы и двойственной к ней имеется простая связь. Предположим для определенности, что формула U содержит две переменных, U=U(X,Y), и рассмотрим следующую таблицу истинности:

X Y U U*

------------------------

0 0 α δ

0 1 β γ

1 0 γ β

1 1 δ α

Несложно заметить, что столбец значений формулы U* представляет собой перевернутый столбец значений формулы U, снабженных отрицанием. То же справедливо и для формул, содержащих большее число пропозициональных переменных. Из этого замечания вытекает следующее утверждение.

Закон двойственности. Формулы алгебры высказываний равносильны тогда и только тогда, когда равносильны двойственные им формулы: U≅V тогда и только тогда, когда U*≅V*.􀀀

Для булевых формул закон двойственности приобретает особенно наглядную форму.

Теорема. Если формула U булева, то двойственная формула U* равносильна формуле U∧∨, полученной из U заменой всех конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции.

Доказательство. Воспользуемся индукцией по длине формулы. Предположим сначала, что формула U состоит всего из одного символа. Это означает, что формула имеет вид U=X, где X – некоторая пропозициональная переменная. Ясно, что для такой формулы U*≅U и U∧∨=U, так что утверждение теоремы справедливо. Предположим теперь, что утверждение теоремы справедливо для всех формул длины меньше n и покажем, что оно справедливо и для произвольной формулы U=U(X,…,Y) длины n. В соответствии с определением формула U имеет вид

а) U=V; б) U=V∧W или в) U=V∨W,

где V и W – некоторые формулы. Ясно, что в любом случае формула U содержит по крайней мере на один знак больше, чем формулы V и W. Значит, длина V меньше n, и длина W меньше n. Поэтому к формулам V и W применимо заключение теоремы, то есть

V*≅V∧∨и W*≅W∧∨.

С учетом этого рассмотрим каждый из трех возможных случаев.

а) U* = (V(X,…,Y)) = V*, U∧∨= V∧∨, откуда U*≅U∧∨.

б) U* = (V(X,…,Y) ∧ W(X,…,Y)), откуда по первой формуле де Моргана U* ≅ V(X,…,Y)∨W(X,…,Y))≅ V*∨W*. С другой стороны, U∧∨= V∧∨∧W∧∨, и, значит, U*≅U∧∨.

в) U* = (V(X,…,Y) ∨ W(X,…,Y)), откуда по второй формуле де Моргана U* ≅ V(X,…,Y)∨W(X,…,Y))≅ V*∧W*. С другой стороны, U∧∨= V∧∨∨W∧∨, и, значит, U*≅U∧∨. В соответствии с принципом математической индукции утверждение теоремы верно для формул любой длины, то есть для всех формул.􀀀

Обычно закон двойственности применяют к булевым формулам и в этом случае называют двойственной к формуле U формулу U∧∨. Следуя этой традиции, мы тем не менее сохраним за двойственной формулой обозначение U*.

В списке основных равносильностей идущие парами равносильности получаются друг из друга по закону двойственности (или, короче, по двойственности).

Пример. Формулы X(Y∨Y) и X∨(YY) двойственны, поэтому равносильность

X(Y∨Y) ≅ X

получается из равносильности

X∨(YY) ≅ X

по двойственности.􀀀






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных