Лекция № 12. Язык логики предикатов.

1. Предикаты.

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

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

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

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

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

Пример 1.

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

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

в) В описаниях вычислительных процедур и, в частности, в языках программирования, часто встречаются указания типа “повторять цикл до тех пор, пока переменные и не станут равными или прекратить вычисление цикла после ста повторений”. Если обозначить через счётчик повторений, то описанное здесь условие примет вид , а само указание в целом описывается выражением: “повторять, если ”.

1. Кванторы.

Пусть предикат, определённый на множестве . Высказывание “для всех истинно” обозначается или . Здесь множество входит в обозначение, но когда оно ясно из контекста пишут просто . Знак называется квантором общности.

Высказывание “существует такое значение , что истинно” обозначается или . Знак называется квантором существования. Переход от предиката к выражениям вида или называется связыванием переменной , а также навешиванием квантора на переменную (или на предикат ). Переменная, на которую навешен квантор, называется связанной, несвязанная переменная называется свободной.

Смысл связанных и свободных переменных в предикатах принципиально различен. Свободная переменная – это обычная переменная, которая может принимать различные значения из множества ; выражение - переменное высказывание, зависящее от значения . Выражение не зависит от переменной и имеет вполне определённое значение. Это, в частности, означает, что переименование связанной переменной, то есть переход от выражения к выражению и наоборот не меняет истинности выражения. Переменные, являющиеся, по существу, связанными, встречаются не только в логике. Например, в выражениях или переменная связана: при фиксированной функции первое выражение равно определенному числу, а второе становится функцией от пределов интегрирования.

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

Пример 2.

а) Пусть предикат “ чётное число”. Тогда высказывание истинно на любом множестве чётных чисел и ложно, если множество содержит хотя бы одно нечётное число. Высказывание истинно на любом множестве, содержащем хотя бы одно чётное число и ложно на любом множестве нечётных чисел.

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

1. Истинные формулы и эквивалентные соотношения.

При логической (истинностной) интерпретации формул логики возможны три основные ситуации.

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

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

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

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

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

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

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

Аналогично доказывается истинность соотношения

Большое значение имеют следующие свойства, которые могут быть доказаны способом, рассмотренным в примере 3.

1) Дистрибутивность квантора относительно конъюнкции:

.

2) Дистрибутивность квантора относительно дизъюнкции:

.

Если же кванторы и поменять местами, то получатся соотношения, верные только в одну сторону:

3) ,

4) .

В таких случаях говорят, что левая часть является более сильным утверждением, чем правая, поскольку она требует для своего выполнения более жёстких условий. Так, например, в соотношении 3 в левой части требуется, чтобы оба предиката были истинны для одного и того же значения , тогда как в правой части они могут быть истинны при различных значениях переменной. Пример случая, когда соотношения 3 и 4 в обратную сторону неверны: “ чётное число”, “ нечётное число”.

Пусть некоторое переменное выражение, не содержащее переменной . Тогда выполняются соотношения:

5) .

6) .

7) .

8) .

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

1. Доказательства в логике предикатов.

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

, .

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

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