Алгебра
логики: основные понятия
Алгебра логики -
раздел математики. Она оперирует логическими высказываниями.
Логическое высказывание -
любое предложение в повествовательной форме, о котором можно однозначно
сказать, истинно оно или ложно. Примеры логических высказываний:
·
"Москва - столица России" (высказывание истинно).
·
"После зимы наступает осень" (высказывание ложно).
Простое высказывание -
логическое высказывание, состоящее из одного утверждения.
Сложное высказывание -
логическое высказывание, состоящее из нескольких утверждения, объединенных с
помощью "связок": союзов "и", "или (либо)",
частицы "не", связки "если, то" и др. Примеры сложных
высказываний:
1. "Иван сдает экзамен по физике и информатике".
Высказывание содержит два утвеждения, объединенных
"и":
·
Утверждение1: "Иван сдает экзамен по физике".
·
Утверждение2: "Иван сдает экзамен по информатике".
2. "Игорь решил записаться в секцию по воллейболу или баскетболу".
Высказывание содержит два утвеждения, объединенных
"или":
·
Утверждение1: "Игорь решил записаться в секцию по
воллейболу".
·
Утверждение2: "Игорь решил записаться в секцию по
баскетболу".
3. "Если Илья будет много готовиться самостоятельно и будет
заниматься с репетитором, то он поступит в ВУЗ".
Высказывание содержит три утвеждения, объединенных связкой
"если, то" и союзом "и":
·
Утверждение1: "Илья будет много готовиться
самостоятельно".
·
Утверждение2: "Илья будет заниматься с репетитором".
·
Утверждение2: "Илья поступит в ВУЗ".
Логические операции -
"связки": союзы и частицы естественного языка, образующие из
простых высказываний сложные, представленные в формальном виде.
Логическое выражение -
простое или сложное логическое высказывание, представленное в формальном виде.
Примеры логических выражений:
·
простое: A,
·
сложное: AVB→C,
где A, B, C - утверждения;
Λ, V, → - логические операции.
Законы алгебры логики -
законы, позволяющие преобразовывать логические выражения.
Логическая переменная -
переменная, которая может принимать значение 1 (истина) или 0 (ложь).
Логическая функция -
функция, аргументы и значение которой могут принимать значение 1 (истина) или 0
(ложь).
Таблица истинности -
таблица, которая используется для описания логических функций, в частности
отдельных логических операций.
Диаграммы Эйлера-Венна -
диаграммы, которые служат для наглядного представления всех вариантов
пересечения нескольких множеств. В качестве множеств могут использоваться
простые логические высказывания. Диаграмма строится для логического
высказывания, которое содержит от одного до трех утверждений
Логические
операции
Чаще всего используются следующие логические операции:
·
инверсия (отрицание, логическое не),
·
конъюнкция (логическое и),
·
дизъюнкция (логическое или),
·
импликация (следование),
·
эквивалентность (тождество).
Рассмотрим каждую из них подробно. Для описания используем диаграммы Эйлера-Венна и
таблицы истинности.
Логическая операция/
соответствие в русском языке
|
Обозначение
|
Диаграмма Эйлера-Венна
|
Таблица
истинности
|
инверсия (отрицание,
логическое "НЕ")/
"...не...", "неверно, что..."
|
¬
|
|
A
|
¬A
|
0
|
1
|
1
|
0
|
|
конъюнкция (логическое "И")/
"...и..."
|
Λ, &
|
|
A
|
B
|
AΛB
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
|
дизъюнкция (логическое "ИЛИ")
"...или...", "...либо..."
|
V
|
|
A
|
B
|
AVB
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
импликация (следование)/
"если...,то...", "когда..., тогда..."
|
→
|
|
A
|
B
|
A→B
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
|
|
|
|
|
|
|
эквивалентность (тождество)
"тогда и только тогда, когда"
|
↔, ≡
|
|
A
|
B
|
A↔B
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
Основные логические операции:
инверсия, конъюнкция, дизъюнкция.
Остальные логические операции можно выразить через них:
A→B=¬AVB;
A↔B=(AΛB)V(¬AΛ¬B).
Порядок выполнения логических операций в
выражении (от наибольшего приоритета к наименьшему):
инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.
Пример:
AV¬BΛC→D↔E.
Порядок выполнения:
1.
¬B
2.
(¬B)ΛC
3.
AV((¬B)ΛC)
4.
(AV((¬B)ΛC))→D
5.
((AV((¬B)ΛC))→D)↔E
Диаграммы Эйлера-Венна
Диаграмма Эйлера-Венна - наглядное средство для
работы со множествами. На этих диаграммах изображаются все возможные варианты
пересечения множеств. Количество пересечений (областей) n определяется по
формуле:
n=2N,
где N - количество множеств.
Таким образом, если в задаче используется два множества, то n=22=4,
если три множества, то n=23=8, если четыре множества, то n=24=16.
Поэтому диаграммы Эйлера-Венна используются в основном для двух или трех
множеств.
Множества изображаются в виде кругов (если используется 2-3
множества) и эллипсов (если используется 4 множества), помещенных в
прямоугольник (универсум).
Универсальное множество (универсум) U (в
контексте задачи) - множество, содержащее все элементы рассматриваемой задачи:
элементы всех множеств задачи и элементы, не входящие в них.
Пустое множество Ø (в
контексте задачи) - множество, не содержащее ни одного элемента рассматриваемой
задачи.
На диаграмме строят пересекающиеся множества, заключают их в
универсум. Выделяют области, количество которых равно количеству
пересечений.
Диаграммы Эйлера-Венна также используются для визуального
представления логических операций.
Разберем примеры построения диаграмм Эйлера-Венна для двух и
трех множеств.
Пример 1
Пусть есть следующие множества чисел:
А={1,2,3,4}
В={3,4,5,6}
Универсум U={0,1,2,3,4,5,6}
Диаграммы Эйлера-Венна для двух множеств А и В:
Определим
области, и числа которые им принадлежат:
А
|
B
|
Обозначение
области
|
Числа
|
0
|
0
|
0)
|
0
|
0
|
1
|
1)
|
5,6
|
1
|
0
|
2)
|
1,2
|
1
|
1
|
3)
|
3,4
|
Пример 2
Пусть есть следующие множества чисел:
А={1,2,3,4}
В={3,4,5,6}
С={1,3,6,7}
Универсум U={0,1,2,3,4,5,6,7}
Диаграммы
Эйлера-Венна для трех множеств А, В, С:
Определим
области, и числа которые им принадлежат:
А
|
B
|
C
|
Обозначение
области
|
Числа
|
0
|
0
|
0
|
0)
|
0
|
0
|
0
|
1
|
1)
|
7
|
0
|
1
|
0
|
2)
|
5
|
0
|
1
|
1
|
3)
|
6
|
1
|
0
|
0
|
4)
|
2
|
1
|
0
|
1
|
5)
|
1
|
1
|
1
|
0
|
6)
|
4
|
1
|
1
|
1
|
7)
|
3
|
Задание:
Дан фрагмент таблицы истинности выражения F:
X
|
Y
|
Z
|
F
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
Каким выражением может быть F?
1.
X /\ Y /\ Z
2.
¬X \/ ¬Y \/ Z
3.
X \/ Y \/ Z
4.
¬X /\ ¬Y /\ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=XΛYΛZ=1 только в случае,когда
X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Подходит.
F=¬XV¬YVZ. Подставляем значения из таблицы:
1V1V0=1.F=0. Следовательно, не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1.
Проверяем по таблице. Не подходит.
F=¬XΛ¬YΛ¬Z. Подставляем значения из таблицы:
1Λ1Λ1=1.F=0. Следовательно, не подходит.
Задание:
Дан фрагмент таблицы истинности выражения F.
№
области
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
F
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
2
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
3
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
Каким из приведённых ниже выражений может быть F?
1.
¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
2.
¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7
3.
x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
4.
x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7
Решение:
Сначала определим, как связаны переменные в F: с помощью
конъюнкции (Λ) или дизъюнкции (V).
Если выражение содержит только конъюнкции, то оно может быть
истинно только на одной области.
В данном случае F истинна (равна 1) на одной области (область №3
в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции.
Это вариант 1 и вариант 3.
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
F
|
F=¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
(вариант 1)
|
F=x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
(вариант 3)
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0Λ1Λ1Λ1Λ1Λ0Λ0=0
|
1Λ0Λ0Λ0Λ1Λ1Λ0=0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0Λ0Λ0Λ0Λ1Λ0Λ1=0
|
1Λ1Λ1Λ1Λ1Λ1Λ1=1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1Λ1Λ1Λ1Λ1Λ1Λ1=1
|
|
Получили вариант 1:
¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
Дан фрагмент таблицы истинности выражения F:
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
F
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
Каким выражением может
быть F?
1) x1 ∨
x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6
2) ¬x1 ∨
x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ ¬x6
3) x1 ∧
x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ x6
4) ¬x1 ∧ ¬x2
∧ x3 ∧ x4 ∧ x5 ∧ x6
Пояснение.
Посмотрим внимательно на ответы. Они представляют собой
либо конъюнкцию, либо дизъюнкцию данных пяти переменных или отрицательных
к ним. Сначала выясним, конъюнкция это или дизъюнкция.
Конъюнкция не может принимать значение единицы дважды из
трех разных комбинаций, следовательно, в ответе должна быть дизъюнкция.
Вычеркиваем 3 и 4 варианты ответа.
Из 1 и 2 вариантов подходит 2.
Правильный ответ указан под номером 2.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.