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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


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


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


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




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


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




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


[math]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].[/math]

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


[math]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).[/math]

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


[math]\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}[/math]

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


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

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


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


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



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


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

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


[math](x=1)\lor (\exists u)(\exists v) (x=u\cdot v\land u\ne 1\land u\ne x).[/math]

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


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

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


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




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


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


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


[math](\forall y)\bigl(Q(y)\to (\exists x)(Q(x)\land P(x,y))\bigr).[/math]

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


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


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


[math](\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],[/math]

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

[math](\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],[/math]

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


[math]\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}[/math]

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


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

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