Системы функций алгебры логики

 

Рассмотрим теорему Жегалкина, которая играет важную роль в алгебре логики.

Теорема Жегалкина. Любая булева функция может быть представлена многочленом вида

f (x 1, х 2,..., хn) = k 0 k 1 x 1 k 2 x 2…  kn +1 x 1 x 2 kn +2 x 1 x 3…  kn + mx 1 x 2 xn,

 

где ki – коэффициенты, принимающие значения 0 или 1.

Теорема Жегалкина дает возможность представить любую логическую функцию в виде полиномов разной степени.

Существует несколько классов ФАЛ, которые также важны для логического анализа.

Класс линейных функций (Кл). Булева функция называется линейной, если она представляется полиномом первой степени:

 

Количество линейных функций равно 2 n +l. Например, для n = 2 количество линейных функции равно восьми, т. е.

1); 2); 3);

4); 5); 6);

7); 8).

Класс функций, сохраняющих нуль (K0). Если функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет нуль:

f (0,0,...,0) = 0.

Для двух переменных (табл. 1.15) такими функциями являются f 1, f 2, f 3, f 4, f 5, f 6, f 7, f 8.

 

Таблица 1.15

Класс функций, сохраняющих единицу (K1). Если функция на единичном наборе переменных равна единице, то говорят, что такая функция сохраняет единицу: f (1,1,..., 1) =1. Для двух переменных такими функциями являются f 2, f 4, f 6, f 8, f 10, f 12, f 14, f 16(см. табл. 1.15).

 

Класс монотонных функций (Км). Функция алгебры логики называется монотонной, если при любом возрастании набора значения этой функции не убывают. Примером таких функций для двух переменных являются функции f 1, f 2, f 4, f 6, f 8, f 14(см. табл. 1.15).

 

Класс самодвойственных функций (Кс). Функция алгебры логики является самодвойственной, если на каждой паре противоположных наборов она принимает противоположные значения, т. е.

 

Для двух переменных такими функциями являются f 4, f 6, f 11, f 13.

Все названные выше классы функций обладают замечательным свойством: любая функция алгебры логики, полученная с помощью операции суперпозиции и подстановки из функций одного класса, обязательно будет принадлежать этому же классу.

Базисом называется полная система ФАЛ, с помощью которой любая ФАЛ может быть представлена суперпозицией исходных функций.

 

Теорема Поста-Яблонского. Для того чтобы система ФАЛ была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию:

не сохраняющую нуль,

не сохраняющую единицу,

не являющуюся линейной,

не являющуюся монотонной,

не являющуюся самодвойственной.

 

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

К базису относится система функций И, ИЛИ, НЕ (базис 1), свойства которых были изучены Дж. Булем. Поэтому алгебра высказываний, построенная на основе этих функций, названа булевой алгеброй. Базисами являются также системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (базис 3), состоящие из функции Шеффера (базис 4) и функции Пирса (Вебба) (базис 5). Это перечисление показывает, что базисы могут быть избыточными (базис 1) и минимальными (базисы 4 и 5).

Базис минимальный, если удаление хотя бы одной функции превращает систему ФАЛ в неполную.

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

Базис И, ИЛИ, НЕ является избыточной системой, так как возможно удаление из него некоторых функций. Например, используя законы де Моргана, можно удалить либо функцию И, заменив ее на функции ИЛИ и НЕ, либо функцию ИЛИ, заменяв ее на функции И и НЕ.

 

Построение логических схем

 

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

· единицей, если он реализует логическое сложение;

· знаком конъюнкции &, если реализует логическое умножение;

· знаком отрицания -, если реализует логическое отрицание;

· mod, если соответствует сложению по модулю 2;

·, если реализует функцию эквивалентности.

На рис. 2 представлен набор логических элементов.

Рис. 2. Логические элементы

 

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

В качестве примера составим логическую цепь в базисе Шеффера для функции, заданной следующей таблицей истинности (табл. 1.16):

 

Таблица 1.16

Пользуясь таблицей истинности, запишем логическую функцию в виде СНДФ:

 

 

Упрощая эту функцию с помощью диаграммы Вейча (рис. 3), найдем минимизированное выражение:

 

 

Рис. 3. Диаграмма Вейча для заданной функции

 

Для построения логической цепи на элементах Шеффера преобразуем функцию к виду

 

 

F =(х 1| x 2) | (х 1| x 3) | (х 2| x 3).

 

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

Рис. 4. Схема, реализующая заданную функцию