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

Булевой называется произвольная n-местная функция , где .

Эти функции нам встречались в теме «Математическая логика» при составлении 16-ти функций для двух переменных.

Полная система булевых функций обозначается Е имеет следующий вид:

f₁(x₁,x₂,…x_k1)

f₂(x₁,x₂,…x_k2)

…………….

F_e(x₁,x₂,…x_ke)

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

Суперпозиция – это функция f^*, которая получена из функции f с помощью следующих преобразований:

Ø замена переменной. f(x₁, x₂, x_j,…,x_n) f^*=f(x₁, x₂, x_j-1,y, x_j+1,…,x_n)

Ø подстановка вместо х_j некоторой функции из системы (1).

f^*=f_i(x₁, x₂, x_j-1, f_e(x₁,x₂,…x_ke) x_j+1,…,x_ki).

Пример: система функций (Е₁) всегда полна, т. к. каждая функция этой системы может быть представлена в виде СДНФ, следовательно СДНФ является суперпозицией, через которую может быть выражена любая из функций системы;

Система функций (Е₂) также является полной, т. к. недостающая функция () может быть выражена через остальные две по правилу де Моргана и двойного отрицания: .

Задание №7

Доказать полноту системы:

.

Для наглядности эту систему можно записать следующим образом: . То есть нам дана система, состоящая из булевой функции (импликации) и константы 0. С их помощью мы можем выразить операцию отрицания, для этого мы константу 0 подставим вместо одной из переменных:

следовательно данная система является полной.