Презентации лекций / Презентация лекции 3 ДМ 20
.pdf
Тема 3 «Булевы функции и способы
их задания»
«Дискретная математика» Олейник Татьяна Анатольевна
кафедра ВМ-1
План лекции
1. Понятие булевой функции
2. Элементарные булевы функции
3. Задание булевых функций формулами
2
План лекции
1. Понятие булевой функции
2. Элементарные булевы функции
3. Задание булевых функций формулами
3
1
2
3
область определения |
множество значений |
сопоставляет каждому элементу области определения |
|
конкретный (один!) элемент множества значений |
|||
|
|
Область |
Множество |
определения |
значений |
4
Обсудим область определения булевых функций |
1 |
|
2 |
|
3 |
Булеввектор = , ,… |
– |
|
упорядоченный набор |
|
, |
где равно0или1. |
|
|
|
Примеры: |
– координаты |
– длина вектора |
(0,1,0,0) – булев вектор длины 4 |
|
(1,1,1,1,1) – булев вектор длины 5 |
вектора |
|
|
|
|
Совокупностьбулевыхвекторовдлины
-
единичный -мерныйкуб
5
1
2
Единичный
-мерныйкуб
- 3
множествобулевыхвекторовдлины
Примеры: |
|
|
|
|
Множество булевых векторов длины 1: |
= { ,( )} |
|
|
|
Множество булевых векторов длины 2: |
= { , , , , , ,( ,)} |
|
||
Множество булевых векторов длины 3: |
= { ,, , |
,, , |
,, , |
,, , |
|
,, , |
,, , |
,, ,( ,,)} |
|
Чемуравна мощность 
?
6
1
2
3
Булевы вектора 
однойдлины нумеруют.
|
|
|
|
|
|
|
- |
номер 
|
|
|
0,0,0 |
= 0 |
|
|
|
|
0,0,1 |
= 1 |
|
|
0,0 |
= 0 |
0,1,0 |
= 2 |
|
Примеры: |
0,1 |
= 1 |
0,1,1 |
= 3 |
|
1,0 |
= 2 |
1,0,0 |
= 4 |
||
|
|||||
|
1,1 |
= 3 |
1,0,1 |
= 5 |
|
|
|
|
1,1,0 |
= 6 |
|
|
|
|
1,1,1 |
= 7 |
7
1
2
3
Булевафункцияот
переменных –
функция,определеннаяна
ипринимающаязначения0 или1.
8
Перечисляем
булевы
векторы
впорядке возрастания номеров
Пример:
1
Таблицаистинностифункции 2
3
|
|
… |
|
|
|
( , ,… ) |
0 |
0 |
… |
0 |
|
0 |
(0,0,…0,0) |
0 |
0 |
… |
0 |
|
1 |
(0,0,…0,1) |
0 |
0 |
… |
1 |
|
0 |
(0,0,…1,0) |
… |
… |
… |
… |
|
… |
… |
1 |
1 |
… |
1 |
|
1 |
(1,1,…1,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( , ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
0,0 |
= 1 |
|
|
|
0 |
0 |
|
1 |
|
|
|
|
|
, = (1,0,1,1) |
0,1 |
= 0 |
|
|
|
|
|
|
|
||||||
|
|
|
0 |
1 |
|
0 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|||||
1,0 |
= 1 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
1 |
0 |
|
1 |
|
|
|
- векторзначений |
||||
11 |
= 1 |
|
|
|
|
|
|
|
||||||
|
|
|
|
|||||||||||
|
|
|
|
|
1 |
1 |
|
1 |
|
|
|
|
|
функции |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9
Сколькоимеембулевыхфункций от
переменных?
1
2
3
|
|
|
… |
|
|
|
( , ,… ) |
|
|
|
|
|
|
0 |
0 |
… |
0 |
|
0 |
? |
0 |
2варианта |
|
|
|
строк |
0 |
0 |
… |
0 |
|
1 |
? |
1 |
2варианта |
|
|
|
|
0 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|||
|
|
|
|
|
|
|
|
|
|
множителей |
||
|
… |
… |
… |
… |
|
… |
… |
|
|
2 |
||
|
1 |
1 |
… |
1 |
|
1 |
? |
0 |
2варианта |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
10