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

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

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

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

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

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.

§1. Предикаты и операции над ними

§2. Формулы логики первого порядка

§3. Интерпретация в логике первого порядка

§4. Равносильность, законы логики первого порядка

§6. Логическое следствие

§7. Нормальные формы

Как и в логике высказываний, в логике первого порядка вводятся нормальные формы. Мы рассмотрим две из них: предваренную нормальную и сколемовскую нормальную формы.


Определение. Формула G имеет предваренную нормальную форму (сокращенно: ПНФ), если

G(Q1,x1)…(Qn,xn)H,

где Q1,…,Qn кванторы, а формула H не содержит кванторов.

Например, формула ("x)($y)(P(x,y)&ØQ(y)) имеет предваренную нормальную форму, а формула Ø("x)(T(x)&S(x,y)) не имеет.


Теорема 3.3. Для всякой формулы F существует формула G, равносильная F и имеющая предваренную нормальную форму.

Доказательство теоремы легко следует из анализа алгоритма приведения к ПНФ.


Алгоритм приведения к предваренной нормальной форме

Шаг 1. Используя законы 21 и 20, исключить эквиваленцию и импликацию.


Шаг 2. Занести отрицание к атомарным формулам, пользуясь законами 17-19 и 26-27.


Шаг 3. С помощью законов 22-23, 28-31 вынести кванторы вперед, используя при необходимости переименование связанных переменных (законы 32-33).


Рассмотрим пример. Пусть


F=("x)P(x)®($y)("z)(P(y)&Q(y,z)).


Выполнив шаг 1 (с помощью закона 20), получим формулу


F1=Ø("x)P(x)Ú($y)("z)(P(y)&Q(y,z)).


С помощью закона 26 перейдем к формуле


