Лекция №8. Тема: свойства сднф и скнф.

· СДНФ не содержит двух одинаковых конъюнкций, а СКНФ - двух одинаковых дизъюнкций.

· Ни одна конъюнкция (дизъюнкция) СДНФ (СКНФ) не содержит одновременно двух одинаковых переменных

· Ни одна конъюнкция (дизъюнкция) СДНФ (СКНФ) не содержит одновременно некоторую переменную и ее отрицании в одной скобке.

· Каждая конъюнкция СДНФ содержит либо переменную, либо ее отрицание- , это относится ко всем переменным, входящим в данную формулу.

· Каждая булева функция от n переменных, отличная от 0, имеет единственную СДНФ и каждая булева функция отличная от единицы имеет единственную СКНФ. СДНФ содержит столько слагаемых, сколько единиц имеет таблица истинности. СКНФ содержит столько сомножителей, сколько нулей имеет таблица истинности.

 

Приведение ДНФ (КНФ) к СДНФ (СКНФ)

 

Примеры:

Привести к СДНФ

1)

Удаляем первую конъюнкцию слева, т.к. здесь переменная со своим отрицанием, остаётся →

2) Из конъюнкции (Y Z Y) удаляем Y, т.к. оно входит два раза →

3) К слагаемому добавляем (умножаем) , а (Y Z) умножаем на и с помощью дистрибутивного закона, получаем:

4) К первой и второй конъюнкции добавляем , получаем:

 

 

Привести к СКНФ: .

1) Во второй дизъюнкции нет Y, добавим туда

2) В третью добавим

3) Выписываем все элементарные дизъюнкции, используя закон дистирибутивности для преобразования выражения:

 

Общее правило преобразований:

Чтобы привести ДНФ к СДНФ надо в те скобки, где не хватает какой-либо переменной, например х, добавить и производить дальнейшие операции. Чтобы привести КНФ с СКНФ также надо добавить переменную и её отрицание, но только теперь с умножением

 

 

Лекция №9. Тема: минимизация булевых функций с помощью карты Карно.

 

Алгоритм минимизации булевой функции:

ü Привести булеву функцию ДНФ.

ü Нанести элементарные конъюнкции данной формулы (функции), как единиц на карту Карно.

ü Обвести единицы общим контуром, там, где это возможно.

ü Провести упрощение в объединенных конъюнкциях.

ü Оставшиеся члены объединить.

 

Карта Карно

Пример:

_ _ _ _

1. F = f(XYZ) = XYZ XYZ X YZ XYZ

Варианты Х	Варианты Х, Z
	_ _ YZ	_ YZ	YZ	_ YZ
X
_ X

 

_ _

1) (XYZ XYZ) = YZ(X X) = YZ

_ _ _ _ _ _

2) (XYZ XYZ) = YZ(X Z) = YZ

_ _ _ _ _ _

3) F = f(XYZ) = XYZ XYZ XYZ XYZ = YZ YZ = Y(Z Z) Y –минимизированная функция.

 

_ _ _ _ _ _ _ _ _ _ _ _ _

2. F = ABCD ABCD ABCD ABCD ABCD ABCD

 

	_ _ СD	_ CD	CD	_ CD
_ AB
_ AB
AB
_ AB

Если несколько единичек в карте Карно расположены на соседних клетках, то каждая единичка может и должна включаться во все контура, которые могут образоваться.

_ _ _ _ _ _ _ _ _ _

1) (ABCD ABCD) = ABD(C C) = ABD

_ _ _ _ _ _

2) (ABCD ABCD) = ABD(C C) = ABD

_ _ _ _ _ _ _ _ _ _

3) (ABCD ABCD) = ABC(D D) = ABC

_ _ _ _ _ _

4) f(ABCD) = ABD ABD = AD(B B) = AD

_ _ _

5) f(ABCD) = AD ABC – минимизированная функция

 

	_ _ x3x4	_ x3x4	x3x4	_ x3x4
_ _ x1x2
_ x1x2
x1x2
_ x1x2

_ _ _ _ _ _ _ _

3. F = x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄

__{___}_ __{__} __{_}_ _ _ _ _ _

1) (x₁x₂x₃x₄ x₁x₂x₃x₄) = x₂x₃x₄ (x₁ x₁) = x₂x₃x₄

__{_} __{_} _ _ _

2) (x₁x₂x₃x₄ x₁x₂x₃x₄) = x₂x₃x₄ (x₁ x₁) = x₂x₃x₄

_ _ _ _ _{_}_ _

3) F = (x₂x₃x₄ x₂x₃x₄) = x₂x₄ (x₁ x₁) =x₂x₄ – минимизированная функция.