Проблема разрешимости в АВ
Существует ли алгоритм, который относительно произвольной формулы АВ позволяет установить, является она тавтологией или нет?
I Составление и анализ таблицы истинности
Достоинства: простота
Недостатки: с увеличением n количества переменных в формуле число строк в таблице 2n «растет» слишком быстро
II Рассуждения
Эффективны при наличии в формуле большого количества импликаций. Известны в этом случае под названием алгоритм редукции.
III Равносильные преобразования
Выполняя преобразования формулы, нужно получить выражение @1 или то, которое заведомо 7(@1). В общем случае вывод о наличии тождественной истинности лучше делать, приведя данную формулу к КНФ.
Л.1 Конъюнкция является тавтологией Û каждый член в ее составе является тавтологией.
Л.2 Дизъюнкция является тавтологией Û среди ее членов присутствуют некоторая переменная и ее отрицание.
Т.1 Формула является тавтологией Û каждый дизъюнкт в составе ее КНФ содержит некоторую переменную и ее отрицание.
Т.2 Формула является противоречием Û каждый конъюнкт в составе ее ДНФ содержит некоторую переменную и ее отрицание.
IV Алгоритм Квайна
Идея: последовательная (а не одновременная) подстановка в формулу F(X1, X2, …, Xn) значений переменных и анализ логических значений получившихся выражений. В результате вывод о том, тавтология данная формула или нет, делается после прохождения только части связанного с формулой семантического дерева.
Пример. ? F(X,Y,Z) @ (X®(Y®Z))«(Y®(X®Z))
1) X=0: F(0,Y,Z) @ (0®(Y®Z))«(Y®(0®Z)) @ 1« (Y®1) @ 1« 1 @ 1.
Значит, на всех наборах вида (0,Y,Z) формула F принимает значение 1.
2) X=1: F(1,Y,Z) @ (1®(Y®Z))«(Y®(1®Z)) @ (Y®Z)«(Y®Z) @ 1.
Таким образом, и на наборах (1,Y,Z) формула F принимает значение 1.
Семантическое дерево для формулы трех переменных имеет вид
 X
| 
| 7X |
  Y
|  7Y Y
| 7Y 
|
 
|    
|  
|
| Z 7Z | Z 7Z Z | 7Z Z 7Z |
Пользуясь алгоритмом Квайна, мы установили, что F – тавтология, пройдя только следующую часть дерева:
| X
|
| 7X |
1 1
Булевы функции (БФ)
ОК БФ 1
Булева функция (БФ) n аргументов
f: {0, 1}n ® {0, 1}
Способы задания: табличный, вектором значений, аналитический
Т. Существует ровно 
различных булевых функций от n аргументов.
(Почему?)
Булевы функции одного аргумента
f: {0, 1} ® {0, 1}
| x | f(x) | f0(x) | f1(x) | f2(x) | f3(x) |
| f(0) | |||||
| f(1) |
f0(x)=0 – тождественный ноль, f1(x)=x – тождественная,
f2(x)=x¢ – отрицание, f3(x)=1 – тождественная единица.
Булевы функции двух аргументов
f: {0, 1}2 ® {0, 1}
| x | y | f(x, y) | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 |
| f(0, 0) | ||||||||||||||||||
| f(0, 1) | ||||||||||||||||||
| f(1, 0) | ||||||||||||||||||
| f(1, 1) |
f0(x,y)=0 – тождественный ноль,
f1(x,y)=x×y – конъюнкция,
f2(x,y)=(x®y)¢
f3(x,y)=x
f4(x,y)=(y®x)¢
f5(x,y)=y
f6(x,y)= (x«y)¢=x+y – сумма Жегалкина (сложение по модулю 2, XOR, «исключающее ИЛИ»)
f7(x,y)=xÚy – дизъюнкция
f8(x,y)=(xÚy)¢=x¯y – стрелка Пирса
f9(x,y)=x«y – эквивалентность
f10(x,y)=y¢
f11(x,y)=y®x
f12(x,y)=x¢
f13(x,y)=x®y – импликация
f14(x,y)=(x×y)¢=x½y – штрих Шеффера
f15(x,y)=1 – тождественная единица
ОК БФ 2
Существенная переменная xi функции f(x1, x2, …, xn):
f(a1, a2, …, ai-1, 0, ai+1, …, an) ¹ f(a1, a2, …, ai-1, 1, ai+1, …, an)
на некотором наборе (a1, a2, …, ai-1, ai+1, …, an) конкретных значений переменных (x1, x2, …, xi-1, xi+1, …, xn)
Удаление (введение) фиктивной переменной
 x
| y | z | f(x,y,z) |
 1
| |||
 1
| |||
 1
