Лекция 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
Касательно математической логики, как и множеств, есть люди,
несогласные с рядом ее законов. Прежде всего это опять законы
исключенного третьего и противоречия. То есть заполнение
очевидных таблиц истинности для конструктивистов (интуиционистов)
неочевидно!
Конструктивисты относительно сложного высказывания "Теорема
Ферма верна ИЛИ теорема Ферма НЕверна" говорят, что это сложное
высказывание не может быть истинным хотя бы потому, что признав
его истинность мы окончательно делаем неразрешимым вопрос "Так
верна она или нет?!". Более человеколюбивые логики в качестве
аргумента приводят сложные высказывания типа: "Человек почти
лысый ИЛИ НЕ ВЕРНО, что человек почти лысый". Утверждают, что
определить истинность этого сложного высказывания не только
невозможно, но и просто бестактно.
Логика высказываний, и алгебра высказываний в частности, как
уже ранее говорилось, бурно расцветали на заре вычислительной
техники. Одно из важнейших алгебраических преобразований - это
минимизация сложных высказываний. То есть было создано множество
методик получения из исходного высказывания равносильного, но
имеющего наименьшее возможное число логических операций. А в
соответствии с таким высказыванием можно построить и максимально
простое техническое устройство. И всем заинтересованным лицам
будет хорошо и выгодно от результатов, полученных с помощью науки.
Лекция 9. ЛОГИКА ПРЕДИКАТОВ "Предикат" с английского переводится как сказуемое. Ноговорить "логика сказуемых" - себя не уважать. Формальнопредикатом называется функция, аргументами которой могут бытьПРОИЗВОЛЬНЫЕ ОБ'ЕКТЫ из некоторого множества, а значения функции"истина" или "ложь". Предикат можно рассматривать как расширениепонятия высказывания. Пример. Вместо трех высказываний "Маша любит кашу" "Даша любит кашу" "Саша любит кашу"можно написать один предикат "Икс любит кашу"и договориться, что вместо неизвестного Икс могут быть либо Маша,либо Даша, либо Саша. Подстановка вместо Икс имени конкретного ребенка превращаетпредикат в обычное высказывание. Для предикатов справедливы, и имеют тот же смысл, ранеерассмотренные логические операции. Например, "ЕСЛИ Маша любит кашу, ТО Саша любит кашу". Но есть и две новые операции, специфические. Они называютсянесколько вызывающе - операциями НАВЕШИВАНИЯ КВАНТОРОВ. Этиоперации соответствуют фразам "для всех" - квантор общности и"некоторые" - квантор существования. Мы договорились не писатьформул, но все-таки следует сказать о значках, которые здесьиспользуются, в силу их экзотичности. Квантор общности произошелот английского All и обозначается буквой A, перевернутой вверхногами. Квантор существования произошел от английского Exist иобозначается буквой E, которую вверх ногами переворачиватьбесполезно, поэтому ее повернули кругом. Наш предикат, после навешивания каждого из кванторов, такжепревращается в высказывание, которое может быть истинно или ложно! "ВСЕ любят кашу" "НЕКОТОРЫЕ любят кашу" Это, кстати, был (до навешивания кванторов) одноместныйпредикат (одноместная функция). Но предикаты могут быть не толькоодноместные. Это просто проиллюстрировать, если представить, чтодети могут любить не только кашу... "Икс любит Игрека" -двухместный предикат. "ВСЕ любят Игрека" - одноместный предикат."ВСЕ любят КОЙ-КОГО [некоторого]" - нульместный предикат, тоесть высказывание. Интересно посмотреть, как ведут себя кванторы в присутствииоперации отрицания. Возьмем отрицание предиката "ВСЕ любят кашу":"НЕ ВЕРНО, что ВСЕ любят кашу". Это равносильно (по закону ДеМоргана!) заявлению: "НЕКОТОРЫЕ НЕ любят кашу. То есть отрицание"задвинули" за квантор, в результате чего квантор сменился напротивоположный. А теперь сделаем одно из самых важных заявлений: ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ - САМЫЙБЛИЗКИЙ К ЕСТЕСТВЕННОМУ. Поэтому работы по искусственномуинтеллекту тяготеют к использованию этого языка. В сравнении сестественным, это очень во многих смыслах ограниченный язык. Нолучшего за 100 лет не придумано, если не считать так называемого"синтаксического сахара", когда вместо соответствующей символикииспользуются, например, слова естественного языка. (Вроде того,как мы пытаемся это делать). В хорошо формализованных системах даже наоборот,дополнительно ограничивают этот язык для удобной реализации накомпьютерах. Примером тому язык (логического) программированияПРОЛОГ - ПРОграммирование на ЛОГике. Так вот, язык предикатов наследует пороки языка логикивысказываний, которые обуславливают изначальное несоответствиеестественного и логического языков. На языке предикатов можно описать далеко не все, хотя имногое. Но даже в этом ограниченном пространстве подчасприходится применять хитрости и уловки, которые бы большепристали ремеслу или искусству. Хотя об'яснения, в конце концов,обычно бывают строго формальные. Вот некоторые "классические примеры".Если мы желаем сказать на языке предикатов "Все студенты отличники",то рекомендуется конструкция "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс студент, ТО икс отличник" Но если хотим сказать "Некоторые студенты отличники", то этоследует записать "ДЛЯ НЕКОТОРЫХ иксов справедливо: икс студент И иксотличник" Конструкция ЕСЛИ ..., ТО в даном случае не подходит. Ивот почему: стоит затесаться в компанию одному иксу-нестуденту ион сделает этот предикат истинным, даже если там нет ни одногоотличника! И еще высказывание "Собакам и кошкам вход воспрещен".Конструкция "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака И икс -кошка, ТО иксу вход запрещен" Ясно что таких иксов, которые бы были одновременно собакой икошкой не существует! Как, впрочем, и таких игреков. Поэтому "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака ИЛИ икс -кошка, ТО иксу вход запрещен" И список таких фокусов-выкрутасов можно продолжать долго. Добесконечности. Но, главное, во-время остановиться и понять, чтоесли бы даже придумать другую логику, в которой не было бы этихпроблем, то получится логика, в которой будут другие проблемы,скорее всего существенно большие. А мы даже не трогали такихзаморочек, присущих естественным языкам, как синонимы, омонимы,метафоры, гиперболы и т.д и т.п. Одни идиомы, кто знает, чегостоят!.. Так что "братания" языка логики с естественным языкомне предвидится и в самой отдаленной перспективе, даже когдапланета Земля начнет остывать...
Лекция 10. АКСИОМАТИЧЕСКИЕ ТЕОРИИ Если алгебра логики и дает образец логического мышления, тоуж очень специфический. Строгие логические рассуждения и близкоот такого образца не лежали. Создавать (абсолютно) строгиелогические (то есть абсолютно логичные) системы позволяетдедуктивный подход. Не путать с "дедуктивным методом" ШерлокаХолмса. У Холмса, или скорее у Конан-Дойля, явно были проблемы слогикой, коль скоро он путал дедукцию с индукцией... ДЕДУКТИВНЫЙ подход, называемый еще АКСИОМАТИЧЕСКИМ, этоподход от общего к частному. От аксиом (постулатов) к теоремам(следствиям). Аксиоматическая теория строго задана, если строгосформулирован (задан) язык теории, ее аксиомы и правила вывода.Стоит хотя бы в одной из этих трех составляющих "дать слабину" истрогой теории как не бывало! Знаменитая (одна из первых) аксиоматическая теория -геометрия Эвклида худо-бедно обеспечила строгость только в одномкомпоненте - в постулатах. Но язык, на котором проводятсядоказательства в геометрии даже через тысячелетия, как истрогость самих доказательств не выдерживают критики. Это неболее, чем неоднозначный метафорическо-аллегорический язык иправдоподобные рассуждения. Потому-то нередки случаи, когдаопровергаются "доказанные" теоремы. Собственно, почти всяматематика, за исключением сравнительно малюсенького раздела излогики аксиоматических систем, покоится (лучше звучит - зиждется)на правдоподобных рассуждениях и порядочности доказывающих. Так что образцовая безупречно строгая теория задается наязыке предикатных формул. (Мы здесь зареклись использоватьформулы, поэтому остается полагаться на собственную честность). Аксиомами об'являются некоторые из формул. В жизни мы такжеоб'являем законами (аксиомами) не все фразы, которые можноввернуть в той или иной ситуации, а лишь некоторые, которые мырешили считать таковыми... Законы (Аксиомы) это вопрос веры, аиногда целесообразности. Они недоказуемы! Если доказуемы, то этоуже теоремы! Существование Бога недоказуемо! Иначе это была бы теорема.А из каких, простите, более первичных понятий такую "теорему"выводить прикажете?!.. Закон всемирного тяготения недоказуем. Мы просто емуповерили, посколько надоело проводить эксперименты по падениютел, в ожидании, когда с ними произойдет что-нибудь оригинальное. Выводы в теории тоже следует формализовать, посколькукаждому в жизни встречались люди, которые "убедительно" доказываликакую-нибудь чушь. Кстати, самое знаменитое правило вывода в математическойлогике (modus ponens) удручает своей очевидностью и дажепримитивностью. Проиллюстрировать его можно так: Пусть в системеесть утверждения "ЕСЛИ хорошая погода, ТО мы гуляем"и "Хорошая погода"тогда в соответствии с modus ponens выводимо утверждение "Мы гуляем" При всей своей примитивности это правило вывода имеетрешающее достоинство. Оно очевидно для всех. Очевиднее небывает! А если в системе есть еще и утверждение: "ЕСЛИ мы гуляем, ТО обязательно заблудимся"то с учетом ранее выведенного "Мы гуляем"получим "Обязательно заблудимся" Видите, как далеко можно зайти маленькими очевиднымишажками! Существует много и других правил вывода, но все имеютобязательное свойство - очевидность. Эта очевидность позволяетдалее использовать эти правила абсолютно формально. То естьрезультат вычисляется. Такие символьные вычисления называютсяИСЧИСЛЕНИЯМИ. Есть еще один подход к аксиоматике, когда основной упорделается именно на правила вывода. Такие системы (почему-то)называются системами естественного вывода, намекая на то, что вних собраны базовые естественные правила логических рассуждений. Логики резвились меж собой до тех пор, пока не былсформулирован подход к созданию аксиоматических систем подназванием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ. Он очень способствовалпродвижению логики в широкие народные массы. С одной стороны, активизировались работы по использованиюкомпьютеров для реализации логического вывода и работы поискусственному интеллекту в частности. А с другой стороны, наэтой основе был создан язык ПРОЛОГ. Это совсем другое программирование, нежели традиционноепроцедурное. Это даже не программирование в обычном смысле слова,коль скоро здесь программист не пишет алгоритм решения задачи. Онописывает логические зависимости "мира", в котором существуетзадача. На основе описанной логики "мира" система (машина) самасоздает алгоритм в процессе поиска решения! Это только кажется, что аксиоматические системы - этосложно. Любой может напридумывать их сколько угодно. Болеепростым делом вам вряд ли приходилось заниматься. Например, в качестве языка можно об'явить любые "слова" изпоследовательности буквы Я. Букву Я об'явим аксиомой. Правило вывода будет удваивать букву Я. То есть сходу придумана теория, в которой выводимы любыепоследовательности (слова), состоящие из буквы Я. Я ЯЯ ЯЯЯ ... ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ ... И все бы хорошо, только такая строго заданная теория малочто дает создателю, кроме радости созидания. Поэтому встаетвопрос целесообразности, смысла. Той самой семантики... Здесьлогики заняли очень(!) интересную позицию. Коль скоро логика не интересуется смыслом высказываний, алишь их истинностью, то ее (истинность) и об'явили смысломвысказываний. Вдумайтесь, смысл высказывания, например, "Газ принагревании расширяется" не в том, что это отражение физическогозакона, а в том что оно истинно. Следовательно, точно такой жесмысл(!) имеет высказывание "Никита Михалков - кинорежиссер". Тоесть его смысл в том, что оно тоже истинное. Дальше - больше. Язык предикатов - это существенноерасширение языка высказываний и обычным образом перебрать всеслучаи даже в простейшей ситуации, вроде "Икс любит кашу", невсегда возможно. Тем более, что речь может идти и обесконечностях. Для решения проблем семантики в этом случаеприбегают к теории моделей. Но это теория также, в конечномитоге, упирается в "смысл" типа истинно-ложно. Возвращаясь к аксиоматическим теориям следует сказать, что вматематике "практический смысл" имеют лишь такие теории, вкоторых можно выводить только истинные формулы. И нельзя ложные.Одна ложная формула "уничтожает без остатка" любуюаксиоматическую теорию. Наша теория, созданная из буквы Я, не привязана к понятиюистинности. Поэтому она бессмысленна, как бессистемнаяперестановка детских кубиков. С кубиками все ясно. Но проблемы аксиоматических теорий наэтом не исчерпываются. Пожалуй самым фундаментальным открытием вэтой сфере следует считать доказанную Геделем ТЕОРЕМУ ОНЕПОЛНОТЕ. Оказывается, в сколько-нибудь сложной аксиоматическойсистеме (посложнее, чем кубики, но достаточно даже арифметики)существуют формулы, которые нельзя ни доказать, ни опровергнуть.Может в этом причина, что не все школьные задачки имеют решения?!Так что, создавая свои аксиоматические теории помните, что онидолжны обладать какими-то полезными свойствами. А такие теориисоздавать уже не так-то просто. Хотя создать свою собственнуюматематику может каждый! Известно высказывание одного крупного математика:"Преимущество аксиоматизации - это преимущество воровства передчестным трудом".