Эквивалентность через конъюнкцию и дизъюнкцию

Эквивалентность через конъюнкцию и дизъюнкцию

XII.- законы поглоще­ния.

Для сокращения и лучшей обозримости записей бу­дем иногда опускать знак конъюнкции (так же как опус­кают знак умножения), условившись под выражением ХY подразумевать формулу (X/Y). Так, например, вме­сто формулы (X/У)/Z будем иногда писать ХУ/Z‑ запись X(Y/Z)X нужно понимать как формулу (Х /(Y/))/.

Обратим внимание на характер соответствий между равносильностями, объединенными в пары под номерами V-XIII. В этих соответствиях проявляется так назы­ваемый принцип двойственности.

Две фор­мулы, не содержащие знаков → и ↔, называются двой­ственными, если каждую из ник можно получить из другой заменой /, /, и, л соответственно на /, /, л, и.

Принцип двойственности утверждает следующее: если две формулы (не содержащие знаков → и ↔) равно­сильны, то двойственные им формулы тоже равносильны.

Например, для формулы л двойственной является формула и, а для формулы Х/л — формула Х/и; убе­дившись, что Х/л≡л, согласно принципу двойственности получаем равносильность Х/и≡и.

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

Имеют место следующие равносильности (проверь­те!):

Будем говорить, что равносильность (1) выражает им­пликацию через дизъюнкцию и отрицание, а равносиль­ность (2) — через конъюнкцию и отрицание.

Эквиваленция выражается через конъюнкцию и импликацию равносильностью

(проверьте!). Из равносильностей (3) и (1) получаем равносильность

выражающую эквиваленцию через конъюнкцию, дизъюнкцию и отрицание. Из равносильностей (3) и (2) получаем равносильность

выражающую эквиваленцию через конъюнкцию и отри­цание.

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

Возникает вопрос: а нельзя ли выразить через какую-ни­будь одну операцию все остальные? Можно доказать, что ни через одну из введенных здесь пяти логических операций этого сделать нельзя. Нужны, по меньшей мере, две операции; при этом одной из них обязательно должно быть отрицание.

Все остальные операции можно выра­зить через конъюнкцию и отрицание, дизъюнкцию и от­рицание или импликацию и отрицание. Через эквиваленцию и отрицание остальные операции выразить нельзя.

Зачем же вводить пять операций, когда можно обой­тись двумя? Напомним, что введенные пять операций соответствуют наиболее употребительным союзам. Ис­пользование лишь двух операций усложнило бы формализацию предложений естественного языка и привело 6ы к громоздким, труднообозримым формулам. В других приложениях математической логики эти доводы в пользу введения и употребления всех пяти операций теряют силу; там ограничиваются меньшим числом опера­ций. Аналогичное положение имеет место в арифметике: всякое число может быть записано с помощью двух цифр: 0 и 1; однако, поскольку записи чисел и выкладок в двоичной системе счисления очень громоздки, мы при­бегаем к этой системе лишь в специальных случаях.

Можно ввести логическую операцию, через которую выражаются все пять операций: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Такова, напри­мер, операция, соответствующая сложному союзу «не A или не B» («или» — неразделительное). Эта операция обозначается символом | (например, А|В) и получила название штрих Шеффера. Штрих Шеффера определяет­ся с помощью такой таблицы:

X Y Х|Y
и и л
и л и
л и и
л л и

Непосредственно из таблицы видно, что Х|У≡.

Легко убедиться (сделайте это!), что Х|Х≡. Из этих двух равносильностей следует, что X/Y(X|Y)|(X|Y).

Таким образом, нам удалось выразить через штрих Шеффера отрицание и конъюнкцию, а через них, в свою очередь, можно выразить дизъюнкцию, импликацию и эквиваленцию.

| следующая лекция ==>
IX.- законы де Моргана | Теория Грооса

Дата добавления: 2014-01-07 ; Просмотров: 1219 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

В символической логике доказано, что одни логические союзы могут заменяться на другие и при этом не нарушится смысл высказывания. Выражение, содержащее, скажем, союз “или”, можно при желании переформулировать в такое, в котором вместо него будет стоять, скажем, конъюнкция или импликация, и если исходное выражение было истинным, то и полученное в результате преобразования тоже останется истинным. Мы остановимся лишь на самых распространенных видах сложных высказываний — конъюнкции, дизъюнкции и импликации. Они являются также наиболее употребительными и в обычном языке. Доказательство формул для преобразования одних видов суждений в другие очень сложно, мы его опускаем, беря их каждый раз уже готовыми.

