Язык логики предикатов. Интерпретация и общезначимые формулы

Глава 9. Логика предикатов

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

Шаг к более полному учету внутреннего состава суждения, или высказывания, делает логика предикатов. Она разбивает высказывание на более мелкие единицы, определяет отношения между ними и получает возможность максимально точного выражения мысли.

Логику предикатов можно рассматривать как расширение логики высказываний. Сохраняя все ее средства, она дополняет их новыми возможностями. Важнейшей особенностью логики предикатов по сравнению с традиционной логикой является использование понятия функции, заимствованного из математики[1]. Перейдем к рассмотрению идей логики предикатов[2].

Предикаты

Разберем следующее высказывание:

Вода кипит при 100⁰ С  и нормальном атмосферном давлении.

Выделим в качестве предиката свойство кипеть[3], все остальное - воду, 100⁰ С, нормальное атмосферное давление, т.е. 762 мм ртутного столба, - будем рассматривать как особые предметы, которые взятые вместе характеризуются данным свойством[4]. Высказывание перепишем следующим образом:

Кипеть (вода, 100⁰ С, 762 мм).

Теперь обозначим буквой х химическое вещество вообще, t температуру вообще, р давление вообще. Тогда предикат «кипеть» можно записать в виде следующей формулы:

Кипеть (х, t, р).

Или в обычном языке: «Вещество х кипит при температуре t и давлении р». В зависимости от того, какие конкретные вещество, температуру и давление мы будем подставлять вместо переменных х, t и р, у нас будут получаться истинные или ложные высказывания. Так, подставив в формулу вместо х, t, р снова воду, 100⁰ С, 762 мм ртутного столба, мы получим истинное высказывание. Но пусть вместо воды будет идти речь о ртути. Подставляем ее вместо х, остальные параметры оставим прежними. Получаем формулу:

Кипеть (ртуть, 100⁰ С, 762 мм).

Эта формула соответствует ложному высказыванию «Ртуть кипит при 100⁰ С и нормальном атмосферном давлении». Потому что на самом деле температура кипения ртути при нормальном атмосферном давлении равна не 100⁰ С, а 357⁰ С. Теперь подставим в формулу вместо t температуру 357⁰ С. Получаем:

Кипеть (ртуть, 357⁰ С, 762 мм).

Эта формула соответствует истинному высказыванию «Ртуть кипит при 357⁰ С и нормальном атмосферном давлении».

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

Кипеть (ртуть, 357⁰ С, 100 мм).

Эта формула соответствует ложному высказыванию «Ртуть кипит при 357⁰ С и атмосферном давлении 100 мм ртутного столба», так как при данном атмосферном давлении ртуть имеет иную температуру кипения.

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

Предикат «кипеть» объединяет три предмета: вещество, температуру, давление. Поэтому он называется трехместным предикатом. Существуют одноместные предикаты, например, «Синий (x)». Пусть x означает какой-либо предмет. Подставляя вместо x конкретные предметы: небо, снег, сахар, море…, мы будем получать высказывания: «Небо - синее», «Снег - синий», «Сахар - синий», «Море - синее»…, из этих высказываний первое и четвертое можно считать истинными, второе и третье - ложными.

Приведем пример двухместного предиката: «Любить (x, y)», или «x любит y». В зависимости от того, имена каких конкретных лиц мы подставим вместо переменных x и y, будем получать истинные или ложные высказывания.

Допустим, Николай любит Елену, а Петр и Ольга равнодушны друг к другу. В таком случае высказывание «Любить (Николай, Елена)» будет истинным, высказывание «Любить (Петр, Ольга)» будет ложным. Может оказаться, что высказывание «Любить (Елена, Николай)» будет ложным, если чувство Николая к Елене не является взаимным.

Существуют четырехместные предикаты, например: «Встретить (w, x, y, z)». Пусть w, x означают людей, а y и z − время и место. Формула соответствующего высказывания:

Встретить (Николай, Елена, вечер, фонтан), или «Николай встречает Елену вечером у фонтана».

В общем виде n -местный предикат записывается в виде формулы Р (x ₁, x ₂,... x_n), где Р - предикат, а x ₁, x ₂,... x_n - переменные, способные принимать конкретные значения из соответствующих областей предметов.

