Аналитическая запись булевых функций.
Рассмотрим фиксированный набор элементов
, 
.
, 
.
Рассмотрим функцию 
Назовём 
характеристической функцией единицы.
Теорема 2.
– множество наборов аргументов, на которых f принимает значение 1.
4Пусть имеем фиксированный набор , для которого F = 1. Значит, что среди всех 
существует такая, чей индекс i совпадает с номером набора значений аргумента.
Пусть имеем фиксированный набор , для которого F = 0. Значит, что среди всех нет ни одной, чей индекс i совпадает с номером набора значений аргумента. 3
Определение 3.
Введём понятие степени аргумента 
Рассмотрим конъюнкцию 
.
Рассмотрим 4 случая:
Теорема 3.
Любая ФАЛ кроме константы 0 может быть представлена в виде
Такое представление функции называется СДНФ (совершенная дизъюнктивная нормальная форма).
Алгоритм получения СДНФ:
1. Выбираем те наборы, на которых f = 1.
2. Выписываем конъюнктивные наборы, причём 
3. Объединяем все конъюнкции дизъюнкциями.
Пример.
|
|
|
| |
0 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | ü |
0 | 1 | 0 | 1 | ü |
0 | 1 | 1 | 0 | |
1 | 0 | 0 | 0 | |
1 | 0 | 1 | 1 | ü |
1 | 1 | 0 | 0 | |
1 | 1 | 1 | 1 | ü |
Лекция № 2.
БУЛЕВЫ ФУНКЦИИ (ФАЛ).
Теорема 1.
Любая ФАЛ кроме константы 0 может быть представлена в виде
Такое представление функции называется СПНФ (совершенная полиномиальная нормальная форма).
Алгоритм получения СПНФ:
1. Выбираем те наборы, на которых f = 1.
2. Выписываем конъюнктивные наборы, причём
3. Объединяем все конъюнкции логической связкой 
.
Пример.
|
|
|
| |
0 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | ü |
0 | 1 | 0 | 1 | ü |
0 | 1 | 1 | 0 | |
1 | 0 | 0 | 0 | |
1 | 0 | 1 | 1 | ü |
1 | 1 | 0 | 0 | |
1 | 1 | 1 | 1 | ü |
Теорема 2.
Любая ФАЛ кроме константы 1 может быть представлена в виде
Такое представление функции называется СКНФ (совершенная конъюнктивная нормальная форма).
4Возьмём произвольную ФАЛ и представим её в СДНФ:
Применим операцию отрицания к равенству.
3
Алгоритм получения СКНФ:
1. Выбираем те наборы, на которых f = 0.
2. Выписываем дизъюнктивные наборы, причём 
3. Объединяем все наборы конъюнкцией.
Пример.
|
|
|
| |
0 | 0 | 0 | 0 | ü |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | ü |
1 | 0 | 0 | 0 | ü |
1 | 0 | 1 | 1 | |
1 | 1 | 0 | 0 | ü |
1 | 1 | 1 | 1 |
Характеристическая функция нуля.
|
|
|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Теорема 3.
Любая ФАЛ кроме константы 1 может быть представлена в виде
Такое представление функции называется САПНФ (совершенная анти полиномиальная нормальная форма).
Алгоритм получения САПНФ:
1. Выбираем те наборы, на которых f = 0.
2. Выписываем дизъюнктивные наборы, причём
3. Объединяем все наборы эквивалентностями.
Пример.
|
|
|
| |
0 | 0 | 0 | 0 | ü |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | ü |
1 | 0 | 0 | 0 | ü |
1 | 0 | 1 | 1 | |
1 | 1 | 0 | 0 | ü |
1 | 1 | 1 | 1 |
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
