Учебник. Никифоров А. Л. Логика и теория аргументации

• Название: Никифоров А. Л. Логика и теория аргументации
• Анкор: Учебник
• Дата: 23.09.2020
• Размер: 1.04 Mb.
• Имя файла: Nikiforov_2003.pdf
• Тип: Документы; #139345
• страница: 3 из 9

Тема 6. ТЕОРИЯ ДОКАЗАТЕЛЬСТВ В ИСЧИСЛЕНИИ
ПРЕДИКАТОВ
Изучив материалы темы, Вы сможете:
 указать отличия между теорией доказательств в исчислении высказываний и теорией доказательств в исчислении предика- тов;
 сформулировать теорию дедукции для исчисления предикатов;

 сформулировать правило подстановки в исчислении предика- тов;
 дать определение вывода и доказательства в исчислении пре- дикатов.
Теория доказательств в исчислении предикатов имеет много общего с теорией доказательств в исчислении высказываний, од- нако есть некоторые существенные отличия, которые позволяют разделять эти теории.
Исчисление предикатов имеет свои особенности. В отличие от исчисления высказываний в алфавите исчисления предикатов содержатся предикатные буквы, предметные или индивидные пе- ременные, квантор всеобщности и существования (подробнее см. тему 9).
Эти особенности сказываются на определении формулы в исчислении предикатов и формулировке правил вывода (см. тему
9 и тему 10).
Для предикатной формулы имеют значение свободные и связанные вхождения переменных. Данные вхождения опреде- ляются правилом подстановки. Определение свободных и свя- занных вхождений переменных дано в теме 9. Правило подста- новки в исчислении предикатов формулируется по отношению ко всем видам переменных, фигурирующих в формулах.
Подстановкой в формулу А переменной у вместо х называ- ется замещение в А всех свободных вхождений х вхождениями у.
Результат подстановки в формулу А обозначается посредством
Подстановка в у вместо х называется корректной, если ни одно введённое данной подстановкой вхождение у, не оказывает- ся связанным в
В правильных рассуждениях некорректная подстановка не- допустима, так как она может привести к ложным утверждениям.
Например, мы знаем, что формула выражает всегда вы- полнимое арифметическое условие, то есть условие, которому удовлетворяет любое численное значение переменной. Но некор- ректная подстановка y вместо x в данную формулу даёт высказы- вание
, выражающее ложное суждение.

Теорема дедукции для исчисления предикатов отличается от теоремы дедукции для исчисления высказываний ограничением, которое состоит в том, что во вспомогательном выводе свобод- ные переменные (определение свободных переменных см. в теме
9) должны оставаться фиксированными для подлежащих устра- нению исходных формул.
Теорема дедукции для исчисления предикатов. Если Г, А
├
В,
причем все свободные переменные остаются фиксированными для последней исходной формулы А, то Г ├ (A→B).
Выводом в исчислении предикатов называется непустая ко- нечная последовательность формул
,…,
, удовлетворяющая следующим условиям:
1) каждая есть либо посылка, либо получена из предыду- щих формул по одному из правил вывода;
2) если в выводе применялись правила введения имплика- ции или правила введения отрицания, то все формулы, начиная с последней посылки и вплоть до результата применения данного правила, исключаются из дальнейших шагов построения вывода;
3) ни одна индивидная переменная в выводе не ограничива- ется абсолютно более одного раза (см. ограничения на примене- ние правила «введение всеобщности» и «удаление существова- ния»);
4) ни одна переменная не ограничивает в выводе сама себя
(см. ограничения на применение правила «введение всеобщно- сти» и «удаление существования»).
Доказательство в исчислении предикатов есть вывод из пус- того множества неисключённых посылок.
Завершённым выводом в исчислении предикатов называется вывод, в котором никакая переменная, абсолютно ограничивав- шаяся в выводе, не встречается свободно ни в неисключённых посылках, ни в заключении.
Завершённое доказательство в исчислении предикатов есть завершённый вывод из пустого множества неисключённых посы- лок.
Примеры доказательства в исчислении предикатов приведе- ны в 10.

Контрольные вопросы:
1. Сформулируйте теорему дедукции для исчисления предика- тов.
2. Как определяется вывод в исчислении предикатов?
3. Сформулируйте правило подстановки в исчислении преди- катов?
4. В чём состоит отличие между доказательством в исчислении высказываний и доказательством в исчислении предикатов?
5. Какие особенности определяют различие между исчислени- ем высказываний и исчислением предикатов?
Тема 7. ЭМПИРИЧЕСКОЕ И ДЕДУКТИВНОЕ ДОКАЗА-
ТЕЛЬСТВА
Изучив материалы темы, Вы сможете:
 уяснить сходство между логическим выводом, доказательст- вом и рассуждениями в естественном языке;
 понять суть взаимодействия между интуицией и логикой;
 указать особенности интуиционистской логики;
 показать слабые и сильные стороны «интуитивной» логики.
Процессы логического вывода и доказательства имеют мно- го общего с рассуждениями в естественном языке, где также вы- водят одни высказывания из других, но, правда, при этом явно не указывают логические правила вывода, которыми пользуются, предполагая их известными. Именно это обстоятельство застави- ло логиков строить исчисления, напоминающие выводы в естест- венном языке. Нередко поэтому их называют натуральными вы- водами. Из этих исчислений наиболее известным и признанным считается система натурального вывода, построенная Г. Генце- ном, появившаяся в 1934 г.
Наряду с логикой существуют внелогические элементы мышления. Одним из таких элементов является интуиция. Ин-
туиция – способность непосредственно, как бы «внезапно», не прибегая к опосредованному умозаключению, находить, откры-

вать истину; внутреннее «озарение», просветление мысли, рас- крывающее суть изучаемого вопроса, процесс дальнейшего хода развития исследуемого предмета, явления.
Интуиция как "прямое видение истины" не является чем-то сверхразумным. Она не идет в обход чувств и мышления и не со- ставляет особого рода познания. Ее своеобразие состоит в том, что отдельные звенья процесса мышления проносятся более или менее бессознательно и запечатлевается только итог мысли – внезапно открывшаяся истина.
Существует давняя традиция противопоставлять интуицию логике. Нередко интуиция ставится выше логики даже в матема- тике, где роль строгих доказательств особенно велика. Так, на- пример, Декарт ставит интуицию выше дедукции. Дедукция – это, согласно Декарту, логическое рассуждение, опирающееся на аксиомы (вполне достоверные исходные положения), но досто- верность аксиом усматривается разумом интуитивно.
Неумеренное возвеличение интуиции в ущерб строгому до- казательству неоправданно. Логика и интуиция не исключают и не подменяют друг друга. В реальном процессе познания они, как правило, тесно переплетаются, поддерживая и дополняя друг друга. Доказательство санкционирует и узаконивает достижения интуиции, оно сводит к минимуму риск противоречия и субъек- тивности, которыми всегда чревато интуитивное озарение. Толь- ко проведенное шаг за шагом логическое доказательство делает завоевания интуиции объективно установленным результатом.
Уточняя и закрепляя результаты интуиции, логика сама об- ращается к ней в поисках поддержки и помощи. Логические принципы не являются чем-то заданным раз и навсегда. Они формируются в многовековой практике познания и преобразова- ния мира и представляют собой очищение и систематизацию стихийно складывающихся "мыслительных привычек". Вырастая из аморфной и изменчивой пралогической интуиции, из непо- средственного, хотя и неясного "видения логического", эти принципы всегда остаются связанными с изначальным интуитив- ным "чувством логического". Не случайно строгое доказательст- во ничего не значит даже для математика, если результат остает- ся непонятным ему интуитивно.

Логика и интуиция не должны противопоставляться друг другу, каждая из них необходима на своем месте. Внезапное ин- туитивное озарение способно открыть истины, вряд ли доступ- ные последовательному и строгому логическому рассуждению.
Однако ссылка на интуицию не может служить твердым и тем более последним основанием для принятия каких-то утвержде- ний. Интуиция приводит к интересным новым идеям, но она не- редко порождает также ошибки, вводит в заблуждение. Интуи- тивные догадки субъективны и неустойчивы, они нуждаются в логическом обосновании. Чтобы убедить в интуитивно схвачен- ной истине, как других, так и самого себя, требуется развернутое рассуждение, доказательство.
В современной логике существует направление, для которо- го интуиция является основным понятием и принципом – интуи-
ционистская логика. Интуиционизм – одно из направлений в ма- тематике, которое в интуиции видит основание математики и формальной логики. Интуиционистская логика была системати- зирована Л. Брауэром и представлена в виде исчисления А. Гей- тингом. Предшественником интуиционистской школы является французский математик А. Пуанкаре.
Логику интуиционисты рассматривают как часть математи- ки. Они отрицают понятие актуальной, завершённой бесконечно- сти, а принимают понятие потенциальной, становящейся беско- нечности. В связи с этим положением, они отрицают примени- мость принципа исключённого третьего в операциях с бесконеч- ными множествами. Ход рассуждения интуиционистов при этом таков: допустим, что какому-то элементу бесконечного множест- ва присуще свойство А; доказать, что истинно суждение «Всем элементам этого множества присуще свойство А» или истинно суждение «Ни одному элементу этого множества не присуще свойство А» невозможно, так как ряд этих элементов потенци- ально бесконечен, поэтому проверить все альтернативы в прин- ципе не представляется возможным.
В интуиционистской логике не принимается закон снятия двойного отрицания, то есть отрицается действие закона:

А→А. Но в интуиционистской логике проходит правило наве- шивания двойного отрицания, то есть правило, согласно которо-

