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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи

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

2. Приведем соответствующие формулы:

а) x£y&Øy£x,

б) x<y&("z)(x<z&z£y®z=y),

в) ("y)(x£y),

г) ($z)("y)[z£y&("u)(z<u&u£x®u=x)]

д) (x<y&y<z)Ú(z<y&y<x).


3. Приведем соответствующие формулы:

а) ("y)(x|y),

б) z|x&z|y&("u)(u|x&u|y®u|z),

в) x|z&y|z&("u)(x|u&y|u®z|u),

г) Ø(x=1)&("y)(y|x®y=1Úy=x).


Предикаты «x – четное число» и «x меньше y» невыразимы формулой сигнатуры s. Докажем это. Пусть P – множество простых чисел. Рассмотрим отображение j:P®P такое, что j(2)=3, j(3)=2 и j(p)=p для всех простых чисел p, отличных от 2 и 3. Отображение j расширим на все множество натуральных чисел N следующим образом: Пусть n=2a3bp1g1…pkgk, где p1,…,pk – простые числа, отличные от 2 и 3. Положим:


j(n)=3a2bp1g1…pkgk и j(1)=1.


Например, j(2)=3, j(12)=18, j(42)=42, j(60)=90. Отображение j сохраняет предикат делимости. Это означает, что


u|vÛj(u)|j(v)


для любых u,vÎN. Индукцией по построению формулы можно доказать, что для любой формулы F(x1,…xn) сигнатуры s и любых натуральных чисел а1,…аn высказывание F(а1,…аn) истинно тогда и только тогда, когда истинно F(j(a1),…,j(an)). Предположим теперь, что предикат «x – четное число» определяется формулой G(x). Тогда высказывание G(2) истинно тогда и только тогда, когда G(3) истинно. Но G(2) истинно, а G(3) ложно. Полученное противоречие доказывает, что предикат «x – четное число» невыразим формулой сигнатуры s. Аналогично доказывается невыразимость предиката «x меньше y».


4. Соответствие формул предикатам содержится в следующей таблице:


Формула а б в г д
Предикат в б а д г

5. Приведем соответствующие формулы:

а) ($x)P(x),

б) ("x)("y)(P(x)&P(y)®x=y),

в) ($x)[P(x)&("y)P(y)®x=y)],

г) ($x)($y)[x¹y2&P(x)&P(y)],

д) ("x)("y)("z)[P(x)&P(y)&P(z)&®x=yÚx=zÚy=z],

е) ($x)($y)[x¹y&P(x)&P(y)&("z)(P(z)®x=zÚy=z)].


6. Приведем соответствующие формулы:

а) pl(x)&pl(y)&($z)(p(z)&zÎx&zÎy),

б)pl(x) )&pl(y)&[( $z)p(z)&zÎx&zÎy)®($u)(l(u)&uÎx&uÎy)],

в)l(x)&l(y)&($z)(p(z)&zÎx&zÎy),

г) l(x)&l(y)&($u)(pl(u)&xÎu&yÎu)&Ø($v)(p(v)&vÎx&vÎy),

д)l(x)&l(y)&l(z)&($u)($v)($w)[p(u)&p(v)&p(w)&uÎx&uÎy&vÎx&vÎz&wÎy&wÎz&u¹v&u¹w&v¹w].


7. Приведем решение залачи 7.3. Пусть T(x) означает «x – таможенник», B(x) –»x въезжает в страну», Л(x) – «x высокопоставленное лицо», H(x) – «x способствует провозу наркотиков», O(x,y) – «x обыскивает y». Тогда рассуждение 7.3 может быть переведено на язык логики первого порядка


F1=("x)[B(x)&ØЛ(x)®($y)(T(y)&O(y,x))],

F2=($x)[B(x)&H(x)&("y)(O(y,x)®H(y))],

F3=Ø($x)[Л(x)&H(x)),

G=($x)(T(x)&H(x).


8. Формуле F(x,y) соответствуют следующие предикаты:

а) «x меньше y и между ними находится в точности один элемент»,

б) «x меньше или равно y»,

в) «x=1 и y=4»,

г) «x¹x», т.е. тождественно ложный предикат.


9. Формуле F(x) соответствуют следующие предикаты:

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

б) «x – равно 2»,

в) «x равно 1».


10. Формуле F(x) соответствуют следующие предикаты:

а) «x – равно 0»,

б) «x – равно 1»,

в) «x – равно 1».


11. Формуле F(x) соответствуют следующие предикаты:

а) «x – равно 2»,

б) «x – равно 3»,

в) «x – равно 2».

Предикат «x=4» соответствует формуле F(x) при интерпретации P(x)=«x=4», D(x,y)=«x больше или равно y», а предикат «x – четное число» соответствует этой формуле при интепретации P(x)=«x – четное число» и D(x,y)=«x=x».


12. Формулы равносильны только в случаях г и е.


13. Приведем решение задачи 13в. Пусть


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

G=("x)($u)[P(x,u)®Q(u)].


Применим к формуле F последовательно законы 20 и 26, получим формулу


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


Затем, пользуясь законом 33, в формуле ($y)ØP(x,y) y заменим на u, а в формуле ($z)(P(x,z)&Q(z)) z заменим тоже на u. Формула F1 после этих замен превратится в формулу


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


Применив закон 23, вынесем квантор вперед:


F3=("x)($u)[ØP(x,u)Ú(P(x,u)&Q(u))]


Используя последовательно законы 12,16 и 1, получим формулу:


F4=("x)($u)[ØP(x,u)ÚQ(u)].


Осталось заметить, что в силу закона 20 формула ØP(x,u)ÚQ(u) равносильна формуле P(x,u)®Q(u). Равносильность F и G доказана.


14. Указание. Воспользоваться алгоритмом приведения к ПНФ (см.§6).


15. Указание. Воспользоваться алгоритмом приведения к СНФ (см.§6).


16. Приведем решение задачи 16в. Надо построить интерпретацию, при которой формулы из K истинны, а формула из G ложна. Рассмотрим множество M={1,2,3} и интерпретацию j:(jP)(x)=«x=1», (jQ)(x)=«x=2», (jR)(x)=«x=1 или x=2», (jS)(x,y)=«x=1 и y=2». Легко проверить, что j – искомая интерпретация.


17. Логическим следствием будет только утверждение б.


18. Приведем решение задачи 18.1. Пусть St(x) означает, что «x – студент

нашей группы», M(x) – «x – член клуба «Спартак»«, Sp(x) – «x занимается спортом». Тогда рассуждение 18.1 переводится на язык логики первого порядка последовательностью формул:


F1=("x)(St(x)®M(x)),

F2=($x)(M(x)&Sp(x)),

G=($x)(St(x)&Sp(x)).


Рассмотрим множество M={1,2,3} и интерпретацию j: (jSt)(x)=«x=1», (jM)(x)=«x=1 или x=2», (jSp)(x)=«x=2». Легко видеть, что j(F1)=j(F2)=1 и j(G)=0.

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

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

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

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


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

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