Область действия логического союза и квантора

Область действия логического союза образуют все подформулы, которые он связывает.

Область действия квантора составляет подформула, которая начинается сразу после квантора.

В формуле (х)((Еу)Рху Z) [Еу){~лРху v Qxy)), которая рассматривалась выше, областью действия первого квантора существования (Еу) является подформула (Еу)Рху; областью действия второго квантора существования (Еу) — подформула (Еу)(~лРху v Qxy); областью действия квантора общности (*) — вся формула в целом. *

Связанные и свободные переменные

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

Вхождение предметной переменной ? называется связанным, если и только если она является переменной квантора общности (?) или квантора существования (Eg), или находится в области действия по крайней мере одного из них. Всякое иное вхождение переменной ? называется свободным.

Формализация в логике предикатов

Для формализации высказываний в JIB необходимо иметь знаки для обозначения атомарных формул и такое множество логических союзов, которое позволяет выражать все виды совместимости и несовместимости между высказываниями. Формализация высказываний в JOT носит более сложный характер. Для ее осуществления необходимо иметь:

(а) знаки для обозначения свойств вещей или их отношений друг к другу;

(б) предметные константы для обозначения имен собственных вещей;

(в) предметные переменные для обозначения области действия квантора общности или существования;

(г) функциональные знаки для обозначения операций над константами.

Примем соглашение не ставить внешних скобок в формулах ЛП, начинающихся с кванторов.

Пример

Пусть U ~ «люди»; х, у — предметные переменные; a, b — предметные константы; Рху = «х — учитель^». 1.

«Если а — учитель Ь, то а чей-то учитель»:

(Pab з (Еу)Рау). 2.

«6 — ученик а или b — свой собственный ученик»:

(PabvPbb). 3.

«Если все свои собственные учителя, то а — свой собственный учитель и b — свой собственный учитель»:

(х)Рхх з (Раа & Pbb). 4.

«Каждый — учитель кого-нибудь тогда и только тогда, когда кто-нибудь — ученик каждого»:

(х)(Еу)Рху^(Еу)(х)Рху.

5. «Неверно, что если а — не учитель b,wb — не чей-то ученик»: (-^(—JPab г) -n(Ex)Pxb)).

Семантика логики предикатов

Семантика ЛП, как и ее синтаксис, обобщает семантику ЛВ. Как и в логике высказываний, главная семантическая проблема логики предикатов — интерпретация формул как осмысленных выражений.

Семантика ЛП — соглашения и правила, позволяющие интерпретировать формулы логики предикатов как осмысленные, т. е. истинные или ложные высказывания.

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

Интерпретацией формулы ЛП называется (1)

определение значений всех ее нелогических терминов; (2)

вычисление значения ее истинности в данном универсуме.

Понятие интерпретации формул ЛП основано на понятии расширения нелогических терминов произвольной формулы ЛП.

Расширением (значением)

• предметной константы в универсуме U называется та вещь, чьим именем собственным она является; •

(свободной и связанной) предметной переменной в универсуме U называется произвольная вещь U; •

предиката Р", п ? 0, в универсуме U называется множество элементов U, выполняющих данный предикат; •

функционального символа f,n> 0, в универсуме U называется множество элементов U, удовлетворяющих аргументам и значению обозначаемой им операции.

