Математическая логика и теория алгоритмов

1. Математическая логика и теория алгоритмов

Доцент каф. АОИ, к.т.н. Перемитина Татьяна Олеговна
Математическая логика
и теория алгоритмов
Булевы функции

2. Булевы функции

Введение в булеву алгебру.
Способы задания булевых
функций.
Минимизация булевых функций.
Представление булевых функций
полиномами Жегалкина.
2

3. Булева алгебра

х {0,1} f ( х) : {0,1} {0,1}
Способы задания булевых
функций:
• Табличный;
• Графический;
• Аналитический.
Вопрос: Сколько существует различных
булевых функций от одной переменной?
3

4.

Табличное задание
булевых функций
Count f ( x1 ,..., xn ) 2
2
f ( х), n 1, Count f ( x) 2 4
f 2 ( x) f 3 ( x )
f1 ( x)
f 0 ( x)
2n
1
Вопрос: Сколько существует различных
булевых функций от двух переменных?
4

5.

Табличное задание
булевых функций
f : {0,1} {0,1} {0,1}
f0
f1
f2
– «тождественный нуль»;
– конъюнкция;
– отрицание импликации;
5

6.

Табличное задание
булевых функций
f3
f4
f5
– тождественная функция;
– отрицание обратной импликации;
– тождественная функция;
6

7.

Табличное задание
булевых функций
f6
f7
f8
– сумма по модулю 2 (сумма Жегалкина);
– дизъюнкция;
– стрелка Пирса;
7

8.

Табличное задание
булевых функций
f9
f10
f11
– эквивалентность;
– отрицание y;
– обратная импликация;
8

9.

Табличное задание
булевых функций
f12
f13
f14
f15
– отрицание x;
– импликация;
– штрих Шеффера;
– «тождественная единица».
9

10. Графический способ представления булевых функций

10

11. Пример 1

Укажите булеву функцию,
графическое представление
которой имеет следующий вид:
Из графического представление определяем, что
f (0) 1; f (1) 0.
Ответ: графически представлена f ( x) х
11

12. Задача 1

Укажите булеву функцию,
графическое представление
которой имеет следующий вид:
A.
f ( x) x;
B. f ( x) x;
C.
f ( x) 0.
12

13. Пример 2

Укажите булеву функцию,
графическое представление
которой имеет следующий вид:
Из графического представления
определяем, что
f (0,0) 0; f (0,1) 0;
f (1,0) 1; f (1,1) 1 .
Ответ:
Графически представлена
f ( x, y) x.
13

14. Задача 2

Укажите булеву функцию,
графическое представление
которой имеет следующий вид:
A. f ( x, y) x y;
B. f ( x, y) x y;
C. f ( x, y) y х.
14

15.

Существенные и
фиктивные переменные
Булева функция f(x1, … xi,….,xn)
существенно зависит от переменной xi ,
если существует такой набор значений
переменных , что:
f(x1, … 0,….,xn)≠ f(x1, … 1,….,xn) .
Пример 3:
Какая переменная является существенной?
f ( x, y ) x ( x y )
15

16.

Решение
f ( x, y ) x ( x y )
f (0, y ) 0 (0 y ) 0;
f (1, y ) 1 (1 y ) 1; f (0, y ) f (1, y )
x существенная переменная.
f ( x,0) x ( x 0) x;
f ( x,1) x ( x 1) x; f ( x,0) f ( x,1)
y фиктивная переменная.
16

17. Задача 3

Для какой функции переменная х является
существенной?
A. f ( x, y) x y;
B. f ( x, y) x х у;
C. f ( x, y) ( x y) ( х у).
17

18. Решение

A. f ( x, y) x y х у
11
f (0, y) 1 у 1; f (1, y) 0 у у;
х существенн ая переменная
B. f ( x, y) x х у 1 все переменные
фиктивные.
C. f ( x, y) ( x y) ( х у) у значит
10
переменная х фиктивная.
18

19. Карты Карно

y 0
x
0
0
1
1
y
0
1
0
1
x
f ( x, y)
f(0,0)
f(0,1)
f(1,0)
f(1,1)
f ( x, y) 0011
x
0
ДНФf ( x, y) х.
1
0
f(0,0)
f(0,1)
1
f(1,0)
f(1,1)
y 0
1
0
0
x
1
1
1
19

20. Пример 4

f ( x, y) 1011
Для данной булевой функции определить
минимальную ДНФ.
¬у
y 0
1
0
1
0
1
1
1
x
x
x
0
0
1
1
y
0
1
0
1
f ( x, y)
1
0
1
1
ДНФf ( x, y) х у.
20

21. Задача 4

f ( x, y) 1100
Для данной булевой функции определить
минимальную ДНФ:
A.
f ( x, y) х у;
B.
f ( x, y) х;
C.
f ( x, y) у.
21

22. Решение

f ( x, y) 1100
x
0
0
1
1
y
0
1
0
1
f ( x, y)
1
1
0
0
¬х
y 0
1
0
1
1
1
0
0
x
ДНФf ( x, y) х.
Ответ: Правильный ответ В.
22

23. Карты Карно

x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f ( x,y,z)
f ( 0,0,0)
f ( 0,0,1)
f ( 0,1,0)
f ( 0,1,1)
f ( 1,0,0)
f ( 1,0,1)
f ( 1,1,0)
f ( 1,1,1)
yz 00
01
11
10
x
0
1
f(0,0,0) f(0,0,1) f(0,1,1) f(0,1,0)
f(1,0,0) f(1,0,1) f(1,1,1) f(1,1,0)
23

24. Пример 5

f ( x, y, z) 11110000
Для данной булевой функции определить
минимальную ДНФ.
yz 00
01
11
10
x
0
1
1
1
1
1
0
0
0
0
ДНФf ( x, y, z) х.
¬x
24

25. Карты Карно

zw 00
01
11
10
f(0,0,0,0)
f(0,0,0,1)
f(0,0,1,1)
f(0,0,1,0)
01
f(0,1,0,0)
f(0,1,0,1)
f(0,1,1,1)
f(0,1,1,0)
11
f(1,1,0,0)
f(1,1,0,1)
f(1,1,1,1)
f(1,1,1,0)
10
f(1,0,0,0)
f(1,0,0,1)
f(1,0,1,1)
f(1,0,1,0)
xy
00
25

26.

Пример 6
yz
wy
yz
wx
00
01
11
10
00
1
0
1
1
01
1
0
1
1
11
1
1
0
0
10
1
0
0
0
wx y
f ( x, y, z , w) w y y z w x y.
26

27. Алгебра Жегалкина

Закон коммутативности:
x y y x
Закон дистрибутивности:
x y z xy xz
1
Законы ассоциативности:
x y z x y z
x y z x y z
x x 0; х 0 х; х 1 х.
27

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

f x1 ,..., xn a0 a1 x1...an xn
a12 x1 x2 ... an 1,n xn 1 xn
a123 x1 x2 x3 ... a1... n x1 x2 ...xn ,
где a0 ,..., a1... n 0,1
28

29. Пример 7

f ( x, y) х у
Представьте данную булеву функцию в
виде полинома Жегалкина
f ( x, y) ( х y) (( x 1) ( y 1) 1)
(( х y x y 1) 1)
( х y x y) 1 1
х y x y.
Ответ: f ( x, y) х y x y.
29

30. Спасибо за внимание!

30