Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Теория для уроков по алгебре логики

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



Осталось всего 2 дня приёма заявок на
Международный конкурс "Мириады открытий"
(конкурс сразу по 24 предметам за один оргвзнос)


  • Информатика

Поделитесь материалом с коллегами:

hello_html_648175e3.gifhello_html_m10e7ed94.gifАлгебра логики: основные понятия

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

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

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

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

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

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

1. "Иван сдает экзамен по физике и информатике".

Высказывание содержит два утвеждения, объединенных "и":

  • Утверждение1: "Иван сдает экзамен по физике".

  • Утверждение2: "Иван сдает экзамен по информатике".

2. "Игорь решил записаться в секцию по воллейболу или баскетболу".

Высказывание содержит два утвеждения, объединенных "или":

  • Утверждение1: "Игорь решил записаться в секцию по воллейболу".

  • Утверждение2: "Игорь решил записаться в секцию по баскетболу".

3. "Если Илья будет много готовиться самостоятельно и будет заниматься с репетитором, то он поступит в ВУЗ".

Высказывание содержит три утвеждения, объединенных связкой "если, то" и союзом "и":

  • Утверждение1: "Илья будет много готовиться самостоятельно".

  • Утверждение2: "Илья будет заниматься с репетитором".

  • Утверждение2: "Илья поступит в ВУЗ".

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

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

  • простое: A,

  • сложное: AVB→C, 

где A, B, C - утверждения;

Λ, V, → - логические операции.

Законы алгебры логики - законы, позволяющие преобразовывать логические выражения.

Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).

Логическая функция - функция, аргументы и значение которой могут принимать значение 1 (истина) или 0 (ложь). 

Таблица истинности - таблица, которая используется для описания логических функций, в частности отдельных логических операций.

Диаграммы Эйлера-Венна - диаграммы, которые служат для наглядного представления всех вариантов пересечения нескольких множеств. В качестве множеств могут использоваться простые логические высказывания. Диаграмма строится для логического высказывания, которое содержит от одного до трех утверждений



Логические операции

Чаще всего используются следующие логические операции:

  • инверсия (отрицание, логическое не),

  • конъюнкция (логическое и),

  • дизъюнкция (логическое или),

  • импликация (следование),

  • эквивалентность (тождество).

Рассмотрим каждую из них подробно. Для описания используем диаграммы Эйлера-Венна и таблицы истинности.

Логическая операция/
соответствие в русском языке

Обозначение

Диаграмма Эйлера-Венна

Таблица 
истинности

инверсия (отрицание, логическое "НЕ")/

"...не...", "неверно, что..."

¬

C:\Users\Учитель\Desktop\logika_ne.jpg



A

¬A




0

1




1

0


конъюнкция (логическое "И")/

"...и..."

Λ, &

C:\Users\Учитель\Desktop\logika_i.jpg



A

B

AΛB




0

0

0




0

1

0




1

0

0




1

1

1


дизъюнкция (логическое "ИЛИ")

"...или...", "...либо..."

V

C:\Users\Учитель\Desktop\logika_ili.jpg



A

B

AVB




0

0

0




0

1

1




1

0

1




1

1

1


импликация (следование)/

"если...,то...", "когда..., тогда..."

C:\Users\Учитель\Desktop\logika_impl.jpg



A

B

A→B




0

0

1




0

1

1




1

0

0




1

1

1








эквивалентность (тождество)

"тогда и только тогда, когда"

, ≡

C:\Users\Учитель\Desktop\logika_ekviv.jpg



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ΛCDE.

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

  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}

Диаграммы Эйлера-Венна для двух множеств А и В:

C:\Users\Учитель\Desktop\diagram_eiler_venna2.jpg

Определим области, и числа которые им принадлежат:

А

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}

Диаграммы Эйлера-Венна для трех множеств А, В, С:

C:\Users\Учитель\Desktop\diagram_eiler_venna3.jpg



Определим области, и числа которые им принадлежат:

А

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.





57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


Автор
Дата добавления 26.01.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров128
Номер материала ДВ-379179
Получить свидетельство о публикации
Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх