Полные системы булевых функций

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

Булевой алгеброй илиалгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.

Система булевых функций { f ₁,   f ₂, …, f_n } называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {Ø, &, Ú} является полной. Также полными являются следующие системы функций: а) {Ø, Ú}; б) {Ø, &}; в) {Ø, É}.

Полнота систем  {Ø, Ú} и {Ø, &} следует из полноты системы {Ø, &, Ú}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A & B ºØ(Ø A Ú Ø B); A Ú B º Ø(Ø A & Ø B). Поэтому система {Ø, &, Ú} может быть сокращена на одну функцию.

Полнота системы {Ø, É} следует из полноты системы  {Ø, Ú} и равносильности, позволяющей выразить импликацию через отрицание и дизъюнкцию: A É B ºØ A Ú B.

Пусть дан класс функций B (т. е. конечное или бесконечное множество функций), объединенных по общему признаку. Замыканием этого класса (обозначение – [B]) будем называть множество всех суперпозиций функций из класса B. Класс B будем называть замкнутым, если его замыкание совпадает с ним самим B = [B].

Рассмотрим классы функций, которые являются замкнутыми.

Класс Т₀ – класс функций, сохраняющих константу 0. f() Î Т₀ Û f(0, …, 0) = 0.

Класс Т₁ – класс функций, сохраняющих константу 1. f() Î Т₁ Û f(1, …, 1) = 1.

Класс S – класс самодвойственных функций. f() Î S Û f() = f*().

Функция называется двойственной к f(), обозначается f*(), т. е. f *() = .

Класс М – класс монотонных функций. f() Î М Û " a, b Î , таких, что a £ b Þ f(a) £ f(b).

На множестве наборов значений переменных  введем отношение порядка £, называемое отношением предшествования (отношением сравнимости), следующим образом: a £ b, если ai £ bi, i = .

Класс L – класс линейных функций.

f() Î L Û f() = – представима полиномом Жегалкина не выше первой степени.

Теорема Поста. Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T₀, T₁.

Пример. Исследовать полноту системы А = {f₁ = x Å y, f₂ = xy Å z, f₃ = x Å y Å z Å 1, f₄ = xy Å yz Å zx }(табл. 4).

Решение. Результаты исследования на принадлежность функций каждому из пяти классов отображены в критериальной таблице (табл. 5).

                                                                        Таблица 5

	Т0	Т1	L	S	M
f1	+	–	+	–	–
f2	+	–	–	–	–
f3	–	–	+	+	–
f4	+	+	–	+	+

а) f₁, f₂, f₄ Î Т₀, т. к. f₁(0, 0) = 0 Å 0 = 0, f₂(0, 0) = 0 Ù 0 Å 0 = 0, f₄(0, 0, 0) = 0 Ù 0 Å 0 Ù 0 Å 0 Ù 0 = 0; f₃ Ï Т₀, т. к. f₃(0, 0, 0) = 0 Å 0 Å 0 Å 1 = 1;

б) f₁, f₂, f₃ÏТ₁, т. к. f₁(1,1) = 1Å1= 0, f₂(1,1) = 1Ù1Å1 = 0, f₃(1, 1,1) = 1 Å 1 Å 1 Å 1 = 0; f₄ ÎТ1, т. к. f₄(1, 1, 1) = 1 Ù 1 Å 1 Ù 1 Å 1 Ù 1 = 1;

в) f₁, f₃ Î L, т. к. f₁ = x Å y, f₃ = x Å y Å z Å 1 – представимы полиномом Жегалкина первой степени; f₂, f₄ Ï L, т. к. f₂ = xy Å z, f₄ = xy Å yz Å zx – представимы полиномом Жегалкина второй степени;

г) f₃, f₄ Î S, т. к. f₃*() = () = (1, 0, 0, 1, 0, 1, 1, 0) = f₃(), f₄*() = () = (0, 0, 0, 1, 0, 1, 1, 1) = f₄();

f₁, f₂ Ï S, т. к. f₁*() =  = (1, 1, 0, 0, 0, 0, 1, 1) ¹ f₁(),

f₂*() = () = (1, 0, 0, 1, 0, 1, 0, 1) ¹ f₂();

д) f₁, f₂, f₃ Ï М, т. к. f₁: (0, 0, 1, 1) (1, 1, 0, 0), f₂: (0, 1, 0, 1) (0, 1, 1, 0), f₃: (1, 0, 0, 1) (0, 1, 1, 0); f₄ Î М, т. к. f₄: (0, 0, 0, 1) ≤ (0, 1, 1, 1); (0, 0) ≤ (0, 1) и (0,1) ≤ (1, 1); 0 ≤ 0 и 0 ≤ 1, и 1 ≤ 1.

Вывод: система функций А является полной, т. к. в каждом из столбцов критериальной таблицы есть хотя бы один «–».

Задания

Для аудиторных занятий

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

а) f = x Ú y ~ х и g = (x ® y) Ù y;       б) f = x (y ® z) и g = x ® (y ç zx).

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

а) f() = (х ₂ ® х ₁)(х ₂ ¯ х ₂); б) f() = (х ₂ ~ х ₁)(х ₁| х ₂);

