Страница:
Математическая логика учит логично рассуждать не больше, чем любой другой раздел математики. Это связано с тем, что «логичность» рассуждений в логике определяется самой логикой и корректно может использоваться только в самой логике. В жизни же мы, размышляя логически, как правило используем разные логики и разные методы логических рассуждений, безбожно перемешивая дедукцию с индукцией… Более того, в жизни мы строим свои рассуждения исходя из противоречивых посылок, например, «Не откладывай на завтра, что можно сделать сегодня» и «Поспешишь людей насмешишь». Нередко бывает, что непонравившийся нам логический вывод приводит к пересмотру исходных посылок (аксиом).
Пожалуй, настало время сказать про логику, возможно, самое главное: классическая логика не занимается смыслом. Ни здравым, ни каким другим! Для изучения здравого смысла, между прочим, существует психиатрия. Но в психиатрии логика скорее вредна. Хотя, например, так называемые репертуарные решетки и говорят о некоторых успехах в этом направлении…
Разумеется, размежевывая логику со смыслом, имеем в виду прежде всего классическую логику и житейское понимание здравого смысла. Нет запретных направлений в математике, поэтому исследование логикой смысла, и наоборот, в различных видах присутствует в ряде современных ответвлений логической науки. (Хорошо сложилось последнее предложение, хотя определить термин «логическая наука» не возьмусь даже приблизительно).
Смыслом, если угодно – семантикой, занимается, например, теория моделей. Да и вообще, термин семантика часто заменяют термином интерпретация. И если мы согласимся с философами, что интерпретация (отображение!) об'екта есть осмысление его в некотором данном аспекте, то пограничные сферы математики, которые могут привлекаться для наступления на смысл в логике, становятся неохватными!
В практическом плане семантикой вынуждено интересоваться теоретическое программирование. А в нем, кроме просто семантики, есть и операционная, и денотационная, и процедуральная и т.д. и т.п. семантики…
Еще лишь упомянем апофеоз – ТЕОРИЮ КАТЕГОРИЙ, которая довела семантику до формального малопонятного синтаксиса, где смысл уже настолько простой – разложенный по полочкам, что до него простому смертному совсем невозможно докопаться… Это для избранных.
Так чем же занимается логика? Хотя бы в самой классической ее части? Логика занимается только тем, чем она занимается. (А это она определяет предельно строго). Главное в логике – это строго определиться! Задать аксиоматику. А дальше логические выводы должны быть( !) в значительной степени автоматическими… Другое дело рассуждения по поводу этих выводов! Но эти рассуждения уже вне рамок логики! Поэтому в них требуется строгий математический смысл!
Может показаться, что это простая словесная эквилибристика. НЕТ! В качестве примера некоторой логической (аксиоматической) системы возьмем известную игру 15. Зададим (перемешаем) начальное расположение квадратных фишек. Далее игрой (логическим выводом!), а конкретно – перемещением фишек на свободное место, может заниматься некое механическое устройство, а вы можете терпеливо смотреть и радоваться, когда в результате возможных передвижек в коробочке сложится последовательность от 1 до 15. Но никто не запрещает контролировать механическое устройство и подсказывать ему, ИСХОДЯ ИЗ здравого СМЫСЛАправильные перемещения фишек, чтобы ускорить процесс. А может быть даже доказать, используя для логических рассуждений, например, такой раздел математики, как КОМБИНАТОРИКА, что при данном начальном расположении фишек получить требуемую финальную комбинацию невозможно вообще!
Не больше здравого смысла присутствует и в той части логики, которую называют ЛОГИЧЕСКОЙ АЛГЕБРОЙ. Здесь вводятся ЛОГИЧЕСКИЕ ОПЕРАЦИИи определяются их свойства. Как показала практика, в некоторых случаях законы этой алгебры могут соответствовать логике жизни, а в некоторых нет. Из за такого непостоянства законы логики нельзя считать законами с точки зрения практики жизни. Их знание и механическое использование может не только помогать, но и вредить. Особенно психологам и юристам. Ситуация осложняется тем, что наряду с законами алгебры логики, которые то соответствуют, то не соответствуют жизненным рассуждениям, есть логические законы, которые часть логиков категорически не признают. Это относится прежде всего к так называемым законам ИСКЛЮЧЕННОГО ТРЕТЬЕГОи ПРОТИВОРЕЧИЯ. Более подробно о них поговорим потом.
Лекция 7. ОПЕРАЦИИ НАД ВЫСКАЗЫВАНИЯМИ
Обычно математическую логику начинают изучать с
АЛГЕБРЫ ВЫСКАЗЫВАНИЙи вспоминают при этом Дж. Буля, отца Лилиан Войнич, написавшей роман «Овод». А сам Буль, как незакомлексованный математической эрудицией любитель, пытался придумать математику, которая бы описывала мыслительные процессы. Собственно, с его «алгебры» и ведут историю современной математической логики.
Кстати, многие математики эту алгебру не считают логикой.
Под ВЫСКАЗЫВАНИЕМпонимают повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Например, «Волга впадает в Каспийское море», «Квадрат гипотенузы равен сумме квадратов катетов», «Наполеон родился в Кудымкаре». Здесь два первых высказывания истинны, а третье – ложно. Разумеется, жизнь и тут иногда создает проблемы. Так, про высказывание насчет Волги можно сказать, что оно истинное, если ЗНАТЬэтот факт из географии. Мне, например, пришлось как-то в Америке рассказывать одному бизнесмену, что далеко от США есть такая большая река – Волга… Да и про квадрат гипотенузы не все могут высказаться определенно… Но договоримся, недоучек не принимать в расчет. Или еще проще, чтобы не утонуть в несущественных для данного обсуждения мелочах, будем считать высказываниями повествовательные предложения, истинность которых может установить «высший разум».
Но этим проблема не исчерпывается. Повествовательное предложение «Я лгу» не является высказыванием, поскольку если оно истинно (то есть я действительно лгу) – значит я не лгу, а говорю правду! И наоборот… Это пример ЛОГИЧЕСКОГО ПАРАДОКСА.
Логические парадоксы не относятся к высказываниям. К высказываниям не относятся также вопросительные и восклицательные (т.е. неповествовательные) предложения и определения. Говорить об истинности или ложности определений бессмысленно. Определение есть соглашение о названии. Например, «Назовем эту музыку гимном». И все тут!…
Для того, чтобы не писать " истина" и " ложь" (" true" и " false") часто используют лишь начальные буквы этих слов. А еще чаще просто " 1" и " 0".
А теперь вернемся к самому существенному. Логика высказываний не занимается (и даже не интересуется) СМЫСЛОМвысказываний. Так что в этом смысле логику можно считать БЕССМЫСЛИЦЕЙ! Один из логиков-классиков уподобил алгебру логики рентгену, который, просвечивая высказывание, оставляет математику для рассмотрения только его истинность.
В алгебре высказываний можно обойтись двумя-тремя операциями, хотя обычно рассматривают больше. Операцию ДИЗ'ЮНКЦИЯназывают еще " логическим или". Если два высказывания соединить диз'юнкцией, то получится сложное высказывание которое истинно, если истинно хотя бы одно из входящих в него высказываний. То есть следует уточнить, что это " неисключающее или". Например, «Мы любим пиво или мы любим мороженое» истинное сложное высказывание, поскольку хотя бы одно из входящих в него элементарных высказываний истинно. А возможно, и оба. Представить же себе живое существо, которое не любит и пиво, и мороженое, не позволяет фантазия.
Операцию КОН'ЮНКЦИЯназывают еще " логическим и". Сложное высказывание будет истинно, если истинны оба входящих в него высказывания.
Операция ОТРИЦАНИЕ– " логическое не" – истинное высказывание превращает в ложное и наоборот.
Пожалуй, самая интригующая операция – это ИМПЛИКАЦИЯили " логическое если…, то". Например, «Если Наполеон родился в Кудымкаре, то газ при нагревании сужается». Это, кстати, истинное высказывание! Нет причин считать его ложным. Единственная ситуация, когда импликация ложна, это когда посылка (часть «если») истинна, а следствие (часть «то») ложна.
Еще интереснее с точки зрения здравого смысла то, что импликацию иногда (не совсем корректно по иным причинам!) называют операцией логического следования, хотя наш пример показывает, что высказывания могут логически не следовать одно из другого, более того, могут не иметь между собой никакой логической связи. Напомним, импликация, как и другие операции, берет в расчет только истинность входящих в нее высказываний.
«Если Волга впадает в Каспийское море, то 2 + 2 = 4» истинное высказывание.
«Если Волга впадает в Каспийское море, то 2 + 2 = 5» ложное высказывание.
Хотя оба эти «логические рассуждения» с точки зрения здравого рассуждения одинаково бессмысленны.
Есть также ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬили " тогда и только тогда« (кстати, воспользовавшись»американским приемом", можно записать короче – " ттогда"). Результирующее сложное высказывание истинно, если одновременно истинны или ложны оба входящих в него высказывания.
Назовем еще одну операцию, ШТРИХ ШЕФФЕРАили логическое " и-не". Результат этой операции равносилен последовательному применению операций кон'юнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны. Штрих Шеффера – это операция замечательная тем, что ее одной (необходимое количество раз примененной) достаточно, чтобы записать любое сложное высказывание.
При использовании логики для проектирования логических схем, например отдельных фрагментов процессора, первоначально эксплуатировали аналогию с релейными схемами. Операция диз'юнкции(" или") соответствует параллельному подключению контактов реле, кон'юнкции(" и") – последовательному. Операция отрицания(" не") моделируется нормально замкнутым контактом реле. То есть контакт размыкается при срабатывании реле. Разумеется, все это реализовывалось в полупроводниковом «модульном» варианте. Тогда достаточно было выпустить, например, модули типа «и-не», чтобы на них реализовать любую схему. (А сам процессор был размером со шкаф, но не по вине логики).
Кстати, многие математики эту алгебру не считают логикой.
Под ВЫСКАЗЫВАНИЕМпонимают повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Например, «Волга впадает в Каспийское море», «Квадрат гипотенузы равен сумме квадратов катетов», «Наполеон родился в Кудымкаре». Здесь два первых высказывания истинны, а третье – ложно. Разумеется, жизнь и тут иногда создает проблемы. Так, про высказывание насчет Волги можно сказать, что оно истинное, если ЗНАТЬэтот факт из географии. Мне, например, пришлось как-то в Америке рассказывать одному бизнесмену, что далеко от США есть такая большая река – Волга… Да и про квадрат гипотенузы не все могут высказаться определенно… Но договоримся, недоучек не принимать в расчет. Или еще проще, чтобы не утонуть в несущественных для данного обсуждения мелочах, будем считать высказываниями повествовательные предложения, истинность которых может установить «высший разум».
Но этим проблема не исчерпывается. Повествовательное предложение «Я лгу» не является высказыванием, поскольку если оно истинно (то есть я действительно лгу) – значит я не лгу, а говорю правду! И наоборот… Это пример ЛОГИЧЕСКОГО ПАРАДОКСА.
Логические парадоксы не относятся к высказываниям. К высказываниям не относятся также вопросительные и восклицательные (т.е. неповествовательные) предложения и определения. Говорить об истинности или ложности определений бессмысленно. Определение есть соглашение о названии. Например, «Назовем эту музыку гимном». И все тут!…
Для того, чтобы не писать " истина" и " ложь" (" true" и " false") часто используют лишь начальные буквы этих слов. А еще чаще просто " 1" и " 0".
А теперь вернемся к самому существенному. Логика высказываний не занимается (и даже не интересуется) СМЫСЛОМвысказываний. Так что в этом смысле логику можно считать БЕССМЫСЛИЦЕЙ! Один из логиков-классиков уподобил алгебру логики рентгену, который, просвечивая высказывание, оставляет математику для рассмотрения только его истинность.
В алгебре высказываний можно обойтись двумя-тремя операциями, хотя обычно рассматривают больше. Операцию ДИЗ'ЮНКЦИЯназывают еще " логическим или". Если два высказывания соединить диз'юнкцией, то получится сложное высказывание которое истинно, если истинно хотя бы одно из входящих в него высказываний. То есть следует уточнить, что это " неисключающее или". Например, «Мы любим пиво или мы любим мороженое» истинное сложное высказывание, поскольку хотя бы одно из входящих в него элементарных высказываний истинно. А возможно, и оба. Представить же себе живое существо, которое не любит и пиво, и мороженое, не позволяет фантазия.
Операцию КОН'ЮНКЦИЯназывают еще " логическим и". Сложное высказывание будет истинно, если истинны оба входящих в него высказывания.
Операция ОТРИЦАНИЕ– " логическое не" – истинное высказывание превращает в ложное и наоборот.
Пожалуй, самая интригующая операция – это ИМПЛИКАЦИЯили " логическое если…, то". Например, «Если Наполеон родился в Кудымкаре, то газ при нагревании сужается». Это, кстати, истинное высказывание! Нет причин считать его ложным. Единственная ситуация, когда импликация ложна, это когда посылка (часть «если») истинна, а следствие (часть «то») ложна.
Еще интереснее с точки зрения здравого смысла то, что импликацию иногда (не совсем корректно по иным причинам!) называют операцией логического следования, хотя наш пример показывает, что высказывания могут логически не следовать одно из другого, более того, могут не иметь между собой никакой логической связи. Напомним, импликация, как и другие операции, берет в расчет только истинность входящих в нее высказываний.
«Если Волга впадает в Каспийское море, то 2 + 2 = 4» истинное высказывание.
«Если Волга впадает в Каспийское море, то 2 + 2 = 5» ложное высказывание.
Хотя оба эти «логические рассуждения» с точки зрения здравого рассуждения одинаково бессмысленны.
Есть также ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬили " тогда и только тогда« (кстати, воспользовавшись»американским приемом", можно записать короче – " ттогда"). Результирующее сложное высказывание истинно, если одновременно истинны или ложны оба входящих в него высказывания.
Назовем еще одну операцию, ШТРИХ ШЕФФЕРАили логическое " и-не". Результат этой операции равносилен последовательному применению операций кон'юнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны. Штрих Шеффера – это операция замечательная тем, что ее одной (необходимое количество раз примененной) достаточно, чтобы записать любое сложное высказывание.
При использовании логики для проектирования логических схем, например отдельных фрагментов процессора, первоначально эксплуатировали аналогию с релейными схемами. Операция диз'юнкции(" или") соответствует параллельному подключению контактов реле, кон'юнкции(" и") – последовательному. Операция отрицания(" не") моделируется нормально замкнутым контактом реле. То есть контакт размыкается при срабатывании реле. Разумеется, все это реализовывалось в полупроводниковом «модульном» варианте. Тогда достаточно было выпустить, например, модули типа «и-не», чтобы на них реализовать любую схему. (А сам процессор был размером со шкаф, но не по вине логики).
Лекция 8. АЛГЕБРА ВЫСКАЗЫВАНИЙ
В этой алгебре об'ектами служат высказывания, о которых мы уже поговорили. Операции над высказываниями также обсудили. Осталось поговорить об их свойствах или законах, чтобы определится наконец с алгеброй.
Если использовать только три первых логических операции: диз'юнкцию, кон'юнкцию и отрицание, то алгебра высказываний аналогична алгебре множеств. Аналог диз'юнкции – об'единение, кон'юнкции – пересечение, а отрицания – дополнение. Эти аналогии можно использовать для одного из возможных об'яснений смысла логических операций (это, так называемая, теоретико-множественная интерпретация – и она достаточно «естественна»). Но мы ограничимся формальным подходом. А в связи с этим напомним, что нами были названы еще импликация, эквивалентность и штрих Шеффера, аналогов которым в теории множеств мы не стали искать.
Однако эти операции можно выразить через первые три.
Импликацию можно представить иначе, если взять диз'юнкцию отрицания первого высказывания со вторым. То есть с точки зрения формальной логики равносильны высказывания:
" ЕСЛИстоит хорошая погода, ТОмы купаемся" и
" НЕВЕРНО, что стоит хорошая погода, ИЛИмы купаемся".
Единственный случай, когда оба сложных высказывания ложны, это когда первое высказывание истинно, а второе ложно, то есть когда погода стоит хорошая, а мы не купаемся.
Для эквивалентности замена более длинная, но, фактически, совпадающая с определением. Например, высказывание (пусть и несколько диковатое):
"Хорошая погода стоит ТОГДА И ТОЛЬКО ТОГДА, КОГДАмы купаемся" эквивалентно высказыванию "Хорошая погода Имы купаемся ИЛИ НЕхорошая погода Имы НЕкупаемся".
Кстати, эквивалентность можно было выразить и через кон'юнкцию двух импликаций:
" ЕСЛИстоит хорошая погода, ТОмы купаемся И ЕСЛИмы купаемся, ТОстоит хорошая погода".
Штрих Шеффера для этих же исходных высказываний мог бы выглядеть следующим образом:
" НЕ ВЕРНО, что стоит хорошая погода Имы купаемся" или (по так называемому закону Де Моргана) это равносильно высказыванию:
" НЕхорошая погода ИЛИмы НЕкупаемся".
В алгебре высказываний есть законы: коммутативный, ассоциативный и дистрибутивный, которые аналогичны законам для множеств.
Чтобы убить двух зайцев, для иллюстрации коммутативного закона воспользуемся примером из книги Клини «Математическая логика»: "Мэри вышла замуж Иродила ребенка" равносильно с точки зрения логики тому что "Мэри родила ребенка Ивышла замуж". Первый «заяц» связан c синтаксисом коммутативного закона – то есть можно переставлять местами высказывания, а второй «заяц» – с семантикой, при которой перестановка не соответствует общепринятой морали – для приличного общества существенно, какое событие стоит первым. (Это в очередной раз говорит о том, что математическая логика не учитывает [и не в состоянии это сделать!] многих нюансов, имеющих место в практике жизни).
Ассоциативный законутверждает, что безразлично, в каком порядке мы рассматриваем (истинность) попарных кон'юнкций и диз'юнкций:
"Стоит хорошая погода Имы купаемся Изаработали ангину".
"Стоит хорошая погода ИЛИмы купаемся ИЛИзаработали ангину".
Поскольку очередность выполнения операций в математике часто задают скобками, то ассоциативный закон еще называют законом снятия скобок.
Дистрибутивный закон.
Приведем пример только для «экзотического» случая.
"Стоит хорошая погода ИЛИмы купаемся Изаработали ангину" равносильно высказыванию
"Стоит хорошая погода Имы купаемся ИЛИстоит хорошая погода Изаработали ангину"
Не будем перечислять все возможные законы логики высказываний. Как уже было сказано, они аналогичны законам алгебры множеств. Но важно заметить, что здесь мы вместо слова «равенство» употребляли слово «равносильность». Два сложных высказывания являются равносильными, если они имеют одинаковые ТАБЛИЦЫ ИСТИННОСТИ. В этих таблицах начальные столбцы соответствуют исходным (элементарным) высказываниям, а последний результирующему (сложному) высказыванию. В начальных столбцах проставляются все возможные комбинации истинности элементарных высказываний, а в последнем истинность сложного высказывания.
Для каждой комбинации отдельная строка.
Для последнего примера таблицы будут одинаковыми для левой и правой части дистрибутивного закона:
хорошая погода | мы купаемся | заработали ангину | РЕЗУЛЬТАТ
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1
Касательно математической логики, как и множеств, есть люди, несогласные с рядом ее законов. Прежде всего это опять законы исключенного третьего и противоречия. То есть заполнение очевидных таблиц истинности для конструктивистов (интуиционистов) неочевидно!
Конструктивисты относительно сложного высказывания "Теорема Ферма верна ИЛИтеорема Ферма НЕверна" говорят, что это сложное высказывание не может быть истинным хотя бы потому, что признав его истинность мы окончательно делаем неразрешимым вопрос «Так верна она или нет?!». Более человеколюбивые логики в качестве аргумента приводят сложные высказывания типа: "Человек почти лысый ИЛИ НЕ ВЕРНО, что человек почти лысый". Утверждают, что определить истинность этого сложного высказывания не только невозможно, но и просто бестактно.
Логика высказываний, и алгебра высказываний в частности, как уже ранее говорилось, бурно расцветали на заре вычислительной техники. Одно из важнейших алгебраических преобразований – это минимизация сложных высказываний. То есть было создано множество методик получения из исходного высказывания равносильного, но имеющего наименьшее возможное число логических операций. А в соответствии с таким высказыванием можно построить и максимально простое техническое устройство. И всем заинтересованным лицам будет хорошо и выгодно от результатов, полученных с помощью науки.
Если использовать только три первых логических операции: диз'юнкцию, кон'юнкцию и отрицание, то алгебра высказываний аналогична алгебре множеств. Аналог диз'юнкции – об'единение, кон'юнкции – пересечение, а отрицания – дополнение. Эти аналогии можно использовать для одного из возможных об'яснений смысла логических операций (это, так называемая, теоретико-множественная интерпретация – и она достаточно «естественна»). Но мы ограничимся формальным подходом. А в связи с этим напомним, что нами были названы еще импликация, эквивалентность и штрих Шеффера, аналогов которым в теории множеств мы не стали искать.
Однако эти операции можно выразить через первые три.
Импликацию можно представить иначе, если взять диз'юнкцию отрицания первого высказывания со вторым. То есть с точки зрения формальной логики равносильны высказывания:
" ЕСЛИстоит хорошая погода, ТОмы купаемся" и
" НЕВЕРНО, что стоит хорошая погода, ИЛИмы купаемся".
Единственный случай, когда оба сложных высказывания ложны, это когда первое высказывание истинно, а второе ложно, то есть когда погода стоит хорошая, а мы не купаемся.
Для эквивалентности замена более длинная, но, фактически, совпадающая с определением. Например, высказывание (пусть и несколько диковатое):
"Хорошая погода стоит ТОГДА И ТОЛЬКО ТОГДА, КОГДАмы купаемся" эквивалентно высказыванию "Хорошая погода Имы купаемся ИЛИ НЕхорошая погода Имы НЕкупаемся".
Кстати, эквивалентность можно было выразить и через кон'юнкцию двух импликаций:
" ЕСЛИстоит хорошая погода, ТОмы купаемся И ЕСЛИмы купаемся, ТОстоит хорошая погода".
Штрих Шеффера для этих же исходных высказываний мог бы выглядеть следующим образом:
" НЕ ВЕРНО, что стоит хорошая погода Имы купаемся" или (по так называемому закону Де Моргана) это равносильно высказыванию:
" НЕхорошая погода ИЛИмы НЕкупаемся".
В алгебре высказываний есть законы: коммутативный, ассоциативный и дистрибутивный, которые аналогичны законам для множеств.
Чтобы убить двух зайцев, для иллюстрации коммутативного закона воспользуемся примером из книги Клини «Математическая логика»: "Мэри вышла замуж Иродила ребенка" равносильно с точки зрения логики тому что "Мэри родила ребенка Ивышла замуж". Первый «заяц» связан c синтаксисом коммутативного закона – то есть можно переставлять местами высказывания, а второй «заяц» – с семантикой, при которой перестановка не соответствует общепринятой морали – для приличного общества существенно, какое событие стоит первым. (Это в очередной раз говорит о том, что математическая логика не учитывает [и не в состоянии это сделать!] многих нюансов, имеющих место в практике жизни).
Ассоциативный законутверждает, что безразлично, в каком порядке мы рассматриваем (истинность) попарных кон'юнкций и диз'юнкций:
"Стоит хорошая погода Имы купаемся Изаработали ангину".
"Стоит хорошая погода ИЛИмы купаемся ИЛИзаработали ангину".
Поскольку очередность выполнения операций в математике часто задают скобками, то ассоциативный закон еще называют законом снятия скобок.
Дистрибутивный закон.
Приведем пример только для «экзотического» случая.
"Стоит хорошая погода ИЛИмы купаемся Изаработали ангину" равносильно высказыванию
"Стоит хорошая погода Имы купаемся ИЛИстоит хорошая погода Изаработали ангину"
Не будем перечислять все возможные законы логики высказываний. Как уже было сказано, они аналогичны законам алгебры множеств. Но важно заметить, что здесь мы вместо слова «равенство» употребляли слово «равносильность». Два сложных высказывания являются равносильными, если они имеют одинаковые ТАБЛИЦЫ ИСТИННОСТИ. В этих таблицах начальные столбцы соответствуют исходным (элементарным) высказываниям, а последний результирующему (сложному) высказыванию. В начальных столбцах проставляются все возможные комбинации истинности элементарных высказываний, а в последнем истинность сложного высказывания.
Для каждой комбинации отдельная строка.
Для последнего примера таблицы будут одинаковыми для левой и правой части дистрибутивного закона:
хорошая погода | мы купаемся | заработали ангину | РЕЗУЛЬТАТ
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1
Касательно математической логики, как и множеств, есть люди, несогласные с рядом ее законов. Прежде всего это опять законы исключенного третьего и противоречия. То есть заполнение очевидных таблиц истинности для конструктивистов (интуиционистов) неочевидно!
Конструктивисты относительно сложного высказывания "Теорема Ферма верна ИЛИтеорема Ферма НЕверна" говорят, что это сложное высказывание не может быть истинным хотя бы потому, что признав его истинность мы окончательно делаем неразрешимым вопрос «Так верна она или нет?!». Более человеколюбивые логики в качестве аргумента приводят сложные высказывания типа: "Человек почти лысый ИЛИ НЕ ВЕРНО, что человек почти лысый". Утверждают, что определить истинность этого сложного высказывания не только невозможно, но и просто бестактно.
Логика высказываний, и алгебра высказываний в частности, как уже ранее говорилось, бурно расцветали на заре вычислительной техники. Одно из важнейших алгебраических преобразований – это минимизация сложных высказываний. То есть было создано множество методик получения из исходного высказывания равносильного, но имеющего наименьшее возможное число логических операций. А в соответствии с таким высказыванием можно построить и максимально простое техническое устройство. И всем заинтересованным лицам будет хорошо и выгодно от результатов, полученных с помощью науки.
Лекция 9. ЛОГИКА ПРЕДИКАТОВ
«Предикат» с английского переводится как сказуемое. Но говорить «логика сказуемых» – себя не уважать. Формально предикатом называется функция, аргументами которой могут быть
ПРОИЗВОЛЬНЫЕ ОБ'ЕКТЫиз некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывания.
Пример. Вместо трех высказываний
«Маша любит кашу»
«Даша любит кашу»
«Саша любит кашу» можно написать один предикат
«Икс любит кашу» и договориться, что вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша.
Подстановка вместо Икс имени конкретного ребенка превращает предикат в обычное высказывание.
Для предикатов справедливы, и имеют тот же смысл, ранее рассмотренные логические операции. Например,
" ЕСЛИМаша любит кашу, ТОСаша любит кашу".
Но есть и две новые операции, специфические. Они называются несколько вызывающе – операциями НАВЕШИВАНИЯ КВАНТОРОВ. Эти операции соответствуют фразам «для всех» – квантор общности и «некоторые» – квантор существования. Мы договорились не писать формул, но все-таки следует сказать о значках, которые здесь используются, в силу их экзотичности. Квантор общности произошел от английского Allи обозначается буквой A, перевернутой вверх ногами. Квантор существования произошел от английского Existи обозначается буквой E, которую вверх ногами переворачивать бесполезно, поэтому ее повернули кругом.
Наш предикат, после навешивания каждого из кванторов, также превращается в высказывание, которое может быть истинно или ложно!
" ВСЕлюбят кашу"
" НЕКОТОРЫЕлюбят кашу"
Это, кстати, был (до навешивания кванторов) одноместный предикат (одноместная функция). Но предикаты могут быть не только одноместные. Это просто проиллюстрировать, если представить, что дети могут любить не только кашу… «Икс любит Игрека» – двухместный предикат. " ВСЕлюбят Игрека" – одноместный предикат. " ВСЕлюбят КОЙ-КОГО[некоторого]" – нульместный предикат, то есть высказывание.
Интересно посмотреть, как ведут себя кванторы в присутствии операции отрицания. Возьмем отрицание предиката " ВСЕлюбят кашу": " НЕ ВЕРНО, что ВСЕлюбят кашу". Это равносильно (по закону Де Моргана!) заявлению: " НЕКОТОРЫЕ НЕлюбят кашу. То есть отрицание"задвинули" за квантор, в результате чего квантор сменился на противоположный.
А теперь сделаем одно из самых важных заявлений:
ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ – САМЫЙ БЛИЗКИЙ К ЕСТЕСТВЕННОМУ. Поэтому работы по искусственному интеллекту тяготеют к использованию этого языка. В сравнении с естественным, это очень во многих смыслах ограниченный язык. Но лучшего за 100 лет не придумано, если не считать так называемого «синтаксического сахара», когда вместо соответствующей символики используются, например, слова естественного языка. (Вроде того, как мы пытаемся это делать).
В хорошо формализованных системах даже наоборот, дополнительно ограничивают этот язык для удобной реализации на компьютерах. Примером тому язык (логического) программирования
ПРОЛОГ – ПРОграммирование на ЛОГике.
Так вот, язык предикатов наследует пороки языка логики высказываний, которые обуславливают изначальное несоответствие естественного и логического языков.
На языке предикатов можно описать далеко не все, хотя и многое. Но даже в этом ограниченном пространстве подчас приходится применять хитрости и уловки, которые бы больше пристали ремеслу или искусству. Хотя об'яснения, в конце концов, обычно бывают строго формальные.
Вот некоторые «классические примеры».
Если мы желаем сказать на языке предикатов «Все студенты отличники», то рекомендуется конструкция
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс студент, ТОикс отличник"
Но если хотим сказать «Некоторые студенты отличники», то это следует записать
" ДЛЯ НЕКОТОРЫХиксов справедливо: икс студент И икс отличник" Конструкция ЕСЛИ…, ТОв данном случае не подходит. И вот почему: стоит затесаться в компанию одному иксу-нестуденту и он сделает этот предикат истинным, даже если там нет ни одного отличника!
И еще высказывание «Собакам и кошкам вход воспрещен».
Конструкция
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс – собака Иикс – кошка, ТОиксу вход запрещен"
Ясно что таких иксов, которые бы были одновременно собакой и кошкой не существует! Как, впрочем, и таких игреков. Поэтому
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс – собака ИЛИикс – кошка, ТОиксу вход запрещен"
И список таких фокусов-выкрутасов можно продолжать долго. До бесконечности. Но, главное, во-время остановиться и понять, что если бы даже придумать другую логику, в которой не было бы этих проблем, то получится логика, в которой будут другие проблемы, скорее всего существенно большие. А мы даже не трогали таких заморочек, присущих естественным языкам, как синонимы, омонимы, метафоры, гиперболы и т.д и т.п. Одни идиомы, кто знает, чего стоят!… Так что «братания» языка логики с естественным языком не предвидится и в самой отдаленной перспективе, даже когда планета Земля начнет остывать…
Пример. Вместо трех высказываний
«Маша любит кашу»
«Даша любит кашу»
«Саша любит кашу» можно написать один предикат
«Икс любит кашу» и договориться, что вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша.
Подстановка вместо Икс имени конкретного ребенка превращает предикат в обычное высказывание.
Для предикатов справедливы, и имеют тот же смысл, ранее рассмотренные логические операции. Например,
" ЕСЛИМаша любит кашу, ТОСаша любит кашу".
Но есть и две новые операции, специфические. Они называются несколько вызывающе – операциями НАВЕШИВАНИЯ КВАНТОРОВ. Эти операции соответствуют фразам «для всех» – квантор общности и «некоторые» – квантор существования. Мы договорились не писать формул, но все-таки следует сказать о значках, которые здесь используются, в силу их экзотичности. Квантор общности произошел от английского Allи обозначается буквой A, перевернутой вверх ногами. Квантор существования произошел от английского Existи обозначается буквой E, которую вверх ногами переворачивать бесполезно, поэтому ее повернули кругом.
Наш предикат, после навешивания каждого из кванторов, также превращается в высказывание, которое может быть истинно или ложно!
" ВСЕлюбят кашу"
" НЕКОТОРЫЕлюбят кашу"
Это, кстати, был (до навешивания кванторов) одноместный предикат (одноместная функция). Но предикаты могут быть не только одноместные. Это просто проиллюстрировать, если представить, что дети могут любить не только кашу… «Икс любит Игрека» – двухместный предикат. " ВСЕлюбят Игрека" – одноместный предикат. " ВСЕлюбят КОЙ-КОГО[некоторого]" – нульместный предикат, то есть высказывание.
Интересно посмотреть, как ведут себя кванторы в присутствии операции отрицания. Возьмем отрицание предиката " ВСЕлюбят кашу": " НЕ ВЕРНО, что ВСЕлюбят кашу". Это равносильно (по закону Де Моргана!) заявлению: " НЕКОТОРЫЕ НЕлюбят кашу. То есть отрицание"задвинули" за квантор, в результате чего квантор сменился на противоположный.
А теперь сделаем одно из самых важных заявлений:
ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ – САМЫЙ БЛИЗКИЙ К ЕСТЕСТВЕННОМУ. Поэтому работы по искусственному интеллекту тяготеют к использованию этого языка. В сравнении с естественным, это очень во многих смыслах ограниченный язык. Но лучшего за 100 лет не придумано, если не считать так называемого «синтаксического сахара», когда вместо соответствующей символики используются, например, слова естественного языка. (Вроде того, как мы пытаемся это делать).
В хорошо формализованных системах даже наоборот, дополнительно ограничивают этот язык для удобной реализации на компьютерах. Примером тому язык (логического) программирования
ПРОЛОГ – ПРОграммирование на ЛОГике.
Так вот, язык предикатов наследует пороки языка логики высказываний, которые обуславливают изначальное несоответствие естественного и логического языков.
На языке предикатов можно описать далеко не все, хотя и многое. Но даже в этом ограниченном пространстве подчас приходится применять хитрости и уловки, которые бы больше пристали ремеслу или искусству. Хотя об'яснения, в конце концов, обычно бывают строго формальные.
Вот некоторые «классические примеры».
Если мы желаем сказать на языке предикатов «Все студенты отличники», то рекомендуется конструкция
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс студент, ТОикс отличник"
Но если хотим сказать «Некоторые студенты отличники», то это следует записать
" ДЛЯ НЕКОТОРЫХиксов справедливо: икс студент И икс отличник" Конструкция ЕСЛИ…, ТОв данном случае не подходит. И вот почему: стоит затесаться в компанию одному иксу-нестуденту и он сделает этот предикат истинным, даже если там нет ни одного отличника!
И еще высказывание «Собакам и кошкам вход воспрещен».
Конструкция
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс – собака Иикс – кошка, ТОиксу вход запрещен"
Ясно что таких иксов, которые бы были одновременно собакой и кошкой не существует! Как, впрочем, и таких игреков. Поэтому
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс – собака ИЛИикс – кошка, ТОиксу вход запрещен"
И список таких фокусов-выкрутасов можно продолжать долго. До бесконечности. Но, главное, во-время остановиться и понять, что если бы даже придумать другую логику, в которой не было бы этих проблем, то получится логика, в которой будут другие проблемы, скорее всего существенно большие. А мы даже не трогали таких заморочек, присущих естественным языкам, как синонимы, омонимы, метафоры, гиперболы и т.д и т.п. Одни идиомы, кто знает, чего стоят!… Так что «братания» языка логики с естественным языком не предвидится и в самой отдаленной перспективе, даже когда планета Земля начнет остывать…
Лекция 10. АКСИОМАТИЧЕСКИЕ ТЕОРИИ
Если алгебра логики и дает образец логического мышления, то уж очень специфический. Строгие логические рассуждения и близко от такого образца не лежали. Создавать (абсолютно) строгие логические (то есть абсолютно логичные) системы позволяет дедуктивный подход. Не путать с «дедуктивным методом» Шерлока Холмса. У Холмса, или скорее у Конан-Дойля, явно были проблемы с логикой, коль скоро он путал дедукцию с индукцией…
ДЕДУКТИВНЫЙподход, называемый еще АКСИОМАТИЧЕСКИМ, это подход от общего к частному. От аксиом (постулатов) к теоремам (следствиям). Аксиоматическая теория строго задана, если строго сформулирован (задан) язык теории, ее аксиомы и правила вывода. Стоит хотя бы в одной из этих трех составляющих «дать слабину» и строгой теории как не бывало!
Знаменитая (одна из первых) аксиоматическая теория – геометрия Эвклида худо-бедно обеспечила строгость только в одном компоненте – в постулатах. Но язык, на котором проводятся доказательства в геометрии даже через тысячелетия, как и строгость самих доказательств не выдерживают критики. Это не более, чем неоднозначный метафорическо-аллегорический язык и правдоподобные рассуждения. Потому-то нередки случаи, когда опровергаются «доказанные» теоремы. Собственно, почти вся математика, за исключением сравнительно малюсенького раздела из логики аксиоматических систем, покоится (лучше звучит – зиждется) на правдоподобных рассуждениях и порядочности доказывающих.
Так что образцовая безупречно строгая теория задается на языке предикатных формул. (Мы здесь зареклись использовать формулы, поэтому остается полагаться на собственную честность).
Аксиомами об'являются некоторые из формул. В жизни мы также об'являем законами (аксиомами) не все фразы, которые можно ввернуть в той или иной ситуации, а лишь некоторые, которые мы решили считать таковыми… Законы (Аксиомы) это вопрос веры, а иногда целесообразности. Они недоказуемы! Если доказуемы, то это уже теоремы!
Существование Бога недоказуемо! Иначе это была бы теорема. А из каких, простите, более первичных понятий такую «теорему» выводить прикажете?!…
Закон всемирного тяготения недоказуем. Мы просто ему поверили, поскольку надоело проводить эксперименты по падению тел, в ожидании, когда с ними произойдет что-нибудь оригинальное.
Выводы в теории тоже следует формализовать, поскольку каждому в жизни встречались люди, которые «убедительно» доказывали какую-нибудь чушь.
Кстати, самое знаменитое правило вывода в математической логике ( modus ponens) удручает своей очевидностью и даже примитивностью. Проиллюстрировать его можно так: Пусть в системе есть утверждения
" ЕСЛИхорошая погода, ТОмы гуляем" и
«Хорошая погода» тогда в соответствии с modus ponens выводимо утверждение
«Мы гуляем»
При всей своей примитивности это правило вывода имеет решающее достоинство. Оно очевидно для всех. Очевиднее не бывает! А если в системе есть еще и утверждение:
" ЕСЛИмы гуляем, ТОобязательно заблудимся" то с учетом ранее выведенного
«Мы гуляем» получим
«Обязательно заблудимся»
Видите, как далеко можно зайти маленькими очевидными шажками! Существует много и других правил вывода, но все имеют обязательное свойство – очевидность. Эта очевидность позволяет далее использовать эти правила абсолютно формально. То есть результат вычисляется. Такие символьные вычисления называются
ДЕДУКТИВНЫЙподход, называемый еще АКСИОМАТИЧЕСКИМ, это подход от общего к частному. От аксиом (постулатов) к теоремам (следствиям). Аксиоматическая теория строго задана, если строго сформулирован (задан) язык теории, ее аксиомы и правила вывода. Стоит хотя бы в одной из этих трех составляющих «дать слабину» и строгой теории как не бывало!
Знаменитая (одна из первых) аксиоматическая теория – геометрия Эвклида худо-бедно обеспечила строгость только в одном компоненте – в постулатах. Но язык, на котором проводятся доказательства в геометрии даже через тысячелетия, как и строгость самих доказательств не выдерживают критики. Это не более, чем неоднозначный метафорическо-аллегорический язык и правдоподобные рассуждения. Потому-то нередки случаи, когда опровергаются «доказанные» теоремы. Собственно, почти вся математика, за исключением сравнительно малюсенького раздела из логики аксиоматических систем, покоится (лучше звучит – зиждется) на правдоподобных рассуждениях и порядочности доказывающих.
Так что образцовая безупречно строгая теория задается на языке предикатных формул. (Мы здесь зареклись использовать формулы, поэтому остается полагаться на собственную честность).
Аксиомами об'являются некоторые из формул. В жизни мы также об'являем законами (аксиомами) не все фразы, которые можно ввернуть в той или иной ситуации, а лишь некоторые, которые мы решили считать таковыми… Законы (Аксиомы) это вопрос веры, а иногда целесообразности. Они недоказуемы! Если доказуемы, то это уже теоремы!
Существование Бога недоказуемо! Иначе это была бы теорема. А из каких, простите, более первичных понятий такую «теорему» выводить прикажете?!…
Закон всемирного тяготения недоказуем. Мы просто ему поверили, поскольку надоело проводить эксперименты по падению тел, в ожидании, когда с ними произойдет что-нибудь оригинальное.
Выводы в теории тоже следует формализовать, поскольку каждому в жизни встречались люди, которые «убедительно» доказывали какую-нибудь чушь.
Кстати, самое знаменитое правило вывода в математической логике ( modus ponens) удручает своей очевидностью и даже примитивностью. Проиллюстрировать его можно так: Пусть в системе есть утверждения
" ЕСЛИхорошая погода, ТОмы гуляем" и
«Хорошая погода» тогда в соответствии с modus ponens выводимо утверждение
«Мы гуляем»
При всей своей примитивности это правило вывода имеет решающее достоинство. Оно очевидно для всех. Очевиднее не бывает! А если в системе есть еще и утверждение:
" ЕСЛИмы гуляем, ТОобязательно заблудимся" то с учетом ранее выведенного
«Мы гуляем» получим
«Обязательно заблудимся»
Видите, как далеко можно зайти маленькими очевидными шажками! Существует много и других правил вывода, но все имеют обязательное свойство – очевидность. Эта очевидность позволяет далее использовать эти правила абсолютно формально. То есть результат вычисляется. Такие символьные вычисления называются