🗊Презентация Исчисление высказываний

Булевы функции.

Дизъюнктивная нормальная форма (ДНФ). Конъюнктивная нормальная форма (КНФ).

Пусть функция от трех переменных задана следующей таблицей:

тогда

Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Получаемые при этом формулы называются совершенными дизъюнктивными нормальными формами, (СДНФ). Считается, что СДНФ тождественного нуля– это «пустая» дизъюнкция, не содержащая ни одного дизъюнктивного слагаемого.

Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме, сокращенно СКНФ. Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме, сокращенно СКНФ. СКНФ рассмотренной ранее функции имеет следующий вид: Каждый из пяти конъюнктивных членов (множителей) соответствует набору значений аргументов, для которого функция принимает значение 0.

Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной. Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной. Теорема. Пусть – произвольная булева функция. Тогда

Доказательство. Докажем первую формулу. Чтобы не загромождать выкладки индексами и многоточиями, ограничимся случаем функции от двух переменных. Доказательство. Докажем первую формулу. Чтобы не загромождать выкладки индексами и многоточиями, ограничимся случаем функции от двух переменных. Доказываемая формула принимает следующий вид: При любом y подстановка в правую часть x=1 и x=0 дает соответственно

Таким образом, левая и правая части доказываемого Таким образом, левая и правая части доказываемого равенства совпадают на любом наборе значений аргументов. Следовательно, функции слева и справа от знака равенства равны. На общий случай доказательство распространяется практически без изменений. Достаточно считать, что y обозначает не одну переменную, а набор переменных. Второе равенство из формулировки теоремы доказывается аналогично (кроме того, его справедливость следует из принципа двойственности).

Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно получить СДНФ булевой функции. Например,

Функция представлена в виде дизъюнкции четырех Функция представлена в виде дизъюнкции четырех дизъюнктивных членов. Те из них, для которых коэффициент равен нулю, можно отбросить. В результате получится СДНФ. Например, для функции имеем и , поэтому

Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза. Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза.

Полные системы булевых функций Система булевых функций называется полной, если любая булева функция может быть выражена через функции этой системы с помощью суперпозиций. Таким образом, в соответствии с определением система функций {∧, ∨, ’} полна.

Поскольку дизъюнкцию можно выразить через конъюнкцию и отрицание, система функций {∧, ’} также полна. Точно так же полной является и система функций {∨, ’}, поскольку конъюнкцию можно выразить через дизъюнкцию и отрицание. Отрицание можно выразить через ноль и импликацию, дизъюнкцию– через Поскольку дизъюнкцию можно выразить через конъюнкцию и отрицание, система функций {∧, ’} также полна. Точно так же полной является и система функций {∨, ’}, поскольку конъюнкцию можно выразить через дизъюнкцию и отрицание. Отрицание можно выразить через ноль и импликацию, дизъюнкцию– через импликацию и отрицание. Следовательно, отрицание и импликация, ноль и импликация также образуют полные системы функций {’, →}, {0, →}.

Через ⊕ и 1 можно выразить отрицание, так что система Функций {1, ⊕, ⋅} также является полной. Последнее означает, что любая булева функция может быть представлена в виде многочлена. При этом ненулевыми коэффициентами при одночленах служат единицы, а одночлены не содержат степеней переменных, поскольку умножение (конъюнкция) идемпотентна. Такие многочлены называют полиномами Жегалкина.

Пример. Вычислим полином Жегалкина для функции Пример. Вычислим полином Жегалкина для функции Имеем При выводе использовались равенства

Существуют полные системы, содержащие всего одну Существуют полные системы, содержащие всего одну функцию. Отрицание и конъюнкцию можно выразить через стрелку Пирса. Следовательно, стрелка Пирса составляет полную систему функций {↓}. Точно так же отрицание и дизъюнкция выражаются через штрих Шеффера, так что {|} – тоже полная система функций.

Таким образом, что установить полноту системы функций можно, показав, как через функции этой системы выражаются функции какой-нибудь системы, полнота которой уже известна. Доказательство неполноты может оказаться более изощренным.

Пример. Покажем что система функций {⋅,∨} неполна. Действительно, отрицание нельзя выразить через дизъюнкцию и конъюнкцию. Допустим противное, то есть, что отрицание удалось представить в виде и при этом функция выражена через конъюнкции и дизъюнкции. Тогда Но конъюнкция и дизъюнкция монотонны по своим аргументам:

Тем же свойством обладает и любая сложная функция, составленная из конъюнкции и дизъюнкции. Значит, что противоречит предполагаемому равенству.

Важнейшие замкнутые классы булевых функций. Теорема Поста о полноте Пусть K– некоторый класс булевых функций. Замыканием класса K называется множество всех тех функций, которые могут быть выражены через функции класса K. Замыкание класса K будем обозначать через [K]. Класс функций называется замкнутым, если он совпадает со своим замыканием.

Замыкание любой полной системы функций содержит все Замыкание любой полной системы функций содержит все булевы функции. Для неполной системы функций это уже не так. Например, отрицание не входит в замыкание класса K={∧,∨}.

Рассмотрим важнейшие замкнутые классы булевых функций. Рассмотрим важнейшие замкнутые классы булевых функций. Класс . Класс – это класс всех функций, сохраняющих 0, то есть таких функций для которых В этот класс входят: тождественная функция; конъюнкция; дизъюнкция; сложение по модулю2;

Не входят: тождественная единица; отрицание; импликация. Таблица для функции из класса в первой строке содержит 0, остальные значения могут быть какими угодно.

Класс . Класс – это класс всех функций, сохраняющих 1, Класс . Класс – это класс всех функций, сохраняющих 1, то есть таких функций для которых В этот класс входят: тождественная функция; конъюнкция; дизъюнкция; сложение по модулю2; импликация.

Не входят в : тождественный ноль; отрицание.

Класс . Класс . Класс – это класс всех самодвойственных функций, то есть таких функций f, которые совпадают со своей двойственной функцией, Простейшие примеры самодвойственных функций– x и x’. Функция также самодвойственная:

Конъюнкция и дизъюнкция не самодвойственны. В таблице самодвойственной функции значение в последней строке противоположно значению в первой строке, значение в предпоследней– значению во второй, и т.д.

Класс L. Класс L– это класс всех линейных функций, то есть функций, представимых в виде где – константы. Функции линейные; конъюнкция, дизъюнкция– нет.

Класс M. Класс M. Класс M– это класс монотонных функций. Функция называется монотонной, если при Конъюнкция, дизъюнкция монотонны; отрицание, импликация, сложение по модулю2 – нет.

Теперь мы можем сформулировать один из важнейших Теперь мы можем сформулировать один из важнейших результатов теории булевых функций– теорему Поста о полноте. Теорема. Класс функций K полон тогда и только тогда, когда он не содержится целиком ни в одном из перечисленных выше пяти классов

Как было показано, ни один из перечисленных пяти замкнутых классов не является полным(имеются не входящие в него булевы функции). Поэтому не может быть полным ни один класс функций, целиком содержащийся в одном из них. С помощью теоремы Поста можно устано

Имеются булевы функции, не входящие ни в один из классов Имеются булевы функции, не входящие ни в один из классов Любая такая функция в соответствии с теоремой составляет полную систему функций, то есть через эту функцию может быть выражена любая булева функция. Среди функций от двух переменных такими функциями являются стрелка Пирса и штрих Шеффера.

С помощью теоремы Поста можно установить полноту системы функций, не выписывая непосредственно выражения для булевых функций.