1) ; 2); 3);

4) ; 5);

Можно ли из соответствующих систем функций получить следующие функции , и если “да”, то напишите определяющее выражение:

6) из системы функций получить функцию ;

7) из системы функций

получить функцию 0 ;

8) из системы функций получить функции ;

9) из системы функций

получить функции

;

10) из системы функций получить функции ;

Предполные классы булевых функций

Определение:

Предполным классом К называется неполный класс, при добавлении любой функции, которая не принадлежит ему, получается класс полный.

Утверждение:

Предполный класс является замкнутым.

Доказательство: Допустим противное, что некоторый предполный класс К не замкнут: , тогда рассмотрим функцию

т.е. [ K,f ] не полный

Теорема:

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

Доказательство :

В начале покажем, что данные классы являются предполными, а затем покажем, что других предполных классов нет.

1. Рассмотрим .

Данный класс содержит функции:

поэтому класс Т₀ не принадлехит классам Т₁, S, М, L.

Рассмотрим произвольную , тогдане принадлежит ни одному из пяти классов Поста, следовательно по теореме Поста является полной, следовательно классявляется предполным.

2) Рассмотрим Т₁:

Рассмотрим произвольную не принадлежит ни одному из пяти классов, следовательно по теореме Поста является полной, следовательнопредполный.

3) Рассмотрим S:

Рассмотрим не принадлежит ни одному из пяти классов Поста, следовательно по теореме Поста является полной, следовательнопредполный .

4) Рассмотрим :

Рассмотрим не принадлежит ни одному из пяти классов, следовательно по теореме Поста система полна, следовательнопредполный.

5) Рассмотрим L:

Рассмотрим не принадлежит ни одному из пяти классов, следовательно по теореме Поста система полна, следовательнопредполная. Все перечисленные классы не полны по теореме Поста.

Покажем, что других предполных классов в нет.

Допустим противное, что - предполный :

, следовательно в данном классе :

РИС.1

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

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

Упражнения:

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

1)

2)

3)

4)

5)

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

Определение:

Полной системой бул. функций в замкнутом классе К является система функций, которая принадлежит данному классу, и замыкание которой совпадает с самим классом

.

Определение:

Базисом в замкнутом классе К называют систему В, которая полна в этом классе, но любая собственная подсистема полной в классе не является.

Пример 1: Рассмотрим множество всех булевых функций Р₂. В этом множестве рассмотрим систему .Эта система полна по т. Поста .

Чтобы определить,что все собственные подсистемы не полны, достаточно рассмотреть лишь максимальные по включению собственные подсистемы данной, получаемые из данной удалением какой-либо функции.

Если ни одна из этих подсистем не является полной, то полной не является и любая другая собственная подсистема (докажите предыдущие утвеждения)

В данном примере максимальные собственные подсистемы не полны, значит является базисом вР₂.

Пример 2: Является ли система базисом вР₂?

, поэтому система полна, но собственная подсистематакже полна, поэтому данная система не базис вР₂.

Определение:

Скажем, что функция f не зависима от системы , если эта функция не принадлежит замыканию системы :.

Пример 1: Рассмотрим функцию и систему:

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

Пример 2: Рассмотрим функцию и систему:

x₁ x₂

0 0 1 0 0

0 1 1 1 1

1 0 0 1 1

1 1 1 1 1

Значит, зависима от функции.

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

Утверждение:

Если система функций базис в замкнутом классе К , то тогда каждая функция базиса независима от оставшихся.

Доказательство:

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

Пример 1:

базис в Р₂

Упражнение: Докажите справедливость обратного утверждения: пусть полная система в К, и любая функция системы не зависит от оставшихся, тогда система – базис в К.