Логическое высказывание

, тогда и только тогда, когда  для некоторой подстановки s', которая отличается от s только на переменной x,

, тогда и только тогда, когда  для всех подстановок s', которые отличается от s только на переменной x.

Формула φ, истинна на , что обозначается как , если , для всех подстановок s. Формула φ называется общезначимой, что обозначается как , если для всех моделей . Формула φ называется выполнимой , если хотя бы для одной .

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

Логика первого порядка  обладает свойством компактности: если некоторое множество формул не выполнимо, то невыполнимо также некоторое его конечное подмножество.

Согласно теореме Левенгейма - Сколема если множество формул имеет модель, то оно также имеет модель не более чем счетной мощности. С этой теоремой связан парадокс Сколема, который, однако, является лишь мнимым парадоксом.

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

Возьмем рассуждение «Каждый  человек смертен. Конфуций - человек. Следовательно, Конфуций смертен». Обозначим «x есть человек» через ЧЕЛОВЕК(x) и «x смертен» через СМЕРТЕН(x). Тогда утверждение «каждый человек смертен» может быть представлено формулой: x(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) утверждение «Конфуций - человек» формулой ЧЕЛОВЕК(Конфуций), и «Конфуций смертен» формулой СМЕРТЕН(Конфуций). Утверждение в целом теперь может быть записано формулой

Логика второго  порядка - расширяет логику первого порядка, позволяя проводить квантификацию общности и существования не только над атомами, но и над предикатами.

Логика второго порядка  не упрощается к логике первого порядка.

 

ГЛАВА 2. ПОНЯТИЕ ПРЕДИКАТА

2.1. Предикаты и кванторы

Алгебра предикатов – тот  раздел математической логики, который  непосредственно надстраивается над  алгеброй высказываний.

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

Действительно, рассмотрим следующие простейшие заключения.

Из истинных высказываний «3 меньше 5» и «5 меньше 7» мы заключаем, что «3 меньше 7». Из истинных высказываний «Все птицы – животные» и «Все воробьи – птицы» мы делаем заключение: «Все воробьи – животные». Из высказываний «Петр – сын Ивана» и «Павел – сын Петра» мы заключаем: «Павел – внук Ивана» и т. д.

Заметим, что во всех рассмотренных  примерах истинность заключения зависит  не только от истинности посылок, но и  от их содержания. Если изменить вид  посылок, то может оказаться, что  заключение будет неверным. Так (в  первом примере) из истинных высказываний «3 меньше 5» и «5 не равно 7» нельзя делать заключение (которое оказывается  истинным), что «3 меньше 7», или, изменив  немного второй пример, из истинных высказываний «Все птицы – животные»  и «Никакие рыбы не птицы» нельзя выводить ни ложное высказывание «Никакие рыбы не животные», ни истинное высказывание «Все рыбы – животные». Наконец, видоизменив  последний пример, из истинных высказываний «Петр – сын Ивана» и «Павел – родственник Петра» мы не имеем  права делать заключение (которое  в действительности может быть как  истинным, так и ложным), что «Павел – внук Ивана» (но можем вывести  истинное заключение: «Павел – родственник  Ивана»).

Чтобы построить систему  правил, позволяющую логически выводить правильные заключения, учитывающие  в какой-то мере содержание посылок, мы должны проанализировать строение простых высказываний. И здесь  нам опять кое-что может подсказать грамматика. Следуя по такому пути, мы придем к разделу логики, называемому  алгеброй предикатов. Она предполагает алгебру высказываний уже известной, но идет дальше: простые высказывания, из которых состоят сложные, в  свою очередь расчленяются.

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

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

Рассмотрим сначала некоторое  число простых предложений –  высказываний, выражающих, что некоторый  объект обладает некоторым свойством:

«Сократ – грек»;

«Платон – ученик Сократа»;

«Три – простое число»;

«Василий – студент» и  т. д. ,

Все приведенные примеры  – простые предложения, С точки  зрения грамматики они состоят из подлежащего («Сократ», «Платон», «три», «Москва», «Василий») и сказуемого («есть  грек», «есть ученик Сократа», «есть  простое число»). Подлежащее является наименованием некоторого объекта  – конкретного или абстрактного, сказуемое выражает некоторое свойство. В латинской грамматике сказуемое  называется предикатом, и этим термином принято теперь пользоваться в математической логике в рассматриваемых ситуациях. Основным для алгебры предикатов является второй член предложения –  сказуемое-свойство. Как же алгебра  предикатов трактует понятие «свойство»? Она рассматривает его как  некоторую функцию следующим  образом.

Возьмем первый пример: «Сократ  есть грек».

Вместо человека Сократ мы можем подставить имена всевозможных людей и будем получать всегда осмысленные предложения. Одни предложения  будут истинными, другие – ложными:

«Сократ есть грек» –  истинно;

«Платон есть грек» –  истинно;

«Наполеон есть грек» –  ложно;

«Ньютон есть грек» –  ложно и т. д.

Более обще можно рассматривать  выражение вида «X есть грек», где  буква X указывает место, на которое  нужно подставить имя некоторого человека, чтобы получить высказывание - истинное или ложное. Но, как нам уже известно, существенным свойством высказывания является его значение истинности и или л. Становясь на эту точку зрения, логика предикатов считает выражение «X есть грек» функцией, аргумент которой X пробегает класс всех людей, а сама функция принимает в качестве значений и или л. Если мы будем, как это принято в математике, «X есть грек» записывать сокращенно, например в виде Гр (X), то для значения X = Сократ получим Гр (Сократ) – и, а скажем Гр (Наполеон) – л и т. д. Относительно других приведенных примеров можно дословно повторить все то, что было сказано относительно первого.

