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

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

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

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

Если функция на наборе не определена, то в столбце значений функции используется “-“ (прочерк).

Если определить старшинство переменных, то каждому набору можно присвоить номер указываемый в столбце номеров N.

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

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

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

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

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

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

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

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

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

Пример 2.3.

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

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

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

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

Пример 2.4.

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

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

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

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

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

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

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

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

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

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

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

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

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