- •Часть 1
- •Содержание
- •Введение
- •1. Введение в теорию множеств
- •Операции над множествами
- •Диаграммы Эйлера – Венна
- •Понятие алгебры
- •Упражнения
- •2. Отношения
- •Операции над отношениями
- •Свойства бинарных отношений
- •Задачи и упражнения
- •3. Нечеткие множества
- •Операции над нечеткими множествами.
- •Задачи и упражнения
- •Элементарные функции k-значных логик и соотношение между ними
- •Разложение функций k-значных логик в первую и вторую формы
- •Замкнутые классы и полнота в k-значных логиках
- •Задачи и упражнения
- •5. Логика высказываний
- •Тождества в алгебре высказываний
- •Булевы формулы
- •Интерпретации
- •6. Булевы функции
- •Способы задания булевой функции
- •Равносильные преобразования формул
- •Нормальные формулы Совершенные нормальные формулы
- •Разложение Шеннона Декомпозиция булевых функций
- •Представление булевой функции картами Карно (Вейча)
- •Минимизация булевых функций
- •Классы булевых функций
- •7. Комбинаторика Введение
- •8. Кодирование
- •Алфавитное кодирование
- •Кодирование с минимальной избыточностью
- •Помехоустойчивое кодирование
- •Сжатие данных
- •Шифрование
- •Криптография
- •Цифровая подпись
- •9. Графы Определение графа
- •Задание графов
- •Связность графа
- •Эйлеровы и гамильтоновы графы
- •Деревья
- •Понятие метрики графа
- •Цикломатическое число, раскраска
- •Изоморфизм графов
- •Орграфы
- •Сети Петри
- •Контрольная работа №1 (варианты заданий)
- •Контрольная работа № 2.
- •Контрольная работа №3
- •Список литературы
Равносильные преобразования формул
Две формулы, представляющие одну и ту же функцию, называются равносильными. Преобразования, приводящие некоторую формулу к равносильной ей формуле, называются равносильными. Булева формула может быть представлена большим количеством равносильных формул. Некоторые представляют интерес. Например, формулы, содержащие наименьшее число букв, или формулы, содержащие только некоторые символы операций из множества элементарных операций.
Теория булевых функций занимается изучением специальных функций и равносильных преобразований, приводящих к этим функциям.
Основные свойства элементарных формул (основные равносильности):
закон идемпотентности:
а а = а, а а = а;
закон коммутативности:
a b = b a, a b = b a;
закон ассоциативности:
a (b c) = (a b) c ,
a (b c) = (a b) c;
закон дистрибутивности:
a (b c) = a b a c,
a (b c) = (a b) (a c);
закон двойного отрицания:
= а;
закон де Моргана:
законы склеивания:
a b a = а , (a b) (a ) = а;
законы поглощения:
a a b = а, a (а b) = а;
законы Порецкого:
a b = а b, a ( b) = а b;
законы, определяющие действия с константами 0 или 1:
a = а, a 0 = 0, a 1 = 1,
a 1 = а, a = 1, a = 0.
Правило подстановки: если в равносильных формулах вместо всех вхождений некоторой переменной х подставить одну и ту же формулу, то получатся равносильные формулы.
Правило замены: если в формуле заменить некоторую подформулу на равносильную, то получится равносильная формула.
Нормальные формулы Совершенные нормальные формулы
Обозначим хо = , х1 = х,
Любую конъюнкцию ранга n можно представить в виде:
Элементарной конъюнкцией называется конъюнкция переменных, некоторые из которых могут быть взяты со знаком отрицания, причем переменная в конъюнкции не должна встречаться более одного раза.
Или: элементарной конъюнкцией называется выражение вида ,
То есть элементарная конъюнкция есть логическое произведение переменных взятых в некоторой степени δ, в которой ни одна переменная не употребляется два раза.
Число переменных в конъюнкции или дизъюнкции назовем ее рангом.
Дизъюнкция различных элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).
Конъюнкция различных элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).
Число конъюнкций в ДНФ называется длиной ДНФ.
Если мы возьмем любую формулу из символов a, b, c,…, x, y, z, , , ¬, →, ~, , ( , ), то можно ее заменить равносильной ДНФ.
a→ b = b, a ~ b = a b, a b = a b.
Пример (а ) → (с d) = с d = b c d;
ДНФ весьма просто получается из таблицы истинности. Достаточно поставить в соответствие каждому значению вектор аргумента, на котором функция принимает значение 1, элементарную конъюнкцию, называемую полной и состоящую из всех аргументов. Такая ДНФ, членами которой являются неповторяющиеся полные элементарные конъюнкции, называется совершенной ДНФ (СДНФ), а ее члены констатуэнтами единицы. С ДНФ любой булевой функции единственна с точностью до порядка следования членов и литералов (чего нельзя сказать о ДНФ) и является, как говорят, канонической формой.
Пример. Пусть задана функция (a b) → (c ~ a).
Построим таблицу истинности.
-
a b c
a b
c ~ a
(a b) → (c ~ a)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
0 1 0
1 1 1
0
0
1
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
Построим СДНФ.
КНФ так же удобна для представления нулей булевой функции, как ДНФ для представления единиц.
СКНФ для предыдущего примера запишется
Каждая из составляющих ее полных элементарных дизъюнкций является конституэнтой нуля и определяет значение вектор аргумента, на котором функция обращается в нуль.