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

Система булевых функций {F₁, F₂, …, F_n} называется полной, если любая булева функция может быть выражена через эту систему.

Применение понятия С.Д.Н.Ф. позволяет легко установить полноту операций отрицания, конъюнкции и дизъюнкции.

Теорема 2.3 Система операций отрицания, конъюнкции и дизъюнкции полна.

Доказательство.

Пусть F(x₁, x₂,…,x_n) = 0. Тогда представим ее в виде F(x₁, x₂, …, x_n) = x₁ & x₁. Если же F(x₁, x₂, …,x_n) = 1, то представим ее как С.Д.Н.Ф. Учитывая, что

x при  = 0,

x^ =

x при  = 1,

получим доказательство теоремы.

Пусть  — некоторое подмножество булевых функций. Замыканием  называется множество всех булевых функций, представимых в виде формул через функции множества . Замыкание множества  обозначается []. Если  = [], то  замкнуто. Можно показать, что замыкание обладает рядом свойств, важнейшими из которых являются:

[] и [[]] = [].

В терминах замыкания можно дать следующее определение полноты. Система функций {F₁, F₂, …, F_n} =  называется полной, если замыкание  равно множеству всех булевых функций.

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

Из результатов его теории, в частности, следует, что рассмотренная выше система операций отрицания, конъюнкции и дизъюнкции является лишь примером полных систем.

2.5. Исчисление предикатов

Пусть A — произвольное множество и x_1, x₂, …, x_n  A. Построим функцию P: A   Такая функция называется предикатом, а множество A — предметной областью пре­диката. Сами переменные x_1, x₂,…, x_n называются пред­метными переменными, а число n — местностью пре­ди­ката.

Рассмотрим, например, одноместный предикат

P(x — поэт классик),

который принимает значение единица, если x — фамилия и инициалы поэта — классика и 0 — в противном случае. При подстановке x = «Пушкин А.С.» имеем P = 1, а, например, если x = «Достоевский Ф.М.», то P = 0. То есть в данном случае в качестве предметной области рассматривается ли­те­ратуро­ве­де­ние.

Такая ситуация может возникнуть, например, тогда, когда происходит диалог пользователя с компь­ютером на интеллектуальном уровне. В процессе этого диа­лога компь­ютер выдает текущий запрос на экран или в ау­диосистему: «Сообщите фамилию и инициалы, ин­те­ре­су­ющего Вас поэта‑классика». Если Вы сообщаете, ска­жем, «Пушкин А.С.», то диалоговая система сужает область сво­его опре­деления на базу данных, соответ­ствующую жиз­ни и деятельности А.С. Пушкина. Это про­исходит благодаря то­му, что вычисляемый диалоговой системой предикат при­ни­мает истинное значение — 1. Если же Вы сообщите, скажем, «Достоевский Ф.М.», то предикат примет значение 0 и настроенная на него компьютерная про­­г­рамма возможно сообщит, что Ф.М. Достоевский, как поэт не известен.

В данном случае мы не останавливаемся на описании способа вычисления предиката. Отметим только, что подо­бные вычисления, как правило, относятся к компетенции программирования.

Рассмотрим еще построение предиката, который при­нимает значение 1, если конец вектора V = (x_v,y_v) при­надлежит квадрату со стороной единичной длины, сме­щенного относительно центра системы координат XОУ на l единиц вправо и на m единиц вверх (Рисунок 2.1).

В данном случае предметной областью является теория множеств. Вначале определим предикат принадлежности. Скажем, что

P(а  A) = 1

тогда и только тогда, когда а  A.

Для построения предиката выделим геометрическое место точек квадрата.

y l

(x_v,y_v) m

o x

Рисунок 2.1.

Очевидно, неравенство -0.5  (x - l)  0.5 выделяет поло­су единичной ширины, смещенную на l единиц вправо по оси x. Аналогично, неравенство -0.5  (у - m)  0.5 выделяет полосу также единичной ширины, но смещенную на m еди­ниц вверх по оси ординат. Обозначим выделенные мно­же­ства соответственно X_l и Y_m .

Ясно, что пересечение этих множеств определяет изоб­раженный на рисунке квадрат. Учитывая это, наш предикат может быть записан следующим образом:

P((x_v, y_v)  X_l  Y_m).

Если при этом требуется выразить этот же предикат че­рез операции отношений и операции математической логи­ки, то в таком случае поступим следующим образом. Вна­чале определим предикат отношения : P(x  у) = 1 тогда и только тогда, когда x  у. Далее заметим, что

P((x_v, y_v)  X_l  Y_m) = P((x_v, y_v)  X_l)  P((x_v, y_v) Y_m).

Справедливость данного выражения проверяется непосредственно.

Выразим теперь предикаты отношения через преди­каты принадлежности:

P((x_v, y_v)  X_l) = P(-0.5  (x - l)  0.5),

P((x_v, y_v)  Y_m) = P(-0.5  (у - m)  0.5).

Окончательно получим

P((x_v, y_v)  X_l  Y_m) = P(-0.5  (x_v - l)  0.5)  P(-0.5 

 (у_v - m)  0.5) = P(-0.5  (x_v - l))  P(-0.5  (у_v - m) ) 

 P((x_v - l)  0.5)  P((у_v - m)  0.5).

Правую часть этого отношения можно реализовать на уровне команд любого современного микропроцессора.

Данный пример иллюстрирует применение предикатов в графическом интерфейсе компьютерных диалоговых сис­тем.