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

Определение 11.1. Система булевых функций называется полной, если всякая булева функция является суперпозицией функций из этой системы.

Теорема 11.2. Следующие системы булевых функций являются полными:

1. {Ú,×,'};

2. {+, ×, '};

3. {Ú,'};

4. {×,'};

5. {®, '};

6. { | };

7. { ¯ }.

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

В силу полноты системы {Ú,×,'} каждая булева функция является суперпозицией дизъюнкции, конъюнкции и отрицания. Если мы сможем выразить дизъюнкцию через функции +, ×, ', то тем самым докажем, что всякую функцию можно выразить через эти функции, т.е. докажем полноту системы функций {+, ×, '}. Это можно сделать так: x Ú y = x + y + x × y. Предлагается самостоятельно проверить справедливость приведенного тождества. Аналогично доказывается полнота остальных систем. Теорема доказана. Теперь от разрозненных и случайных примеров полных систем булевых функций перейдем к их исчерпывающему описанию. Прежде чем получить такое описание, в следующем пункте рассмотрим необходимые предварительные понятия.

Специальные классы булевых функций. Говорят, что булева функция f (x 1,..., xn) сохраняет 0, если f (0,...,0) = 0. Обозначим P 0 — класс всех булевых функций, сохраняющих 0.

Говорят, что булева функция f (x 1,..., xn) сохраняет 1, если f (1,...,1) =1. Обозначим P 1 — класс всех булевых функций, сохраняющих 1.

Булева функция f (x 1,..., xn)* называется двойственной функцией для булевой функции f (x 1,..., xn), если f (x 1,..., xn) f '(x '1,..., x ' n)* = для любых x 1,..., xn. Булева функция f называется самодвойственной, если f * = f. Класс всех самодвойственных булевых функций обозначим S.

Введем на множестве {0, 1} отношение порядка, полагая, что 0 £ 0, 0 £1, 1£1. Булева функция f (x 1,..., xn)называется монотонной, если для любых из немедленно следует, что . Класс всех монотонных функций обозначим М. Наконец, булева функция f (x 1,..., xn)называется линейной, если ее можно представить в виде следующего выражения (называемого полиномом Жегалкина степени не выше первой): f (x 1,..., xn)= a 0 + a 1 x 1 +... + an xn, где a 0, a 1,..., an — постоянные, равные либо 0, либо 1. Символом L обозначим класс всех линейных булевых функций.

Введенные классы булевых функций P 0, P 1, S, M, L играют главную роль при описании полных систем булевых функций. В следующей теореме устанавливаются два важных свойства этих классов и одновременно рассматриваются примеры функций, принадлежащих и не принадлежащих каждому из них.

Класс булевых функций называется собственным, если он не пуст и не совпадает с классом всех булевых функций. Класс булевых функций называется замкнутым или классом Поста, если он вместе со всякими своими функциями содержит любую их суперпозицию.

Теорема 11.3. Классы P 0, P 1, S, M, L являются собственными замкнутыми классами булевых функций. Заметим, что, например, функция f (x) = x принадлежит каждому из пяти классов P 0, P 1, S, M, L.

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

Теорема 11.4 (о полноте системы булевых функций). Система булевых функций { f 0, f 1,..., fs,...} является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу P 0, имеется функция, не принадлежащая классу P 1, имеется функция, не принадлежащая классу S, имеется функция, не принадлежащая классу М, имеется функция, не принадлежащая классу L.

До к а з а т е л ь с т в о. Необходимость. Пусть система булевых функций { f 0, f 1,..., fs,...} полна. Допустим, что все функции этой системы входят в класс P 0. Поскольку на основании предыдущей теоремы класс P 0 замкнут, то всякая суперпозиция любых функций из данной системы есть функция из класса P 0. Но также по предыдущей теореме класс P 0 не исчерпывает всех булевых функций. Поэтому найдется булева функция (не принадлежащая классу P 0), которая не является суперпозицией функций из системы { f 0, f 1,..., fs,...}, что противоречит полноте этой системы. Следовательно, в системе имеется функция, не принадлежащая классу P 0. Совершенно аналогично доказываются утверждения о наличии в системе { f 0, f 1,..., fs,...} функций, не принадлежащих классам P 1, S, M, L.
40. Предикаты от n переменных

Понятие предиката. В высказывании все четко: это — конкретное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение.

Определение 18.1. Определенным на множествах M 1,..., Mn п-местным предикатом называется предложение, содержащее п переменных x 1,..., xn, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M 1,..., Mn соответственно. Для п -местного предиката будем использовать обозначение P (x 1,..., xn). Переменные x 1,..., xn называют предметными, а элементы множеств M 1,..., Mn, которые эти переменные пробегают, — конкретными предметами. Всякий п -местный предикат P (x 1,..., xn), определенный на множествах M 1,..., Mn представляет собой функцию п аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-высказыванием. Отметим еще один подход к понятию предиката. Как отмечалось, предикат P (x 1,..., xn), определенный на множествах M 1,..., Mn, превращается в конкретное высказывание P (a 1,..., an), если вместо предметных переменных x 1,..., xn подставить в него конкретные предметы из множеств M 1,..., Mn соответственно. Это высказывание может быть либо истинным, либо ложным, т. е. его логическое значение равно 1 или 0. Следовательно, данный предикат определяет функцию п аргументов, заданную на множествах M 1,..., Mn и принимающую значение в двухэлементном множестве {0, 1}. Иногда эту функцию и называют предикатом.

Классификация предикатов. Определение 18.2. Предикат P (x 1,..., xn), заданный на множествах M 1,..., Mn, называется:

а) тождественно истинным, если при любой подстановке вместо переменных x 1,..., xn любых конкретных предметов a 1,..., an из множеств M 1,..., Mn соответственно он превращается в истинное высказывание P (a 1,..., an);

б) тождественно ложным, если при любой подстановке вместо переменных x 1,..., xn любых конкретных предметов из множеств M 1,..., Mn соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов a 1,..., an из множеств M 1,..., Mn соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат P (x 1,..., xn) последний превратится в истинное (ложное) высказывание P (a 1,..., an). Отметим некоторые достаточно очевидные закономерности взаимосвязей между предикатами различных типов (рекомендуется осмыслить их): 1) каждый тождественно истинный предикат является выполнимым, но обратное неверно; 2) каждый тождественно ложный предикат является опровержимым, но обратное неверно; 3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным; 4) каждый не тождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным.

Множество истинности предиката. Определение 18.3. Множеством истинности предиката P (x 1,..., xn), заданного на множествах M 1,..., Mn, называется совокупность всех упорядоченных п -систем a 1,..., an, в которых a 1 Î M 1, a 2 Î M 2,..., an Î Mn, таких, что данный предикат обращается в истинное высказывание P (a 1,..., an)при подстановке x 1 = a 1, x 2 = a 2,..., xn = an. Это множество будем обозначать P +. Таким образом,

Множество P + истинности п -местного предиката P (x 1,..., xn)представляет собой п -арное отношение между элементами множеств M 1,..., Mn. Если предикат Р(х) — одноместный, заданный над множеством М, то его множество истинности Р+ является подмножеством множества M: P + Í M

В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов (определение 18.2). В самом деле, п -местный предикат P (x 1,..., xn), заданный на множествах M 1,..., Mn, будет:

а) тождественно истинным тогда и только тогда, когда P + = M 1 ´...´ Mn;

б) тождественно ложным тогда и только тогда, когда P + =o;

