Алгебра логических значений. Лекция 8

1. Алгебра логических значений

2.

Пример алгебры дает множество {0,1}
истинностных значений высказываний с nарными операциями F , которые являются
функциями истинностных значений формул
X 1 ,..., X n ,
логики
высказываний
образованных с помощью n пропозициональных
переменных X 1 ,..., X n .
X
Формула
определяет
унарную
операцию F F X (x) , которая обозначается
символом x и называется отрицанием или
дополнением переменной x .

3.

Формулы X Y , X Y определяют
бинарные операции F FX Y ( x, y ) , F FX Y ( x, y ) ,
которые обозначаются соответственно символами
x y,x y
и называются дизъюнкцией и
конъюнкцией переменных x ,y.
Операция x y иногда называется также
объединением или суммой переменных x ,y и
обозначается соответственно через x y или
x y.
Операция x y иногда называется также
пересечением или произведением переменных x ,y
и обозначается соответственно через x y или
x y.

4.

Алгебра B=({0,1}, , , ) впервые была введена
в 19-ом веке английским математиком Дж.Булем с
целью применения в логике математических
методов.
Поэтому эта алгебра называется алгеброй Буля
или алгеброй логических значений.

5.

Теорема.
Алгебра
Буля
B=({0,1}, , , )
удовлетворяет свойствам:
1) a (b c) (a b) c , a (b c) (a b) c –
ассоциативность дизъюнкции и конъюнкции;
2) a b b a , a b b a – коммутативность
дизъюнкции и конъюнкции;
a a a
3) a a a ,
–
идемпотентность
дизъюнкции и конъюнкции;
4) a (b c) (a b) (a c) , a (b c) (a b) (a c)
– дистрибутивность соответственно конъюнкции
относительно
дизъюнкции
и
дизъюнкции
относительно конъюнкции;

6.

5) (a ) a – идемпотентность дополнения;
6) (a b) a b , (a b) a b – законы де
Моргана;
a (a b) a
7) a (a b) a ,
–
законы
поглощения;
8) a a 1 , a a 0
– характеристическое
свойство дополнения,
a 1 a
9) a 1 1 ,
– характеристическое
свойство наибольшего элемента 1,
10) a 0 a , a 0 0 – характеристическое
свойство наименьшего элемента 0.

7. Булевы многочлены и булевы функции

8.

Для описания алгебраических свойств булевых
алгебр
используются
формулы,
которые
называются булевыми многочленами и которые
образованы
из
булевых
переменных
x,y,…(принимающих значения 0,1) и символов
булевых операций +, , по следующим правилам:
1)
все булевы переменные x,y,… и символы 0,1
– булевы многочлены;
2)
если p и q – булевы многочлены, то
таковыми являются выражения
p q , p q , p .

9.

Если p образован с помощью x1 ,..., xn , то он
обозначается p( x1,..., xn ) .
Множество всех булевых многочленов от n
переменных обозначим Pn .
Если в p( x1 ,..., xn ) вместо переменных x1 ,..., xn
подставить произвольные значения a1 ,..., an из
множества B, то в результате вычислений
получится некоторый элемент p(a1,..., an ) алгебры B.
Каждый булев многочлен p( x1,..., xn ) определяет
отображение p : Bn B , которое называется булевой
полиномиальной функцией, определяемой булевым
многочленом p( x1 ,..., xn ) .

10.

p, q Pn
Определение. Булевы многочлены
называются
эквивалентными,
если
они
определяют одну и ту же булеву полиномиальную
функцию, т.е. p q .
Символическая запись: p ~ q или просто p q .
Бинарное
отношение
~
является
эквивалентностью на множестве Pn .
Классы эквивалентности p {q Pn : p ~ q} ,
образуют фактор-множество Pn / ~ { p : p Pn } .
Полные системы представителей этого фактормножества называются системами нормальных
форм булевых многочленов.

11.

Для булевой переменной x и {0,1} положим:
x, если 1,
x
x , если 0.
x
называется литерой.
Выражение
Литера или конъюнкция (соответственно,
дизъюнкция) литер называется конъюнктом
(соответственно, дизъюнктом).
Конъюнкт (дизъюнкт) называется совершенным,
если он содержит все булевы переменные
рассматриваемой формулы.

12.

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

13.

Теорема. Любая булева функция f:Bn B
является булевой полиномиальной функцией
следующих булевых многочленов:
pf
f 1,..., n x1 ...xn
1
n
1 ,..., n B n
и
qf
( f n 1,..., n x1 ... xn ) .
1
1 ,..., n B
n

14.

Следствие 1. Если булева функция f:Bn B не
равна тождественно нулю, то она является
булевой полиномиальной функцией следующей
совершенной дизъюнктивной нормальной формы
pf
1
x1 ...xn ,
n
1 ,..., n B n ,
f 1 ,..., n 1
которая называется совершенной дизъюнктивной
нормальной формой (сокращенно СДНФ)
функции f .

15.

Следствие 2. Если булева функция f:Bn B не
равна тождественно единице, то она является
булевой полиномиальной функцией следующей
совершенной конъюнктивной нормальной формы
qf
1
( x1 ... x n n )
1 ,..., n B n ,
f 1 ,..., n 0
,
которая называется совершенной конъюнктивной
нормальной
формой
(сокращенно
СКНФ)
функции f .

16.

