Составление таблицы истинности

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 4Следующая ⇒

Таблица истинности для функции от 5ти переменных X₁, X₂, X₃, X_4, X₅ заданная выражением 2 < |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| <= 5 и имеющим неопределенное значение при условии:  |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| = 1 (Таблица 1)

Таблица 1 Таблица истинности

ПРЕДСТАВЛЕНИЕ БУЛЕВОЙ ФУНКЦИИ В АНАЛИТИЧЕСКОМ ВИДЕ С ПОМОЩЬЮ КДНФ И ККНФ

Запишем булеву функцию в канонических ДНФ и КНФ. d состояния для уменьшения числа термов при КНДФ заменяем на ноль, а при ККНФ на единицу.

КДНФ: f = _{1 2 3}X₄X₅ ˅ _{1 2}X_{3 4 5} ˅ _{1 2}X_{3 4}X₅ ˅ ₁X_{2 3 4 5} ˅ ₁X_{2 3 4}X₅ ˅ ₁X₂X₃X₄X₅ ˅ X_{1 2}X_{3 4}X₅ ˅ X_{1 2}X₃X_{4 5} ˅ X_{1 2}X₃X₄X₅ ˅ X₁X_{2 3 4}X₅ ˅ X₁X_{2 3}X_{4 5} ˅ X₁X_{2 3}X₄X₅

ККНФ: f  = (X₁ ˅ X₂ ˅ X₃ ˅ X₄ ˅ X₅ ) (X₁ ˅ X₂ ˅ X₃ ˅ ₄ ˅ X₅ ) (X₁ ˅ X₂ ˅ ₃ ˅ ₄ ˅ X₅ ) (X₁ ˅ X₂ ˅ ₃ ˅ ₄ ˅ ₅ ) (X₁ ˅ ₂ ˅ X₃ ˅ ₄ ˅ X₅ ) (X₁ ˅ ₂ ˅ ₃ ˅ X₄ ˅ X₅ ) (X₁ ˅ ₂ ˅ ₃ ˅ ₄ ˅ X₅ ) ( ₁ ˅ X₂ ˅ X₃ ˅ X₄ ˅ X₅ ) ( ₁ ˅ X₂ ˅ X₃ ˅ ₄ ˅ X₅ ) ( ₁ ˅ X₂ ˅ ₃ ˅ X₄ ˅ X₅ ) ( ₁ ˅ ₂ ˅ X₃ ˅ X₄ ˅ X₅ ) ( ₁ ˅ ₂ ˅ ₃ ˅ X₄ ˅ X₅ ) ( ₁ ˅ ₂ ˅ ₃ ˅ ₄ ˅ X₅ )

МИНИМИЗАЦИЯ БУЛЕВОЙ ФУНКЦИИ

МЕТОД КВАЙНА – МАК-КЛАСКИ

Чтобы получить сокращенную ДНФ булевой функции из ее совершенной ДНФ по теореме Квайна, надо выполнить всевозможные неполные склеивания соседних конъюнкций, а затем всевозможные поглощения конъюнкций. Мак Класки сформулировал алгоритм, который организует построение сокращенной ДНФ более эффективно, чем это предложено в теореме. Для использования метода Квайна-Мак-Класки для начала необходима таблица истинности для 0-куба. Для достижения максимального r-куба d в исходной таблице истинности заменяется на 1.

Таблица 2 Простые импликанты

Используя таблицу простых импликантов и проводя операцию склейки, находятся кубы максимальной размерности. Термы, которые не участвовали в операции склейки, отмечены зеленым (простые импликанты) и составляют покрытие Z(f) (Таблица 2). Оно задает СДНФ исходной функции. Склеиваемые термы отмечены *, справа от полученного терма написаны номера, из которых они получились.

Таблица 3 Импликантная таблица

 Чтобы отобразить покрытие простыми импликантами существенных вершин составляется имплекантная таблица. Каждая строка это простая импликанта, а каждый столбец – один из 0-кубов (Таблица 3). Для неполностью определенной функции безразличные наборы исключаются. Далее выделяем множество существенных импликант. Находятся столбцы с одной меткой (выделены красным х). Строки соответствующих импликант удаляются (закрашиваются оранжевым), захватавая другие отмеченные * столбцы, которые встречаются в удаляемой строке.  Множество всех существенных импликант (строки с красным х, 1-5, 7) образует ядро покрытия Т.

T = {0010-; 0100-; 1011-; 1101-; --0-1; -1--1}

