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

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

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

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

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

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

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

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

На множестве B={0,1} в этом параграфе будем смотреть, как на частично упорядоченное множество с отношением 0<1.


Рассмотрим множество


Bn=B ´´ B (n раз).


На множестве Bn введем порядок прямого произведения, т.е.


(a1,…,an)£(b1,…,bn) Û a1£b1,…,an£bn


для любых a1,…,an, b1,…,bnÎB. Например, (1,0,0,1)£(1,0,1,1), (1,0,1,0)£(1,0,1,1). В то же время, неверно, что (1,0,0,1) £(1,0,1,0).


Определение. Функция f(x1,…,xn) называется монотонной, если для любых двух векторов a=(a1,…,an) и b=(b1,…,bn) из условия a£b следует, что f(a)£f(b).

Примерами монотонных функций являются q(x), i(x), x×y, xÚy. Функции n(x), x®y, x+y немонотонны.


Рассмотрим задачу: выяснить будет ли функция f(x1,x2,x3)=x1+x2×x3 монотонной? Для решения этой задачи удобно начертить диаграмму частично упорядоченного множества B3 и в вершинах этой диаграммы проставить значения функции f(x1,x2,x3). Такая диаграмма приведена на рис. 2.1, значения функции f(x1,x2,x3) заключены в квадрат, чтобы их отличать от обозначения вершин множества B3.


Рис. 2.1

Монотонность функции означает, что если в какой-то вершине диаграммы она принимает значение 1, то и всюду выше функция принимает то же значение 1. Функция f(x1,x2,x3)=x1+x2×x3 монотонной не является, так как в вершине (1,1,0) она принимает значение 1, а в вершине (1,1,1), которая выше первой, принимает значение 0.


Класс всех линейных функций обозначим буквой М. Убедимся в том, что М – это замкнутый класс. Монотонность тождественной функции очевидна. Пусть f(x1,…,xn)ÎM и y1,…,yn – новые переменные. Возьмем два набора значений переменных y1,…,yn: a=(a1,…,an), b=(b1,…,bn) таких, что a£b. Но эти векторы будут наборами значений переменных x1,…,xn, и поэтому выполняется неравенство f(a)£f(b). Это означает, что М замкнут относительно переименования аргументов.

Пусть f(x1,…,xk), g1(x1,…,xn),…, gn(x1,…,xn) – монотонные функции и a=(a1,…,an), b=(b1,…,bn) – два набора значений переменных x1,…,xn таких что a£b. Рассмотрим суперпозицию


h(x1,…,xn)= f(g1(x1,…,xn),…, gn(x1,…,xn)).


Значение функций g1(a1,…,an),…,gk(a1,…,an) обозначим соответственно через c1,…,ck, а значение g1(b1,…,bn), …, gk(b1,…,bn) – через d1,…,dk. В силу монотонности функций g1,…,gk имеем, что c1£d1,…,ck£dk. Тогда h(a1,…,an)=f(g1(a1,…,an),…,gk(a1,…,an))=f(c1,…,ck) £ f(d1,…,dk)=f(g1(b1,…,bn),…,

gk(b1,…,bn))=h(b1,…,bn). (Знак неравенства поставлен в силу монотонности функции f). Мы доказали, что класс М замкнут относительно суперпозиции.


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


Лемма. Пусть f(x1,…,xn) – немонотонная функция. Тогда замыкание класса K={f(x1,…,xn), q(x), i(x)} содержит n(x).


Доказательство. Поскольку f(x1,…,xn) немонотонна, то существуют наборы значений переменных a=(a1,…,an), b=(b1,…,bn) такие, что a<b, но f(a)>f(b). Неравенство f(a)>f(b) означает, что f(a)=1 и f(b)=0. Рассмотрим диаграмму частично упорядоченного множества Bn. Так как a<b, то точка а на диаграмме лежит ниже точки b. Существует восходящая цепь, соединяющая точку а с точкой b (см. рис. 2.2).


Рис. 2.2

На этой цепи найдутся соседние точки c=(c1,…,cn) и d=(d1,…,dn) такие, что c<d, f(c)=1 и f(d)=0. Поскольку c и d – соседние точки, то

c=(c1,…,ci-1,0,ci+1,…,cn) и d=( c1,…,ci-1,0,ci+1,…,cn).

Для удобства обозначений будем считать, что c1=…=ci-1=0,ci+1=…cn=1. Рассмотрим функцию g(x)=f(q(x),…, q(x),x;i(x),…,i(x)), где точка с запятой отделяет i-ю компоненту от (i+1)-ой. Ясно, что g(x) принадлежит замыканию класса K.

Далее, g(0)=f(q(0),…, q(0),0; i(0),…, i(0)=
  =f(c1,…,ci-1,0;ci+1,…,cn)=f(c)=1,
  g(1)=f(q(1),…, q(1),1; i(1),…, i(1))=
  =f(c1,…,ci-1,1;ci+1,…,cn)=f(d)=0.

Это означает, что g(x)=n(x).


Лемма доказана.

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

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

Задачи

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

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

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

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

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

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


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

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