МАТЕМАТИЧЕСКАЯ ЛОГИКА
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. Объединяем все наборы дизъюнкциями.
Пример.
![]() | ![]() | ![]() | ![]() | |
ü | ||||
ü | ||||
ü | ||||
ü |