Гильберт, Аккерман - Основы теоретической логики (947372), страница 43
Текст из файла (страница 43)
В силу уже отмеченных нами эквивалентностей (а) и (б) и определения знака «й» случай (1) можно выразить через: (1') Хйу й У. Случай (П) через: (1!') Х й У й 2. Итак, если один из двух случаев (Г) или (!Г) имеет место, то высказывание Р»ы исгинно. Наоборот, если эта высказывание истинно, то имеет песта один из случаев (!') или (1!').
Высказывание; «Р,», истинна», таким образам, эквивалентна высказыванию: (Хйуйй) ту (ХйуйУ). И»генно это высказывание и может служить, следа- ВатЕЛЬНО,ВЫражЕНИЕМдЛя СпажНОГОВЫСКаэнзаиня Рма Так как в сголбце, соответствующем высказыванию Р„„буква и встречается на трех последних местах (в трех последних строках нашей таблицы), то выснззывание Рмм мажет быть выражено формулой: (Х й У й г') тУ (Х й У й 2 ) 'У (Х й У й 7) . т»и иизыввемых чмиогозпачпых вогик». В тихих логиках оысиопыввиии «Х» и »Х истииио» уже ие »ивнев»сигмы.
Если, например, подразделить все пысивиывпиии и»: 1) иеп»ииые, 2) иожиыв, 3) бессмыспепцые (леиии »юбии ирииодигь и пример бе»синг. лицы выр»копие »сапоги в«ми»иу»), то при условии, что вы«ив»ив»иве Р бес«мы«девиа, утворждеиие »Р истинно» должно быть ив»»»ифию»ров»ив ие иви бессиысдипи, и ивх ложь. 17* жо При«оп«ение )! )Е«мм«итерип и э 7 персей еле«и Аналогично, высказывание В„„ истинное толька один раз: когда Х ложно, и У ложно, и ю истинно, выражается формулой хйуй г.
Мы видим, чта для каждого из слс>кных высказываний, из.бражаеь<ых столбцами прав.й части нашей таблицы, за исключением одного единственного всегда лен<ного В„„существует эконвалентное ему выражение, содержащее только знаки, б< и <,7' и притом имеющее пполне определенную форму. Именно, оно представляет собой дизъюпкцию из членов, каждый из ко>орых содержит все элементарные высказывания, снабх<енпые или не снабженные знаками отрицания и соегнненные друг с другом знаками б<. В каждом днзыонк<ивном члене всякое элементарное высказывание встречается при этсм только адин раз.
Такое выражение для слоя<ааго высказывания называе>сч его соверш<ямб норлнпльной формой. Север<пенной потому, что каждое сложное высказывание может бь>ть представлена е эшой форл<е одним единственным способом: ведь разным днзъюнктннным членал< соответстпуют разные строки, в которых для нашего сложного высказывания стакт знзченне «истинное; и, следовательно, две формулы описанного нами вида не могут соответствовать двум эквивалентным высказываниям, если они имеют разное числа дизъюнктивных членов или если у ннх имеются > Тек кок с помощью вкпивепентцостеа: Х д У окв Х у У, Х>УУ екя Хау, Х У екв Х ><7 У. л>абие пве пз епеков щ Н, можно зеиеипть отрицаипеи и третькь> <см.
стр. 27), ю ясна, что тикки образам булет лопе»вне к аостеточпость любой ие пвр> , Зн , Ч> два различных дизыснктивных члена <с иначе распределенными знаками отрицания над буквами). ,Цо сих пар мы имели дело только с примерами, заниствсванными нз табл. 3, т, е. со сложными высказываниями, зависящими от трех элементарных высказываний Х, 1', З. Ясно, однако, ч>о паш прием носит с<вершенно общий характер и может быть распространен на любое число элементарных высказываний Х„Х„..., Х,.
В качестве упражнения запишем в совершенной диэъюнкгивнай нормальной форме, через элементарные высказьшання Х и У, сложное высказывание Х У. Так как последнее определяется таблицей 1, то таким выражением для нега буди: ~ХйУ) >,7(Хб~ ) >У !Хйу), т. с. формула, выража>ошая, что в таблице, спреде- плющей слсжноевысказываниеХ У,значение «истинно» встречается в первей, третьей и четвертой строках. Заметим <ше, что высказывание, выраженное с по. мощью пс всех букв Х„Х„..., Х„всегда можно записать в виде формулы в совершенной нормальной форме. содержащей все буквы Х„Хю..., Хи. Так, высказывание У можно выразить в совершенной нормальной форме ч~рез Х н У следующим образом. В таблице, ссставленнсй для элементарных высказываний Х н У, высказывание У соответствует столбцу, содержащему буквы )сверху вниз): л, и, л, и, Оно, х)-у ) у)х и и л и Таблица 4 гог Прил»женое !1 Н»мыелтлрый л,е 1 лерлгй главы газ следсвательно, истинно в случаях, соответствующих второй и четвертой строкам таблицы 4.
Выра»кением его в дизъюнктивней нормальней форме поэтому служит: (ХйУ) »1(ХйТ). Аналогично высказывание Х, выраженное в совершенной нормальной форме, приобретает вид: (ХАЬ) ~У(ХйУ). Составление таблицы было бы, однако, слишком громоздким приемом решения задачи о приведении произвольной формулы к совершенной дизъюнктнвной нормальной форме. Чн»атель нейдет в тексте книги прастсй общий прием ее решения.
Мы здесь напомним еще только, что среди сложн лх высказываний есть одна, которое не может быть выражено в такай форме, Это всегда-лажное зысказывтание, Однако такое высказывание может быть выражено н двсйственной к дизъюнктивной — коныолклеивл»й совершенной нормальной форме, к которой можно притти следующич образам.
Столбец, соответствующий н нашей таблице 3, например, сложному высказываниео Р„можееа охарактеризовать и с помощью полного перечисления всех случаев, когда это вьесказыаание ложно. Так, и нашей таблице 3 высказывание Р, ложно в случаях, отображенных в шестой н восьмой строках, т. е. противоположное ему высказывание Р, истинно в случаях; или ХЙУ»е 2. Так как выражения »Р, истнннаа н еР»» эквивалентны, то для р„мы получаем дизьюнктивную совершенную нормальную форму: (ХйуйЫ) у(ХйГй2).
Образовав же ее противоположность' по освещенному в книге правилу де-Мартана, мы получим для сложного высказывания Г» новое выражение, теперь уже в так называемой конъюлктивной совершенной нормальной форме: (Х '~ У гр2) й (Х гр У гр 2) или, используя принятые авторами соглашения, относящиеся к способам записи формул: ХУ2»»ХУУ. Ясно, чта в этой форне можно ззписать и всегдалаясиое высказывание (которое при эгон, очевидна, будет содержать все возможные конъ»онктивные члены), иа, наоборот, нельзя выразить всегда-истинное высказывание.
Подробную характеристику конъюнктивной совершенной »юр»»алькой формы, простой способ приведения к цей всякого (кроме всегда-истиннога) высказыванич, а также отличное от использованного нами доказательство едннсеаеннасгн выражения в совершенной нормальной форме читатель найдет и тексте книги. Там же он увидит далее, какую роль играет выраженно в конъюнктивной совершенной нормальной форме для решения задачи о нахождении всех логических следствий (в смысле исчисления нысказываинй] из данных посылок, равно как и задачи о нахождении всех возможных посылок, из которых данное выражение мажет логическа слсдсвать (а смысле исчисления высказываний).
Отметим также простой и остро) нный способ приведения формул исчисления высказываний к совершенной днзъюнктивной нормальней форме, содержащийся в работе И. И. Жегалкина «Арифметизация символической логики», помещенной в «Математическом сборнике», т. 35, вып. 3 — 4, стр. 311— 377 (!928 г.).
Пса<<жени< Ы К<ми<им<рва < я >Π— га в<р«и гяа<н жз К<ми<не<рва к бй 1а — 13 нервен главы Как уже было отмечено в ж мментарии к 1 1 пегвой >.лавы, исчисление высказываний м< жно строить двумя различными си<с<бами; 1) сгдер>кательноалпритмическим, или табличным, и 2) ф<рмнльнодедук<квным, или ансисматическил<. Аьснсматнческс»<у п<стр<ению посвящены п<следнке четыре параграфа первей главы.
В псясиепие их ограничимся здесь только самой общей характеристикой задачи такого псстрсепия. Мы уже видели, что н исчислении иысказываний оси<аную р< ль играют всегда-кстннныа еысказыпша<я, или <законья л< гики. Именно с их псм< шью и решается задача п<лучения л<гических следствий из данных п<сыл<к, Далее, каждым двум эквивалентным формулам Я и 8 соответствует одни всегда-истинная формула <>1 5.
Так, паре энвквалентных формул: Х У и Х ы У соответствует ф<рмула: Хву Х <у У, паре э>,вквалентгых ф<р»ул Х и Х вЂ” ф<рл<ула: Х Х Всякой зкгивглентности, на основании которой происходит преобразовагие ф<рмул к нормальной и соаерценной нормальной форме,соответствует таким образом всегда-истинная формула. Для целей исчислений высказываний достаточно поэтсму указать сп<ссб, позволяющий охарактеризовать весь запас нсегда-истинных формул этого исчисления. При аксиаматичесном псстроеини это делается следующим <бравом. Из всегда-истинных формул исчисления высказываний выбираются некоторые, принимаемые за аксиомы.
Затем задаются правила, пазно. ля<ащие из выбранных формул <выводить» новые. Как аксиомы, так и гынодимые из них формулы считаются дона>вялыми. Задача, катару<о приходится решать прн аксиоматическом пестр<енин, состоит в такам выборе аксиом н правил вывода, чт<бы запас долизуеных ф<рмул и:сидя:атичгсвого п<стр енин совпал с запасом г;егда-истинных фар»>ул содержательного.
При такой' н<,стан<вне в<пр<са ясна, что аьсиоматическсе настроение имеет смысл только, если мы располагаем уже содер>кательным. Но в таком случае, естественно, встает вопрос, для каких целей оиа может понадобиться. ' Для ответа на этот вспрсс заметим, чта даже в применении к исчислению высказываний, рассматривающему элементарные высказывания как нерасчленяемые целые, возможно дальнейшее развитие. Последнее и прогсхсдит на самом деле и прит<м даже в двух различных направлениях. При табличном и< стр<ении перед<пят от двузначн<го исчисления, соответствующего классической формальн< й лсгике, к различ>.ым мн<г<значным, рвзличаюшн»>, например, такие характеристики суждений, как необходимость.
воэможность н негазможигсть и мн<гие другие. Прн ансисматическ<м и<стр< енин извеняют или с, всем отказываются ат нек<тсрых анш<гм или правил оывгда. При этом оказывается, чта для всяк<хо табличн<го п<стр<ения всегда существует с<веги<ение адэлнатное ему аксиоматическ<е; однако не всшце акскаматически п стр<еннсе исчисление может быть построено и табличка. Так называемая <конструктиакая» л<гика, к<торую, как показал А. Н. Кглмог<ров, м<жно истолковать как исчисяеиге луобяея< и в кот<.р< й нет «закона исключенного тре>ьег<», нли различные исчисления «строгай импликации», о которых мы упоминали уже в комментарии к первому пара~рафу, не дспускают, например, адэкватн<го им табличного пестр<ения. Табличнсе п<стр<ение невозможно и для >ик называемого «узксго исчисления предикатсв», следующего в настоящей книге за исчислением высказываний и строящегося н ней акспоматически.
Таким образом, Прп южеиие !! Комм»ни>прей и Я !Π— >З первой «зели 267 аксиоматическое построение является более общим, чем табличное. рйы назвали табличное построение исчисления высказываний ссдержательно-алгоритмическим. а аксиоматическсе †формаль-дедуктивным. Ззметим, оливка, чта и аксиомы можно трактовать содерщсате.гьне, понимая, например, входящие в них буквы Х У, Л,...
как высказывания, а знаки —,д,~/,—, как логические связи между высказываниями. ПКстати, именно в этом смысле аксиомы и должны быть всегда-истинными иысказыванияии). С другой стороны, при табличном построении мы фактически использовали толька то обстоятельство, что каждое из элементарных высказываний мажет иметь одна и только одно из двух значений: епстиннсь, сложно», и чго значением зависящего от элементарных сложного высказывания опя~ьтаки мажет быть одно и толька одно из этих двух зиа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
