Полнота, примеры полных систем

Двойственность. Класс самодвойственных функций.

Лекция 2

Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания.

Будем называть операцию конъюнкции двойственной операции дизъюнкции, а операцию дизъюнкции

двойственной операции конъюнкции. Определение. Формулы А и А * называются двойственными, если формула А * получается из формулы А путем замены в ней каждой операции на двойственную.

Например, для формулы А º (х Úy)&z двойственной формулой будет формула А * º (х& у) Ú z.

Теорема. Если формулы А и В равносильны, то равносильны и им двойственные формулы, то есть

А* º В *.

Предварительно докажем лемму.

Лемма. Если для формулы A(x₁,x₂....x_n) двойственной формулой является А*(x₁,x₂....x_n), то справедлива равносильность А*(x ₁,..., x_n) = (₁,..., _n).

(Доказательство леммы разбирается студентом самостоятельно см. Лихтарников «МЛ» стр. 28-29)

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:

x	f	f *

Функции f (x) = x и g (x) = двойственны сами себе:

x	f	f *	g	g *

так как f *(0)=(1).

Определение 1. Если f *(x ₁,..., x_n) = f (x ₁,..., x_n), то f (x ₁,..., x_n) называется самодвойственной.

Множество всех самодвойственных функций обозначается через S.

Если f *– самодвойственна, то (₁,..., _n) = f (x ₁,..., x_n), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 1. Покажем, что функция х ₁Ú х ₂двойственна к x ₁& x ₂, функция х ₁ х ₂ двойственна к функции x ₁| x ₂.

x ₁ x ₂ f = х ₁_Ú х ₂ f * g = x ₁| x ₂ g *= x ₁ x ₂

Пример 2. Построить формулу, реализующую f *, если f = ((x y) Ú z) (y (xÅyz)). Покажем, что она эквивалентна формуле N = z (x Å y).

Найдем (x Å y)* и (x y)*.

x	y	xÅy	(x Å y)*	x y	(x y)*

Из таблиц видно, что

(x y)* = x ~ y = = x y 1, x y = y x ,

(x y)* = y x y = y.

По принципу двойственности:

f * = yz ((x (y z)1)) = yz z (x (y z)1) = z ( y Ú( x Å z Å)) = z ( y Ú(x Å z Å1)) = z ( y Ú(x Å)) = z y Ú(z x Å z ) = z ( y Ú x ) = z (x Å y).

Тогда f = (f *)* = [ z (x Å y)]* = z Ú(x ~ y).

Обозначим множество всех функций двузначной алгебры логики Р₂. Обозначим через Р₂(n) число функций, зависящих от n переменных. Очевидно, Р₂(n)=2²ⁿ.

Определение. Система функций { f ₁, f ₂,..., f _s,...}Ì P ₂ называется полной в Р ₂, если любая функция f (x ₁,..., x_n) Î P ₂ может быть записана в виде формулы через функции этой системы.

Примеры полных систем:

1. P ₂– полная система.

2. Система M ={ x ₁& x ₂, x ₁_Ú x ₂, } – полная система, т.к. любая функция алгебры логики может быть записана в виде формулы через эти функции.

Примерами неполных систем являются: { }, {0,1}.

Лемма (достаточное условие полноты)

Пусть система U = { f ₁, f ₂,..., f_s,...} полна в Р ₂. Пусть B = { g ₁, g ₂,..., g_k,...} – некоторая система из Р ₂, причем любая функция f_i _Î U может быть выражена формулой над B, тогда система B полна в Р ₂.

Данная лемма может быть использована следующим образом:

_1.Покажем, что система { x ₁_Ú x ₂, } – полна в P ₂.

Возьмем в качестве полной в Р ₂ системы U ={ x ₁_Ú x ₂, , x ₁& x ₂}, B ={ x ₁_Ú x ₂, }. Надо показать, что x ₁& x ₂ представляется формулой над B. Действительно, по правилу Де Моргана получим: x ₁& x ₂=.

2. Система { x ₁| x ₂} полна в Р ₂. Для доказательства возьмем в качестве полной в Р ₂ системы U = { x ₁& x ₂, } и выразим х ₁& х ₂ и через х ₁| x ₂: = x ₁| x ₁, x ₁& x ₂ == (x ₁| x ₂)|(x ₁| x ₂).

3. Система { x ₁ x ₂} полна в Р ₂. U = { x ₁_Ú x ₂, }, = x ₁ x ₁, x ₁_Ú x ₂= = (x ₁ x ₂) (x ₁ x ₂).

7. Система { x ₁& x ₂, x ₁_Å x ₂, 0, 1}, U = { x ₁& x ₂, }, = x ₁_Å1.

Следствие. Полином Жегалкина.

f (x ₁,..., x_n) Ì P ₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как { x ₁& x ₂, x ₁_Å x ₂, 0, 1} полна в Р ₂. В силу свойства x & (yÚz) = xy Ú xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ... х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.