«Ш. И. ГАЛИЕВ МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ УЧЕБНОЕ ПОСОБИЕ Казань 2002 2 УДК 6 Галиев Ш. И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ им. А. Н. Туполева. 2002. - 270 с. ISBN ...»

Замечание 2. Равносильности (2.38), (2.40) и (2.41) показывают, что при вынесении кванторов за скобками получили не один квантор, как это было ранее, а уже два квантора.

Для рассмотренного выше примера, проведя переименования переменных, а затем используя равносильность (2.41) легко получить, что Также нетрудно получить, что Таким образом, из формул (xB(x))xC(x) и (xB(x))&xC(x) мы все же вынесли кванторы за скобки, но за скобками оказались уже два квантора с различными переменными. Сравнивая равносильности (2.46) и (2.47) с равносильностями (2.27) и (2.28), видим, что в последних кванторы вынесены без всякого изменения и удвоения их.

Из равносильностей (2.33) - (2.36) и (2.38)-(2.41) очевидным образом следует, что для любой формулы можно добиться, чтобы сначала были записаны кванторы, а затем формула, не имеющая кванторов, т.е. "вынести" кванторы за скобки. Здесь применены кавычки, т.к. для получения равносильных формул кванторы выносятся за скобки, возможно, оставаясь неизмененными, либо меняясь на двойственные, либо выносятся за скобки только после переименования связанных переменных (в самом кванторе и области его действия). При этом переименование переменных осуществляется по правилам, описанным в предыдущем параграфе.

Формула вида:

кванторов, а формула В не содержит кванторов называется формулой в предваренной нормальной форме или в пренексной нормальной форме.

Для формулы А Q1Q2...QnВ совокупность кванторов Q1,Q2,...,Qn называется префиксом формулы А, а формула B – матрицей формулы А.

Будем дополнительно считать, что матрица приведена к конъюнктивной нормальной форме Из доказанных выше теорем легко следует следующая теорема.

Теорема 2.9. Для каждой формулы логики предикатов существует равносильная ей формула в предваренной нормальной форме.

1. Понятие предиката.

2. Кванторы. Использование кванторов и предикатов для символизации 3. Термы, элементарные формулы и формулы логики предикатов.

4. Свободные и связанные переменные. Замкнутые формулы. Замыкание 5. Интерпретация, выполнимые, истинные и ложные в данной интерпретации формулы.

6. Модель.

7. Свойства формул в данной интерпретации.

8. Логически общезначимые формулы. Выполнимые формулы.

9. Логическое следствие в логике предикатов. Равносильные формулы.

10. Правила перенесения отрицания через кванторы.

11. Можно ли переставлять рядом стоящие одноименные кванторы?

12. Можно ли переставлять рядом стоящие разноименные кванторы?

13. Определение предваренных нормальных форм. Для каждой ли формулы логики предикатов существует предваренная нормальная 14. Алгоритмы нахождения предваренных нормальных форм.

Символизация языка. Предикаты, кванторы 1. Какие из следующих выражений являются предикатами:

а) число x – простое число;

д) все подобные треугольники равны;

е) x2+y2x)((x>1)(x2)&(x>3))(22)&(x1)(xy;

ж) x(sinx>1)(x y).

18. Пусть все приведенные ниже предикаты определены на множестве всех действительных чисел. Изобразить графически области изменения свободных переменных, при которых следующие предикаты принимают значение И:

в) M=(0,1], 2). Истинна, ложна или выполнима формула xA(f1(x,y),f2(f1(x,y))) в интерпретации: M=(-,); f2(z): z2; f1(x,y): x+y; A(x,y): x=y.

20. Предикат A(x,y) задан на множестве M={1,2,3} таблицей Определить истинностное значение приведенных ниже формул при каждом значении свободной переменной:

21. Пусть M={1,2,3} и на этом множестве M заданы предикаты A(x,y) и B(x) таблицами:

Определить истинностное значение формул:

д) xy(B(y)A(x,y)).

22. Пусть формула В не содержит свободных переменных, а P(x) – одноместный предикат. Для области M, состоящей из двух элементов, построить таблицы истинностных значений формул:

23. Предикат P(x,y) задан на множестве целых положительных чисел бесконечной таблицей, в которой значения И стоят в первой строке, первом столбце и по диагонали. Выяснить, следующие формулы принимают значения И:

24. Пусть предикат P(x,y) тот же, что и в предыдущей задаче. Выяснить, принимают ли значение И следующие формулы:

д) xyP(x,y)yP(5,y); е) x(yP(y,y)P(x,x));

25. Истинна ли формула xA1 ( x ) yA1 ( y ) :

