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

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

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

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

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

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

Тема посвящена рассмотрению метода доказательства того, что формула G является логическим следствием формул F1,F2,...,Fk, который называется методом резолюций. Отметим, что задача о логическом следствии сводится к задаче о выполнимости. Действительно, формула G есть логическое следствие формул F1,F2,...,Fk тогда и только тогда, когда множество формул {F1,F2,...,Fk,ØG} невыполнимо. Метод резолюций, если говорить более точно, устанавливает невыполнимость. Это первая особенность метода. Вторая особенность метода состоит в том, что он оперирует не с произвольными формулами, а с дизъюнктами (или элементарными дизъюнкциями).

§1. Метод резолюций в логике высказываний

§2. Подстановка и унификация

§3. Метод резолюций для логики первого порядка

§4. Эрбрановский универсум множества дизъюнктов

По определению интерпретации ее областью может быть любое непустое множество М. Было бы удобно иметь одно множество в качестве области интерпретации. В случае, когда решается вопрос о выполнимости множества дизъюнктов, таким множеством является так называемый эрбрановский универсум.


Пусть S – множество дизъюнктов.


Введем следующее обозначение. Через H0 обозначим множество констант, содержащихся в S. Если S не содержит констант, то H0 состоит из одной константы, скажем а, т.е. H0={a}. Предположим, что введено множество Hi. Тогда Hi+1 есть объединение множества Hi и термов вида f(t1,…,tn), где t1,…,tnÎHi, f – символ n-местной функции, содержащейся хотя бы в одном из дизъюнктов множества S.


Определение. Множество H¥=H0ÈH1ÈÈHnÈ… называется эрбрановским универсумом множества дизъюнктов S.


Приведем три примера, которые будем использовать в дальнейшем.


Пример 1. Пусть S={P(x), ØP(x)ÚQ(f(y)), ØQ(f(a))}. Тогда


H0={a},

H1={a,f(a)},

            . . .

H¥={a,f(a)}, f(f(a)),…}.


Пример 2. Пусть S={P(x), Q(x)ÚØR(y)}. Множество S не содержит констант, поэтому H0={a},. Так как дизъюнкты из S не содержат функциональных символов, то H0=H1=H2=…=H¥={a}.


Пример 3. Пусть S={P(x), ØP(b)ÚQ(y,f(y,a))}. Тогда H¥={a, b, f(a,a), f(a,b), f(b,a), f(b,b), f(f(a,a),a),…}.


Эрбрановский универсум, как мы видим. Определяется не всем множеством дизъюнктов S, а только символами функций и константами, входящими в дизъюнкты из S.


Определение. Множество атомарных формул вида P(t1,…,tn), где t1,…,tnÎН¥, а P – символ n-местного предиката, входящий в дизъюнкты из S, называется эрбрановским базисом множества дизъюнктов S.


Для множества дизъюнктов S из примера 1 эрбрановским базисом будет множество атомарных формул B1={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}. Эрбрановским базисом множества дизъюнктов S из примера 2 будет множество B2={P(a), Q(a), R(a)}.

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


Определение. Пусть D – дизъюнкт из множества дизъюнктов S. Основным примером дизъюнкта D называется дизъюнкт, полученный из D заменой переменных на элементы эрбрановского универсума Н¥.


Пусть S – дизъюнкт из примера 1. Тогда дизъюнкт ØQ(f(a)) имеет один основной пример – сам дизъюнкт, множество основных примеров дизъюнкта ØP(x)ÚQ(f(y)) бесконечно {ØP(a)ÚQ(f(a)), ØP(f(a))ÚQ(f(a)), ØP(a)ÚQ(f(f(a))),…}. Если S – множество дизъюнктов из примера 2, то каждый из дизъюнктов этого множества S имеет один основной пример.


Как утверждалось в начале параграфа (и будет доказано в конце), для решения вопроса о выполнимости дизъюнктов в качестве области интерпретации достаточно рассматривать только эрбрановский универсум. Оказывается, можно еще ограничить и саму интерпретацию до так называемой H-интерпретации.


Определение. Пусть H¥ – эрбрановский универсум множества дизъюнктов S. Интерпретация j с областью H¥ называется H – интерпретацией множества S, если она удовлетворяет следующим условиям:

