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

1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

2. Определение

• Высказыванием называется
повествовательное предложение, которое
можно охарактеризовать либо как
истинное, либо как ложное, но не как то и
другое вместе.
• Высказывания обозначают прописными
буквами латинского алфавита: . Истинное
высказывание обозначают символом 1, а
ложное – символом 0.

3. Логические операции

• Высказывания, образованные из других
высказываний с помощью логических
связок, называются составными.
Высказывания, не являющиеся составными,
называются элементарными.
• Образование составного высказывания из
элементарных высказываний с помощью
логической связки называется логической
операцией.

4. Логические операции

Отрицание
Конъюнкция

5. Логические операции

Дизъюнкция
Импликация

6. Логические операции

Эквиваленция
Порядок операций
Конечная последовательность букв,
знаков логических операций и
скобок, выражающая логическую
структуру высказывания,
называется формулой логики
высказываний. Символы 0 и 1
также считаются формулами
логики высказываний.
Скобки в формуле указывают
порядок выполнения операций.
Для уменьшения количества
скобок и сокращения записи
принят следующий порядок
выполнения операций: 1)
отрицание; 2) конъюнкция; 3)
дизъюнкция; 4) импликация; 5)
эквиваленция.

7. Таблица истинности

8. Таблица истинности

• В общем случае, если формула содержит
логических переменных, то ее таблица истинности
будет содержать 2n строк. В рассмотренном
примере число строк равно 23.
• Формула, принимающая значение 1 при всех
наборах значений истинности входящих в нее
логических переменных, называется
тождественно-истинной (или тавтологией).
• Формула, принимающая значение 0 при любых
наборах значений истинности входящих в нее
логических переменных, называется
тождественно-ложной.

9. Равносильные формулы

• Две формулы логики высказываний называются
равносильными, если они принимают
одинаковые значения истинности при одних и
тех же наборах значений истинности входящих в
них логических переменных. При этом формулы
должны содержать одинаковый набор
логических переменных.
• Формулы можно обозначать греческими
буквами , , и т.п.
• Если формулы и равносильны, то пишут
= .

10. Законы логики высказываний

11. Доказательство равносильности

12. Доказательство равносильности формул

13. Определение логического следствия

14. Правила логического вывода

15. Пример. Первый способ

16. Пример. Первый способ

17. Пример. Первый способ

18. Пример. Второй способ

19. Пример. Второй способ