| |||
| 1
|
Равенство БФ с точностью до набора фиктивных переменных
Свойства булевых операций:
1) идемпотентность конъюнкции, дизъюнкции
2) ассоциативность конъюнкции, дизъюнкции, суммы Жегалкина
3) коммутативность конъюнкции, дизъюнкции, суммы Жегалкина
4) дистрибутивность конъюнкции относительно дизъюнкции, дизъюнкции
относительно конъюнкции, конъюнкции относительно суммы Жегалкина
5) инволютивность отрицания
6) законы поглощения
7) законы де Моргана
8) свойства 0 и 1
9) свойства отрицания
10) выражения операций ®, « через другие операции
ОК БФ 3
Разложение булевых функций по переменным x1, x2, x3, …, xk
(1)
(2)
СДНФ и СКНФ булевых выражений, правила их составления
Многочлен Жегалкина БФ от n переменных, правило его составления
Пример.
| x | y | z | f(x, y, z) | С-конъюнкты | С-дизъюнкты |
| xÚyÚz | |||||
| xÚyÚz | |||||
| xyz | |||||
| xyz | |||||
| xyz | |||||
| xyz | |||||
| xÚyÚz | |||||
| xyz |
СДНФ f(x, y, z): xyz Ú xyz Ú xyz Ú xyz Ú xyz
СКНФ f(x, y, z): (xÚyÚz) (xÚyÚz) (xÚyÚz)
Многочлен Жегалкина f(x, y, z): xyz + xyz + xyz + xyz + xyz =
= xy (z + z)+ xy(z + z) + xyz = (x+1)y + x(y+1) +xyz = xy + y + xy + x + xyz =
= xyz + x + y
Линейная и нелинейная БФ
ОК БФ 4
Элементарная суперпозиция (суперпозиция 1-го ранга) функций f1, f2, …, fm
Класс булевых функций М={f1, f2, f3, …, fm} называется полным,
если любая булева функция может быть выражена через f1, f2, f3, …, fm
с помощью суперпозиций
Т.Пусть система М = {f1, f2, f3, …, fm} – полная, и любая из функций f1, f2, f3, …, fmможет быть выражена через функции g1, g2, g3, …, gkс помощью суперпозиций. Тогда система {g1, g2, g3, …, gk} –полная. (Докажите!)
Замыканием класса булевых функций M называется множество, состоящее из этих функций и их всевозможных суперпозиций
Класс булевых функций М={f1, f2, f3, …, fm} называется замкнутым,
если [M] = M.
Важнейшие замкнутые классы
T0 = {fÎP2| f (0, 0, 0, …, 0)=0} – класс функций, сохраняющих ноль.
T1 = {fÎP2| f (1, 1, 1, …, 1)=1} – класс функций, сохраняющих единицу.
TS = {fÎP2| f = f*} – класс самодвойственных функций.
f = f* Û f (x1, x2, x3, …, xn) = f(x1, x2, x3, …, xn),
т.е. f самодвойственна, если на противоположных наборах значений аргументов она принимает противоположные значения.
a 
Î{0, 1}n, b 
Î{0, 1}n,
a предшествует b, если ai bi по всем i=1, …, n
TM = {fÎP2| для всех a, bÎ{0, 1}n a b Þ f(a) f(b)} – класс монотонных функций.
TL = {fÎP2| f = a0+a1x1+a2x2+…+anxn, aiÎ{0, 1}, i = 0, …, n} – класс линейных функций.
Проверка принадлежности булевой функции замкнутым классам T0, T1, TS, TM осуществляется по таблице истинности. Проверка принадлежности булевой функции классу TL осуществляется путем построения полинома Жегалкина.
T0, T1, TS, TM, TL замкнуты, неполны, попарно различны
Т. (Поста) Система M булевых функций функционально полна тогда и только тогда, когда она не содержится целиком ни в одном из пяти замкнутых классов T0, T1, TS, TM, TL.
Другие формулировки теоремы Поста
ОК БФ 5
Под релейно-контактной схемой (РКС) понимается устройство из проводников и двухпозиционных контактов.
Контакты РКС: замыкающие и размыкающие
Всей РКС ставится в соответствие булева функция f(x1, x2, x3, …, xn) такая, что
f(x1, x2, x3, …, xn) = 
Такая функция называется функцией проводимости РКС.
x f (x) = x
x f (x) = x
x y f (x, y) = xy
x
f (x,y) = xÚy
y
Составление РКС с заданными условиями работы называется задачей синтеза РКС.
Упрощение РКС называется задачей анализа таких схем.
Пример.
| x | y | z | f(x, y, z) | С-конъюнкты |
| xyz | ||||
| xyz | ||||
| xyz | ||||
| xyz |
f (x, y, z) = xyz Ú xyz Ú xyz Ú xyz схема 1
f (x, y, z) = yz Ú xz Ú xy схема 2
f (x, y, z) = y(zÚx) Ú xz схема 3
Изобразите каждую из схем
ОК БФ 6
Рассмотрим задачу поиска для данной булевой функции ДНФ, содержащей наименьшее число вхождений переменных.
Формула j(x1, x2, x3, …, xn) называется импликантой булевой функции f, если j – импликанта СДНФ, представляющей f.
Импликанта j называется простой, если после отбрасывания любой литеры из j полученная формула не является импликантой.
Сокращенная ДНФ Þ Тупиковая ДНФ Þ Минимальная ДНФ
Метод минимизирующих карт
| x1 | x2 | … | xn | x1x2 | x1x3 | … | xn-1xn | x1x2 x3 | … | xn-2xn-1 xn | … | x1x2… xn |
| x1 | x2 | … | xn | x1x2 | x1x3 | … | xn-1xn | x1x2 x3 | … | xn-2xn-1 xn | … | x1x2… xn |
| x1 | x2 | … | xn | x1x2 | x1x3 | … | xn-1xn | x1x2x3 | … | xn-2xn-1 xn | … | x1x2… xn |
| … | ||||||||||||
| x1 | x2 | … | xn | x1x2 | x1x3 | … | xn-1xn | x1x2 x3 | … | xn-2xn-1 xn | … | x1x2… xn |
| x1 | x2 | … | xn | x1x2 | x1x3 | … | xn-1xn | x1x2x3 | … | xn-2xn-1 xn | … | x1x2… xn |
| … | ||||||||||||
| x1 | x2 | … | xn | x1x2 | x1x3 | … | xn-1xn | x1x2x3 | … | xn-2xn-1xn | … | x1x2… xn |
Т.Если совершенный конъюнкт i-ой строки таблицы не входит в состав СДНФ функции f(x1, x2, x3, …, xn), то никакой конъюнкт этой строки не содержится в составе никакой ДНФ, выражающей данную функцию.
Метод Квайна
а) Операция полного склеивания: j × x Ú j × x = j
б) Операция неполного склеивания: j × x Ú j × x = j Ú j × x Ú j × x
в) О) операция элементарного поглощения: j ×x Ú j =j , j × x Ú j = j
Т.(Квайна) Если в СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ.
таблица Квайна
Карты Карно
 x
