Лекция 13_3гр

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

2.

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

3.

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

4.

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

5.

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

6.

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

7.

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

8. Переключательные схемы

9.

Рассматриваются
электрические
ПС,
представляющие собой соединенные проводниками
переключатели и источники тока.
Условимся обозначать символом 1 протекание
тока в проводниках и символом 0 – отсутствие тока
в проводниках.
P2
P1
P3
A
B
P4
P5

10.

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

11.

Переключатели p,q могут быть
последовательно или параллельно.
соединены
p
p
q
q
Рис.3
Рис.4
Через
последовательно
соединенные
переключатели p,q ток проходит в том и только том
случае, если p=q=1 такое соединение
моделируется булевым многочленом pq.
Через параллельно соединенные переключатели
p,q ток не проходит в том и только том случае, если
p=q=0 - такое соединение моделируется булевым
многочленом p+q.

12.

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

13.

Переключательную схему, моделирующую булев
многочлен p p x1 ,..., xn , можно представлять в виде
устройства с n входами и одним выходом, которое
преобразует входные булевы значения x1 a1,..., xn an
в выходное булево значение p a1,..., an .
Графически
диаграммой:
такое
устройство
a1
a2
an
p
p a1,..., an
изображается

14.

Простейшие булевы многочлены моделируют
ПС, которые называются логическими элементами
(или вентилями) и обозначаются специальными
диаграммами.
Примеры.
p ( x ) x
Булев
многочлен
моделирует
устройство с одним входом и одним выходом,
которое изображается диаграммой
a
и называется NOT-элементом.
a

15.

Булев многочлен p x1 ,..., xn x1...xn моделирует
устройство с n входами и одним выходом, которое
изображается диаграммой
a1
a2
p
a1a2 ...an
an
и называется AND-элементом.

16.

p x1 ,..., xn x1 ... xn
Булев
многочлен
моделирует устройство с n входами и одним
выходом, которое изображается диаграммой
a1
a2
an
и называется OR-элементом.
a1 a2 ... an

17.

Примеры.
1. Построим ПС, которая моделирует сложение двух
двоичных цифр и называется полусумматором. Такая
ПС имеет два входа a1 , a2 и два выхода s(a1, a2 ) , c(a1, a2 ) ,
которые описывают два разряда суммы a1 a2 .
Таблица этих булевых функций имеет следующий вид:
a1 a2 s(a1, a2 ) c(a1, a2 )
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1

18.

СДНФ функций: c( x1, x2 ) x1x2 , s( x1 , x2 ) x1 x2 x1 x2 .
s( x1 , x2 ) x1 x2 x1 x2 ( x1 x2 ) ( x1 x2 ) ( x1 x2 )( x1 x2 )
( x1 x1 x1 x2 x2 x1 x2 x2 ) ( x1 x2 x1 x2 ) ( x1 x2 ) ( x1 x2 ) c ( x1 x2 ) ,
Полусумматор представляется диаграммой:
a1
c(a1, a2 )
s(a1, a2 )
a2

19.

Символически
диаграммой:
полусумматор
a1 a2
a1
a2
изображается
ПС
a1 a2
Сложностью ПС называется число логических
элементов в этой схеме.
Полусумматор реализуется ПС сложности 4.

20.

Примеры.
2. Построим ПС, которая моделирует сложение трех
двоичных цифр и называется сумматором. Такая ПС
a1 , a2 , a3
имеет
три
входа
и
два
выхода
s (a1 , a2 , a3 ) , c (a1 , a2 , a3 ) , которые описывают два разряда
суммы a1 a2 a3 .
Легко проверить, что
Реализуется сумматор ПС сложности 9.

21.

С помощью полусумматоров такую ПС можно
представить следующей диаграммой:
a1
s(a1, a2 , a3 )
a2
s(a2 , a3 ) ПС
a3
c(a2 , a3 )
ПС
c(a1, s(a2 , a3 ))
c(a1, a2 , a3 )
Сумматор реализуется ПС сложности 9.

22.

Теорема 1. Суммирование двух n-разрядных
двоичных чисел реализуется ПС сложности
которая
обозначается
сумматором порядка n.
и
называется
Теорема 2. Умножение двух n-разрядных
двоичных чисел реализуется ПС сложности
которая обозначается
и называется
умножителем порядка n.

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

24.

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

25.

Операции дизъюнкция + и конъюнкция являются
примерами двух из шестнадцати булевых функций от
двух переменных, которые перечисляются в следующей
таблице:
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 .
-
Шеффера,
стрелка
Пирса,

26.

Функция f10 ( x, y ) = x y - эквивалентность.
Функция f 7 ( x, y ) f10 ( x, y ) называется суммой
Жегалкина и обозначается x y .
Функция f14 ( x, y ) = x y - импликация.
Функция f3 ( x, y ) f14 ( x, y ) - обозначается x y .
Функция
импликация.
f12 ( x, y ) = x y
-
обратная
Функция f 5 ( x, y ) f12 ( x, y ) - обозначается x y .

27.

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

28.

Лемма. Булевы функции от двух переменных
взаимосвязаны следующими свойствами:
1) ( x y ) x y , ( xy ) x y – законы де Моргана;
2) x xy x , x( x y) x – законы поглощения;
3) x x 1 , xx 0
– характеристическое
свойство отрицания;
4) x 1 1, x 1 x – характеристическое свойство
элемента 1;
x 0 0 – характеристическое
5) x 0 x ,
свойство элемента 0;
xy ( x y )
6) x y ( x y ) ,
– взаимосвязь
конъюнкции и дизъюнкции;
x y ( xy )
7) x y x y ,
– взаимосвязь
импликации с дизъюнкцией, конъюнкцией и
отрицанием;

