Совершенные нормальные формы.

Пример 2.4.

Пример 2.3.

Нормальные формы записи булевых функций.

Задание функции комбинационных логических схем.

Функция может быть задана:

1) таблицей истинности.

Таблица истинности (табл. 2.1.) перечисляет все наборы значений двоичных переменных и содержит строк, где n – число переменных. Для каждого набора указывается значение функции. Если функция на наборе не определена, то в столбце значений функции используется “-“ (прочерк). Если определить старшинство переменных, то каждому набору можно присвоить номер, указываемый в столбце номеров N.

2) номерами наборов, например, F=1 на наборах {2,3,6}.

3) задание в виде формулы алгебры логики.

Формула представляет собой совокупность имён логических переменных, знаков логических операций и скобок.

.

Выражение вычисляется слева на право в соответствии со старшинством операций .

4) топологические способы задания функции в виде графов или диаграмм (карт) Карно, в виде n - мерных кубов.

Любая функция алгебры логики может быть представлена в дизъюнктивной нормальной форме (ДНФ) или конъюнктивной нормальной форме (КНФ).

ДНФ – дизъюнкция элементарных конъюнкций.

Элементарная конъюнкция – это конъюнкция переменных функций и их отрицаний. Она не может включать переменную и её отрицание одновременно.

Следующие выражения являются элементарными конъюнкциями.

Дизъюнкция элементарных конъюнкций: - ДНФ.

КНФ – конъюнкция элементарных дизъюнкций.

Элементарная дизъюнкция – это дизъюнкция переменных функций и их отрицаний. Она не может включать переменную и её отрицание одновременно.

Следующие выражения являются элементарными дизъюнкциями.

Конъюнкция элементарных дизъюнкций: - КНФ.

Одна и та же функция может иметь несколько ДНФ или КНФ.

Конституентой единицы называют элементарную конъюнкцию, содержащую все переменные функции. По-другому, конституента единицы называется конъюнктивной конституентой, или минитермом.

Конституентой нуля называют элементарную дизъюнкцию всех переменных функций, иначе её называют дизъюнктивной конституентой, или макситермом.

Конституента единицы принимает единственное значение тогда и только тогда, когда все буквы принимают единичное значение (буква – сама переменная или её отрицание ).

abc=1 только на том наборе, где a=1, b=1, c=1, N=7 (см. табл. 2.1)

только на том наборе, где , N=5.

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

Конституента нуля равна 0 на наборе , а конституента нуля равна 0 на наборе .

На основе конституент единицы (нуля) строятся совершенные нормальные формы (СНФ)

Дизъюнкция конституент единиц носит название совершенной дизъюнктивной нормальной формы (СДНФ).