Игошин Математическая логика и теория алгоритмов (1019110), страница 48
Текст из файла (страница 48)
Используя символику ограниченных кванторов (см. Я 20), это определение можно записать компактнее: апр. а = 1пп а„с=~ (Ъе > 0) (Элр а У) (ол > лр)(1а„- а) < е). 196 Нередко требуется доказать, что некоторое число а не является пределом последовательности [а„], т.е. а ~ 1пп а„. Для доказательства нужно построить утверждение, являющееся отрицанием сформулированного определения. Поможет в этом логика предикатов. Используя равносильности логики предикатов, преобразуем отрицание исходной формулы к приведенному виду: (Фе)[е > 0 -+ (Зп«)(л я )«'л (Фп)(п > и, — » ~а„— а] < е))] в = (3 е)- [-(е > 0) ч (Бл«)(л«в Ф л ( Фл)(л > л« -+ !а„— а/ < е))] я = (Зе)[(е > 0) л (Уп«)(-,(л» е )У) ч —,(Фл)(-(л > и«) ч [а„— а~ < е))] =- = (Зе)[(е > 0) л ('Фл«)(- (л» е )У) ч (Зл)(л > л«л — (/а„— а! < е)))] я я (Зе)[(е > О) «(Ъп«Нпа в Ф -+ (Эл)(п > и» л lа„- а! > е))].
Полученное утверждение можно записать компактнее, используя символику ограниченных кванторов: (Зе > О)('Фп«в ФНЭ и > л»)(!а„- а~ < е). Таким образом, утверждение «Число а не является пределом последовательности [а„]» раскрывается так: «Существует такое положительное число е, что для всякого натурального числа и, найдется такое натуральное и > л», что ~а„- а~ ~ е». Несходимость последовательности [а»] означает, что никакое число не является ее пределом, т.е.
('Фа)(а ~ 1цп а„). Это вместе с полученным утверждением дает («а)(Зе > 0)(Ъл«в ФНЗл > п»)(~а„- а~ > е). Пример 24.2. Запишем на языке логики предикатов определение простого числа: «Натуральное число х называется простым, если оно не равно 1 и при всяком разложении его в произведение двух натуральных чисел одно из них оказывается равным 1 или х»: -(х = 1) л (Фи)('Фи)(х = и . в -+ (и = 1) «(и = х)). Отрицание этого утверждения — утверждение того, что число х составное, записывается следующим образом: (х = !) «(Ли)(Бв)(х = и . о л и ~ 1 л и ю~ х). Предлагается самостоятельно разобраться в его составлении. Пример 24.3.
Определение «Точка х«из области определения функции 7' называется точкой локального максимума функции 7; если существует такая б-окрестность данной точки, что для всех х из этой окрестности Дх) <7 (х«)» на языке логики предикатов запишется так: х«в Р~ л (Зб > О)('Фх)(!х — х«! < б -» Ях) < Дх«)). Запишите самостоятельно отрицание данного утверждения. 197 Сраашение логики предикатов и логики высказываний. В начале 5 21 уже отмечалось, что язык и логика алгебры предикатов тоньше и точнее отражают процессы мышления, нежели язык и логика алгебры высказываний.
Приведем два примера, подтверждающих эту мыа~ь. Пример 24.4. Рассмотрим высказывание «Каждый человек имеет мать». Если на языке алгебры высказываний формулировка данного высказывания сведется лишь к обозначению его некоторой буквой, скажем А, то на языке логики предикатов возможна формализация, учитывающая внутреннюю (субъектно-предикатную) структуру этого высказывания. Действительно, пусть Р(х, у) — двухместный предикат «х есть мать у», определенный на множестве всех людей. Тогда данному высказыванию отвечает формула логики предикатов (яу)(Лх)(Р(х, у)). Рассматриваемое высказывание можно перевести на язык логики предикатов и иначе. Если ввести еще одноместный предикат Ц(х); «х есть человек», определенный на произвольном множестве, то высказывание запишется так: (Ъу)(о(у) -+ (Зх)(о(х) л Р(х, у))). Пример 24.5. Этот пример еще более наглядно демонстрирует выразительные возможности языка логики предикатов по сравнению с языком логики высказываний.
Рассмотрим два высказывания: «В Москве живет женщина, имеющая брата в Петербурге» и «В Петербурге живет мужчина, имеющий сестру в Москве». Каждое из данных утверждений следует из другого, т.е. они равносильны. Спрашивается, можно ли выразить эту равносильность на языке алгебры высказываний, на языке логики предикатов? Оказывается второе возможно, а первое нет. В самом деле, как мы могли бы формализовать данные высказывания на языке алгебры высказываний? Можно обозначить первое высказывание через А, второе — через В.
Ясно, что ни о какой равносильности формул А и В говорить не приходится. Можно расчленить данные высказывания на более простые: А, — «Женщина живет в Москве»; А, — «Женщина имеет брата в Петербурге»; В, — «Мужчина живет в Петербурге»; Вт — «Мужчина имеет сестру в Москве». Тогда первое исходное высказывание есть коньюнкция А, л Аь а второе — В, л Вь Но и эти две формулы алгебры высказываний не следуют одна из другой. В отличие от алгебры высказываний, формализация на языке логики предикатов позволяет обнаружить равносильность двух данных высказываний.
Действительно, введем предикаты, определенные на множестве людей: Р,(х) — «х — женшина»; Р,(х)— «х живет в Москве»; О,(у) — «у — мужчина»; Щу) — «у живет в Петербурге; Ю(х, у) — «х есть сестра у». Тогда высказыванию «В Москве живет женщина, имеющая брата в Петербурге» соответствует формула логики предикатов (Зх)(Р~(х) л Р2(х) л (Зу)(01(у) л 02(у) л 5(х, у))1, 198 а высказыванию «В Петербурге живет мужчина, имеющий сестру в Москве» вЂ” формула (Ву)[Я(у) л Ц2(у) л (Бх)(Р~(х) л Рз(х) л 5(х, у))].
Покажем, что полученные формулы равносильны, для чего первую из них равносильными преобразованиями сведем ко второй (предлагается обнаружить те равносильности логики предикатов, которые используются на каждом шаге преобразований): (3х)[Р~(х) л Рз(х) л (Лу)(01(у) л Щу) л Я(х, у))] =- и (Лх)(3у)[Р)(х) л Р2(х) л 0~(у) л Щу) л 5(х, у)] =- сч (3у)(Лх)[Ц1(у) л Щу) л Р~(х) л Р2(х) л 5(х, у)] в в (Бу)[о,(у) л Оз(у) л (Эх)(Р~(х) л Р2(х) л Ю(х, у))]. Строение математических теорем. Остановимся на формах теорем четырех видов, выделенных еще в аристотелевской логике„ основоположником которой был один из наиболее разносторонних мыслителей Древней Греции Аристотель (384 — 322 гг.
до н.э.), и названных категорическими суждениями. Многие математические теоремы имеют именно такой вид. Логика предикатов позволит проанализировать их строение, сравнить между собой, и этот анализ будет более тонким, нежели анализ строения теорем, проведенный в алгебре высказываний. (Впрочем можно заметить, что в алгебре высказываний этот анализ проходил несколько в ином аспекте, и оба анализа скорее дополняют друг друга.) Величайшая заслуга Аристотеля в области логики состоит в том, что он впервые систематизировал и подверг анализу с некоторой формальной точки зрения приемы рассуждений, уже практически широко применявшиеся его современниками, но до него остававшиеся еще теоретически неосознанными, несформулированными.
Он показал, что правильное рассуждение можно свести к систематическому применению небольшого числа неизменных правил, независимых от частной природы объектов, относительно которых происходит рассуждение. Тем самым Аристотель применил такие подходы к исследованию рассуждений, которые сделали логику наукой. С точки зрения современной формальной (математической) логики этот особый вид логических рассуждений, который подробно исследовал Аристотель и который получил название «силлогического», представляет собой небольшую и довольно элементарную часть, относящуюся к логике предикатов, причем — к логике одноместных предикатов.
В своем учении о силлогизме Аристотель выясняет общие закономерности, при которых из двух высказываний-посылок, имеющих вполне определенную логическую структуру (выражаемую специальными формулами логики предикатов, содержащими лишь одноместные предикатные пеРеменные), определенное заключение с необходимостью либо следует, либо не следует.
Современная форма силлогистики в ее 199 окончательном виде конечно же еще не содержится в трудах самого Аристотеля, она является результатом работы его многочисленных комментаторов и последователей — древнегреческих, древнеримских, арабских и средневековых логиков. Аристотель, проанализировав строение простых высказываний (или, как он говорил, «категорических суждений»)„пришел к выволу, что содержание любого из них может быть сведено к утверждению о наличии или отсутствии у предметов определенных свойств. При этом такие утверждения могут относиться не только к отдельным предметам, но и к классам предметов. Высказывание, в котором утверждается, что конкретный предмет обладает или не обладает определенным свойством, называется единичным (соответственно единичноутвердительным или единичноотрицательным). Например, высказывание «Число 10 четное» является единичноутвердительным. Его содержание сводится к утверждению о наличии у конкретного числа 10 свойства делимости на 2.
Высказывание, в котором утверждается, что все предметы класса обладают или не обладают определенным свойством, называется общим (соответственно общеутвердительным или общеотрицательиым). Например, высказывание «Все металлы тонут в воде» обще- утвердительное, а высказывание «Все простые числа не являются четными» общеотрицательное. Высказывание, в котором утверждается, что некоторые предметы класса обладают или не обладают определенным свойством, называется частным (соответственно частноутвердительвым или частноотрицательным). Например, высказывание «Некоторые реки впадают в озеро Байкал» является частноутвердительным, а высказывание «Некоторые прямоугольные треугольники не являются равнобедренными» вЂ” частноотрицательным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
