В Степин - Новая философская энциклопедия. Том второй Е—M

ЛОГИКАВЫСКАЗЫВАНИЙ, пропозициональная логика — раздел логики символической, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. При этом в отличие от логики предикатов внутренняя структура простых высказываний не рассматривается, а учитывается лишь, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные. Под высказыванием понимается то, что выражается повествовательным предложением. Поэтому логику высказываний некоторые авторы называют также «логикой предложений». В естественном языке существует много способов образования сложных высказываний из простых. Обычно выбирают пять общеизвестных грамматических связок (союзов): «не», «и», «или», «если..., то» и «если..., и только если». Процесс символизации языка логики высказываний состоит в следующем. Элементарные высказывания заменяются пропозициональными переменными р, q, г, ... с индексами или без них; указанным выше грамматическим связкам ставятся в соответствие (с близким смыслом) логические связки, которые получают соответственно следующие обозначения и названия: -i (отрицание), л или & (конъюнкция), v (дизъюнкция), Z) (импликация) и = (эквиваленты); и, наконец, используются скобки (,) для того, чтобы можно было по-разному группировать высказываниям и этим определять порядок выполнения операций. Отрицание называется одноместной связкой, а остальные четыре — двухместными связками. Выражением языка логики высказываний называют любую последовательность указанных выше символов. Некоторые из этих выражений объявляются правильно построенными. Их называют формулами. Формулы определяются следующими правилами, где буквы А, В... представляют произвольные высказывания: (1) всякая пропозициональная переменная есть формула; (2) если А и В — формулы, то (-А), (А л В), (A v В), (А эВ), (А=В) тоже формулы; (3) никакие другие соединения символов не являются формулами. Примерами формул являются р, ->q, -.(pvq). Внешние скобки при записи формул обычно опускают, а связки (по определению) различают по «силе связывания». Напр., знак

415