Если мы подставим конкретные значения на место не всех переменных в формуле, а лишь некоторых, то тем самым уменьшим число переменных при предикате, или, по-другому, уменьшим его местность. Например, четырехместный предикат «Встретить (w, x, y, z)» можно превратить в одноместный, оставив переменную w и подставив вместо переменных   x, y и z конкретные значения:

Встретить (w, Елена, вечер, фонтан).

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

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

Превратить формулу в истинное или ложное высказывание можно другим способом - поставив перед формулой квантор общности или квантор существования при соответствующей переменной. Квантор общности записывается знаком ", квантор существования - $. Например:

" wВстретить (w, Елена, вечер, фонтан).

$ wВстретить (w, Елена, вечер, фонтан).

В первом случае будет читаться так: «Каждый человек встречает Елену вечером у фонтана», очевидно, это ложное высказывание. Во втором случае получаем: «Существует человек, который встречает Елену вечером у фонтана». Это высказывание является истинным, потому что ранее мы приняли, что истинным является высказывание «Встретить (Николай, Елена, вечер, фонтан)».

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

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

Так, в формуле " wВстретить (w, Елена, вечер, z) переменная w связана квантом общности ", а переменная z является свободной. Поэтому данная формула не является высказыванием.

Попробуем связать кванторами все переменные. Получаем, например, такое высказывание: $ w $ x " y " zВстретить (w, x, y, z). Или: «Существует один человек и существует другой человек, которые встречаются в любое время и в любом месте». Ясно, что такое высказывание является ложным.

Теперь свяжем все переменные кванторами существования: $ w $ x $ y $ zВстретить (w, x, y, z). Получаем высказывание: «Существует один человек и существует другой человек, существуют такое время и такое место, в которых эти два человека встречаются». Очевидно, что данное высказывание является истинным.

Еще один пример: $ w $ xВстретить (w, x, вечер, фонтан). Соответствующее высказывание: «Существует один человек и существует другой человек, которые встречаются вечером у фонтана». Это высказывание будет истинным, потому что очевидно, что в мире кто-то с кем-то встречается вечером у фонтана.

Задание 1. Запишите формулами логики предикатов высказывания «Число 6 − четное», «7 больше 4», «Пальма растет в Африке», «Иван Петрович − сын Петра и Марии».

Задание 2. Перепишите формулы, полученные в задании 1, заменив конкретные предметы соответствующими переменными. Определите местность полученных формул. Преобразуйте их в формулы меньшей местности.

Задание 3. Подставляя в формулы вместо переменных названия конкретных предметов, получите истинные и ложные высказывания.

Задание 4. Свяжите переменные в формулах кванторами общности и существования (дайте отдельные случаи), определите истинностное значение полученных формул.

Имена

Вернемся к высказыванию «Кипеть (вода, 100⁰ С, 762 мм)». Обратим внимание на то, что выражения «вода», «100⁰ С», «762 мм» являются именами соответствующих конкретных предметов − конкретного вещества, конкретных температуры и атмосферного давления. Такие имена называются собственными. А вот выражения «химическое вещество», «температура», «атмосферное давление» − являются общими именами.

Следует отметить, что в зависимости от контекста одно и то же слово или словосочетание может быть собственным именем или общим. Имя «вода» будет собственным, если имеется в виду конкретное химическое вещество наряду с другими химическими веществами − ртуть, сера, азотная кислота и т.д. Но имя «вода» будет общим, если в качестве конкретных предметов имеются в виду вода в реке Кама, вода Тихого океана, вода в виде снега, вода в этом стакане и т.д.

Дадим еще примеры имен собственных: «озеро Байкал», «Черное море», «город Воронеж», «первый в мире космонавт», «самая высокая гора»[5]. Общие имена: «озеро», «море», «город», «космонавт», «высокая гора», «гора».

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

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

Теперь сравним выражения «Черное море» и «город на берегу Черного моря». Первое имя − собственное. Второе − общее имя, так как городов на берегу Черного моря больше одного. Но различие между этими двумя именами состоит еще и в том, что второе имя включает в свой состав первое имя.

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