му можно от формулы А переходить к формуле А (но не об- ратно).
В интуиционистской логике не отрицается применимость закона исключённого третьего для конечных множеств. Законы тождества и противоречия признаются интуиционистами в неог- раниченном смысле.
Контрольные вопросы:
1. Почему логические исчисления напоминают выводы в есте- ственном языке?
2. Что такое интуиция?
3. Какую роль играет интуиция в доказательстве?
4. Кто является основателем интуиционистской логики?
5. Какие особенности интуиционистской логики определяют её принадлежность неклассической логике?
Тема 8. КЛАССИЧЕСКАЯ ЛОГИКА ВЫСКАЗЫВАНИЙ
Изучив материалы темы, Вы сможете:
 понять, что такое логика высказываний, и какую роль она иг- рает в анализе естественного языка;
 перевести на язык логики высказываний любое сложное суж- дение и построить для него таблицу истинности;
 указать основные законы логики;
 уяснить суть семантической проблемы разрешения;
 уметь использовать в качестве разрешающей процедуры по- строение таблиц истинности и приведение к нормальным фор- мам формул логики высказываний;
 знать основные равносильности логики высказываний.
Логика высказываний, или исчисление высказываний – раз- дел математической логики, изучающий логические операции с простыми высказываниями, которые объединяются в сложные высказывания с помощью пропозициональных связок, сходных с принятыми в обычной речи союзами: «и» (в математической ло- гике представлен символом &), «или» (v), «если…, то…» (→),
«если … и только если…», «тогда и только тогда, когда» (↔), а

также с отрицанием, обозначаемым частицей «не» (¬). Исчисле-
ние – такая система изучения тех или иных областей объективно- го мира, в которой предметам какой-либо определённой области ставятся в соответствие материальные знаки (цифры, буквы и др.), с которыми затем по принятым в системе точным правилам производятся операции, необходимые для решения поставленной цели.
Высказыванием в исчислении высказываний называют вы- ражение, в отношении которого можно утверждать, что его со- держание либо истинно, либо ложно.
Особенность исчисления высказываний состоит в том, что в нём не рассматривается логическая структура простых высказы- ваний, т. е. связь между субъектом и предикатом, как это имеет место в суждении.
Алфавит логики высказываний содержит три категории зна- ков:
1. Пропозициональные переменные, которыми обозначают про- стые суждения, входящие в состав сложного –
,
,
,
...,
,
,
,
1 1
1 1
s
r
q
p
s
r
q
p
2. Логические союзы и знак одноместной операции отрицания: ,
&, v, →
, ↔, .
3. Скобки, которые выполняют роль знаков препинания: ( , ).
Роль структурных образований, аналогичных элементарным и сложным высказываниям, играют в этом языке формулы. Фор- мулы – это такие конечные последовательности знаков алфавита, которые построены по определённым правилам и образуют за- конченные выражения логики высказываний.
Определение формулы логики высказываний:
1. Пропозициональная переменная есть формула.
2. Если А – произвольная формула, то А – тоже формула.
3. Если А и В – произвольные формулы, то (А&В), (АvВ), (А→В),
(А↔В), (А В) – тоже формулы.
Заглавные латинские буквы А и В, которые употребляютсяв определении формулы, принадлежат не языку логики высказыва- ний, а его метаязыку, то есть тому языку, на котором мы говорим о языке логики высказываний, и служит для обозначения произ- вольных формул, записанных на языке логики высказываний. В

отличие от букв, которые являются пропозициональными пере- менными, их называют метапеременными, или метабуквами.
Содержащие метабуквы выражения А, (АvВ), (А&В),
(А→В), (А↔В), (А В) – не формулы, а схемы формул опреде- лённого вида. Например, выражение (А&В) есть схема формул
(p&q), ((p↔q)&r), ((p→q)&(svr)) и т.п., а выражение (АvА) – схема формул (pvp), (qvq), ((p→r)v(p→r)).
Каждая формула логики высказываний превращается в ис- тинное или ложное высказывание, если все входящие в неё про- позициональные переменные заменить конкретными истинными или ложными высказываниями.
Точный смысл (семантика) логических знаков может быть разъяснён с помощью специальных таблиц, в которых зафикси- ровано, при каких логических значениях формул А и В формулы
А, (А&В), (АvВ), (А→В), (А↔В), (А В) истинны, а при каких ложны.
Таблица истинности p q p&q pvq p q p→
q p↔
q и и л л и л и л и л л л и и и л л и и л и л и и и л л и
Таблица истинности (для отрицания) p p и л л и
Построив искусственный логический язык, постоянным ко- торого придан точный смысл, мы можем теперь переводить на него выражения естественного языка. Перевод с обычного разго- ворного языка на язык логики высказываний осуществляется в результате содержательного анализа смысла предложений.
Рассмотрим в качестве примера сложное суждение: «Спорт- смен подлежит дисквалификации, если он нетактично себя ведёт по отношению к сопернику или судье и если спортсмен употреб- ляет стимулирующие вещества». В этом сложном суждении 4