в) выполнимым тогда и только тогда, когда P + ¹ o;

г) опровержимым тогда и только тогда, когда P + ¹ M 1 ´...´ Mn.

На языке множеств истинности еще более отчетливо проясняются закономерности взаимосвязей между предикатами различных типов, отмеченные в конце предыдущего пункта. Проанализируйте их еще раз.

Равносильность и следование предикатов. Определение 18. 4. Два п -местных предиката P (x 1,..., xn)и Q (x 1,..., xn), заданных над одними и теми же множествами M 1,..., Mn называются равносильными, если набор предметов (элементов) a 1 Î M 1, a 2 Î M 2,..., an Î Mn превращает первый предикат в истинное высказывание P (a 1,..., an)в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание Q (a 1,..., an).

Утверждение о равносильности двух предикатов Р и Q символически будем записывать так: P Û Q. Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех п -местных предикатов, определенных на множествах M 1,..., Mn, распадается на непересекающиеся классы равносильных предикатов (все они определяют одну и ту же функцию, заданную на множествах M 1,..., Mn и принимающую значения в двухэлементном множестве {0,1}). Переход от предиката P 1 к равносильному ему предикату P 2 называется равносильным преобразованием первого. Это понятие очень важно для школьной математики, потому что изучаемые в ней уравнения и неравенства представляют собой частные виды предикатов. Решение уравнения и неравенства есть поиск их множеств истинности. При таком поиске мы проделываем над уравнением и неравенством различные преобразования, и здесь важно, чтобы эти преобразования были равносильными, т.е. чтобы найденное множество оказалось бы множеством истинности именно исходного уравнения или неравенства. Аналогична ситуация при решении систем уравнений или неравенств. Отметим следующее немаловажное обстоятельство: может быть так, что два предиката равносильны, если их рассматривать над одним множеством, и неравносильны, если их рассматривать над другим (в частности, объемлющим первое) множеством.

Определение 18.5. Предикат Q (x 1,..., xn), заданный над множествами M 1,..., Mn, называется следствием предиката P (x 1,..., xn), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат P (x 1,..., xn). Утверждение о том, что предикат Q является следствием предиката Р, будем символически записывать так: P Þ Q. Язык множеств истинности позволяет установить взаимосвязь между понятиями равносильности и следования предикатов: два предиката, определенные на одних и тех же множествах, равносильны тогда и только тогда, когда каждый из них является следствием другого. Кроме того, этот же язык дает возможность без труда установить следующие простые теоремы.

Теорема 18.6. Каждые два тождественно истинных (тождественно ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (тождественно ложному) предикату, сам является тождественно истинным (тождественно ложным) предикатом.

Теорема 18. 7. Каждый тождественно истинный п-местный предикат является следствием любого другого п-местного предиката, определенного на тех же множествах. Каждый п-местный предикат является следствием любого тождественно ложного п-местного предиката, определенного на тех же множествах.

Теорема 18.8. Пусть P (x 1,..., xn) и Q (x 1,..., xn)— два п-местных предиката, определенные на одних и тех же множествах, такие, что Q (x 1,..., xn) есть следствие P (x 1,..., xn). Тогда: а) если P (x 1,..., xn) тождественно истинный (выполнимый), то и Q (x 1,..., xn) тождественно истинный (выполнимый);

б) если Q (x 1,..., xn) тождественно ложный (опровержимый), то и P (x 1,..., xn) тождественно ложный (опровержимый).