Язык логики предикатов

Рассмотрим язык логики предикатов. В его алфавите следующие символы:
1) p, q, r, s, p₁, … - пропозициональные переменные (символы для предложений);
2) a, b, c, d, a₁, … - индивидные константы (символы для единичных имен);
3) x, y, z, x₁, … - индивидные переменные (символы для общих имен);
4) P, Q, R, S, P₁, … - предикаторы (символы для признаков, а также свойств и отношений);
5) (знак отрицания, читается: "не" или "неверно, что"), (знак конъюнкции, т.е. соединения, читается: "и"), (знак нестрогой, или простой, дизъюнкции, т.е. нестрогого, или простого, разделения, читается: "или"), (знак строгой дизъюнкции, читается: "или …, или"), (знак импликации, читается: "если …, то"), (знак эквивалентности, читается: "если и только если …, то"), (квантор всеобщности, читается: "все", "всякий", "любой"), (квантор существования, читается: "существует такой …, что" или "некоторые") - логические символы;
6) (,) (скобки),, (запятая) - служебные символы.Таким образом, в алфавите представлены символы для основных семантических категорий. Строгий смысл знака отрицания и знаков логических связок (конъюнкции, дизъюнкции, импликации и эквивалентности) задают с помощью таблиц истинности. Если А и В - высказывания, 0 - ложь, а 1 - истина, в двузначной логике, т.е. в такой логике, где высказывание может быть либо ложным, либо истинным, а третьего не дано, эти таблицы имеют следующий вид:

A A 0 1 1 0

A В A В A В A В A В 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1

Отметим, что представленные в таблицах логические символы различают по силе связывания, в порядке убывания которой они выстраиваются так: , , , , . Учет силы связывания позволяет сократить количество скобок в логических формулах. Пусть нам нужно исследовать на истинность формулу (p q) r ("если р или q, то r"). Так как дизъюнкция сильнее импликации, мы можем убрать скобки: p q r. Читается полученная формула так же, как исходная. Иногда скобки убирать не следует. Например, в формуле (p q) r ("если р, то q, или r") р и q связаны сильнее, чем q и r, а если убрать скобки, соотношение станет обратным.

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

Определение правильно построенной формулы (ППФ) языка логики предикатов дается в четыре шага:
1) пропозициональная переменная является ППФ;
2) выражение вида A(t₁, t₂, …, t_n), где A - предикатор, а t_k - произвольный индивидный символ из данной в скобках последовательности, является ППФ;
3) если В и С - ППФ, а - индивидная переменная, то выражения вида В, В С, В С, В С, В С, В С, В, В - ППФ;
4) ничто иное не является ППФ.

Видно, что определение дано очень строго, и это не случайно: выше мы отмечали, что строгость - отличительное свойство искусственных языков.

Теперь приведем примеры формул языка логики предикатов. Возьмем пословицу "Язык до Киева доведет". Легче всего написать формулу для этого высказывания, используя пропозициональную переменную. Получится очень просто: р. Но по второму пункту определения ППФ мы можем построить более длинное предложение на языке логики предикатов: xP(x), где х - язык, Р - быть способным довести до Киева. Читается это предложение так: "Для любого х Р от х". Если мы учтем, что признак "быть способным довести до Киева" содержит двухместное отношение, то формула выйдет еще длиннее: xP(x, a), где х - язык, а - Киев, Р - быть способным довести до (чего-либо). Что выражает любая логическая формула? Она выражает логическую форму данного высказывания, т.е. форму абстрактной мысли, которая в нем заключена. Эта форма предстает в искусственных языках логики в удобном для логического анализа виде: кратко и точно.

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

В формуле p q r три разных пропозициональных символа, у каждого из которых может быть одно из двух истинностных значений - либо истина, либо ложь. Рассчитаем, пользуясь правилом комбинаторики, количество сочетаний этих значений для трех символов: 2³=8. Это значит, что в нашей таблице будет восемь строк. При двух пропозициональных символах было бы всего четыре строки (2²=4).

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

р		q		r
0 0 0 0 1 1 1 1		0 0 1 1 0 0 1 1		0 1 0 1 0 1 0 1

Следует обратить внимание на алгоритм перебора сочетаний: под первым символом пишем четыре раза "0" и четыре раза "1", под вторым - попарно "0" и "1", под третьим - попеременно "0" и "1". В результате ни одна из строк не повторяет другие и учтены все комбинации истинностных значений. Осталось провести исследование логических констант, содержащихся в формуле, в соответствии с их смысловыми значениями:

р		q		r
0 0 0 0 1 1 1 1	0 0 1 1 1 1 1 1	0 0 1 1 0 0 1 1	1 1 0 1 0 1 0 1	0 1 0 1 0 1 0 1

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