простых суждения, обозначим каждое из них пропозициональной переменной:
Спортсмен подлежит дисквалификации – p;
Он нетактично ведёт себя по отношению к сопернику – q;
Он нетактично ведёт себя по отношению к судье – r;
Спортсмен употребляет стимулирующие вещества – s.
Запишем это суждение в виде формулы:
(((qvr)&s)→p)
Осуществив перевод с естественного языка на язык логики высказываний, мы достигли того, что избавились от всей инфор- мации, которая не относится к логике, выявили логическую структуру сложного высказывания, сделали её недвусмысленной и доступной прямому наблюдению.
По каждой формуле логики высказываний всегда можно по- строить отвечающую ей таблицу, в которой зафиксировано, какие логические значения будет получать данная формула при различ- ных наборах логических значений своих переменных.
Построим таблицу истинности для данной формулы, причём количество комбинаций истинностных значений определяется по формуле 2n (два в энной степени), где n – количество перемен- ных, входящих в формулу. В нашей формуле 4 переменные, по- этому комбинаций истинностных значений будет 16: p q r s (qvr) ((qvr)&s)
(((qvr)&s)→p)
и и и и и и
и
и и и л и л
и
и и л л и л
и
и л л л л л
и
л л л л л л
и
л л л и л л
и
л л и и и и
л
л и и и и и
л
л и л и и и
л
и л и л и л
и
л л и л и л
и
и и л и и и
и
и л л и л л
и
л и и л и л
и
и л и и и и
и
л и л л и л
и

Заключительный столбец (последний столбец в нашей таб- лице) содержит и значение «истина» и значение «ложь». Это зна- чит, что наша формула является нейтральной (фактической).
Существуют тождественно-истинные высказывания – это вы- сказывание, которое при любых значениях простых суждений, входящих в его состав, имеет значение «истина». Такие высказы- вания называют также тавтологиями, а формулы, которые им со- ответствуют, тождественно-истинными формулами или законами логики. Каждая тождественно-истинная формула выражает ка- кой-то логический закон.
Например, формула p→p является выражением закона то-
ждества. Согласно закону тождества всякая мысль в процессе рассуждения должна оставаться тождественной самой себе.
Построим таблицу истинности для данного закона: p p→p и
и
л
и
Независимо от того, принимает пропозициональная пере- менная p значение «истина» или «ложь», формула p→p имеет значение «истина».
Закон исключённого третьего, согласно которому два про- тиворечащих друг другу суждения не могут быть одновременно истинными и одновременно ложными, имеет формулу pvp.
Построим таблицу для данного закона: p p pvp и л
и
л и
и
Независимо от того, принимает пропозициональная пере- менная p значение «истина» или «ложь», формула pvp имеет значение «истина».
Закон противоречия, согласно которому два противополож- ных суждения не могут быть одновременно истинными, по край- ней мере, одно из них необходимо ложно, имеет формулу
(p&p).
Построим таблицу для данного закона:

p p p&p
(p&p) и л л
и
л и л
и
Независимо от того, принимает пропозициональная пере- менная p значение «истина» или «ложь», формула (p&p) имеет значение «истина».
Существуют также тождественно-ложные формулы или противоречия, которые принимают только значение «ложь».
Например, суждение «Она хорошо готовит, если и только если неверно, что она хорошо готовит». Формула данного сужде- ния: p↔p.
Данная формула имеет таблицу: p p p↔p и л
л
л и
л
Независимо от того, принимает пропозициональная пере- менная p значение «истина» или «ложь», формула p↔p имеет значение «ложь».
Иногда различные по своей структуре формулы таковы, что одинаковым наборам логических значений переменных во вход- ных столбцах таблиц этих формул отвечают одинаковые логиче- ские значения в соответствующих строках заключительных столбцов.
Например, в таблицах формул (p→q) и (p&q) p q q
(p→q) и и л
л
л и л
и
и л и
и
л л и
и
p q p&q
(p&q) и и и
л
и л л
и
л и л
и
л л л
и
одинаковым наборам логических значений переменных p и q во входных столбцах отвечают одинаковые логические значе- ния в соответствующих строках заключительных столбцов. О та- ких формулах говорят, что они равносильны.