Термы ядра: _{1 2}X_{3 4, 1}X_{2 3 4} , X_{1 2}X₃X₄, X₁X_{2 3}X_{4, 3}X_5, X₂X₅

Удалив ядро из таблицы получим упрощенную импликантную таблицу (Таблица 4).

Таблица 4 Упрощенная импликантная таблица

Термы упрощенной таблицы (выбираем любой, оба покрывают g 0-куб) и добавляем его к ядру покрытия, чтобы получить минимальное покрытие:

С_min = {0010-; 0100-; 1011-; 1101-; --0-1; -1--1; 1---1}

1---1 соответствует X₁X_5, следовательно

МДНФ: f = _{1 2}X_{3 4} ˅ ₁X_{2 3 4} ˅ X_{1 2}X₃X₄ ˅ X₁X_{2 3}X₄ ˅ ₃X₅ ˅ X₂X₅ ˅ X₁X₅

Вычислим цену покрытия S^a, которая является количеством переменных, участвующих в записи МДНФ; цену покрытия S^b, которая является суммой цены S^a и количества термов МДНФ. Данные цены образуют предельные границы цены схемы по Квайну: S^a ≤ S_Q ≤ S^b.

Посчитаем цену покрытия: S^a = 22, S^b = 29

Неравенство ограничения цены схемы по Квайну: 22 ≤ S_Q ≤ 29.

МЕТОД ПЕТРИКА

Невозможно применить к упрощенной таблице из-за ее маленького объема, поэтому применяем к обычной таблице.

Таблица 5 Таблица для метода Петрика

Для метода Петрика нужно выписать булево выражение Y, покрывающее все существенные вершины:

Y = EA(A ˅ F)B(B ˅ E ˅ F ˅ G)G(F ˅ H)C(C ˅ H) (E ˅ F ˅ G ˅ H)D(D ˅ E ˅ G ˅ H)

Попарно умножив термы с одинаковыми буквами, применив закон поглощения, упростим выражение и приведем его к дизъюнктивной форме:

Y = ABCDEG(F v H) = ABCDEGF v ABCDEGH

Оба терма состоят из 7ми букв, так что можно выбрать любой. ABCDEGH соответствует минимальному покрытию:

С_min = {0010-; 0100-; 1011-; 1101-; --0-1; -1--1; 1---1}

МДНФ ( также не изменилась): f = _{1 2}X_{3 4} ˅ ₁X_{2 3 4} ˅ X_{1 2}X₃X₄ ˅ X₁X_{2 3}X₄ ˅ ₃X₅ ˅ X₂X₅ ˅ X₁X₅

Цена не изменилась: S^a = 22, S^b = 29

Цена по методу Квайна – Мак – Класки не изменилась в методе Петрика, потому что в итоге выбирается одинаковое количество импликант с одинаковым покрытием вершин. Метод Квайна – Мак – Класки скорее визуальный, а метод Петрика позволяет точно вычислить каждую комбинацию импликантов и покрытых вершин, где потом выбирается вариант с минимальным покрытием.

МЕТОД КАРТ КАРНО

ДЛЯ МДНФ

Для определения МДНФ функции рассмотрим карты с единичными значениями функции, а также доопределим значение d до единицы (Таблица 6). Выделяем области с максимальным количеством единиц, которые могут содержать количество элементов кратное двум в степени n, те. 2, 4, 8..

Таблица 6 Карты Карно при МДНФ

ДЛЯ МКНФ

Для определения МКНФ функции рассмотрим карты с нулевыми значениями функции, а также доопределим значение d до нуля (Таблица 7). Выделяем области с максимальным количеством нулей, которые могут содержать количество элементов кратное двум в степени n, те. 2, 4, 8..

Таблица 7 Карты Карно при МКНФ

Посчитаем цену покрытия: S^a = 28, S^b = 37

Неравенство ограничения цены схемы по Квайну: 28 ≤ S_Q ≤ 37.

Сравним цены различных МДНФ и МКНФ.

Границы для МДНФ:

Ограничения цены схемы по Квайну, метод К-М-К: 22 ≤ S_Q ≤ 29.

Ограничения цены схемы по Квайну, метод Петрика: 22 ≤ S_Q ≤ 29

Ограничения цены схемы по Квайну, метод карт Карно: 24 ≤ S_Q ≤ 32

Границы для МКНФ:

Ограничения цены схемы по Квайну, метод карт Карно: 28 ≤ S_Q ≤ 37

Для факторизации и декомпозиции берем МДНФ, полученную методом К-М-К и методом карт Карно, потому что они имеют наименьшую S^a, равную 22 и 24.

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров