Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

тельных функций (табл. 4.2), которые в переключательной алгебре можно трактовать как элементарные операторы. Указанным опера­ торам могут быть поставлены в соответствие элементарные опе­ рации математической логики.

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

0) = 0. Поскольку на одном из наборов значения функций фикси­ рованы, произвольными остаются (в случае п переменных) лишь

зывается линейной, если ее возможно представить в виде канониче­

ление самодвойственных функций будет следующее.

Булева функция называется самодвойственной, если на любых двух противоположных наборах она принимает противоположные значения (0 и 1).

Самодвойственная функция в случае табличного способа зада­ ния функций будет иметь вид таблицы 4-14.

98

Из таблицы 4-14 видно, что при расположении набора в естест­ венном порядке противоположные друг другу наборы помещаются симметрично относительно середины этого расположения.

Количество самодвойственных булевых функций от п аргумен­

-fin

тов равно | Примеры:

1. /(%!, X2)= * lV * 2 , /*(*!, X2)==X1\/^2 = ^lA^2=^lA^2-

2. f2(x) = x, /* ( x)=J (x) = x = x.

функции (х, х г х г). Приведем определения для суперпозиции лю­ бого числа функции данного класса:

1)суперпозиция любого числа булевых функций, сохраняющих кон­ станту «О», является также функцией,сохраняющей константу «О»;

2)суперпозиция любого числа булевых функций, сохраняющих

константу «1», является функцией, сохраняющей константу «1»;

3)суперпозиция любого числа линейных булевых функций пред­ ставляет собою снова линейную функцию',

4)суперпозиция любого числа самодвойственных функций яв­ ляется снова самодвойственной функцией',

5)суперпозиция любого числа монотонных булевых функций яв­ ляется, в свою очередь, монотонной функцией.

Свойства элементарных функций указаны в таблице 4-15.

Система [набор] элементарных логических функций называется функционально полной, если произвольную булеву функцию можно представить в виде суперпозиции функций этой системы.

Введенное определение легко распространяется на произволь­ ные булевы функции. При установлении необходимых и достаточ­ ных условий функциональной полноты большую роль играют пять классов булевых функций. Используя пять классов булевых функ­ ций в работе «Синтез цифровых автоматов», В. М. Глушков рас-

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

Теорема гласит: Для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала по крайней мере одну функцию: 1) не сохраняющую константу «О», 2 ) не сохра­ няющую константу «1», 3) несамодвойственную, 4 )немонотонную, 5) нелинейную.

Доказательство необходимости описываемых в этой теореме свойств системой булевых функций вытекает из определений 1—5, а также из того, что тривиальные функции f (хг...........хп) -- xt при­ надлежат каждому (i — 1, . . . , п) из пяти классов булевых функ­ ций. Целью теоремы является построение в виде суперпозиций функ­ ции системы s и переменных (хг, . . . , хп) любой заданной булевой функции f (х1г . . . , хп) этих переменных.

Из теоремы следует, если каждая функция не обладает лишь одним из пяти перечисленных выше свойств, то для функциональ­ ной полноты потребуется система из пяти функций. Если какая-либо функция не обладает ни одним из этих пяти свойств, то она одна образует функционально полную систему.

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

100

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

Система функций, которая в сумме накрывает значками «-}-» все пять колонок (табл. 4-15), является функционально полной. Несо­

стемы, состоящие из определенного количества элементарных буле­

Анализ таблицы 4-15 показывает, что несократимые полные системы элементарных функций могут состоять не более чем из трех функ­ ций.

К числу несократимых не относится система (Д , V>—), а так-

же максимальная система. Максимальная система является набо­ ром всех элементарных функций двух переменных.

Система (Д , \J , —) и максимальная являются функционально полными. Из системы (Д , \J , —) может быть исключена без нару­ шения полноты одна из операций: «—», «Д» или «!/»•

Из максимальной системы могут быть образованы все несокра­ тимые системы.

Вопросы и задачи для самопроверки

1.Какие функции называются переключательными?

2.Как зависит число различных переключательных функций от числа ар­ гументов? Подсчитайте число различных функций от двух, трех и четы­ рех аргументов.

3.Составьте таблицы значений функций:

/1 (Х1 >х2<хз) = *1 V х2х3 >

/ 2 (xlt х2, х3) = (х, V х2) -> (хх V х3).

101