Жуланова В. П., КРИПКиПРО Часть 2. Логические законы

Сперва хочу Вам в долг вменить На курсы логики ходить, Ваш ум нетронутый доныне, На них приучат к дисциплине, Чтоб взял он направленья ось, Не разбредаясь вкривь и вкось. Гёте «Фауст», перевод Б. Пастернак

Основные законы логики Закон тождества В процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе. А=А Закон непротиворечия Из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано И Ӣ =1 Закон исключенного третьего Невозможно что-либо одновременно утверждать и отрицать. И = Ӣ Закон двойного отрицания Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована А & А =0

Основные законы логики Свойства констант А & 0 =0 Отсутствие коэффициентов Законы идемпотентности Законы коммутативности Высказывания в операциях конъюнкции и дизъюнкции можно менять местами 1=0 Свойства констант Отрицание лжи есть истина Свойства констант Отрицание истины есть ложь А 0=А А 1=1 0=1 А & 1 =А А А=А А & А =А Отсутствие степеней А В = В А А & В = В & А

Основные законы логики Дистрибутивность конъюнкции относительно дизъюнкции Законы дистрибутивности Законы поглощения Если в выражении используется только операция дизъюнкции или только операция конъюнкции, то скобками можно пренебрегать или произвольно их расставлять А (А & В) = А А (В С) = (А В) С А & (В & С) = (А & В) & С Законы ассоциативности А (В & С) = (А В) & (А С) А & (В С) = (А & В) (А & С) Дистрибутивность дизъюнкции относительно конъюнкции А & (А В) = А

Основные законы логики Описание вариантов вместе Законы де Моргана А В = А & В А & В = А В Отрицание одновременной истинности дизъюнкции конъюнкция Отрицание есть отрицания конъюнкции дизъюнкция дизъюнкции конъюнкция Отрицание есть отрицания конъюнкции дизъюнкция или и Отрицание истинности А В тождественно тому, что ложно А ложно В и или или и Отрицание истинности А В тождественно тому, что ложно А ложно В и или А В = А & В А & В = А В

Основные законы логики Е= Неверно, что если я выиграю конкурс, то получу приз Замена операции импликации А В = А В А В = В А А= Я выиграю конкурс В= Я получу приз А= Я выиграю конкурс В= Я получу приз Е= А В = А В = А & В = А & В Если Винни-Пух съел мед, то он сыт = Если Винни-Пух не сыт, то меда он не ел Если Винни-Пух съел мед, то он сыт = Если Винни-Пух не сыт, то меда он не ел

Основные законы логики Упрощение логических выражений: Задание 1. Какое логическое выражение равносильно выражению ¬ (¬A \/ B) \/ ¬ C? Решение: Применим закон де Моргана к выражению в скобке: ¬ (¬A \/ B) \/ ¬ C = ¬ ¬A & ¬B \/ ¬ C Применим закон двойного отрицания: ¬ ¬A & ¬B \/ ¬ C = A & ¬B \/ ¬ C. Задание 1. Какое логическое выражение равносильно выражению ¬ (¬A \/ B) \/ ¬ C? Решение: Применим закон де Моргана к выражению в скобке: ¬ (¬A \/ B) \/ ¬ C = ¬ ¬A & ¬B \/ ¬ C Применим закон двойного отрицания: ¬ ¬A & ¬B \/ ¬ C = A & ¬B \/ ¬ C. Решить: Какое логическое выражение равносильно выражению Задание 2. ¬ (A /\ B) /\ ¬C? Задание 3. ¬(A \/ ¬ B \/ C)? Решить: Какое логическое выражение равносильно выражению Задание 2. ¬ (A /\ B) /\ ¬C? Задание 3. ¬(A \/ ¬ B \/ C)?

Основные законы логики Упрощение логических выражений: Задание 1. Докажите равносильность следующих формул: (A B) ( B A) B A, Решение: 1. Опустим скобки по закону ассоциативности, т. к. стоит одинаковый знак конъюнкции: (A B) B A B A 2. Умножим скобку на В по закону коммутативности: ((A B) B) A B A 3. По закону поглощения в скобке остается переменная В: В A B A Задание 1. Докажите равносильность следующих формул: (A B) ( B A) B A, Решение: 1. Опустим скобки по закону ассоциативности, т. к. стоит одинаковый знак конъюнкции: (A B) B A B A 2. Умножим скобку на В по закону коммутативности: ((A B) B) A B A 3. По закону поглощения в скобке остается переменная В: В A B A Решить: Докажите равносильность следующих формул: (¬ (A B)) ((¬ A) (¬ B)) ¬ (A B) Решить: Докажите равносильность следующих формул: (¬ (A B)) ((¬ A) (¬ B)) ¬ (A B)

