Александр Соловьев - ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ Страница 8

Лекция 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, которую вверх ногами переворачивать бесполезно, поэтому ее повернули кругом.

Наш предикат, после навешивания каждого из кванторов, также превращается в высказывание, которое может быть истинно или ложно!

"ВСЕ любят кашу"

"НЕКОТОРЫЕ любят кашу"

Это, кстати, был (до навешивания кванторов) одноместный предикат (одноместная функция). Но предикаты могут быть не только одноместные. Это просто проиллюстрировать, если представить, что дети могут любить не только кашу… «Икс любит Игрека» – двухместный предикат. "ВСЕ любят Игрека" – одноместный предикат. "ВСЕ любят КОЙ-КОГО [некоторого]" – нульместный предикат, то есть высказывание.

Интересно посмотреть, как ведут себя кванторы в присутствии операции отрицания. Возьмем отрицание предиката "ВСЕ любят кашу": "НЕ ВЕРНО, что ВСЕ любят кашу". Это равносильно (по закону Де Моргана!) заявлению: "НЕКОТОРЫЕ НЕ любят кашу. То есть отрицание"задвинули" за квантор, в результате чего квантор сменился на противоположный.