а) для произвольной одноэлементной области; б) для произвольной двухэлементной области.

26. Перед следующими предикатами, определенными на множестве всех действительных чисел, поставьте соответствующие кванторы так, чтобы получить истинное высказывание;

27. Выяснить, выполнима ли формула xyP(x,y,z) в интерпретации:

M=(-,); P(x,y,z):x+y< z. Является ли эта формула истинной для данной интерпретации?

28. Для формулы xP(x,y)P(y,y) найдите интерпретацию, в которой эта формула выполнима.

29. Истинна ли формула xP(x,y)P(y,y) на произвольной двухэлементной области.

Выполнимые формулы. Логически общезначимые формулы. Равносильные формулы 30. Показать, что формула xyA(x,y)yxA(x,y) не является логически общезначимой. Выполнима ли эта формула?

31. Является ли выполнимой формула 32. Доказать, что, если формула логики предикатов А, содержащая свободно только переменную x, является логически общезначимой, то формула xA также является логически общезначимой, и обратно.

Обобщить сформулированное утверждение на формулы, содержащие любое конечное число свободных переменных.

33. Если формула логики предикатов А, содержащая только свободную переменную x, является логически общезначимой, то xA также является логически общезначимой. Верно ли обратное?

34. Доказать, что а) если формула логики предикатов АВ является логически общезначимой, то формулы xAxB и xAxB также являются логически общезначимыми;

б) если формула логики предикатов АВ является логически общезначимой, то формулы xAxB и xAxB также являются логически общезначимыми.

35. Показать, что формула xy(Р(x) Р(y)) является истинной для одноэлементной области и только для нее, здесь Р является одноместной предикатной буквой.

36. Докажите, что формула xyAyxA является логически общезначимой.

37. Является ли выполнимой формула xyP(x,y)yxP(f(x),y)? Будет ли эта формула логически общезначимой?

38. 1). Являются ли истинными или выполнимыми для произвольной двухэлементной области следующие формулы (А и В не содержат свободных переменных):

а) x(AB(x))(AxB(x)); б) x(A(x)B)(xA(x)B);

в) x(A(x)B)(xA(x)B); г) x(AB(x))(AxB(x)).

2). Являются ли формулы а) – г) логически общезначимыми или нет?

39. Являются ли выполнимыми следующие формулы:

а) xyz(A(x,x)&(A(x,z)A(x,y)A(y,z))) xyA(x,y);

б) xyz(A(x,x)&A(y,x)&(A(y,z))A(x,y))).

40. Пусть А не содержит свободных переменных, P, Q – одноместные предикатные буквы. Выяснить, являются ли логически общезначимыми следующие формулы:

1) A&xQ(x)x(A&Q(x));

2) A&xQ(x)x(A&Q(x));

3) xP(x)&xQ(x)x(P(x)&Q(x));

4) xP(x)xQ(x)x(P(x)Q(x));

5) xP(x)xQ(x)x(P(x)Q(x));

6) xP(x)&xQ(x)x(P(x)&Q(x));

7) xP(x)xQ(x)x(P(x)Q(x));

8) x(P(x)&Q(x)) xP(x)&xQ(x).

41. Пусть А не содержит свободных переменных P, Q - одноместные предикатные буквы. Какие из следующих формул являются логически общезначимыми:

1) x(P(x)A)(xP(x)A); 2) x(P(x)A)(xP(x)A);

3) x(P(x)A)(xP(x)A); 4) x(AP(x))(AxP(x));

42. Какие из приведенных ниже формул являются выполнимыми, а какие из них логически общезначимыми (P, Q – одноместные предикатные буквы):

1) x(P(x)Q(x))xP(x)xQ(x);

2) x(P(x)Q(x))x(P(x)& xQ(x));

3) (xP(x)xQ(x))x(P(x) Q(x));

4) x(P(x)Q(x))(xP(x))xQ(x)).

43. Выяснить, являются ли равносильными следующие пары формул (P, Q – одноместные предикатные буквы, А – произвольная формула, имеющая указанные аргументы):

г) xy(P(x)Q(y)) и xy(P(y)Q(x));

44. 1). Для следующих формул найти равносильные формулы, не содержащие кванторов вне скобок (внести кванторы под скобки):

а) xy(A(x)B(x,y)); б) xy(A(x)B(y));

в) xy(A(x)B(y)); г) xy(B(x,y)A(x)).

2). Для следующих формул найти равносильные формулы, в которых относится только к элементарным формулам:

а) x(y(А(x)В(y)));

б) x(yА(x,y,z)uВ(x,u))&tv(С(t)D(v));