Таким образом, предикатом или, лучше, предикатом-свойством будем  считать функцию, определенную на некотором  универсальном множестве и принимающую  значения и и л. Те элементы, для  которых значение предиката «истинно», обладают данным свойством, остальные  не обладают.

Отсюда сразу видно, что  в действительности всякий предикат-свойство вполне определяется подмножеством  тех объектов, на которых данная функция принимает значение «истинно». Полезно привести примеры предикатов-свойств  из области арифметики. Такими будут, например, свойства натуральных чисел  «быть простым числом», «быть  четным числом», «быть квадратом» и  т. д.

Остановимся на примере «три есть простое число» и на соответствующем  предикате-свойстве «быть простым  числом». Введем для этого свойства сокращенное обозначение Пр (X). Предикат Пр (X) определен на множестве натуральных  чисел. Имеем Пр(1) = л (поскольку 1 не принято рассматривать как простое число). Пр (2) = и, Пр (3) = и, Пр (4) = л, ..., Пр (10) = л, Пр (11) = и и т. д.

Подобно приведенным предикатам-свойствам, математическая логика рассматривает  более общее понятие предиката-отношения. В зависимости от того, между каким  числом объектов устанавливается отношение, мы различаем двухместные (бинарные), трехместные (тернарные) и т. д., в  общем случае – n-местные отношения. Рассмотренные выше предикаты-свойства считаются унарными предикатами. Наконец, оказывается удобным в понятие  предиката-отношения как частный  случай включить и высказывания в  качестве «0 – местных предикатов».

Все математические дисциплины имеют дело с предикатами-отношениями, причем самыми распространенными являются бинарные отношения. Они описываются, различными словами: «равны», «не равны», «больше», «меньше», «делить», «перпендикулярны», «параллельны» и т. д.

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

Рассмотрим пример бинарного  отношения, определенного на множестве  натуральных чисел, а именно отношение, описываемое словом «больше». Если рассматривать это отношение  как функцию от двух переменных X и Y (на множестве натуральных чисел), принимающую значения и или л  в зависимости от того, будет ли соответствующее отношение выполняться  или нет, то эта функция определяет предикат, который обозначим через > (X, Y). Тогда имеем, например, > (3, 2) = и, > (1, 3) = л, > (7, 5) = и и т. д. Более  полно и обозримо двухместный  предикаты >(Х, Y).

	1	2	3	4	5	…
1	л	и	и	и	и	…
2	л	л	и	и	и	…
3	л	л	л	и	и	…
4	л	л	л	л	и	…
5	л	л	л	л	л	…
…	…	…	…	…	…	…

Конечно, совсем нетрудно указать  в элементарной математике примеры  трехместных предикатов и предикатов от еще большего числа аргументов. Так, трехместным предикатом является в геометрии отношение, описываемое  словом «между»: «Точка Y лежит между  точками X и Z». В арифметике хорошо известны понятия наибольшего общего делителя и наименьшего общего кратного двух целых чисел: фраза «Число d является наибольшим общим делителем чисел  а и b» описывает трехместный  предикат. Трехместные предикаты  на множестве действительных чисел  задают действия сложения, вычитания, умножения и деления: X + Y = Z, X –  У = Z, X • Y = Z, X : Y = Z. Примером четырехместного  предиката может служить отношение  между членами пропорции X : Y = Z : W

Ознакомившись с понятием предиката, мы переходим теперь к  рассмотрению операций, позволяющих  из некоторых исходных предикатов строить  новые. Начнем изучение с простейшего  случая одноместных предикатов. Пусть  Р (X) и Q (X) – два одноместных предиката, определенных на некотором множестве  М. С помощью операций алгебры  высказываний мы можем строить новые  предикаты на множестве М. Конъюнкция Р (X)ÙQ (X) – это предикат R1(X) = Р(X)ÙQ(X), который истинен для тех объектов а из М, для которых оба предиката  Р(X) и Q(X) истинны. Аналогично определяется дизъюнкция Р(X)ÚQ(X):R2(X) = Р(X)ÚQ(X) – это  предикат на М, который истинен в  точности для тех а М, для которых истинен по меньшей мере один из предикатов Р (X) и Q (X). Так же определяется отрицание ùР (X): R3(X) = ùР(X) – предикат на М, истинный для тех и только тех а Î М, для которых Р (X) ложен.

2.2. Кванторы

В алгебре предикатов наряду с операциями логики высказываний важнейшую  роль играют операции, называемые кванторами. Именно употребление кванторов делает алгебру предикатов значительно  более богатой, чем алгебру высказываний. Кванторы соответствуют по смыслу тому, что на обычном языке выражается словами «все» («для каждого», «для всех» и т. п.) и «существует» («некоторый», «найдется» и т. п.).

Понятие, обозначаемое словом «все», лежит в основе квантора всеобщности (или квантора общности). Если через  Гр (X) обозначен предикат «X есть грек», определенный на множестве М всех людей, то из этого предиката с  помощью слова «все» мы можем  построить высказывание «Все люди –  греки» (конечно, ложное высказывание). Это пример применения квантора всеобщности.

Вообще же квантор всеобщности  определяется так. Пусть Р (X) – какой-нибудь предикат. Тогда квантор всеобщности  – это операция, которая сопоставляет Р (X) высказывание

«Все X обладают свойством  Р (X)». (*)

Для этой операции («все») употребляется  знак  (перевернутая латинская буква А, напоминающая о немецком слове «alle» или английском «all» – все). Высказывание (*) записывается так: (X)P(X) (читается: «для всех X Р от X»). В соответствии со смыслом слова «все» (X)Р(X) – ложное высказывание, кроме того единственного случая, когда Р (X) тождественно-истинный предикат.