DiskretPDF

1. Булевы функции. Основные логические операции. Штрих Шеффера и стрелка Пирса. Выразимость одних операций через другие.

Буулева ф нкцияуу (или логиуческая функция, или функция аулгебры л гикиоу )[1] от n аргументов —

вдискретной математике — отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно», хотя

вобщем случае они рассматриваются как формальные символы, не несущие определённого

смысла.

Булевой функциейy=f(x1, x2... xn) от п переменных x1, x2, xnназывается любая функция, в которой

аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц (x1, x2... xn) ставится в соответствие значение 0 или

1.

В алгебре логики существует три основные операции:

Логическое отрицание {инверсия).

Обозначается: ¯А, ¬A, not А, не А.

Высказывание ¬А истинно при ложном А и ¬А ложно при истинном А.

Логическое умножение {конъюнкция).

Обозначается А&В, A and В, А*В, А^В, АВ, А и В.

Высказывание А ^ В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Логическое сложение {дизъюнкция).

Обозначается: A v В, A or В, А + В, А или В.

Высказывание A v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Остальные операции алгебры логики выражаются через первые три операции: отрицание, конъюнкцию и дизъюнкцию. Перечислим их.

Логическое следование {импликация).

Обозначается: А → В, А => В.

Высказывание А → В ложно только тогда, когда А истинно, а В ложно.

Важно: в операции импликации посылка А не обязана быть истинной, в отличие от логического оператора в языках программирования «если А, то В».

Импликация выражается через дизъюнкцию и отрицание: А => В = A v В.

Эквивалентность (равносильность, необходимо и достаточно).

Обозначается: А ~ В, А <=> В, А = В.

Высказывание А <=> В истинно тогда и только тогда, когда значения А и В совпадают. Эквивалентность выражается через отрицание, дизъюнкцию и конъюнкцию: А <=> В = (¬А v В) ^ (¬B v А).

Исключающее ИЛИ.

Обозначается A XOR В.

Высказывание A XOR В истинно, когда А и В не равны.

Стрелка Пирса

Это высказывание истинно только тогда, когда ложны оба высказывания, входящие в это сложное высказывание.

А ¯ В ≡

Штрих Шеффера

Высказывание со штрихом Шеффера ложно в том случае, если истинны и А и В одновременно. В противном случае истинны

А|В ≡

Порядок исполнения операций задается круглыми скобками. При отсутствии скобок порядок выполнения операций следующий: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

2. ДНФ и КНФ. Теоремы о совершенных ДНФ и КНФ.

ДНФ - нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть

приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

КНФ - нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.[1] Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.

