Логические функции. Лекция 3

1. Лекция 3 Тема: Логические функции

Учебные вопросы:
1. Виды логических функций
2. Канонические формы логических
формул
3. Суперпозиция функций
4. Замкнутые классы логических функций
1

2. 1. Виды логических функций

Логической функцией называют функцию
f(x1,x2, … xn ) аргументы которой x1,x2, … xn и сама
функция принимают значения 0 или 1.
Для n = 0 – (нульарные функции) существует 2
различные
логические
функции,
значения:
константы 0 и 1;
n = 1 (унарные функции) существует 4 различных
логических функций, значения: g1(x)=Л; g2(x)=¬x,
g3(x)=x, g4(x)=И,
2

3.

n = 2 (бинарные функции) существует 16
различных логических функций от 2 переменных;
x
y
f0
f1
f2
f3
f4
f5
f6
f7
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
f0(x,y)=0=g1(0)
f4(x,y)= (y x)
f1(x,y)=x & y
f5(x,y)=y=g3(y)
f2(x,y)= (x y)
f6(x,y)=x y
f3(x,y)= x=g3(x)
f7(x,y)=x y
3

4. Логические функции от двух переменных

x
y
f8
f9
f10
f11
f12
f13
f14
f15
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
f8(x,y)= (x y)
f12(x,y)= x=g2(x)
f9(x,y)= x ~ y
f13(x,y)= x y
f10(x,y)= y=g2(y)
f14(x,y)= (x & y)
f11(x,y)= y x
f15(x,y)= 1=g4(1)
где (x y) = x y
где (x & y) = x | y
-стрелка Пирса,
Функция Вебба,
функция Даггера
- штрих Шеффера
4

5.

Формы представления логических функций
Логические функции
Аналитическое представление
(формула)
Табличное представление
Графическое представление
5

6.

2. Канонические формы
логических формул
Виды форм логических функций
Нормальная форма, если булева функция
выражена через дизъюнкцию, конъюнкцию и
отрицание переменных
Совершенная форма, если функция
записывается единственным образом
6

7.

Формы логических функций
Совершенная дизъюнктивная нормальная форма
(СДНФ)
Совершенная конъюнктивная нормальная форма
(СКНФ)
Совершенная полиномиальная нормальная форма
(СПНФ)
7

8. Теоремы о формах логических функций

Теорема1. Пусть f(x1 ,x2 , … xn ) – булева функция от n
переменных, не равная тождественно 0. Тогда существует СДНФ,
причем единственная, выражающая функцию f.
f(x1,x2,…,xn)= f(1,1,…,1,1) x1x2…xn-1xn +
+ f(1,1,…1,0) x1x2…xn-1 xn +…
+ f(0,1,…1,1) x1x2…xn-1xn +
+ f(1,1,…0,0)x1x2… xn-1 xn +…
+ f(0,0,…1,1) x1 x2…xn-1xn +…
+ f(0,0,…0,0) x1 x2 … xn-1 xn
Булева функция двух переменных
f(x1,x2)= f(1,1) x1x2 + f(1,0) x1 x2 + f(0,1) x1x2 +
+ f(0,0) x1 x2
8

9.

Теорема2. Пусть f(x1 ,x2 , … xn ) – булева функция от n
переменных, не равная тождественно 1. Тогда существует СКНФ,
причем единственная, выражающая функцию f.
f(x1,x2,…,xn)= (f(1,1,…,1,1) + x1+ x2+…+ xn-1+ xn )
(f(1,1,…1,0)+ x1+ x2+ …+ xn-1+xn ) …
(f(1,1,…0,0)) + x1+ x2+ …+ xn-1+xn) …
(f(0,0,…1,1) +x1+x2+ …+ xn-1+ xn ) …
(f(0,0,…0,0) +x1+x2+ …+ xn-1+xn )
СКНФ булевой функции двух переменных
f(x1,x2)= (f(1,1)+ x1+ х2 ) ( f(1,0) + x1+ x2)
( f(0,1)+x1+ x2 ) (f(0,0) + x1+x2)
9

10.

Следствие. Если логическая функция представляет собой
константу Л (на всех наборах 0), то для нее не существует
СДНФ.
Аналогично, если логическая функция представляет
собой константу И (на всех наборах 1), то для нее не
существует СКНФ.
Формулу называют элементарной конъюнкцией,
если она является конъюнкцией одной или нескольких
переменных, взятых по одному разу с отрицанием или без
отрицания.
Примеры:
x1; ¬x2;
x1& x2;
x1 & x2 & ¬x3
10

