- Преподавателю
- Информатика
- Теория для уроков по алгебре логики
Теория для уроков по алгебре логики
Раздел | Информатика |
Класс | 8 класс |
Тип | Другие методич. материалы |
Автор | Трофимова Н.С. |
Дата | 25.12.2015 |
Формат | docx |
Изображения | Есть |
Алгебра логики: основные понятия
Алгебра логики - раздел математики. Она оперирует логическими высказываниями.
Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно. Примеры логических высказываний:
-
"Москва - столица России" (высказывание истинно).
-
"После зимы наступает осень" (высказывание ложно).
Простое высказывание - логическое высказывание, состоящее из одного утверждения.
Сложное высказывание - логическое высказывание, состоящее из нескольких утверждения, объединенных с помощью "связок": союзов "и", "или (либо)", частицы "не", связки "если, то" и др. Примеры сложных высказываний:
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
AΛB
0
0
0
0
1
0
1
0
0
1
1
1
дизъюнкция (логическое "ИЛИ")
"...или...", "...либо..."
V
A
AVB
0
0
0
0
1
1
1
0
1
1
1
1
импликация (следование)/
"если...,то...", "когда..., тогда..."
→
A
A→B
0
0
1
0
1
1
1
0
0
1
1
1
эквивалентность (тождество)
"тогда и только тогда, когда"
↔, ≡
A
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.
Порядок выполнения:
-
¬B
-
(¬B)ΛC
-
AV((¬B)ΛC)
-
(AV((¬B)ΛC))→D
-
((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?
-
X /\ Y /\ Z
-
¬X \/ ¬Y \/ Z
-
X \/ Y \/ Z
-
¬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?
-
¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
-
¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7
-
x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
-
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.