Нахождение основного простого импликанта

Question

Учитывая таблицу:

Я пытался найти простые импликанты функции F (ш, х, у, г) = сумма (0, 2, 5, 7, 8, 10, 12, 13, 14, 15). Я получил существенный основной импликатор xz. Мне было интересно, были ли более существенные первичные импликанты? Мне трудно понять, как их найти.

Answer 1

Основной импликатор является логическим термином в минимальном DNF (дизъюнктивная нормальная форма, SOP = сумма продуктов) или минимальная CNF (конъюнктивная нормальная форма, POS = произведение сумм), которая после удаления какой-либо ее части не будет быть главным импликантом для выходной функции.

Рассмотрим более простой пример:

a\b 0 1 
    +---+---| 
    0 | 0 | 0 | 
    1 | 0 |(1)| 
    +---+---+ 

Вы могли бы написать функцию вывода в виде ДНФ, как minterm на позиции значений литералов: a=1, b=1 („кружились“ в круглых скобках в K-карта):

y = a*b 

это является премьер импликантой, потому если вы удалите любой из литералов (переменная или отрицание переменной), она больше не будет импликантом для функции вывода!

Здесь у вас есть только две переменные, поэтому вы можете удалить из правой функции выходной функции y = a*b либо a (a, либо ее отрицание), либо b (b или его отрицание).

Удаление б от у = а * б вы бы либо круг один ноль на позиции a=1, b=0:

a\b 0 1 
    +---+---| 
    0 | 0 | 0 | 
    1 |(0 1)| 
    +---+---+ wrong_output_function: y1 = a 

или обвести один нежелательныйнулевой на позиции a=0, b=1 путем удаления a (a или его отрицания):

a\b 0 1 
    +---+---| 
    0 | 0 |(0)| 
    1 | 0 |(1)| 
    +---+---+ wrong_output_function: y2 = b 

В этом примере, выбирая для выражения функции вывода в DNF, вы хотите обвести все те части и NO ноль, поэтому все эти два булевых выражения y1 и y2 ошибочны.

Для примера:

Для нахождения минимального формы DNF вы хотели бы найти самые крупные группы (термины) возможно, те имеют наименьшее возможное число переменных в них, не ставя под угрозу обоснованность функция вывода в этом случае добавляет нуль в любую из групп (импликанты выходной функции).

Здесь вы можете видеть, что некоторые из групп перекрываются, но это нормально, потому что группы имеют минимальную форму по определению. Это K-карта минимальна, потому что вы не можете сделать выбранные группы более крупными.

Вы могли бы, например, круг в красные не захвачена зеленым кругом по отдельности, но в этом случае они не будут простыми импликантами, потому что вы можете сделать их группы больше, как показано в предыдущей карте Карно , Следовательно, это K-отображение не является минимальным, так как существуют не-первичные импликанты.

Примечание: индексы в вашей функции не соответствуют индексам в моем K-карте, из-за различные перестановки переменных. Мои K-карты соответствуют позициям переменных в вашем исходном стиле K-map. На этом основана выходная функция.