Вопросы и упражнения для самостоятельной работы

Проверить принадлежность каждому из классов P₀,P₁,S,L,Mследующих функций:a), б), в).

Найти все булевы функции двух переменных, принадлежащие а) классу M, б) классуS.

Принадлежит ли классу Lфункция а)xy, б)xy, в)xy.

Построить булеву функцию, не принадлежащую ни одному из классов P₀,P₁,S,L,M.

Монотонны ли следующие функции:

а) xyz, б)x(yz), в)x’y(xy’z).

Найти линейную булеву функцию f(x,y), удовлетворяющую условиям:

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

б) f(1,0)=0,f(0,1)=1 иf(1,1)=1.

Найти линейную булеву функцию f(x,y,z), удовлетворяющую условиям:

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

б) f(0,0,1)=0,f(0,1,0)=1,f(1,1,1)=1 иf(1,1,0)=1.

§1.4. Полные системы. Теорема Поста

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

Теорема (Поста о полноте).Класс функцийKполон тогда и только тогда, когда он не содержится целиком ни в одном из классовP₀, P₁, S, L, M.

Примеры

1. Доказать, полноту системы функций а) {,’}, б) {}.

Решение. а) Система функций {, , ’} полна, поскольку любая функция представима в СДНФ (СКНФ), т.е. выражается через дизъюнкцию, конъюнкцию и отрицание. Выразим дизъюнкцию через конъюнкцию и отрицание:xy=(x’y’)’. Следовательно, любую функцию можно выразить и через конъюнкцию и отрицание, откуда следует полнота.

б) Выберем какую-либо полную систему функций, например, из предыдущего пункта {,’}. Выразим входящие в систему функции через стрелку Пирса:

x’=xx,xy=x’y’=(xx)(yy).

Здесь мы использовали формулы (1) – (2) из §5.1.

2. Доказать, что система функций {,} не полна, а система {,, 1} – полна.

Решение.Составим таблицу принадлежности функций к классамP₀,P₁,S,L,M(«+» означает принадлежность, «–» - нет):

φk	P0	P1	S	L	M
	+	+	–	–	+
	+	–	–	+	–
1	–	+	–	+	+

Первые две строки соответствуют системе {,}. Согласно теореме Поста, полная система функций не должна содержаться целиком ни в одном классе, но функциииобе содержатся в классеP₀. Следовательно, система функций {,} неполна.

При рассмотрении всех строк (система {,,1}), обнаруживаем, что каждый столбец содержит хотя бы один минус, следовательно, данная система полна.

3. Записать функциюf =xy, используя стрелку Пирса.

Решение.Разложим функциюfпо системе {, ’}, а затем по системе {}, используя (1), (2) :

{, ’}:f= xy=(x’y’)’

{}:f=((xx)(yy))’=((xx)(yy))((xx)(yy))=

={[(xx)(xx)][(yy)(yy)]}{[(xx)(xx)][(yy)(yy)].

4. Представить штрих Шеффера в виде полинома Жегалкина.

Решение.Требуется разложить функциюf =xyпо системе функций {,,1}. Разложим функциюfпо системе {, ’}, затем по системе {,,1}, используя (1),(3):

{, ’}:f= xy=x’y’=(xy)’,

{,,1}:f=1xy.

Вопросы и упражнения для самостоятельной работы

Доказать полноту следующих систем функций двумя способами (исходя из определения и используя теорему Поста)

а) {}; б) {1,}; в) {,’}.

Проверить полноту системы функций

а) {0, }; б) {0,}; в) {,}; г) {,1,}.

Доказать, что существует ровно две полные системы функций двух переменных, каждая из которых состоит из одной функции.

Разложить функции fиgпо указанной системе функций:

а) f=(x’y)z,g=(xy’)z’ по {, ‘};

б) f=xy’,g=(x’y)zпо {,,1};

в) f=xy,g=x’yпо {1,}.

Записать функцию , используя штрих Шеффера:

а) f=xy; б)f=xy; в)f=xy’z.

19