Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Равносильность формул. Логическое следование. Связь булевых функций с формулами алгебры высказываний.
1. Равносильность формул. Логическое следование.
Важным понятием, связанным со сравнением различных формул, является понятие их равносильности.
Определение. Две формулы A и B, зависящие от одного и того же набора высказывательных переменных называются равносильными, если I(A)=I(B) для любой интерпретации I. Равносильность формул A и B записывается следующим образом:AB.
Замечание. Следует различать символы ~ и . Символ «~» является символом алфавита, используемом при построении и записи формул, а символ «» указывает на определённые свойства, связанные с интерпретацией формул.
Отношение равносильности на множестве формул логики высказываний является отношением эквивалентности, так как оно:
Рефлексивно AA
Симметрично AB ВА
Транзитивно AB и ВºС АС
Отношение эквивалентности разбивает все формулы на непересекающиеся классы эквивалентных формул. Формулам из одного класса можно сопоставить описанным выше способом одну и ту же булеву функцию, причём разным классам сопоставляются разные функции.
С понятием равносильности тесно связано понятие логического следования.
Определение. Формула B логически следует из формулы A (обозначается AB), если формула B имеет значение И при всех интерпретациях, при которых формула A имеет значение И.
Нетрудно убедиться, что AB тогда и только тогда, когда AB и AB одновременно.
Основные равносильности, которые используются в процессе преобразования формул, следующие:
1. AAA; AAA - идемпотентность и
2. ABBA; ABBA - коммутативность и
3. A(BC)=(AB)C; A(BC)=(AB)C - ассоциативность и
4. A(BC)(AB)(AC) - дистрибутивность относительно
5. A(BC)(AB)(AC) - дистрибутивность относительно
6. AЛA; AЛЛ
7. AИИ; AИA
8. (A)A - снятие двойного отрицания
9. (AB)AB; (AB)AB - первый и второй законы де Моргана
10. AAИ; AAЛ
11. A(AB)A; A(AB)A - первый и второй законы поглощения
12. A(AB)(AB); A(AB)(AB) - первый и второй законы асщепления
13. A~B(AB)(BA)(AB)(AB)
14. AB(AB)(AB)
15. ABAB(AB)
16. AB(AB)(AB)
Приведённые соотношения равносильности могут быть доказаны либо с помощью таблиц истинности, либо на основе рассмотрения вариантов значений. Для демонстрации докажем второй закон де Моргана на основе рассмотрения вариантов значений.
Пусть для некоторой интерпретации I имеем:
I((AB))=И |I(AB)=Л | I(A)=Л и I(B)=Л | I(A)=И и I(B)=И | I(AB)=И.
Обратно, пусть I(AB)=И | I(A)=И и I(B)=И | I(A)=Л, I(B)=Л | I(AB)=Л | I((AB))=И.
(Самостоятельно провести доказательства всех равносильностей двумя способами).
Обсудим теперь вопрос сохранения свойства равносильности формул при различных преобразованиях.
Теорема 2. Пусть AB и C – произвольная формула. Тогда:
Доказательство: продемонстрируем на примере одного из соотношений. Пусть при некоторой интерпретации I имеем I(A)=I(B)=s; и пусть I(C)=t. Тогда обе части каждой из формул, например, 4) ACBC принимают абсолютно одинаковый вид (st).
Следующая теорема устанавливает тесную связь понятий равносильности и логического следствия с понятием тавтологии.
Теорема 3.
Доказательство.
2) Необходимость:
Пусть I(A)= И. Тогда из определения следования вытекает I(B)=И I(AB)=И. Таким образом формула AB тавтология.
Достаточность: Пусть AB – тавтология. Предположим I(A)=И. Тогда необходимо I(B)=И, иначе I(AB)=Л. таким образом, AB.
1) (самостоятельно) доказательство проводится аналогично 2).ð
Следствие: AB AB – противоречие.
Доказательство следует теоремы равносильности 3).
Таким образом, теорема 3 позволяет свести изучение равносильности и логического следования формул к изучению соответствующих тавтологий.
2. Связь булевых функций с формулами алгебры высказываний.
Теорема 6. Всякая формула алгебры высказываний естественным образом (канонически) порождает некоторую булеву функцию, т.е. если - некоторая формула, в которую входят высказывательные переменные и только они, тогда канонически порожденная булева функция , где
Доказательство: проведем методом математической индукции по - количеству символов в слове . Минимальное количество символов в формуле равно 1, т.к. пустое множество не является формулой.
Пусть - высказывательная переменная, .
Пусть нам известно, что для всех формул у которых , где утверждение теоремы 6 истинно. Докажем, что для формул, у которых , это утверждение тоже будет истинным.
Возьмем произвольную формулу , у которой () символов. Тогда , или , или , или . Формулы А и В содержат меньше символов, чем формула , т.е. и , но для этих формул утверждение теоремы 1 истинно. Согласно индуктивному предположению формулы и канонически порождают булевы функции соответственно и .
Так для
Аналогично показывается это утверждение для остальных случаев. ð
Пример.
Верна и обратная теорема.
Теорема 7. Для любой булевой функции существует высказывательная формула , в которую входят высказывательные переменные , канонически порождающая функцию .
3. Разложение булевых функций по переменным
Определение: Булева функция существенно зависит от переменной хi, если существует такой набор значений а1, …, аi-1, ai+1, …, an, что
f(а1, …, аi-1, 0, ai+1, …, an)≠ f(а1, …, аi-1, 1, ai+1, …, an)
В этом случае переменная хi называется существенной, в противном случае – несущественной (фиктивной).
Используем далее обозначение
Теорема 8. (о разложении функции по переменным). Для каждой f:ЕnE , где E={0,1}, при любом m = 1, 2, …, n справедливо представление:
f(x1, …, xn)=
Доказательство. Покажем, что левая и правая части равенства из условия теоремы принимают равные значения при произвольном наборе значе ний переменных (а1, …, аn).
Левая часть равна f(а1, …, an). Правая часть равна
Так как =1 тогда и только тогда, когда аi =i, i = 1,2,…,m, то слагаемые, соответствующие наборам , равны 0, а слагаемое, соответствующее набору , равно . ð
Следствие 1 (разложение б.ф. по одной переменной):
f(x1, …, xn-1, xn)=
Если f не равна константе 0, то условие теоремы 8 можно переписать:
f(x1, …, xn)=
Данное представление называют совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x1, …, xn), а двойственную формулу, получаемую взаимной заменой констант 01 и операций ,- совершенной конъюнктивной нормальной формой (СКНФ).
f(x1, …, xn)=
Следствие 2. Каждая б.ф. представима в виде формулы через от рицание, конъюнкцию и дизъюнкцию.
Доказательство. Для функции f(x1, …, xn), отличной от констан ты 0, утверждение вытекает из теоремы 8. Для f=0 справедливо: . ð
Задание б.ф. с помощью СДНФ и СКНФ нередко менее громозд ко, чем задание с помощью таблицы. В ряде случаев удобно пользо ваться не СДНФ и СКНФ, а более компактными формулами, которые могут быть получены из них. Существуют различные способы минимизации СДНФ и СКНФ, которые будут рассмотрены на практике.
Поскольку любую формулу над данной системой раскрытием скобок, логическим умножением и приведением подобных членов можно привести к каноническому многочлену по mod2, то имеем следующую теорему.
Теорема 10 (И. И. Жегалкин). Каждая б.ф. однозначно предста вима многочленом по mod2:
f(x1, …, xn)=
Так как число таких многочленов от n переменных совпадает с числом различных б.ф., то представление функции полиномом единственно. ð
Это представление называется многочленом Жегалкина или Алгебраической нормальной формой (АНФ).
4. Полнота и замкнутость системы функций
Система функций Р = {f1, …, fs, …} из P2 называется (функцио нально) полной, если любая б.ф. представима формулой над Р. Сле дующая теорема связывает полноту одних систем с полнотой других систем.
Теорема 9. Пусть система Р = {f1, f2, …} из P2 полна и каждая ее функция выражается формулой над системой Q = {q1, q2, …} Тогда система Q полна.
Доказательство. Произвольная б.ф. h в силу полноты системы Р выражается суперпозицией формул над Р.
h=C[f1, …, fs, …]
По условию теоремы каждая из функций системы Р является в свою очередь суперпозицией функций из Q.
f1=C1[q1, q2, …], f2=C2[q1, q2, …], …
В фор муле для h исключаем вхождения функций из системы Р, заменяя их формулами над Q. В результате получаем:
h = C[C1[q1, q2, …], C2[q1, q2, …], …] = C[q1, q2, …]. ð
Примеры полных систем функций:
;