Представление функций алгебры логики

Булевой (переключательной, двоичной) функцией называется двоичная переменная , значение которой зависит от значений других двоичных переменных ( , , …, ), именуемых аргументами:

				(		).
Задание булевой функции означает, что каждому из возможных сочетаний аргументов по-
ставлено в соответствие определённое значение .
При	аргументах общее число сочетаний				. Так как каждому сочетанию аргументов со-
ответствует два значения функции (0, 1), то общее число функций							.
Булевая функция может быть задана на словах, таблично, алгебраически или числовым спо-
собом.
Для алгебры логики установлено, что если					(	), где	и — двоичные функции, т.е.
(	),	(	), то	(	).

Операцию замены одной функции другими функциями называют суперпозицией. Эта операция даёт возможность с помощью функций малых аргументов получить функции большего числа аргументов. Так, при помощи суперпозиции можно получить функцию с требуемым числом аргументов, используя только функцию двух аргументов.

При помощи набора булевых функций двух аргументов можно описать любую цифровую систему. На практике используют не все функции, а лишь те из них, которые методом суперпозиции обеспечивают представление любой другой функции. Набор таких функций называют функциональ-

но полным набором (ФПН).

Существует несколько ФПН. В качестве ФПН применяются дизъюнкция, конъюнкция и инверсия. Этот набор называют основным ФПН (ОФПН).

Кроме ОФПН, широкое применение получили:

функционально-полная система, включающая в себя только одну функцию — функцию Пирса (ИЛИ-НЕ);

функционально-полная система, включающая в себя только одну функцию — функцию Шеффера (И-НЕ).

При помощи этих функций можно построить любую цифровую систему.

Синтез логических устройств в базисе ОФПН состоит из представления этих функций в нор-

мальных формах и минимизации.

Нормальной формой считают представление этих функций посредством суперпозиций вспомогательных функций — минтермов и макстермов.

Минтермом называют функцию, которая принимает 1 только при одном значении аргументов и 0 — при других (иногда в литературе используется термин «конституэнта единицы»).

101

Макстермом называют функцию, которая принимает 0 только при одном значении аргументов и 1 — при другом (иногда в литературе используется термин «конституэнта нуля»).

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

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

102