Рассмотрим теорему Жегалкина, которая играет важную роль в алгебре логики. Теорема Жегалкина. Любая булева функция может быть представлена многочленом вида
f(x1,x2,...,xn)=k0k1x1
k2x2
...
kn+1x1x2
kn+2x1x3
...
kn+mx1x2xn
где к - коэффициенты, принимающие значения 0 или 1.
Теорема Жегалкина даёт возможность представить любую логическую функцию в виде полиномов разной степени.
Существует несколько классов ФАЛ, которые также важны для логического анализа.
Класс линейных функций (Кл). Булева функция называется линейной, если она представляется полиномом первой степени:
f(x1,x2,...,xn)=k0
k1x1
k2x2
...
knxn
Количество линейных функций равно 2^ (n+1). Например, для n = 2 количество линейных функций равно восьми,т. е.
1) f1(x1,x2)=0;
2) f2(x1,x2)=x1;
3) f3(x1,x2)=x2;
4) f4(x1,x2)=x1 x2
5) f5(x1,x2)=1 x
6) f6(x1,x2)=1 x2
7) f7(x1,x2)=1 x1
x2
8) f4(x1,x2)=1
Класс функций, сохраняющих нуль (К нуль). Если функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет нуль:
f(0,0,...,0)=0
Для двух переменных (таблица 11) такими функциями являются f1, f2, f3, f4, f5, f6, f7, f8.
Функция | 00x1x2 | 01 | 10 | 11 | Классы | ||||
Kл | К0 | К1 | КМ | КС | |||||
f1 | 0 | 0 | 0 | 0 | v | v | v | ||
f2 | 0 | 0 | 0 | 1 | v | v | v | ||
f3 | 0 | 0 | 1 | 0 | v | ||||
f4 | 0 | 0 | 1 | 1 | v | v | v | v | v |
f5 | 0 | 1 | 0 | 0 | v | ||||
f6 | 0 | 1 | 0 | 1 | v | v | v | v | |
f7 | 0 | 1 | 1 | 0 | v | v | |||
f8 | 0 | 1 | 1 | 1 | - | v | v | v | |
f9 | 1 | 0 | 0 | 0 | - | - | - | - | |
f10 | 1 | 0 | 0 | 1 | v | v | |||
f11 | 1 | 0 | 1 | 0 | v | v | |||
f12 | 1 | 0 | 1 | 1 | v | ||||
f13 | 1 | 1 | 0 | 0 | v | v | |||
f14 | 1 | 1 | 0 | 1 | v | ||||
f15 | 1 | 1 | 1 | 0 | - | - | - | - | - |
f16 | 1 | 1 | 1 | 1 | v | v |
Класс функций, сохраняющих единицу (К единица). Если функция на единичном наборе переменных равна единице, то говорят, что такая функция сохраняет единицу: f(1,1,...,1)=1.
Для двух переменных такими функциями являются f2,f4,f6,f8,f10,f12,f14,f16.
Класс монотонных функций (К м). Функция алгебры логики называется монотонной, если при любом возрастании набора значения этой функции не убывают. Примером таких функций для двух переменных являются функции f1,f2,f4,f6,f8,f14
Класс самодвойственных функций(К с). Функция алгебры логики является самодвойственной, если на каждой паре противоположных наборов она принимает противоположные значения, т. е.
f(x1,x2,...,xn)=f┐(┐x1,┐x2,...,┐xn))
Для двух переменных такими функциями являются f4,f6,f11,f13. Все названные выше классы функций обладают замечательным свойством: любая функций алгебры логики, полученная с помощью операции суперпозиции и подстановки из функций одного класса, обязательно будет принадлежать этому же классу.
Базисом называется полная система ФАЛ, с помощью которой любая ФАЛ может быть представлена суперпозицией исходных функций.
Теорема Поста-Яблонского. Для того чтобы система ФАЛ была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию:
не сохраняющую нуль,
не сохраняющую единицу,
не являющуюся линейной,
не являющуюся монотонной,
не являющуюся самодвойственной.
В таблице представлены свойства функции двух переменных.
К базису относится система функций И, ИЛИ, НЕ (базис 1), свойства которых были изучены Дж. Булем. Поэтому алгебра высказываний, построенная на основе этих функций, названа булевой алгеброй. Базисами являются также системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (базис 3), состоящие из функции Шеффера (базис 4) и функции Пирса (Вебба) (базис 5). Это перечисление показывает, что базисы могут быть избыточными (базис 1) и минимальными (базис 4 и 5).
Базис минимальный, если удаление хотя бы одной функции превращает систему ФАЛ в неполную.
Проблема простейшего представления логических функций сводится к выбору не только базиса, но и формы наиболее экономного представления этих функций.
Базис И, ИЛИ, НЕ является избыточной системой, так как возможно удаление из него некоторых функций. Например, используя законы де Моргана, можно удалить либо функцию И, заменив её на функции ИЛИ и НЕ, либо функцию ИЛИ, заменяв её на функции И и НЕ.
Построение логических схем
Техническая реализация логических функций может быть различна, но существует единая система графического представления логических функциональных элементов. Каждый элемент представляет собой прямоугольник со входами и одним выходом, инверсные входы и выходы соответствуют незакрашенным кружочкам. Сам элемент обозначается:
единицей, если он реализует логическое сложение;
знаком конъюнкции &? Если реализует логическое умножение;
знаком отрицания -, если реализует логическое отрицание;
mod, если соответствует сложению по модулю 2;
=, если реализует функцию эквивалентности.
На рисунке представлен набор логических элементов
Для построения схемы в заданном базисе логическая функция в начале минимизируется и преобразуется к виду, удобному для реализации на логических элементах заданного типа.
В качестве примера составим логическую цепь в базисе Шеффера для функции, заданной следующей таблицей истинности:
x1 | x2 | x3 | F |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Пользуясь таблицей истинности, запишем логическую функцию в виде СНДФ:
F=┐x1x2x3+x1x2┐x3+x1x2x3+┐x1x2x3
Упрощая эту функцию с помощью диаграммы Вейча, найдём минимизированное выражение:
F=x1x2+x1x3+x2x3
Для построения логической цепи на элементах Шеффера преобразуем функцию к виду
F=┐(┐(x1x2)+┐(x1x3)+┐(x2x3))
F=(x1 | x2) | (x1 | x3 ) | (x2 | x3 )
Из последнего выражения видно, что для построения логической схемы в данном случае потребуется три двухвходовых и один трёхвходовый элемент Шеффера.
![]() |
Практические задания |
![]() |
Tест для самоконтроля |