F2=($x)ØP(x)Ú($y)("z)(P(y)&Q(y,z)).


Тем самым, шаг 2 также выполнен. Применим закон 30 слева направо Q1=$, Q2=$, u=y, получим формулу


F3=($x)($y)[ØP(x)Ú("z)(P(y)ÚQ(y,z))].


(Пользуемся тем, что ØP(x) не содержит y, а ("z)(P(y)&Q(Y,z)) не содержит х. Так как формула ØP(x) не содержит z, то применение закона 26 слева направо дает формулу


F4=($x)($y)("z)[ØP(x)ÚÚ(P(y)&Q(y,z))].


Это и есть искомая формула, имеющая ПНФ и равносильная формуле F.


В предыдущем примере выполнение шага 3 можно организовать по-другому. В формуле F2 связанную переменную y заменим на переменную х (закон 33), получим формулу


F3/=($x)ØP(x)Ú($x)("z)(P(x)&Q(x,z)).


Используя закон 23, перейдем к формуле


F4/=($x)[ØP(x)Ú("z)(P(x)&Q(x,z))].


Затем, как и в предыдущем абзаце, с помощью закона 28 вынесем квантор по z за квадратную скобку. Получим формулу


F5/=($z)("z)[ØP(x)Ú(P(x)&Q(x,z)].


Формула F5/, как и формула F4, имеет предваренную нормальную форму и равносильна формуле F. В некоторых ситуациях формула F5/ предпочтительнее формулы F4, поскольку содержит меньше кванторов. (Кстати, бескванторную часть формулы F5/ можно упростить).

Перейдем к изучению сколемовской нормальной формы. Отметим вначале, что в логике первого порядка понятие конъюнктивной нормальной формы вводится точно так же, как и в логике высказываний. Сохраняется полностью алгоритм приведения к КНФ и утверждение теоремы 1.3.


Определение. Формула G имеет сколемовскую нормальную форму (сокращенно: СНФ), если

G=("x)…("xn)H,

где формула Н не содержит кванторов и имеет конъюнктивную нормальную форму.

Например, формула ("x)[P(x)Ú(P(y)&Q(x,y)] имеет сколемовскую нормальную форму, а формулы ("x)($y)Q(x,y), ("x)[P(x)&(P(y)ÚQ(x,y)] не имеют.

В отличие от предыдущего случая предваренной нормальной формы мы здесь вначале рассмотрим алгоритм приведения к СНФ, а затем сформулируем теорему.


Алгоритм приведения к сколемовской нормальной форме

Шаг 1 – Шаг 3 – те же, что и в предыдущем алгоритме.


Шаг 4. Бескванторную часть привести к конъюнктивной нормальной форме (алгоритм описан в §5 темы 1).


Шаг 5. Исключить кванторы существования. Этот шаг изложим на примере. Пусть после выполнения четвертого шага имеем формулу


F=($x)("y)($z)("u)($v)H(x,y,z,u,v),


где Н – не содержит кванторов. Предположим, что формула не содержит константы с, символов одноместной функции f и двухместной функции g. Тогда в формуле Н заменим х на с, z – на f(y), v заменим на g(y,u). Все кванторы существования вычеркнем. Получим формулу


G=("y)("u)H(c,y,f(y),u,g(g,u)).


Это и есть результат выполнения шага 5.


Приведем пример приведения к СНФ. Пусть


F=($x)("y)[P(x,y)®($z)(Q(x,z)&R(y))].


Применяя законы 20 и 23, получаем формулу


F1=($x)("y) )($z)[ØP(x,y)Ú(Q(x,z)&R(y))].


Она имеет предваренную нормальную форму. Используя закон 12 приводим бескванторную часть к КНФ:


F2=($x)("y) )($z)[ØP(x,y)Ú(Q(x,z)&(ØP(x,y)Ú(R(y))].


Сделаем подстановку x=a, z=f(y), получим искомую формулу


G=("y)[(ØP(a,y)ÚQ(a, f(y)))&(ØP(a,y) )ÚR(y))].


Теорема 3.4. Для всякой формулы F существует формула G, имеющая сколемовскую нормальную форму и одновременно выполнимая (или невыполнимая) с F.


Доказательство. Пусть G – результат работы алгоритма приведения к СНФ. То, что результатом работы алгоритма является формула в сколемовской нормальной форме, ясно из описания алгоритма. Формула, которая получается после выполнения шагов 1-4 равносильна исходной, и в частности, одновременно выполнима или не выполнима.

Проанализируем шаг 5. Предположим вначале, что исключается квантор существования, впереди которого нет кванторов общности. Можно считать, что это первый квантор в записи формулы; т.е. E(u1,…,un)=($y)E′(y,u1,…,un). (Формула E′ может содержать кванторы.) Рассмотрим интерпретацию j с областью М, при которой формула E выполнима. Выполнимость означает, что найдутся элементы а1,…,anÎM такие, что высказывание (jE)(a1,…,an) или (что тоже самое) высказывание ($y)(jE′)(y,a1,…,an) истинно. Отсюда следует, что существует элемент bÎM такой что высказывание (jE′)(b,a1,…,an) также истинно. Исключение квантора существования по y на пятом шаге приводит к формуле D=E′(c,u1,…,un), где c – константа, отсутствующая в E′. Расмотрим интерпретацию y, которая совпадает с j на всех символах предикатов и функций, входящих в запись формулы F, и y(с)=b. Тогда (yD)(a1,…,an)=(jE′)(b,a1,…,an). Мы доказали, что если формула E выполнима, то выполнима и формула D.

Предположим теперь, что выполнима формула D(u1,…,un)=E′(c,u1,…,un). Это означает, что существует интерпретация y с областью М и элементы а1,…,anÎM такие, что высказывание (yE′)(y(c),a1,…,an) истинно. Но отсюда следует истинность высказывания ($y)(yE′)(y,a1,…,an). Следовательно, формула E(u1,…,un) выполнима. Мы доказали, что из выполнимости формулы D следует выполнимость формулы E.

Рассмотрим теперь случай, когда исключается квантор существования, впереди которого есть k кванторов общности, т.е.


E(u1,…,un)=("x1)…("xk)($y)E/(x1,…,xk,y,u1,…,un).


(Формула E/ может содержать кванторы). Исключение квантора по у на шаге 5 приведет к формуле


D(u1,…,un)>("x1)…("xk)E(x1,…,xk,f(x1,…,xk),u1,…,un),


где f – символ k–местной функции, не содержащийся в Е. Предположим, что формула Е выполнима. Выполнимость означает существование интерпретации j областью М и элементов a1,…,anÎM таких, что высказывание (jE(a1,…,an) истинно. Истинность этого высказывания означает, что для любых элементов x1,…,xkÎM найдется элемент yÎM такой, что высказывание E/( x1,…,xk,y,a1,…,an) истинно. Если для данных элементов x1,…,xk таких элементов y несколько, то зафиксируем один. Тем самым мы определили на М функцию i:Mx…xM®M такую, что высказывание


(jE′)(x1,…,xk,i(x1,…,xk),a1,…,an


истинно для всех x1,…,xkÎM. Рассмотрим интерпретацию y, которая совпадает с j на всех символах функций и предикатов, входящих в запись формулы Е, и (yf)( x1,…,xn)=i(x1,…,xn). Тогда


(yD)(a1,…,an)=("x1)…("xk)(jE/)(x1,…,xk,i(x1,…,xk),a1,…,an),


последнее высказывание, как мы видели истинно. Следовательно, формула D(u1,…,un) выполнима. Мы показали, что из выполнимости формулы Е следует выполнимость формулы D.

Пусть выполнима формула D. Это означает, что существует интерпретация y с областью М и элементы a1,…,anÎM такие, что высказывание (yD)(a1,…,an) или (что то же самое) высказывание ("x1)…("xk)(yE/)( x1,…,xk,(yf)(x1,…,xk),a1,…,an) истинно. Отсюда следует, что для любых x1,…,xk найдется y (равный (jf)( x1,…,xk)) такой, что высказывание (yE/)(x1,…,xk,y,a1,…,an) истинно. Следовательно, истинно высказывание ("x1)…("xk)($y)(yE/)( x1,…,xk,y,a1,…,an), т.е. высказывание (yE)(a1,…,an). Мы доказали, что из выполнимости формулы D следует выполнимость формулы Е.

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

§8. Невыразимость в логике первого порядка

§9. Многосортная логика первого порядка

Задачи

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

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

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

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

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


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

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