Вариант 6 — различия между версиями
Korobko (обсуждение | вклад) |
Korobko (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
|} | |} | ||
<br /> | <br /> | ||
| − | '''Определение логической формулы''' | + | '''Определение логической формулы:''' |
# Булева переменная <m>x</m> является формулой. | # Булева переменная <m>x</m> является формулой. | ||
| − | # Если <m> | + | # Если <m>A</m> и <m>B</m> - формулы, то конструкции <m>¬A</m>, <m>(AB)</m>, <m>(A \lor B)</m>, <m>(A \rightarrow B)</m> , <m>(A \sim B)</m> , <m>(A \downarrow B)</m> , <m>(A \setminus B)</m> - также формулы. |
| − | # Других формул, кроме формул, перечисленных в п. 1 и п.2, нет. | + | # Других формул, кроме формул, перечисленных в п.1 и п.2, нет. |
Версия 21:18, 22 ноября 2013
Содержание |
Синтез логических устройств для реализации симметрических булевых функций
Введение
При проектировании вычислительных устройств возникает задача реализации на одном логическом устройстве всех булевых функций,принадлежащих определенному классу. В качестве такого класса часто используется класс симметрических булевых функций или некоторые его подклассы. Интерес к симметрическим булевым функциям объясняется тем, что такими булевыми функциями описываются структура и поведение многих типовых устройств вычислительной техники [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, нет.
Заключение
Синтезированы устройства для вычисления самодвойственных симметрических булевых функции трех, пяти и семи переменных.
