III. Образцы решения задач

Программа аттестации студентов по курсу «Дискретная математика» содержит задачи по следующим пяти темам:

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

2. Замкнутые классы и полнота систем функций алгебры логики.

3. Реализация булевых функций схемами из функциональных элементов в стандартном базисе.

4. Классы вычислимых и рекурсивных функций. Операции суперпозиции, примитивной рекурсии и минимизации.

5. Алфавитное кодирование. Алгоритм распознавания однозначности декодирования. Самокорректирующиеся коды.

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

Специальные представления булевых функций – это разложение булевых функций по переменным, СДНФ, СКНФ и полином Жегалкина.

Задача 1

Разложить функцию f(x,y,z) = ∑₀(0,1,2,4) по всем переменным, найти ее СДНФ, СКНФ и построить для нее полином Жегалкина.

Решение:

СДНФ

, где f (σ₁, σ₂, σ₃) = 1,

т.е. СДНФ ∑₀(0,1,2,4) =

СКНФ

, где f (σ₁, σ₂, σ₃) = 0,

т.е. СКНФ ∑₀(0,1,2,4)=

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

Метод таблиц: ,

f (δ₁, δ ₂, δ ₃)=1,

т.е. ∑₀(0,1,2,4) = = (x+1)yz+x(y+1)z+xy(z+1)+xyz = = xyz+yz+xyz+xz+xyz+xy+xyz = xy+xz+yz.

Вывод:

∑₀(0,1,2,4)= = = = xy+xz+yz.

2. Замкнутые классы и полнота систем функций алгебры логики

Основными замкнутыми классами в Р₂ являются классы T₀, T₁, S, M, L, где

T₀ – класс функций алгебры логики (ФАЛ), сохраняющих константу 0;

T₁ – класс ФАЛ, сохраняющих константу 1;

S – класс самодвойственных функций;

M – класс монотонных функций;

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

Каждый из классов T₀, T₁, S, M, L является предполным.

Критерий полноты в Р₂. Система ФАЛ F полна в Р₂ тогда и только тогда, когда она полностью не содержится ни в одном из предполных классов T₀, T₁, S, M, L.

Задача 2

Исследовать полноту системы F = {f₁ = xy+z, f₂ = x+y+1}.

Решение: Построим критериальную таблицу для функций системы. Она имеет вид:

	T0	T1	S	M	L
f1	+	–	–	–	–
f2	–	+	–	–	+

Знак «+» в таблице означает, что функция в данном классе содержится, знак «–» – функция в данном классе не содержится. Если в каждом столбце имеется хотя бы один минус, то это означает, что система полна. Если в таблице имеется хотя бы один столбец из одних плюсов, то это означает, что система не полна.

Вывод: В каждом столбце имеется не менее одного минуса, то по критерию полноты данная система полна.

3. Реализация булевых функций схемами из функциональных элементов в стандартном базисе

Как известно, любую булеву функцию f(x₁, … , x_n) можно реализовать схемой из функциональных элементов (СФЭ) в стандартном базисе Б={&, , –}, при этом сложность СФЭ L(S) ≤ n^.2ⁿ⁺¹, где n ≥ 1.