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

мых конституентами единицы. Например, для функции / (х1, х 2, х 3, х4) конституентами единицы являются элементарные конъюнк­

ции ХуХ2х^>с4, ХуХ2х3х4. Для функции п переменных конституенты еди­

ницы имеют вид х хх 2 . . . хп.

Конституента единицы принимает единичное значение тогда и только тогда, когда все буквы принимают единичные значения. Смысл термина «конституента единицы» поясним на следующем примере. Предположим, что задана постоянно истинная четырех­ местная функция. Выразим эту функцию в виде формулы:

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

Если считать единицу функцией п аргументов, то ее можно раз­

ложить на 2" конституент, т. е. на 2" дизъюнктивно связанных эле­ ментарных конъюнкций п-то ранга, так как количество различных

наборов значений п равно 2 " .

О п р е д е л е н и е . Совершенной дизъюнктивной нормальной формой [СД Н Ф ] переключательной функции называется дизъюнк­ ция тех конституент единицы, которые обращаются в единицу на тех же наборах значений аргументов, что и данная функция.

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

Сокращенная запись СДНФ имеет вид:

/ = V $ при i = 0, 1, . . . , (5.8)

здесь п — ранг конъюнкции; i — номер набора, на котором функ­ ция принимает значения 1.

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

Пример 3. Разложим на конституенты единицу. Для этого пред­ ставим 1 = х V х, или 1 — (хг V ^iM*» V х 2). Использовав рас­

108

пределительный закон умножения относительного сложения, по­ лучим: 1 --x Lx 2 V x ix 2 V х 1 х з V х хх2•Аналогично

1= (Х1 V *i)( * 2 V Ч) {хз V Ха) = (*i*aV x~i*2 V \/-П■^'2 V -И^2)‘(-'-3V *з)=~X|XoX;j\УXiXgXg \/ Х2Хо\/

У-И^2 -^3V xlx2Х3 V Х1 Х2 Х3 V Х1 Х2 Х3 V И Х2 Х3.

Вобщем случае:

Слагаемые (5.9) называются конституентами разложения еди­ ницы «1». Конституенты «1» обладают следующими свойствами:

1 )произведение двух каких-либо конституентов «1 »равно нулю, так как любые два конституента обязательно содержат хотя бы одну одинаковую переменную в различных степенях (переменную и ее обращение)-,

2 )сумма всех конституентов единицы равна единице.

Указанные свойства запишем в виде формул

kr kj = 0 при i Ф j (i, / = 0, 1, 2, . . . 2'1-1);

2«—1_

1= V к

1-0

Любой конституент разложения «1» в соответствии с принятыми обозначениями можно записать,

— п °k ki = Д xk . ft=i

В алгебре релейных схем «1» представляет модуль умножения. Выше отмечалось, что любая булева функция имеет несколько ДНФ и одну СДНФ. Любая ДНФ получается в результате миними­ зации СДНФ. Переход от ДНФ к СДНФ называется развертыва­ нием. Развертывание можно выполнить с помощью законов (1—10).

Рассмотрим пример перехода от ДНФ к СДНФ.

*1 * 2 V % V *0*1 * 2 V *3 = *1 * 2 (хо V х) (х3 V *з) V *0*2 •

• (*i V *1 ) (*з V *з) V х о x i Х2 (*з V *з) V *з (*о V х 0) (хг V *1)•

• (х2 V х2) = Х 0Х гХ 2Х 3 V *0*1*2*3 V х0*1*2*3 V х0 Хх х2х3V Х 0ХхХ2Х3 V

109

V *0*1*2 *S V *0 *1 *2 *3 V *0 *1*2 *3= *0 *1 *2 *3 V*0 *1 *2 *3 V

V Х0*1*2*з\/ *0*1*2 *3 V *0 *1*2*3 V *0*1*2*3 V *0*1*2*3 V *0*1*2*3 V

ной конъюнктивной нормальной формой (СКНФ). Для этого исполь­ зуется понятие к о н с т и т у е н т ы н у л я . Смысл термина «конституента нуля» поясним на следующем примере. Используем таблицу 5.1 и будем считать, что задана постоянно ложная четырех­ местная булева функция. Ее формулу получим путем инверсии обеих частей формулы

Формула (5.11) представляет конъюнкцию 16, то есть всех воз­ можных различных элементарных дизъюнкций максимальной длины.

В данной формуле нулевое значение аргумента обозначается его буквой без знака инверсии, а единичное — буквой со знаком инверсии. На каждом наборе обращается в нуль лишь одна из дизъюнкций формулы (5.11), чего, однако, достаточно, согласно закону (5) для обращения всего выражения в нуль. Таким образом, можно сказать что формулой (5.11) представлено разложение нуля на его конституенты (составляющие), являющиеся элементарными дизъюнкциями 4-го ранга.

Теорема 3. Любую функцию алгебры логики (теорема де Мор­ гана) f (*х, *2, . . . , хп) (л!> 1) можно представить в форме:

110

конъюнкции, можно опускать. Сомножитель конъюнкции будет

111