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

Иван Иванович Жегалкин(1869-1947) – российский математик и логик, один из основоположников современной математической логики. Из его открытий наибольшую известность получил так называемый полином Жегалкина. Жегалкин награжден Орденом Трудового Красного Знамени. В своем письме М. Я. Выгодскому известный советский математик Николай Лузин, вспоминая студенческие годы, говорит, что из профессоров не боялся лишь Жегалкина.
Чарльз Сандерс Пирс (1839-1914)- американский философ, логик, математик, основоположник прагматизма и семиотики.
Ввёл в философию термин фанерон, предложил концепцию тихизма. В логику — стрелку Пирса, в картографию — проекцию Пирса. Немецкий философ Апель назвал Пирса «Кантом американской философии».

Число булевых функций n аргументов равно . Для задания булевой функции нужно указать её значение для каждого из 2 в степени n различных значений её аргументов. Если значение функции равно 0, то такая функция постоянна и называется константой 0.
Если значение функции равно 1, то такая функция называется константой 1.
Для функций справедливы равенства:
a v a = a; aa=a
a v b = b v a; ab=ba
(a v b) v c = a v (b v c); (ab)c=a(bc)
a v 1 = 1, a·1=1
a v (b · c)=(a v b)·(a v c)
a · (b v c)=(a · b) v (a · c)
a v (b · a)=a; a · (b v a)
(X v Y)’=X’ · Y’; (X · Y)’=X’ v Y’
X v X’ = 1; X · X’= 0
X’’=X
a v 0 = a; a · 0 = 0
a→b=a’ v b’
a↔b=(a→b) ·(b → a)

Все приведённые выше формулы проверяются с помощью таблиц булевых функций. Докажем последнюю формулу.
1. Составим таблицу:
2. Сравним третий и шестой столбцы, видим, что они одинаковы, значит функции стоящие в левой и правой части доказываемой формулы, принимают одинаковые значения для одинаковых наборов аргументов

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Для этого нужно:
Избавится от всех логических операций, содержащихся в формуле, заменив их основными – конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать используя равносильные формулы: A→B=A v B ;A↔B=(A v B) ∙(A’ v B’); A↔B=(A∙B) v (A’∙B’).
Заменить знак отрицания, относящийся к выражениям типа АВ или А v B, знаками отрицания. Относящимся к отдельным переменным высказываниям на основании формул А v B = AB; A’B’= A’ v B’
Избавится от знаков двойного отрицания: A=A’’
Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности, формулы поглощения.
Теорема: Формула алгебры высказываний является тождественно ложной тогда и только тогда, когда каждое слагаемое (т. е. каждое элементарное произведение) ее ДНФ содержит пару сомножителей, один из которых есть элемен­тарное высказывание, другой — его отрицание.

Можно построить КНФ для отрицания исходной формулы. Если окажется, что она удовлетворяет условиям теоремы, то исходная формула невыполнима, так как ее отрицание тож­дественно истинно.
В не перечисленных выше случаях формулы являются вы­полнимыми.
Рассмотрим, например, формулу:
(a٨b٨c)(a٨b٨c)(a٨b٨c)
При приведении этой формулы к КНФ среди дизъюнктивных одночленов будет а v b v с, что противоречит условию суще­ствования тавтологии.Поэтому данная формула - не тавтология.
При решении ряда задач часто бывает удобно использо­вать совершенную дизъюнктивную нормальную форму функ­ции (СДНФ) или совершенную конъюнктивную нормальную форму функции (СКНФ).
Одночлен от некоторых переменных называется совершен­ным, если каждая из этих переменных входит в него точно один раз либо со знаком отрицания, либо без него.

Конструктивно СДНФ для каждой формулы алгебры выс­казываний, приведенной к ДНФ, можно определить так: Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, облада­ющая следующими свойствами:
ДНФ не содержит двух одинаковых слагаемых.
Ни одно слагаемое не содержит одновременно двух одина­ковых сомножителей.
Ни одно слагаемое не содержит одновременно некоторое высказывание и его отрицание.
Каждое слагаемое содержит в качестве сомножителя либо переменное высказывание, либо его отрицание для всех переменных входящих в формулу.
Приведем, например, к СДНФ булеву функцию(a v b’) ∙ (a→c). Используя свойства булевых функций, получаем:
(a v b’) ∙ (a→c)= (a’ ∙ b’ )v (a’ ∙ c)=(a’ ∙ b’ ∙ a’) v (a’ ∙ b’ ∙ c)=(a’ ∙ b’) v (a’ ∙ b’ ∙ c)=a’ ∙ b‘=a’ ∙ b’(c v c’)=(a’ ∙ c ∙ b’) v (a’ ∙ c’ ∙ b’)

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

Построим, СДНФ и СКНФ для формулы A=(p→q) ^ (p v q). Для решения задачи используем истинную таблицу для А.

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