Функциональные системы с операциями: алгебра логики

Задание 3.1. Подсчитайте количество различных булевых функций n переменных, если

а) n = 1; б) n = 2; в) n = 3; г) n = 4.

Решение. Количество различных булевых функций n переменных вычисляется по формуле

K(n) = ;

поэтому

а) K(1) = 2² = 4; б) K(2) = 2⁴ =16; в) K(3) = 2⁸ =256; г) K(4) = 2¹⁶ = 65536.

Задание 3.2. Проверить, выполняются ли законы ассоциативности для штриха Шеффера.

Решение. Составив таблицу, сравним значения функций f₁(x, y, z) = (x | y) | z и

f₂(x, y, z) = x | (y | z).

Таблица 1.

Так как f₁(x, y, z) ≠ f₂(x, y, z), то для штриха Шеффера законы ассоциативности не выполняются.

Задание 3.3. Составить СДНФ и СКНФ для функции x ~ y.

Решение. Мы имеем два набора: (0, 0) и (1, 1), на которых эта функция равна 1; поэтому СДНФ имеет вид: x ~ y = x⁰&y⁰ Ú x¹&y¹= Ú x y.

Эта функция равна 0 на наборах (0,1) и (1,0); поэтому СКНФ имеет вид: x ~ y = = (х Ú ) ( Ú y).

Задание 3.4. Выразить функцию x₁ Ú x₂ в виде полинома Жегалкина.

Решение. Запишем полином Жегалкина для функции двух переменных в общем виде: f(x₁,x₂) = a₁₂x₁x₂ Å a₁x₁ Å a₂x₂ Å a₀. Определим теперь неизвестные постоянные a₁₂, a₁, a₂, a₀. Для этого положим x₁=x₂=0 и подставим эти значения в полином. Получим 0=a₀, т.е. a₀=0.

При x₁=0, x₂=1 имеем 1 = a₂Å a₀, т.е. a₂=1,

при x₁=1, x₂=0 имеем 1 = a₁Å a₀, т.е. a₁=1, наконец,

при x₁=x₂=1 имеем 1 = a₁₂Åa₁Åa₂Åa₀, т.е. a₁₂=1.

Окончательно имеем: x₁Úx₂ = x₁x₂ Å x₁ Å x₂.

Ответ: x₁Úx₂ = x₁x₂ Å x₁ Å x₂.

Задание 3.5. К каким из основных замкнутых классов T₀, T₁, S, M, L принадлежит и к каким не принадлежит функция φ(x) = ? Ответ обосновать.

Решение.

1. Так как φ(0) = 1, то φ(x) Ï T₀.

2. Так как φ(1) = 0, то φ(x) Ï T₁.

3. Так как на противоположных наборах φ(x) принимает противоположные значения, то φ(x) Î S.

4. Так как φ(0) > φ(1), то φ(x) Ï M.

5. Так как полином Жегалкина xÅ1 этой функции не содержит конъюнкций, то эта функция линейная , т.е. φ(x) Î L.

Задание 3.6. Используя теорему о функциональной полноте проверить, является ли полной система функций

f₁ = x₁&x₂, f₂ = 0, f₃ = 1 и f₄ = x₁Åx₂Å x₃ ?

Решение. Так как f₃ Ï T₀, f₂ Ï T₁, f₂ Ï S, f₄ Ï M, f₁ Ï L, то система этих функций целиком не содержится ни в одном из пяти указанных классов, а значит, является полной.