город на берегу (Черное море).

Пусть теперь буква x означает все конкретные водные объекты − моря, реки, озера, океаны и т.п. Тогда выражение можно переписать следующим образом:

город на берегу (x).

Подставляя вместо x водные объекты, мы будем получать различные сложные имена: «город на берегу Черного моря», «город на берегу Волги», «город на берегу Тихого океана» и т.д.

Перечисленные сложные имена являются общими. Но сложные имена могут быть и собственными. Рассмотрим выражение «столица Австралии». Это сложное имя, так как в свой состав включает имя определенного государства. В то же время − это собственное имя, так как столица Австралии существует в единственном числе, его синонимом будет собственное имя «Канберра».

Запишем выражение «столица Австралии» в виде формулы:

столица (Австралия).

Теперь обозначим буквой y государство вообще. Тогда выражение можно переписать в виде формулы:

столица (y).

Подставляя вместо переменной y имена конкретных государств, можно получать новые собственные сложные имена: «столица Швеции», «столица Китая», «столица США», «столица Египта» и т.д. Их синонимами будут простые имена «Стокгольм», «Пекин», «Вашингтон», «Каир»…

Как и в случае с предикатами, сложные имена могут быть одно-, двух-, трех- и т.д. местными. Так, «город на берегу (x)», «столица (y)» − являются одноместными именами.

Но рассмотрим формулу сложного имени «сын (x, y)», в которой переменные x и y означают соответственно отец вообще и мать вообще. Это − формула сложного двухместного имени. Подставляя вместо x и y имена конкретных родителей, например: Николай и Ольга, Петр и Анастасия, Александр и Александра, мы будем получать сложные имена: «сын (Николай, Ольга)», «сын (Петр, Анастасия)», «сын (Александр, Александра)». В зависимости от того, сколько сыновей у конкретной пары родителей − один или больше одного, полученные сложные имена будут собственными или общими.

Приведем пример трехместного сложного имени: «периметр треугольника (x, y, z)». Здесь переменные x, y, z означают различные стороны треугольника. Подставляя конкретные длины этих сторон, например, 3, 4, 5, или 6, 8, 10, или 9, 12, 15[6], будем получать различные сложные собственные имена: «периметр треугольника (3, 4, 5)», «периметр треугольника (6, 8, 10)», «периметр треугольника (9, 12, 15)». Этим сложным именам будут соответствовать простые имена: 12 (3+4+5), 24 (6+8+10), 36 (9+12+15).

Пример четырехместного сложного общего имени: «подаренные (w, x, y, z)». Здесь переменной w можно обозначить человека, который дарит, x − человека, которому дарят, y − предмет дарения, z − повод дарения. Это общее имя можно превратить в собственные имена: «подаренные(Николай, Ольга, розы, ко дню рождения)», «подаренная(Петр, Анастасия, квартира, ее замужество)» и т.д.

Можно уменьшить местность формулы сложного имени, заменив часть переменных в скобках конкретными именами. Так, двухместную формулу «сын (x, y)» можно превратить в одноместную: «сын (Николай, y). Если же мы заменим все переменные конкретными именами, то получим нуль-местное сложное имя, соответствующее собственному или общему имени.

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

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

Предикат является предметно-истинностной функцией, так как она предметам (или их совокупностям) ставит в соответствие «истину» или «ложь».

Теперь рассмотрим следующее высказывание: «Сын Николая и Ольги учится в педагогическом университете». Запишем его в виде предикатной формулы:

Учиться (сын Николая и Ольги, педагогический университет).

Выражения «сын Николая и Ольги» и «педагогический университет» являются сложными именами, так как включают в свой состав другие имена − «Николай», «Ольга», «университет», поэтому их можно переписать в виде выражений: «сын(Николай, Ольга)», «педагогический(университет)». Учитывая это обстоятельство, предикатную формулу перепишем в следующем виде:

Учиться (сын (Николай, Ольга), педагогический (университет)).

Пусть теперь x и y означают соответственно отец вообще и мать вообще, а z − учебное заведение вообще. Тогда можно перейти к общей предикатной трехместной формуле:

