Доказать, что следующие функции вычислимы 2 страница

3. ; 4. ;

5. .

Задание 6

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

1. ; 2. ;

3. ; 4. ;

5. ; 6. .

Задание 7

Найти отрицание следующих формул.

1. ; 2. ;

3. ; 4. ;

5. ;

6. ; 7. .

 

 

Задание 8

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

1. ; 2. ;

3. ; 4. ;

5. ; 6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13.

;

14. ; 15. ;

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. .

Задание 9

Пусть и два одноместных предиката, определенных на множестве таким образом, что высказывание - всегда истинно. Доказать, что высказывание - всегда ложно.

Задание 10

Пусть обозначает “ – простое число”, – “ – четное число”, – “ – нечетное число”, – “ делится на ”. Дать словесную формулировку следующим формулам:

1. ; 2. ; 3. ;

4. ; 5. ;

6. ;

7. ;

8. ;

9.

.

Задание 11

Даны утверждения – “число делится на 3”, – “число делится на 2”, – “число делится на 4”, – “число делится на 6”, – “число делится на 12”. Укажите, какие из следующих утверждений истины, а какие ложные.

1. ; 2. ; 3. ; 4. ;

5. ; 6. ;

7. .

Задание 12

Доказать следующие равносильности.

 

1. ; 2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. .

Задание 13

Какие из заданных формул являются общезначимыми?

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ; 13. ;

14. ;

15. ;

16. ;

17. ;

 

18. ;

19. ).

Задание 14

Доказать тождественную ложность формул.

1. ;

2. /

 

ЛАБОРАТОРНАЯ РАБОТА № 5

ПЕРЕВОД ВЫСКАЗЫВАНИЙ ЕСТЕСТВЕННОГО ЯЗЫКА НА ЯЗЫК ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

 

1. ЦЕЛЬ РАБОТЫ

 

Целью работы является приобретение навыков перевода высказываний естественного языка на язык исчисления предикатов

 

2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

В естественном языке слово “все” обычно опускается.

Так, например, “Рыбы дышат жабрами” означает, что все рыбы дышат жабрами или, что каждая рыба дышит жабрами. Если обозначить , а , то при символизации фразы “Рыбы дышат жабрами” необходимо использовать квантор всеобщности: . Однако не в каждом случае

 

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

Рассмотрим особенности перевода на язык исчисления предикатов следующих выражений: “Все студенты отличники” и “Некоторые студенты отличники”.

Первое выражение может быть перефразировано так: “Для всех справедливо, если - студент, то - отличник”. Перевод этой фразы будет таким: , где - “ - студент”, - “ - отличник”.

Второе выражение может быть перефразировано так: “Для некоторых справедливо: - студент и - отличник”. Перевод этой фразы будет таким: . Использование в этом случае конструкции: “Для некоторых справедливо: если - студент, то - отличник” является неверным, так как стоит попасть в компанию одному нестуденту, и он сделает этот предикат истинным, даже если там нет ни одного отличника.

Для перевода высказываний естественного языка на язык логики предикатов можно использовать таблицу, приведенную в [4].

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

Пример 1. Любые два действительных числа либо равны, либо одно из них меньше другого.

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

- “ есть действительное число”; - “ ”;

- “ ”; - “ ”.

 

 

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

Пример 2. Ни один пациент не любит знахарей.

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

- “ - пациент”; - “ – знахарь”;

- “ любит ”.

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

.

 

3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

 

Перевести выражения естественного языка на язык исчисления предикатов

1. Если произведение конечного числа сомножителей равно нулю, то, по меньшей мере, один из сомножителей равен нулю. ( – “ есть произведение конечного числа сомножителей», – « есть один из сомножителей числа ”).

2. Наибольший общий делитель чисел и делится на всякий их общий делитель ( – “ есть один из делителей числа ”, а – “ есть наибольший общий делитель чисел и ”).

3. Для всякого действительного числа существует большее действительное число .

