Практическое занятие 1 «Логика высказываний и предикатов»

1. Теоретические вопросы

1. Понятие высказывания. Атомы. Логические связки.

2. Формулы логики высказываний. Высказывательные формы.

3. Интерпретация формул логики высказываний. Общезначимые, противоречивые и выполнимые формулы логики высказываний.

4. Логические функции и формулы логики высказываний.

5. Аксиомы и основные тождества логики высказываний (с доказательством).

6. Нормальные формы формул логики высказываний.

7.Алгоритмы приведения формул к СДНФ и СКНФ.

8. Логические следствия. Теоремы о логических следствиях. Понятие теоремы в логике высказываний.

9. Определение n-местного предиката. Предметная область и множество истинности предиката..

10. Определение равносильности предикатов. Тождественно истинные и тождественно ложные предикаты.

11. Алфавит языка предикатов. Кванторы всеобщности и существования.

12. Понятие “терма” и формулы логики предикатов.

13. Интерпретация формул в логике предикатов.

14. Интерпретация формул логики предикатов, заданных в различной форме.

15. Общезначимые, противоречивые и выполнимые формулы логики предикатов.

16. Понятие исчисления предикатов. Полуразрешимость исчисления предикатов. Теорема Эрбрана.

17. Аксиомы логики предикатов (с доказательством).

18. Аксиомы переноса квантора через отрицание.

19. Вынос квантора за скобки.

20. Переименование связанных переменных в формулах логики предикатов.

21. Приведенные и предваренные нормальные формы формул логики предикатов.

22. Алгоритм получения предваренной нормальной формы формул логики предикатов.

23. Сколемовские стандартные формы формул логики предикатов.

24. Алгоритм элимирования кванторов существования в формулах логики предикатов.

25. Множество дизъюнктов формы Сколема.

26. Резолютивный вывод в исчислении высказываний. Понятие резолюции и резольвенты.

27. Исчисление высказываний с помощью метода резолюций.

28. Понятие подстановки и унификации в методе резолюций исчисления предикатов.

29. Понятие наибольшего общего унификатора для множества дизъюнктов.

30. Алгоритм унификации в методе резолюций исчисления предикатов. Теорема унификации.

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

2. Примеры решения типовых задач

Задача 1.Доказать выполнимость формулы логики высказываний:

.

Решение.Формула называется выполнимой, если существует хотя бы один такой набор значений истинности простейших элементарных высказываний (символов), при которых эта формула принимает значение И (истина).

Самый простой метод решения задачи – построить таблицу истинности данной формулы. В этом случае формула интерпретируются как логическая функция f(Q, P, R), определенная на множестве {И, Л}, со значениями в этом же множестве,полученная с помощью логических операций: инверсии (), конъюнкции (& ), дизъюнкции () и импликации ().

Таблица 1

Q	P	R	P&Q	PR			f(Q,P,R)
И	И	И	И	И	И	Л	Л
И	И	Л	Л	И	Л	Л	Л
И	Л	И	Л	И	Л	Л	Л
И	Л	Л	Л	Л	Л	Л	Л
Л	И	И	И	И	И	И	И
Л	И	Л	Л	И	И	И	И
Л	Л	И	Л	И	И	И	И
Л	Л	Л	Л	Л	И	Л	Л

Как следует из табл.1, функция f(Q,P,R) принимает значение И на трех наборах < Л, И, И>, <Л, И, Л>, <Л, Л ,И>. Следовательно, эта функция выполнима.

По другому к этому же выводу можно прийти, приведя исходную формулу к СДНФ:

Kаждый из трех конъюнктов принимает значение И на одном из трех наборов <Л, И, И>, <Л, И, Л>, <Л, Л, И>.

Задача 2.Доказать тождественную истинность формулы:

.

Решение.Приведем решение задачи тремя способами: построение таблицы истинности (таблица 2), использование аксиом логики высказываний и с помощью метода резолюций.

Таблица истинности будет иметь вид:

Таблица 2

A	B
И	И	И	Л	И	И
И	Л	Л	И	Л	И
Л	И	И	И	И	И
Л	Л	И	И	И	И

Из табл.2 следует, что формула истинна на всех наборах A и B.

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

Формула тождественно истинна.

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

, ( * )

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

Строим семантическое дерево вывода:

A- исходные дизъюнкты

R₁=- резольвента первого уровня

R₂=- резольвента второго уровня-пустой дизъюнкт

Вывод пустого дизъюнкта есть доказательство невыполнимости формулы (*) или общезначимости исходной формулы.

Задача 3. Доказать эквивалантность формулы:

Решение. Доказательство эквивалентности левой и правой частей формулы можно провести или построением таблицы истинности, или преобразованием левой части.

Используем второй путь.

Задача 4.Записать на языке логики предикатов следующие высказывания: а) любое рациональное число является действительным числом; б) некоторые действительные числа являются рациональными; в) определение непрерывной функцииf:в точке(R-множество действительных чисел).

Решение. Перефразируем высказывание а) следующим образом: “ для любого x: еслиx рациональное число, тоxесть действительное число”.

Введем следующие значения предикатов:

R(x)- “xесть действительное число ”.

Q(x)-“x есть рациональное число ”.

Тогда высказывание а) запишется в виде формулы:

F:

Высказывание б) переформулируем так: “ существуют такие x, чтоxявляется действительным числом ”. На языке логики предикатов это запишется так:

И, наконец, запишем определение непрерывности в точке: “ функция действительного переменного называется непрерывной в точке, если для любого сколь угодно малого положительного числаE>0 найдется такое положительное число>0, что если ||<, то

||<E ”.

Это определение на языке логики предикатов запишется так:

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

Решение. Доказательство общезначимости заданной формулы опровержением ее отрицания, т.е. надо доказать, что формула

является тождественно ложной.

Формула (**) представлена в предваренной нормальной форме: ее префикс содержит два квантора существования , а матрица равна

Сохраняя потиворечивость формулы, элимируем кванторы существования, введя вместо предметных переменных x и yскулемовские константы a и b.

Формула логики предикатов (**) преобразуется в формулу логики высказываний

Построение доказательств :

1). |-Ø"xA(x)~$xØA(x) :

1. Ø"xA(x) (допущение)

2. A(x) (допущение противного)

3. "xA(x) ("- введение)

4. ØA(x) (Ø- введение,2)

5. $xØA(x) ($- введение, 4)

6. Ø"A(x)®$xØA(x) (теорема дедукции,1,5)

7. $xØA(x) (допущение)

8. "xA(x) (допущение противного)

9^¢.ØA(x) (допущение)

10^¢A(x) ("- удаление,8)

11^¢.Ø"xA(x) (слабое удалениеØ)

12. Ø"xA(x) ($- удаление,7)

13. Ø"xA(x) (Ø-введение,8)

14. $xØA(x)®Ø"xA(x) (теорема дедукции,7,12)

15. Ø "x A(x) « $x Ø A(x)(« - введение, 6,13).

2) "x (P(x)®Q(x)) |- "x P(x)® "x Q(x) :

