Выполнимыми являются выражения, которые по меньшей мере при одном сочетании значений своих пропозициональных переменных принимают значение «истина».

С учетом объединения нейтральных выражений и законов в одну разновидность все формулы логики высказываний подразделяются на два класса - выполнимые и противоречия.

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

Мы остановимся лишь на самых важных и наиболее применимых на практике[Остальное в этом параграфе можно не изучать, если возникнут трудности.]. Совокупность развитых ранее положений послужит нам теоретической базой, они помогут нам обосновать последующие установления символической логики. В этом смысле те принципы, которые уже рассмотрены, являются фундаментальными, они позволят нам вывести последующие. Но надо помнить, что их математически строгого обоснования здесь нет. Развернутая на предыдущих страницах аргументация построена отчасти на примерах, отчасти на полуинтуитивных догадках. Однако поскольку в гуманитарных отраслях науки большей строгости и не требуется, то с точки зрения принятых здесь критериев достигаемое таким путем теоретическое единство более чем удовлетворительно решает основную задачу - придать изложению предельно компактный характер.

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

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

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

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

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

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

AÙ(BÚC)=(AÙB)Ú(AÙC), (10)

AÚ(BÙC)=(AÚB)Ù(AÚC). (11)

Это правило можно записать для большего числа переменных, если воспользоваться правилом подстановки. Допустим, у нас имеется формула (AÚB)Ù(CÚD). Заменим одну из скобок, скажем первую, буквой E и тогда у нас получится выражение, для которого закон дистрибутивности уже написан нами: EÙ(CÚD), Это позволит нам записать новое выражение

(AÚB)Ù(CÚD)= EÙ(CÚD),

применив к нему правило (10), получим

(AÚB)Ù(CÚD)= (EÙC)Ú (EÙD).

Теперь снова воспользуемся правилом подстановки, но уже для обратной цели - развернуть каждую из стоящих справа скобок и затем применить к каждой из них правило (10):

(AÚB)Ù(CÚD)= ((AÚB)ÙC)Ú ((AÚB)ÙD),

(AÚB)Ù(CÚD)= ((AÙC)Ú (BÙC)Ú (AÙD)Ú (BÙD)).

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

(AÚB)Ù(CÚD)= ((AÙC)Ú (AÙD) Ú (BÙC) Ú (BÙD)). (12)

Совершенно аналогично можно и правило дистрибутивности (11) обобщить на большее число переменных:

(AÙB)Ú(CÙD)= ((AÚC)Ù(AÚD)Ù(BÚC)Ù(BÚD)). (13)

Закон двойственности. В логике высказываний имеется также закон двойственности. Из формул (2) и (4) можно увидеть, что конъюнкция и дизъюнкция переходят друг в друга в некотором отношении подобным образом: чтобы получить из дизъюнкции конъюнктивное выражение, надо поменять знаки над пропозициональными переменными и над самой формулой, затем поменять знак дизъюнкции на конъюнктивный. Точно таким же образом конъюнкция переходит в дизъюнкцию. В логике высказываний доказывается также, что сходным способом преобразуются строгая дизъюнкция и эквивалентность:

Мы можем получить эту формулу, опираясь на те фундаментальные положения, которые изучены ранее. Для этого надо осуществить цепочку эквивалентных преобразований выражения (A«B). Сначала согласно (8) заменить эквивалентность на конъюнкцию двух импликаций и одновременно перевести импликации в дизъюнкции согласно (7), затем с помощью правила дистрибутивности для четырех переменных (12) развернуть формулу

Освобождаем полученное выражение от тождественно-ложных дизъюнктов и получаем

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

И теперь полученную дизъюнкцию двух скобок переведем в соответствии с (4) в конъюнкцию тех же скобок:

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

Заметим попутно, что строгая дизъюнкция при одновременной смене знаков над обоими ее переменными не меняет своего семантического значения; это можно увидеть из закона (9): при подобной смене все сводится к перестановке правой и левой скобок.

Обоснование второй из приведенных формул проводится аналогично.

Знаки Ù и Ú, а также и « называют двойственными. И все формулы, получающиеся простой заменой знаков на двойственные им, тоже называют двойственными. Переход в двойственное выражение, описываемый законами (2), (4), (14), (15), осуществляется и применительно к двойственным формулам любой сложности. Так, если у нас имеется формула

то двойственная ей будет

Как гласит закон двойственности, если формулы A и B эквивалентны, то тогда обязательно эквивалентны между собой и двойственные им формулы A* и B*.

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

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

