Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
* * * ^*8 = ^1^2/1 (^31 • * ?! "Ь
(»1 *«)
+ ^1/2 ('^31 * * • 1 ^й) “Ь з^/з (*з> ? * • > /й (*^3> • * ? 1 ^0»
где в силу единственности полинома /1(^3, ? ? ?п)^0.
Пусть а3, ..а» таковы, что /Дссз, ..ап) = 1. Тогда
<р(®1, Хг)=}(хи хг, а3, сс„) = хухг + ах1 + + 7,
где ос, р, -у — константы, равные 0 пли 1. Рассмотрим функцию ?2), получаемую из ф {хи хг) следующим
образом:
^(^1, *г) = <р(^1 + Р, хг + се)+ ар + Y•
Очевидно, что
<р + р, х2 + а) + ар + у ~
= (ху + р) {х2 + а) + а (.Г! + р) +
+ р (хг + а) + у + ар + ^ = Х1Х*
Следовательно,
Ч1(ж1т ?г) = #1 & Яг.
Лемма доказана полностью.
В заключение заметим, что замкнутые классы То, Т.и М и Ь попарно различны, что видно из табл. 8, в которой знак + означает, что функции содержится в классе, а знак — обозначает противоположную ситуацию.
Таблица 8
То Т, м о
0 + + +
„ + — + +
X — — р 1 — +
Теперь мы можем перейти к рассмотрению одного из основных вопросов алгебры логики — вопроса ц необдц-
/,(> Ч I ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
дины* й достаточных условиях полноты. Итак, пусть
*Р - {Д, и и •? .>
пршкшолмшп система функций из Р2. Спрашивается, км к мы нсиигь, будет ли она полной или пот? Ответ на шит вопрос дает следующая теорема.
'Г о орем а 7 (о функциональной полноте). Для того чтобы система функций ^была полной, необходимо и до-статично^ чтобы она целиком не содержалась ни в одном ил пяти замкнутых классов Ти 5, М и Ь.
Доказательство. Необходимость. Пусть ^ полна, т. е. [КЦ = Ре. Допустим, что ^содержится в одном из указанных классов — обозначим его через т. е.
П. Тогда в силу свойств замыкания и замкнутости П имеем
р, = ЙИ = РЧ = я.
Значит П = Р2* что не так. Необходимость доказана.
Достаточность. Пусть $ целиком не содержится ни в одном из пяти указанных классов. Тогда из » можно выделить подсистему содержащую не более пята функций, которая также обладает этим свойством. Для итого возьмем в ^функции Д, Д, Д, /т, которые не принадлежат соответственно классам Т0, Ти 5, М и ЬЛ и положим
Г = </«, 1ь и к и.
Можно считать, что все эти функции зависят от одних и тех же переменных хи ..., хп (см. замечание из § 1).
Доказательство достаточности будем проводить в три этапа.
I. Построение прп помощи функций Д, Д и Д констант 0 и 1.
Рассмотрим функцию Д 0 7Т Возможны два случая:
1. Д (1, .1)= 1. Тогда ф(ж) = .Д(ж, ..х) есть константа 1, ибо
Ф(0)=Д(0........0)=1, Ф(1) = Д(1, 1)=1.
Вторая константа получается из Д: Д (1, ..., 1) = 0.
2. Д(1, ..1) = 0. Тогда ф(ж) = Д(а!, ..х) есть а:, ибо
Ф(0) = Д(0, ..., 0) = 1, ф(1) = Д(1, ..1)= 0.
Возьмем Д (Д$^5). Так как мы имеем ,г, то в силу леммы 1 из Д мы можем получить константу. Поскольку
хл. 1, 'рхиххххш
мы располагаем х, то находим и вторую константу. Итак, в обоих случаях мы получаем константы 0 и 1.
II. Построение при помощи констант 0, 1 и функции /т функции х. Это осуществляется на основе леммы 2.
III. Построение при помощи констант 0, 1 и функций х и /( функции $1 & х2. Это осуществляется на основе леммы 3.
Таким образом, мы при помощи формул над ^ (а значит и над !?) реализовали функции х и х1 & х2. Этим достаточность доказана.
Следствие 1. Всякий замкнутый класс 2Й функций из Р2 такой, что Ш1ФР2, содержится по крайней мере в одном из построенных классов.
Определение. Класс 91 функций из Р2 называется предполным (или максимальным), если 91 неполный, а для любой функции }ФШ) класс 91 и {/) —
полный.
Из определения следует, что предполный класс является замкнутым.
Следствие 2. В алгебре логики существует только пять предполных классов, а именно: Т0, Ти 5, М и Ь.
Рассмотрим пример, иллюстрирующий возможности теоремы о функциональной полноте.
Пример 15. Покажем, что система функций
Д — Х&г, /г = 0, /8 = 1 И 1>. = Х1 + Хг + Х9
является ПОЛНОЙ.
Мы имеем: /в Ф Т0, Д Ф ^Ф 5, Д Ф М, Д ФЬ. С другой стороны, удаление любой из функций приводит к неполной системе:
{/2, /31 /4} с В, {Д, Д, Д) с: Ти
{д, Д, Д^П, {’Д,Д, П)С2М.
Из доказательства теоремы 7 непосредственно вытекает следующая теорема.
Теорема 8. Из всякой полной в Р2 системы $ функций можно выделить полную подсистему, содержащую не более четырех функций.
Доказательство. Мы видели, что из ф можно выделить полную подсистему содержащую не более пяти функций. Оказывается, что функция Д ФТй, кроме
?і, і, V» системы с операциями
того, либо не самодвойственна (случай 1), так как /і(0, ..0)= /,(1, ..., 1), либо не сохраняет 1 и не монотонна (случай 2): Д(0, ..0) >/,-(!, ..1). Поэтому полной будет либо система (Д, Д, /т, /Л либо система
Чи Лі /гЛ
Пример 15 показывает, что константа 4 не может быть понижена.
Теорема о функциональной полноте на самом деле дает не только критерий полноты. Она позволяет (в сочетании с разложением в Д. н. ф. или к. п. ф.) найти для произвольной булевой функции / формулу через функции полной системы $.
§ 7. Представление о результатах Поста
Весьма глубокое изучение замкнутых классов в Рг было осуществлено американским математиком Э. Постом. Им была описана структура всех замкнутых классов в Р%. Сформулируем некоторые из важнейших результатов, связанных с этим исследованием.