ЛОГИКА ВЫСКАЗЫВАНИЯ отрицания -I связывает сильнее, чем двухместные связки. Т. о., правила задают эффективный способ распознавания, является ли выражение логики высказываний формулой. Затем делают два основных допущения, на которых основывается семантика логики высказываний: (I) Каждое простое высказывание является или только истинным, или только ложным (принцип двузначности). «Истина» и «ложь» называются истинностными значениями высказывания и обозначаются соответственно И и Л, или 1 и 0. (II) Истинностное значение сложного высказывания определяется только истинностными значениями составляющих его простых высказываний. Это означает, что логические связки (их называют также пропозициональные связки) являются истинностными функциями. Удобным способом задания истинностных функций является табличный, где слева указываются все возможные приписывания значений аргументам (пропозициональным переменным), а справа — значения самой функции: р и и л л q и л и л PAq И л л л pvq И И и л p=>q и л и и p = q И Л Л И Р И Л -Р Л И Приведенные выше таблицы называются истинностными таблицами, а определяемые ими пропозициональные связки — классическими связками. Легко определить, сколько имеется различных классических связок. Число различных строк в таблице длины m равно 2т и на каждой из них значение функции можно задать двумя способами: И или Л. Поэтому число функций двузначной логики, зависящих от m аргументов, составляет 2 в степени 2т. Отсюда, напр., число одноместных связок равно 4, а число двухместных связок равно 16. Каждая формула задает некоторую истинностную функцию, которая графически может быть представлена истинностной таблицей, содержащей 2т строк, если в формуле имеется m различных пропозициональных переменных. При этом формула может быть такой, что на каждой строке она принимает только одно значение, равное И, или только одно значение, равное Л. В первом случае она называется тавтологией (тождественно истинным высказыванием), а во втором — противоречием (тождественно ложным высказыванием). В формальной логике тавтологии играют важную роль. Они служат для записи ее законов (Закон логический), так как тавтологии являются всегда истинными высказываниями только в силу своей символической формы, независимо от содержания входящих в них исходных высказываний. Легко установить, что формулы вида Ad A, A v-A,-. (Ал-А) являются тавтологиями. Законы, выражаемые этими формулами, называются соответственно законом тождества, законом исключенного третьего и законом непротиворечия. Исключительно важное свойство истинностных таблиц состоит в следующем: они дают эффективную процедуру для решения вопроса о том, является ли данная пропозициональная формула тавтологией. Указанная процедура называется разрешающей процедурой и отсюда следует, что развиваемая здесь логика высказывании является разрешимой логикой (см. Разрешения проблема). Вот некоторые общие факты о тавтологиях, настолько общие, что они называются правилами логики высказываний: 1. Правило заключения (modus ponens). Если А и Ar) В тавтологии, то В тавтология. 2. Правило подстановки. Если А(р) есть тавтология и В — формула, то А(В) тоже тавтология, где В замешает каждое вхождение переменной р в формуле А, т. е. подстановка в тавтологию приводит к тавтологии. Уже отсюда следует, что имеется бесконечное множество тавтологий. 3. Правило замены. Формулы А и В называют эквивалентными, если формула А = В есть тавтология. Очевидно, что если формулы А и В эквивалентны, то они равны как истинностные функции, т. е. принимают одинаковые истинностные значения. Тогда, если А = В есть тавтология, то С(А) = С(В) тоже тавтология, где С(А) — формула, содержащая некоторую формулу А в качестве своей составной части, и С(В) — формула, полученная из С(А) заменой этой составляющей А на формулу В. Из последнего правила следует, что можно преобразовывать формулы, получая другие, им эквивалентные, на более простые (содержащие меньше пропозициональных связок и переменных). Можно теперь любую формулу привести к какому-либо каноническому виду и этим решать определенного рода задачи. Более того, некоторые эквиваленции выражают основные свойства пропозициональных связок. Напр., эквиваленции (А л В) = (В л А) и (A v В) = (A v В) выражают коммутативный закон конъюнкции и соответственно дизъюнкции. Все эти вопросы (и другие) изучает алгебра логики, основы которой заложены в работах Дж. Буля ( 1847,1854) и А. де Моргана (1847). Отметим некоторые эквиваленции, указывающие на взаимовыразимость одних связок через другие: А л В=-i(-A v -iB), A v В= -ibA л-,В), AdB = -AvB, (А^В)ЦАзВ)л(ВзА). Система пропозициональных связок M называется полной, если всякая формула эквивалентна некоторой формуле, в которую входят только связки из системы М, т. е. посредством такой системы можно выразить все истинностные функции. Так, системы связок {-i, л, v}, {-¦, л}, {->,v} и {-i, 3 } являются полными. Это значит, что мы можем строить логику высказываний на основе любой из указанных систем связок. Оказывается, полной может быть система, состоящая только из одной связки |, которая называется «штрих Шеффера»: высказывание р | q истинно тогда и только тогда, когда неверно, что р и q оба истинны. Достаточность связки | следует из тавтологий -А = А|А, AvB = (A|A)|(B|B). Наряду с понятием тавтологии фундаментальным для логики высказываний является понятие логического следования (см. Следование логическое), поскольку одной из главных задач логики является устанавливать, что из чего следует, и тем самым указывать, какие высказывания являются теоремами при заданных условиях. Всякую теорему можно записать в виде импликации и т. о. выделить ее условие и заключение. Говорят, В логически следует из А или является логическим следствием из А, и пишут А | = В, если в таблицах истинности для А и В формула В имеет значение И во всех тех строках, где А имеет значение И. Отсюда вытекает, что А | = В тогда и только тогда, когда A Z) В есть тавтология. Если формула А тавтология, то иногда пишут | = А. Приведенное определение логического следования без труда расширяется на некоторую систему формул (систему посылок) А,,..., Ап, которая обозначается посредством Г, и тогда пишут Г | = В. Примером логического следования (вывода) из посылок является уже упомянутое правило modus ponens. Выводимость В из высказываний АиАэ В следует из того, что формула (А л (Аз В)) 3 В является тавтологией. Отметим также, что в силу таблиц истинности для связки импликации получаем, что тождественно истинная формула логически следует из любой системы формул. А из того, что имеется разрешаю-