Отношение равносильности, во-первых, рефлексивно, т.е. А
равносильно А; во-вторых, симметрично, т.е. если А равно-
сильно В, то В равносильно А; в-третьих транзитивно, т. е. ес-
ли А равносильно В и В равносильно С, то А равносильно С.
Пусть А и В – формулы, Е1, Е2,…, Еn список всех пропози- циональных переменных, входящих по крайней мере в одну из них. Будем говорить, что А и В – равносильные формулы, если при любых логических значениях Е1, Е2,…,Еn логические значе- ния А и В совпадают.
Список равносильных формул:
(1) A равносильно A;
(2) A&B равносильно B&A – закон коммунитативности конъ- юнкции;
(3) A&(B&C) равносильно (A&B)&C – закон ассоциативности конъюнкции;
(4) AvB равносильно BvA – закон коммутативности дизъюнкции;
(5) Av(BvC) равносильно (AvB)vC – закон ассоциативности дизъюнкции;
(6) Av(B&C) равносильно (AvB)&(AvC) – закон дистрибутивно- сти дизъюнкции относительно конъюнкции;
(6') (B&C)vA равносильно (AvB)&(AvC) – закон дистрибутивно- сти дизъюнкции относительно конъюнкции;
(7) A&(BvC) равносильно (A&B)v(A&C) – закон дистрибутивно- сти конъюнкции относительно дизъюнкции;
(7') (BvC)&A равносильно (A&B)v(A&C) – закон дистрибутивно- сти конъюнкции относительно дизъюнкции;
(8) A&A равносильно A – закон идемпотентности конъюнкции;
(9) AvA равносильно A – закон идемпотентности дизъюнкции;
(10) (A&B) равносильно AvB – закон де Моргана;
(11) (AvB) равносильно A&B – закон де Моргана;
(12) A&B равносильно (A→B);
(13) A→B равносильно AvB;
(14) A&B равносильно (AvB);
(15) AvB равносильно (A&B);
(16) A↔B равносильно (AvB)&(BvA);
(17) A B равносильно (AvB)&(AvB);
(18) (AvB)&(AvB) равносильно B – закон исключения;
(19) A&(AvB) равносильно A – закон поглощения;

(20) Av(A&B) равносильно A – закон поглощения;
(21) (AvC)&(BvC) равносильно (AvC)&(BvC)&(AvB) – закон выявления;
(22) (A&C)v(B&C) равносильно (A&C)v(B&C)v(A&B) – закон выявления;
(23) A→B равносильно B→A – закон контрапозиции;
(24) A↔B равносильно A↔B;
(25) A B равносильно (A↔B);
(26) A↔B равносильно (A→B)&(B→A);
(27) A↔B равносильно (A&B)v(A&B);
(28) AvB равносильно A→B;
(29) A→B равносильно (A&B);
(30) (A→B) равносильно A&B;
(31) A↔B равносильно (A B);
(32) A B равносильно (A↔B);
(33) A↔B равносильно (A B);
(34) (A B) равносильно (A↔B).
Знаки & и v, а также знаки ↔ и являются двойственными логическими знаками.
Пусть А формула, в которую не входит знак →. Формулой, двойственной А, называют формулу А*, которая получается из А заменой каждого вхождения знаков & и ↔ соответственно двой- ственными им знаками v и и заменой каждого вхождения зна- ков v и в А соответственными им знаками & и
↔.
Например, если А – формула
(pvq)↔((p&r)v(q&r)),
То двойственная ей формула А* будет иметь вид
(p&q)
((
pvr)&(qvr)).
Все приведённые равносильности можно доказать при по- мощи таблиц истинности.
Используя транзитивность отношения равносильности, зная о равносильности одних формул, можем судить о равносильности других.
Правило разрешающее в формуле А выделенное вхождение подформулы В заменять равносильной формулой В', называется
правилом равносильной замены.
Например, надо доказать равносильность формул (pvq) и
(p→q).

(pvq) равносильна (p&q) согласно равносильности (11)
(p&q) равносильна (p→q) согласно равносильности (12)
Как уже было сказано каждая формула логики высказыва- ний может быть или тождественно-истинной, или тождест-
венно – ложной, или нейтральной. Тождественно-истинные и
нейтральные формулы являются выполнимыми формулами. Вы-
полнимая формула – формула логики высказываний, получающая значение «истина» хотя бы для одного набора логических значе- ний своих переменных.
Задача, состоящая в отыскании процедуры, позволяющей для любой формулы выяснить, какому из трёх перечисленных выше классов она принадлежит, называется семантической про-
блемой разрешения для формул логики высказываний. В соответ- ствии с этим процедура, позволяющая конечным числом простых действий решить проблему разрешения, называется разрешаю-
щей процедурой. Процесс построения по данной формуле отве- чающей ей таблицы есть разрешающая процедура семантической проблемы разрешения для формул логики высказываний.
Впрочем, использовать табличный метод можно только в том случае, когда в формулу входит небольшое количество пере- менных и она не очень длинная. Для формул, содержащих боль- шое количество переменных, существуют другие разрешающие процедуры.
Известно, что смысл разрешающей процедуры заключается в возможности отличить тождественно-истинные формулы от ос- тальных.
Первым пунктом разрешающей процедуры является приве- дение к нормальной форме.
Формула логики высказываний имеет нормальную форму, если она: а) не содержит знаков →,↔, и б) знаки отрицания стоят в ней только при переменных.
Например, формула (((pvq)&r)v(rvq)) имеет нормальную форму, а формула ((p&q)vr)v(qvs) – нет.
Любую формулу А, не имеющую нормальной формы, мож- но преобразовать в формулу А', которая имеет нормальную фор- му.

