Математическая логика. Шапорев С.Д, страница 2

Поэтому необходимо выбрать некоторме начальные законы, нщыввемые аксиомами, которые принимаются без доказательств, остальные законы — теоремы — могут быть дакюаны исходя нз аксиом. К системе аксиом предъявляется одно непременное требование — она должна быть непротиворечивой. Это значи~, что из данной системы аксиом (непротиворечивой) нельзя логическим путем вывести деа прети воречащик друг другу утверждения.

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

Остальные понятия, нвзыеаемые прошводггы»ги, определяются в терминах основных. Совокупность основных и производных понятий, аксиом и теорем назывеется аксиомагялческой сисвгежой. Все составляющие аксиаматическай системы могут рассматриваться с двух точек зрели»: в виде сбьекта, имеющего собственную внутреннюю структуру, или в виде предложения, выражающего определенный факт. Изучение внутренней структуры аксиом и теорем назыщется со»макси вским иву»ел»ем иксиоматичгскш с стем, изучение их смысла — семантическим итучелиен. Современная теория множеств — база мвтематической логики — не содержит "парадоксов" (типа парадокса рассела о "нормальном" множестве), однако средства этой аксиоматической теории не позволяют докиать ее непротиворечивость.

'и й Иваеее Лова евсея» (1792 — галь) — Вус к В метем»ми Раааа 1. Алгебре лешки ~алгебра ени знваннй2 1.2. Операции над высказываниями учение о высказываниях — алгебра высказываний, или алгебра логики,— являстся прсстейшейг логической теорией Она рассматривает конечные конйигурапии символов и взаимоотношения между ними. Знакоьютво с законами алгебры высказываний облегчает изучение более сложных логических исчислений. Высказывание — это всякое повествовательг~ое прелдожсние, унверлдающее что-либо а чем-либо, при этом нспреьзенно истинное нли ложное. Логическими значениями высказываний являются "истина" и "ложь", обозначаемые ~ и О. Высказывание — это те первичныс понятия теории, «сторыс не определяютгж строго, а лишь поясншотся Высказывания.

представлмощие собой одно утверлгдснпс, называютс» луосшымн или юемеямауныжн; высказывания, получагошиеся из злсментарныь с помощью грамматических связок "не", "и", "или", "если, то.. ", называютея слоаклыжн. Эти нювания нс носят абсолютного характера, высказывания, которые в одной ситуании молгна считать простыми, в другой сигуании будут сложными. В алгебре высказываний исслелуетсв вопрос сб истинности сложного высказывания в зависимоспз от истинности входящих в него простых высказыааниьз. При зтам необходимо иметь в виду, что высказыюние может быть истинно в определенной ситуанин.

