Булева алгебра (1023551), страница 3
Текст из файла (страница 3)
или у = ^ (0, 1, 2) (6)
Для любой ФАЛ СДНФ и СКНФ единственны.
Так как в СДНФ и СКНФ можно представить любую ФАЛ, а в выражениях (1) и (4) используются три логические операции И, ИЛИ и НЕ, то говорят, что набор этих операций образует функционально полную систему (ФПС), позволяющую реализовать произвольные ФАЛ. Совокупность И, ИЛИ и НЕ называют основной функционально полной системой (ОФПС).
Если к выражению (1) применить закон двойного отрицания и правило де-Моргана, то получим следующее выражение:
(7)
из которого видно, что для представления любой ФАЛ достаточно использовать только две операции И и НЕ, которые также являются ФПС.
Если к выражению (4) применить закон двойного отрицания и правило де-Моргана, то получим следующее выражение:
(8)
из которого видно, что для представления любой ФАЛ достаточно использовать только две операции ИЛИ и НЕ, которые также являются ФПС.
Карта Карно является специальной компактной формой таблицы истинности, которая позволяет не только представить ФАЛ, но и минимизировать ее. На рис. 1 показана карта Карно для ФАЛ, заданной табл. 1.
Р
ис. 1. Карты Карно: а) – эталонная, б) – рабочая
Переключательная схема может рассматриваться как техническая модель логических выражений. Одну из первых моделей предложил в 1910 году физик П.С.Эренфест, в которой использована аналогия между высказываниями и электрическими переключателями, поскольку и те и другие имеют двоичную природу. На рис. 2 приведены модели для констант 0 и 1 и базовых функций И, ИЛИ, НЕ.
Положение переключателей, указанное на рис. 2, соответствует нулевому значению переменной. Переключательная схема для ФАЛ, заданной табл. 1, приведена на рис. 3 в минимизированном варианте.
Диаграммы Венна, названные по имени священника Джона Венна (1834 - 1923), применявшего их в исследованиях по логике, являются графическим представлением, демонстрирующим соотношения между множествами. На основе соответствия между теорией булевой алгебры и теорией множеств диаграммы Венна очень полезны для визуального представления аксиом и законов булевой алгебры, однако, их не следует использовать для построения доказательств тождеств, поскольку большинство общих положений эти диаграммы показать не могут.
На рис. 4 приведены диаграммы Венна для констант 0, 1 и базовых функций И, ИЛИ, НЕ, где область, ограниченная кружком соответствует одной переменной.
Рис. 2. Переключательные модели констант 0 и 1
и функций И, ИЛИ, НЕ
Р
ис. 3. Переключательная модель ФАЛ, заданной табл. 1
Р
ис. 4. Диаграммы Венна
Н
а рис. 5 приведена диаграмма Венна для ФАЛ, заданной табл.1. Диаграммы Венна удобны только для n <= 3.
Рис. 5. Диаграмма Венна для y= x2 + x1 x0
Геометрическое представление булевой функции получается путем отображения булевой функции n переменных на n-мерный куб.
Для отображения булевой функции n переменных на n-кубе устанавливается соответствие между членами СДНФ и вершинами n-куба. Вершины (наборы), на которых функция принимает единичное значение, выделяются жирными точками. На рис. 6 представлена в виде куба ФАЛ, заданная табл. 1.
Г
еометрическое представление удобно только для n ≤ 3. Для n = 4 геометрическое представление уже довольно сложное, поэтому для n ≥ 4 используют аналитическое представление n-кубов.
Рис. 6. Геометрическое представление для y= x2 + x1 x0
Д
иаграмма двоичного решения (ДДР) является разновидностью корневого ориентированного графа, обеспечивающая полное, краткое и простое описание сложных цифровых функций. На рис. 7 приведена ДДР ФАЛ, представленной табл. 1.
Рис. 7. Диаграмма двоичного решения для y= x2 + x1 x0
На рис. 7 прямоугольники с цифрами 0 и 1 соответствуют финишным (окончательным) значениям ФАЛ. Узел, обозначенный кружком, соответствует переменной, от которой зависит ФАЛ, а цифры у ветвей - значениям этих переменных. ДДР широко используются для анализа сложных функций, формирования тестов, задач верификации и т.д.
Прежде чем формулировать свойства различных видов ФАЛ, представим в виде обобщенной таблицы истинности полный набор ФАЛ, зависящих от двух переменных. Обоснованием этого можно рассматривать следующие моменты: общее число таких функций невелико:
Все эти функции находят широкое практическое применение; обращение к таблице позволит на простых примерах осмыслить особенности различных ФАЛ, подсчитать их количество и т. п.
В табл. 2 индекс ‘i’ функции уi совпадает с десятичным эквивалентом двоичного числа, условно составленного из значений функций на четырех наборах. Все 16 функций являются полностью определенными.
Запишем аналитические выражения для всех этих функций (см. табл. 3) в СДНФ для случая, когда число единичных значений функции меньше или равно двум (то есть половине числа всех наборов) и в СКНФ, если функция имеет один нуль, с последующей минимизацией с использованием правила склеивания.
Таблица 2
| № | x1 | x0 | y0 | y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | y9 | y10 | y11 | y12 | y13 | y14 | y15 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Из табл. 2 и уравнений табл. 3 следует, что функции y0 и y15 не зависят ни от одной переменной и являются константами; y3, y5, y10 и y12 являются функцией только одной переменной. Такие функции, т.е. функции, значение истинности которых не зависит от одной или нескольких переменных, называются вырожденными, а переменные, от которых функция не зависит– фиктивными .
Можно заметить также, что 
, то есть функция yi является обратной по отношению к функции 
и наоборот.
Таблица 3
y0 = 0 – константа 0,
y1 = х0 
х1 = х1•х0 = х1 & х0 = х1 х0 – конъюнкция, функция И – логическое умножение,
y2 = 
– запрет переменной x1,
y3 = 
– повторение переменной x1,
y4 = 
– запрет переменной x0,
y5 = 
– повторение переменной x0,
y6 = 
– сложение по модулю 2,
y7 = 
– дизъюнкция , функция ИЛИ – логическое сложение,
y8 = 
– стрелка Пирса – или‑не,
y9 = х1 
х0 = х1 ~ х0 – эквивалентность (равенство),
y10 = 
– отрицание переменной x0,
y11 = 
= х1→ х0 – импликация (включение) x0 в x1,
y12 = 
– отрицание переменной x1,
y13 = 
= х0→ х1 – импликация x1 в x0,
y14 = 
– штрих Шеффера и‑не
y15 = 1 – константа 1.
Полином Жегалкина
Полином Жегалкина – это одна из форм представления логических функций.
Особенность полинома – для каждой функции он единственный.
Рассмотрим методы построения полинома Жегалкина.
Метод неопределенных коэффициентов
-
Записываем полином в общем виде.
-
Поочередной подстановкой в полином всех 2n наборов, получаем систему 2n уравнений, решаемых по мод 2.
-
Решение системы дает коэффициенты полинома.
Пример. f = х0 → х1 (две переменные n =2)
Решение: Общий вид полинома Жегалкина
f = х0 → х1 = а0 ⊕ а1х0 ⊕ а2х1 ⊕ а3х0х1
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
