2001-0084-0-01 (Лабы), страница 3

Функционально полные наборы и базисные наборыФункционально полным называется набор булевых функций {f1,f2, …, fn} такой, что любая сколь угодно сложная булева функция можетбыть выражена в виде суперпозиции (сочетания) функций из этого набора.Базисным называется такой функционально полный набор, из которого нельзя исключить ни одну булеву функцию без ущерба для егофункциональной полноты.Поскольку любая булева функция, заданная таблицей истинности,может быть представлена в виде СДНФ (или СКНФ), то набор1) {&, ∨,  ) – функционально полный набор.Набор 1) не является базисным набором, так как из него можно исключить либо &, либо ∨, а недостающую функцию реализовать с помощьюоставшихся функций.

Например, если из набора 1) исключена &, то ееможно реализовать так: AB =  ( A ∨ B) (выражение справа понимается так: A ∨ B ). Если же из набора 1) исключена функция ∨, то она можетбыть реализована так: X ∨ Y =  ( X Y) = X Y .14Таким образом, получаем два функционально полных (базисных) набора:2) {&,  };3) {∨,  }.Русский математик Жегалкин показал, что любая булева функцияможет быть представлена с использованием операций конъюнкции(&) сложения по модулю 2 (⊕) и константы 1. Покажем, как известные функции набора 1) представить в виде декомпозиции функцийЖегалкина:  A = A ⊕ 1; A ∨ B =  ( A B) = (A ⊕ 1)(B ⊕ 1) ⊕ 1 == AB ⊕ A ⊕ B ⊕ 1 ⊕ 1 = AB ⊕ A ⊕ B.Поэтому следующим функционально полным (базисным) наборомбудет набор функций Жегалкина:4) {&, ⊕ , 1 }.Аналогично можно показать, что набор5) {∨, ⊕ , 1} – базисный набор.Выше было показано, что мажоритарная функция M(X, Y, Z) == XY ∨ XZ ∨ YZ.

Если на один из входов, например Z, подать константу1, то получим M(X, Y, 1) = XY ∨ X ∨ Y = X ∨ Y , а если на этот же вход Zподать константу 0, то получим M(X, Y, 0) = XY. Поэтому получаем ещедва базисных набора:6) {M, , 1};7) {M, , 0}.Когда говорят о “мажоритарном базисе” , то имеют в виду эти дванабора (или их объединение: {M, , 1, 0}), предполагая, что 1 и 0 реализуются “без затрат”, а инверсия аргументов всегда присутствует, есликомбинационная схема подключается к триггерным устройствам (элементарным автоматам), которые имеют как прямой, так и инверсныевыходы.На практике, как правило, используются базисные наборы, состоящие только из одной функции (“штрих Шеффера” или “стрелка Пирса”):8) {/};9) {↓}.Набор 8) реализует функцию  (XY) = XY . Инверсия аргумента может быть получена так:  X =  (XX).

Конъюнкция XY =  ( (XY) == X Y = X Y X Y . Дизъюнкция может быть реализована так: X ∨ Y ==  ( XY) = X Y = X X Y Y .15Набор 9) реализует функцию  (X ∨ Y) = X ∨ Y . Инверсия аргументаможет быть получена так:  (X ∨ X). Дизъюнкция может быть получена так: X ∨ Y =  ( (X ∨ Y)). Конъюнкция может быть получена так:XY = ( X∨ Y).П р и м е р .

Перевести в базис Шеффера и Пирса функцию, заданную в дизъюнктивной форме:F = A B ∨ A CD ∨ B D.В базисе Шеффера функция будет иметь видF = A B AC D B DВ базисе Пирса функция будет иметь видF = A∨ B ∨ A∨ C ∨ D ∨ B ∨ DПримеры для самостоятельной работы.Представить в базисах Шеффера и Пирса следующие функции (принеобходимости предварительно упростить):а) ABC ∨ BD ∨= AC ∨ ACDб) XZ ∨ ZY ∨ ZP =;.1.9. Примеры реализации комбинационных схемРедко задание на проектирование комбинационных схем формулируется в виде перечисления входных и соответствующих им выходныхнаборов (таблиц истинности).

Часто оно задается в виде описания работы.П р и м е р 1. Построить однотактное устройство, реализующее следующий алгоритм работы.На вход устройства подается 5-разрядный двоичный код (x1, x2, x3,x4, x5).На выходе вырабатывается 0, если число единиц в коде равно 0или 1, и вырабатывается 1, если число единиц равно 4 или 5. Остальные случаи не предусмотрены (на остальных наборах можно проставить “–”).Построим диаграмму Вейча по данному описанию.16x3x2x1––1––––0–111–1––––1––––00–––0–00x5x4Выпишем решение при очевидном способе доопределения и представим его в базисе Шеффера и Пирса:F = x2 x3 ∨ x4 x5 = x2 x3 x4 x5 = x2 ∨ x3 ∨ x4 ∨ x5 .Комбинационные схемы на несколько выходов строятся аналогичным образом. Однако предпринимаются попытки провести совместнуюминимизацию схем, реализующих отдельные выходные сигналы.