1. "x(P(x)®Q(x)),"xP(x)|-P(x)®Q(x) (удаление")

2. "x(P(x)®Q(x)),"xP(x)|-P(x) (удаление")

"x(P(x)®Q(x)),"xP(x)|-Q(x) (удаление®)

"x(P(x)®Q(x))|-"xP(x)®Q(x) (введение®)

"x(P(x)®Q(x))|-"xP(x)®"xQ(x) (введение")

Формула вида Q₁x₁…Q_nx_nA, гдеAбескванторная формула, аQ_iесть"или$, называется предваренной (или пренексной)нормальной формой.

ТЕОРЕМА 9.У всякой формулы исчисления предикатов есть эквивалентная ей предваренная нормальная форма.

ТЕОРЕМА (Геделя о полноте исчисления предикатов).|-EÛ|=E.

(Без доказательства).

Следствие.Исчисление предикатов непротиворечиво.

Упражнение

1. Обосновать допустимость производных правил вывода исчисления предикатов.

2.Доказать следующую теорему: Какова бы ни была формула Eи нуль-местная предикатная букваP, всегда|-E~(P&F₁)Ú(ØP&F₂), гдеF_iестьPилиØP, или некоторая формула, не содержащаяP(i=1,2).

3. Доказать основные тавтологии исчисления предикатов с кванторами.

4. Найти ошибку в выводе:

P(x),Q(x)ú-$x(Q(x) &P(x))

P(x), $x Q(x) ú- $x(Q(x) & P(x))

$x P(x), $x Q(x) ú- $x(Q(x) & P(x))

$x P(x) & $x Q(x) ú- $x(Q(x) & P(x))

ú-$x P(x) & $x Q(x) ®$x(Q(x) & P(x))

5. Доказать, что следующие теоремы имеют место, если A(x,x) является результатом подстановки ‘x’ вместо свободных вхождений ‘y’ вA(x,y), причем ‘x’ свободно для ‘y’ вA(x,y) :

1. "x"y A(x,y)®"x A(x,x) b)$x A(x,x)®$x$y A(x,y)

6. Какое из утверждений верно: A(x)ú-"xA(x) илиú-A(x)Þ"xA(x)?

7. Доказать теорему 9.

8. Привести к предваренной форме формулу:

(Ø$x P(x)Ú"x Q(x)) & (R®"x S(x))

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

1. "x$y A(x,y) ® $y A(x,y);

2. ("xP(x)®P(y))®("xP(x)®"yP(y)), гдеP– одноместная предикатная буква;

(c) A(x)®$x A(x);

(d) (A(x)®$x A(x))®("x A(x)®(A(x)®$x A(x)));

5. "x A(x)®(A(x)®$x A(x));

6. ("x A(x)®A(y)) ® ("xA(x)®"yA(y));

1. (A(y)®$x A(x)) ® ($yA(y)®$x A(x))).

10. Доказать при условии, что переменная xне входит свободно в формулы списка Г : (a) Если Гú-A(x)~B(x), то Гú-"xA(x)~"xB(x).

(b) Если Гú-A(x)~B(x), то Гú-$xA(x)~$xB(x).

11. Обосновать правильность вывода: "x(P(x)~$zR(x,w,z))ú-

P(x) Ú "x $y (P(x) ® Q(y)) ~ P(x) Ú "x$y($z R(x,w,z) ® Q(y)).

12. Доказать УТВЕРЖДЕНИЕ об эквивалентности конгруентных формул.

13. Доказать, что если множества формул T₀,T_1,T_2,… непротиворечивы иT_iÍT_i+1(i=0,1,…), то È T_i - непротиворечивое множество формул.

14. Пусть множество Г È{$xA(x)} непротиворечиво. Доказать, что если переменная ‘y’ не входит в Г и$xA(x), то множество ГÈ{$xA(x),A(y)} непротиворечиво.

15. Пусть множество формул Г полно и непротиворечиво. Доказать, что для любых замкнутых (не содержащих свободных переменных) формул AиBверно:a) Г|-A&BÛГ|-Aи Г|-B;

b) Г|-AÚBÛГ|-Aили Г|-B;

c) Г|-ØAÛне( Г|-A);

d) Г|-A®BÛне(Г|-A) или Г|-B.

16. Добавим в алфавит исчисления предикатов функциональные символы f⁽ⁿ⁾(x₁,…,x_n) (n³0) и определим новые выражения – термы: (1)x₁,x₂,…-термы; (2) еслиt₁,…,t_n– термы иf⁽ⁿ⁾(x₁,…,x_n) (n³0) – функциональный символ, тоf⁽ⁿ⁾(t₁,…,t_n) - функциональный терм.

Интерпретациями функциональных символов являются отображения (соответствующей местности) на заданной предметной области D¹Æ.

Найти значения функционального терма t=f(f(x)) на областиD={1,2}

и построить истинностную таблицу формулы P(f(x))®$xØP(f(f(x))).

17. Какие из термов: (a)f(x,y), (b)g(w,y), (c)g(z,f(x,y)), (d)g(y,f(h,x))

свободны для ‘x’ в формуле ‘"w(P(x,y)Ú$zQ(y,z)®R(w))’?

18. Пусть x– произвольная переменная иA(x) – произвольная формула,

t– терм, свободный дляxв формулеA(x).Доказать, что

(a) |="x A(x) ®A(t), (b) |=A(t)®$x A(x).

19. Пусть формулы Г не содержат свободно переменной xи термtсвободен дляxв формулеA(x). Доказать, что Г|-A(x)ÞГ|-A(t).

Практическое занятие 2

«Графы»

Задание 1. Компоненты сильной связности ориентированного графа.

С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.

Cоставляем матрицу смежности A(D) размерности (n− количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин , из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины v_i и входящая в v_j, то элемент матрицы смежности, стоящий на пересечении i-той строки и j-того столбца равен 1, иначе – 0.).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.