Закон контрапозиции. Этот закон был известен еще Аристотелю. В традиционной логике с ним приходится сталкиваться в разделе о непосредственных умозаключениях и среди условно-категорических силлогизмов. Суть этого закона состоит в том, что, когда нам известна обусловленность одного положения другим (A®B) , то отсутствие второго является свидетельством отсутствия первого (от отсутствия следствия можно заключать к отсутствию основания - . Существует закон простой контрапозиции и сложной. Простой вариант этого закона может быть записан следующим образом:

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

.

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

Можно обосновать и более сильное выражение этого же самого закона простой контрапозиции. Для этого надо сначала применить полученный закон к выражению :

А это означает, что закон контрапозиции действует как в прямом, так и в обратном порядке, и мы можем написать его в двух формах:

, ,

затем конъюнктивно объединить обе формулы в одну:

и потом заменить обе импликации (в больших скобках) на одну эквивалентность, как это допускается формулой (8). Тогда у нас между скобками в (16) будет стоять не знак импликации, а эквивалентность:

В традиционной логике некоторым подобием контрапозиции является противопоставление предикату. Согласно правилам этого вида непосредственного умозаключения из суждения, скажем, «Радуга имеет семь цветов» можно вывести: «Несемицветное не является радугой». Чтобы сходство с контрапозицией стало очевиднее, лучше записать все рассуждение в иной форме: «Если явление есть радуга, то оно семицветное; следовательно, если явление не семицветное, то оно не есть радуга» где p - «Явление есть радуга», q - «Явление - семицветное»).

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

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

Его интерпретацией может быть, скажем, такое рассуждение: «Если абитуриент сдал вступительные экзамены и оплатил обучение, то он зачисляется в вуз, следовательно, если он не зачисляется в вуз, то значит или не сдал вступительные экзамены, или не оплатил обучение».

Как и в первом случае, мы подтвердим с помощью КНФ общезначимость этой формулы. Для этого заменим все импликации в формуле на дизъюнкции в согласии с (7):

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

Закон импортации. Его называют также законом внесения антецедента и записывают с помощью формулы

Смысл этого выражения не нуждается в особом пояснении. «Если зимой наступает оттепель, то, если затем ударит мороз, тогда на улицах гололед, отсюда следует, что если зимой наступает оттепель и затем ударит мороз, то тогда на улицах гололед» - такой пример может послужить иллюстрацией этого закона. Его приведение к конъюнктивной нормальной форме тоже не представляет особых затруднений:

Первое выражение получилось в результате замен всех импликаций в соответствии с (7) на дизъюнкции, затем мы стали преобразовывать конъюнкции в соответствии с (2) и дизъюнкции по формуле (4). Из полученного итога непосредственно виден общезначимый характер исходной формулы (18).

Закон экспортации. Этот закон представляет обратное отношение к тому, которое открывается в предыдущем:

и так же легко обнаруживает свой общезначимый характер:

Закон транспозиции. Соотношение логических союзов, названное законом транспозиции, было известно еще древним логикам из философской школы стоиков. Этот закон они даже доказывали. Нормальные формы ими, правда, не использовались. Их доказательства основаны на рассуждениях о логических союзах и их комбинациях. Но так делается и в современных учебниках по символической логике. В древних системах счисления нет также символов. Вместо них используются числительные. Конъюнктивное выражение в их передаче будет звучать: «Есть первое и второе», импликация у них выражается так: «Если есть первое, то есть и второе». Формула этого закона выглядит следующим образом:

Чтобы придать ему наглядность, возьмем высказывание «Если товар ходовой и рентабельный, то мы получим прибыль». Согласно закону транспозиции при верности такого высказывания должно быть истинным также и высказывание «Если товар ходовой, но прибыли нет, то, значит, товар не рентабельный». Для сведения выражения к нормальной форме избавимся сначала от импликаций, а затем от отрицаний над скобками:

По такой методике можно исследовать и все остальные выражения логики высказываний. Правда, когда заранее неизвестно, к какой категории относится анализируемое выражение, тогда приходится приводить его сначала к КНФ и, если оно не является тождественно-истинным, то тогда надо еще привести его и к ДНФ. Если же оно и к тождественно-ложным не относится, то значит перед нами нейтральное выражение.

Допустим, предстоит провести проверку такой формулы:

(p®q)Ù(p®r)®(p®(qÙr).

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

которое далее может быть преобразовано в дизъюнктивную нормальную форму (ДНФ):

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

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

У нас получилось две конъюнктивные нормальные формы – одна в большой скобке справа, другая – слева. Мы можем применить к ним правило дистрибутивности (12), рассматривая каждую маленькую скобку (в одном случае символ p) как одну переменную и учитывая, что самих переменных больше, чем указано в правиле. Тогда каждая такая скобка из левой части будет сочетаться с каждой из правой:

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

Из других законов логики высказываний полезно помнить еще закон исключения:

законы поглощения:

и законы выявления:

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

Глава II. Логика предикатов