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

Ассоциативный закон утверждает, что безразлично, в каком порядке мы рассматриваем (истинность) попарных кон'юнкций и диз'юнкций:

"Стоит хорошая погода И мы купаемся И заработали ангину".

"Стоит хорошая погода ИЛИ мы купаемся ИЛИ заработали ангину".

Поскольку очередность выполнения операций в математике часто задают скобками, то ассоциативный закон еще называют законом снятия скобок.

Дистрибутивный закон .

Приведем пример только для «экзотического» случая.

"Стоит хорошая погода ИЛИ мы купаемся И заработали ангину" равносильно высказыванию

"Стоит хорошая погода И мы купаемся ИЛИ стоит хорошая погода И заработали ангину"

Не будем перечислять все возможные законы логики высказываний. Как уже было сказано, они аналогичны законам алгебры множеств. Но важно заметить, что здесь мы вместо слова «равенство» употребляли слово «равносильность». Два сложных высказывания являются равносильными, если они имеют одинаковые ТАБЛИЦЫ ИСТИННОСТИ . В этих таблицах начальные столбцы соответствуют исходным (элементарным) высказываниям, а последний результирующему (сложному) высказыванию. В начальных столбцах проставляются все возможные комбинации истинности элементарных высказываний, а в последнем истинность сложного высказывания.

Для каждой комбинации отдельная строка.

Для последнего примера таблицы будут одинаковыми для левой и правой части дистрибутивного закона:

хорошая погода | мы купаемся | заработали ангину | РЕЗУЛЬТАТ

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

Касательно математической логики, как и множеств, есть люди, несогласные с рядом ее законов. Прежде всего это опять законы исключенного третьего и противоречия. То есть заполнение очевидных таблиц истинности для конструктивистов (интуиционистов) неочевидно!

Конструктивисты относительно сложного высказывания "Теорема Ферма верна ИЛИ теорема Ферма НЕ верна" говорят, что это сложное высказывание не может быть истинным хотя бы потому, что признав его истинность мы окончательно делаем неразрешимым вопрос «Так верна она или нет?!». Более человеколюбивые логики в качестве аргумента приводят сложные высказывания типа: "Человек почти лысый ИЛИ НЕ ВЕРНО , что человек почти лысый". Утверждают, что определить истинность этого сложного высказывания не только невозможно, но и просто бестактно.

Логика высказываний, и алгебра высказываний в частности, как уже ранее говорилось, бурно расцветали на заре вычислительной техники. Одно из важнейших алгебраических преобразований – это минимизация сложных высказываний. То есть было создано множество методик получения из исходного высказывания равносильного, но имеющего наименьшее возможное число логических операций. А в соответствии с таким высказыванием можно построить и максимально простое техническое устройство. И всем заинтересованным лицам будет хорошо и выгодно от результатов, полученных с помощью науки.

«Предикат» с английского переводится как сказуемое. Но говорить «логика сказуемых» – себя не уважать. Формально предикатом называется функция, аргументами которой могут быть ПРОИЗВОЛЬНЫЕ ОБ'ЕКТЫ из некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывания.

Пример. Вместо трех высказываний

«Маша любит кашу»

«Даша любит кашу»

«Саша любит кашу» можно написать один предикат

«Икс любит кашу» и договориться, что вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша.

Подстановка вместо Икс имени конкретного ребенка превращает предикат в обычное высказывание.

Для предикатов справедливы, и имеют тот же смысл, ранее рассмотренные логические операции. Например,

" ЕСЛИ Маша любит кашу, ТО Саша любит кашу".

Но есть и две новые операции, специфические. Они называются несколько вызывающе – операциями НАВЕШИВАНИЯ КВАНТОРОВ . Эти операции соответствуют фразам «для всех» – квантор общности и «некоторые» – квантор существования. Мы договорились не писать формул, но все-таки следует сказать о значках, которые здесь используются, в силу их экзотичности. Квантор общности произошел от английского All и обозначается буквой A , перевернутой вверх ногами. Квантор существования произошел от английского Exist и обозначается буквой E , которую вверх ногами переворачивать бесполезно, поэтому ее повернули кругом.