Методы доказательств в логике высказываний примеры доказательств
Обновлено: 22.12.2024
Логика — это наука о способах доказательства.Выясним, в чем, собственно, состоит различие в построении доказательств в логике высказываний и логике Буля.
В булевой логике все доказательства строились на отношении эквивалентности. Даже если в множественных выражениях и фигурировало отношение включения, что является частным случаем отношения порядка, то его мы переводили в тождество. Две логические функции считались эквивалентными, если они давали на соответствующих наборах аргументов абсолютно одинаковые значения нулей и единиц. При использовании формальной записи логических выражений отдельные звенья цепи любого доказательства там были связаны через символ равенства «=». Отношение эквивалентности удовлетворяет трем законам —
рефлексивности: А = А;
симметричности: если А = В , то В = А;
транзитивности: если А = В и В = С, то А = С.
В логике высказываниивсе доказательства строятся наотношении порядка, т.е. на отношении, которое существует между причиной и следствием. Здесь уже отдельные звенья цепи доказательства связаны символом импликации. Однакс символ импликации « -> » при логическом выводе мы будем заменять на символ « =$• », подобно тому, как в логике Буля используются два символа эквивалентности — «
» являетсяобъектным, а « = » —субъектным. Таким образом, следует различатьязыклогики высказываний иметаязыкисследователя. Во избежание путаницы введем еще дваметасимвола: вместо объектной конъюнкции «» будем использоватьсубъектныйсимволметаконъюнкции— «,»,< вместообъектной дизъюнкции«» —субъектную метадизъюнкцию« ; ». Тогда утверждение, которое требуется доказать, в логике высказываний оформляется в виде следующегопричинно-следственного отношения:
где Рi—посылка (причина), С —заключение (следствие). Читается: «Если посылки Р1, Р2, . , Рn-1, Рn истинны, то заключение С тоже истинно» или, по-другому «Если причины Р1, Р2, . , Рn-1, Рn имели место, то будет иметь место и следствие С».
Чтобы не спутать объектное высказывание(предложение) ссубъектным высказыванием, справедливость которого мы намереваемся установить, условимся предложения типа (1.1) называтьклаузой(clause).
Клауза — это метапредложение, в котором использованоотношение порядка,оформленное через символметаимпликации« => ». Как и отношение эквивалентности, отношение порядка удовлетворяет трем законам:
рефлексивности: А => А;
антисимметричности: если , то;
транзитивности: если А => В и В => С, то А => С.
если А=>В и В=>А, то А = В.
Клауза есть именно формальная запись доказываемого предложения. Вместо букв в ней можно подставить объектные высказывания, и тогда клауза наполняется конкретным содержанием, которое уже именуется семантикой или легендой. Пример клаузы:
Если принять, что
А = сверкнула молния, В =грянул гром, то можно составить следующую легенду:
Известно, что если сверкнула молния, то после этого грянет гром. Молния сверкнула. Следовательно, должен и грянуть гром.
Над субъектом, который формулирует метапредложения, может стоять другой субъект, для которого уже предложения первого субъекта окажутся объектными. Тогда клаузу (1.1) второй субъект или метасубъект запишет для себя следующим логическим выражением:
.
Преобразовав это выражение в дизъюнкт, получим:
.
Отсюда легко находим:
.
Поэтому клауза (1.1) может быть представлена в другой эквивалентной форме:
. (1.2)
В силу коммутативности конъюнкции на месте посылки РЛ может оказаться любая другая, причем не одна. Например, клауза:
может быть преобразована в другую эквивалентную форму:
. (1.3)
Однако клауза (1.1) по сравнению с (1.2) и другими подобными формами, типа (1.3), имеет определенные преимущества и, в частности, используется в языке логического программированияПРОЛОГ. Ее называютхорновской. Произвольную клаузу всегда можно свести путем эквивалентных преобразований к хорновскому виду.
Если символ метаимпликации « => » клаузы (1.2) сместить в крайнее левое положение, то она превратится в тавтологию; если же его сместить в крайнее правое положение, то — впротиворечие.
1 => — тавтология,
— противоречие.
RДобавив в клаузу (1.1) слева 1 через «,» и сместив импликацию влево, получим смещением тавтологию.
Добавив в клаузу (1.1) справа через «;» 0 и сместив импликацию вправо, получим противоречие.
Ниже мы рассмотрим пять конкретных методов доказательства справедливости логических клауз:
аксиоматический метод,
метод таблиц истинности,
метод резолюций,
метод Вонга,
метод натурального исчисления.
Как и в логике Буля, в логике высказываний существуют аксиоматическийиконструктивныйподходы доказательств логических выражений. Два первых из только что названных пяти как раз являются яркими представителями таких подходов, остальные три метода — смешанной стратегии. Аксиоматическое построение логики высказываний состоит в том, чтобы попытаться вычленить из бесконечного числа истинных клаузнезависимую систему аксиом, с помощью которой можно было бы установить справедливость любых других клауз.
Мы уже сказали, что доказательство в логике высказываний строится на отношении порядка, которое является более общим случаем отношения эквивалентности. В самом деле, закон симметричности:
если А = В , то В = А
всегда можно представить в антисимметричной форме:
если А = В , то ,
но не наоборот. Следовательно, логика высказывания является расширениемлогики Буля. Поэтому все истинные тождества логики Буля автоматически становятся справедливыми клаузами логики высказываний. Например,закон склеивания:
можно представить следующими справедливыми клаузами:
,,
,.
Таким образом, независимая система аксиом логики Буля, которая состоит из четырех законов — коммутативности, ассоциативности, дистрибутивности, нуля и единицы— автоматически становится системой аксиом и логики высказываний. Для выражения жеотношения порядка, в принципе, требуется какое-то одноэлементарноевысказывание, к которому можно было бы сводить остальные более сложные высказывания. Сейчас мы его и введем.
Истину может изречь всякий.
На формальном языке логики высказываний эту сентенцию можно представить следующей клаузой:
Она означает: «если А истинно, то источником этой истинности может быть что угодно, например В ». Если произвести эквивалентное преобразование этой клаузы
Р, откуда следует
то семантика ее тоже изменится, и станет примерно такой: «если ранее было установлено, что А истинно, то истинность В не может проявиться так, что А станет ложным» или «истинность одного высказывания (B) не может повлиять на истинность другого высказывания (A)». Путем эквивалентных преобразований клаузу (1.4) всегда можно преобразовать к другим формам:
, А => А; В,, .
Однако в качестве основной аксиомы логики высказываний, выражающей отношение порядка, мы возьмем клаузу (1.4).
Теперь на первом нашем примере, который был приведен выше, выясним, как производится доказательство справедливости логической клаузы. Исходная клауза имела вид:
Преобразуем ее к несколько иному виду:
.
После раскрытия скобок и упрощения сразу же приходим к аксиоме порядка (1.4). Доказанная элементарная клауза (1.5) известна с времен Аристотеля и играет исключительно важную роль в логике высказываний. Она имеет даже специальное латинское название — modus ponens — правило отделения. Если в процессе доказательства справедливости какой-либо сложной клаузы удалось свести ее к клаузе (1.5), будем считать, что доказательство состоялось.
Читайте также: