Презентации лекций / Презентация лекции 3 ДМ 20
.pdf
План лекции
1. Понятие булевой функции
2. Элементарные булевы функции
3. Задание булевых функций формулами
11
1
2
3
Булевыфункцииот однойпеременной
|
тождественный |
|
тождественная |
|
отрицание |
|
тождественная |
|
ноль |
|
функция |
|
|
единица |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|||||
0 |
0 |
|
0 |
|
1 |
|
1 |
1 |
0 |
|
1 |
|
0 |
|
1 |
|
|
|
|
|
|
|
|
Другое обозначениедляотрицания: |
¬ |
|
|
12
Элементарные булевыфункцииот двухпеременных
|
|
|
|
|
эквивалент- |
сложение |
штрих |
стрелка |
|
|
|
|
|
помодулю |
|||
|
|
конъюнкция |
дизъюнкция |
импликация |
Шеффера |
|||
|
|
|
|
|
ность |
два |
|
Пирса |
|
|
|
|
|
|
|
|
|
|
|
|
|
→ |
↔ |
|
| |
↓ |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
Другие обозначения:дляконъюнкции |
|
и дляэквивалентности |
, |
& , |
|||
|
|
|
|
, , →, ↔ ~ , , |, ↓ - логические связки
1
2
3
13
План лекции
1. Понятие булевой функции
2. Элементарные булевы функции
3. Задание булевых функций формулами
14
множество функций |
алфавит переменных |
Формула над множествомфункций 
– 
?
Определение формулы индуктивное, что непривычно.
Поэтому начнем с простого: опишем как можно действовать, чтобы записать формулу.
1 шаг. Пишем какую-нибудь функцию из . Например, |
|
, |
, … (такая запись – уже |
одна из формул). |
|
|
|
|
|
|
|
2 шаг. Вместо любой переменной написанной функции можем записать любую букву из (имя переменной) или любую функцию из . Например, ,( , ,… , ,…) (такая запись – одна ихформул).
3 шаг. Вместо любой переменной в формуле, получившейся на 2-м шаге, можем записать любую букву из (имя переменной) или любую функцию из . Например, ,( ( , ,…), ,… , ,…) (получили очередную формулу)
и так далее … (любое конечное число раз)
1
2
3
15
Определение формулынад 
:
Базисиндукции: |
переменнаяиз |
формулаглубины0 |
|
|
|||
|
|
константа0/1 |
формулаглубины0 |
|
(еслиестьв) |
||
|
Множествоподформулформулы глубины 0 состоиттолькоиз нее самой.
Индуктивный переход:
, |
, |
|
… из, |
|
|
|
|
|
Ф = , , ,… - |
||
, , ,… формулы |
|||||
формулаглубины + |
|||||
наибольшейглубины |
|||||
|
|||||
|
|
|
|
|
|
Множествоподформул формулы Ф включаетее самуи всеподформулы формул , , ,….
1
2
3
16
1
Определение функции, заданной формулой: 2
3
Базисиндукции: |
|
тождественная |
|
переменная |
|
|
функция |
|
|
|
Формулаглубины0 |
|
|
тождественный0 |
||
константа0 |
||
константа1 |
тождественная1 |
|
|
|
Индуктивныйпереход:
Формулаглубины + |
|
|
|
Ф = , ,… |
|
|
, ,… |
|
|||||||||
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
такая, чтоеезначениенанаборе |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( , ,…)находитсякакзначение |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
функции нанаборе |
|||
|
|
|
|
|
|
какформулам глубины |
|
|
( , ,… |
, |
, |
,… , …),т.е. |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, ,… |
= |
|
|
|
|
|
, ,… |
|
|
|
|
, ,… |
|
|
… |
|
= ( , ,… |
, , ,… , …). |
||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17
Пример
Найти вектор значений функции, заданной формулой:
2)
1
2
3
18
1
2
3
Пример:
, , = |
|
|
→ |
|
→ |
= Ф[ ,→,¬, ] |
Пример:
, |
, = |
|
|
→ → |
|
|
|
|
− суперпозицияфункций { ,→,¬, ] |
19
Символконъюнкцииможноопускать:
|
|
Внешниескобкиможноопускать:
(( )) |
( ) |
1
2
3
Можноопускатьчастьскобок,используя иерархиюсвязок:
¬
→,↔
Функции, обозначенныестаршимисвязками, можновскобкине брать:
тогда,еслискобкинепредписываютиное, действиявыполняютсявпорядке«старшинства»
20