Теория для уроков по алгебре логики

Раздел Информатика
Класс 8 класс
Тип Другие методич. материалы
Автор
Дата
Формат docx
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

Теория для уроков по алгебре логикиТеория для уроков по алгебре логикиАлгебра логики: основные понятия

Алгебра логики - раздел математики. Она оперирует логическими высказываниями.

Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно. Примеры логических высказываний:

  • "Москва - столица России" (высказывание истинно).

  • "После зимы наступает осень" (высказывание ложно).

Простое высказывание - логическое высказывание, состоящее из одного утверждения.

Сложное высказывание - логическое высказывание, состоящее из нескольких утверждения, объединенных с помощью "связок": союзов "и", "или (либо)", частицы "не", связки "если, то" и др. Примеры сложных высказываний:

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.

Порядок выполнения:

  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.



© 2010-2022