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