Для того чтобы данную формулу привести к нормальной форме, необходимо произвести в ней следующие равносильные замены:
1) каждую подформулу вида (А В) заменить согласно равно- сильности (17) формулой ((AvB)&(AvB));
2) каждую подформулу вида (A↔B) заменить согласно равно- сильности (16) формулой ((AvB)&(BvA));
3) каждую подформулу вида (A→B) заменить согласно равно- сильности (13) формулой (AvB);
4) каждую подформулу вида (A&B) заменить согласно равно- сильности (10) формулой (AvB);
5) каждую подформулу вида AvB заменить согласно равносиль- ности (11) формулой (A&B);
6) каждую подформулу вида A заменить согласно равносиль- ности (1) формулой А.
Формула имеет нормальную форму, если ни один из пере- численных пп. 1) – 6) настоящего предписания к ней не приме- ним.
Например, дана формула
(p q)→((p→r)→(q→r))
Четырежды применяя правило равносильной замены, со- гласно равносильности (13) получаем формулу
(p q)v((pvr)v(qvr))
Из неё согласно равносильности (17) получаем формулу
((pvq)&(pvq))v((pvr)v(qvr))
Из неё согласно равносильности (10) получаем формулу
(pvq)v(pvq)v((pvr)v(qvr))
Из неё согласно равносильности (11) получаем формулу
(p&q)v(p&q)v((p&r)v(qvr))
Трижды применяя правило замены, согласно равносильно- сти (1) получаем следующую формулу в нормальной форме
(p&q)v(p&q)v((p&r)v(qvr))
Которую, пользуясь соглашением о бесскобочной записи кратной дизъюнкции, можно записать
(p&q)v(p&q)v(p&r)v(qvr)
Приведение к конъюнктивной нормальной форме (КНФ) по- зволяет по виду формулы, приведённой к некоторой стандартной форме, судить о том, тождественно-истинная она или нет.

Формула логики высказываний имеет КНФ, если она имеет вид
В1&B2&…&Bm,
Где В1, В2,…, Вm – элементарные дизъюнкции и m ≥ 1.
Элементарной дизъюнкцией называется формула, которая имеет вид
А1vА2v…vАn,
Где n ≥1, а Аi (i ≤ n ) есть или переменная, или отрицание переменной.
Для того чтобы формулу привести к КНФ, необходимо вна- чале с помощью известной процедуры привести её к нормальной форме. Затем каждую подформулу вида (Av(B&C)) согласно рав- носильности (6) и каждую подформулу вида ((B&C)vA) согласно равносильности (6') заменить формулой ((AvB)&(AvC)).
Например, формула (p→q)→(pvq)
Приведём её вначале к нормальной форме:
(pvq)→(pvq) (13)
(pvq)v(pvq) (13)
(p&q)v(pvq) (11)
(p&q)v(pvq) (1)
Затем, с помощью равносильности (6') получаем формулу
(pvqvp)&(pvqvq),
Которая имеет КНФ. Данная формула является тождествен- но-истинной.
Формула, имеющая КНФ, тождественно-истинна тогда и только тогда, когда тождественно-истинны все её конъюнктив-
ные члены, т.е. когда каждая элементарная дизъюнкция содер- жит хотя бы одну пару дизъюнктов, из которых один есть неко- торая переменная, а другой – её отрицание.
Каждая не тождественно-истинная формула имеет КНФ, ко- торая называется совершенной.
Совершенной конъюнктивной нормальной формой (СКНФ) некоторой формулы называется такая её КНФ, которая удовле- творяет следующим условиям: a) в ней нет двух одинаковых конъюнктивных членов, и ни в од- ном конъюнктивном члене нет двух одинаковых дизъюнктов;

b) ни в одном конъюнктивном члене нет таких двух дизъюнктов, из которых один есть переменная, а другой – отрицание этой переменной; c) в каждом конъюнктивном члене содержатся все переменные данной формулы.
Для того чтобы привести формулу к СКНФ необходимо:
1) Привести её к КНФ;
2) На основании равносильностей (2), (4), (8) устранить из КНФ повторяющиеся конъюнкты, т. е. из всех имеющихся одинако- вых конъюнктивных членов оставить один и вычеркнуть ос- тальные;
3) На основании равносильностей (4) и (9) устранить все повто- рения в конъюнктивных членах КНФ;
4) На основании равносильностей (2), (4) и (47) (AvИ (тождест- венно-истинная формула) равносильно А) устранить из КНФ те конъюнктивные члены, которые являются тождественно- истинными элементарными дизъюнкциями;
5) Ко всем тем конъюнктивным членам, в которых отсутствует какая-либо из содержащихся в данной формуле переменных Е, на основании равносильности (50) приписать знак дизъюнкции и вслед за ним тождественно-ложную конъюнкцию (Е&Е), а затем применить правило замены по равносильности (6). Эту процедуру повторять до тех пор, пока в каждый конъюнктив- ный член не будут входить все переменные, содержащиеся в данной формуле;
6) Если в получившейся КНФ снова появились одинаковые конъюнктивные члены, то надо устранить повторения.
Процедура приведения формулы к СКНФ используется для отыскания логических следствий данных посылок.
Например, приведём к СКНФ формулу (p→q)v(p&r)
Сначала приведём её к КНФ
(pvq)v(p&r) (13)
(pvqvp)&(pvqvr)
Потом устраняем повторения в первом конъюнкте
(pvq)&(pvqvr)
Так как в первом конъюнктивном члене отсутствует пере- менная r, то присоединяем к нему знаком дизъюнкции формулу
(r&r)

