Логика первого порядка
Ло́гика пе́рвого поря́дка, называемая иногда логикой или исчислением предикатов — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высших порядков.
Содержание
Основные определения
Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов <math>\mathcal{F}</math> и множества предикатных символов <math>\mathcal{P}</math>. С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные, так и предикатные символы арности 0. Первые иногда выделяют в отдельное множество констант. Кроме того, используются следующие дополнительные символы:
- символы переменных (обычно <math>x</math>, <math>y</math>, <math>z</math>, <math>x_1</math>, <math>y_1</math>, <math>z_1</math>, <math>x_2</math>, <math>y_2</math>, <math>z_2</math> и т. д.);
- логические операции:
| Символ | Значение |
|---|---|
| <math>\neg</math> | Отрицание («не») |
| <math>\land</math> | Конъюнкция («и») |
| <math>\lor</math> | Дизъюнкция («или») |
| <math>\to</math> | Импликация («если ..., то ...») |
| Символ | Значение |
|---|---|
| <math>\forall</math> | Квантор всеобщности |
| <math>\exists</math> | Квантор существования |
Перечисленные символы вместе с символами из <math>\mathcal{P}</math> и <math>\mathcal{F}</math> образуют алфавит логики первого порядка. Более сложные конструкции определяются индуктивно.
- Терм есть символ переменной, либо имеет вид <math>f( t_1, \ldots, t_n )</math>, где <math>f</math> — функциональный символ арности <math>n</math>, а <math>t_1, \ldots, t_n</math> — термы.
- Атом (атомарная формула) имеет вид <math>p( t_1, \ldots, t_n )</math>, где <math>p</math> — предикатный символ арности <math>n</math>, а <math>t_1, \ldots, t_n</math> — термы.
- Например, <math>(x+1)*(x+1) \geqslant 0</math> это атомарная формула, истинная для любого действительного числа <math>x</math>. Формула состоит из 2-арного предиката <math>\geqslant</math>, аргументами которого являются термы <math>(x+1)*(x+1)</math> и 0. При этом терм <math>(x+1)*(x+1)</math> состоит из константы 1 (которую можно считать 0-арной функцией), переменной <math>x</math> и символов бинарных (2-арных) функций + и *.
- Формула — это либо атом, либо одна из следующих конструкций: <math>\neg F</math>, <math>F_1\lor F_2</math>, <math>F_1\land F_2</math>, <math>F_1\to F_2</math>, <math>\forall x F</math>, <math>\exists x F</math>, где <math>F, F_1, F_2</math> — формулы, а <math>x</math> — переменная.
Переменная <math>x</math> называется связанной в формуле <math>F</math>, если <math>F</math> имеет вид <math>\forall x G</math> либо <math>\exists x G</math>, или же представима в одной из форм <math>\neg H</math>, <math>F_1\lor F_2</math>, <math>F_1\land F_2</math>, <math>F_1\to F_2</math>, причём <math>x</math> уже связана в <math>H</math>, <math>F_1</math> и <math>F_2</math>. Если <math>x</math> не связана в <math>F</math>, её называют свободной в <math>F</math>. Формулу без свободных переменных называют замкнутой формулой, или предложением. Теорией первого порядка называют любое множество предложений.
Аксиоматика и доказательство формул
Система логических аксиом логики первого порядка состоит из аксиом исчисления высказываний дополненной двумя новыми аксиомами:
- <math>\forall x A \to A[t/x]</math>,
- <math>A[t/x] \to \exists x A</math>,
где <math>A[t/x]</math> — формула, полученная в результате подстановки терма <math>t</math> вместо каждой свободной переменной <math>x</math>, встречающейся в формуле <math>A</math>.
Правил вывода 2:
- Modus ponens:
- <math>\frac{A, A \to B}{B}</math>
- Правило обобщения (англ.):
- <math>\frac{A}{\forall x A}</math>
Интерпретация
В классическом случае интерпретация формул логики первого порядка задается на модели первого порядка, которая определяется следующими данными:
- Несущее множество <math>\mathcal{D}</math>,
- Семантическая функция <math>\sigma</math>, отображающая
- каждый <math>n</math>-арный функциональный символ <math>f</math> из <math>\mathcal{F}</math> в <math>n</math>-арную функцию <math>\sigma(f):\mathcal{D}\times\ldots\times\mathcal{D}\rightarrow\mathcal{D}</math>,
- каждый <math>n</math>-арный предикатный символ <math>p</math> из <math>\mathcal{P}</math> в <math>n</math>-арное отношение <math>\sigma(p)\subseteq\mathcal{D}\times\ldots\times\mathcal{D}</math>.
Обычно принято отождествлять несущее множество <math>\mathcal{D}</math> и саму модель, подразумевая неявно семантическую функцию, если это не ведет к неоднозначности.
Предположим, <math>s</math> — функция, отображающая каждую переменную в некоторый элемент из <math>\mathcal{D}</math>, которую мы будем называть подстановкой. Интерпретация <math>[\![t]\!]_s</math> терма <math>t</math> на <math>\mathcal{D}</math> относительно подстановки <math>s</math> задается индуктивно:
- <math>[\![x]\!]_s = s(x)</math>, если <math>x</math> — переменная,
- <math>[\![f(x_1,\ldots,x_n)]\!]_s = \sigma(f)([\!\![\,x_1]\!]_s,\ldots,[\![x_n]\!]_s)</math>
В таком же духе определяется отношение истинности <math>\models_s</math> формул на <math>\mathcal{D}</math> относительно <math>s</math>:
- <math>\mathcal{D}\models_s p(t_1,\ldots,t_n)</math>, тогда и только тогда, когда <math>\sigma(p)([\!\![\,t_1]\!]_s,\ldots,[\![t_n]\!]_s)</math>,
- <math>\mathcal{D}\models_s \neg\phi</math>, тогда и только тогда, когда <math>\mathcal{D}\models_s \phi</math> — ложно,
- <math>\mathcal{D}\models_s \phi\land\psi</math>, тогда и только тогда, когда <math>\mathcal{D}\models_s \phi</math> и <math>\mathcal{D}\models_s \psi</math> истинны,
- <math>\mathcal{D}\models_s \phi\lor\psi</math>, тогда и только тогда, когда <math>\mathcal{D}\models_s \phi</math> или <math>\mathcal{D}\models_s \psi</math> истинно,
- <math>\mathcal{D}\models_s \phi\to\psi</math>, тогда и только тогда, когда <math>\mathcal{D}\models_s \phi</math> влечет <math>\mathcal{D}\models_s \psi</math>,
- <math>\mathcal{D}\models_s \exists x\, \phi</math>, тогда и только тогда, когда <math>\mathcal{D}\models_{s'} \phi</math> для некоторой подстановки <math>s'</math>, которая отличается от <math>s</math> только значением на переменной <math>x</math>,
- <math>\mathcal{D}\models_s \forall x\, \phi</math>, тогда и только тогда, когда <math>\mathcal{D}\models_{s'} \phi</math> для всех подстановок <math>s'</math>, которые отличается от <math>s</math> только значением на переменной <math>x</math>.
Формула <math>\phi</math> истинна на <math>\mathcal{D}</math> (что обозначается как <math>\mathcal{D}\models \phi</math>), если <math>\mathcal{D}\models_s \phi</math> для всех подстановок <math>s</math>. Формула <math>\phi</math> называется общезначимой (что обозначается как <math>\models \phi</math>), если <math>\mathcal{D}\models \phi</math> для всех моделей <math>\mathcal{D}</math>. Формула <math>\phi</math> называется выполнимой, если <math>\mathcal{D}\models \phi</math> хотя бы для одной <math>\mathcal{D}</math>.
Свойства и основные результаты
Логика первого порядка обладает рядом полезных свойств, которые делают её очень привлекательной в качестве основного инструмента формализации математики. Главными из них являются:
- полнота (это означает, что для любой замкнутой формулы выводима либо она сама, либо её отрицание);
- непротиворечивость (ни одна формула не может быть выведена одновременно со своим отрицанием).
При этом если непротиворечивость более или менее очевидна, то полнота — нетривиальный результат, полученный Гёделем в 1930 году (теорема Гёделя о полноте). По сути теорема Гёделя устанавливает фундаментальную эквивалентность понятий доказуемости и общезначимости.
Логика первого порядка обладает свойством компактности: если некоторое множество формул не выполнимо, то невыполнимо также некоторое его конечное подмножество.
Согласно теореме Лёвенгейма — Скулема если множество формул имеет модель, то оно также имеет модель не более чем счётной мощности. С этой теоремой связан парадокс Скулема, который, однако, является лишь мнимым парадоксом.
Использование
Логика первого порядка как формальная модель рассуждений
Являясь формализованным аналогом обычной логики, логика первого порядка даёт возможность строго рассуждать об истинности и ложности утверждений и об их взаимосвязи, в частности, о логическом следовании одного утверждения из другого, или, например, об их эквивалентности. Рассмотрим классический пример формализации утверждений естественного языка в логике первого порядка.
Возьмем рассуждение «Каждый человек смертен. Конфуций — человек. Следовательно, Конфуций смертен». Обозначим «x есть человек» через ЧЕЛОВЕК(x) и «x смертен» через СМЕРТЕН(x). Тогда утверждение «каждый человек смертен» может быть представлено формулой: <math> \forall</math>x(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) утверждение «Конфуций — человек» формулой ЧЕЛОВЕК(Конфуций), и «Конфуций смертен» формулой СМЕРТЕН(Конфуций). Утверждение в целом теперь может быть записано формулой
См. также
Напишите отзыв о статье "Логика первого порядка"
Литература
- Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947
- Клини С. К. Введение в метаматематику. М., 1957
- Мендельсон Э. Введение в математическую логику. М., 1976
- Новиков П. С. Элементы математической логики. М., 1959
- Черч А. Введение в математическую логику, т. I. М. 1960
Отрывок, характеризующий Логика первого порядка
Он оглянулся на кузину и на гостью барышню: обе смотрели на него с улыбкой одобрения.– Нынче обедает у нас Шуберт, полковник Павлоградского гусарского полка. Он был в отпуску здесь и берет его с собой. Что делать? – сказал граф, пожимая плечами и говоря шуточно о деле, которое, видимо, стоило ему много горя.
– Я уж вам говорил, папенька, – сказал сын, – что ежели вам не хочется меня отпустить, я останусь. Но я знаю, что я никуда не гожусь, кроме как в военную службу; я не дипломат, не чиновник, не умею скрывать того, что чувствую, – говорил он, всё поглядывая с кокетством красивой молодости на Соню и гостью барышню.
Кошечка, впиваясь в него глазами, казалась каждую секунду готовою заиграть и выказать всю свою кошачью натуру.
– Ну, ну, хорошо! – сказал старый граф, – всё горячится. Всё Бонапарте всем голову вскружил; все думают, как это он из поручиков попал в императоры. Что ж, дай Бог, – прибавил он, не замечая насмешливой улыбки гостьи.
Большие заговорили о Бонапарте. Жюли, дочь Карагиной, обратилась к молодому Ростову:
– Как жаль, что вас не было в четверг у Архаровых. Мне скучно было без вас, – сказала она, нежно улыбаясь ему.
Польщенный молодой человек с кокетливой улыбкой молодости ближе пересел к ней и вступил с улыбающейся Жюли в отдельный разговор, совсем не замечая того, что эта его невольная улыбка ножом ревности резала сердце красневшей и притворно улыбавшейся Сони. – В середине разговора он оглянулся на нее. Соня страстно озлобленно взглянула на него и, едва удерживая на глазах слезы, а на губах притворную улыбку, встала и вышла из комнаты. Всё оживление Николая исчезло. Он выждал первый перерыв разговора и с расстроенным лицом вышел из комнаты отыскивать Соню.
– Как секреты то этой всей молодежи шиты белыми нитками! – сказала Анна Михайловна, указывая на выходящего Николая. – Cousinage dangereux voisinage, [Бедовое дело – двоюродные братцы и сестрицы,] – прибавила она.
– Да, – сказала графиня, после того как луч солнца, проникнувший в гостиную вместе с этим молодым поколением, исчез, и как будто отвечая на вопрос, которого никто ей не делал, но который постоянно занимал ее. – Сколько страданий, сколько беспокойств перенесено за то, чтобы теперь на них радоваться! А и теперь, право, больше страха, чем радости. Всё боишься, всё боишься! Именно тот возраст, в котором так много опасностей и для девочек и для мальчиков.
– Всё от воспитания зависит, – сказала гостья.
– Да, ваша правда, – продолжала графиня. – До сих пор я была, слава Богу, другом своих детей и пользуюсь полным их доверием, – говорила графиня, повторяя заблуждение многих родителей, полагающих, что у детей их нет тайн от них. – Я знаю, что я всегда буду первою confidente [поверенной] моих дочерей, и что Николенька, по своему пылкому характеру, ежели будет шалить (мальчику нельзя без этого), то всё не так, как эти петербургские господа.
– Да, славные, славные ребята, – подтвердил граф, всегда разрешавший запутанные для него вопросы тем, что всё находил славным. – Вот подите, захотел в гусары! Да вот что вы хотите, ma chere!
– Какое милое существо ваша меньшая, – сказала гостья. – Порох!
– Да, порох, – сказал граф. – В меня пошла! И какой голос: хоть и моя дочь, а я правду скажу, певица будет, Саломони другая. Мы взяли итальянца ее учить.
– Не рано ли? Говорят, вредно для голоса учиться в эту пору.
– О, нет, какой рано! – сказал граф. – Как же наши матери выходили в двенадцать тринадцать лет замуж?
– Уж она и теперь влюблена в Бориса! Какова? – сказала графиня, тихо улыбаясь, глядя на мать Бориса, и, видимо отвечая на мысль, всегда ее занимавшую, продолжала. – Ну, вот видите, держи я ее строго, запрещай я ей… Бог знает, что бы они делали потихоньку (графиня разумела: они целовались бы), а теперь я знаю каждое ее слово. Она сама вечером прибежит и всё мне расскажет. Может быть, я балую ее; но, право, это, кажется, лучше. Я старшую держала строго.
– Да, меня совсем иначе воспитывали, – сказала старшая, красивая графиня Вера, улыбаясь.
Но улыбка не украсила лица Веры, как это обыкновенно бывает; напротив, лицо ее стало неестественно и оттого неприятно.
Старшая, Вера, была хороша, была неглупа, училась прекрасно, была хорошо воспитана, голос у нее был приятный, то, что она сказала, было справедливо и уместно; но, странное дело, все, и гостья и графиня, оглянулись на нее, как будто удивились, зачем она это сказала, и почувствовали неловкость.
– Всегда с старшими детьми мудрят, хотят сделать что нибудь необыкновенное, – сказала гостья.
– Что греха таить, ma chere! Графинюшка мудрила с Верой, – сказал граф. – Ну, да что ж! всё таки славная вышла, – прибавил он, одобрительно подмигивая Вере.
Гостьи встали и уехали, обещаясь приехать к обеду.
– Что за манера! Уж сидели, сидели! – сказала графиня, проводя гостей.
Когда Наташа вышла из гостиной и побежала, она добежала только до цветочной. В этой комнате она остановилась, прислушиваясь к говору в гостиной и ожидая выхода Бориса. Она уже начинала приходить в нетерпение и, топнув ножкой, сбиралась было заплакать оттого, что он не сейчас шел, когда заслышались не тихие, не быстрые, приличные шаги молодого человека.
Наташа быстро бросилась между кадок цветов и спряталась.
Борис остановился посереди комнаты, оглянулся, смахнул рукой соринки с рукава мундира и подошел к зеркалу, рассматривая свое красивое лицо. Наташа, притихнув, выглядывала из своей засады, ожидая, что он будет делать. Он постоял несколько времени перед зеркалом, улыбнулся и пошел к выходной двери. Наташа хотела его окликнуть, но потом раздумала. «Пускай ищет», сказала она себе. Только что Борис вышел, как из другой двери вышла раскрасневшаяся Соня, сквозь слезы что то злобно шепчущая. Наташа удержалась от своего первого движения выбежать к ней и осталась в своей засаде, как под шапкой невидимкой, высматривая, что делалось на свете. Она испытывала особое новое наслаждение. Соня шептала что то и оглядывалась на дверь гостиной. Из двери вышел Николай.
– Соня! Что с тобой? Можно ли это? – сказал Николай, подбегая к ней.
– Ничего, ничего, оставьте меня! – Соня зарыдала.
– Нет, я знаю что.
– Ну знаете, и прекрасно, и подите к ней.
– Соооня! Одно слово! Можно ли так мучить меня и себя из за фантазии? – говорил Николай, взяв ее за руку.
Соня не вырывала у него руки и перестала плакать.
Наташа, не шевелясь и не дыша, блестящими главами смотрела из своей засады. «Что теперь будет»? думала она.
– Соня! Мне весь мир не нужен! Ты одна для меня всё, – говорил Николай. – Я докажу тебе.
– Я не люблю, когда ты так говоришь.
– Ну не буду, ну прости, Соня! – Он притянул ее к себе и поцеловал.
«Ах, как хорошо!» подумала Наташа, и когда Соня с Николаем вышли из комнаты, она пошла за ними и вызвала к себе Бориса.
– Борис, подите сюда, – сказала она с значительным и хитрым видом. – Мне нужно сказать вам одну вещь. Сюда, сюда, – сказала она и привела его в цветочную на то место между кадок, где она была спрятана. Борис, улыбаясь, шел за нею.
– Какая же это одна вещь ? – спросил он.
Она смутилась, оглянулась вокруг себя и, увидев брошенную на кадке свою куклу, взяла ее в руки.
– Поцелуйте куклу, – сказала она.
Борис внимательным, ласковым взглядом смотрел в ее оживленное лицо и ничего не отвечал.
– Не хотите? Ну, так подите сюда, – сказала она и глубже ушла в цветы и бросила куклу. – Ближе, ближе! – шептала она. Она поймала руками офицера за обшлага, и в покрасневшем лице ее видны были торжественность и страх.
– А меня хотите поцеловать? – прошептала она чуть слышно, исподлобья глядя на него, улыбаясь и чуть не плача от волненья.
Борис покраснел.
– Какая вы смешная! – проговорил он, нагибаясь к ней, еще более краснея, но ничего не предпринимая и выжидая.
Она вдруг вскочила на кадку, так что стала выше его, обняла его обеими руками, так что тонкие голые ручки согнулись выше его шеи и, откинув движением головы волосы назад, поцеловала его в самые губы.
Она проскользнула между горшками на другую сторону цветов и, опустив голову, остановилась.
– Наташа, – сказал он, – вы знаете, что я люблю вас, но…
– Вы влюблены в меня? – перебила его Наташа.
– Да, влюблен, но, пожалуйста, не будем делать того, что сейчас… Еще четыре года… Тогда я буду просить вашей руки.
Наташа подумала.
– Тринадцать, четырнадцать, пятнадцать, шестнадцать… – сказала она, считая по тоненьким пальчикам. – Хорошо! Так кончено?
