Тема Преобразование логических выражений

Тема Преобразование логических выражений

Цель научиться из множества сложных логических выражений выводить простое понятное истинное значение

Задачи

1.  Вспомнить и Повторить :

1.1.  законы алгебры логики

1.2.  таблицы истинности логических операций

1.3.  приоритет операций

2.  Рассмотреть все возможные способы решения и выбрать самый рациональный.

3.  Уметь доказать рациональность найденного решения

4.  Довести до автоматизма навыки упрощения логических выражений, чтобы уложиться во временной отрезок формата ЕГЭ (10 минут на одно задание повышенного уровня сложности)

Что нужно знать[1]:

·  условные обозначения логических операций[2]

·  таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция»

·  операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = A  B

·  операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:

A ↔ B = A  B  A  B или в других обозначениях A ↔ B =

·  если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

·  логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

·  логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

·  правила преобразования логических выражений (законы алгебры логики):

Что нужно уметь: Свободно решать задачи: А3, А10, В12 (в формате ЕГЭ-2012)

Для сдачи зачета по теме необходимо:

1.  Зачет по законам алгебры логики

2.  Сдать теоретический тест

3.  Выполнить тренировочные задания:

3.1.  легкий тренажер (любые 10 заданий)

3.2.  посерьезнее - В15  http://kpolyakov. *****/download/B15.doc

3.2.1. задачи на поиск количества решений (любые 5 задач)

3.2.2. задачи на поиск наибольшего (наименьшего) значения переменной (любые 5 задач)

3.2.3. задачи на поиск значений логических переменных (любые 5 задач)

3.2.4. задачи на составление таблицы истинности (любые 5 задач)

4.  Выполнить контрольную работу (примерные задачи по уровням перечислены в разделе «Контрольно-измерительные материалы»)

1.  Рейтинг курса:

оценка – “5” соответствует проценту усвоения более 90 %,

“4”	-	75 – 90%	61 – 73 баллов
“3”	-	60 – 74%	49 – 60 баллов
“2”	-	менее 60%	Менее 49 баллов

Таблица баллов

Зачетные мероприятия	Кол-во баллов
Зачет по законам алгебры логики	3
Теоретический зачет	6
Легкий тренажер (любые 10 заданий)	10
задачи на поиск количества решений (любые 5 задач по 4 балла)	15
задачи на поиск наибольшего (наименьшего) значения переменной (любые 5 задач по 2 балла)	10
задачи на поиск значений логических переменных (любые 5 задач по 2 балла)	10
задачи на составление таблицы истинности (любые 5 задач по 3 балла)	15
Контрольная работа	12 (4+2+2+3+0,5+0,5)
Итого	81балл – 100%
Дополнительно
Олимпиадные задачи	1 задача – 10 баллов

Вопросы на зачет

1.  Сколько строчек в таблице истинности выражения с двумя переменными?, тремя?, пятью?

2.  Когда истинно высказывание А*В?

3.  Когда истинно высказывание А+В?

4.  В чем отличие математического и логического сложения?

5.  Как выразить импликацию через «не» и «или»? Докажите эту формулу.

6.  Как выразить эквивалентность через «не», «и», «или»? Докажите эту формулу.

7.  В каком порядке выполняются действия в логических выражениях?

8.  Можно ли сказать, что таблица истинности однозначно определяет

a.  Логическое выражение

b.  Логическую функцию

9.  *Чем отличается операция «исключающее или» от «или»?

10.  * Как выразить операцию «исключающее или» через «не», «и», «или»?

Критерии оценивания

Вопросы №1-8	По 0,5 баллов
Вопросы №9-10	По 1 баллу
Итого	6 баллов

Контрольно-измерительные материалы

«Удовлетворительно»

1.  Упростите логическое выражение[3]:

1.1.  А*В*А*В+В (0,5 б.)

1.2.  А*В+В+А*В (0,5 б.)

1.3.  А* (В+С) (0,5 б.)

1.4.   (А+В)+  (А+В)+А*В (0,5 б.)

1.5.   (АС)*С (0,5 б.)

2.  Решите логическое выражение

2.1.  А+В+(В(С+D)) (1б.)

3.  Сколько различных решений имеет уравнение

3.1.  (A+B)(B*C*D)=0 (1 б.)

«Хорошо»

1.  (14)Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) (K → M)  (K → (M  L  N)) истинно.

Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (2б.)

2.  A, B и С – целые числа, для которых истинно высказывание

(А = B)  ((A > B)→(B > C))  ((B > A)→(С > B))

Чему равно В, если A = 45 и C = 43? (2б.)

3.  (31)Сколько различных решений имеет уравнение

M  K  N  J (L  L) = 0 (2б.)

«Отлично»

1.  Сколько различных решений имеет уравнение