Примерами таких схем могут служить различные преобразователи кодов.П р и м е р 2. Построить однотактное устройство, преобразующеедвоичный код в код Грэя.Выпишем таблицу истинности четырех разрядов кода Грэя.x40000000011111111x30000111100001111x20011001100110011x10101010101010101y40000000011111111y30000111111110000y20011110000111100y1011001100110011017Число диаграмм Вейча равно четырем, причем для y4 она тривиальная (y4 = x4), а для остальных имеет следующий вид.Для y1x4x311111111y1 = x1 x2 ∨ x1 x2 = x1 ⊕ x2 .x2x1Для y2x4x311111111y2 = x2 x3 x2 ∨ x3 = x2 ⊕ x3 .x2x1Для y3x4x311111111y3 = x3 x4 ∨ x3 x4 = x3 ⊕ x4.x2x11.10.

Изображение комбинационных элементовна функциональных схемахДля изображения комбинационных элементов в различных базисахиспользуются следующие обозначения.18Изображение элемента “И”&Изображение элемента “ИЛИ”1Изображение элемента “И-НЕ” (Шеффера)&Изображение элемента “ИЛИ-НЕ” (Пирса)1Изображение элемента “НЕ”Изображение элемента “⊕” (сумма по модулю 2)⊕Упражнение. Нарисуйте функциональные схемы двух устройств вразличных базисах, которые были синтезированы в подразд.

1.9.192. БУЛЕВЫ ПРЕОБРАЗОВАНИЯДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ2.1. Постановка задачиПусть имеются две двоичные последовательности A(a1, a2, …, an) иB(b1, b2, …, bn). При этом ai, bi ∈ {0, 1}, i = 1, 2, 3, …, n. Элементыпоследовательности B будем получать булевым преобразованием последовательности A, при этом bi будет результатом булевого преобразования, зависящего от ai и некоторых элементов из окружения ai. Максимальное число аргументов булевой преобразующей функции F равноN = 2n – 1. Так, для n = 3 N = 5; для n = 4 N = 7; для n = 5 N = 9.Рассмотрим методы нахождения функций F.2.2.

Теорема о преобразованияхдвоичных последовательностейСформулируем теорему, на основании которой можно строить булевы функции, преобразующиe одну последовательность в другую. Этатеорема являeтся аналогом теоремы, доказанной в литературе1.Теорема. Для того чтобы существовала булева функция F, преобразующая произвольную последовательность А в произвольную последовательность В, необходимо и достаточно, чтобы А была ненулевой последовательностью. Число аргументов F не превышает 2n – 1.Необходимость следует из того, что при нулевой последовательности А все элементы последовательности В будут либо нулями, либо единицами, и в этом случае В не может быть произвольной последовательностью.Для доказательства достаточности построим часть таблицы истинности функции F, в которой функция определена:1Åðîø È. Ë., Èãíàòüåâ Ì.

Á., Ìîñêàëåâ Ý. Ñ. Àäàïòèâíûå ñèñòåìû óïðàâëåíèÿ ïðîìûøëåííûìè ðîáîòàìè: Ó÷åá. ïîñîáèå äëÿ âòóçîâ / ËÈÀÏ. Ë., 1985. 144 ñ.20a1 a2 … anb1a1 a2 … anb2a1 a2 … anb3……………………………………………bna1 a2 … an+1Если хотя бы один элемент последовательности А не равен 0, то всенаборы, на которых функция определена, будут различными, поэтому несуществует ни одной одинаковой пары наборов, на которой функция должна принимать одновременно значение 0 и 1.П р и м е р .

Пусть A (101), B (011). Функция F будет зависеть отаргументов (ai – 2 , ai – 1, ai , ai + 1, ai + 2). Таблица истинности этойфункции (точнее, только та ее часть, на которой функция определена)будет иметь видai – 2ai – 11aiai+11010101aiB+21011Функция пяти аргументов задается на 32 наборах. Однако эта функция задана в примере всего на 3 наборах.

На остальных 29 наборахфункция не определена и ее можно доопределить 229 способами. Диаграмма Вейча этой функции будет иметь видai – 2ai – 1ai––––––0–––––––––––––1––––1––––––ai + 2ai + 1Доопределить и минимизировать данную функцию достаточно просто: F = ai + 2 . Действительно, применив булево преобразование F к A,получим B.21При длинах векторов A и B, равных n, булева функция будет задаваться на n наборах, а на 2(2n-1) – n наборах функция будет не определена.

Доопределение и минимизация булевой функции не однозначны.Определение. Два набора Ai и Aj длины n будем называть связанными сдвигом, если при некотором сдвиге одного набора относительнодругого у этих наборов совпадают позиции всех единиц. Например, A =1 0 0 1 0 1 1 0 0 0 и B = 0 0 1 0 0 1 0 1 1 0 – наборы, связанные сдвигом.Из приведенной выше теоремы сформулируем следствия.Следствие 1. Если Ai, i = 1, 2, 3, …, k – двоичные векторы, не связанные сдвигом, и В – произвольный вектор, то существует одна булевафункция F, преобразующая любой вектор Ai в вектор В, т.

е. B = F(Ai),i = 1, 2, 3, …, k.П р и м е р 1. Пусть A1 = 1011; A2 = 1001; A3 = 0110; B = 0111.Построим часть таблицы истинности функПример 1 ции F, выписывая только те наборы, на которых функция определена, при этом для удобa b c d e g h Fства введем очевидные переобозначения1 0 1 1 0аргументов.1 0 1 11Упражнение. Постройте диаграмму Вейча функции F и убедитесь в том, что при не1 0 1 11котором способе доопределения функция1 0 1 11будет иметь вид1 0 0 1 0F=a∨c∨e g.Проверьте, что эта функция из любой при1веденной последовательности Ai (i = 1, 2, 3)1строит одну и ту же последовательность В.1 0 0Следствие 2.