(pvqv(r&r))&(pvqvr)
Затем применяем равносильность (6) получаем формулу
(pvqvr)&(pvqvr)&(pvqvr)
Устраняем один из одинаковых конъюнктивных членов и получаем формулу в СКНФ:
(pvqvr)&(pvqvr)
С помощью СКНФ можно получить обзор всех таких след- ствий из данных посылок, которые сами имеют СКНФ. Однако интерес представляют наиболее сильные следствия данных посы-
лок. Формула А сильнее формулы В, а формула В слабее формулы
А, если тождественно-истинна формула А→В, но не формула
В→А. Поэтому представляют интерес простые следствия. След- ствие В из посылок А1, А2,…, Аn называют простым, если В есть такая не содержащая повторений и не тождественно-истинная элементарная дизъюнкция, которая не «поглощается» никаким другим более сильным следствием из посылок А1, А2,…, Аn та- кого же вида. Простые следствия из данных посылок мы можем найти при помощи процедуры приведения к сокращённой КНФ.
Сокращённой КНФ данной формулы называется такая её
КНФ, которая удовлетворяет следующим условиям: а) ни в одном конъюнктивном члене нет двух одинаковых дизъюнктов; б) ни в одном конъюнктивном члене нет таких двух дизъ- юнктов, из которых один есть переменная, а другой отрицание этой переменной; в) нет таких пар конъюнктивных членов, что каждый дизъ- юнкт из одного имеется в другом, т.е. нет двух одинаковых конъюнктивных членов и нет таких двух конъюнктивных членов, из которых один поглощается другим; г) если имеются такие два конъюнктивных члена, из кото- рых один содержит некоторую переменную, а другой – её отри- цание, то в той же КНФ имеется конъюнктивный член, который является элементарной дизъюнкцией, построенной из всех дизъ- юнктов данной пары, отличных от упомянутой переменной и её отрицания.
Для того чтобы привести формулу к сокращённой КНФ не- обходимо:
1) привести её к КНФ;

2) из всех одинаковых конъюнктивных членов КНФ оставить толь- ко один и в элементарных дизъюнкциях также устранить все по- вторения;
3) устранить все тождественно-истинные конъюнктивные члены;
4) если среди конъюнктивных членов КНФ имеются два таких, что один содержит некоторую переменную, а другой – её отрицание, то на основании закона выявления, необходимо добавить новый конъюнктивный член, являющийся дизъюнкцией остальных дизъюнктов этих двух конъюнктивных членов, а также, новый конъюнктивный член не должен быть тождественно-истинным и отличается от уже имеющихся;
5) применяя закон поглощения, равносильность (19), устраняем все поглощаемые конъюнктивные члены.
Например, даны посылки p→r, r→q, p→r. Необходимо найти все их простые следствия. Приводим конъюнкцию посылок к КНФ:
(p→r)&(r→q)&(p→r)
(pvr)&(rvq)&(pvr)&(qvp)&(pvp)
Устраняем повторения в новых конъюнктах
(pvr)&(rvq)&(pvr)&(qvp)&p
Производим все поглощения:
(rvq)&p
Формулы (rvq) и p являются простыми следствиями данных посылок, т.е. если посылки истинны, то формула (rvq) – истинна, и p – истинна.
Формулы логики высказываний наряду с КНФ могут иметь дизъюнктивную нормальную форму (ДНФ).
Формула логики высказываний имеет дизъюнктивную нор-
мальную форму, если она имеет вид В1, В2,…Вm, где В1,
В2,…Вm – элементарные конъюнкции и m ≥ 1.
Элементарной конъюнкцией называется формула, которая имеет вид А1, А2,…, Аn, где n ≥ 1, Аi (I ≤ n) – либо переменная, либо отрицание переменной.
Для того чтобы привести формулу к ДНФ, необходимо при- вести её вначале к нормальной форме. Затем каждую подформулу вида (A&(BvC)) согласно равносильности (7) и каждую подфор- мулу вида ((BvC)&A) согласно равносильности (7') заменить формулой ((А&B)v(A&C)).

Например, надо привести к
ДНФ формулу
(((p→q)→(q→r))&(rvp)).
Сначала приводим её к нормальной форме:
((p&q)v(qvr))&(rvp)
Затем приводим к ДНФ:
(((rvp)&(p&q))v((rvp)&(qvr)))
(p&q&r)v(p&q&p)v(((rvp)&q)v((rvp)&r)))
(p&q&r)v(p&q&p)v(q&r)v(q&p)v(r&r)v(r&p)
Данная формула не является тождественно-ложной, так как только один дизъюнктивный член содержит пару конъюнктов, из которых один есть переменная, а другой – её отрицание (r&r).
Если бы все дизъюнктивные члены содержали бы пару конъюнк- тов, из которых один есть переменная, а другой – её отрицание, то формула была бы тождественно-ложной.
Каждая не тождественно-ложная формула имеет ДНФ, ко- торая называется совершенной.
Совершенной ДНФ (СДНФ) некоторой формулы называется её ДНФ, которая удовлетворяет следующим условиям: а) в ней нет двух одинаковых дизъюнктивных членов, и ни в одном дизъюнктивном члене нет двух одинаковых конъюнктов; б) ни в одном дизъюнктивном члене нет таких двух конъ- юнктов, из которых один есть переменная, а другой – отрицание этой переменной; в) в каждом дизъюнктивном члене содержатся все перемен- ные данной формулы.
Для того чтобы привести формулу к СДНФ, необходимо:
1) привести её к ДНФ;
2) на основании равносильностей (2), (4) и (9) устранить из ДНФ повторяющиеся дизъюнкты;
3) на основании равносильностей (2) и (8) устранить все повторе- ния в дизъюнктивных членах ДНФ;
4) на основании равносильностей (2), (4) и (50) устранить из формулы те дизъюнктивные члены, которые являются тожде- ственно-ложными элементарными конъюнкциями;
5) ко всем тем дизъюнктивным членам, в которых отсутствует какая-нибудь из содержащихся в данной формуле переменных
Е, на основании равносильности (47) приписать знак конъюнк- ции, вслед за ним – тождественно-истинную дизъюнкцию