Основные законы логики Решение логических задач Задача 1. Для какого имени истинно высказывание: ¬ (Первая буква имени гласная Четвертая буква имени согласная)? ЕЛЕНА, ВАДИМ, АНТОН, ФЕДОР Задача 1. Для какого имени истинно высказывание: ¬ (Первая буква имени гласная Четвертая буква имени согласная)? ЕЛЕНА, ВАДИМ, АНТОН, ФЕДОР Решение: Обозначения: А= Первая буква имени гласная. В = Четвертая буква имени согласная Формализация: ¬(А В) Упрощение: Применим закон замены импликации, закон двойного отрицания и закон де Моргана А В = А v В = А & В = А & В Заменим переменные высказываниями: Первая буква имени гласная И четвертая буква имени НЕ согласная/ Ответ: АНТОН Решение: Обозначения: А= Первая буква имени гласная. В = Четвертая буква имени согласная Формализация: ¬(А В) Упрощение: Применим закон замены импликации, закон двойного отрицания и закон де Моргана А В = А v В = А & В = А & В Заменим переменные высказываниями: Первая буква имени гласная И четвертая буква имени НЕ согласная/ Ответ: АНТОН Решить: Задача 2. Какое из приведенных имен удовлетворяет логическому условию ¬ (первая буква гласная вторая буква гласная) /\ последняя буква гласная: ИРИНА, МАКСИМ, АРТЕМ, МАРИЯ? Решить: Задача 2. Какое из приведенных имен удовлетворяет логическому условию ¬ (первая буква гласная вторая буква гласная) /\ последняя буква гласная: ИРИНА, МАКСИМ, АРТЕМ, МАРИЯ?

Основные законы логики Решение логических задач: Задание 1. Для какого числа X (1, 2, 3, 4) истинно высказывание ((X>3) \/(X (X<1) = 1 Решение: 1. Обозначим: А = ((X>3) \/(X<3)) ; В = (X<1). 2. Применим закон замены импликации: А В = ¬ А v В: ¬ ((X>3) \/(X<3)) v (X<1) = 1 3. Применим закон де Моргана к первой скобке: (¬(X>3) & ¬ (X<3)) v (X<1) = 1 4. Дизъюнкция равна единице, когда одно из высказываний равно 1. X<1 = 0, т. к. в условии задачи задано Х = 1, 2, 3, (¬(X>3) & ¬ (X 3) = 1, т. е. (Х<3) v (X = 3) = 1 ¬ (X 3) v (X = 3) = 1. Двум условиям удовлетворяет значение Х = 3. v (X<1) Задание 1. Для какого числа X (1, 2, 3, 4) истинно высказывание ((X>3) \/(X (X<1) = 1 Решение: 1. Обозначим: А = ((X>3) \/(X<3)) ; В = (X<1). 2. Применим закон замены импликации: А В = ¬ А v В: ¬ ((X>3) \/(X<3)) v (X<1) = 1 3. Применим закон де Моргана к первой скобке: (¬(X>3) & ¬ (X<3)) v (X<1) = 1 4. Дизъюнкция равна единице, когда одно из высказываний равно 1. X<1 = 0, т. к. в условии задачи задано Х = 1, 2, 3, (¬(X>3) & ¬ (X 3) = 1, т. е. (Х<3) v (X = 3) = 1 ¬ (X 3) v (X = 3) = 1. Двум условиям удовлетворяет значение Х = 3. v (X<1) Решить: Для какого числа X (1, 2, 3, 4) истинно высказывание ¬ ((X>2) (X>3))? Решить: Для какого числа X (1, 2, 3, 4) истинно высказывание ¬ ((X>2) (X>3))?

Основные законы логики Основные приемы замены отдельной переменной или константы формулой Упрощение сложных высказываний А = А & 1 А=А 0 А = А & 1 А=А 0 по свойствам константы 1=А А по закону исключенного третьего по закону непротиворечия А = А А = А А А А А= А & А = А & А & А & А А = А А = А А А А А= А & А = А & А & А & А по закону идемпотентности по закону двойного отрицания А = А Самостоятельная работа 0=А & А

Литература 1. Лыскова В., Ракитина Е. Логика в информатике. – М.: ЛБЗ, – 160 с. 2. Математика для гуманитариев. 3. Мендельсон Э. Введение в математическую логику. М.: Наука, Столл Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, Михайлов А.Б., Плоткин А.И., Рисе Е.А., Яшина Е.Ю. Математический язык в задачах. СПб.: Изд-во РГПУ им. Герцена, Игошин В.И. Задачник-практикум по математической логике. М.:Просвещение, Гиндикин С.Г. Алгебра логики в задачах. М.: Наука, Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984.