 |
Тождественно истинные и тождественно ложные высказывания
|
|
|
|
· логика, как наука;
· алгебра высказываний;
· логические операции;
· логические функции;
· приоритет логических операций;
· тождественно истинные и тождественно ложные операции;
· основные законы алгебры логики;
· доказательство логических законов;
· простейшие преобразователи информации;
· домашнее задание.
Если сложное высказывание истинно для всех значений входящих в него переменных, то такое высказывание называется ТОЖДЕСТВЕННО ИСТИННЫМ или тавтологией (обозначается константой 1).
НАПРИМЕР высказывание: "Демократ - это человек, исповедующий демократические убеждения" - всегда истинно, то есть является тавтологией.
Все математические, физические и др. законы являются тавтологиями. Например: (а+b)2= a2+ 2ab + b2
Прогноз погоды на завтра может быть, например, таким: "Дождь будет или дождя не будет". Такое предсказание будет всегда истинным, хотя вряд ли кого устроит. Его математическая запись:
А V не(А) = 1
(по закону исключенного третьего всегда должно быть истинным либо суждение, либо его отрицание).
Проверить, является ли сложное высказывание тождественно истинным, можно по таблице истинности.
Если сложное высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется ТОЖДЕСТВЕННО ЛОЖНЫМ (обозначается константой 0).
НАПРИМЕР, высказывание: "Сегодня среда, а это - второй день недели" является тождественно ложным. Тождественно ложным является и следующее высказывание: "Компьютер включен и компьютер не включен (выключен)". Математическая запись его такова:
A & не(A) = 0
(по закону противоречия: не могут быть одновременно истинны утверждение и его отрицание.)
|
|
|
Если значения сложных высказываний совпадают при всех возможных значениях входящих в них переменных, то такие высказывания называют РАВНОСИЛЬНЫМИ, ТОЖДЕСТВЕННЫМИ, ЭКВИВАЛЕНТНЫМИ
Упрощение сложных высказываний - это замена высказывания на равносильное ему на основе законов алгебры высказываний
ОСНОВНЫЕ ЗАКОНЫ (РАВНОСИЛЬНОСТИ) АЛГЕБРЫ ЛОГИКИ
· логика, как наука;
· алгебра высказываний;
· логические операции;
· логические функции;
· приоритет логических операций;
· тождественно истинные и тождественно ложные операции;
· основные законы алгебры логики;
· доказательство логических законов;
· простейшие преобразователи информации;
· домашнее задание.
При решении логических задач часто приходится упрощать формулы. Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на основные законы.
Законы логики высказываний - это такие выражения, которым всегда соответствует истинное высказывание, какие бы подстановки значений мы ни делали вместо переменных. В алгебре высказываний логические законы выражаются в виде формул.
1.1. Закон тождества:
А = А
- всякая мысль тождественна самой себе, то есть "А есть А", где А – любое высказывание.
2. Закон исключенного третьего:
А V А = 1
- в один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А.
НАПРИМЕР. "Число 123 либо четное, либо нечетное, третьего не дано".
Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: либо-либо, истина-ложь. Там же где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.
Рассмотрим следующее высказывание: "Это предложение ложно". Оно не может быть истинным, потому, что оно утверждает, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.
|
|
|
Парадокс (греч. paradoxos - неожиданный, странный) возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере:
"В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру?"
В нашей формальной системе нет возможности ввести такое ссылающееся само на себя истолкование, поэтому мы не можем выразить все возможные мысли и доводы.
3. Закон непротиворечия:
(А ^ А) = 1
- не могут быть одновременно истинными суждение и его отрицание. То есть, если высказывание А - истинно, то его отрицание А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.
3a. А ^ А =0.
Именно эта формула часто используется при упрощении сложных логических выражений.
Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными.
ПРИМЕР. Е = "На Марсе есть жизнь и на Марсе жизни нет"
4. Закон двойного отрицания:
А = А
- если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание.
НАПРИМЕР: А = " Неверно, что Матроскин не кот"
эквивалентно высказыванию А = "Матроскин - кот".
СВОЙСТВА КОНСТАНТ
5. 0 = 1
6. 1 = 0
7. А V 0 = А
8. А ^ 0 = 0
9. А V 1 = 1
10. А ^ 1 = А
ЗАКОНЫ ИДЕМПОТЕНТНОСТИ
11. А V А = А
Отсутствие коэффициентов
12. А ^ А = А
Отсутствие степеней
12. А ^ А = А
Отсутствие степеней
Сколько бы раз мы ни повторяли "на улице тепло и на улице тепло" ни на один градус теплее от этого не станет, аналогично, от повторения “телевизор включен или телевизор включен” значение высказывания не меняется.
Сколько бы раз мы ни повторяли "на улице тепло и на улице тепло" ни на один градус теплее от этого не станет, аналогично, от повторения “телевизор включен или телевизор включен” значение высказывания не меняется.
ЗАКОНЫ КОММУТАТИВНОСТИ
13. А V В = В V А
14. А ^ В = В ^ А
ЗАКОНЫ АССОЦИАТИВНОСТИ
15. А V (В V С) = (А V В) V С
|
|
|
16. А ^ (В ^ С) = (А ^ В) ^ С
ЗАКОНЫ ДИСТРИБУТИВНОСТИ
17. А V (В^С) = (АVВ) ^ (АVС)
дизъюнкции относительно конъюнкции
18. А ^ (ВVС) = (А ^ В) V (А ^ С)
конъюнкции относительно дизъюнкции
Закон 18 аналогичен дистрибутивному закону в алгебре, а закон 17 аналога не имеет, он справедлив только в логике. Доказательство его удобнее всего провести по таблице истинности.
| А | B | C | 2 L 3 | 1 V 4 | 1 V 2 | 1 V 3 | 6 L 7 | 5 = 8 |
ЗАКОНЫ ПОГЛОЩЕНИЯ
19. А V А ^ В = А
20. А ^(А V В) = А
ЗАКОНЫ де МОРГАНА
21. (А V В) = А ^ В
Отрицание вариантов
22. (А ^ В) = А V В
Отрицание одновременной истинности
Мнемоническое правило. В левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция дизъюнкция на конъюнкцию и наоборот.
ПРИМЕРЫ:
"Неверно, что я знаю арабский или китайский язык" тождественно тому, что "Я не знаю арабского языка и не знаю китайского языка"
"Неверно, что я выучил урок и получил по нему двойку" тождественно тому, что "или я не выучил урок, или я не получил двойку"
Операций импликации и эквивалентности иногда нет среди логических операций конкретного компьютера или транслятора с языка, а при решении задач они требуются. Существуют формулы замены данных операций с использованием только операций отрицания, дизъюнкции и конъюнкции. Так, вместо операции импликации можно использовать следующее тождественное выражение:
A → B = A V B
Для замены операции эквивалентности существует два выражения:
A <=> B = (A ^ B) V (A ^ B)
A <=> B = (A V B) ^ (A V B)
Знание данных формул помогает, например, правильно построить отрицание импликации.
|
|
|
Рассмотрим следующий пример.
Пусть дано высказывание:
Е = "Неверно, что если я выиграю конкурс, то получу приз"
Пусть А = "Я выиграю конкурс", В = " Я получу приз", тогда
Е = (A → B) = (A V B) = A ^ B = A ^ B,
то есть Е = "Возможно, что я выиграю конкурс, но приз не получу".
Интерес представляют и следующие формулы:
А → B = B → A
A <=> B = (A → B) ^ (B → A)
Доказать их справедливость можно также с помощью таблиц истинности. Интересно их выражение в разговорном языке. Например, фраза "Если Винни-Пух съел мед, то он сыт" тождественна фразе "Если Винни-Пух не сыт, то меда он не ел".
ДОКАЗАТЕЛЬСТВО ЛОГИЧЕСКИХ ЗАКОНОВ
· логика, как наука;
· алгебра высказываний;
· логические операции;
· логические функции;
· приоритет логических операций;
· тождественно истинные и тождественно ложные операции;
· основные законы алгебры логики;
· доказательство логических законов;
· простейшие преобразователи информации;
· домашнее задание.
Для того, чтобы использовать какие-либо законы в практике, необходимо быть уверенным в их правильности. Доказать закон алгебры высказываний можно:
построив таблицу истинности для правой и левой части закона;
выполнив эквивалентные преобразования над правой и левой частью формулы для приведения их к одному виду;
с помощью диаграмм Эйлера-Венна;
путем правильных логических рассуждений.
Упрощение сложных высказываний - это замена их на равносильные им на основе законов алгебры высказываний.
При упрощении сложных высказываний используются следующие основные приемы:
по свойству констант
X = Х ^ 1, Х = X V 0
по закону исключенного третьего
1= A V A
по закону противоречия
Z ^ Z = 0
по закону идемпотентности
В = В V В = B V B V B V B,
C = C ^ C = C ^ C ^ C ^ C
по закону двойного отрицания
Е = Е
Пример 1. Упростить: А ^В V А ^ В
По закону дистрибутивности вынесем А за скобки:
А ^В V А ^ В = A ^ (B V B) = А ^ 1= А
Пример 2. (первый способ)
Упростить: (А V В) ^ (А V В)
Раскроем скобки по закону дистрибутивности:
(А V В) ^ (А V В) = A V (B ^ B) =A V 0 = А
Пример 2. (второй способ)
Упростить: (А V В) ^ (А V В)
Перемножим скобки (как в обычной алгебре) на основании того же закона дистрибутивности:
(А V В) ^ (А V В) =
=A ^ A V A ^ B V B ^ A V B ^ B =
= A V A ^ (B V B) V 0 = = A V A ^ 1 = А
Пример 3.
Упростить: X V X ^ Y
На первый взгляд, пример не позволяет его упростить, так как в этом выражении ничего нельзя вынести за скобки. Заметим, что “хочется”, чтобы у переменной Х “появился” Y. Для этого представим
Х как Х ^1, а 1 распишем по закону исключенного третьего
как (Y V Y).
Далее раскроем скобки.
X ^(Y VY) V X ^ Y =
=X ^ Y V X ^ Y V X ^ Y =
добавим к полученному выражению X ^ Y.
|
|
|
Получим:
=X ^ Y V X ^ Y V X ^ Y V X ^ Y =
=X ^ (Y V Y) V Y ^ (X V X) =
=X ^ 1 V Y ^ 1 =
=X V Y
Пример 4.
Упростить: A ^ C V B ^ C V A ^ B
Один из возможных вариантов упрощения состоит в том, чтобы добавить к последнему слагаемому переменную С. Это делается стандартным способом: умножить А ^ B на 1, а 1 расписать как (С V C).
A ^ C V B ^ C V A ^ B ^ 1=
A ^ C V B ^ C V A ^ B ^ (C V C) =
A ^ C V B ^ C V A ^ B ^ C V B ^ C) =
A ^ C V B ^ C V A ^ B ^ C V A ^ B ^ C =
A ^ C ^ (1 V B) V B ^ C ^ (1 V A) =
A ^ C ^ 1 V B ^ C ^ 1 =
A ^ C V B ^ C
Пример 5.
Упростить: (X V Y)
(X V Y) =
применим закон де Моргана
X ^ Y = X ^ Y= X ^ Y
|
|
|
