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

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

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

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

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

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

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

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

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

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

Задачи

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

1. Приведем доказательство включения [KÇL]Í[K]Ç[L]. Пусть {Mi½iÎI}

– семейство замкнутых классов, содержащих KÇL, {Kj½jÎJ} – семейство замкнутых классов, содержащих K. Тогда, поскольку KÇLÍK, то все Kj содержат KÇL, т.е.


{Kj½jÎJ}Í{Mi½iÎI}.


Отсюда следует, что Ç{Kj½jÎJ}ÊÇ{Mi½iÎI}. Это означает, что [KÇL]Í[K]. Аналогично доказывается включение [KÇL]Í[L]. Следовательно, [KÇL]Í[K]Ç[L].


2. Приведем решение задачи. Пусть K={i(x), xy, xÚy}. Функции q(x) и

n(x) не принадлежат [K], поскольку все функции из K (а следовательно, и из [K]) сохраняют единицу, а функции q(x) и n(x) единицу не сохраняют.


3. Указание. Построить таблицу, задающую функции двойственную к

f функцию и функцию g. В случаях а, в, д и е ответ положительный, в остальных случаях – отрицательный.


4. Указание. Построить таблицу, задающую функцию f и двойственную к ней. Функции n(x), (xy)Ú(xz)Ú(yz) и (xÚy)×(xÚz)×(yÚz) самодвойственны (последние две просто равны), остальные нет.


5. Указание. Рассмотреть таблицы, задающие функции, существенно зависящие от двух переменных.


6. Указание. Проставить значения функций в вершинах диаграммы

частично упорядоченного множества B3.


7. Монотонными являются функции xy+y+x, x®(y®x), (xy)Ú(xz)Ú(yz).


9. Приведем решение задачи. Класс функций {q(x), i(x), xy, xÚy}.обозначим буквой С. Пусть f(x1,…,xn) – монотонная функция. Если f(x1,…,xn) тождественно равна 0, то f(x1,…,xn)=q(x1)××q(xn). Если же эта функция тождественно равна 1, то f(x1,…,xn)=i(x1)××i(xn). Следовательно, в этих двух случаях функция f принадлежит [C]. Будем считать, что f(x1,…,xn) принимает оба значения. Рассмотрим диаграмму Bn частично упорядоченного множества Bn и в вершинах диаграммы проставим значения функции f(x1,…,xn). Поскольку функция f монотонна, то из того, что в некоторой вершине функция f принимает значение 1, то и всюду выше она принимает то же значение. (В частности, в нижней вершине диаграмма f принимает значение 0, в верхней – значение 1.) Отсюда следует, что существуют вершины диаграммы a1, a2,…,ak такие, что если f(b)=1 для некоторой вершины b, то ai£b для некоторого iÎ{1,…,k}.


Рис. 2.3

Другими словами, {aÎBn½f(a)=1}=D1ÈD2ÈÈDk, где Di={aÎBn½ai£a} (см. рис. 2.3).

Рассмотрим вектор a1. Пусть у этого вектора единицы стоят на местах i1 , i2,…,il. Для упрощения обозначений предположим, что i1=1,…, il=l. Пусть g1(x1,…,xn)=x1×x2××xl. Легко видеть, что D1={aÎBn½g1(a)=1}. Аналогичным образом существование функций g2(x1,…,xn),…, gl(x1,…,xn), таких, что D2={aÎBn½g2(a)=1},…, Dl={aÎBn½gl(a)=1}. Тогда поскольку множество {aÎBn½f(a)=1} есть объединение D1ÈÈDk, получаем равенство:


f(x1,…,xn)=g1(x1,…,xn)ÚÚgl(x1,…,xn).


Мы доказали, что замыкание класса C совпадает с М, т.е. с классом всех монотонных функций. Покажем, что С – базис М. Если из С удалить q(x) то из оставшихся функций нельзя выразить q(x), поскольку они сохраняют 1. Аналогично доказывается, что нельзя удалить i(x).

Докажем, что замыкание класса C′=C\{x×y} не содержит x×y. Предположим противное, пусть x×y выражается (с помощью суперпозиции и переименования аргументов) через функции класса C′ и пусть g(x,y) – самое короткое выражение для этой функции. (В частности это означает, что x×y=g(x,y)). Тогда g(x,y)¹q(h(x,y)), для некоторого h(x,y) поскольку в случае равенства g(x,y)=q(h(x,y)) произведение xy тождественно равно 0. Аналогично заключаем, что g(x,y)¹i(h(x,y). Следовательно, x×y=g(x,y)=g1(x,y)Úg2(x,y). Отсюда следует, что g1(0,0)=g1(1,0)=g1(0,1)=0 и g2(0,0)g2(1,0)=g2(0,1)=0, поскольку 0×0=1×0=0×1=0. Далее, так как 1=1×1=g1(1,1)Úg2(1,1), то g1(1,1)=1 или g2(1,1)=1. Это означает, что в качестве g(x,y) можно взять g1(x,y) или g2(x,y), что противоречит выбору функции g(x,y). Следовательно, x×y не принадлежит замыканию класса C\ {x×y}. Аналогично доказывается, что ÏxÚyÏ[C\{xÚy}].

Мы доказали, что {q(x), i(x), x×y, xÚy} – базис класса монотонных функций.


10. Указание. См. решение аналогичной задачи в начале §4.

Линейными являются все функции, кроме первой.


12. Приведем решение задачи 12 г. Пусть K={x+y, x«(yz)}. В силу теоремы Поста, надо в классе K найти функцию, не сохраняющую 0, функцию, не сохраняющую 1, не самодвойственную, немонотонную, нелинейную функцию. Функция x«(yz) не сохраняет 0, поскольку 0«(0×0)=1. Функция x+y не сохраняет 1. Она же несамодвойственна (см. таблицу 2.6) и немонотонна (см. рис. 2.4)


Таблица 2.6

x y x+ y n(x)+n(y) n(n(x)+n(y))
0 0 0 0 1
0 1 1 1 0
1 0 1 1 0
1 1 0 0 1

Рис. 2.4

Докажем, что функция x«(y×z) нелинейная. Предположим, что x«(y×z)=a0+a1×x+a2×y+a3×z. Составим таблицу, задающую функции из левой и правой части равенства (см. таблицу 2.7).

Таблица 2.7

x y z y×z x«(y×z) a0+a1×x+a2×y+a3×z Следствие
0 0 0 0 1 a0 a0=1
0 0 1 0 1 1+a3 а3=0
0 1 0 0 1 1+a2 а2=0
0 1 1 1 0 1 Противоречие
1 0 0        
1 0 1        
1 1 0        
1 1 1        

Полученное противоречие показывает, что x«(y×z) – нелинейная функция. (Разумеется, таблицу можно было бы ограничить первыми четырьмя строками).


13. Указание. Применить теорему Поста. В случаях г, ж, и з классы будут полными, в остальных нет.

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

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

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

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

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


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

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