Эта снгуания бывает определена или не апрелслена в самом лысказывании Существуют высказывания истинные (иззи ложиые2 во всех аозьзожных снтуаниях Такие высказывания называются абснлюлгво нсгннллыжн (соответствсьзно абсолюмно гожггыяш) Абсолютна истинные и абсолютно ложные высказывания называннся логнчесьлмл колсшаллю и. В алгебре логики все высказывания рассматрнваютс» толька с гочки зрения их логического значения, житейское содержание игнорируется Какгдое высказывание может быль либо истинным, либо ложным.

ни одно высказынание не может быть одновременно истинным и ложным. Элементарные высказывания обозначаются строчныьзи буквами яатинского шзфавша. а, 6, с Из высказываний с помощью логических связок образунмся новые высказывания. Рассмотрим теперь несколько логических связок. Отрнггикием еьзслазыаання х называется новое высказывание, коларов явллетсл истинным, если высказывание х ложно, и ложным, сали х истинно. Обозначается х, ~итается "ие х " нли "неверно, что х ". Все логические значения высказывания: можно описать с помощью табл. К2.К Если х — высказывание, то х — орш ннопо.южное высказывание.

Тогда ьюжно образовать х, которое называется деойныи огггрггггаггзгезг еыскггзыеа пн. Логические Часзь Г. Математическая ломка значения о, очевидно, совпалащт со значениями х . Эта операция одноместная в том смысле, что из одного данного простого высказывания х строится новое еыскюыеание х. Коиьюнкяией (логическом умножением) двух высюмыеюгий х и у называется новое высказывание х, которое истинно только тогда, когда оба высказывания х и у истинны, и ложно, когда хотя бы одно из х и у ложно. Обозначается хму или хну, читается "х и уд Таблица истинности конъюнкции дана в таб».

!.2.2. Тайюяа !.2. Г Таалиягг 1.22 О О ! Из определения операции конъюнкции видно, что союз "и" а алгебре логики гпотребляется е томже смысле, что и е повседневной речи. Однако в алгебре югнки этой связкой можно связывать любые, сколь угодно далекие по смысгу выскюыеаниа. (оиъюикцию часто называют логическим умножением.

В современной маематике алово "умножение" часто обозначает различные математические игерации, обладающие свойствами, более или менее похожими иа свойства грифметнческого умножения Пргг построении таблицы истинности испольюважя союз "и". Однако результат был бы тот же самый, если бы были эзя'ы союзм "а", "но", "однако", "хати" и т. и. Таким образом, хотя соотеетстбющие этиьг союзам логические связки имеют различные смысловые птенки, с точки зрения алгебры высюзыеаннй они неразличимы. 2юъюнкпией (логичесюю слоэсеиием) пвуа высказываний х и у называется ювсе высююыеание, коъзрое считается истинным, если хоти бы одно из еы,«азыеаний х и у истинно, и ложным, если они оба ложны.

Обозначается х м у, читается "х или у ". Логические значения дизъюнкции описываются ~ табл. !.2Л. рава Г. Лпгеб логики ~аогсл а вн я аиващя Таял Ла 2.2.С Теаляяа 2.2.3 В повселневной речи союз "или" употрсбллеюа н различном смысяс: нскльочающем и неискюачающем В алгебре лье логики связка "илн" упогребляется всегда е ненскжо ьающси смысле (объелиььяьощсм смысле). Анююгнчно в латинском языке имеется соьоз "ссГ' лля еюночигельной дизъюнкции и "ань" длн разделительной. Сиььвол 'г происходит от первой буклы союза "сеГ' Имилнхаьгьгсьз бьосььчсскюь слсоосоь и яг2 двух вьюказьжаний х и у ннзываетсл новас высказывание, которое считается ложным, когда т истинно, а у лоькно, и истинным во всех осщгщных случаяк Обозначассся .т -ь у, читаетс» "есви х, то у" нли "из .ь следует у" Высказывание .с называется усяоенсн, посылкой нли авьььслсдсьььььоьь, ньюкезываиис у — юьсдсжсисм, зоюю ьслнсм или коисскссюнон.

Уаблщы истинности этой операшьи приведена в табл. О2.4. Из таблицы истинности видно, что если условие х истинно н истинна импликация х -Ь у. зо верно и закльочение у. Эго классическое правило вывода, которас постоянно используется в математике орн переходе от одних высказываний к другим с помощью лоьсазььььяемых теорем.

которые, как правило. имсьст форму нмплнканнй. Распространенная ошибка в иатсматическик рассуждениях состоит в том. что к высказываньио л, истинность которого ие установлена, приььеняется правильная теорема х -Ь у и из истинности предлоькения у деластс» вывод об истиьщости х. В обыденной речи высказывание типа "если х, то у " носит объясняющий характер. Оно как бы разьясняет, почему имщт места событие у — потому, что имело место событие .ь Объяснякилий характер импзикации тесна связан с причинно-следственны» отношением, при котором х выступает в роли причины, а у — слелстлия.

Употребление союзов "если..., то " в алгебре логики отличается от употребления их в обылонной речи, гд» по обыкновению считают, что если хложно, ю у вообще не имееь смысла Кроме того, в обыденной речи полразумепаюся, что из предложения л всегда вытекает у. В математической Йсгь 1. Матвхмжчесяая лоГищ логике последнего ие требуется, т.к. смысл высказываний игнорируется, кроме ик свойств быть истинными или ложными. В случае имплнктции несоответствие между обычным пониманием истинности сложного высказывания и идеализированной точкой зрения алгебры высказываний еще заметнее, чем для других логических операций. Здесь истинность импликации в некоторой ситуации означает лишь, что если в этой ситуации истинна посылка, то истинно и заключение. Зкаияшгслппей гэкянватсгглгиослгью, логической эквивпленлтосшью) двук высказываний х и у нюываетс» новое высказывание, которое истинно, когда оба выскюываиия х и у либо одновременно истиннм, либо одновременно ложны, и ложно во всех сстальнык случаях.

Обозначается х г-т у, читается "для того чтобы х, необходимо и достаточно, чтобы у" илн "х тогда и только тогда, когда у ". Эквивачентность играет значительную роль в математических докюатсльствак. Известно, что большое число теорем формулируется в форме необходпмык и достаточных условий. Это теоремы существования.

Например, "лл» тога, чтобы два вектора а и Ь были линейно зависимы, необходимо и достаточно, чтобы они были коллинеарны". Логические значения операции эквивалеиции описывжотся в табл. 1.25. Символы,гчщ-ь,ет называются иролозштнональными связками или ашзками исчисления высказываний. Вместо употребляемого нами знака ь-з часто пишут — или и, вместо -+ пишут ~, вместо ш или л часто употребляют точку, причем точку иногда опускают, вместо употребляют знак перед выскюыюнием. уяа Ю т.дя Т Г «па 1.Дб Логическим связкам приписываются ранги в следующем порядке убывания старшинства:,л,щ-в,тч. Таким образом, связка более высокого ранга имеет большую область действия.

(- ляв г, ллгвбра ланки (ал сбра емталишнил) Н» следует думать, что эзим набором исчерпываижся все логические связан. Например,сушествуетзикая операннц как штрик Шеффера, Она обозначается символом х ( у н опрелелястся слелуюшей таблицей истинности (табл, 1,2 б) Как ьгы покажеьз в дальнейшем, всякую формулу алгебры логики путем зквиралеитных преобразований можно заменить формулой, содержащей только дие логические операции: коньюнкцию и отрицание илн дизъюикцию и отрицание.

Двльнейшее исключение логических операций невозможно. Опера ция же штрих Шеффера характерна теы. что с ее иомошью может быть выражена лвзбая из пяти операций. Например, хах)х. Таблица истинности для этой формулы приведена в табл. ).2.7. Для операции «аньюнкции, нызример, выражение через цшрих Шеффера имеет вил х л у = ( л ) у )ах ~ у ). Его з аблица истинности лана в табл. ) Од, Тяббил» 7.2. 7 Таб Лв 1.2.б 1.3.