�ݺ�ߣ

Основные операции Таблицы истинности Законы логики

Математическая логика

11 февраля 2013 г.



Три основные логические операции

Название Обозначение Альт. Соответствие Знач.
Конъюнкция & ∧ умножение и
Дизъюнкция ∨ сложение или
Отрицание ¬ отрицание не
Полезно запомнить соответствия — это помогает
определить порядок выполнения операций: отрицание,
конъюнкция, дизъюнкция.



&



¬



∨



A ∨ ¬B&C
Какой порядок выполнения?



¬A&¬B ∨ C &(¬D ∨ E )
Какой порядок выполнения?



Таблицы истинности



Таблица истинности для конъюнкции

Рассмотрим, чему может быть равно высказывание A & B:

A B A&B
И И И
И Л Л
Л И Л
Л Л Л



Таблица истинности для дизъюнкции

Рассмотрим, чему может быть равно высказывание A ∨ B:

A B A∨B
И И И
И Л И
Л И И
Л Л Л



Таблица истинности для отрицания

Рассмотрим, чему может быть равно высказывание ¬A:

A ¬A
И Л
Л И



Правила для запоминания / понимания

Конъюнкция требует, чтобы оба условия были истинны: и
то, и другое.
Дизъюнкции достаточно, чтобы одно из условий
выполнялось: или первое, или второе (или оба вместе).
Отрицание меняет значение на противоположное.



Пример построения таблицы истинности

Построим таблицу истинности для высказывания
A & B ∨ ¬C .
Построение заключается в переборе всех возможных
вариантов.

A B C Итог
И И И
И И Л
И Л И
Л И И
И Л Л
Л И Л
Л Л И
Л Л Л




Посчитаем первую строку, подставив значения A, B, C:
A&B ∨ ¬C = И&И∨¬И = И&И∨Л = И ∨ Л = И

A B C Итог
И И И И
И И Л
И Л И
Л И И
И Л Л
Л И Л
Л Л И
Л Л Л




Аналогично рассчитываем для каждой оставшейся строки.

A B C Итог
И И И И
И И Л И
И Л И Л
Л И И Л
И Л Л И
Л И Л И
Л Л И Л
Л Л Л И



Задачи

Построить таблицу истинности для следующих
высказываний:
1 A ¬ B ∨ ¬¬A
2 ¬(A&¬B)&C
3 A ¬A
4 A ∨ ¬A



Законы логики



Основные законы логики

Как и в математике, в логике есть свои законы.
Во многом, они похожи на математические.
Название Закон
Переместительный A&B = B&A
A∨B = B∨A
Сочетательный A&(B&C) = A&(B&C)
A∨(B∨C) = A∨(B∨C)
Распределительный A&(B∨C) = (A&B)∨(A&C)
A∨(B&C) = (A∨B)&(A∨C)
Правила де Моргана ¬(A&B) = ¬A∨¬B
¬(A∨B) = ¬A&¬B



В логике можно доказывать законы

Но как?



Доказательство правила де Моргана

В логике два высказывания называются равными, если
совпадают их таблицы истинности.
Для доказательства одного из правил де Моргана
построим таблицы истинности для левых и правых частей
равенства.
Если таблицы совпадут, значит, формула верна:
A B ¬(A&B) A B ¬A∨¬B
И И Л И И Л
И Л И И Л И
Л И И Л И И
Л Л И Л Л И



Задачи

Докажите переместительный закон для конъюнкции.
Докажите распределительный закон конъюнкции
относительно дизъюнкции (первый).



Остальные законы

Название Закон
Двойного отрицания ¬¬A = A
Противоречия A&¬A = Л
A∨¬A = И
Повторения A&A = A
A∨A = A
Просто закон A&И = A
A∨И = И
Просто закон 2 A&Л = Л
A∨Л = A



Задачи

Пример с раскрытием скобок:
A&¬(B∨C) = A&(¬B&¬C) = A&¬B&¬C
Раскрыть скобки у следующих выражений:
1 ¬(A&¬B)&C
2 ¬(¬(¬¬A&¬B)&C )


�ݺ�ߣ

Основы математической логики

Recommended

More Related Content

Viewers also liked (10)

More from Evgeny Smirnov (20)

Основы математической логики