Конъюнкция преобразуется в дизъюнкцию с таким же набором значений истинности переменных следующим образом:

Мы ставим знак равенства между выражениями, подчеркивая этим, что формула не доказана. Но вообще в логике высказываний доказательства этой и других подобных формул даны со всей математической строгостью. Так что при использовании этого закона допустимо ставить знак эквивалентности и применять к нему все законы логики высказываний, подтверждая их, если, надо с помощью нормальных форм (см. выше пар. 1.3). Для преобразования в импликацию надо руководствоваться формулой, которая тоже приводится здесь без доказательства:

Допустим, у нас имеется сложное конъюнктивное высказывание: “Казак — это пахарь и воин”. Разбив его на два конъюнкта и воспользовавшись приведенными законами преобразования, мы легко получим два высказывания, равносильных исходному, но выраженных иначе — с дизъюнкцией и импликацией: “Неверно, что казак — это или не пахарь, или не воин”, “Неверно, что если казак — пахарь, то он не воин”.

Читайте также:  Лджи вебос тв смарт

На месте переменных A и B может быть и сложное выражение. Возьмем фразу из комедии «Горе от ума», один из персонажей которой говорит: «Умный человек не может быть не плутом». Придадим ему сначала форму конъюнктивного выражения: «Не бывает, чтоб человек был умен и не был плутом» . Здесь одна переменная имеет отрицание, но указанные законы все равно применимы и в этом случае. Если проводить преобразование по формуле (2), то получится сначала, а потом после применения закона (1) останется:

На словах это звучит так: «Или не умен, или плут». А вот как выглядит преобразование по третьей формуле:

Переведя полученное выражение в словесную формулировку, имеем: «Если человек умен, то он плут».

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

Для преобразования выражений с тремя переменными возьмем такое сложное высказывание: “Преступление раскрыто, но неверно, что его раскрыли Петров или Сидоров” — гдеp — “Преступление раскрыто”, q — “Преступление раскрыл Петров”, r —“Преступление раскрыл Сидоров”. Преобразуем его в такое, которое содержит импликацию вместо конъюнкции, для чего нам понадобится воспользоваться законом (3), а скобку мы будем рассматривать как одну переменную (в соответствии с правилом подстановки):

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

Дизъюнкция преобразуется в другие выражения по следующим формулам:

,

Например, дизъюнктивное высказывание “Преступная группа совершила ограбление вчера (p) или позавчера (q)” будет равносильно такому, выраженному через конъюнкцию: “Неверно, что преступная группа не совершала ограблений ни вчера, ни позавчера”. А высказывание “товар, проходящий через таможню, является экспортным (p) или импортным (q)” может быть преобразовано в равносильное импликативное: “Если товар, проходящий через таможню, не является экспортным, то он является импортным”. Можно также попробовать преобразовать известное латинское изречение: “О мертвых — или ничего, или хорошо”. Сначала напишем формулу для него: гдеp означает “О мертвых что-нибудь говорить”, q — “О мертвых говорить хорошо”. Преобразование формулы в соответствии с законом (5) пройдет в два этапа:

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

Возможно, конечно, преобразование этого же изречения и в конъюнкцию по формуле (4):

“Hевеpно (неправильно) говорить что-либо о мертвых и при этом не говорить хорошо”.

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

Формула для перевода импликации в дизъюнкцию выводится аналогично.

Чтобы проиллюстрировать эти правила преобразования наглядным примером, возьмем широко известное шутливое изречение: “Кому не везет в картах, тому везет в любви”. Обозначив как p — “Везет в картах” и q — “Везет в любви”, получим запись этой мысли с помощью символов: Преобразование ее в конъюнкцию по формуле (7) и дизъюнкцию по формуле (6) проведем одновременно:

Дизъюнктивное высказывание, эквивалентное первоначальному, будет звучать: “Или везет в картах, или везет в любви”; конъюнктивное — “Не бывает, чтобы не везло в картах и не везло в любви”.

Для проведения таких же преобразований на высказывании с тремя переменными можно взять одно из правил поведения пешехода: “Если переходишь улицу (p), то сначала оглянись направо (q) и налево (r)”. Замена формулы, соответствующей этому утверждению потребует обращаться с выражением в скобках как с одной переменной и представляется согласно (6) и (7) в следующем виде:

Читайте также:  Как убрать диспетчер realtek hd

В результате получим заново восстановленные словесные высказывания, эквивалентные разбираемому правилу: “Или не переходи улицу, или сначала оглянись направо и налево”; “Hевеpно переходить улицу и при этом не признавать, что надо сначала оглянуться направо и налево”.

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

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

При формулировании законов логики высказываний вместо принятого в ней знака эквивалентности мы использовали знак равенства (=), то есть тот обычный знак равенства, который хорошо знаком каждому со школьных лет. Для нас здесь и в дальнейшем оба знака одинаковы. Обычный математический знак ставится тогда, когда мы не предполагаем применять к эквивалентности правила преобразования ее в другие логические союзы. Не желая прибегать к словесным выражениям, мы будем пользоваться таким символом, дабы подчеркнуть, что распространять на него законы логики высказываний можно только после замены их на принятые в ней знаки. Причем правомерность такой замены должна быть обоснована.

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

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

Тогда окончательно правило для преобразования строгой дизъюнкции в другие формулы может быть записано следующим образом:

Пояснить данный закон удобно и наглядно с помощью высказывания “Идет либо дождь, либо снег”. Так как выражено оно с помощью союза “либо”, то значит предполагается, что одновременно они не наблюдаются. Тогда значит надо согласиться с тем, что говорит высказывание, образованное из тех же переменных по полученной нами формуле (9): “Идет дождь или снег, но при этом или не идет дождь, или не идет снег”.

С помощью указанных законов и выражающих их формул возможно решение и обратной задачи — проверить равносильность высказываний, когда они составлены из одинаковых простых суждений. Попробуем, например, сопоставить известную поговорку (а) “Любопытство — не порок, но большое свинство” с таким утверждением (б): “Неверно, что если любопытство есть большое свинство, то тогда оно — порок”. Можно ли считать их одной и той же мыслью, только по-разному высказанной, или же они не совпадают? Для ответа надо записать оба высказывания символами:

(а) (б)

где p означает “Любопытство — порок”, а q — “Любопытство есть свинство”. Теперь осталось только преобразовать либо конъюнкцию в импликацию, либо, наоборот, импликацию в конъюнкцию и посмотреть, получается ли из одной формулы другая или нет. В данном случае проще импликацию превратить в конъюнкцию по формуле (7):

С учетом закона коммутативности конъюнкции получим:

Видно, что полученная формула в точности идентична той, через которую записано конъюнктивное высказывание: “Любопытство — не порок, но большое свинство”. Значит, одно получается из другого в результате преобразования и они, стало быть, эквивалентны.

Попробуем также сопоставить еще два выражения, одно из которых является библейским (а): «Нет власти не от бога» (не бывает, чтобы являлось властью и не было от бога). Другое (б), допустим, звучит так: «Или не власть, или не от бога». Одна это мысль или нет? Чтобы ответить на этот вопрос, надо сначала записать то и другое формулой, а затем привести оба выражения к одному знаку.

(а) (б)

Если мы для преобразования выберем первое выражение, которое является конъюнкцией, и его надо превратить в дизъюнкцию, то нам понадобится формула (2).

Отсюда видно, что записанное нами дизъюнктивное выражение вовсе не является равносильным первому. На деле, чтобы быть последовательным, надо первое переделывать в такое дизъюнктивное высказывание: «Или не власть, или от бога».

Для преобразования выражения с тремя переменными воспользуемся знакомыми каждому словами из арии о красавице и приписываемых ей склонностях. И запишем их в двух таких выражениях: (а) «Неправда, что или не красавица, или склонна к измене и к перемене»; (б) «Красавица, но неверно, будто склонна к измене и к перемене».

(а) (б)

Здесь, как и в предыдущих случаях с тремя переменными, не только одни и те же переменные, но и целая скобка одинаковая в обоих высказываниях. Разница в знаке между этой скобкой и другой переменной. Чтобы сравнить их на равносильность надо привести их к одному знаку именно в этом месте. Допустим, мы возьмемся преобразовывать выражение (а). Но поскольку между скобкой и одиночной переменной дизъюнкция, то выбирать нужную нам формулу, по которой будет происходить преобразование, надо среди (4) и (5). А раз в итоге нам требуется получить конъюнктивное выражение, то значит нужно взять (4).

Читайте также:  Лики войны что это

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

Попробуем, далее, выразить сами слова арии как импликацию: «Если красавица, то склонна к измене и к перемене» И теперь преобразуем, скажем, выражение (2) в импликативное по формуле (6).

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

Операция называется дизъюнкцией и обозначается символом «p/q» (иначе ее называют альтернацией, адъюнкцией, логическим сложением), или «р + q». Дизъюнкция выражается с помощью операций конъюнкции и отрицания.

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

