Поволжский государственный университет телекоммуникаций и информатикиПоволжский государственный университет телекоммуникаций и информатики Заочный факультет
РЕГИСТРАЦИОННЫЙ № ______
Контрольная работа № _______ Вариант ________
По дисциплине __________________________________________
На тему__________________________________ _______________
Студент ________________________________________________
Факультет _________ курс ________ шифр __________ гр.______
Работа выслана «______»____________________ 201___г.
Оценка _______________ Дата _______________201___г.
Подпись преподавателя ___________________
Самара
2011 г. «Исчисления с помощью логики предикатов» 1. Записать следующие определения: а) Терм – это знак (символ) или комбинация знаков, являющаяся наименьшим значимым элементом языка. б) Предикат – это логическая функция, которая выражает отношение между своими аргументами и принимает значение «1», если это отношение имеется, или «0», в обратном случае. в) Функция – это последовательность из нескольких констант или переменных, заключенных в (), следующая за функциональным символом (функтором). г) n-местный предикат – это заключенная в () последовательность из n термов, перед которой стоит предикатный символ. д) Предикатная формула – это последовательность атомарных предикатов и логических связок.
2. Являются ли приведенные ниже примеры атомарными формулами: 1. Ремонтировать (электрик, проводка) - является 2. Столица (Париж) 3. Элемент (процессор, ПК) - является 4. Элемент (процессор, ПК) v Элемент (видеокарта, ПК) – не является 5. Элемент (крылья, птица) v Элемент (клюв, птица) v Элемент (хвост, птица) – не является
3. Привести 5 примеров других атомарных предикатов:
4. Записать в виде предикатной формулы: а) Все люди смертны "х [человек (х) → смертен (х)] б) Если пингвин летает, то я – не студент Алтунбаев если (пингвин летает) → студент (я, Алтунбаев) в) Если Москва – не столица России, то пингвины летают столица (Москва, Россия) → летают (пингвины) д) Нет такого студента, который не хотел бы быть отличником "х [студент (х) → хотеть быть (х, отличник)] е) Если все полученные в сессию отметки – пятерки, то студент отличник студент (х) ^ ["у пятерка (у)] ^ оценка (у, х) → отличник (х) ж) Все слоны имеют серую окраску " х [слон (х) → окраска (х, серая)] з) Не все девушки – блондинки "х [девушка (х) → блондинка (х)]
5. Придумать 7 своих примеров и записать их в виде задания на русском языке и решения с помощью предикатной формулы: а) Все рептилии холоднокровные "х [рептилия (х) → холоднокровность (х)] б) Не все птицы летают "х [птица (х) → летать(х)] в) Некоторые люди больны $ х [люди (х) → болеть (х)] г) Не все люди читают "х [люди (х) → читать (х)] д) Некоторые мужчины-пенсионеры работают $ х [мужчина (х) ^ пенсионер (х) → работать(х)] е) У всех людей есть сердце "х [люди (х) → иметь (х, сердце)] ж) Не все полезно, что съедобно "х [съедобно (х) → полезно(х)]
6. Записать для каждой формулы равносильную, расшифровать запись аналогом на русском языке: б) ($ х А) = " х А (не существует такого х, для которого выполняется А, т.е. для каждого х не выполняется А) в) " х А v " х В = $ х (А v В) (для каждого х выполняется А или для каждого х выполняется В, т.е. не существует такого х, для которого не выполняется А или В) г) $ х А v $ х В = $ х (А v В) (существует такой х, для которого выполняется А, или существует такой х, для которого выполняется В, т.е. существует такой х, для которого выполняется А или В) д) " х А v С = " х (А v С) = $ х (А v С) (для каждого х выполняется А или С, т.е. не существует такого х, для которого не выполняется А или С) е) " х А ^ С = " х (А ^ С) = " х А ^ " х С (для каждого х выполняется А и С, т.е. для каждого х выполняется А и для каждого х выполняется С)
7. Пусть предикаты имеют следующий смысл: N(x): x – натуральное число C(x): x – целое число P(x): x – простое число Ч(х): х – четное число П(х): х – положительное число D(x, у): x – делитель у Сформулируйте смысл формул и укажите, какие из них являются тождественно истинными: а) " х (N(x) → C(х)) – является для любого числа х: если х натуральное, то оно целое б) " х (С(x) → Ч(х) v Ч(х)) – является для любого числа х: если х целое, то оно четное или нечетное в) " х $ у (С(x) v С( у ) → D(х, y )) – не является для любого числа х существует такое число у, что если х и у целые, то х является делителем у г) " х (P(x) → Ч(х)) – не является для любого числа х: если х – положительное число, то оно четное д) " х (С(x) v П (х) → N (х)) – не является для любого числа х: если х целое или положительное, то оно натуральное
8. Для предикатов из предыдущего задания записать 5 своих тождественно истинных формул: а) для любого числа х существует такое число у, что если х четное, у является делителем х " х $ у (Ч(x) → D( y, х)) б) для любого числа х: если х – простое число, то оно натуральное " х (P(x) → N(х)) в) для любого числа х: если х – натуральное, то оно положительное " х (N(x) → П (х)) г) для любого числа х: если х – целое и положительное, то оно натуральное " х (С(x) ^ П (х) → N (х)) д) для любого числа х: если х – простое, то оно нечетное " х (P(x) → Ч(х))
|
