- •Введение
- •Предисловие
- •1. Теория множеств
- •1.1. Понятие множества
- •1.2. Операции над множествами
- •1.3. Основные тождества алгебры множеств
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Бинарные отношения. Свойства отношений
- •1.6. Соответствия. Отображения. Функции
- •Вопросы для самопроверки
- •2. Элементы комбинаторики
- •Вопросы для самопроверки
- •3. Логические операции
- •3.1. Основные понятия
- •3.2. Простейшие связки (операции)
- •3.3. Другие связки (операции)
- •3.4. Основные законы, определяющие свойства введенных логических операций.
- •4. Булевы функции
- •4.1. Основные понятия
- •4.2. Свойства элементарных булевых функций
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
- •4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •Задачи по теме «Булевы функции.»
- •Вопросы для самопроверки
- •5. Теория графов
- •5.1. Ориентированные графы
- •5.2. Неориентированные графы
- •5.3. Матричное задание ориентированных графов
- •5.4. Матричное задание неориентированных графов
- •5.5. Изоморфизм графов
- •5.6. Операции над графами
- •5.7. Пути, контуры, маршруты, цепи, циклы
- •5.8. Расстояние в графах
- •5.9. Связность в неориентированных графах
- •5.10. Связность в ориентированных графах
- •5.11. Эйлеровы графы
- •5.12. Гамильтоновы графы
- •5.13. Деревья
- •5.14. Остовные деревья
- •5.15 Взвешенные графы. Экстремальные остовы графов
- •5.16 Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры
- •5.17 Раскраска графов. Раскраска вершин графа
- •Вопросы для самопроверки
- •Библиографический список
- •Оглавление
- •Подписано к изданию «8» октября 2014.
- •394026 Воронеж, Московский просп., 14
4.2. Свойства элементарных булевых функций
Для булевых функций справедливы равенства, аналогичные формулам, сформулированным для высказываний.
1. Функции: конъюнкция, дизъюнкция, сумма по модулю два, стрелка Пирса, штрих Шеффера обладают свойством коммутативности.
2. Функции: конъюнкция, дизъюнкция, сумма по модулю два обладают свойством ассоциативности и свойством дистрибутивности.
3. Закон де Моргана: , .
4. Закон двойного отрицания: = х.
5. Выражение дизъюнкции через конъюнкцию и суммы по модулю два: .
6. Выражение дизъюнкции через импликацию:
.
7. Выражение отрицания через штрих Шеффера, стрелку Пирса, сумму по модулю два и эквивалентность: .
8. Выражение конъюнкции через штрих Шеффера:
9. Выражение дизъюнкции через стрелку Пирса: .
10. Закон поглощения: , .
11. Закон склеивания: .
12. Для функций: конъюнкция, дизъюнкция и сумма по модулю два справедливы следующие тождества:
,
, .
13. Для функций конъюнкция и дизъюнкция справедливы тождества: .
Для доказательства справедливости любых из приведенных тождеств нужно составить таблицы истинности для булевых функций.
Булеву функцию любого числа переменных можно задать формулой, содержащей функции одной и двух переменных посредством подстановки одних булевых функций вместо переменных в другие булевы функции, т. е. посредством суперпозиции булевых функций.
4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
Конъюнктивным одночленом от переменных называется конъюнкция этих переменных или их отрицаний. Элементарной конъюнкцией называется конъюнктивный одночлен, в который переменные, в том числе и их отрицания, входят по одному разу. Например, — конъюнктивный одночлен, а , — элементарные конъюнкции.
Дизъюнктивным одночленом от переменных называется дизъюнкция этих переменных или их отрицаний. Элементарной дизъюнкцией называется дизъюнктивный одночлен, в который переменные, в том числе и их отрицания, входят по одному разу. Например, , — элементарные дизъюнкции.
Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных конъюнктивных одночленов, называется дизъюнктивной нормальной формой (ДНФ) данной формулы.
Например: — ДНФ.
Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных дизъюнктивных одночленов, называется конъюнктивной нормальной формой (КНФ) данной формулы.
Например: — КНФ.
Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Для этого нужно:
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
.
2 ) Заменить знак отрицания, относящийся к выражениям типа или , знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
.
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример 4.1. Приведем формулу к ДНФ.
Решение.
Применим отрицание к переменным и сократим двойные отрицания:
.
Используем закон дистрибутивности, приведем формулу ДФН:
.