(Союз «или» в таком случае применяется в значении допущения, если допускается правильность обоих высказываний). Например: «выпал дождь или полили парк». Поэтому такое соединение двух высказываний также называется дизъюнкцией. (Символ «V» читается также как «или»).

Операция конъюнкция выражается с помощью операций дизъюнкции.

Таким образом, руководствуясь теоремой, что каждая логическая операция может быть выражена с помощью только операций дизъюнкции и отрицания «ни-ни»

Операция «р влечёт q» и называется импликацией (с предварительным членом р и с последующим членом q).

Допустим, что если р = п, то значение выражения р влечёт q будет или п, или л в зависимости от того, является ли значение q п, или л. Это аналогично тому, что высказывание типа «если А, то В», в котором первый член А является правильным, считается или правильным, или ложным в зависимости от того, правильный или ложный второй его член В. Поэтому соединению типа «если А, то В» соответствует импликация в области логических значений. Но в то же время при ложном высказывании А предложение типа «если А, то В» может вообще не считаться высказыванием Например: если горит лампочка, то лифт работает.

Если высказывание «горит лампочка» правильно, то правильностью высказывания «лифт работает» однозначно решается правильность вышеприведенного предложения. Но если высказывание «горит лампочка» ложно, то ничего нельзя сказать о правильности вышеприведенного предложения. Можно сказать : надо подождать, пока лампочка загорится Приведем пример, в котором не будет даже возможности «подождать»:

Если 2 * 2 = 5, то Дунай является европейской рекой. Если принять то, что соединение типа «если . . .то» соответствует операции импликации, при соблюдении последнего тождества высказывание «если А, то В» выражалось бы с помощью операций конъюнкции и отрицания в следующем виде : «неправильно, что : А и не В» (здесь присутствует выражение «не В» вместо выражения «неправильно, что В»; таким образом, ясно, что выражение «неправильно, что», расположенное в начале высказывания, относится не только к Л, но и к выражению «А и не В»). В соответствии с этим приведенные выше два предложения в примере могут быть переформулированы следующим образом:

  • а) Неправильно, что горит лампочка и лифт не работает.
  • б) Неправильно, что 2 * 2 = 5 и Дунай не является европейской рекой. Если выражение «горит лампочка» ложно, то ложно и выражение «лампочка горит и лифт не работает», а отрицание его — по а) — является правильным. Выражение. «2 * 2 = 5» ложно, ложно также и выражение «Дунай не является европейской рекой»; их конъюнкция — также ложна, а отрицание этой конъюнкции — по б) — является правильным. Здесь нет противоречия по сравнению с обычным пониманием вещей, так как обычно не обращают внимание на правильность сложного предложения типа «если . . . то» в том случае, когда первый член соединения является ложным.

Выражения вида «если А, то В» можно считать синонимами выражений вида «неправильно, что: «А и не В»; они называются импликациями (с предварительным членом А, с последующим членом В); для их обозначения применяется символ А влечёт В.

Представленное в области логических значений понятие импликации типа р влечёт q соответствует понятию вышеприведенной операции высказывания.

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

Упоминаются еще некоторые грамматические синонимы операции «А влечёт В»: «В, если только Л», «Только тогда А, если В», «Достаточным условием В является А», «Необходимым условием А является В», «В если не А».

И конъюнкция и дизъюнкция выражаются с помощью операций импликации и отрицания.

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

Последний вид выражения операции эквивалентности.

Так как высказывание p эквивалентно q = n тогда и только тогда, когда p = q, то данная логическая операция соответствует образованию сложного предложения вида «А тогда и только тогда, когда В». Понимание и логическое значение предложения такого характера, образованного из двух любых высказываний, иногда затруднительно для восприятия человека, как и понимание предложения вида «если . . . то». Например, «2

Ссылка на основную публикацию
Шаблоны букв английского алфавита для вырезания
Трафареты и шаблоны букв английского алфавита для вырезания из бумаги, это разнообразные шрифты разного стиля и тематики. Трафареты помогут вам...
Что значит спящий режим компьютера
В операционной системе Windows есть несколько режимов выключения компьютера – это обыкновенный режим, (который полностью выключает PC), режим гибернации и...
Что значит сторнировать документ
Сто́рно (итал. storno — перевод на другой счёт, отвод; от stornare — поворачивать обратно) — в общем смысле возврат к...
Шаблоны для брошюры в ворде
Автор: admin Дата записи Быстрей всего набросать буклет, если под рукой окажется готовый шаблон. Проще всего создать буклет в программе...
Adblock detector