в) f() = (х ₁ Å х ₂) ® х ₃)×ù(х ₃ ® х ₂); 

г) f() = (х ₁ Ú х ₂ Ú ) ® (х ₁× х ₂| ) Å (х ₂ ® х ₁)× .

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

а) f() = ((х ₂ Ú х ₁) ® х ₁× х ₂ ) Å (х ₁® х ₂) Ù (  х ₂ ® х ₂);

б) f() = (х ₁ ® х ₂ х ₃)× (х ₂  ® х ₁ х ₃) Ú (х ₁ ~ х ₂).

4. Указать все фиктивные переменные у функции f:

а) f() = (1, 0, 1, 0, 1, 0, 1, 0); б) f() = (0, 1, 1, 0, 0, 1, 1, 0);   

в) f() = (1, 1, 1, 1, 0, 1, 1);

г) f() = (1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1);          

д) f() = (0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1).

5. Указать все фиктивные и существенные переменные у функции f:

а) f() = (х ₂ ® х ₁)(х ₂ ¯ х ₂); б) f() = (х ₂ ~ х ₁)(х ₁| х ₂);

в) f() = (х ₁ Å х ₂) ® х ₃)×ù(х ₃ ® х ₂);      

г) f() = (х ₁ Ú х ₂ Ú ) ® (х ₁× х ₂| ) Å (х ₂ ® х ₁)× .

6. Перечислить существенные переменные у следующих функций:

а) f() = ((х ₂ Ú х ₁) ® х ₁× х ₂) Å (х ₁ ® х ₂)(х ₂ ® х ₂);

б) f() = (х ₁ ® х ₂ х ₃)× (х ₂ ® х ₁ х ₃) Ú (х ₁ ~ х ₂).

7. Какие значения принимает булева функция двух переменных для x ₁ Å x ₂?Как называется эта функция?

8. Выяснить, является ли самодвойственной и монотонной функция f:

f = x ₁ x ₂ Ú x ₁ x ₃ Ú x ₃ x ₂.

9. Выяснить, полна ли система функций:

А = { xy, x Ú y, x Å y Å z Å 1}.

Для самостоятельной работы

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

а) f = xy ® х и g = xy ® y; б) f = xy Ù z и g = x ® (y ç zx).

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

а) f() = (х ₂ ~ х ₁)(х ₂ ¯ х ₂);  б) f() = (х ₂ ® х ₁)(х ₁| х ₂);

в) f() = (х ₁ Å х ₂) ® ù х ₃)× (х ₃ ® х ₂); 

г) f() = (х ₁Ú х ₂| ) Å (х ₁× х ₂ Ú ) ® (х ₂ ® х ₁)× .

3. Указать все фиктивные переменные у функции f:

а) f() = (1, 0, 1, 0, 1, 0, 1, 1); б) f() = (0, 1, 0, 0, 0, 1, 1, 0);   

в) f() = (1, 0, 1, 1, 0, 1, 1); г) f() = (1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1); д) f() = (1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0).

4. Указать все фиктивные и существенные переменные у функции f:

а) f() = (х ₂ ~ х ₁)(х ₂ ¯ х ₂);  б) f() = (х ₂ ® х ₁)(х ₁| х ₂);

в) f() = (х ₁ Å х ₂) ® х ₃)×ù(х ₃ ~ х ₂);        

г) f() = (х ₁ ~ х ₂ Ú ) ® (х ₁× х ₂| ) Å (х ₂ ® х ₁)× .

5. Перечислить существенные переменные у следующих функций.

а) f() = ((х ₂ ~ х ₁) ® х ₁× х ₂) Å (х ₁ ® х ₂)(х ₂ ® х ₂);

б) f() = (х ₁ ~ х ₂ х ₃)× (х ₂ ® х ₁х₃) Ú (х ₁ ~ х ₂).

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

а) f() = (х ₂ ® х ₁× х ₂) Ù (х ₁ ® х ₂) Å (х ₂ ® х ₂);

б) f() = (х ₁ ® х ₂ Å х ₃)× (х ₂ ® х ₁ Ú х ₃) Ú (х ₁ ~ х ₂).

7. Какие значения принимает булева функция двух переменных для x ₁ Å x ₂? Как называется эта функция?

8. Выяснить, является ли самодвойственной и монотонной функция f

f = x ₁ ® x ₂ Ú x ₁ x ₂ ~ 1.

9. Выяснить, полна ли система функций:

А = { xy, x Ú y, x Å y, xy Ú yz Ú zx }.

 

Литература

1. Гаврилов, Г. П. Задачи и упражнения по курсу дискретной математики: учеб. пособие / Г. П. Гаврилов, А. А. Сапоженко. – М.: Наука, 1992 – 408 с.

2. Горбатов, В. А. Фундаментальные основы дискретной математики  / В. А. Горбатов. – М.: Наука, 2000. – 544 с.

3. Нефедов, В. Н. Курс дискретной математики: учеб. пособие / В. Н. Нефедов, В. А. Осипова. – М.: Изд-во МАИ, 1992. – 264 с.

4. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.

 

Практическое занятие № 11