Минимизация неполностью определенных переключательных функций

Чтобы найти простейшее представление неполностью определенной ПФ, кроме минимальных дизъюнктивных форм следует получить минимальные конъюнктивные нормальные формы и выбрать из них ту, которая содержит наименьшее число букв.

Алгоритм получения минимальных конъюнктивных форм подобен рассмотренному алгоритму получения минимальной ДНФ и заключается в следующем.

Пусть задана неполностью опре

деленная функция f(x1, x2, …, xn). Тогда для получения минимальной КНФ достаточно найти сокращенную КНФ эквивалентной функции j0(x1, x2, …, xn), а функцию j1(x1, x2, …, xn) записать в СКНФ. Затем следует составить ипликантную матрицу, включив в нее все конституенты нуля функции j1(x1, x2, …, xn) и все члены сокращенной конъюнктивной нормальной формы функции j0(x1, x2, …, xn). По импликантной матрице рассмотренным выше способом можно получить минимальные КНФ функции f(x1, x2, …, xn).

Пример. Найти минимальную КНФ функции, записанной таблицей.

СКНФ эквивалентной функции j1(x1, x2, x3, x4):

СКНФ функции

Сокращенная КНФ функции j0(x1, x2, x3, x4)

Импликантная матрица имеет вид:

Минимальная КНФ функции f(x1, x2, x3, x4)

Рассмотренная функция имеет четыре минимальные ДНФ

 Скачать реферат