Задача 1. A, B - некоторые множества. Постройте граф логической зависимости для высказываний 1-5:
1) B = A; 2) A¢ÇB = B; 3) A¢ = B¢; 4) A Í ય; 5) ADB¢ Í Æ.
Пусть M - множество рассмотренных выше пяти высказываний. R - бинарное отношение, заданное на M следующим образом: "x,yÎM (x R y Û y - логическое следствие x). Проверьте свойства (рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, линейность) отношения R.
Теперь посмотрите на отношение R как на соответствие из M в M и проверьте свойства (однозначность, всюду определенность, разнозначность, соответствие ”на”) этого соответствия.
 |
Решение: Рассмотрим диаграмму Эйлера для множеств A и B (рисунок 4).
Исследуем, какие области на диаграмме должны отсутствовать, чтобы выполнялось каждое из высказываний 1-5.
1) B = A
Очевидное условие: области 2 и 1 должны быть пустыми.
2) A¢ÇB = B
Множество A¢ состоит из областей 0 и 2, а множество B - из областей 2 и 3, тогда A¢ÇB состоит из области 2. С другой стороны, множество B состоит из областей 2 и 3. Чтобы выполнилось условие A¢ÇB = B, область 3 должна быть пустой, т.е. множества A и B не пересекаются.
3) A¢ = B¢
Очевидно, что A¢ = B¢ тогда и только тогда, когда A = B, т.е. высказывание 3 равносильно высказыванию 1.
4) A Í ય
Это высказывание истинно, так как универсальное множество включает в себя все рассматриваемые множества.
5) ADB¢ Í Æ
Множество, которое включается в пустое множество, само является пустым, т.е. ADB¢ = Æ.
Заметим, что ADB¢ = (A\B¢)È(B¢\A). Множество A\B¢ состоит из области 3, множество B¢\A состоит из области 0, тогда множество ADB¢ состоит из областей 3 и 0. Поскольку ADB¢ = Æ, то области 3 и 0 должны быть пустыми. В этом случае A = B¢.
Теперь построим граф логической зависимости для высказываний 1-5.
а) Очевидно, что каждое высказывание равносильно себе, т.е. X «X.
б) Истинное высказывание 4 логически следует из любого высказывания, т.е. 1 ® 4, 2 ® 4, 3 ® 4, 4 ® 4, 5 ® 4.
в) Высказывания 1 и 3 равносильны, т.е. 1 «3.
г) Между высказываниями 1 и 2 нет никакой логической зависимости, следовательно, между высказываниями 3 и 2 тоже нет логической зависимости.
д) Аналогично, нет логической зависимости между высказываниями 1 и 5, 3 и 5.
е) Рассмотрим высказывания 2 и 5. Высказывание 2 (A¢ÇB = B) равносильно тому, что A и B не пересекаются. Высказывание 5 (ADB¢ Í Æ) равносильно тому, что A = B¢. Если A и B не пересекаются, то не обязательно A = B¢, т.е. 5 не следует из 2. Если A = B¢, то A и B не пересекаются, т.е. 5 ® 2.
 |
Итак, изобразим граф логической зависимости для высказываний 1-5:
Продолжим решение задачи 1. Пусть M - множество рассмотренных выше пяти высказываний. R - бинарное отношение, заданное на M следующим образом: "x,yÎM (x R y Û y - логическое следствие x). Проверим свойства отношения R.
а) Рефлексивность: "xÎM (x R x)
Поскольку каждое высказывание равносильно себе, то рефлексивность выполняется.
б) Симметричность: "x,yÎM (x R y Þ y R x)
Отношение R не симметрично, т.к., например, 1 ® 4, но 1 не следует из 4.
в) Транзитивность: "x,y,zÎM (x R y & y R z Þ x R z)
Отношение R транзитивно, т.к. если x ® y и y ® z, то x ® z.
г) Антирефлексивность не выполняется, т.к. выполняется рефлексивность.
д) Антисимметричность: "x,yÎM (x R y & y R x Þ x=y)
Отношение R не антисимметрично, т.к., например, 1 ® 3 и 3 ® 1, но 1¹3.
е) Линейность: "x,yÎM (x R y Ú y R x Ú x=y)
Отношение R не линейно, т.к., например, между высказываниями 1 и 2 нет логической зависимости и 1¹2.
Итак, отношение R рефлексивно, не симметрично, транзитивно, не антирефлексивно, не антисимметрично, не линейно.
Продолжим решение задачи 1.
Посмотрим на отношение R как на соответствие из M в M и проверим свойства этого соответствия.
а) Однозначность не выполняется, т.к., например, 1 ® 3 и 1 ® 4, т.е. элемент 1 имеет более одного образа.
б) Всюду определенность выполняется, т.к. каждое высказывание следует из себя.
в) Разнозначность не выполняется, т.к., например элемент 4 имеет более одного прообраза (4 следует из всех высказываний).
г) Поскольку каждое высказывание следует из себя, то соответствие является соответствием «на» (у каждого элемента есть хотя бы один прообраз).
Задача 2 аналогична задаче 1, но по условию требуется построить только граф логической зависимости (не нужно проверять свойств бинарного отношения и свойств соответствия).
Задача 3. Постройте граф логической зависимости для высказываний 1-3 о натуральных числах a, b:
1) a>b; 2) a+b3=3; 3) a=7 Þ b=9.
Решение:
а) Очевидно, что из первого высказывания не следует второе. Например, «10>3» - истинное высказывание, но «10+33=3» - ложное, т.е. импликация «a>b Þ a+b3=3» ложна.
б) Проверим, будет ли из второго высказывания следовать первое. Высказывание «a+b3=3» истинно лишь при a=2, b=1, следовательно «a>b». Итак, из второго высказывания следует первое.
в) Проверим, будет ли из первого высказывания следовать третье. Пусть высказывание «a>b» истинно, а «a=7 Þ b=9» - ложно, т.е. a=7 и b¹9. Выберем, например, a=7 и b=2. Высказывание «7>2» истинно, но высказывание «a=7 Þ b=9» ложно, следовательно, импликация «a>b Þ (a=7 Þ b=9)» ложна, т.е. из первого высказывания не следует третье.
г) Очевидно, что из третьего высказывания не следует первое. Например, при a=10, b=23 высказывание «a=7 Þ b=9» истинно (посылка импликации ложна), а высказывание «a>b» - ложно.
д) Проверим, будет ли из второго высказывания следовать третье. Как мы вясняли ранее, высказывание «a+b3=3» истинно лишь при a=2, b=1, но при этом наборе значений a и b высказывание «a=7 Þ b=9» истинно (посылка импликации ложна). Итак, из второго высказывания следует третье.
е) Очевидно, что из третьего высказывания не следует второе. Например, при a=5, b=2 высказывание «a=7 Þ b=9» истинно (посылка импликации ложна), а высказывание «a+b3=3» - ложно.
Итак, изобразим граф логической зависимости для высказываний 1-3:
 |