((J → K) →(M  N))  ((M  N) → (J  K))  (M  N  K  L) = 0 (3б.)

2.  (54) Сколько различных решений имеет система уравнений (4б.)

(X1  X2)  (X1  X2)  (X2  X3)  (X2  X3) = 1 (

(X2  X3)  (X2  X3)  (X3  X4)  (X3  X4) = 1

...

(X8  X9)  (X8  X9)  (X9  X10)  (X9  X10) = 0

Эталонная задача

Сколько различных решений имеет система уравнений

(X1®X2)*(X2®X3)* (X3®X4)* (X4®X5)=1

(Y1®Y2)*(Y2®Y3)* (Y3®Y4)* (Y4®Y5)=1

X3*Y3=1

Решение

1.  Помним, логическое произведение истинно тогда и только тогда, когда все множители принимают значение - истина

X	Y	X®Y
0	0	1
0	1	1
1	1	1

2.  В первых двух системах множитель представляет импликацию двух переменных.

3.  Визуально реализовать решение задачи лучше построением дерева решений:

3.1.  Найдем количество решений первых двух уравнений

X1	Y1
X2	Y2
X3	Y3
X4	Y4
X5	Y5

3.2.  А сейчас, мы вспомним про третье условие X3*Y3=1, очевидно Х1=1 и Y1=1. А значит, в дереве решений отсекаем ветку Х3=0 и ветку Y3=0

X1	Y1
X2	Y2
X3	Y3
X4	Y4
X5	Y5

Таким образом, общее количество решений равно 3*3=9

Задания для продвинутых

Задача 1[4]

Определите значение истинности высказываний A, B, C, D, если известна истинность следующих выражений:

1) (A or B) → (C and D) = 0

2) (A and D) ↔ not (B and C) = 1

3) (B or D) → (A and C) = 1

Ответ запишите в виде последовательностей нулей и единиц в порядке ABCD, где единица обозначает истинность высказывания, а ноль – ложность (например запись «0101» означает, что суждение A – ложно, B – истинно, C – ложно, D – истинно).

Задача 2

A	B	C	F
0	0	1	1
0	1	0	1
0	1	1	1
1	0	1	1
1	1	1	1

Дана логическая функция F(A, B,C) = (…and C) or not A and B, в записи которой пропущен фрагмент, обозначенный многоточием. Этой функции соответствует приведенный фрагмент таблицы истинности. Известно, что функция F(A, B,C) принимает ложные значения на всех наборах значений операндов, кроме представленных в таблице.

Выберите пропущенный фрагмент в записи функции F.

1) not B

2) not A→B

3) A→not B

4) (A or not B)

5) (not A or B)

6) A and not B

Задача 3

Упростите логическое выражение или укажите его результат (при его однозначности). Результат упрощения может содержать только операции инверсии, конъюнкции и дизъюнкции.

not (A → B) or not(A or B) or B

Комментарий по вводу ответа: операнды вводятся большими латинскими буквами; логические операции обозначаются, соответственно как not, and и or. Между названием логической операции и операндом ставится пробел; между открывающей скобкой и операндом или логической операцией пробел не ставится; между операндом или логической операцией и закрывающей скобкой пробел не ставится; между скобками пробел не ставится; перед открывающей скобкой и после закрывающей скобки ставится пробел.

Скобки используются только для изменения порядка выполнения операций. Если порядок выполнения операций очевиден из их приоритетов – дополнительное использование скобок считается ошибкой.

При однозначном ответе – истинный ответ обозначается как 1, а ложный как 0.

Пример записи ответа: (A or not B) and C

2.  Тренажер Задачи В15 в формате ЕГЭ-2012 

http://kpolyakov. *****/download/B15.doc

Если не получается С чего спортсмены начинают тренировку?

Разминка

1.  Повторить законы

2.  Повторить таблицы истинности и решить задачи №1-8 А3 формата ЕГЭ-2012 (http://kpolyakov. *****/school/ege. htm)

3.  Решить задачи на проверку истинности логического выражения №1-8 А10 формата ЕГЭ-2012 (http://kpolyakov. *****/school/ege. htm)

4.  Разминка на применение законов (в ответах к некоторым примерам допущены ошибки, постарайся их найти)[5]

5.  Теперь можно приступать к тренировке[6] (развиваем критическое мышление и чувство взаимопомощи – поможем автору исправить ошибки в ответах)

[1] http://kpolyakov. *****/download/B15.doc

[2] http://www. *****/publ/uroki/tema_2_vyskazyvanija_i_operacii_nad_nimi/

[3]
[3] . Логические уравнения // Информатика, № 14, 2011, с. 30-35.

[4](архив задач по информатике http://olymp. *****/archive/problems/)

[5] . Логические уравнения // Информатика, № 14, 2011, с. 30-35.

[6] . Логические уравнения // Информатика, № 14, 2011, с. 30-35.