в) xz(А(x)В(z));

г) yx(А(x)&В(y))zС(x,y,z).

45. Пусть A(x,y) двухместный предикат на множестве всех вещественных чисел. Через MA обозначим область истинности предиката A(x,y), т.е.

множество тех точек (x,y) плоскости R2, для которых A(x,y)=И. Рассмотрите предикаты xA(x,y) и x A(x,y) и выясните, как связаны области истинности этих предикатов с множеством MA Формула Q1x1Q2x2…QnxnВ, где Qixi квантор всеобщности или существования, xi и xj различны, если ij и В не содержат кванторов, называется формулой в предваренной нормальной форме (иногда – пренексной нормальной формой). Сюда относится и случай n=0, когда вообще нет кванторов.

46. 1). Привести к предваренным нормальным формам формулы из предыдущей задачи.

2). Привести к предваренным нормальным формам следующие формулы:

а) x(A(x)B(x,y))((yA(y))zB(y,z));

б) xB(x,y)(A(x) zB(x,z));

в) x(yzC(x,y,z)A(x))xA(x);

г) xA(x)zyxC(x,y,z).

47. Привести к предваренным нормальным формам следующие формулы:

в) xу(z(А(x,y)&В(y,z)) vС(x,y,v));

г) x(А(x) yВ(x,y));

д) x(А(x) yВ(x,y));

е) x((уА(x,у)) (zВ(z) С(x)));

ж) xу(zА(x,y,z)&(uВ(x,u) vС(y,v))).

Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ § 1. Логическое следствие и проблема дедукции в логике высказываний Пусть А и В пропозициональные формы (формулы логики высказываний). Считаем, что В логически следует из А, если для каждой совокупности значений пропозициональных букв, при которых А=И форма В тоже принимает значение И. В этом случае записываем и читаем: «из А логически следует В» или «В является логическим следствием из А».

Легко доказать следующую теорему.

Теорема 3.1. Если А В и В С, то А С.

Запись А в логике высказываний означает, что А является тавтологией (общезначимой). Докажем следующую теорему.

Теорема 3.2. А В тогда и только тогда, когда АВ.

Доказательство. Построим таблицу истинности для АВ. Пусть имеем, что А В, тогда в каждой строке таблице, где А=И будет В=И, следовательно, АВ тавтология, то есть АВ. Если же имеем АВ, то в таблице истинности для АВ всюду, где А=И должно быть В=И, следовательно получим А В.

Пропозициональная форма В называется логическим следствием пропозициональных форм А1,А2,…,Аm, m1, если для каждой совокупности значений пропозициональных букв при которых формы А1, А2,…,Аm одновременно равны И форма В тоже принимает значение И. В этом случае записываем:

Выяснение будет ли В логическим следствием из А1, А2,…,Аm, m1, называют проблемой дедукции.

Очевидно, что имеет место следующая теорема.

Теорема 3.3. Для произвольных формул логики высказываний А1,А2,…,Аm, m1, имеют место соотношения:

А1,А2,…,Аm А1&А2&…&Аm, А1,А2,…,Аm Аi для любого i, 1 i m.

Теорема 3.4. Если формула А1&А2&…&Аm& В является противоречием, тогда В является логическим следствием из А1,А2,…,Аm, т.е.:

Доказательство. Пусть формула (3.4) является противоречием, тогда ее отрицание является тавтологией, т.е. имеем:

(А1&А2&…&Аm& В).

Очевидно, что имеем (А1&А2&…&Аm& В) (А1&А2&…&Аm)В Следовательно, утверждение (3.6) можно записать в виде:

(А1&А2&…&Аm) В.

Из (3.7) по теореме 3.2 получаем, что (А1&А2&…&Аm) В.

Теперь используя утверждение (3.2) теоремы 3.3 и утверждение (3.8) получим требуемое утверждение (3.5). Теорема доказана.

Используя утверждения (3.2) и (3.3) теоремы 3.3, можно получать следствия из заданного множества формул следующим образом. Для заданного множества формул А1, А2,…,Аm, m1, строим их конъюнкцию:

С=А1&А2&…&Аm. Для С находим с.к.н.ф.: С= D1&D2&…&Dk, здесь Di, 1ik, элементарные суммы (дизъюнкты). Теперь по указанной теореме 3. получаем, что каждый дизъюнкт Di, 1 i k, а также их конъюнкции являются следствиями из А1, А2,…,Аm, m1, т. е. имеем:

А1, А2,…,Аm Di для любого i, 1 i k;

А1, А2,…,Аm Ds1 & Ds 2 &... & Ds r, для любого r, 1 r k и любых s1, s2,…,sr, 1 s1, s2,…,sr k.

Заметим, что для формул логики предикатов понятие логического следствия из данной формулы (данных формул) введено в 6 – ом параграфе второй главы. Нетрудно убедиться, что теоремы 3.1 - 3.4 остаются в силе и для формул логики предикатов, в частности, теорема 3.2 для формул логики предикатов уже доказана, см. теорему 2.1.

§ 2. Резольвента дизъюнктов логики высказываний Пропозициональные буквы с отрицанием либо без отрицания, входящую в элементарную сумму (дизъюнкт), называют литералами (литерами) логики высказываний.

Литеры L и L называются контрарными. Так, например, в дизъюнктах D1=P Q и D2= PQS литеры P и P контрарные. Также контрарные литеры Q и Q.

Пусть для двух дизъюнктов D1 и D2 существует литера L1 в D1, которая контрарна литере L2 в D2. Вычеркнув L1 и L2 из D1 и D2 соответственно, построим дизъюнкцию оставшихся частей D1 и D2. Полученный таким образом дизъюнкт называется (бинарной) резольвентой D1 и D2, который часто обозначают через R.

Примеры. 1. Пусть D1=PQ, D2= PT, тогда R=QT.

2. Пусть D1=P, D2= PQ (D2~PQ), тогда R=Q, иначе из P и PQ получаем Q.

3. Пусть D1= PQ (D1=PQ), D2= QT (D2=QT), тогда R= PT (R=PT). Иначе из PQ и QT получаем PT.

Теорема 3.5. Пусть для дизъюнктов D1 и D2 существует резольвента R.

Тогда R есть логическое следствие из D1 и D2.

Доказательство. Пусть D1=PD1*, D2= P D2*, где Di* оставшаяся часть дизъюнкта Di, i=1,2. Докажем, что D1,D2 D1*D2*. Выпишем всевозможные наборы истинностных значений букв входящих в D1 и D2.

Выберем набор, положим k-ый, на котором D1=И и D2=И. Допустим, что на этом k-ом наборе буква P принимает значение И, тогда P=Л, поэтому должно быть D2*=И, следовательно D1*D2*=И. Таким образом из истинности D1 и D2 получили истинность D1*D2*. В случае если на k-ом наборе P=Л, то D1*=И и вновь получаем, что из истинности D1 и D2 следует истинность D1*D2*. В силу произвольности выбранного набора получаем, что из истинности D1 и D2 следует истинность для D1*D2*, что и требовалось.

§ 3. Метод резолюций в логике высказываний Рассмотрим задачу выяснения будет ли В логическим следствием из А1,А2,…,Аm, то есть истинна ли следующая запись:

А1,А2,…,Аm В.

В § 1 данной главы показано, что эта задача сводится к выяснению невыполнимости формы С=А1&А2&…&Аm& В.

Найдем для формулы С ее к.н.ф., то есть получим конъюнкцию дизъюнктов: С=D1&D2&…&Dk.

Каждое слагаемое дизъюнкта является литералом.

Множество дизъюнктов {D1,D2,…,Dk} считается невыполнимым тогда и только тогда, когда формула С невыполнима.

Методом резолюций называется последовательное получение бинарных резольвент из данных дизъюнктов и вновь получаемых дизъюнктов. Пусть, например, даны дизъюнкты Используя D1 и D2 затем D1 и D3, получим резольвенты Затем из D3 и D4 получим пустой дизъюнкт. Пустой дизъюнкт будем обозначать через.

Можно доказать следующую теорему.

Теорема 3.6 (полнота метода резолюций). Множество S дизъюнктов невыполнимо тогда и только тогда, когда существует вывод пустого дизъюнкта из S (имеется в виду, что выводом является применение метода резолюций).

Существует много различных подходов к построению вывода с помощью метода резолюций. Рассмотрим некоторые из них: метод насыщения уровня, стратегию вычеркивания, лок-резолюцию и один метод для дизъюнктов специального вида.

Ранее был введен метод резолюций и приведена теорема, утверждающая полноту метода резолюций. Пусть имеем множество дизъюнктов S={D1,D2,…,Dk}. Процедура получения бинарных резольвент неоднозначна, ибо можно сравнивать D1 и D2, затем D1 и D3 или как-то иначе.

Рассмотрим метод насыщения уровня. Он состоит в вычислении всех резольвент всех пар дизъюнктов из S, добавлении этих резольвент к множеству S, вычислении всех следующих резольвент и повторении этого процесса, до тех пор пока не найдется пустой дизъюнкт. Это значит, мы порождаем S0,S1,S2,S3,…, где S0=S, а