Учиться (сын (x, y), педагогический (z)).

Подставляя в эту формулу вместо переменных x и y имена различных родителей, а вместо переменной z типы учебного заведения, мы будем получать высказывания. Например:

Учиться (сын (Петр, Анастасия), педагогический (училище));

Учиться (сын (Александр, Александра), педагогический (институт));

Учиться (сын (Николай, Ольга), педагогический (колледж));

Учиться (сын (Иван, Марья), педагогический (университет)).

Каждое из этих высказываний будет либо истинным, либо ложным[7]. Рассмотрим еще один пример конкретного высказывания, построенного на основе сложных имен.

Муж дочери Николая и Ольги вчера сдал экзамен по логике доценту Петрову на оценку «отлично».

Здесь можно выделить предикат «сдать экзамен», все остальное является именами различных предметов: «муж дочери Николая и Ольги», «вчера», «логика», «доцент Петров», «оценка «отлично»[8]. Перепишем эти имена в виде выражений: «муж(дочь(Николай, Ольга))», «вчера», «логика», «доцент(Петров)», «оценка «отлично».

Первое и четвертое имена сложные, так как включают в свой состав другие имена. Причем первое имя включает в свой состав имя, которое тоже является сложным, − «дочь(Николай, Ольга)». Второе, третье и пятое имена − простые.

Перепишем высказывание в виде предикатной формулы:

Сдать экзамен (муж (дочь (Николай, Ольга)), вчера, логика, доцент (Петров), оценка «отлично»).

Теперь введем переменные. Пусть u и v означают соответственно мужское и женское имена, w − время, x − учебный предмет, y − фамилию, z − виды оценок. Тогда предикатная формула примет следующий вид:

Сдать экзамен (муж (дочь (u, v)), w, x, доцент (y), z).

Эта формула является шестиместной, так как охватывает шесть переменных: u, v, w, x, y, z. Подставляя вместо переменных конкретные значения, мы получим различные истинные либо ложные высказывания. Примеры:

Сдать экзамен (муж (дочь (Александр, Александра)), вчера, китайский язык, доцент (Иванов), оценка «удовлетворительно»);

Сдать экзамен (муж (дочь (Николай, Ольга)), сегодня, логика, доцент (Горемыкин), оценка «хорошо»);

Сдать экзамен (муж (дочь (Петр, Анастасия)), позавчера, история, доцент (Князева), оценка «хорошо»);

Сдать экзамен (муж (дочь (Кирилл, Дарья)), вчера, логика, доцент (Петров), оценка «неудовлетворительно»).

И т.д.

Мы можем шестиместную формулу «Сдать экзамен (муж (дочь (u, v)), w, x, доцент (y), z)» превратить в трехместную, заменив три переменные в формуле конкретными значениями:

Сдать экзамен (муж (дочь (Петр, Анастасия)), w, x, доцент (y), оценка «хорошо»).