(ЕvЕ) и применить правило замены по равносильности (7).
Эту процедуру повторять до тех пор, пока не окажется, что в каждый дизъюнктивный член входят все переменные, содер- жащиеся в данной формуле. Если в формуле снова появились одинаковые дизъюнктивные члены, то надо устранить повто- рения.
С помощью СДНФ можно получить обзор всех гипотез дан- ной формулы, которые имеют СДНФ.
Гипотезой формулы В называют такую формулу А, что формула А→В тожденственно-истинна.
Например, приведём формулу (q&(rvs)) к СДНФ.
Вначале приведём её к ДНФ:
(q&r)v(q&s)
Пополняем оба дизъюнкта недостающими переменными:
((q&r)&(svs))v((q&s)&(rvr))
(q&r&s)v(q&r&s)v(q&s&r)v(q&s&r)
Устраняем возникшие повторения и получаем СДНФ дан- ной формулы:
(q&r&s)v(q&s&r)
С помощью сокращенной ДНФ можно найти все простые гипотезы формулы. Гипотеза А формулы В называется простой, если А есть элементарная конъюнкция, которая не тождествен-
но-ложная, не содержит повторений и не поглощается никакой
другой, более слабой, гипотезой формулы В такого же вида.
Сокращённой ДНФ данной формулы называется такая её
ДНФ, которая удовлетворяет следующим условиям: а) ни в одном дизъюнктивном члене нет двух одинаковых конъюнктов; б) ни в одном дизъюнктивном члене нет таких двух конъ- юнктов, из которых один есть переменная, а другой – отрицание этой переменной; в) нет двух одинаковых дизъюнктивных членов и нет таких двух членов, из которых один поглощается другим; г) если имеются такие два дизъюнктивных члена, из кото- рых один содержит некоторую переменную, а другой – её отри- цание, то в этой же ДНФ имеется дизъюнктивный член, который является элементарной конъюнкцией, построенной из всех конъ-

юнктов данной пары, отличных от упомянутой переменной и её отрицания.
Для того чтобы привести формулу к сокращённой ДНФ нужно произвести следующие преобразования:
1) привести её к ДНФ;
2) во всех дизъюнктивных членах ДНФ и в элемнтарных конъ- юнкциях устранить все повторения;
3) устранить из ДНФ все тождественно-ложные дизъюнктивные члены;
4) если среди дизъюнктивных членов ДНФ имеются два таких, что один содержит некоторую переменную, а другой – её от- рицание, то на основании закона выявления, т.е. равносильно- сти (22), добавить новый дизъюнктивный член, представляю- щий собой конъюнкцию остальных конъюнктов этих двух дизъюнктивных членов, при условии, что новый дизъюнктив- ный член не тождественно-ложный и отличается от всех ос- тальных;
5) снова устранить повторения в новых дизъюнктивных членах
ДНФ;
6) если среди дизъюнктивных членов ДНФ имеются такие, кото- рые поглощаются другими, то по равносильности (20), устра- няются все поглощаемые дизъюнктивные члены.
Например, дана формула (((p&q)v(r&s))→(p&q&r)). Не- обходимо найти все простые гипотезы данной формулы.
Сначала приводим её к ДНФ:
(((p&q)v(r&s))v(p&q&r))
(((p&q)&(r&s))v(pvqvr))
(((pvq)&(rvs))vpvqvr)
((((pvq)&r)v((pvq)&s))vpvqvr)
(r&p)v(r&q)v(s&p)v(s&q)vpvqvr
Затем приводим полученную формулу к сокращённой ДНФ:
pvrv(s&q)vq
pvrv(s&q)vqvs
pvrvsvq
Таким образом, данная формула логически следует из гипо- тезы p, или гипотезы r, или гипотезы s, или гипотезы q.
Контрольные вопросы:

1. Дайте определение логики высказываний.
2. Какие формулы называются тождественно-истинными?
3. В чём отличие между законом исключённого третьего и за- коном противоречия?
4. Как Вы думаете, почему при ложности антецедента и ис- тинности консеквента, импликация принимает значение
«истина»?
5. В чём заключается смысл процедуры приведения формулы к нормальной форме?
6. Какие логические знаки являются двойственными?
7. Укажите преимущества и недостатки построение таблицы истинности для данной формулы как разрешающей проце- дуры семантической проблемы разрешения.