Буль функцияларини соддалаштириш Режа

Минимальная ДНФ

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

Импликанта

• Элементарную конъюнкцию φк назовем импликантой булевой функции f, если не существует такого двоичного набора переменных, при котором функция φк принимает значение 1, а функция f – значение 0, то ecть φk  f = f.
• Проверить, являются ли одночлены
• и импликантами булевой функции

Справедливы утверждения

• Если f1, f2,…,fn импликанты булевой функции f, то f1  f2  …  fn и f1  f2  …  fn также являются ее импликантами.
• Если функция f1  f2  …  fn есть импликанта функции f, то функции f1, f2,…,fn также являются импликантами функции f.

СокрДНФ

• Элементарная конъюнкция, входящая в ДНФ булевой функции, называется ее простой импликантой, если никакая ее часть не является импликантой этой функции.
• Сокращенной ДНФ данной булевой функции называется ее ДНФ, составленная только из простых импликант.

Правило склеивания

Правило поглощения

• X  XF = X

• .

Пример

Пример

• Испытаем член AC. AC = 1, если A = 1 и C = 1.
• Подставим в оставшееся выражение 

• A = 1 и C = 1, получим

• При B = 0 F(A, B, C) = 1·1 + 0·0 = 1, но при В=1
• F(A, B, C) = 0·1 + 0·0 = 0.
• Следовательно, член AC не лишний

• Испытаем член BC, равный 1 при B = 0, C = 1. При этом

• Последнее выражение равно 1 как при A = 1,
• так и при A = 0. Поэтому член 

• – лишний.
• Испытание члена 

• по этой же методике показывает, что он не является
• лишним, в итоге тупиковая форма исходной функции
• имеет вид:

• .