Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Применение логики предикатов к математической практике

Применение логики предикатов к математической практике


Некоторые современные математики и методисты склонны относить математику как науку и как учебный предмет к разряду гуманитарных дисциплин, поскольку она изучает язык, на котором, по образному выражению Галилея, написана грандиозная книга — Вселенная. Конечно, здесь речь идет о специфическом языке — языке математическом. Но математика, развиваясь, довела свой язык до такого совершенства и такой выразительной силы, что он вплотную приблизился по своим информационно-выразительным свойствам к общечеловеческому языку. Такого совершенства математический язык достиг, когда математикой был разработан язык математической логики и прежде всего язык логики предикатов. Язык логики предикатов — это, по существу, открытое вторжение математики в общечеловеческий язык, математизация общечеловеческого языка с целью более точного, более адекватного его использования в первую очередь в самой математике. В языке логики предикатов соединились логика мышления, без которой немыслим общечеловеческий язык, и математика. В человеческий язык вошла математика, а математический язык стал почти неотличим от общечеловеческого, слился с ним.


Поэтому умение грамотно оперировать языком логики предикатов (читай — языком математической логики) является основой современной логической культуры вообще. В связи с этим в настоящем параграфе мы уделим немало внимания записи на языке логики предикатов различных математических предложений, что будет способствовать более глубокому пониманию их структуры.


Практически важнейшей сферой применения логики предикатов к логико-математической практике является сфера построения доказательств различных теорем, основывающаяся на теории логического следования. Более сложное строение формул логики предикатов, по сравнению с формулами логики высказываний, дает возможность проводить более сложные доказательства и в результате получать более тонкие заключения. В настоящем параграфе мы попытаемся на простейших примерах проиллюстрировать суть теории логического вывода и ее применение.


Будут рассмотрены также приложения логики предикатов к теории множеств, к анализу аристотелевой силлогистики.




Запись на языке логики предикатов различных предложений


С помощью кванторной символики удобно записывать формулировки различных определений и теорем. В процессе такой записи приходится осмысливать данное предложение, отчетливо выявлять в нем посылки и следствие (если это теорема), очерчивать более широкий круг понятий и четко выявлять ограничивающее условие (если это определение). Одним словом, перевод расплывчатой словесной формулировки на строгий, не допускающий противоречивых толкований язык логики предикатов способствует четкости и ясности мышления. Рассмотрим некоторые примеры.




Пример 24.1. Определение предела последовательности "Число а называется пределом последовательности \{a_n\}, если для всякого положительного числа \varepsilon>0 существует такое натуральное число n_0, что для всякого натурального n, большего n_0,\,|a_n-a|< \varepsilon" на языке логики предикатов записывается так:


a=\lim a_n \overset{\text{def}}{\Leftrightarrow} (\forall \varepsilon) \bigl[\varepsilon>0\to (\exists n_0) \bigl(n_0\in \mathbb{N}\land (\forall n)(n>n_0\to |a_n-a|< \varepsilon)\bigr)\bigr].

Используя символику ограниченных кванторов, это определение можно записать компактнее:


a=\lim a_n \overset{\text{def}}{\Leftrightarrow} (\forall \varepsilon>0)(\exists n_0\in \mathbb{N})(\forall n>n_0)(|a_n-a|< \varepsilon).

Нередко требуется доказать, что некоторое число а не является пределом последовательности \{a_n\}, то есть a\ne\lim a_n. Для доказательства нужно построить утверждение, являющееся отрицанием сформулированного определения. Поможет в этом логика предикатов. Используя равносильности логики предикатов, преобразуем отрицание исходной формулы к приведенному виду:


\begin{aligned}\lnot & (\forall \varepsilon) \bigl[\varepsilon>0\to (\exists n_0) \bigl(n_0\in \mathbb{N}\land (\forall n)(n>n_0\to |a_n-a|< \varepsilon)\bigr)\bigr]\cong\\[2pt] &\cong (\exists \varepsilon)\lnot \bigl[\lnot (\varepsilon>0)\lor (\exists n_0) \bigl(n_0\in \mathbb{N}\land (\forall n)(n>n_0\to |a_n-a|< \varepsilon\bigr)\bigr]\cong\\[2pt] &\cong (\exists \varepsilon) \bigl[(\varepsilon>0)\land (\forall n_0) \bigl(\lnot (n_0\in \mathbb{N}) \lor\lnot (\forall n) (\lnot (n>n_0) \lor |a_n-a|< \varepsilon)\bigr)\bigr]\cong\\[2pt] &\cong (\exists \varepsilon) \bigl[(\varepsilon>0)\land (\forall n_0) \bigl(\lnot (n_0\in \mathbb{N}) \lor (\exists n) (n>n_0 \land\lnot (|a_n-a|< \varepsilon))\bigr)\bigr]\cong\\[2pt] &\cong (\exists \varepsilon) \bigl[(\varepsilon>0)\land (\forall n_0) \bigl(n_0\in \mathbb{N}\to (\exists n) (n>n_0\land |a_n-a| \geqslant \varepsilon)\bigr)\bigr]. \end{aligned}

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


(\exists \varepsilon>0) (\forall n_0\in \mathbb{N}) (\exists n>n_0) (|a_n-a| \geqslant \varepsilon).

Таким образом, утверждение "Число а не является пределом последовательности \{a_n\}" раскрывается так: "Существует такое положительное число \varepsilon, что для всякого натурального числа n_0 найдется такое натуральное n>n_0, что |a_n-a| \geqslant \varepsilon".


Несходимость последовательности \{a_n\} означает, что никакое число не является ее пределом, т.е. (\forall a)(a\ne \lim a_n). Это вместе с полученным утверждением дает


(\forall a) (\exists \varepsilon>0) (\forall n_0\in \mathbb{N}) (\exists n>n_0) (|a_n-a| \geqslant \varepsilon).



Пример 24.2. Запишем на языке логики предикатов определение простого числа: "Натуральное число x называется простым, если оно не равно 1 и при всяком разложении его в произведение двух натуральных чисел одно из них оказывается равным 1 или x":


\lnot (x=1) \land (\forall u) (\forall v) \bigl(x=u\cdot v\to (u=1)\lor (u=x)\bigr).

Отрицание этого утверждения — утверждение того, что число x составное, записывается следующим образом:


(x=1)\lor (\exists u)(\exists v) (x=u\cdot v\land u\ne 1\land u\ne x).

Предлагается самостоятельно разобраться в его составлении.


Пример 24.3. Определение "Точка x_0 из области определения функции / называется точкой локального максимума функции f, если существует такая 8-окрестность данной точки, что для всех x из этой окрестности f(x)<f(x_0)" на языке логики предикатов запишется так:

x_0\in D_f\land (\exists\delta>0) (\forall x) \bigl(|x-x_0|<\delta\to f(x)< f(x_0)\bigr).


Запишите самостоятельно отрицание данного утверждения.




Сравнение логики предикатов и логики высказываний


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


Пример 24.4. Рассмотрим высказывание "Каждый человек имеет мать". Если на языке алгебры высказываний формулировка данного высказывания сведется лишь к обозначению его некоторой буквой, скажем A, то на языке логики предикатов возможна формализация, учитывающая внутреннюю (субъектно-предикатную) структуру этого высказывания. Действительно, пусть P(x,y) — двухместный предикат "x есть мать y", определенный на множестве всех людей. Тогда данному высказыванию отвечает формула логики предикатов (\forall y)(\exists x)(P(x,y)). Рассматриваемое высказывание можно перевести на язык логики предикатов и иначе. Если ввести еще одноместный предикат Q(x)\colon "x есть человек", определенный на произвольном множестве, то высказывание запишется так:


(\forall y)\bigl(Q(y)\to (\exists x)(Q(x)\land P(x,y))\bigr).

Пример 24.5. Этот пример еще более наглядно демонстрирует выразительные возможности языка логики предикатов по сравнению с языком логики высказываний. Рассмотрим два высказывания: "В Москве живет женщина, имеющая брата в Петербурге" и "В Петербурге живет мужчина, имеющий сестру в Москве". Каждое из данных утверждений следует из другого, т.е. они равносильны. Спрашивается, можно ли выразить эту равносильность на языке алгебры высказываний, на языке логики предикатов? Оказывается второе возможно, а первое нет.


В самом деле, как мы могли бы формализовать данные высказывания на языке алгебры высказываний? Можно обозначить первое высказывание через A, второе — через B. Ясно, что ни о какой равносильности формул A и B говорить не приходится. Можно расчленить данные высказывания на более простые: A_1 — "Женщина живет в Москве"; A_2 — "Женщина имеет брата в Петербурге"; B_1 — "Мужчина живет в Петербурге"; B_2 — "Мужчина имеет сестру в Москве". Тогда первое исходное высказывание есть конъюнкция A_1\land A_2, а второе — B_1\land B_2. Но и эти две формулы алгебры высказываний не следуют одна из другой.


В отличие от алгебры высказываний, формализация на языке логики предикатов позволяет обнаружить равносильность двух данных высказываний. Действительно, введем предикаты, определенные на множестве людей: P_1(x) — "x — женщина"; P_2(x) — "x живет в Москве"; Q_1(y) — "y — мужчина"; Q_2(y) — "y живет в Петербурге; S(x,y) — "x есть сестра y". Тогда высказыванию "В Москве живет женщина, имеющая брата в Петербурге" соответствует формула логики предикатов


(\exists x)\bigl[P_1(x)\land P_2(x)\land (\exists y)\bigl(Q_1(y)\land Q_2(y)\land S(x,y)\bigr)\bigr],

а высказыванию "В Петербурге живет мужчина, имеющий сестру в Москве" — формула


(\exists y)\bigl[Q_1(y)\land Q_2(y)\land (\exists x)\bigl(P_1(x)\land P_2(x)\land S(x,y)\bigr)\bigr],

Покажем, что полученные формулы равносильны, для чего первую из них равносильными преобразованиями сведем ко второй (предлагается обнаружить те равносильности логики предикатов, которые используются на каждом шаге преобразований):


\begin{aligned}&(\exists x)\bigl[P_1(x)\land P_2(x)\land (\exists y)\bigl(Q_1(y)\land Q_2(y)\land S(x,y)\bigr)\bigr]\cong\\[2pt] &\cong (\exists x) (\exists y) \bigl[P_1(x)\land P_2(x)\land Q_1(y)\land Q_2(y)\land S(x,y)\bigr]\cong\\[2pt] &\cong (\exists y) (\exists x) \bigl[Q_1(y)\land Q_2(y)\land P_1(x)\land P_2(x)\land S(x,y)\bigr]\cong\\[2pt] &\cong (\exists y) \bigl[Q_1(y)\land Q_2(y)\land (\exists x)\bigl(P_1(x)\land P_2(x)\land S(x,y)\bigr)\bigr]\end{aligned}
Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved