Дискретная математика без формул
Шрифт:
«Если Волга впадает в Каспийское море, то 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
Касательно математической логики, как и множеств, есть люди, несогласные с рядом ее законов. Прежде всего это опять законы исключенного третьего и противоречия. То есть заполнение очевидных таблиц истинности для конструктивистов (интуиционистов) неочевидно!