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

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

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

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

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

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

Будем исходить из некоторого множества F функциональных символов. Каждому символу приписано натуральное число – местность (или арность) символа. Можно считать, что F представляет собой объединение F1ÈF2ÈFnÈ, где Fn – множество символов n-местных функций. Кроме F, имеется множество переменных V, элементы которого будем обозначать буквами u,v,w,x,y,z с индексами и без них. Каждому n-местному функциональному символу поставлено в соответствие (всюду определенное) отображение



(При этом разным символам может соответствовать одно и то же отображение.) Это отображение будем обозначать той же буквой, что и символ.


Введем основное понятие.


Определение. Булевыми функциями называются выражения одного из следующих видов:


1)     f(v1,…vn), где fÎFn, v1,…,vn – переменные,

2)     f(t1,…tn), где fÎFn, t1,…,tn – булевы функции.


Для обозначения двухместных функций наряду с префиксным f(v1,v2) мы будем применять и инфиксное v1fv2, особенно, если речь идет об известных функциях, например, x1+x2, x1×x2. Условимся так же об обозначении некоторых часто встречающихся функций. Эти обозначения содержатся в таблицах 2.1 и 2.2.

Таблица 2.1

x q(x) i (x) e(x) n(x)
0 0 1 0 1
1 0 1 1 0

Таблица 2.2

x y x×y xÚy x®y x«y x+y x|y x¯y
0 0 0 0 1 1 0 1 1
0 1 0 1 1 0 1 1 0
1 0 0 1 0 0 1 1 0
1 1 1 1 1 1 0 0 0

(Заметим, что любую функцию f(x1,…,xn) можно задать аналогичной таблицей, содержащей 2n строк). Функции q(x) и i(x) будем называть константами, e(x) – тождественной функцией. Функцию n(x) будем иногда называть отрицанием. Для функций xÚy, x®y, x«y сохраним названия, идущие из логики высказываний: дизъюнкция, импликация и эквиваленция. Функции x×y и x+y, – естественно, умножение и сложение; умножение можно было бы назвать конъюнкцией. Функция x|y – штрих Шеффера, x¯y – стрелка Пирса (или стрелка Лукасевича).


В обозначениях функций будем допускать фиктивные переменные. Так, например, функцию x1+x2 можно обозначить через f(x1,x2,x3).


Определение. Класс булевых функций K называется замкнутым относительно переименования аргументов, если из того, что n-местная функция f(x1,…,xn) принадлежит K, а y1,…yn – другие переменные (среди которых могут быть и совпавшие), то функция f(y1,…yn) также принадлежит K.

Например, если K содержит функцию x+y и замкнут относительно переименования аргументов, то K содержит также и функцию q(x).


Определение. Класс булевых функций K называется замкнутым относительно суперпозиции, если из того, что функции f(x1,…xk), g1(x1,…xn),…, gk(x1,…,xn) принадлежат K следует, что функция


f(g1(x1,…,xn),…gk(x1,…xn))


также принадлежит K.

Например, если K содержит функцию xÚy и n(x) и замкнут относительно суперпозиции (и переименования аргументов), то K содержит и x×y, поскольку x×y=n(n(x)Ú n(y)).


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

1)     содержит тождественную функцию;

2)     замкнут относительно переименования аргументов;

3)     замкнут относительно суперпозиции.


Приведем примеры. Функция f(x1,…,xn) называется сохраняющей

ноль, если f(0,…,0)=0. Функции x×y, xÚy, x+y сохраняют ноль, а x«y, x|y, x¯y не сохраняют. Через T0 обозначим класс всех функций, сохраняющих 0, т.е.


T0={f(x1,…,xn)| f(0,…,0)=0}.


Докажем, что класс T0 замкнут. Функция e(x) сохраняет 0 и поэтому e(x)ÎT0. Если f(x1,…,xn) сохраняет 0 и y1,…yn – новые переменные, то очевидно, что f(y1,…,yn) также сохраняет ноль. Это означает, что T0 замкнут относительно переименования аргументов. Пусть f(x1,…,xk), g1(x1,…,xn), …, gk(x1,…,xn) сохраняют 0. Тогда


f(g1(0,…,0),…,gk(0,…,0))=f(0,…,0)=0.


Это означает, что T0 замкнут относительно суперпозиции. Мы доказали, что T0 – замкнутый класс.

Функция f(x1,…,xn) называется сохраняющей единицу, если f(1,…,1)=1. Функции x×y, xÚy, x®y сохраняют единицу, а функции x+y, x|y, x¯y не сохраняют. Через T1 обозначим класс всех функций, сохраняющих 1, т.е.


T1={f(x1,…,xn)| f(1,…,1)=1}.


Класс T1 является замкнутым. Доказательство аналогично приведенному в предыдущем абзаце.


Теорема 2.1. Пересечение непустого семейства K={Ki | iÎI} замкнутых классов является замкнутым классом.


Доказательство. Пусть K=Ç{Ki½iÎI}. Класс K содержит тождественную функцию, так как все Ki ее содержат. Если f(x1,…,xn) принадлежит K, а y1,…,yn – новый набор переменных, то для любого i функция f(x1,…,xn)ÎKi, поскольку K – пересечение этих классов, и f(y1,…,yn)ÎKi, поскольку Ki замкнут относительно переименования аргументов. Если функция f(y1,…,yn) принадлежит всем классам Ki, то эта функция принадлежит и их пересечению, т.е. K. Следовательно, K замкнут относительно переименования аргументов.

