- •Введение
- •Тема 1. Логика высказываний
- •1.1. Понятие высказывания
- •1.2. Логические операции
- •1. Отрицание или инверсия ( – не)
- •Конъюнкция ( ,, ·, логическое и )
- •4. Импликация ( ) “если а, то b”
- •6. Сумма по модулю два
- •7. Штрих Шеффера ( , обратная конъюнкция и – не)
- •8. Стрелка Пирса ( , обратная дизъюнкция или – не )
- •1.3. Булевы функции
- •1.3.1. Некоторые определения из теории множеств
- •1.3.2. Булевы функции
- •1.4. Формулы
- •1.5. Равносильные формулы
- •1.6. Подстановка и замена
- •1.7. Формы представления высказываний
- •1.8. Минимизация сложных высказываний методом Квайна
- •1.9. Полные системы функций
- •1.9.1. Система функций { }
- •1.9.2. Замкнутые классы
- •1.9.3. Функциональная полнота
- •Тема 2. Логические исчисления
- •2.1. Интерпретация формул
- •2.2. Примеры тождественно истинных формул высказываний
- •2.3. Формальные теории
- •Выводимость.
- •2.5. Интерпретация формальных теорий
- •2.6. Исчисление высказываний.
- •2.7. Производные правила вывода
- •2.8. Дедукция
- •2.9. Некоторые теоремы теории £
- •Тема 3. Логика и исчисление предикатов
- •3.1. Предикаты
- •3.2. Исчисление предикатов
- •3.3. Интерпретация
- •3.4. Основные равносильности для предикатов
- •3.5. Приведенная форма представления предикатов
- •Тема 4. Автоматическое доказательство теорем
- •4.1. Постановка задачи
- •4.2. Доказательство от противного
- •4.3.Правило резолюции для исчисления высказываний
- •4.4. Правило резолюции для исчисления предикатов
- •4.5. Основные положения мр (выводы)
- •4.6. Логическое программирование
- •Тема 5. Теория алгоритмов
- •5.1. Интуитивное понятие алгоритма
- •5.2. Конкретизация понятия алгоритма
- •5.2.1. Машины Тьюринга
- •5.2.3. Рекурсивные функции
- •5.2.3. Нормальные алгорифмы Маркова
- •5.3. Алгоритмически неразрешимые проблемы
- •5.3.1. Проблема самоприменимости
- •5.3.1.1. Нумерация мт
- •5.3.1.2. Самоприменимость мт
- •5.3.2. Проблема останова
- •5.3.3. Разрешимые и неразрешимые задачи математики
- •5.4. Характеристики сложности вычислений
- •5.5. Классы сложности задач
- •5.5.1. Р задачи
- •5.5.2. Np задачи
1.8. Минимизация сложных высказываний методом Квайна
Алгоритм:
Получить СДНФ.
Получить сокращенную ДНФ (СкДНФ), используя следующие равносильности:
- неполное склеивание;
- поглощение.
Построить импликантную матрицу, с помощью которой получить МДНФ.
Пример.
1. - ДНФ
- СДНФ
1 2 3 4 5 6
2. Применяя операции склеивания, получаем СкДНФ.
1-2: |
|
1-5: |
|
2-3: |
|
3-4: |
|
4-6: |
|
5-6: |
|
3. Импликантная матрица
|
|
|
|
|
|
|
|
+ |
+ |
|
|
|
|
|
+ |
|
|
|
+ |
|
|
|
+ |
+ |
|
|
|
|
|
|
+ |
+ |
|
|
|
|
|
|
+ |
|
+ |
|
|
|
|
|
+ |
+ |
Выбираем импликанты, которые поглощают все конституенты единицы.
1.9. Полные системы функций
1.9.1. Система функций { }
Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции .
Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2n строк. Каждую строку можно представить в виде конъюнкции переменных х1,…хn, куда входит либо , либо . Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций.
Пример.
x |
y |
f(x,y) |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
Получим СДНФ, используя таблицу истинности.
Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции?
1.9.2. Замкнутые классы
Пусть множество булевых функций от n переменных.
Замыканием F ([F]) называется множество всех булевых функций, реализуемых формулами над F.
Множество функций (класс) называется замкнутым, если [F]=F.
Рассмотрим следующие классы функций.
Класс функций, сохраняющих 0:
.
Класс функций, сохраняющих 1:
Класс самодвойственных функций:
, где .
Класс монотонных функций
где .
Класс линейных функций
, где + - означает сложение по модулю 2, а знак конъюнкции опущен.
Теорема. Классы Т0, Т1, Т*, ТМ, TL – замкнуты.
Доказательство. Чтобы доказать, что некоторый класс F замкнут достаточно показать, что, если формула реализована в виде формулы над F, то она принадлежит F.
Рассмотрим доказательство для одного класса функций Т0.
Пусть и . Тогда .
Аналогичные доказательства можно привести для остальных классов.