29.

8) x y ( x y)( y x) , x y ( x y )( x y ) ;
xy ( x | y ) ( x | y ) | ( x | y ) ,
x x | x ,
9) x | y ( xy ) ,
x y x | y ( x | x) | ( y | y ) – взаимосвязь штриха
Шеффера
с
дизъюнкцией,
конъюнкцией
и
отрицанием;
10) x y ( x y) , x x x , x y ( x y) ( x y) ( x y) ,
xy x y ( x x) ( y y) – взаимосвязь стрелки
Пирса с дизъюнкцией, конъюнкцией и отрицанием;
11) x y y x , ( x y) z x ( y z ) , x( y z) xy xz,
x 1 x ,
x x 0,
x 0 x,
x x 1
–
характеристическое свойство суммы Жегалкина;
x y x y 1,
x y xy x 1 ,
12) x y xy x y ,
x y ( x 1)( y 1) 1 x y xy
–
взаимосвязь
суммы Жегалкина с дизъюнкцией, конъюнкцией,
отрицанием, импликацией и эквивалентностью.

30.

Определение. Суперпозицией булевых функций
g ( y1 ,..., ym ) и h1 ( x1 ,..., xn ) , …, hm ( x1 ,..., xn ) называется
булева функция f ( x1,..., xn ) , значения которой
определяются по формуле:
f ( x1 ,..., xn ) g h1 ( x1 ,..., xn ),..., hm ( x1 ,..., xn ) .
Для упрощения записи суперпозиции булевых
функций скобки по возможности опускаются с
учетом следующего приоритета выполнения
булевых операций: , и затем все остальные
операции.

31.

Определение.
Система
F f1 ,..., f k называется
булевых
функций
- полной, если любая булева функция может быть
представлена в виде суперпозиции функций из этой
системы F;
замкнутой, если она содержит любые
суперпозиции функций из этой системы F.
Для любой системы булевых функций F есть
наименьшая замкнутая система булевых функций
, содержащая систему F. Система
называется
замыканием системы булевых функций F.

32.

Проблема. Найти критерий полноты системы
булевых функций.
Теорема Жегалкина. Любая булева функция f от
n переменных представима в виде следующего
полинома Жегалкина
f ( x1 ,..., xn )
i1 ,..., ik
xi1 ...xik c
для некоторых значений c 0,1 и 1 i1 ... ik n .
Причем такое представление булевой функции f
единственно с точностью до порядка слагаемых.

33.

Определение. Булева функция f называется линейной,
если ее представление полиномом Жегалкина не
содержит произведения переменных.
Множество всех линейных булевых функций
обозначим символом L.
Определение. Булева функция f ( x1,..., xn ) называется
f
(
x
,...,
x
)
f
(
x
,...,
x
)
самодвойственной, если
.
1
n
1
n
Множество всех самодвойственных булевых функций
обозначим символом S.
Определение. Булева функция f ( x1,..., xn ) называется
монотонной, если для любых x1 ,..., xn , y1 ,..., yn 0,1 из
x1 y1 ,..., xn yn следует f ( x1 ,..., xn ) f ( y1 ,..., yn ) .
Множество всех монотонных
обозначим символом M.
булевых
функций

34.

Определение. Булева функция f называется линейной,
если ее представление полиномом Жегалкина не
содержит произведения переменных.
Множество всех линейных булевых функций
обозначим символом L.
Определение. Булева функция f ( x1,..., xn ) называется
f
(
x
,...,
x
)
f
(
x
,...,
x
)
самодвойственной, если
.
1
n
1
n
Множество всех самодвойственных булевых функций
обозначим символом S.
Определение. Булева функция f ( x1,..., xn ) называется
монотонной, если для любых x1 ,..., xn , y1 ,..., yn 0,1 из
x1 y1 ,..., xn yn следует f ( x1 ,..., xn ) f ( y1 ,..., yn ) .
Множество всех монотонных
обозначим символом M.
булевых
функций

35.

Пусть P0 - класс всех булевых функций f ( x1,..., xn ) ,
удовлетворяющих условию f (0,...,0) 0 .
Пусть P1 - класс всех булевых функций f ( x1,..., xn ) ,
удовлетворяющих условию f (1,...,1) 1.
Определение. Классы булевых функций L,S,M,P0,P1
называются классами Поста.
Лемма. Классы Поста L,S,M,P0,P1
замкнутыми системами булевых функций.
являются
Теорема Поста. Система булевых функций в том и
только том случае является полной, если она не
содержится ни в одном из классов Поста.

36.

Алгоритм
доказательства
булевых функций
полноты
системы
:
1. Составить таблицу, столбцы которой
помечены классами Поста L,S,M,P0,P1 и строки –
функциями системы f1 ,..., f n .
2. Для каждой из функций f1 ,..., f n проверить
принадлежность ее к классам Поста и результаты
проверки зафиксировать словами «Да» или «Нет»
в соответствующей клетке таблицы.
3. По теореме Поста данная система является
полной в том и только том случае, если в каждом
столбце таблицы имеется слово «Нет».

37.

Пример.
Рассмотрим систему F | , состоящую из одной
булевой функции | – штрих Шеффера. Составляем
таблицу, столбцы которой помечены классами
Поста L,S,M,P0,P1 и одна строка – функцией |.
Функция
|
Классы Поста
L
S
M
P0
P1
Нет
Нет
Нет
Нет
Нет