Критерий Поста
Теорема 6.7 (критерий Поста). Множество булевых функций полно тогда и только тогда, когда оно не содержится целиком ни в одном из классов Поста.
Необходимость условия теоремы доказывается просто: если бы для некоторого класса Поста выполнялось , то всякая суперпозиция над , согласно теореме 6.5, снова лежала бы в . Между тем существуют функции, не содержащиеся ни в одном из классов Поста, например штрих Шеффера (см. пример 6.9). Таким образом, нашлась бы функция, которую нельзя представить в виде суперпозиции над , что противоречит предположению о полноте .
Переходим к доказательству достаточности условия теоремы. Для доказательства полноты множества , удовлетворяющего условию теоремы, построим формулы над для функций отрицания и конъюнкции, поскольку, как было замечено выше, множество, образованное этими функциями, полно. Тогда в силу теоремы 6.3 будет полным и множество .
Для немонотонной функции , согласно теореме 6.6, найдутся два таких набора и , что
![\begin{aligned}\widetilde{\alpha}&= \bigl(\alpha_1,\ldots, \alpha_{i-1},0, \alpha_{i+1},\ldots, \alpha_n\bigr),\\[2pt] \widetilde{\beta}&= \bigl(\alpha_1,\ldots, \alpha_{i-1},1, \alpha_{i+1},\ldots, \alpha_n\bigr),\end{aligned}\quad f_M(\widetilde{\alpha})=1,](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAaAAAAA1BAMAAAD1xCIuAAAAMFBMVEVHcEwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAlTPQ5AAAAD3RSTlMAhLxBARAgMdDwn2FR4HF8PmpDAAAIoklEQVRo3u1aa2wUVRQ+8y67tewuWW21tbsVpYJAARXRH51qoWA0jsUHNdZuAWMkxi5KfMZYQKLyw0qtCmhwra9igizEaPDF+ooxUWkRTUSj1YjPKJQiRQTquXfeM7tr7UWliTcpzM6euXO+e8/zfgvw/xiZI5j+j97b+w9NvJnh2QUqw8MT2HWXIk+pcsp9T354+PPVx79k0KahihnQh0+27axMuu/xoeHPVyE2MNgrF2MGtAtmRXZ57t2dGPZ0Qj8EdjDYy8A/4kLFw3eDmgHg9g//zeJSdu2bKzLeWccTP4qc8ReL+U02D+b3AddvhKyK6BBjm0MworLiCR65cp1MfObmaWScRQD14T9bdt0eas734IzvGlMB393zEVCfDnjZki7t+KGY2bIllZoJqZwZ0NY0rL+UuPHXYTKIBuIfBCdwv/0KkMz1nNIHwYE3QTLdLekFNC8GLdEdoJjyOTWggt3Gh22sgKTVuCrnuGeR0GYauuGi/hVycc6oc/HDIPSdBrwuIJiCFiCxPAOjJ/TCj3iNoLnJOd2GCE4yI2N1khFQEb69ehL4AG1NgXA4JDXnBHR3DIS9KZCNzGUKEh86QvVco8Jx96lwOV6iRSvVOQEZggYg1kRUg8pXt4JlclHD5HDZhANqnrywOwTS7xpc60kggQEjKMh7EV0/SGTFiYvmBGQIyho1ym0JRkAkxlanPYBw18qr0KJ0PWWyaNcRNyDK3UIMDN+6rQokdKMSByAiGMQ81AG36pPMboVFyx2A5mq4/WS2BQQImQ0FJSIYg3PXhWN6UDibCZBwCIS2qHtZxDhAS0Y8p+8KqufFuGHiE/j6Jsx6yiAqta0DnSwE89sVrsUBaA4KSjuhMSQNotaVIG3Ykwx9oZscBbQRSyyeGORXWITOwY2UBpOW4B/CHvymSxVw31nG6+F4/bIqX2IN9kSixadQPXm0CbgfMc/+BNd1NYnYiKxwVeTZkgkQgWYaG6ngQfzu9tIKTWpDCPPiz08/mFIeFMLheDhEAZXjQnCH8GI9vrDgEQRkCE47mBK6i3AKcSXIT7C5kThdhbO8Do9rdMESsS6hu8Z8Ikb+iOeSP/EE/KfuTFAS8IXm8KFFJKJsQn0EsicLNDTUQNSxQ+JYgFrVmI3OVNhrCnIpHq8lhFvjBiQ6QnC96fmZvweST7uKxTd8AmOtbNQdcgi+aj1mBd9RizUbkOwLMYGk/c4mzONFGJ8K3Enkth47/N7rvXCE5nyGKphpTi5bi75/qvf7QqsaV3p0jZSJ7WmQVpi351uix52k7xDfho4Z8BmTLTg60VCK/ooSU9yKPrbGDsk40dR4Al6DGV71Z/2S11A3uYoj3/7y9nTXOnOaJXiCfTNhmBwxnUW+F9mCMl3jMF651y84YJeMLRpctbTsQOWpcL6nwRH3tuUFdGGGzS899UtiqIKFKb/5d9jXzwPcAOKbYxCmt0VRy9lbw39nzLH9TnxM/68W97PfKzdSADWXxy3rEgZor/EsAdUzUgHN3T3GCoTBfRgjKpeUJL/HTp+ex9COZ/qIAgTldvnNIaCCT+CSp+9BQMT7ptBqrXRkAZqsugCVp4F/CI2wTB2hJidiYyF0IoLIGAJIbNOAP4DxvWTEAiL14YcxzNx0h8TDql7eUpNb7DS59MgAJGAFDyd3Q814GhTEdsxMpCr3BwXcxWn6Mz+9c8OxC6iIhOqn9sFLmIMUvC4DqWTfu9nCdgjEQWp2NcsGHz12AQUwEMAzA/LL+2liFet7Os9uj9Gq3GWZg4ODY6EtpB/HXJ04dgEVYKEgpPu5om699CFdbx3WSB2+IqrW6FqyVFS4Lpn/Rn1fLbe5CX2dSzzwHk++ud4qir3FqasZUSp8BhlmORhj6aBf8Hy+/xeiJ8RDo0gQ4ywYM7K+xGhGpmqNnpCnMNApdSUsCaHR83DZvbRPLdYofzDTavCWZ31ab0awLeM9nSRphoebN7ZPZgHEjfVMR8vR3teKKuihcr3Z8OdLOlwVjAr5zxSGX3yxAJL6h9g55RmzVZiR8J36DGGKHAJMgMSV7JFlSnP4c/Cdy4HSOSn/c3IkruUFdA3tXIYwnIJdKjOg0rcqaAyY5qZTfnzx+vx0ypZv58W4PICUlQvXa0NhiJSdCzccRTqFnEnQfXafbQf7oWb/zwA5E5LQhzKbQDatNeMF1BiDpmg3XGmmmJwKNBA6pdX4wEyngGh2Sw5jInRKKxTmp1M6dDpFjydCV8wLaGMGRsfT8AP8BZ0CG6uooD6Y2QdSLogeQJROCYFwuDcP+1CdonSKGRk4LyBxDdYtOktCjrFq89ApcDTpFOAyIB20Tc5k8Aj7cCAfzb67F6TDGiUjsgIyWZKk4yg4uwvpgkpiATU55rqSzxi0tYNjXUXVKjToFIWYw3lkM4mfvE1q+oRFp7yv2YCoIGGW4AM9shS0wuLlDkDXoLBMfkNwIxjSpmAMPlr3dUwPCt8zn3u978272Ey1pMXNfXN1OuUIoVNw3VsonYLGsZXSKeLU9qCPTqGNiUGnyBP3pN10CgrxJIR66BQiGD1E6ZRiYKVTzu3qGue994MKhWs7Q2XjqJ4B7BJhIm4KvwJV2I4f7noIkW3vjG6ZIJ7ooFMCa43GRDodIdQvHX9de0p4UCF0Si8FtGUH7u7jeFGCOPhPcTZbsNCiUz5jc6NScaHvXguu0azLYKZqsyRuP36OhI6FpLD+OOHwoTto/aAaLEmdCrMgcLyDfSAR1SrRbDqFCnKpgu/0eFRTxZqG/H2FVdu5WRJr3GPFyOx0is2SjFrsMDnvj6ScggXppqv0aXiVNQ35A4/ZPnhYEqvRtwDLS/UdUk53Cd5kd5xOOoX3rb0tqNMp5NdYm5g2SMnaKbzi/BBM+tbVXd/7BR0/ICHLTfFji3ynbzm9vzR5Eu9F4eiP4L/Vgtd6WvCQ/97fGn8CLmkpzkfaNswAAAAASUVORK5CYII=) а  .
Тогда , т.е. отрицание может быть получено из немонотонной функции подстановкой вместо некоторого ее переменного переменного , а вместо остальных переменных констант , определяемых выбранными выше наборами и . Но, вообще говоря, система может и не содержать констант. Поэтому константы 0 и 1 необходимо представить некоторыми формулами над .
Рассмотрим два случая.
Первый случай. В существует функция , не сохраняющая константу 0, которая сохраняет константу 1; или существует функция , не сохраняющая константу 1, но сохраняющая константу 0.
Если существует функция и , то константа 1 представляется формулой , так как и . Чтобы выразить константу 0, используем любую функцию , не сохраняющую константу 1:
Если же указанная функция не существует, но найдется функция , to константы представляем формулами над аналогично (двойственным образом).
Второй случай. Любая функция из , не сохраняющая константу 0, не сохраняет и константу 1, и, наоборот, любая функция из , не сохраняющая константу 1, не сохраняет и константу 0.
Пусть и . Тогда мы получаем возможность представить отрицание следующей формулой:
Переходим к построению формул для констант, так как они потребуются нам далее при построении формулы для конъюнкции. Чтобы представить константы формулами над , воспользуемся несамодвойственной функцией из . Для этой функции найдется такой набор , что . Введем функцию от одного переменного (в предположении, что . Легко видеть, что , так как для любого имеем
Итак, значение есть константа. Если она равна 0, то константу 1 представляем через функцию, не сохраняющую константу 0; если же , то константу 0 представляем через функцию, не сохраняющую константу 1.
Опишем построение формулы для конъюнкции. Берем нелинейную функцию из . В полиноме Жегалкина для этой функции выберем произвольное нелинейное слагаемое, содержащее наименьшее число переменных; пусть это будет слагаемое при . Вместо каждого переменного функции , где , подставим константу 0, т.е. заменим нулем все переменные, которые не вошли в выбранную ранее конъюнкцию. Получим "редуцированную" функцию
Заметим, что коль скоро мы уже представили константы формулами над , то функция тоже представлена формулой над . Разобьем теперь множество переменных произвольно на две части: и , где , и заменим все переменные первой части переменным , а переменные второй части — переменным . В результате получим функцию от двух переменных
где .
Ясно также, что функция х может быть представлена такой формулой над 
т.е. функция получена из нелинейной функции путем подстановки на место ее переменных с номерами переменного , на место переменных с номерами — переменного , а на место всех остальных переменных — константы 0, уже представленной формулой над (см. выше).
Определим функцию . Выразив эту функцию из полинома Жегалкина для получим
поскольку сумма по модулю 2 любого четного числа равных слагаемых равна 0. Итак, функция и есть конъюнкция. Так как прибавление к любой функции константы по модулю 2 есть либо сама исходная функция, либо ее отрицание, а отрицание уже представлено формулой над базисом , то тем самым и конъюнкция представлена такой формулой.
Чтобы исследовать полноту конкретного множества функций , нужно построить так называемую критериальную таблицу (табл. 6.6).
Строки таблицы соответствуют функциям исследуемого множества, а столбцы — классам Поста. В результате анализа функций множества клетки таблицы заполняются: если функция принадлежит некоторому классу Поста , то в соответствующей клетке критериальной таблицы ставится знак и "+" (плюс), а если нет, то — знак "–" (минус). Множество тогда полно, если и только если в каждом столбце таблицы стоит хотя бы один знак "–".
Пример 6.21. а. Пусть . Ниже приведены результаты исследования элементов этого множества на принадлежность к классам Поста, а также заполненная критериальная таблица (табл. 6.7).
При этом , так как функция (эквивалентность) не сохраняет константу 0, но сохраняет константу 1 (т.е. имеет место первый случай из доказательства достаточности условия теоремы Поста). Константа 0 принадлежит самому множеству . Поскольку , то ввиду полноты множества будет полным и рассматриваемое множество. Конъюнкцию можно представить формулой над , следуя доказательству теоремы Поста. Берем единственную нелинейную функцию данного множества, дизъюнкцию, и записываем для нее полином Жегалкина:
Видно, что этот полином есть не что иное, как функция при и . Следовательно,
Но так как , то . Этот же результат (в данном конкретном случае) можно получить и гораздо проще:
Итак, исходное множество является полным.
Заметим, что это полное множество двойственно к базису Жегалкина в том смысле, что каждая из его функций двойственна к соответствующей функции базиса Жегалкина: эквивалентность двойственна к сумме по модулю 2, дизъюнкция — к конъюнкции, константа 0 — к константе 1. Полезно заметить также, что никакое собственное подмножество заданного множества не будет полным.
б. Функция задана картой Карно (рис. 6.21), а вектор значений функции есть .
Для функции очень просто находятся ДНФ и полином Жегалкина:
откуда следует нелинейность функции . Легко показать также, что эта функция принадлежит лишь классу .
Так как , а , то функция не сохраняет ни константу 0, ни константу 1. Далее, эта функция несамодвойственна, поскольку ; немонотонность ее следует из того, что, например, , но . Вопрос о нелинейности функции оставим пока открытым, так как даже из частично заполненной критериальной таблицы (табл. 6.8) вытекает, что множество полно.
Формулы для отрицания и констант находятся легко:
Формулу для конъюнкции проще всего построить прямо по ДНФ для функции 
Вернемся теперь к отложенному вопросу о нелинейности функции . По приведенной на рис. 6.21 карте Карно можно построить одну из минимальных ДНФ, представляющих эту функцию в виде
Подставляя в последнюю формулу 0 вместо , а вместо , 1 вместо и вместо , получаем , что доказывает нелинейность функции и одновременно полноту множества .
Константы же можно представить формулами над базисом , используя несамодвойственность функции (см. разбор второго случая в доказательстве достаточности условия теоремы Поста): мы уже видели, что , т.е. набор из упомянутого места в доказательстве теоремы Поста есть , и тогда функция , фигурирующая в том же месте доказательства и равная в данном случае константе 1, будет иметь вид . Но так как , то получаем
Подставив эти формулы в написанную выше формулу для конъюнкции, получим окончательно формулу над базисом для конъюнкции. Мы не выписываем эту формулу ввиду ее громоздкости.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|