Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

В этой теме рассматриваются всюду определенные функции, заданные на множестве B={0,1}. Такие функции называются булевыми. Основная цель темы – доказать критерий полноты класса функций – теорему Поста.

§1. Замкнутость и полнота

§2. Самодвойственные функции

§3. Монотонные функции

§4. Линейные функции

§5. Критерий полноты

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


Определение. Классы T0,T1,S,M и L называются основными замкнутыми классами функций.


Теорема 2.4. Класс булевых функций K является полным тогда и только тогда, когда он не содержится ни в одном из основных замкнутых классов.


Доказательство. Докажем необходимость. Пусть K – полный класс. Если K содержится в одном из основных полных классов, скажем KÍT0, то [K]Í[T0]. Но [K] – класс всех булевых функций, [T0]=T0 и, следовательно, любая булева функция сохраняет 0. Противоречие показывает, что K не содержится в T0. Аналогично доказывается, что K не содержится и в других основных замкнутых классах.

Перейдем к доказательству достаточности. Пусть K не содержится ни в одном из классов T0,T1,S,M и L. Тогда класс K содержит функции f0(x1,…,xn), f1(x1,…,xn), f2(x1,…,xn), f3(x1,…,xn), f4(x1,…,xn), такие, что f0ÏT0, f1ÏT1, f2ÏS, f3ÏM и f4ÏL.

Докажем, что [K] содержит n(x) и x×y. Так как f0ÏT0, то f0(0,…,0)=1. Относительно значения f0(1,…,1) рассмотрим два случая.


Случай 1: f0(1,…,1)=0. Рассмотрим функцию g(x)=f(x,…,x). Тогда g(0)=f0(0,…,0)=1 и g(1)=f0(1,…,1)=1, т.е. g(x)=n(x). Это означает, что замыкание класса K содержит отрицание. Классу K принадлежит несамодвойственная функция f2(x1,…,xn). По лемме о несамодвойственной функции замыкание класса K содержит константы. Поскольку K содержит нелинейную функцию f4(x1,…,xn), то в силу леммы о нелинейной функции [K] содержит произведение. Мы доказали, что в первом случае [K] содержит n(x) и x×y.


Случай 2: f0(1,…,1)=1. Тогда, если g(x)=f0(x,…,x) и h(x)=f1(g(x),…,g(x)), то g(0)=f0(0,…,0)=1=f0(1,…,1)=g(1), h(0)=f1(g1(0),…,g1(0))=f1(1,…,1)=0=f1(g(1),…,g(1))=

h(1), поскольку f1 не сохраняет 1. Это означает, что константы принадлежат [K]. Так как K содержит немонотонную функцию, то по лемме о немонотонной функции, [K] принадлежит отрицание. Далее, f4 – нелинейная функция из K, поэтому по лемме о нелинейной функции [K] содержит и произведение x×y.

Итак, в обоих случаях, замыканию [K] принадлежит n(x) и x×y. Поскольку {n(x), x×y – полный класс, то K – так же полный класс.

Теорема доказана.


В доказательстве достаточности устанавливается более сильное утверждение: если K не содержится ни в одном из основных замкнутых классов, то в K найдутся пять функций f0,…,f4 таких, что класс { f0,…,f4} является полным. На самом деле, более внимательное рассмотрение доказательства достаточности позволяет получить следующее утверждение.


Теорема 2.5. Каждый полный класс содержит полный подкласс, состоящий из не более чем четырех функций.


Доказательство. Пусть K – полный класс. Тогда по теореме 2.4 класс K не содержится ни в одном из основных замкнутых классов. В K найдутся, как и в доказательстве предыдущей теоремы, функции f0,…,f4. При рассмотрении случая 1 использованы три функции f0,f2 и f4, т.е. в этом случае {f0,f2,f4} – полный подкласс класса K. В случае 2 использованы четыре функции: f0,f1,f3 и f4 . В этом случае {f0,f2,f3,f4} – полный подкласс класса K. Итак, в обоих случаях в K найдется полный подкласс, содержащий не более четырех функций.

Теорема доказана.


Приведем пример, показывающий, что в формулировке предыдущей теоремы нельзя «четырех» заменить на «трех». Рассмотрим класс


K={q(x), i(x), x×y, x+y+z}.


Очевидно, что q(x) не принадлежит T1, i(x) не принадлежит T0. Функция x×y не является, как отмечалось, ни самодвойственной, ни линейной. Нетрудно проверить, что x+y+z – немонотонная функция. Следовательно, по теореме Поста K – полный класс. В то же время, любой его собственный подкласс полным не является. Действительно, если удалить функцию q(x), то оставшиеся функции будут сохранять 1, если удалить i(x), то будут сохранять 0. Класс функций K без функции x×y состоит из линейных функций, а без последней функции – из монотонных.


Параграф закончим рассмотрением следующего понятия.


Определение. Замкнутый класс K называется предполным. Если K – неполный класс, но для любой функции fÏK класс KÈ{f} является полным.


Теорема 2.6. Предполными являются классы T0,T1,S,M и L и только они.


Доказательство. Необходимость докажем на примере класса T0. Класс T0 содержит не самодвойственную и нелинейную функцию x×y, немонотонную функцию x+y и функцию q(x), не сохраняющую 1. Если fÏK, то класс {K′={q(x),f,x×y,x+y} не содержится ни в одном из основных замкнутых классов и поэтому K′ – полный класс. Поскольку K′ÍKÈ{f}, то класс KÈ{f} также является полным.

Докажем достаточность. Пусть K – предполный класс. Поскольку класс K не является полным, то K содержится в одном из основных замкнутых классов. Для определенности предположим, что KÍT0. Если KÌT0, то существует функция f такая, что fÏK и fÎT0. Тогда KÈ{f}ÍT0 и класс KÈ{f} не может быть полным. Следовательно, K=T0.

Теорема доказана.

Задачи

Ответы, указания и решения

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru