2018-03-09
290
Суперпозиция функций. Терм. Атомарная формула. Операции над предикатами: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, навешивание квантора. Формула алгебры предикатов. Подформула формулы алгебры предикатов. Свободное и связанное вхождение переменной в формулу. Алгебраическая система. Интерпретация формул алгебры предикатов в алгебраической системе. Типы формул алгебры предикатов.
18.1. Определить термы среди следующих выражений:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
.
(Здесь и далее: 
– предметные переменные,
– предметные константы,
– предикатные переменные,
– функциональные переменные,
причем верхний индекс предикатных и функциональных переменных служит для обозначения числа аргументов.)
18.2. Выбрать формулы алгебры предикатов среди следующих выражений. Какие из них являются атомарными формулами? Определить в формулах свободные и связанные вхождения переменных:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
.
18.3. Выписать все подформулы данных формул, предварительно установив порядок выполнения операций в этих формулах:
|
|
|
1) 
;
2) 
;
3) 
;
4) 
.
18.4. Определить предметные переменные, константы, функции и предикаты в следующих суждениях:
1) Около четырехугольника 
можно описать окружность.
2) Точка 
лежит на прямой 
.
3) Отец Антона работает бухгалтером.
4) Среднее арифметическое двух неотрицательных действительных чисел не меньше их среднего геометрического.
5) С.Ю. Витте – министр финансов России в 1895 году.
6) Наибольший общий делитель любых двух целых чисел делится на любой их общий делитель.
18.5. Формализовать следующие суждения, используя указанные предикаты, определенные на множестве всех людей:
,
,
,
1) Все студенты умеют читать.
2) Некоторые японцы знают русский язык.
3) Ни один из студентов не является японцем.
4) Некоторые люди, знающие русский язык, не являются японцами.
5) Не все студенты 
знают русский язык.
6) Среди студентов встречаются японцы.
7) Существуют умеющие читать японцы.
8) Кен – японец, знающий русский язык.
9) Мери любит Билла.
10) Мери любит всех японцев.
11) Мери любит всех.
12) Все любят Мери.
13) Некоторые не любят Билла.
14) Каждый японец любит себя.
15) Некоторые люди любят всех.
16) Существуют люди, которые никого не любят.
17) Кого-то любят все.
18) Все кого-нибудь любят.
19) Не существует людей, не любящих себя.
20) Никто никого не любит.
18.6. Перевести с формального языка на содержательный:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
;
9) 
;
10) 
.
18.7. Определить, какие из следующих формул истинны, а какие ложны на 
:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
;
9) 
;
10) 
.
|
|
|
18.8. Определить, при каких значениях свободных переменных следующие формулы истинны на 
:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
;
9) 
;
10) 
.
18.9. Формализовать следующие суждения, определив подходящие предикаты:
1) Некоторые девушки курят.
2) Некоторые девушки и юноши курят.
3) Все девушки, кроме курящих, занимаются спортом.
4) Некоторые девушки любят Элвиса Пресли.
5) Есть юноши и девушки, любящие друг друга.
6) Некоторые девушки любят безответно.
7) Существует наименьшее натуральное число.
8) Не существует наибольшего целого числа.
9) У каждого натурального числа есть хотя бы один делитель.
10) Уравнение 
имеет ровно два комплексных корня.
11) 5 – простое число.
12) Число 52 имеет по крайней мере два простых различных делителя.
13) Всякое натуральное число, не меньшее 2, имеет не меньше одного делителя, отличного от 1.
14) 
– наименьший элемент множества 
.
15) – точная нижняя грань множества .
18.10. Для интерпретации 
функциональных и предметных переменных определить значения термов в алгебраических системах. Указать, какие еще возможны интерпретации функциональных переменных в этих алгебраических системах:
1) 
а) 
, 
, 
;
б) 
, 
, 
;
в) 
, где 
– множество всех подмножеств множества 
, 
, 
;
2) 
а) 
, где 
, , 
, , 
б) 
, где 
– множество всех одноместных функций из в , 
, 
, 
, 
, 
, 
, 
;
18.11. Для интерпретации функциональных, предикатных и предметных переменных определить значения атомарных формул в алгебраических системах:
1) 
а)
, 
, 
, 
, 
;
б) 
, где 
– множество всех людей, 
, 
, 
, 
, 
, 
, 
, 
;
2) 
а) 
, где 
– множество героев греческих мифов, , 
, 
,
, 
, 
, 
,
.
18.12. Для интерпретации определить значения формул в алгебраических системах:
1) 
а) 
, где 
, 
, 
;
б) 
, где – множество всех людей, 
, , , 
, 
, 
;
2) 
а) 
, 
, 
;
б)
, , ;
3) 
а)
, , ;
б)
, , ;
4) 
а)
, ;
б) 
, где 
– множество векторов трехмерного евклидова пространства 
, 
, 
– отношения перпендикулярности и параллельности векторов, 
, 
– операции векторного произведения и сложения векторов
, 
;
5) 
а) 
, где – множество всех людей, , , 
, 
, 
;
6) 
а) 
, 
;
б)
, .
18.13. Описать множество истинности следующих формул и построить их геометрическую интерпретацию. В пунктах 3 – 10) формулы 
и 
определены также, как в пунктах 1 – 2):
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
;
9) 
;
10) 
.
18.14. Определить тип формул на указанной алгебраической системе при данных интерпретациях предикатных и функциональных переменных:
1) 
, где 
, 
, 
а) 
;
б) 
;
в) 
;
2) 
, где – множество всех людей, 
, 
, , 
а) 
, 
, 
; 
;
б) , 
, 
; .
18.15. Определить тип следующих формул на данных алгебраических системах, построив интерпретации на этих системах:
1) 
, где , 
2) 
, где – множество всех людей, 
, 
, 
, , 
, 
.
18.16. Определить тип формулы алгебры предикатов, построив подходящие алгебраические системы и интерпретации формулы в них:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
;
9) 
,
;
10) 
;
11) 
;
12) 
18.17. Доказать тождественную истинность (логическую общезначимость) следующих формул:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
,
;
9) 
,
;
10) 
;
11) 
.
18.18. Используя заданные предикаты, формализовать утверждения:
,
1) Я всегда что-то вижу.
2) Иногда я ничего не вижу.
3) Существуют предметы, которые я всегда вижу.
4) Существуют предметы, которые я никогда не вижу.
5) Я вижу каждую вещь в некоторый момент времени.
6) Если я вижу предмет, то я тут же его беру.
7) Не существует предметов, которых я никогда не беру.
8) Я беру всякий предмет, который я еще не взял до этого.
18.19. Записать с помощью формул алгебры предикатов следующие высказывания:
1) Существует не более чем один элемент 
, такой, что 
.
2) Существует по крайней мере два элемента и 
, такие, что и 
.
|
|
|
3) Существует один и только один элемент , такой, что .
4) Существует не более двух элементов и , таких, что и .
5) Существует два и только два элемента и , таких, что и .
18.20. Формализовать утверждения, используя следующие предикаты:
,
,
,
1) Все жители королевства носят бороду.
2) Не существует бородатых женщин.
3) Смит живет в королевстве, следовательно, Смит не является женщиной.
4) Некоторые соседи Смита женаты.
5) Жена Смита живет по соседству с женой Брауна.
6) Жены Смита и Брауна не живут в королевстве.
7) Смит женат только на одной женщине, а Браун – женат на двух.
8) Фокс холост.
18.21. Записать на формальном языке следующиеутверждения:
1) Не существует минимального целого числа, кратного 
.
2) Последовательность 
, 
, ограничена сверху.
3) Если число кратно 
, то оно кратно и 
.
4) Произведение трех последовательных целых чисел делится на 
.
5) Разность некоторых двух из четырех целых чисел делится на три.
6) 
– простое число.
7) Множество простых числе бесконечно.
8) Для делимости числа на 
необходима его делимость на 
.
9) Всякое четное число, большее 
, представляется в виде суммы двух простых чисел.
10) Все корни уравнения 
рациональны.
11) Уравнение 
имеет ровно два различных корня.
12) Не все кубические корни из 
являются действительными числами.
13) Функция 
непрерывна на отрезке 
.
