Игошин Математическая логика и теория алгоритмов (1019110), страница 5
Текст из файла (страница 5)
аонмонкциейдвух высказываний Р и Д называется новое высказывание, обозначаемое Р л Д или Р ес Ц (читается: «Р и Д»), которое истинно лишь в единственном случае, когда истинны оба исходных высказывания Р и Ц, и ложно во всех остальных случаях. Другими словами, логическое значение высказывания Р н Ц связано с логическими значениями высказываний Р и Д, как указано в следующей таблице, называемой таблицей истинности операции конъюнкции: !7 Практика полностью подтвердила, что именно такое распределение значений истинности наиболее соответствует тому смыслу, который придается в процессе мыслительной деятельности связующему союзу «и». Пример 1.4.
Применим операцию конъюнкции к высказываниям Аз и Аз. Получим высказывание Аз л А,: «Саратов находится на берегу Невы, и все люди смертны». Конечно, мы не воспринимаем это высказывание как истинное из-за первой, ложной, его части. К выводу о ложности полученного высказывания также придем, исходя из логических значений исходных высказываний Аз и Аз и определения !.3 конъюнкции на основании приведенной там таблицы.
В самом деле, ЦАз п Аз) = ЦА,) п 7(Аз) = О л 1 = О. Дизъюикция двух высказываний. Определение 1.5. Дизьюннцией двух высказываний Р и Ц называется новое высказывание, обозначаемое Р з~ Д (читается «Р или Д»), которое истинно в тех случаях, когда хотя бы одно из высказываний Р или Д истинно, и ложно в единственном случае, когда оба высказывания Р и Д ложны.
Другими словами„Р «Д — такое высказывание, логическое значение которого связано с логическими значениями исходных высказываний Р и Д так, как указано в следующей таблице, называемой таблицей истинности операции дизьюнкции: Пример 1.6. Применим операцию дизъюнкцию к высказываниям Аз и Аз. Получим составное высказывание Аз «А,: «Все люди смертны, или 7< 4». Несмотря на первоначально кажущуюся странность этого высказывания, нет сомнений в его истинности. К аналогичному заключению приводит также формальное вычисление логического значения данного высказывания по таблице из определения 1.5, исходя из логических значений высказываний Аз и Аз: ~(Аз '~ Аз) = ) (Аз)»' ЦАз) = 1 «О = 1.
В то же время высказывание 18 «Саратов находится на берегу Невы, или А. С. Пушкин — великий русский математик», являющееся дизъюнкцией высказываний А, и А,, безусловно, ложно, что полностью согласуется с формальным вычислением его логического значения по таблице из определения 1.5: Х(А, ~ А,) = Х(А2) «к(А,) = О ч О = О. Импликация двух высказываний. Определеиие 1.7. Импликациейдвух высказываний Р и Ц называется новое высказывание, обозначаемое Р— » Д (читается: «если Р, то Ц», или «из Р следует Ц», или «Р влечет Д», или «Р достаточно для Д», или «О необходимо для Р»), которое ложно в единственном случае, когда высказывание Р истинно, а Π— ложно, а во всех остальных случаях — истинно.
Другими словами, логическое значение высказывания Р-» Д связано с логическими значениями высказываний Р и Ц, как указано в следующей таблице, называемой таблицей истинности операции импликации: В высказывании Р— » Ц высказывание Р называется посылкой или антецедентом, а высказывание Π— следствием или консеквентом. При определении импликации с еще большей силой встает вопрос, почему именно такое распределение принято в ее таблице истинности.
Последние две строки в ней достаточно хорошо согласуются с нашим пониманием выражения «если..., то...». Их обоснованием могут служить следующие соображения. Импликация призвана отразить процесс рассуждения, умозаключения. Общая характеристика этого процесса следующая. Если мы исходим из истинной посылки и правильно (верно) рассуждаем, то мы приходим к истинному заключению (следствию, выводу). Другими словами, если мы исходили из истинной посылки и пришли к ложному выводу, значит, мы неверно рассуждали.
В импликации Р «Д имеется посылка Р, следствие Ц и процесс рассуждения — >. Процесс рассуждения как раз и моделируется результатом операции Р— > Ц. Приведенное соображение служит обоснованием результата 1 -+ О = О, а также результата 1 — » 1 = 1. Определенные сомнения возникают при оценке адекватности первых двух строк в таблице, определяющей импликацию. В первой строке при ложной посылке и ложном следствии импликация признается истинной. Следующие два примера добавляют аргументы в пользу такого определения логического значения импликации в этом случае. Рассмотрим такое высказывание: «Если число делится на 5, то и его квадрат делится на 5». Его истинность не 19 вызывает сомнения.
В частности, мы могли бы сказать: «Если 10 делится на 5, то 10з делится на 5» или «Если 11 делится на 5, то и 11з делится на 5». В первом из этих высказываний и посылка, и следствие истинны, во втором — и посылка, и следствие ложны. Тем не менее оба этих высказывания истинны. Для большей убедительности второе высказывание можно сформулировать в сослагательной форме: «Если бы ! 1 делилось на 5, то и !!' делилось бы на 5». Есть утверждения такого типа и в житейской речи, которые признаются вполне нормальными. Например, «Если ты можешь переплыть Черное море, то я — турецкий султан», В пользу второй строки таблицы, когда импликация остается истинной при ложной посылке и истинном следствии, говорит такой пример.
Высказывание «Если первое слагаемое делится на 5 и второе слагаемое делится на 5, то и сумма делится на 5», несомненно, истинно. Но, в частности, мы могли бы сказать: «Если 10 делится на 5 и 20 делится на 5, то 30 делится на 5» или «Если 12 делится на 5 и 13 делится на 5, то 25 делится на 5». В первом из этих высказываний и посылка истинна (как конъюнкция двух истинных выражений), и следствие истинно.
Во втором же высказывании посылка ложна (как конъюнкция двух ложных высказываний), а следствие истинно. Тем не менее, как мы уже отметили, оба этих высказывания признаются истинными. Пример 1.8. Высказывание Аь -+ Ар «Если Волга впадает в Каспийское море, то 7 < 4» ложно, так как Х(Аь -» А,) = ЦАь) — » — » Х(А5) = 1 -» 0 = О. Высказывание «Если Саратов находится на берегу Невы, то А.С.Пушкин — великий русский математик», являющееся импликацией высказываний Аз и А„истинно, так как Х(Аг -+ А,) = Х(Аз) » Х(А,) = 0 -» 0 = 1. Эквивалентность двух высказываний.
Определение 1.9. Эквивалентностью двух высказываний Р и 0 называется новое высказывание, обозначаемое Р <-» Д (читается: «Р эквивалентно Д», или «Р необходимо и достаточно для 0», или «Р тогда и только тогда, когда Д», или «Р, если и только если 0»), которое истинно в том и только в том случае, когда одновременно оба высказывания Ри а либо истинны, либо ложны, а во всех остальных случаях — ложно.
Другими словами, логическое значение высказывания Р»» Д связачо с логическими значениями высказываний Р и Д, как указано в следующей таблице, называемой таблицей истинности операции эквивалентности: 20 Пример 1.10. Высказывание «7 < 4 тогда и только тогда, когда снег белый», являющееся эквивалентностью высказываний А, и А,, ложно, так как ).(А5 с-э А8) = ».(А5) <-+ ) (А8) = О <-> ! = О. Напротив, высказывание «Саратов находится на берегу Невы, если и только если А.
С. Пушкин — великий русский математик» истинно, так как оно является эквивалентностью двух ложных высказываний. Союзы языка и логические операции (язык и логика). Итак, каждая из введенных логических операций является неким математическим образом, моделью соответствующего логического союза нашего языка. Эти понятия призваны отразить на языке нулей и единиц соответствующие союзы нашего мышления, которыми человечество пользуется в течение тысячелетий.
Вне всякого сомнения, язык нулей и единиц значительно беднее человеческого языка, и это отражение достаточно грубо и несовершенно. Тем не менее какие-то основные черты (существенные аспекты процессов мышления) понятия логических операций все же отражают. Так, отрицание, конъюнкция и эквивалентность достаточно точно передают суть логических союзов «не», «и», «тогда и только тогда, когда» соответственно.
Хуже обстоит дело с дизъюнкцией, призванной отразить языковый союз «или». Следует отметить, что кроме рассматриваемой так называемой дизаюнкции в не исключающем смысле (она истинна тогда и только тогда, когда по меньшей мере один ее член истинен) некоторые авторы рассматривают дизъюнкцию в исключающем смысле (или строгую дизъюнкцию): она истинна тогда и только тогда, когда истинен точно один ее член.
Наименее адекватным соответствующему союзу языка является понятие импликации, которое призвано отразить логический союз «если..., то...». Это и понятно: на этом союзе основан один из сложнейших умственных процессов — процесс построения выводов, умозаключений. Импликация остается все же самой «коварной» из всех логических операций, и ее определение при всех приведенных доводах оставляет в нас чувство незавершенности. И это неспроста. Наиболее наглядно эта неадекватность определения языку проявится в ходе развития алгебры высказываний, когда мы, например, придем к тому, что тавтологией окажется следующая формула: (Р— г О) ч (О-~ Р).
Это означает, что какие бы ни были высказывания Р и Д, по меньшей мере одно из высказываний Р » О или 0 — ~ Р непременно будет истинным. Этот факт уже не согласуется с общепринятой практикой, и он еще раз подтверждает, что понятие импликации лишь весьма условно и приблизительно переводит на язык нулей и единиц тот смысл, который имеется в виду при построении фразы типа «если..., то...». Из приведенного следует вывод о том, что тонкое и многообРазное человеческое мышление не так легко поддается научному 2! осмыслению и изучению и что алгебра высказываний — всего лишь одно из приближений, всего лишь шаг на пути к познанию человеческого мышления.
По поводу происхождениия терминов отметим, что «конъюнкция» происходит от лат. соп~ипсйр — соединение, дизъюнкция— от лат. Йку'ипсйв — разъединение, импликация от лат. олрйсаИо— сплетение и плрйсо — тесно связываю. Общий взгляд иа логические операции. Еще раз отметим, что только логические значения или значения истинности, а не их содержание интересуют нас в развиваемой теории. Поэтому каждое из введенных определений (1.1, 1.3, 1.5, 1.7, 1.9) операций над высказываниями можно рассматривать как определение некоторого действия над символами О и 1, т.е. как определение некоторой операции на двухэлементном множестве (О, и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
