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

Опр. Сис-ма булевых ф-ций наз-ся полной, если любую булеву ф-цию м.получить из ф-ций дан.сис-мы с пом-ю операций подстановки ф-ции в ф-цию и замены переем-х, примененных конечное число раз.Основные лог.связки, используемые нами – &, Ú, Ø,®. С помощью равносильности x®y ~ мы м.во всех ф-лах, в кот.встр-ся под.ф-ла x®y заменить ее на и, тем самым, исключить из использования знак ®.Т1 С-ма булевых ф-ций {&, Ú, Ø} явл-ся полной.Люб. булеву ф-кцию м.записать в СДНФ. (н-р табличным способом).Т2 С-ма булевых ф-кций {Ú, Ø} явл-ся полной.

Следует из Т1 и з-нов де Моргана: ~ , ~

~ Т3 С-ма булевых ф-кций {&, Ø} явл-ся полной. .

Т4 Сис-а булевых ф-ций {Ø,®} явл-ся полной.Следует из Т2 и равносильности xÚy ~ .Т5 С-ма булевых ф-ций {&, Ú,®}, не содержащая Ø, не является полной.До-во: Р! булеву ф-цию специального вида. Назовем ф-цию (или формулу (АВ)) f(x₁,x₂,…,x_n) сохраняющей истину, если f(1,1,…,1)=1.

Док-м, что булевы ф-ции &, Ú,® сохраняют истину. Пусть f₁(x₁,x₂,…,x_n) и f₂(x₁,x₂,…,x_n) – ф-ции, сохраняющие истину, т.е. f₁(1, 1,…,1)=1 и f₂(1, 1,…,1)=1. Тогда:f₁ & f₂=1;f₁ Ú f₂=1;f₁ ® f₂=1.Т.е. булевы ф-ции &, Ú,® сохраняют истину, если они применяются к ф-циям, сохраняющим истину. Других же ф-ций получить нельзя.Но среди булевых ф-кций есть ф-ции, не сохраняющие истину. Н-р: .

Эту ф-цию нельзя получить с пом-ю рассматриваемой системы булевых ф-ций {&, Ú,®}.

Следствие: Сис-мы булевых ф-ций {&, Ú}, {&,®}, {Ú,®}, {&}, {Ú}, {®} неполны. (Как подсистемы неполных систем).

Т6 Сист-ма булевых ф-ций {Ø} неполна.Пусть даны пропозициональные переем-е x₁, x₂, …,.x_n. При помощи отрицания можно получить только x₁, x₂, …,.x_n, , т.е. ф-ции от одной переем-й и ни одной ф-ции с двумя переем-ми. Это док-т неполноту этой сис-мы.

Вместе с тем сущ-т полные сис-мы, содерж.одну булеву ф-цию, кот.выражается через &, Ú, Ø.