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

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

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

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

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

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

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

Этот и два следующих параграфа посвящены рассмотрению трех конкретных классов функций: самодвойственных, монотонных и линейных.


Определение. Функция g(x1,…,xn) называется двойственной k f(x1,…,xn), если выполняется равенство


g(x1,…,xn)=n[f(n(x1),…,n(xn)]].


Например, x×y двойственна xÚy, и наоборот. Это следует из равенств x×y=n(n(x)Ún(y) и xÚy=n(n(x)×n(y)), которые мы уже приводили. Функция x®y двойственна функции n(x)&y, поскольку n(n(x)®n(y)=n[n(n(x))Ún(y)]=n(xÚn(y)) =n(x)&y. Отметим, что первое равенство выполняется на основании закона 20, второе 19 и третье 18 и 19.


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


f(x1,…,xn)=n[f(n(x1),…,n(xn)]. (1)


Другими словами, функция самодвойственна, если она совпадает со своей двойственной.


Приведем примеры. Легко видеть, что самодвойственными функциями являются тождественная функция и отрицание: n[e(n(x))]=n[n(x)]=x=e(x), n[n(n(x))]=n(x). В то же время, произведение x×y самодвойственной не является, поскольку двойственно дизъюнкции xÚy и x×y¹xÚy. Можно показать, что никакая функция от двух переменных, существенно зависящая от каждого аргумента, самодвойственной не является. В качестве еще одного примера самодвойственной функции приведем функцию

f(x1,x2,x3)=(x1×x2)Ú(x1×x3)Ú (x1×x3).

Действительно, n[f(n(x1), n(x2), n(x3)]=
  =n[n(x1)×n(x2))Ú(n(x1)×n(x3))Ú(n(x2)×n(x3))]=
  =n[n(x1Úx2)Ún(x1Úx3))Ún(x2Úx3)]=
  =(x1Úx2)×(x1Úx3)×(x2Úx3)=
  =(x1×x1×x2)Ú(x1×x1×x3)Ú(x1×x3×x2)Ú(x1×x3×x3)Ú
  Ú(x2×x1×x2)Ú(x2×x1×x3)Ú(x2×x3×x2)Ú(x2×x3×x3)=
  =(x1×x2)Ú(x1×x3)Ú(x1×x2×x3)Ú(x1×x3)Ú
  Ú(x1×x2)Ú(x1×x2×x3)Ú(x2×x3)Ú(x2×x3)=
  =(x1×x2)Ú(x1×x3)Ú(x2×x3)Ú(x1×x2×x3)=
  =(x1×x2)Ú(x1×x3)Ú(x2×x3).

Последнее равенство выполняется на основании закона поглощения.


Отметим, что равенство (1) из определения самодвойственности равносильно равенству n(f(x1,…,xn))=f(n(x1),…,n(xn)). (2)

Класс всех самодвойственных функций обозначим буквой S. Убедимся в том, что S – замкнутый класс. Как уже отмечалось, S содержит e(x). Пусть f(x1,…,xn)ÎS и y1,…,yn – новый набор переменных. Тогда поскольку равенство f(x1,…,xn)=n[f(n(x1),…,n(xn)] выполняется для всех значений переменных x1,…,xn, то n[f(n(y1),…,n(yn)]=f(y1,…,yn). Следовательно, f(y1,…,yn)ÎS и S – замкнут относительно переименования аргументов. Возьмем теперь функции f(x1,…,xk), g1(x1,…,xn),…, gk(x1,…,xn) из S. Поскольку эти функции принадлежат S, то, используя равенство (2), получаем, что


n(f(x1,…,xk))=f(n(x1),…,n(xn)),

n(g1(x1,…,xn))=g1(n(x1),…,n(xn)),

· · ·

n(gk(x1,…,xn))=gk(n(x1),…,n(xn)).


Тогда если h(x1,...,xn)=f(g1(x1,…,xn),…,gk(x1,...,xn)),то
  h(n(x1),…,n(xn))=
  =f[g1(n(x1),…,n(xn)),…,g(n(x1),…,n(xn))]=
  =f[n(g1(x1,…,xn)),…, n(gk(x1,…,xn))]=
  =n[f(g1(x1,…,xn),…,gk(x1,…,xn))]=
  =n(h(x1,…,xn)).

В силу равенства (2), h(x1,…,xn) – самодвойственная функция. Следовательно, класс S замкнут относительно суперпозиции.


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


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


Доказательство. Поскольку f(x1,…,xn) – несамодвойственная функция, то существуют a1,…,anÎB такие, что


n[f(a1,…,an)]¹f(n(a1),…,n(an)).


Множество B содержит только два элемента. Поэтому из этого неравенства следует равенство


f(a1,…,an)=f(n(a1),…,n(an)).


Для удобства обозначений предположим, что a1,…,ak=0, ak+1,…, an=1. Тогда последнее равенство можно записать так:


f(0,…,0;1,…,1)=f(1,…,1;0,…,0),


где точка с запятой отделяет k-ый аргумент от (k+1)-го.

Рассмотрим функцию


g(x)=f(x,…,x;n(x),…,n(x)).


Заметим, что g(x) принадлежит [K]. Имеем равенства

g(0)=f(0,…,0; n(0),…,n(0))=f(0,…,0;1,…,1)=

=f(1,…,1;0,…,0)=f(1,…,1; n(1),…,n(1))=g(1).

Следовательно, g(x) – одна из констант, принадлежащая [K]. Поскольку K содержит отрицание, то и другая константа принадлежит [K].

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


В заключение параграфа рассмотрим пример решения задачи на распознавание самодвойственности: определить, будет ли функция f(x1,x2)=x2×(x2®x1) самодвойственной? (Впрочем, мы уже знаем, что f(x1,x2) несамодвойственна, но надо это доказать). Для получения ответа на вопрос составим таблицу, задающую функции f(x1,x2) и n(f(n(x1),n(x2)). (см. таблицу 2.4)


Таблица 2.4

x1 x2 x2® x1 n(x2) n(x2)®n(x1) f(x1,x2) n(f(n(x1),n(x2))
0 0 1 1 1 0 0
0 1 0 0 1 0 1
1 0 1 1 0 0 1
1 1 1 0 1 1 1

Мы видим, что f(x1,x2)¹n(f(n(x1),n(x2)), например при x1=0, x2=1. Следовательно, функция f(x1,x2) самодвойственной не является. (Для того, чтобы сделать заключение о несамодвойственности, можно было, конечно, прервать составление таблицы на второй строке.

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

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

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

Задачи

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

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

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

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

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

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


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

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