Минимизация булевых функций

Минимизация булевых функций

Основные понятия

Элементарные конъюнкции(дизъюнкции) называются конституентами единицы(нуля), если он содержат все переменные функции.

В геометрическом смысле каждому набору переменных соответствует вершина n- мерного куба с координатами(например х1х2 х3). Элемент х1х2 х3 принято называть 0- кубом. Множество 0- кубов, на которых функция принимает единичные значения, называется кубическим комплексом К0 .

Например,  для f=xyz

К0 будет иметь следующий вид 000

              011

              110

              010

Если рассматривать ребро куба, то увидим что задействуется два К0 куба и образуется К1 куб. Причем на месте где есть различие между кубами ставится Х. Например 100 и 101 различаются по третьей координате и следовательно запись для К1 имеет вид 100 и 10Х(т. е. рассматривается ребро куба).

Например, для К0     011

              100

              101

              110

              111

К1 будет иметь следующий вид    Х11

              10Х

              1Х0

              1Х1

              11Х

т.е. каждый 0- куб последовательно сравнивается друг с другом.

В кубе для набора из 3 переменных – 4 вершины образуют грань.

Карты Карно – специальные таблицы, позволяющие упрощать процесс поиска минимальной формы булева выражения(булевой функции).

Карта Карно для функций двух переменных

            х

y                         
 

Карта Карно для функций трех переменных

Карта Карно для функций четырех переменных

Примеры карт Карно булевых выражений

Пример№1. Упростить булево выражение    xyz

Карта Карно для функций трех переменных

Проставим 1 в ячейки, где конъюнкции в выражении и таблицы совпадает

Запишем таблицу в другом виде

В первом прямоугольнике получим   xy y=y, результат y.

          Пример№2.               Пусть f=xyy   yz     xyz