11.

Совершенная дизъюнктивная нормальная форма
Алгоритм построения СДНФ
1. постройте таблицу истинности логической функции;
2. отметьте наборы переменных, на которых логическая
функция истинна;
3. выпишите отмеченные наборы переменных, соединяя
между собой операцией конъюнкции, а между наборами –
дизъюнкцией. Причем, если переменная имеет ложное
значение, то она берется с отрицанием, а если истинное
значение, то без отрицания;
4. упростите полученную формулу.
11

12. Пример 1. Постройте СДНФ для функции f(x1,x2, x3), заданной таблицей.

x1
x2
x3
f(x1,x2, x3)
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
СДНФ:
f(x1,x2,x3)= x1x2 x3 + x1 x2 x3 + x1 x2x3 =
= x1x2 x3 + x1 x2( x3 + x3) =
= x1x2 x3 +
x1 x2
12

13.

Совершенная конъюнктивная нормальная форма
Формулу называют элементарной дизъюнкцией, если она
является дизъюнкцией одной или нескольких переменных, взятых
по одному разу с отрицанием или без отрицания.
Примеры:x1,¬x2, x1 x2, x1 ¬x2 x3
Алгоритм построения СКНФ
1. постройте таблицу истинности логической функции;
2. отметьте наборы переменных, на которых логическая функция
ложна;
3. выпишите отмеченные наборы переменных, соединяя между
собой операцией дизъюнкции, а между наборами – конъюнкцией.
Причем, если переменная имеет ложное значение, то она берется
без отрицания, а если истинное значение, то с отрицанием;
4. упростите полученную формулу.
13

14. Пример 2. Постройте СКНФ для функции f(x1,x2, x3), заданной таблицей.

x1
x2
f(x1,x2)= x1 x2
0
0
1
1
0
1
0
1
1
1
0
1
СКНФ:
f(x1,x2)= x1 x2
14

15.

Совершенная полиномиальная нормальная форма
(полином Жегалкина)
Алгоритм построения СПНФ
1. Построить СДНФ логической функции.
2. Все переменные с отрицанием заменить:
A = 1 A
3. В скобочной форме выполнить раскрытие скобок:
(A B)&C = A&C B&C
4. Использовать тождество:
А V В = A B A&B
5. Из полученного выражения удалить попарно A A = 0
15

16.

Полученная СПНФ является полиномом Жегалкина
Полином Жегалкина — полином (многочлен), то есть
полином с коэффициентами вида 0 и 1, где в качестве
произведения берется конъюнкция, а в качестве сложения
строгая дизъюнкция.
Алгеброй
Жегалкина
называется
алгебра
над
множеством логических функций и переменных, которые
содержат две бинарные операции & и и две нульарные
операции – константы 0 и 1.
16

17.

В алгебре Жегалкина выполняются следующие соотношения:
1. x y = y x;
2. x( y z ) = xy xz;
3. x x = 0;
4. x x = 1;
5. x 0 = x.
Полином Жегалкина - еще один способ выразить любую
булеву функцию через бинарные операции.
Теорема: Любая булева функция n переменных может
быть представлена единственным полиномом Жегалкина.
17

18. Пример 3. Постройте СПНФ для функции f(x1,x2, x3), заданной таблицей.

x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f(x1,x2, x3)
0
1
0
1
0
0
0
0
СДНФ: f(x1,x2,x3) = x1 x2 x3 + x1x2x3=
= x1x3( x2 + x2) = x1x3
СПНФ: f(x1,x2,x3) = (1 x1)x3 = x3 x1x3
18

19. 3. Суперпозиция функций

Результат вычисления булевой функции может быть
использован в качестве одного из аргументов другой функции.
Результат такой операции можно рассматривать как новую
булеву функцию со своей таблицей истинности.
Составление сложных функций из элементарных функций
системы называется суперпозицией.
Пример 4. Постройте суперпозицию для функции:
F(A,B)=A B Л
Решение:
f13(f6(g3(а),g3(в)),g1(0))
19

20. Применение суперпозиции функций

Пример 5. Постройте суперпозицию для функции:
F(A,B)= B (A B)
Решение:
f9(g2(в),f8(g3(а),g3(в)))
Применение суперпозиции функций
Любую булеву функцию с любым количеством
аргументов можно построить через суперпозицию
элементарных логических функций.
Поэтому для представления любой функции алгебры
логики достаточно ограниченного числа функций,
составляющих функционально полную систему - базис.
20

21.

В электронике это означает, что для реализации всего
многообразия
схем
преобразования
сигналов,
представляющих
логические
значения,
достаточно
нескольких типовых элементов.
С другой стороны, использование функций, не входящих
в некоторый базис, позволяет существенно сократить
сложность реализующих выражения схем и тем самым
повысить их надёжность.
Помимо отрицания в базис булевой алгебры входят и
конъюнкция, и дизъюнкция, хотя достаточно только одной
из них.
21

22. 4. Замкнутые классы функций

Множество функций замкнуто относительно
операции суперпозиции, если любая суперпозиция
функций из данного множества тоже входит в это же
множество.
Эмиль Пост сформулировал необходимое и
достаточное условие полноты системы булевых функций.
Для этого он ввел в рассмотрение замкнутые классы
булевых функций:
-класс К0 функции, сохраняющие нуль (функция от нуля
даёт ноль, т.е. f(0,0,…0)=0);
22

23.

-класс К1 функции, сохраняющие единицу (функция от единицы
даёт единицу, т.е. f(1,1,…,1)=1);
-класс L линейные функции (функция представима
многочленом, в котором каждый член состоит из переменных
первой степени);
-класс М монотонные функции (функция монотонно не убывает
по каждому из своих аргументов);
- класс S самодвойственные функции. На противоположных
наборах эти функции принимают противоположные значения,
т.е.
f(x1, x2)= f( x1, x2).
23

24.

Теорема. Класс К0 функций, сохраняющие нуль (функция
от нуля даёт ноль, т.е. f(0,0,…0)=0) замкнут относительно
операции суперпозиции функций.
Теорема. Класс К1 функций, сохраняющие 1(функция от
1даёт ноль, т.е. f(1,1,…1)=1) замкнут относительно операции
суперпозиции функций.
24

25. Полные системы булевых функций

Система булевых функций {f1, f2, …, fm} называется
полной, если любая булева функция может быть выражена
через функции этой системы с помощью составления из них
сложных функций (суперпозиции).
Достаточные условия полноты системы
1. Критерий Поста-Яблонского
Набор булевых функций тогда и только тогда является полным,
когда он не содержится ни в одном из пяти классов: класс М,
класс К0, класс К1, класс L, класс S.
2. Теорема о полноте
Если даны две системы логических функций F1 и F2 и F1
полна, то система F2 полна тогда, когда каждая функция
системы F1 представима через функции F2.
25

26.

Пример 6. Для функции f(x, y, z) = (0010 1000) выясните вопрос
об ее принадлежности к классам Поста.
Решение: выпишем развернутую таблицу
функций f:
xyz
000
001
010
011
100
101
110
111
f
0
0
1
0
1
0
0
0
1.Так как в полиноме Жегалкина для функции f
присутствуют конъюнкции, то f L.
2.f(0, 0, 0)=0 f K0. Следовательно, {f} – не
является функционально полной.
3.f(1, 1, 1)=0 f K1;
4.(0, 1, 0) < (0, 1, 1), но f(0, 1, 0) > f(0, 1, 1)
f M;
5.(0, 0, 0) и (1, 1, 1) – противоположные наборы,
f(0, 0, 0) = f(1, 1, 1) f S;
6.f(x, y, z) = (x 1)y (z 1) x(y 1)(z 1)=
=xyz xy yz y xyz xy xz x =
=xz yz x y.
26

27.

Пример 7. Выясните, можно ли из функции
f(x, y, z) = (1001 0100)
с помощью суперпозиций получить функцию
g(x, y, z) = (1001 0110)?
Решение:
проверим f(x, y, z) на принадлежность к классам Поста.
1.f(0, 0, 0)=1 f T0; f(1, 1, 1)=0 f T1;
2.(0, 0, 0) < (0, 0, 1), но f(0, 0, 0) > f(0, 0, 1) f M;
3.(0, 0, 1) и (1, 1, 0) – противоположные наборы,
f(0, 0, 1) = f(1, 1, 0) f S;
27

28.

4.f(x, y, z) = (x 1)(y 1)(z 1) (x 1)yz x (y 1)z =
= 1 x y z xy xz yz xyz xyz yz xyz xz =
= 1 x y z xy xyz
Т.к. в полиноме Жегалкина для функции f присутствуют
конъюнкции, то f L.
Итак, функция f(x, y, z) не принадлежит ни одному из
классов Поста, значит система {f} функционально полна и с
помощью суперпозиции из f можно получить любую логическую
функцию, в частности:
g(x, y, z) = (1001 0110).
28