§ 1.4. Об исчислении предикатов (двузначных)

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

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

где — предметные переменные и их алфавиты.

В связи с тем, что двузначные предикаты принимают значения из двухэлементного множества 0 и 1, они могут выступать в качестве аргументов в двузначных однородных логических функциях; по отношению к ним имеет смысл применение символики исчисления высказываний.

Пусть мы имеем предикаты

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

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

Из предикатов (1.38) и двузначных логических переменных

можно построить сложную функцию, например,

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

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

Применяются кванторы двух видов: квантор общности и квантор существования.

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

в которой является символом квантора общности. Запись эта читается так: «при любом имеет место .

Квантор существования — это оператор, приводящий в соответствие любому одноместному предикату такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда при всех значениях . Символически это записывается формулой

в которой является символом квантора существования. Запись эта читается так: «существует такое , что имеет место .

Рассмотрим некоторые общие свойства введенных операторов.

В соответствии с определениями кванторов логическая переменная z в выражениях

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

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

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

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

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

Эти тождества являются следствием определений кванторов общности и существования.

Система тождеств исчисления высказываний, дополненная тождествами (1.42), дает возможность осуществлять различные преобразования для решения тех или иных конкретных задач. Так же как и в исчислении высказываний, в исчислении предикатов на первом по важности месте стоит проблема разрешимости, но из-за изменения состава независимых переменных постановка задачи в этой проблеме несколько видоизменяется.

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

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

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