4. Существуют такие действительные числа , , что сумма чисел и больше, чем произведение чисел и .

5. Для каждого действительного числа существует такое , что для каждого , если сумма и 1 меньше , то сумма и 2 меньше 4.

6. Существует x, меньшее, чем 5 и, большее, чем 3.

7. Для любого числа существует число , меньшее .

8. Для любых чисел и суммы и равны.

9. Для любого числа существует такое число , что для любого , если разность меньше, чем , то разность меньше 3

10. Между любыми двумя различными точками на прямой лежит, по крайней мере, одна точка, с ними не совпадающая.

11.Каждый студент выполнил, по крайней мере, одну лабораторную работу.

12.Если произведение натуральных чисел делится на простое число, то на него делится, по крайней мере, один из сомножителей.

13. Через три точки, не лежащие на одной прямой, проходит единственная плоскость.

14. Всякое животное, встречающееся с вежливыми людьми, счастливо.

15. Все люди, посещающие зоопарк, вежливы.

16. Животные, живущие в зоопарке, встречаются с людьми, посещающими зоопарк.

17. Никакой продавец игрушками сам себе их не покупает.

18. Те римляне, которые ненавидели диктатора, пытались убить его.

19. Римляне либо были преданы диктатору, либо ненавидели его.

20. Некоторые судьи - старики, но бодрые.

21. Судья Иванов не стар и не бодр.

22. Не все юристы судьи.

23. Некоторые юристы, являющиеся политиками, – члены конгресса.

24. Ни один член конгресса не бодр.

25. Все старые члены конгресса - юристы.

26. Некоторые женщины одновременно являются юристами и членами конгресса.

27. Некоторые пациенты любят докторов.

28. Ни один доктор не является знахарем.

29. Выгул кошек или собак запрещен.

30. Ни одна женщина не является одновременно политиком и домашней хозяйкой.

31. Ни один судья не является преподавателем.

32. Некоторые женщины-юристы являются домашними хозяйками.

33.Все женщины-юристы восхищаются каким-нибудь судьей.

34. Некоторые юристы восхищаются только судьями.

35. Некоторые юристы восхищаются женщинами.

36. Некоторые преподаватели не восхищаются ни одним юристом.

37. Судья Иванов не восхищается ни одним преподавателем.

38. Существуют как юристы, так и преподаватели, которые восхищаются судьей Ивановым.

39. Только судьи восхищаются судьями.

40. Все судьи восхищаются только судьями.

41. Все студенты группы свободно владеют всеми тремя языками: английским, немецким, французским.

42. Каждый студент группы владеет каждым иностранным языком (английским, немецким, французским).

43. Есть студенты, которые свободно владеют и английским и немецким и французским языками.

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

 

45. Нет столь великой вещи, которую не превзошла бы величиной еще большая.

46. Каждое рациональное число есть действительное число. Некоторое действительное число есть рациональное число. Не каждое действительное число есть рациональное число.

47. Пусть и означают соответственно “ ”, “ линия”, “ проходит через и ”, “ ”. Перевести следующее предложение: для любых двух точек существует одна и только одна линия, проходящая через эти точки

48. На всех кошек и собак следует получить разрешение.

49. Любые два действительных числа либо равны, либо одно из них меньше другого.

50. Каждый ребенок человека состоит в браке с ребенком человека .

51. У человека существует ребенок, который не состоит в браке с ребенком человека .

52. Существуют два человека такие, что каждый ребенок одного из них состоит в браке с ребенком другого.

53. Существуют два человека такие, что ни один ребенок одного из них не состоит в браке с ребенком другого.

54. Если является ребенком человека , то каждый ребенок человека является внуком человека .

55. Введем следующие обозначения:

- “я вижу предмет в момент времени ”;

- “я беру предмет в момент времени ”;

- “ момент времени предшествует моменту ”.

Перевести следующие выражения на язык исчисления предикатов

55.1. Я всегда что-то вижу.

 

 

55.2. Иногда я ничего не вижу.