Глава 1. Пропозициональная логика §1. Пропозициональная теория

1. Высказывания, простые и составные

Любое рассуждение состоит из высказываний. Высказывание удобно воспринимать как неопределяемое понятие – как утверждение, про которое можно определённо сказать, что оно является либо безусловно истинным, либо безусловно ложным. При этом возможно, что неизвестно – истинно или ложно в действительности (в данный момент или в принципе навсегда) некоторое конкретное высказывание. Таковы, например, высказывания «Бог существует» и «В десятичной записи числа π содержится бесконечно много девяток». Абстрагируясь от «особенностей текста», высказывание можно воспринимать как логическую константу с известным или неизвестным значением. Напротив, в силу отчётливо выраженного условного характера, высказываниями не являются, например, фразы «бог существует» (написание с маленькой буквы уничтожает недвусмысленную ссылку на христианского творца и требует уточнения – какой именно бог имеется в виду) и «x делится на 5» (истинность этого утверждения зависит от значения, принимаемого переменной x).

Высказывания можно комбинировать, создавая из нескольких высказываний новое при помощи так называемых логических связок. Например, из высказываний «Сборная России по футболу – действующий чемпион мира» и «Ныне здравствующий Папа Римский по национальности – индеец сиу» можно построить ещё несколько высказываний: «Сборная России по футболу – действующий чемпион мира и ныне здравствующий Папа Римский по национальности – индеец сиу», «Если сборная России по футболу – действующий чемпион мира, то ныне здравствующий Папа Римский по национальности – индеец сиу», «Либо сборная России по футболу – действующий чемпион мира, либо ныне здравствующий Папа Римский по национальности – индеец сиу». Заметим, что одно из этих высказываний даже является истинным .

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

2. Алфавит

Во-первых, рассмотрим множество Ω всех высказываний. Переменные, принимающие значения из множества Ω, будем называть пропозициональными переменными и обозначать маленькими латинскими буквами. Множество всех пропозициональных переменных обозначим буквой V. Заметим, что термин «множество всех пропозициональных переменных» (так же, собственно, как и «множество всех высказываний»), строго говоря, математически некорректен, так как V обладает некоторыми свойствами, противоречащими обычному пониманию термина «множество». Например, для любого «настоящего» множества пропозициональных переменных найдётся переменная, в него не входящая, а V таким свойством не обладает, так как в V входят все пропозициональные переменные.

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