В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 42
Текст из файла (страница 42)
Укажите самостоятельно примеры конкретных таких предикатов, например, на множестве 1«'. 9.71. Выясните, будут ли выполняться в логике предикатов следующие логические следования, выражающие на языке логики предикатов «слабые» модусы аристотелевой силлогистики: а) (Чх)(М(х) -+ Р(х)) л ('Фх)(Я(х) -+ М(х)) в= (Эх)(5(х) л л Р(х)) (фигура 1, модус ВагЬаг!); б) ('с~х)(М(х) -+ -юР(х)) л ('с~х)(5(х) -+ М(х)) ~ (Зх)(Ю(х)», л -иР(х)) (фигура 1, модус Се1агоп!)' в) ('«х)(Р(х) -+ М(х)) л («х)(Я(х) -+ -чМ(х)) ~= (Бх)(Я(х) л л -юР(х)) (фигура П, модус Сатез~гор); г) ('Фх)(Р(х) -+ ~М(х)) л (~х)(Я(х) -+ М(х)) ~= (Зх)(Я(х) л л -зР(х)) (фигура П, модус Сезаго); д) ('Фх)(Р(х) -+ М(х)) л (~х)(М(х) -+ -зЯ(х)) ~= (Зх)(Я(х) л л -зР(х)) (фигура 1У, модус Сатепоз).
0 10. Применение логики предикатов к логико-математической практике Записи иа языке логики предвкатов. Задачи такого типа имеют важное методологическое значение. Они по существу являются своеобразной моделью одной из сторон научно-исследовательского процесса, когда от своего рода «технической» постановки задачи требуется перейти к ее математической постановке, с тем чтобы в процессе ее решения можно было использовать математические методы. 10.1. Запишите следующие высказывания на языке логики предикатов: а) Существует не более одного х такого, что Р(х); б) Существует точно один х такой, что Р(х); в) Существует по меньшей мере два различных х таких, что Р(х); г) Существует не более двух х таких, что Р(х)' д) Существует точно два различных х таких, что Р(х).
Р е ш е н и е. а) Прежде переформулируем данное утверждение так, чтобы, во-первых, не исказить его смысл, а во-вторых, сде- 204 лать его полностью готовым к переводу на логико-математический язык, т.е. на язык логики предикатов. Вот эта переформулировка: не верно, что существуют два различных предмета х и у такие, что Р(х) и Р(у) (какие бы два предмета ни удовлетворяли условию Р, они не могут не совпадать, т.е. обязаны совпадать). Теперь мы готовы записать последнюю фразу символически: ('Фх)(~1у)((Р(х) л Р(у)) -+ х = у). 10.2. Введя подходящие одноместные предикаты на соответствующих областях, переведите следующие высказывания на язык логики предикатов: а) Все рациональные числа действительные; б) Ни одно рациональное число не является действительным; в) Некоторые рациональные числа действительные; г) Некоторые рациональные числа не являются действительными.
Определите, какие из данных высказываний истинны. Р е ш е н и е. Введем следующие одноместные предикаты: Д(х): «х — рациональное число»; А(х): х — действительное число», Тогда перевод данных высказываний на язык логики предикатов будет таким: а) (~х)(Д(х) -+ А(х)); б) (~х)(0(х) -+ -~А(х)); в) (Зх)(Д(х) л А(х)); г) (Зх)(0(х) л ~А(х)). 10.3. Введите одноместные предикаты на соответствующих областях и запишите при их помощи следующие высказывания в виде формул логики предикатов: а) Всякое натуральное число, делящееся на 12, делится на 2, 4 иб; б) Жители Швейцарии обязательно владеют или французским, или итальянским, или немецким языком; в) Функция, непрерывная на отрезке [О, 1[, сохраняет знак или принимает нулевое значение; г) Некоторые змеи ядовиты; д) Все собаки обладают хорошим обонянием; е) Все ромбы являются параллелограммами; ж) Некоторые параллелограммы являются ромбами; з) Ни один параллелограмм не является ромбом; и) Некоторые ромбы не являются параллелограммами; к) Ни один ромб не является параллелограммом; л) Все параллелограммы являются ромбами.
10.4. В следующих примерах проделайте то же самое, что и в предыдущей задаче, необязательно ограничиваясь одноместными предикатами: а) Если а есть корень многочлена от одной переменной с вещественными коэффициентами, то сопряженное число (а) также является корнем этого многочлена; б) Между любыми двумя различными точками на прямой лежит по меньшей мере одна, с ними не совпадающая; 205 в) Через две различные точки на плоскости проходит единственная прямая; г) Каждый студент выполнил по меньшей мере одну лабораторную работу; д) Если произведение нескольких натуральных чисел делится на простое число, то на него делится по меньшей мере один из сомножителей; е) Через три точки, не лежащие на одной прямой, проходит единственная плоскость; ж) Наибольший общий делитель чисел а и Ь делится на всякий их общий делитель; з) х — простое число; и) Каждое четное число, большее четырех, является суммой двух простых чисел (гилотеза Гольдбаха)' к) Существуют три точки на плоскости, не принадлежащие одной прямой.
Решение. к) Первая форма записи данного утверждения: (ЗА)(ЗВ)(ЗС) -з (З1)(А е 1 л В е 1 л С е 1). Вторая форма: (ЗА)(ЗВ)(ЗС)(~1) (А а! ч В а ! ч С а 1). 10.5. Запишите на языке логики предикатов отрицание каждого из предложений предыдущей задачи, предварительно сформулировав его. Р е ш е н и е. к) Отрицание формулируется следующим образом: «Любые три точки принадлежат некоторой прямой». В случае второй формы записи отрицание выглядит так: ('ФА)(«'В)('Ф С)(З!)(А а е1лВе!л Се!).
10.6. Пусть Р(х) означает «х — простое число», Е(х) означает «х — четное число», 0(х) означает «х — нечетное число», 2)(х, у) — «х делит у» или «у делится на х». Переведите на русский язык следующие символические записи на языке логики предикатов, учитывая, что переменные х и у пробегают множество натуральных чисел: а) Р(7); б) Е(2) л Р(2); в) (»х)(!)(2, х) -+ Е(х)); г) (Зх)(Е(х) л Ю(х, б)); д) (~хН-зЕ(х) -+ -зХ>(2, х)); е) (тх)((Р(х, 32) л х ~ 1) -+ Е(х)); ж) («х)(Е(х) -+ (Зу)(х = 2у)); з) (~х)(Р(х) -+ (Зу)(Е(у) л 2)(х, у))); и) ('Фх)( 0(х) -+ (Ъу)(Р(у) -+ -~!)(х, у))); к) (Зх)(Е(х) л Р(х)) л -з(Зх)(0(х) л Р(х)) л (Эу)(х ~ у л Е(у) л л Р(у)); л) (»х)(Е(х) -+ ('Фу)(Ю(х, у) -+ Е(у))).
Решение. л) Это высказывание можно прочитать так: «Для любого натурального числа х, если оно четное, то для любого 206 натурального числа у, если х делит у, то и у будет четным числом», Мы прочитали это высказывание что называется»с листагс произнесли словами нового языка то, что было написано на старом языке, не вникая в математическую суть утверждения. Вдумаемся теперь в суть этого утверждения и придадим ему более подобающую русскому языку и более понятную форму: «Всякое натуральное число, делящееся на четное число, само будет четным». 10.7. Запишите на языке логики предикатов определения: а) монотонной последовательности; б) ограниченной последовательности; в) предела последовательности (сходящейся последовательности); г) фундаментальной последовательности (или последовательности Коши); д) возрастающей функции, монотонной функции; е) четной функции; ж) периодической функции; з) функции, стремящейся к бесконечности в точке; и) предела функции в точке; к) непрерывности функции в точке; л) равномерной непрерывности функции на множестве.
Решение. л) Функция Ях) называется равномерно непрерывной на множестве М, если абсолютная величина разности между значениями функции для каждой пары точек хь х~ е М может быть сделана меньше любого наперед заданного как угодно малого положительного числа, если только эти точки достаточно близки друг к другу. Символически, на языке логики предикатов (или, как говорят в анализе, на (с, 5)-языке): ('»'а > О)(ЛЬ > О)(Чхь хз а М)() х, — хз ~ < 5 -+ ~ Дх,) -Ях~) ! < а).
10.8. Пользуясь записями, полученными при решении предыдущей задачи, ответьте на следующие вопросы. Что значит: а) последовательность не является монотонной; б) последовательность не является ограниченной; в) последовательность не является фундаментальной; г) последовательность не является сходящейся; д) функция не является возрастающей, монотонной; е) функция не является четной; ж) функция не является периодической; з) последовательность не имеет предела; и) функция не имеет предела в точке; к) функция не является непрерывной в точке; л) функция не является непрерывной на отрезке? Ре ше ни е. л) Это значит, что существует такое положительное число, меньше которого не может быть сделана абсолютная 207 величина разности между значениями данной функции в точках хь хз а М, как бы близко ни находились друг от друга эти точки. На языке логики предикатов: (Ла > 0)(Ъ'б > 0)(Эхь хз е М)(~ х, — хз ~ < 5 л ) Ях,) — ~(хз) ~ > с).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