Предположим, что функции f(x1,…,xk), g1(x1,…,xn), …, gk(x1,…,xn) принадлежат K. Тогда эти функции принадлежат всем классам Ki. Класс Ki замкнут относительно суперпозиции. Следовательно, для любого i класс Ki содержит функцию


f(g1(x1,…,xn),…, gk(x1,…,xn)).


Отсюда следует, что эта функция принадлежит пересечению этих классов – классу K. Мы доказали, что K замкнут относительно суперпозиции.

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


Определение. Замыканием класса K называется пересечение всех замкнутых классов, содержащих K.

Замыкание класса K будем обозначать через [K]. Из теоремы 2.1 следует, что [K] – замкнутый класс.


Отметим ряд простых свойств замыкания.


Теорема 2.2. Пусть K – класс булевых функций. Тогда

1) KÍ[K],

2) если KÍL, то [K]Í[L],

3) класс K замкнут тогда и только тогда, когда K=[K].

Доказательство. Пусть K={Ki½iÎJ} – семейство (всех) замкнутых классов, содержащих K. Так как K содержится в Ki для любого i, то K содержится и в их пересечении, т.е. в [K].

Предположим, что Z={Lj½ÎJ}-семейство замкнутых классов, содержащих L, и что KÍL.Тогда KÍLj для любого j и поэтому LÍK. Отсюда следует, что Ç{Ki½iÎI}ÍÇ{Lj½jÎJ}, т.е. что [K]Í[L].

Если K – замкнутый класс, то KÎK. Следовательно, K=Ç{Ki½iÎI}=[K]. Если же K=[K], то K совпадает с одним из классов Ki и поэтому замкнут.

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


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


Пусть K={q(x), i(x), x+y, x×y}. Тогда класс [K] содержит многочлены (от любого числа переменных). Эти многочлены называются полиномами Жегалкина. Поскольку произведение элементов множества B удовлетворяет тождеству u2=u, то полином Жегалкина можно записать в виде Sai1,…,ikxi1…xik, где {i1,…,ik}Í{1,…,n}, ai1,…,ikÎB и суммирование ведется по всем подмножествам множества [1,…,n}. Например, 1×x1x2+0×x1+1×x2+1 – полином Жегалкина от двух переменных х1 и х2 и а12=1, а1=0, а2=1, а0==1. Этот полином можно, конечно, записать и так: х1х22+1.


Обозначим через BF класс всех булевых функций.


Определение. Класс функций K полным, если [K]=BF.

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


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

1)     K1={x×y, xÚy, n(x)}

2)     K2={x×y, n(x)}

3)     K3={xÚy, n(x)}

4)     K4={x×y, x+y, q(x), ((x)}


Доказательство. Докажем, что любая функция может быть получена из функций класса K1 с помощью суперпозиции и переименования аргументов. Доказательство проведем на примере функции f(x1,x2,x3), заданной таблицей 2.3.


Таблица 2.3

x1 x2 x3 f(x1, x2, x3)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Выделим те строки таблицы, где в последнем столбце стоит 1. Это вторая, шестая, и седьмая строки. Каждой строке поставим в соответствие произведение переменных или их отрицаний следующим образом. Второй строке поставим в соответствие произведение n(x1)×n(x2)×x3, шестой – x1×n(x2)×x3, седьмой – x1×x2×n(x3), т.е. если переменная x принимает значение 1, то пишем x, если принимает значение 0, то пишем n(x). Легко видеть, что функция


g(x1,x2,x3) =[n(x1)×n(x2)×x3]Ú[x1×n(x2)×n3]Ú[ x1×x2×n(x3)]


задается той же таблицей 2.3. Это означает, что f(x1,x2,x3) равна g(x1,x2,x3). Но в записи функции g(x1,x2,x3) использованы только функции из класса K1. Следовательно, f(x1,x2,x3) может быть получена из функций класса K1 суперпозицией и переименованием аргументов, т.е. f(x1,x2,x3)Î[K]. (Естественно, есть прямая аналогия между построением функции g(x1,x2,x3) и приведением к СДНФ, изложенном в конце §5 темы 1.) На основании этого заключаем, что любая булева функция принадлежит замыканию [K1]. Следовательно, K1 – полный класс.

Полнота классов K2 и K3 получается из полноты класса K1 с помощью следующего утверждения. Если K – полный класс и любая функция класса K выражается (с помощью суперпозиции и переименования аргументов) через функции класса L, то L – полный класс. Действительно, если любая булева функция выражается через функции класса K, то она будет выражаться и через функции класса L. Мы уже отмечали, что x×y=n(n(x)Ún(y)). Это равенство доказывает полноту класса K3. Далее справедливо равенство xÚy=n(n(x)×n(y)), из которого следует полнота класса K2. Полнота класса K4 следует из полноты класса K2 и равенства n(x)= x+i(x). Полнота класса K4 означает, в частности, что каждая булева функция может быть задана полиномом Жегалкина. Например, x1®x2=x1×x21+1, х1Úх21×х212.

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


Связь излагаемого материала с логикой высказываний достаточно очевидна. Тем не менее, отметим следующее. Пусть F(X1,…,Xn) и G(X1,…,Xn) – формулы логики высказываний. Заменим ØX на n(X), X&Y на X×Y, большие буквы Xi на маленькие xi(1£i£n). Получим функции f(x1,…,xn) и g(x1,…,xn). Тогда формулы F(X1,...,Xn) и G(X1,...,Xn) равносильны в том и только в том случае, когда функции f(x1,…,xn) и g(x1,…,xn) равны. Это замечание позволит нам при доказательстве равенства функций ссылаться на законы логики высказываний.

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

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

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

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

Задачи

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

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

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

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

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

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


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

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