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