Вариант 6

Ссылки сюда (1) →

Синтез логических устройств для реализации симметрических булевых функций

Введение

При проектировании вычислительных устройств возникает задача реализации на одном логическом устройстве всех булевых функций,принадлежащих определенному классу. В качестве такого класса часто используется класс симметрических булевых функций или некоторые его подклассы. Интерес к симметрическим булевым функциям объясняется тем, что такими булевыми функциями описываются структура и поведение многих типовых устройств вычислительной техники [1]. К настоящему времени имеется довольно-таки много результатов в области синтеза устройств для вычисления произвольных симметрических булевых функций [2, 3], а также для вычисления фундаментальных [4] и полиномиально-однородных [5] симметрических булевых функций.

Основные понятия теории булевых функций

Среди функций одной переменной наибольший интерес представляет функция – отрицание (инверсия) переменной. Такая функция называется элементарной булевой функцией одной переменной. Кроме функции к числу элементарных относится 7 булевых функций, зависящих от двух переменных и  :

• функция называется конъюнкцией (или логическим умножением);
• функция называется сложение по модулю два;
• функция называется дизъюнкцией (или логическим сложением);
• функция называется стрелкой Пирса (или функцией Вебба);
• функция называется эквивалентностью;
• функция называется импликацией ( посылка (основание), заключение (следствие));
• функция называется штрих Шеффера.

Таблица истинности элементарных булевых функций двух переменных

x1	x2	F1	F2	F3	F4	F5	F6	F7
0	0	0	0	0	1	1	1	1
0	1	0	1	1	0	0	1	1
1	0	0	1	1	0	0	0	1
1	1	1	0	1	0	1	1	0

Определение логической формулы

1. Булева переменная является формулой.
2. Если и - формулы, то конструкции , , , , , , - также формулы.
3. Других формул, кроме формул, перечисленных в п. 1 и п.2, нет.

Заключение

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