- •Оглавление
- •Глава 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.3. Аналитические методы нахождения мднф Метод Квайна
Дает возможность нахождения Сокр. ДНФ из СДНФ функции.
Формулы метода
–неполное склеивание,
–поглощение,
где x– переменная,Aи B– конъюнкции любой длины.
Алгоритм метода
Шаг 1. Положить «формулу» равной СДНФ функции.
Шаг 2. Положитьnравным числу переменных функции.
Шаг 3. Провестивсевозможные операции неполного склеивания для входящих в «формулу» элементарных произведений, содержащих ровноnпеременных. Все получаемые элементарные произведения, ранее отсутствовавшие в «формуле», дописывать в нее через дизъюнкцию. Если формула не изменилась, то перейти на шаг 6.
Шаг 4. Удалить из «формулы» все элементарные произведения, для которых операция неполного склеивания была проведена хотя бы один раз (т.е. выполнить поглощение).
Шаг 5. Еслиn1, то уменьшитьn на 1 и перейти на шаг 3.
Шаг 6. Алгоритм закончен, «формула» является дизъюнкциейвсехпростых импликант исходной функции.
Метод Блейка
Дает возможность нахождения Сокр. ДНФ из любой ДНФ функции.
Формулы метода
–обобщенное склеивание,
–поглощение,
где x– переменная,Aи B– конъюнкции любой длины.
Алгоритм метода
Шаг 1. Положить «формулу» равной заданной ДНФ функции.
Шаг 2. Провести все возможные операции обобщенного склеивания для входящих в «формулу» элементарных произведений.
Шаг 3. Все полученные на шаге 2 элементарные произведения, ранее отсутствовавшие в «формуле», дописать в нее через дизъюнкцию. Если формула не изменилась, то перейти на шаг 5.
Шаг 4. Провести в «формуле» все возможные операции поглощения и перейти на шаг 1.
Шаг 5. Алгоритм закончен, «формула» является дизъюнкцией всех простых импликант исходной функции.
Таблица 6
Сравнение методов Квайна и Блейка
Параметры |
Метод Квайна |
Метод Блейка |
Область применения |
СДНФ |
Любая ДНФ |
Формула склеивания |
|
|
Формула поглощения |
|
|
Количество шагов |
Не превышает число переменных функции |
Заранее не известно |
Результат алгоритма |
Сокращенная ДНФ |
Сокращенная ДНФ |
Построение мднф из Сокр.Днф с помощью таблицы Квайна
Чтобы из fСокр.ДНФполучитьfМДНФ, необходимо отбросить все лишние импликанты. Для этого используетсятаблица Квайна, заголовки строк которой –простые импликанты, а столбцов – конституенты единиц минимизируемой функции. На пересечении строки и столбца ставится, если простая импликанта сохраняет единицу на том наборе, на котором конституента равна единице.
Алгоритм получения fМднФс помощью таблицы Квайна
Шаг 1. Для всех столбцов, содержащих ровно одну, выписать вfМДНФ(через дизъюнкцию) соответствующие простые импликанты.
Шаг 2. Удалить из таблицы все столбцы, в которых на пересечении со строками, выбранными на шаге 1, стоит.
Шаг 3. Удалить из таблицы все строки, соответствующие выбранным на шаге 1 простым импликантам, а также все строки, в которых нет ни одной.
Шаг 4. Повторять шаги 1–3 до тех пор, пока таблица изменяется.
Шаг 5. Из оставшихся строк перебором всех возможных вариантов выбрать минимальное по суммарному числу вхождений переменных множество простых импликант так, чтобы все оставшиеся столбцы имели на пересечении хотя бы с одной из выбранных строк.
Пример 28.Для функции
получить сокращенную и минимальную ДНФ)
1. Построим сокращенную ДНФ, используя метод Квайна. Для данной функции СДНФ была получена ранее (см. пример 26, стр. 57). Для сокращения записи алгоритма пронумеруем все дизъюнкты СДНФ и будем записывать номера дизъюнкт, участвующих в склейке, и результат.
I этап – операции полного склеивания для конъюнкций длины 4
1-2 (1’) 1-5 (2’) 2-3 (3’) 3-4 (4’) |
3-9 (5’) 5-6 (6’) 5-7 (7’) 6-8 (8’)
|
6-9 (9’) 7-8 (10’) |
IIэтап – операции полного склеивания для конъюнкций длины 3 (взятых с предыдущего этапа)
6’-10 (1”) 7’-8’(1”).
После проведения всех необходимых операций поглощения получим:
.
2. Получим теперь сокращенную ДНФ, используя метод Блейка (очевидно, что результат должен совпасть с предыдущим). Для метода Блейка необходима любая ДНФ функции. Возьмем в качестве исходной ДНФ, полученную выше (см. пример 27, стр.61):
.
Так же как и в предыдущем случае, пронумеруем дизъюнкты.
Iэтап. Операции обобщенного склеивания:
1–3 0 1–6 0
|
2–3 0 2–4 (7) 2–5 0 2–6 (8) |
3–4 0 3–5 (9) 3–6 0 |
4–6 0
|
5–6 (10) |
Операции поглощения:
1 поглощает 7, 8 поглощает 6, 9 поглощает 3.
IIэтап. Операции обобщенного склеивания (склеивания, в результате которых получены 0 не указаны):
1–5 (4) 1–8 (2) 2–4 (7) |
2–10 (8) 9–4 (5) 4–10 (5) |
5–8 (10) 5–10 (5)
|
Новых конъюнкций не появилось, поэтому можно записать
.
Матрица Квайна для функции f имеет следующий вид:
о |
|
|
|
|
|
|
|
|
|
|
* |
* |
|
|
|
|
|
|
|
|
* |
|
|
|
* |
|
|
|
|
|
|
* |
* |
|
|
|
|
|
|
|
|
|
* |
* |
|
|
|
|
|
|
|
|
* |
|
|
|
|
|
* |
|
|
|
|
|
|
* |
|
|
* |
|
|
|
|
|
* |
* |
* |
* |
|
Простыми не лишними импликантами точно являются ,
После первого этапа матрица примет вид:
|
|
|
|
|
* |
* |
|
|
* |
|
|
|
|
* |
|
|
|
|
* |
|
|
|
* |
Функция fимеет четыре тупиковые формы:
,
,
,
,
среди которых минимальными являются и.
Отметим, что в методе Квайна была использована на каждом этапе новая нумерация, так как на i-й этап выходят только элементарные произведенияi–1-го этапа. А в методе Блейка вi-м этапе участвуют все конъюнкции, полученные вплоть доi–1-го этапа, поэтому там использована сквозная нумерация.