Совершеунная дизъюнкт внаяиу норм льнаяау ф рмаоу(СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных конъюнкций

в каждой конъюнкции нет одинаковых пропозициональных букв

каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в

данную ДНФ пропозициональных букв, причём в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причём единственная.

Совершеунная конъюнкт внаяиу норм льнаяау ф рмаоу(СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций

в каждой дизъюнкции нет одинаковых пропозициональных переменных

каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

3.Минимальные ДНФ. Импликанты и простые импликанты, сокращенные ДНФ и тупиковые ДНФ. Алгоритм нахождения минимальной ДНФ.

ДНФ наименьшего веса называется минимальной. Весом ДНФ называется количество литералов, входящих в ДНФ.

Элементарный конъюнктназывается импликантом булевой

функции, если , для всех x1, x2, . . . , xn B. Если K присутствует в ДНФ функции f, то K является импликантом f.

Импликант функции f называется простым импликантом, если ни одна его собственная часть не

является импликантом f.

Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым импликантом.

Доказательство. Пусть является минимальной ДНФ. Докажем, что K1 (например) является простым импликантом. Пусть не так: существует импликант K’, являющийся собственной частью K1. Тогда

то есть получили ДНФ, с меньшим

весом чем минимальная. Противоречие.

Следствие. Пусть P — множество всех простых импликантов булевой функции f. Тогда.

Доказательство. Пусть минимальная ДНФ. Тогда

Дизъюнкция всех простых импликантов функции f называется

сокращенной ДНФ.

Пусть P — множество всех простых импликантов f. ДНФ вида где S P,

называется тупиковой ДНФ, если для имеем Теорема. Минимальная ДНФ является тупиковой.

Доказательство. Пусть минимальная ДНФ для f. Ясно, что вес

будет еще меньше при

Нахождение минимальной ДНФ. 1. Строим сокращенную ДНФ.

2. Последовательно удаляем лишние конъюнкты из сокращенной ДНФ, находим все тупиковые ДНФ.

3. Находим минимальную ДНФ, выбирая тупиковую ДНФ с наименьшим весом.

?4. Монотонные функции. Теорема о сокращенной ДНФ для монотонных функций. Композиция монотонных функций есть снова монотонная функция.

Монотоунная ф нкцияуу — это функция, приращение которой не меняет знака, то есть либо всегда неотрицательное, либо всегда неположительное[1]. Если в дополнение приращение не равно нулю, то функция называется строуго монот ннойоу . Монотонная функция — это функция, меняющаяся в одном и том же направлении.

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции Равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

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

Конъюнкция — монотонная функция. Поэтому элементарные конъюнкты без отрицаний — монотонные функции.

Дизъюнкция — монотонная функция. Поэтому дизъюнкции нескольких элементарных конъюнктов без отрицаний — монотонные функции.

5. Многочлен Жегалкина. Представимость булевых функций многочленами Жегалкина.

Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.

Примеры. 0, 1, xy, 1 + x, x + y, x + y + xy, 1 + x + xy + xyz,

Теорема. Любая булева функция представляется в виде многочлена Жегалкина, причем единственным образом.

6. Замкнутые классы булевых функций. Классы T_0 и T_1. Классы монотонных, линейных и самодвойственных функций.

Если любаябулева функция, являющаясясуперпозициейфункций некоторого множества принадлежит этому множеству, то такое множество называютзамкнутым

Замыканиеммножества функций называется такое подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества

Говорят, что функциясохраняет ноль, если.

Говорят, что функциясохраняет один, если.

7. Полные классы функций. Теорема Поста о полноте (доказательство теоремы слева направо).

Множество булевых функций называетсяполной системой, если замыкание этого множества совпадает с множеством всех функций.

Набор булевых функций K является полным тогда и только тогда, когда он не содержится полностью ни в

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

8. Лемма о несамодвойственной функции. Лемма о немонотонной функции.

Лемма. Если f S , то 0, 1 [{f,}].

Док-во. Пусть f S . Тогда существует набор (σ1, . . . , σn) такой, что Тогда

Поэтому для формулы имеем Таким образом, одна из констант 0, 1 является формулой над {f, }. Подставляя ее в отрицание, получим другую константу.

Лемма о немонотонной функции : Если f M , то я [{f, 0, 1}].

Пусть f M.Тогда существует наборы (σ1, . . . , σn) ≤ (τ1, . . . τn) такие, что f(σ1, . .

. , σn) = 1 и

f(τ1, . . . τn) = 0. Определим формулы

Тогда gi(0) = σi и gi(1) = τi для всех i = 1,..,n. Поэтому для формулы h(x) = f(g0(x),

. . . , gn(x)) имеем h(0) = 1 и h(1) = 0, то есть h(x) = x.

9. Лемма о функциях, не сохраняющих T_0 и T_1. Теорема Поста о полноте (доказательство теоремы справа налево).

Лемма. Если f T0 и g T1, то либо [{f, g}], либо 0, 1 [{f, g}]. Доказательство. Имеем f(0, . . . , 0) = 1 и g(1, . . . , 1) = 0. Если f(1, . . . , 1) = 0, то f(x, . . . , x) = x и лемма доказана. Пусть теперь f(1, . . . , 1) = 1. Тогда f(x, . . . , x) = 1 и, следовательно, 1 [{f, g}].

Остается показать, что 0 [{f, g}]:

Следствие. Если f T0, g T1, p S и q M , то либо, 0, 1 [{f, g, p}], либо , 0, 1 [{f, g, q}].

Теорема (критерий Поста). Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0, T1, M, L,S.

Док­во. Обратно, пусть B содержится в одном из пяти вышеперечисленных классов. Выделим в B систему функций fT0, fT1, f S , f M , f L, не принадлежащих классам

T0 , T1 , S , M и L соответственно. Не ограничивая общности можно считать, что каждая из этих функций зависит от фиксированного числа переменных x1, . . . , xn .Покажем, что при помощи функций fT0, fT1 и fS можно получить константы 0 и 1. Если fT0(1, . . . ,1) = 1, то функция ϕ(x) = fT0(x, . . . , x) тождественно равна 1, поскольку ϕ(0) = 1 = ϕ(1). Константа 0 получается из fT1, поскольку

fT1(1, . . . ,1) = 0. Если же fT0(1, . . . ,1) = 0, то ϕ(x) = fT0(x, . . . , x) = !x, поскольку ϕ(0) = fT0(0, . . . ,0) = 1 и ϕ(1) = fT(1, . . . ,1) = 0. По лемме 10 при помощи x и fS можно получить константу. Вторая константа получается применением x. при помощи констант 0, 1 и функции fM можно получить !x. Наконец, по лемме 12 при помощи констант 0, 1 и функций ! x и fL можно получить x1 & x2 . Теперь полнота системы B следует из полноты конъюнкции и отрицания. Неполный класс функций A назовем предполным, если класс A {f} будет полным для любой функции f 6 A.