Алгоритм нахождения СДНФ и СКНФ функции
f:Bn B:
1. Составить таблицу значений функции f и
добавить к ней два дополнительных столбца с
заголовками «Совершенные конъюнкты» и
«Совершенные дизъюнкты».
2. Если при значениях x1 k1 ,..., xn kn значение
функции f равно 1, то в соответствующей строке
таблицы в столбце «Совершенные конъюнкты»
k1
x1 ...xnk n
записать
конъюнкт
и в столбце
«Совершенные дизъюнкты» сделать прочерк (при
1
0
x
x
x
x ).
этом
и

17.

3. Если при значениях x1 m1,..., xn mn значение
функции f равно 0, то в соответствующей строке таблицы
в столбце «Совершенные дизъюнкты» записать
m
дизъюнкт x1 1 ... xnmn и в столбце «Совершенные
конъюнкты» сделать прочерк.
x1
…
xn
...
f x1 ,..., xn
…
…
…
…
…
…
…
...
...
...
...
...
…
1
…
0
…
k1
…
m1
…
kn
…
mn
…
Совершенные Совершенные
конъюнкты
дизъюнкты
…
…
–
x1k1 ...xnk n
…
–
…
x1m1 ... xnmn
…
…

18.

4. Дизъюнкция полученных совершенных
конъюнктов
k1
kn
x1 ...xn +…
является СДНФ функции f , конъюнкция
полученных совершенных дизъюнктов
( x1m1 ... xnmn ) ...
является СКНФ функции f .

19. Минимизация булевых многочленов

20.

Рассмотрим вопрос минимизации ДНФ p .
Конъюнкт q называется импликантом формы p,
если pq q . Импликанты, минимальные по
числу вхождений в них булевых переменных,
называются
простыми
импликантами.
Дизъюнкция всех простых импликант формы p
называется сокращенной ДНФ.
Лемма 1. Любая ДНФ p
некоторой сокращенной ДНФ.
эквивалентна

21.

Сокращенную ДНФ формы p можно получить
методом Квайна с помощью последовательного
применения следующих двух видов операций:
1) операция склеивания, которая для конъюнктов q
и булевых переменных x определяется по формуле:
qx qx qx qx q ;
2) операция поглощения, которая для конъюнктов q,
булевых переменных x и значений {0,1}
определяется по формуле:
qx q q .

22.

Пример. Найдем сокращенную ДНФ для булева
многочлена
p x yz x yz xy z xyz xyz .
В результате применения операции склеивания к
различным парам конъюнктов многочлена p
получим ДНФ
x yz x yz xy z xyz xyz x y yz yz xz xy y .
В результате применения операции поглощения
к различным парам конъюнктов последней ДНФ
получим булев многочлен xz y , который является
сокращенной ДНФ булева многочлена p.

23.

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

24.

Минимальная ДНФ формы p получается с помощью
матрицы Квайна:
столбцы матрицы помечаются конъюнктами
p1 ,..., pm формы p ;
строки матрицы помечаются
q1 ,..., qk сокращенной ДНФ формы p ;
импликантами
на пересечении строки q i и столбца p j ставится
символ , если импликант q i является частью
конъюнкта p j .
Тупиковые ДНФ - дизъюнкции тех минимальных
наборов импликант, в строках которых имеются
звездочки для всех столбцов матрицы Квайна.
Тупиковые ДНФ с наименьшим числом вхождений
булевых
переменных
являются
искомыми
минимальными ДНФ формы p .

25.

Пример. Найдем минимальную ДНФ для многочлена
p x y z x y z xy z xyz .
В результате применения операции склеивания получим
ДНФ x y z x y z xy z xyz x y y z xz .
С помощью операции поглощения получим x y y z xz сокращенная ДНФ булева многочлена p. Матрица Квайна:
x y
y z
x y z
x y z
xy z
xyz
Минимальный набор импликант, в строках которых
имеются звездочки для всех столбцов матрицы Квайна,
состоит из конъюнктов x y и xz . Значит, x y xz минимальная ДНФ формы p .
xz

26.

Следствие 3. Любая булева функция, не
равная
тождественно
нулю,
представима
минимальной ДНФ и любая булева функция,
не
равная
тождественно
представима минимальной КНФ.
единице,

27. Системы булевых функций

28.

Операция отрицания является одной из
четырех булевых функций от одной переменной,
которые перечисляются в следующей таблице:
x
f1 ( x )
f 2 ( x)
f 3 ( x)
f 4 ( x)
0 0
0
1
1
1 0
1
0
1

29.

Операции дизъюнкция + и конъюнкция являются
примерами двух из шестнадцати булевых функций от
двух переменных, которые перечисляются в следующей
таблице:
x y
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
f16
0 0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0 1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1 0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1 1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
x
y
+
y
x
1
-
штрих
Функция f15 ( x, y ) f 2 ( x, y )
обозначается x | y .
f 9 ( x, y ) f8 ( x, y )
Функция
обозначается x y .
-
Шеффера,
стрелка
Пирса,

30.

Так f10 ( x, y) является функцией истинностных
значений формулы X Y , то она называется
эквивалентностью и обозначается x y . Функция
f 7 ( x, y ) f10 ( x, y )
– отрицание эквивалентности, она
называется суммой Жегалкина и обозначается x y .
Так как функция f14 ( x, y) является функцией
истинностных значений формулы X Y , то она
называется импликацией и обозначается x y .
Так как функция f12 ( x, y) является функцией
истинностных значений формулы Y X , то она
называется обратной импликацией и обозначается
x y.