|  x
| ||
 y
| z | ||
| 
| z | |
| |||
| y | z |
f (x, y, z) = xyz Ú xyz Ú xyz Ú xyz Ú xyz = y Ú xz
Логика предикатов (ЛП)
ОК ЛП 1
Все люди смертны. Сократ – человек. Следовательно, Сократ смертен.
A, B C
Высказывание
 |  |
Объект Свойство
(предикат)
n-местным предикатом, определенным на множестве M1× M2× M3×…× Mn, называется повествовательное предложение, содержащее переменные x1, x2, x3, ..., xn, которое превращается в высказывание при подстановке вместо x1, x2, x3, ..., xn набора конкретных значений из M1× M2× M3×…× Mn
P(x1, x2, x3, ..., xn)
Q, R, S, T, …
Предметные переменные
Предметная область
Множество истинности предиката P(x1, x2, x3, ..., xn)
I(P) = {(a1, a2, a3, …, an)| (P(a1, a2, a3, …, an) = 1)}
Классификация предикатов
I(P) = M1× M2× M3×…× Mn
I(P) = Æ
I(P) ¹ Æ
I(P) ¹ M1× M2× M3×…× Mn
Логические операции над предикатами
Кванторные операции над предикатами
"x P(x) «для любого (значения) x P(x) (истинное высказывание)»
$x P(x) «найдется (значение) x такое, что P(x) (истинное высказывание)»
ОК ЛП 2
Алфавит ЛП:
- предметные переменные x, y, z, xi, yi (iÎN)
- нульместные предикатные переменные P, Q, R, …
- n-местные (n1) предикатные переменные
- P1(n)( , , …, ), P2(n)( , , …, ), …, Q(n)( , , …, ) R(n)( , , …, ) с указанием числа свободных мест в них
- символы логических операций
- кванторы
- вспомогательные символы
1 Каждая нульместная предикатная переменная есть формула
2 Если P(n)( , , …, ) - n-местная (n1) предикатная переменная и x1, x2, …, xn – предметные переменные, то P(x1, x2, …, xn) – формула, в которой x1, x2, …, xn – свободные
3 Если F – формула, то 7F – тоже формула, в которой свободными являются те и только те переменные, которые свободны в F
4 Если F1, F2 – формулы, причем их общие переменные свободны или связаны в каждой из них, то (F1*F2), где * – один из символов Ù, Ú, ®, «, являются формулами. Свободными (связанными) в них являются те переменные, которые свободны (связаны) хотя бы в одной из формул F1, F2
5 Если F – формула и x входит в нее свободно, то ("x F) и ($x F) являются формулами, у которых x – связанная переменная
6 Других формул ЛП нет
Формулы, определенные в п.п. 1, 2, называются элементарными
Интерпретация формулы ЛП:
указание предметной области;
задание конкретных значений предикатных переменных;
при наличии свободных предметных переменных – указание их значений
Классификация формул ЛП
Нахождение общезначимых формул является одной из важнейших задач ЛП
Т. (Черча, 1936) Не существует алгоритма, позволяющего установить, общезначима или нет произвольная формула ЛП