- •Оглавление
- •Глава 3. Логика высказываний 78
- •Глава 4. Логика предикатов 90
- •Введение
- •I. Системы счисления
- •1.1. Непозиционные системы счисления. Римская система счисления
- •1.2. Позиционные системы счисления
- •1.3. Взаимосвязь систем счисления
- •I. Алгоритм перевода целого числа Aq из q-ичной системы счисления в число Bd d-ичной системы
- •II. Алгоритм перевода целого числа Ad из d-ичной системы счисления в число Bq q-ичной системы
- •III. Алгоритм перевода правильных дробей из q-ичной системы счисления в d-ичную с вычислениями в d-ариф-метике
- •IV. Алгоритм перевода правильных дробей из d-ичной системы счисления в q-ичную с вычислениями в d-арифметике
- •V. Алгоритм перевода чисел из d-ичной системы счисления в dn-ичную систему счисления
- •VI. Алгоритм перевода чисел из dn-ичной системы счисления в d-ичную систему счисления.
- •1.4. Двоичная система счисления
- •1.4.1. Двоичная арифметика
- •1.4.3. Вычитание с использованием двоичного дополнения. Умножение
- •Алгоритм вычитания целых десятичных чисел
- •Алгоритм отыскания двоичного дополнения числа
- •Теория множеств
- •Глава 1. Множества
- •1.1. Основные определения
- •1.2. Основные операции теории множеств
- •Старшинство операций (операции даны по убыванию приоритетов)
- •1.4. Диаграммы Венна
- •1.5. Основные законы теории множеств
- •1.6. Декартово произведение и отношения
- •Глава 2. Бинарные отношения
- •2.1. Основные определения
- •Глава 3.Функции и операции
- •Примеры функций
- •Операции над функциями
- •Свойства бинарных операций
- •Глава 4.Алгебраические структуры
- •III. Математическая логика
- •Глава 1. Переключательные функции
- •1.1. Основные определения
- •Переключательные функции двух аргументов
- •1.2. Основные теоремы (эквивалентные соотношения) переключательных функций
- •Глава 2.Булева алгебра
- •2.1. Основные определения
- •Эквивалентные соотношения в булевой алгебре
- •2.2. Минимизация булевых функций
- •2.3. Аналитические методы нахождения мднф Метод Квайна
- •Формулы метода
- •Алгоритм метода
- •Метод Блейка
- •Формулы метода
- •Алгоритм метода
- •Сравнение методов Квайна и Блейка
- •Построение мднф из Сокр.Днф с помощью таблицы Квайна
- •Алгоритм получения fМднФс помощью таблицы Квайна
- •2.4. Графическая минимизация логических функций
- •Метод карт Карнапа
- •Алгоритм минимизации по карте Карнапа
- •2.5. Полнота систем булевых функций
- •Классы Поста
- •Полиномы Жегалкина
- •Глава 3.Логика высказываний
- •3.1. Основные понятия
- •3.2. Алгебра логики высказываний
- •3.3. Применение к естественному языку
- •Список наиболее часто встречающихся выражений, соответствующих логическим связкам
- •3.4. Исчисление высказываний (ив)
- •Глава 4.Логика предикатов
- •Определения кванторных высказываний
- •4.1. Алгебра логики предикатов
- •4.2. Выполнимость и общезначимость
- •4.3. Равносильность формул
- •Приведенные формулы
- •4.4. Применение логики предикатов к естественному языку
- •4.4.1. Суждения
- •Виды категорических суждений
- •4.4.2. Исчисление одноместных предикатов как исчисление классов. Теория категорических суждений и силлогизмов Аристотеля
- •Законы формальной логики Аристотеля:
- •4.4.3. Умозаключения
- •Наиболее распространенные схемы правильных дедуктивных рассуждений
- •4.4.4. Основные законы формальной логики. Логические основы аргументации
- •4.5. Исчисление предикатов
- •Литература
- •Предметный указатель
2.2. Минимизация булевых функций
Импликантой f2(x1, x2,..., xn) данной функцииf1(x1, x2,..., xn) называется функция со следующими свойствами:
Лемма 5. Функцияgявляется импликантой функцииf тогда и только тогда, когда переключательная функцияgf равнаconst1.
Лемма 6. Если функцияg– импликанта функцииfиg =ab, гдеaиb – произвольные функции, тоaиb также являются импликантами функцииf.
Простой импликантой булевой функции называется элементарное произведение, которое является импликантой, и никакая собственная часть которого не является импликантой.
Лемма 7. Конституенты единицы тех наборов, на которых данная функция равна единице, есть импликанты данной функции.
Лемма 8. Любая собственная часть конституенты единицы фиксированного набора сохраняет единицу на этом фиксированном наборе.
Сокращенная дизъюнктивная нормальная форма (Сокр. ДНФ) есть дизъюнкция всех простых импликант функции. ОбозначаетсяfСокр.ДНФ(x1, x2,..., xn). Формулы, получаемые перестановкой конъюнкт и дизъюнкт, считаются одной и той же Сокр. ДНФ.
Теорема 2. Всякая переключательная (логическая) функция представима, причём однозначно, в виде некоторой сокращенной дизъюнктивной нормальной формы.
Сокращенная ДНФ функции может содержать так называемые лишние импликанты. Лишниминазываются теимпликанты, удаление которых из Сокр. ДНФ функции не изменяет ее таблицы истинности.
Форма булевой функции, которая является дизъюнкцией простых импликант, среди которых нет лишних, называется тупиковой ДНФ (ТДНФ). Различные тупиковые ДНФ одной и той же функцииf(x1, x2,..., xn) могут содержать разное число вхождений переменных. Выбор среди всех тупиковых ДНФ функцииf(x1, x2,..., xn) формы с наименьшим числом вхождений переменных даетминимальную дизъюнктивную нормальную форму (МДНФ). Необходимо отметить, что в общем случае у одной функцииf (x1, x2,..., xn) может быть несколько различных МДНФ, но все они имеют одинаковое число вхождений переменных, причем наименьшее среди всех ДНФ функцииf(x1, x2,..., xn).
Пример 27.Получить тупиковую форму для функции:
.
Согласно лемме 5, функции ,,,,,являются импликантами функцииf. Проверим, являются ли эти импликанты простыми. Для этого надо построить таблицы истинности для всех собственных частей этих импликант (импликанта является простой, если никакая ее собственная часть импликантой не является).
Очевидно, что никакая часть не импликанты не может быть импликантой. Поэтому, если при проверке на простоту импликанты длины n оказалось, что все ее собственные части длины n–1 оказались не импликантами, то не имеет смысла проверять ее собственные части длины n–2, …,1.
Ниже в табл. 4 приведены истинностные значения для всех функций, необходимых для подтверждения простоты импликант. Выделены те единицы функции, из-за которых она не является импликантой (достаточно одной такой единицы-нарушителя у функции). В первой строке таблицы указаны импликанты, которые проверяются на простоту, а во второй строке для каждой из этих функций выписаны ее собственные части (не все, а лишь только те, которые необходимы для установления простоты).
Таблица 4
|
|
|
|
|
и | ||||||||||||
x,y,z,p |
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 0 0 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
1 |
1 |
0 0 0 1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
0 0 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 0 1 1 |
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
0 1 0 0 |
1 |
|
|
|
|
1 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 1 0 1 |
1 |
|
1 |
|
|
1 |
1 |
1 |
1 |
|
|
|
1 |
1 |
1 |
|
|
0 1 1 0 |
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
1 |
|
|
1 |
|
0 1 1 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
1 |
|
|
|
|
1 0 0 0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 0 0 1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 0 1 0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 0 1 1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 1 0 0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
1 |
1 1 0 1 |
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
1 1 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 1 1 1 |
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
Импликанта? («+» – да) |
|
– |
+ |
– |
– |
– |
– |
– |
+ |
– |
+ |
– |
– |
– |
– |
– |
– |
Окончание табл. 4
|
|
|
|
|
| |||||||
x,y,z,p |
f |
|
|
|
|
|
|
|
|
|
|
|
0 0 0 0 |
1 |
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
0 0 0 1 |
|
|
1 |
1 |
|
|
|
|
1 |
|
|
1 |
0 0 1 0 |
|
|
1 |
|
1 |
|
|
|
|
|
|
|
0 0 1 1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
0 1 0 0 |
1 |
|
|
|
|
1 |
|
|
|
1 |
|
|
0 1 0 1 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 1 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
0 1 1 1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
1 0 0 0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
1 0 0 1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
|
|
1 |
1 0 1 0 |
1 |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
1 0 1 1 |
1 |
1 |
1 |
|
|
|
|
1 |
|
|
|
|
1 1 0 0 |
|
1 |
|
|
|
1 |
1 |
|
|
1 |
|
|
1 1 0 1 |
1 |
1 |
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 1 1 0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
1 1 1 1 |
|
1 |
|
|
|
|
|
1 |
|
|
1 |
|
Импликанта? («+» – да) |
|
– |
– |
– |
– |
– |
– |
– |
– |
– |
– |
– |
Теперь перепишем из табл. 4 все простые импликанты функции. В полученной таблице не обязательно присутствуют вообще все простые импликанты данной функции, мы лишь можем утверждать, что дизъюнкция всехпростых импликантиз таблицыдает исходную функцию, т.е.
.
Чтобы получить некоторую тупиковую форму, осталось удалить все лишние импликанты из этой записи. Для этого можно воспользоваться следующей таблицей (из таблицы истинности убрали строки, в которых функция равна 0).
Таблица 5
x,y,z,p |
f |
|
|
|
|
|
|
|
0 0 0 0 |
1 |
|
|
1 |
1 |
|
|
|
0 1 0 0 |
1 |
|
1 |
1 |
|
|
|
|
0 1 0 1 |
1 |
1 |
1 |
|
|
|
1 |
|
0 1 1 1 |
1 |
|
|
|
|
|
|
|
1 0 0 0 |
1 |
|
|
|
1 |
|
|
1 |
1 0 0 1 |
1 |
|
|
|
|
1 |
|
1 |
1 0 1 0 |
1 |
|
|
|
|
|
|
|
1 0 1 1 |
1 |
|
|
|
|
|
|
1 |
1 1 0 1 |
1 |
|
|
|
|
1 |
1 |
|
В таблице отмечены те единицы функции, которые говорят, что импликанта точно не лишняя. Лишними можно считать, например, импликанты ,и, тогда
.