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

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

Теорема Жегалкина. Любая булева функция может быть представлена многочленом вида , где – коэффициент, принимающий значения 0 или 1.

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

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

.

Количество линейных функций равно .

Например, при n=2 количество линейных функций равно 8.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Класс функций, сохраняющих 0 ( ).

Если функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет ноль:

.

Класс функций, сохраняющих 1 ( ).

Если функция на единичном наборе переменных равна 1, то говорят, что функция сохраняет единицу:

.

Класс монотонных функций ( ).

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

Класс самодвойственных функций ( ).

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

.

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

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

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

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

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

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

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

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

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

Перечень базисов.

1. - базис Пирса (элемент Вебба);

2. - базис Шеффера;

3. - коипликация, эквиваленция;

4. - импликативный базис;

5. - импликация, коимпликация;

6. - импликация, сложение по модулю 2;

7. - коимпликативный базис;

8. - импликативный базис;

9. - конъюнктивный базис Буля;

10. - дизъюнктивный базис Буля;

11. - коимпликативный базис (коимпликация, константа 1);

12. - эквиваленция, конъюнкция, константа 0;

13. - эквиваленция, дизъюнкция, константа 0;

14. - сложение по модулю 2, конъюнкция, эквиваленция;

15. - сложение по модулю 2, дизъюнкция, эквиваленция;

16. - базис Жегалкина;

17. - сложение по модулю 2, дизъюнкция, константа 1.

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

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

Если сравнить в смысле минимальности различные формы представлений ФАЛ, то станет ясно, что нормальные формы экономичнее совершенных нормальных форм, но с другой стороны, нормальные формы не дают однозначного представления.

Минимальная (тупиковая) форма представления ФАЛ содержит минимальное количество термов и переменных в термах , дальнейшие упрощения минимальной формы не возможны.

Дисциплина «Методы логического проектирования»рассматривает теоретические аспекты минимизации логических функций. Методов минимизации несколько. Перечислим основные: Метод неопределённых коэффициентов для базиса И- ИЛИ - НЕ, метод Квайна, метод минимизирующих карт и т.д. Подробно каждый из методов рассмотрен в пособии А.Я. Савельева «Основы информатики».

Упрощение сложных логических выражений может быть осуществлено по основным законам и аксиомам, изложенным выше.

Пример.

Пусть задана логическая функция с помощью таблицы истинности:F(a,b,c) = A9₁₆.

Представить её в базисе Жегалкина, используя не более 4 - х элементов.

Решение.

A	B	c	F
0	0	0	1	*
0	0	1	0
0	1	0	1	*
0	1	1	0
1	0	0	1	*
1	0	1	0
1	1	0	0
1	1	1	1	*

Построим СДНФ для заданной функции.

Так как задан базис Жегалкина, целесообразно элементарные минтермы соединить операцией сложение по модулю 2.

СДНФ: ¬a ¬b ¬c ⊕ ¬ab ¬c ⊕ a ¬b ¬c ⊕ abc.

Упростим полученную формулу:

¬a ¬b ¬c ⊕ ¬ab ¬c ⊕ a ¬b ¬c ⊕ abc = ¬a ¬c(¬b ⊕ b) ⊕ a (¬b ¬c ⊕ bc) = ¬a ¬c ⊕ a(b~c) = ¬a ¬c ⊕ a(b ⊕ ¬c) = ¬a ¬c ⊕ ab ⊕ a ¬c = ¬c(¬a⊕ a) ⊕ ab = ¬c ⊕ ab =

c ⊕ ab⊕1.