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

Таблица истинности для функции от 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 Карты Карно при МДНФ

	K1: X1X5			K5: X1X2 3X4
	K2: X2X5			K6: X1 2X3X4
	K3: 3X5			K7: 1X2 3 4
	K4: 4 X5			K8: 1 2X3 4

 

Объединим их с помощью операции ИЛИ, получим МДНФ:

f = X1X5 v X2X5 v 3X5 v 4 X5 v X1X2 3X4 v X1 2X3X4 v 1X2 3 4 v 1 2X3 4 Посчитаем цену покрытия: S^a= 24, S^b = 32 Неравенство ограничения цены схемы по Квайну: 24 ≤ SQ ≤ 32.

ДЛЯ МКНФ

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

 

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

	D1: 1v 2v 3				D5: X2v X3v X4
	D2: 1v X2v X3				D6: 2v 3v X5
	D3: 1v X4v X5				D7: X2v X3v X5
	D4: 2v 3v X4				D8: X1v 4v X5
					D9: X1v X2v 3v 4

Объединим их с помощью операции И, получим МКНФ:

f = ( 1v 2v 3) ( 1v X2v X3) ( 1v X4v X5) ( 2v 3v X4) (X2v X3v X4) ( 2v 3v X5) (X2v X3v X5) (X1v 4v X5) (X1v X2v 3v 4)

 

Посчитаем цену покрытия: 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.