Игошин Математическая логика и теория алгоритмов (1019110), страница 47
Текст из файла (страница 47)
к задаче, имеющей алгоритмическое решение. Следовательно, и наша исходная проблема разрешения общезначимости для класса формул логики предикатов, содержащих только одноместные предикаты, разрешима. Проблема разрешения общезначимости и мощность множества, иа котором рассматривается формула. Обратимся к проблеме общезначимости. Теорема Левенгейма, отмеченная выше, применительно к проблеме разрешения общезначимости звучит так: если формула тождественно истинна в счетно-бесконечной области, то она общезначима. Но снова, как и для проблемы выполнимости формул, переход от (счетно) бесконечных множеств к конечным или обратно является качественным. Следующий пример показывает, что, в отличие от проблемы выполнимости, разрешимость проблемы общезначимости на некотором множестве не влечет ее разрешимости на множестве, объемлющем данное.
Пример 23.4. Докажем, что следующая формула тождественно истинна на любом конечном множестве, но не является таковой на бесконечном множестве: (~гх, у, г)[А(х, х) л (А(х, г) — » (А(х, у) ч А(у, г)))) -» -+ (Лх)(ч'у)(А(х, у)). Во-первых, отметим, что предикат «х < у», заданный на бесконечном множестве У, превращает данную формулу в ложное высказывание: (ч'х, у, г) [х < х л (х < г -» (х < у ~ у < г))1 — > (Лх) ( чу)(х < у), ибо посылка этой импликации истинна, а следствие ложно.
Во-вторых, докажем, что данная формула тождественно истинна на любом конечном множестве. Доказательство будем вести индукцией по числу элементов в множестве. Для М= (а,) это очевидно (убедитесь самостоятельно). Если М= (ап аз), то истинными будут утверждения А(а„а,), А(аз, аз) и А(а1, а,) -+ (А(ан аз) м ч А(ац а,)), а значит, и дизъюнкция А(ао аз) ч А(ап а,). Если при этом истинно А(а„а,), то истинно (~у)(А(ан у)), т.е. истинны заключение (Зх)('Фу)(А(х, у)) импликации данной формулы и вся данная формула. Аналогично, если истинно А(аъ а,), то истинно (~УУ)(А(аг, У)) и снова истинна всЯ даннаи фоРмУла.
193 Предположим теперь, что данная формула тождественно истинна на всяком конечном множестве, содержащем не больше, чем и элементов. Покажем тогда, что она будет тождественно истинна и на любом (и+ !)-элементном множестве. Пусть М= (аь ..., а„, а„,). В силу тождественной истинности данной формулы на и-элементном подмножестве М' = (аь ..., а„) и предположения истинности на М' посылки данной формулы, имеем истинные высказывания: ('Фх)(А(х, х)) и ('Фх)(А(х, х) -~ (Уу)(А(х, у) " А(у х))). Тогда истинно заключение (Зх) (Ъу)(А(х, у)). Не нарушая общности, можно считать, что таким х будет элемент ап т.е.
('Фу)(А(аь у)), т.е. истинны все утверждения А(ап а,), ..., А(аь а„). Мы хотим доказать, что данная формула истинна на (и+ !)-элементном множестве М= (а„..., а„, а„,,). Для этого нужно показать, что на нем в предположении истинности посылки данной формулы верно ее заключение (Зх) ('Фу)(А(х, у)). Если верно А(а„ а„,,), то утверждение доказано.
Если же А(а„а„,,) неверно, то, в силу истинности дизъюнкции А(а„а„,,) ~~ А(а„, „а,), заключаем, что истинно А(а„, „а,). Далее, в силу истинности в М посылки (Ъх, у, г)(А(х, х) — > — ~(А(х, у) ч А(у, г))) и утверждений А(аь аг), ..., А(аь а„), приходим к истинности всех следующих дизъюнкций: А(а„а„„,) ~~ ч А(а„, и аз), ..., А(а„а„,,) ч А(а„, „а„). Поскольку первый член каждой дизъюнкции ложен, то истинны все вторые члены А(а„,, аз), ..., А(а„, „а„). Учитывая еше и истинность А(а„, „а,) и, кроме того, А(а„, „а„,,), приходим к истинности утверждения (Чу)(А(а„, „у)) на М. Это означает истинность на М заключения данной формулы (Зх) (чу)(А(х, у)) и всей данной формулы. Ситуация с проблемой разрешимости общезначимости, отмеченная в рассмотренном примере, имеет место не только при переходе от конечного множества к бесконечному, но и при переходе от одного конечного к другому конечному, содержащему большее количество элементов.
Соответствующий пример формулы, тождественно истинной в области из трех элементов и не являющейся таковой в области из четырех элементов, приведен в Задачнике„Мо 9. 57. Решение проблемы для У-формул и 3-формул. В заключение покажем, как решается проблема разрешения общезначимости еше для двух классов формул логики предикатов — Ъ'-формул и 3-формул: и в этих случаях она сводится к тождественной истинности формул на конечных множествах.
Под 1г'-формулой понимается формула (Ъх,)(Ухз) ... (Ъх„)(Г(Рп Р,, ..., Р„)), у которой в предваренной нормальной форме кванторная часть содержит только кван- торы общности, а под 3-формулой понимается формула (Зх,)(Зхз) ... (Зх„)(Г(Рп Р„..., Рь)), у которой в предваренной нормальной форме кванторная часть содержит только кванторы существования, причем Р, = Р,(х„х,, ..., х„), ~ = 1, 2, ..., lс. !94 Теорема 23.5. Ъ'-формула (чх1) ... (Ъх„)(Р(Рп „,„Рг)) общезначима тогда и только тогда, когда она тождественно истинна на л-элементном множестве.
Доказательство. Всамомделе, пустьданнаяформулатождественно истинна на некотором н-элементном множестве. Тогда ясно, что она тождественно истинна на любом и-элементном множестве (это следует из наличия взаимно-однозначного отображения этих множеств друг на друга). Тогда на всяком л-элементном множестве будет тождественно истинна и формула Р(Рь ..., Рь). Рассмотрим теперь интерпретацию на произвольном множестве: Р, = А„..., Рь = А». Получим конкретный предикат Р(Аь ..., А„), зависящий от и переменных. Подставляя вместо них конкретные предметы, мы фактически имеем дело с н-элементным множеством, на котором этот предикат тождественно истинен. Значит, он будет тождественно истинен и на всем данном множестве.
Значит, формула Р(рп ..., Р„) тождественно истинна на любом множестве, а вместе с ней тождественно истинна на любом множестве, т. е. общезначима, и формула (Ъх,) ... (Ъх„)(Р(Рь ..., Р„)). П Теорема 23.б. 3-формула (Зх,) ... (Зх„КР(рь ..., Рг)) общезначима тогда и только тогда, когда она тождественно истинна на одно- элементном множестве. Доказательство этой теоремы аналогично доказательству предыдущей теоремы. Проведите его самостоятельно. Итак, рассмотрения настоящего параграфа красноречиво демонстрируют, что в то время как в алгебре высказываний проблемы разрешимости выполнимости и общезначимости формул решались сравнительно легко, в логике предикатов они представляют собой весьма трудные и, в целом, отнюдь не решенные до конца проблемы.
$ 24. Применение логики предикатов к логико-математической практике Некоторые современные математики и методисты склонны относить математику как науку и как учебный предмет к разряду "уманитарных дисциплин, поскольку она изучает язык, на котоРом, по образному выражению Галилея, написана грандиозная книга — Вселенная. Конечно, здесь речь идет о специфическом языке — языке математическом. Но математика, развиваясь, довела свой язык до такого совершенства и такой выразительной силы, что он вплотную приблизился по своим информационно- выразительным свойствам к общечеловеческому языку. Такого совершенства математический язык достиг, когда математикой был разработан язык математической логики и прежде всего язык логики предикатов. язык логики предикатов — это, по существу, открытое вторжение математики в общечеловеческий язык, 195 математизация общечеловеческого языка с целью более точного, более адекватного его использования в первую очередь в самой математике.
В языке логики предикатов соединились логика мышления, без которой немыслим общечеловеческий язык, и математика. В человеческий язык вошла математика, а математический язык стал почти неотличим от общечеловеческого, слился с ним. Поэтому умение грамотно оперировать языком логики предикатов (читай — языком математической логики) является основой современной логической культуры вообще. В связи с этим в настоящем параграфе мы уделим немало внимания записи на языке логики предикатов различных математических предложений, что будет способствовать более глубокому пониманию их структуры.
Практически важнейшей сферой применения логики предикатов к логико-математической практике является сфера построения доказательств различных теорем, основывающаяся на теории логического следования. Более сложное строение формул логики предикатов, по сравнению с формулами логики высказываний, дает возможность проводить более сложные доказательства и в результате получать более тонкие заключения. В настоящем параграфе мы попытаемся на простейших примерах проиллюстрировать суть теории логического вывода и ее применение.
Будут рассмотрены также приложения логики предикатов к теории множеств, к анализу аристотелевой силлогистики. Запись на языке логики нредикатов различных предложений. С помощью кванторной символики удобно записывать формулировки различных определений и теорем. В процессе такой записи приходится осмысливать данное предложение, отчетливо выделять в нем посылки и следствие (если это теорема), очерчивать более широкий круг понятий и четко выделять ограничивающее условие (если это определение). Одним словом, перевод расплывчатой словесной формулировки на строгий, не допускающий противоречивых толкований язык логики предикатов способствует четкости и ясности мышления.
Рассмотрим некоторые примеры. Пример 24.1. Определение предела последовательности «Число а называется пределом последовательности (ап), если для всякого положительного числа е > 0 существует такое натуральное число л,, что для всякого натурального л, большего пр, 1а„- а~ < е» на языке логики предикатов записывается так: апр. а = 1пп а„<» (ре) [е > 0 — р (ЗпрНпр о Ф л (рлНл > ло — р!о„- о1 < е))].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
