Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Логические символы и называют двойственными друг другу. Формула А двойственна формуле А, если она получена из А одновременной заменой и на двойственные. Например, формула F=A (B& C) двойственна формуле F =A& (B C). Это первый способ получения двойственной формулы. Теорема (принцип двойственности): если A B, то A B . Доказательство: Пусть на некоторой оценке s общего списка переменных для всех четырёх рассматриваемых формул формула A принимает значение 1. Тогда формула A, двойственная A , принимает значение 0 на оценке t, двойственной оценке s. Так как A B, то формула B тоже принимает значение 0 на оценке t. Отсюда формула B , двойственная B, принимает значение 1 на оценке s, двойственной оценке t. Поскольку оценка s произвольна, то получаем, что A B .
Дата публикования: 2014-11-29; Прочитано: 1439 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!