Формулы логики высказываний, интерпретация

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

Определение. Атомарными формулами логики высказываний называются выбранные буквы латинского алфавита с индексами и без них. В качестве выбранных букв мы будем использовать U, V, W, X, Y, Z.

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

1) атомарные формулы;

2) символы истины 1 и лжи 0;

3) выражения вида (F)& (G), (F) v (G), (F), (F)→(G), (F)↔(G), где F и G – формулы логики высказываний.

На первый взгляд может показаться, что определение содержит “порочный круг”; понятие формулы логики высказываний определяется само через себя. На самом деле, это определение относится к так называемым индуктивным определениям. Такие определения вводят сначала базовые объекты (в нашем случае – атомарные формулы и символы 0 и 1) и способы порождения новых объектов из уже полученных (в нашем случае – операции, введенные в начале лекции).

Приведем пример. Буквы X, Y, Z – атомарные формулы. В силу первого пункта определения эти буквы являются формулами логики высказываний, а в силу второго формулами являются выражения (X)&(Y), ((X)&(Y)) → (Z). Мы видим, что если строго следовать определению, в формуле надо писать много скобок. Это неудобно для восприятия формулы. Чтобы уменьшить количество скобок условимся, во-первых, атомарные формулы в скобки не заключать, во-вторых, ввести приоритет (силу связывания) для связок. Будем считать, что имеет наивысший приоритет, & и v имеют одинаковый приоритет, который выше, чем y → и ↔. Последние две связки имеют одинаковый приоритет.

Используя эти соглашения, формулу ((X)&(Y)) → (Z) можно записать так: X & Y → Z. Отметим, что поскольку мы не упорядочили & и v по силе связывания, то выражение X & Y v Z не является формулой. Надо в этом выражении поставить скобки, определяющие порядок выполнения операций. Получатся две формулы (X & Y)v Z и X &(Y v Z). Аналогичная ситуация возникает и при записи алгебраических выражений. Операция умножения имеет здесь более высокий приоритет, нежели операция сложения, поэтому в выражении a +(b * c) скобки можно не ставить. Есть, однако, и различие. Операции сложения и вычитания при записи алгебраических выражений имеют одинаковый приоритет. Тем не менее, в выражении a + b – c скобки можно не ставить, так как предполагается, что операции в этом случае выполняются слева направо. В логике высказываний мы последнего предположения не делаем, поэтому, как отмечалось, в выражении X & Y v Z надо ставить скобки. В дальнейшем нам понадобится понятие подформулы. Попросту говоря, подформула формулы F – это “слитная” часть, которая сама является формулой. На строгом уровне это понятие вводится следующим образом.

Определение. Подформулой атомарной формулы является она сама. Подформулами формулы F являются формула F и все ее подформулы. Подформулами формул F & G, F v G, F → G, F ↔ G являются они сами и все подформулы формул F и G.

Например, формула F = X & Y → X v Z имеет шесть подформул: X, Y, Z, X & Y, X v Z, X & Y → X v Z. Теперь необходимо соотнести понятие высказывания и формулы. На самом простом уровне формула – это форма для получения высказываний. Пусть, например, дана формула F = X & Y → Z. Поставим вместо X, Y и Z соответственно высказывания A 1 = “четырехугольник ABCD является параллелограммом”, A 2 = “в четырехугольнике ABCD смежные стороны равны”, A 3=“в четырехугольнике ABCD диагонали перпендикулярны”, то получим высказывание A 4 = “если четырехугольник ABCD является параллелограммом и его смежные стороны равны, то диагонали перпендикулярны ”. Это высказывание получилось “по форме” F. Если вместо X, Y и Z подставить другие высказывания, то получим новое высказывание, имеющее ту же “форму”. На строгом уровне сказанное в предыдущем абзаце оформляется в виде понятия интерпретации. Обозначим через А множество атомарных, а через F – множество всех формул логики высказываний. Зафиксируем некоторую совокупность высказываний P, удовлетворяющую следующим условиям:

1) какие бы два высказывания из P мы ни взяли, P содержит их конъюнкцию, дизъюнкцию, импликацию и эквиваленцию,

2) P содержит отрицание каждого из высказываний, принадлежащих P.

Интерпретацией в широком смысле мы будем называть произвольную функцию φ: A → P. Такая функция, определенная на множестве атомарных формул, естественным образом распространяется на множество всех формул. Выше был приведен пример интерпретации в широком смысле. В этом примере совокупность P содержала высказывания А 1 – А 4, а интерпретация φ на атомарных формулах X, Y, Z действовала так: φ(X)= A 1, φ(Y)= A 2, φ(Z)= A3. Естественное расширение φ на множество всех формул будем обозначать той же буквой. Тогда φ(F) = A4. В дальнейшем от высказываний φ(F) нам на самом деле будут нужны только их истинностные значения 1 и 0. Введем поэтому более узкое понятие интерпретации.

Определение. Интерпретацией в узком смысле (или просто интерпретацией) называется функция

φ: A → { 0, 1 }.

Используя таблицы истинности связок, интерпретацию можно расширить на множество всех формул. Приведем пример. Пусть φ (X) = 1, φ (Y) = 0, φ(Z)= 1, F = X v Y → Z, G = X & Y ↔ X & Z. Тогда φ (F) = 1, φ (G) = 0.

В заключение лекции рассмотрим задачу, решение которой состоит в использовании выразительных возможностей логики высказываний. Рассмотрим следующее рассуждение (которое для последующих ссылок будем называть рассуждением молодого человека). “Если я поеду автобусом, а автобус опоздает, то я пропущу назначенное свидание. Если я пропущу назначенное свидание и начну огорчаться, то мне не следует ехать домой. Если я не получу работу, то я начну огорчаться и мне следует поехать домой. Следовательно, если я поеду автобусом, а автобус опоздает, то я получу эту работу”. Задача состоит в том, чтобы перевести это рассуждение на язык логики высказываний, т.е. представить его в виде последовательности четырех формул (поскольку рассуждение содержит четыре предложения). Обозначим высказывание “я поеду автобусом” буквой X, “автобус опоздает” – буквой Y, “я пропущу свидание” – Z, “я начну огорчаться” – U, “мне следует ехать домой” – V, “я получу работу” – W. Тогда приведенные в рассуждении предложения можно записать в виде следующих формул:

X & Y → Z, Z & U → V, W → U & V, X & Y → W. Мы перевели рассуждение молодого человека на язык логики высказываний.