1) для любой константы с из S выполняется равенство j(с)=с,

2) если f – символ n-местной функции из S, то jf – функция, определенная на H¥ равенством

(jf)(t1,…,tn)=f(t1,…,tn)

для любых t1,…,tnÎH¥.


Если B={B1,B2,…,Bn,…} – эрбрановский базис множества дизъюнктов S, то H-интерпретацию j удобно представлять в виде множества литералов


{L1,L2,…,Ln,…},


где Li есть Bi, если j(Bi)=1, и Li=ØBi, если j(Bi)=0.

Например, если S – множество дизъюнктов из примера 1, то эрбрановскими интерпретациями будут


j1={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}

j2={P(a), Q(a), ØP(f(a)), ØQ(f(a)), P(f(f(a))), Q(f(f(a))), ØP(f(f(f(a)))),…}.

j3={P(a), ØQ(a), P(f(a)), ØQ(f(a)), P(f(f(a))), ØQ(f(f(a))),…}.


Последнее, что нужно сделать, чтобы доказать основное утверждение этого параграфа (теорему 4.5), ввести понятие H-интерпретации j*, соответствующей (произвольной) интерпретации j множества S.


Предположим, что S содержит хотя бы одну константу. Если j – интерпретация множества S с областью М, то для любого элемента h эрбрановского универсума значение j(h) определено (и является элементом множества М.)


Определение. Пусть j – интерпретация множества S с областью М. Тогда H-интерпретацией j*, соответствующей интерпретации j называется H-интерпретация, удовлетворяющая следующему условию: для любых элементов t1,…,tn эрбрановского универсума выполняется эквиваленция:


(j*P)(t1,…,tn)=1 Û (jP)(j(t1),…,j(tn))=1


для любого символа предиката P.


Приведем пример. Пусть S – множество дизъюнктов из примера 1. Напомним, что S={P(x), ØP(x)ÚQ(f(y)), ØQ(f(a))} и эрбрановский базис множества S есть B={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}. Рассмотрим интерпертацию j с областью М={1,2}, определяемую равенством j(а)=1 и таблицей 4.1.


Таблица 4.1

  jf jP jQ
1 2 0 1
2 1 1 1

(В столбцах jP и jQ цифры 0 и 1 – истинностные значения.) Тогда


j*={ØP(a), Q(a), P(f(a)), Q(f(a)), ØP(f(f(a))),…}.


Рассмотрим теперь случай, когда S не содержит констант. Пусть j – интерпретация множества S с областью М и а – константа, образующая эрбрановский универсум H¥. В этом случае значение j(а) неопределено. Для получения H-интерпретации j* расширяем функцию j на а полагая j(а) равным произвольному элементу из М. Далее поступаем так, как описано выше. Если множество М неодноэлементно, то мы можем получить не одну H-интерпретацию j*, соответствующую j. Нетрудно привести пример, когда H-интерпретаций j* столько же, сколько элементов в множестве М.

Следующее утверждение непосредственно следует из определений.


Лемма. Пусть j – интерпретация с областью М, при которой все дизъюнкты из S истинны. Тогда все дизъюнкты из S истинны при любой H-интерпретации j*, соответствующей j.


Теорема 4.5. Множество дизъюнктов S невыполнимо тогда и только тогда, когда S ложно при всех H-интерпретациях, т.е. для любой H-интерпретации множества S в S найдется дизъюнкт, который ложен при этой H-интерпретации.


Доказательство. Необходимость очевидна. Действительно, невыполнимость множества S означает, что это множество ложно при любой интерпретации. В том числе и при любой H-интерпретации. Достаточность следует из леммы, поскольку если S выполнимо, то существует хотя бы одна интепретация j, при которой все дизъюнкты из S истинны. Но тогда все дизъюнкты из S будут истинны и при H-интерпретации j*.

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

§5. Семантические деревья, теорема Эрбрана

§6. Полнота метода резолюций в логике предикатов

§7. Стратегии метода резолюций

§8. Применение метода резолюций.

§9. Метод резолюций и логическое программирование

Задачи

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

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

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

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


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

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