Но если в сложном имени «муж (дочь (Петр, Анастасия)», заменить имя «Анастасия» соответствующей переменной, то вся предикатная формула превратится в четырехместную:

Сдать экзамен (муж (дочь (Петр, v)), w, x, доцент (y), оценка «хорошо»).

Выше мы отмечали, что связывание всех переменных кванторами позволяет превращать предикатную формулу в истинное или ложное высказывание. Дадим соответствующие примеры на основе двухместной формулы«Сдать экзамен (муж (дочь (Петр, Анастасия)), вчера, x, доцент (y), оценка (хорошо))»:

$ y " xСдать экзамен (муж (дочь (Петр, Анастасия), вчера, x, доцент (y), оценка «хорошо»);

$ x $ yСдать экзамен (муж (дочь (Петр, Анастасия)), вчера, x, доцент (y), оценка «хорошо»).

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

Второе высказывание будет звучать так: «Существует учебный предмет и существует доцент, которому муж дочери Петра и Анастасии вчера сдал экзамен на «хорошо» по данному учебному предмету». Ясно, что данное высказывание либо истинно, либо ложно.

Задание 5. Запишите в виде формул сложные имена «аромат дыни», «половина метра», «расстояние между Киевом и Москвой», «выигранная партия в шахматы на мировом чемпионате Алешиным».

Задание 6. Перепишите формулы, полученные при выполнении задания 5, заменив имена конкретных предметов переменными. Определите местность полученных формул. Преобразуйте их в формулы меньшей местности.

Задание 7. Подставляя в формулы, полученные при выполнении задания 5, вместо переменных названия конкретных предметов, получите новые сложные общие или собственные имена.

Язык логики предикатов. Интерпретация и общезначимые формулы

 

Выше мы различали собственные имена конкретных предметов − «озеро Байкал», «Черное море», «100⁰ С», «нормальное атмосферное давление», и общие имена предметов определенного рода − «озеро», «море», «температура», «атмосферное давление».

Обозначим собственные имена латинскими буквами a, b, c. Если этих букв не будет хватать, будем использовать те же буквы, но с индексами: a ₁, b ₁, c ₁, a ₂, b ₂, c ₂ и т.д. Эти буквы будем называть предметными константами.

Общие имена обозначим латинскими буквами x, y, z. Если их не будет хватать, то будем также применять индексы: x ₁, y ₁, z ₁, x ₂, y ₂, z ₂ и т.д. Эти буквы будем называть предметными переменными.

В сложных именах можно различать выражения, которые стоят перед скобкой, например, город на берегу …, столица …, сын …, в именах «город на берегу (Черное море)», «столица (Австралия)», «сын (Александр, Александра)». Для обозначения этих выражений будем использовать латинские буквы f, g, h, f ₁, g ₁, h ₁, f ₂, g ₂, h ₂ и т.д. Назовем эти буквы предметно-функциональными константами.

Таким образом, именам «Черное море», «Александр», «Александра», «Австралия» можно поставить в соответствие предметные константы a, b, c, a ₁. Выражениям город на берегу …, сын …, столица … можно поставить в соответствие предметно-функциональные константы f, g, h. Тогда сложные имена «город на берегу (Черное море)», «сын (Александр, Александра)», «столица (Дания)» запишутся в следующем виде: f (a), g (b, c), h (a₁).

Предметные константы, предметные переменные и сложные имена с предметно-функциональными константами называются термами. Дадим строгое определение терма:

1. Предметная константа есть терм.

2. Предметная переменная есть терм.

3. Если g − предметно-функциональная константа местности n, а r ₁, r ₂, … r_n − термы, то выражение g (r ₁, r ₂, … r_n) есть терм.

4. Ничто иное не есть терм.

Примеры термов, соответствующим пунктам 1 и 2: b, a ₁,   y, x ₁. Примеры термов, соответствующих пункту 3: f (x), g (b, c), h (a ₁, x, y), g (h (a, b)). Последний терм интересен тем, что, сам являясь сложным, включает в свой состав сложный терм h (a, b). Пункт 4 означает, что выражения, не соответствующие первым трем пунктам, например, gr ₁, gh (a, b), g (h (a, f)), не могут считаться термами.

Иногда, к предметно-функциональным константам приписывают в качестве верхнего индекса число, указывающее местность терма, например: f ¹(x), g ²(x, y), h ²(a ₁, x, y).

Терм, в котором все предметные переменные заменены предметными константами, называется замкнутым. Например, термы h (a ₁, x, y) и f (x) не являются замкнутыми, а термы h (a ₁, a, b) и f (a) − замкнуты.

В предикатных формулах можно различать имя предиката, стоящее перед скобкой, например, слово «кипеть» в формуле «Кипеть (х, t, р)». Имя предиката будем обозначать символами F, G, H, F ₁, G ₁, H ₁, F ₂, G ₂, H₂ и т.д. Эти символы будем называть предикатными константами.

Также могут использоваться символы логики высказываний: ù, →, ·, Ú, означающие соответственно операции отрицания, импликации, конъюнкции и дизъюнкции [9], символы ", $ − кванторы общности и существования, скобки (,).

Дадим строгое определение предикатной формулы.

1. Если G − предикатная константа местности N, а r ₁, r ₂, … r_n − термы, то выражение G (r ₁, r ₂, … r_n) есть формула.

2. Если A и B − формулы, то ù A, A → B, A · B, A Ú B − формулы.

3. Если A − формула, а x − предметная переменная, то " xA и $ xA − формулы.

4. Ничто иное не есть формула.

Примеры формул, соответствующие пункту 1: F (a, b), H (x, a, b), F ₁(f (x)), H ₁(h (a, f (b))). Здесь третья и четвертая формулы со сложными термами.

Примеры формулы, соответствующие пункту 2: F (x)· G (x)→(H (x)Ú F₁ (x)), H (x, a, b)Ú F ₁(F (x)).

Пример формулы, построенной в соответствии с пунктом 3: " xF (g (x, a))→ù H (y, b)).

Согласно пункту 4 выражения, не соответствующие первым трем пунктам, не являются формулами. Например, выражение $ a → H (a, b) не является формулой.

Укажем необходимое условие расстановки скобок в правильных формулах: число открывающих скобок должно быть равно числу закрывающих скобок.

Иногда к предикатным константам приписывают в качестве верхнего индекса число, указывающее на местность формулы, например: F ²(x, y).

Интерпретация символов языка логики предикатов. Ранее фактически уже шла речь об интерпретации, когда мы вводили конкретные значения предметных переменных x, y, z, предметных констант a, b, c, и т.д. Теперь рассмотрим это в систематическом виде.

Интерпретация символов языка логики предикатов означает следующее:

− предполагается наличие непустой совокупности (множества) предметов определенного рода, которая называется областью интерпретации, или универсумом рассуждения;

− каждой предметной константе a, b, c, a ₁... приписывают определенный предмет из этого универсума;

− каждой предметно-функциональной константе f, g, h, f ₁... приписывают определенную функцию, ставящую в соответствие одним предметам универсума другие его предметы;

− каждой предикатной константе F, G, H, F ₁,... приписывают определенное свойство предмета при одноместной формуле или определенное свойство (отношение), объединяющее двойки, тройки и т.д. предметов при многоместной формуле;

− каждой предметной переменной x, y, z, x ₁… приписывается произвольный предмет универсума. Считается, что переменные «пробегают» по всем предметам универсума.

Рассмотрим на примерах, как это работает. Возьмем в качестве универсума совокупность целых чисел от 1 до 5. Предметным константам a, b, c, a ₁, b ₁ припишем соответственно числа 1, 2, 3, 4, 5. Предметные переменные x, y, z пусть пробегают по этим числам.

Предметно-функциональным константам f и g припишем операции «максимум», и «минимум». Тогда, например, терм f (a, b) будет соответствовать выражению «максимум(1, 2)», которому соответствует число 2, а терм g (a ₁, c) − выражению «минимум(4, 3)», которому соответствует число 3.

Предикатной константе F припишем свойство «быть четным», а предикатной константе G − «быть простым[10]».

Тогда формула F (a ₁) соответствует истинному высказыванию «число 4 − четное», формула F (a) − ложному высказыванию «число 1 − четное», формула G (b) − истинному высказыванию «число 2 − простое». Формула $ x (G (f (x, b))) соответствует истинному высказыванию «Существует такое число, что максимум из этого числа и 2 является простым числом». Формула " y (F (g (y, a ₁))) соответствует ложному высказыванию «Для всякого числа минимум из этого числа и 4 является четным числом». Формула " x (ù F (x)®ù F (f (x, a))) соответствует истинному высказыванию «Для каждого числа верно, если оно нечетное, то максимум из этого числа и 1 является тоже нечетным числом».

Теперь пусть будет тот же универсум, состоящий из чисел от 1 до 5. Предметным константам a, b, c, a ₁, b ₁ поставим в соответствие те же числа 1, 2, 3, 4, 5. Предметные переменные x, y, z пробегают по всем этим числам. Оставим те же интерпретации предметно-функциональных констант f и g.

Изменим лишь интерпретацию предикатных символов. Символу F припишем свойство «быть меньше 5», а символу G припишем свойство «быть равным 3».

Тогда формула F (a ₁) будет соответствовать истинному высказыванию «4 меньше 5», формула F (a) − истинному высказыванию «1 меньше 5», формула G (b) − ложному высказыванию «2 равно 3». Формула $ x (G (f (x, b))) соответствует истинному высказыванию «Существует такое число, что максимум из этого числа и 2 равен 3». Формула " y (F (g (y, a ₁)) соответствует истинному высказыванию «Для всякого числа минимум из этого числа и 4 меньше 5». Формула " x (F (x)®ù F (f (x, a))) соответствует ложному высказыванию «Для каждого числа верно, что если оно меньше 5, то неверно, что максимум из этого числа и 1 меньше 5».

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

Существуют формулы логики предикатов, которые в силу особенностей своей структуры являются истинными при любой интерпретации их символов. Такие формулы называются общезначимыми. Их можно считать аналогами тавтологий логики высказываний.

Рассмотрим формулу вида " xA ® $ xA, в которой символ A означает формулу логики предикатов. Пусть A будет формула G (f (x, b)). Подставим ее в формулу " xA ®$ xA вместо A. Получаем:

" xG (f (x, b)) ® $ xG (f (x, b)).

Этой формуле при первой интерпретации соответствует высказывание «Если для каждого числа верно, что максимум из этого числа и 2 является простым числом, то существует число, максимум из которого и 2 простое число». Очевидно, что первый член импликативного высказывания − ложен, второй член − истинен. Следовательно, все высказывание является истинным[11].

При второй интерпретации этой формуле соответствует высказывание «Если для каждого числа верно, что максимум из этого числа и 2 равен 3, то существует число, максимум из которого и 2 равен 3». Здесь также первый член импликативного высказывания − ложен, второй член − истинен. Следовательно, все высказывание является истинным.

Итак, независимо от того, какую из двух данных интерпретаций мы выберем, формула " xG (f (x, b)) ® $ xG (f (x, b)) является истинной. Можно показать, что любая формула вида " xA ® $ xA является истинной и, следовательно, общезначимой. В параграфе «Правила редукции и аналитические таблицы» мы докажем общезначимость этой формулы при подстановке вместо A формулы F (x)→ G (x), т.е. общезначимость формулы " x (F (x)→ G (x)) → $ x (F (x)→ G (x)).

Дадим список некоторых общезначимых формул. Напомним, что A − формула логики предикатов.

 

1. " xA ® A (r) − удаление квантора общности. Здесь и ниже A (r) − результат замены в формуле A всех свободных вхождений переменной x замкнутым термом r.

2. A (r) ® $ xA − введение квантора существования.

3. " xA ® $ xA − правило подчинения

4. $ xA Ú $ x ù A − правило непустоты универсума, означающее, что каждому имени соответствует определенный предмет.

5. " x " yA º " y " xA [12] − перестановка кванторов

6. $ x $ yA º $ y $ xA − перестановка кванторов

7. $ x " yA ® " y $ xA − перестановка кванторов

8. ù" xA º $ x ù A − правило отрицания квантора

9. ù$ xA º " x ù A − правило отрицания квантора

10. " xA ºù$ x ù A − взаимовыразимость кванторов

11. $ xA º ù" x ù A − взаимовыразимость кванторов

 

Задание 8. Составьте высказывания, соответствующие формулам F (c, a), $ xF (x, a), " xG (x), G (a ₁), " x (G (x)Ú F (x, b ₁)) при интерпретации A, затем при интерпретации B.

Интерпретация A: универсум − дни недели; предметные константы: a − понедельник, b − вторник, c − среда, a ₁ − четверг, b ₁ − пятница, c ₁ − суббота, a ₂ − воскресенье; предикатные константы: F − отношение «непосредственно следовать за», G − свойство «быть выходным днем».

Интерпретация B: универсум − семь российских городов: Москва, Петербург, Тверь, Саратов, Астрахань, Новгород, Иркутск; эти города обозначаются соответственно предметными константами a, b, c, a ₁, b ₁, c ₁,   a ₂; предикатные константы: F − отношение «расположен севернее», G − свойство «быть столицей России».

Определите истинностные значения формул и укажите, какие из этих формул сохраняют свое истинностное значение при смене интерпретации, а какие не сохраняют.