Расширение предметной константы и предметной переменной не вызывает особых вопросов. Если в словарь формулы ЛП входят константа а и переменная х, то расширением а в универсуме (J ~ «герои пушкинских произведений» должно быть некоторое имя собственное, например, «Татьяна Ларина», расширением х — любой элемент универсума, который может быть подставлен на место х, включая и указанное имя собственное.

Расширение предиката соотносимо с определением его объема в традиционной логике. Выяснить расширение предиката ЛП означает вычислить его объем в заданном универсуме интерпретации. Если объем предиката не пуст, он получает значение «истина», в противном случае — значение «ложь».

Результат расширения произвольного предиката Р", п > 0, зависит от того, обозначает ли он простое высказывание ЛВ (n ~ 0), свойство (и = 1) или отношение (п > 1).

Если п = 0, предикат Р" обозначает простое высказывание Л В, которое либо истинно, либо ложно. В этом случае расширение предиката Р" сводится к доказательству Р" ~ T или Pn = F.

Если п- 1, предикат Р" обозначает свойство. В этом случае расширением предиката Р" является (возможно, пустое) множество всех вещей универсума, выполняющих его. Расширением предиката Рх = (ос — круглый» в произвольном универсуме, будет множество всех круглых вещей. Если оно не пусто, предикат Рх получает значение «истина», Рх = Т; если же в заданном универсуме нет ни одной круглой вещи, то предикат Рх получает значение «ложь», Рх = F. В рассматриваемом случае процедура расширения предиката, обозначающего свойство, сводится к отображению элементов U, образующих его расширение, во множество {Т, F}.

Если п — 2, предикат Р" обозначает бинарное отношение.

Если п > 2, предикат Р" обозначает «-местное отношение с числом термов, большим двух. В этом случае расширение предиката Р" образует (возможно, пустое) множество всех упорядоченных й-ок элементов универсума, выполняющих обозначаемое им отношение. И в этом случае процедура расширения предиката сводится к отображению последовательностей упорядоченных элементов из множества, образованного п-й степенью U: Ur\Ur\ ...nU-lT,n> 2, и образующих его расширение, во множество {Т, F}. Например, в универсуме ?/ = {1, 2, 3, 4, 5} расширением предиката Pxyz = «у больше х и меньше z на единицу» будет множество упорядоченных троек чисел {<1,2, 3>, <2, 3, 4>, <3,4, 5>}, которое является подмножеством множества всех троек: U о U о U = if.

В общем случае, построить расширение предиката Р", п > 0, означает установить его соответствие с отображением произведения if во множество {Т, F}.

Результат расширения произвольной функции/, п > 0, зависит от того, обозначает ли она предметную константу (п = 0) или я-месгную операцию (п> 1) в заданном универсуме интерпретации.

Если п = 0, функция / обозначает предметную константу. Это возвращает нас к проблеме расширения данной константы.

Если п = 1, функция/ обозначает одноместную операцию. В универсуме U= «натуральные числа» функции/ может соответствовать, например, операция возведения в квадрат:/ =х2. Расширением такой функции будет следующая бесконечная последовательность результатов возведения в квадрат: /(1) = 1,/(2) = 4,/(3) = 9, .... Для вы- числения расширения одноместной функции необходимо построить отображение (обозначается далее символом «-»>) множества элементов универсума в это же множество элементов, U->U.

Если п = 2, функция/ обозначает двухместную операцию. В универсуме U = «натуральные числа» функции / может соответствовать, например, операция сложения: / = (дг + у). Расширением этой функции будет следующая бесконечная последовательность результатов сложения всех пар чисел: /(1 + 1) = 2, /(1+2) = 3, /(2 + 1) = 3, ... . Для вычисления расширения двухместной функции необходимо построить отображение множества элементов универсума в это же множество элементов, U2 —> U.

В общем случае построить расширение функции f, п > 0, означает установить ее соответствие с отображением произведения if во множество элементов U.

Истинность квалифицированных высказываний также основана на понятии расширения.

Произвольная формула ЛП, главным знаком которой является квантор всеобщности, истинна в заданном универсуме, если формула ф% истинна в каждом своем расширении; аналогично формула главным знаком шторой является квантор всеобщности, истинна в заданном универсуме, если формула ф? истинна хотя бы в одном своем расширении.

Объединяет сказанное следующее определение.

Формула ЛП получает интерпретацию, если (1)

задан универсум интерпретации (У; (2)

определено расширение каждого ее нелогического символа в U, (3)

формуле )ф? главным знаком которой является квантор всеобщности, приписано значение «истина», если формула ф% истинна при подстановке на место переменной ? любой вещи из универсума U; и приписано значение «ложь» в противном случае; (4)

формуле главным знаком которой является квантор существования, приписано значение «истина», если формула истинна при подстановке на место переменной ? по крайней мере одной вещи из универсума U; и приписано значение «ложь» в противном случае;

(5) формуле, главным знаком которой является логический союз, приписано значение истинности согласно правилу для этого логического союза.

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

Формула ЛП •

выполнима, если и только если она истинна хотя бы в одной интерпретации; •

логически истинна, если и только если она истинна во всех интерпретациях; •

логически ложна, т. в. невыполнима, если и только если ежа ложна во всех интерпретациях.

Пример

Вычислить значение истинности следующих формул в U~ {а, Ь}, где a = «Сократ», b = «Платон», Рху - «х старше у».

(х)(у)Рху = (y)Pay & (у)РЬу

(расширение формулы (х)[(у)Р.гу]) =

= {{Раа & Pab) & (РЬа & РЬЪ))

(расширение формулы (х)(у)Рху) - = ((F & Г) & (F & F))

(значения истинности элементов расширения) = = (F&F) =

= F (значение истинности формулы (х)(у)Рху).

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

В итоге только формула (Ех)(Еу)Рху истинна в указанном универсуме при заданном значении констант и предикатного символа.

Значит, она истинна в данной интерпретации и тем самым выполнима, а все остальные формулы в этой интерпретации ложны.