Методические указания к практической работе № 5

Определение. Система булевых функций f₁, f₂, …, f_n называется полной, если любая булева функция может быть выражена через функции f₁, f₂, …, f_n с помощью суперпозиций.

Пример.

Исходя из определения полной системы булевых функций, следует, что система {Ù, Ú, Ø } является полной, так как любая булева функция может быть представима в виде СДНФ и/либо СКНФ.

Дадим определение суперпозиции функций.

Определение. - конечная система булевых функций. Функция f называется суперпозицией ранга 1 (или элементарной суперпозицией) функций f₁, f₂, …, f_m, если f может быть получена одним из следующих способов:

1. переименованием некоторой переменной x_j какой-нибудь функции f_i, т. е. f=f_i(x₁, …, x_j-1, y, x_j+1, …, x_k1), где y может совпасть с любой переменной;

2. подстановкой некоторой функции f_l (1£ l m) вместо какой-либо переменной x_j любой из функций fiÎ K⁰, т. е. f=f_i(x₁, …, x_j-1, f_l(x₁, x₂, …, x_k1), x_j+1,..., x_ki).

Определение. Суперпозиции ранга 1 образуют класс функций К¹. Класс функций, получающихся из функций класса К^r-1 суперпозиций ранга r-1 с помощью элементарных суперпозиций, называется классом функций K^r суперпозиций ранга r. Суперпозициями функций из К⁰ называются функции, входящие в какой-либо из классов K^r.

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

Пример.

1. Четыре булевы функции одной переменной (f₁ = 00, f₂ = 11, f₃ = 01, f₄ = 10) образуют замкнутый класс.

2. Булевы функции f₁ = x и образуют замкнутый класс.

Теорема. Класс T₀={f | f(0, 0, …, 0)=0} функций, сохраняющих константу ноль на нулевом наборе, замкнут относительно суперпозиций.

Теорема. Класс T₁ ={ f | f(1, 1, …, 1)=1} функций, сохраняющих константу один на единичном наборе замкнут относительно суперпозиций.

Определение. Двойственной для функции f(x₁, x₂, …, x_n) называется функция

Пример.

Построить функцию, двойственную данной:

1. f = x Ú y;

2. f = x® y.

Решение.

1.

2.

Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.

Утверждение. Если функция f(x₁, x₂, …, x_n) самодвойственна, то функция тоже самодвойственна.

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

Определение. Противоположными называются те наборы, которые в сумме дают двоичный код числа (2ⁿ-1).

Пример.

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

1. ;

2. f = 01110010.

Решение.

1. Строим таблицу истинности для данной функции :

№	x	y	z
0
1
2
3
4
5
6
7

Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.

2. Строим таблицу значений для функции f = 01110001.

Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.

Теорема. Класс S = {f | f = f*} самодвойственных функций замкнут относительно суперпозиций.

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Функция f(x₁, x₂, …, x_n) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x₁, x₂, …, x_n) = a₁x₁ + … + a_nx_n + a_n+1, где каждое a_i равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = {f | f = a₀+a₁x₁+…+a_nx_n, a_iÎ {0, 1}} линейных функций замкнут относительно суперпозиций.

Определение. Если a = (a₁, …, a_n) и b = (b₁, …, b_n) - наборы длины n из 0 и 1, то a £ b, если a₁ £ b₁, …, a_n £ b_n.

Пример.

Наборы (0, 1, 0) и (1, 1, 0) сравнимы, причем (0, 1, 0) £ (1, 1, 0).

Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и (1, 1, 0).

Определение. Функция f(x₁, x₂, …, x_n) называется монотонной, если для всяких наборов a = (a₁, …, a_n) и b = (b₁, …, b_n) условие a £ b влечет f(a) £ f(b).

Теорема. Класс M = {f | a£ b Þ f(a)£ f(b)} монотонных функций замкнут относительно суперпозиций.

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f₁, …, f_m} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T₀, T₁, L, M, S нашлась хотя бы одна функция f_i из системы, не принадлежащая этому классу.

Пример.

Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста.

Решение.

Строим таблицу значений и треугольник Паскаля:

Многочлен Жегалкина имеет вид: f = x₃ + x₂x₃ + x₁ + x₁ x₃.

1. f(0, 0, 0) = 0 Þ fÎ T₀;

2. f(1, 1, 1) = 1 Þ fÏ T₁;

3. f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то f Ï S;

4. так как в многочлене Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то f Ï L;

5. сокращенная ДНФ функции имеет вид: , так как она содержит отрицания, то f Ï M.

Сведем полученные данные:

Пример.

Доказать полноту системы {+, Ú, 1}.

Решение.

Введем обозначения: f₁ = x₁ + x₂, f₂ = x₁ Ú x₂, f₃ = 1. Построим единую таблицу для функций.

Многочлен Жегалкина:

Поскольку для каждого из пяти функционально замкнутых классов нашлась функция, не принадлежащая этому классу (в каждом столбце имеется хотя бы один минус), то система булевых функций {+, Ú, 1} является полной.

Варианты заданий

Вариант 1

Задание 1. Определите к каким классам относится функция следующего вида:

a) (01100111)

b)

Задание 2. Определите, является ли полной система функций?

.

Вариант 2

Задание 1. Определите к каким классам относится функция следующего вида:

a) (110100111)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 3

Задание 1. Определите к каким классам относится функция следующего вида:

a) (01100011)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 4

Задание 1. Определите к каким классам относится функция следующего вида:

a) (11100101)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 5

Задание 1. Определите к каким классам относится функция следующего вида:

a) (11000101)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 6

Задание 1. Определите к каким классам относится функция следующего вида:

a) (10011011)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 7

Задание 1. Определите к каким классам относится функция следующего вида:

a) (01101110)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 8

Задание 1. Определите к каким классам относится функция следующего вида:

a) (11101011)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 9

Задание 1. Определите к каким классам относится функция следующего вида:

a) (01010101)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 10

Задание 1. Определите к каким классам относится функция следующего вида:

a) (10101011)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 11

Задание 1. Определите к каким классам относится функция следующего вида:

a) (10110011)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 12

Задание 1. Определите к каким классам относится функция следующего вида:

a) (10101010)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 13

Задание 1. Определите к каким классам относится функция следующего вида:

a) (01111010)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 14

Задание 1. Определите к каким классам относится функция следующего вида:

a) (10111101)

b)

Задание 2. Определите, является ли полной система функций?

Вариант 15

Задание 1. Определите к каким классам относится функция следующего вида:

a) (01100110)

b)

Задание 2. Определите, является ли полной система функций?

Вопросы к защите практической работы №5

1. Какая система булевых функций называется полной?

2. Что называется суперпозицией ранга 1?

3. Что называется суперпозицией ранга г?

4. Какие системы называются двойственными? Самодвойственными?

5. Охарактеризуйте основные классы функций.

6. Сформулируйте теорему Поста.