ЕГЭ Урок 9 Алгебра логики

Логическое умножение (конъюнкция) «И» A B, A&B A B истинно тогда и только тогда, когда оба высказывания A и B истинны. A B истинно тогда и только тогда, когда оба высказывания A и B истинны. В официальных заданиях ЕГЭ конъюнкция обозначается символом « ». Логическое сложение (дизъюнкция) «ИЛИ» A B, A+B A B ложно тогда и только тогда, когда оба высказывания A и B ложны. A B ложно тогда и только тогда, когда оба высказывания A и B ложны. Логическое отрицание (инверсия) «НЕ» A, A, Логическое отрицание (инверсия) делает истинное выражение ложным и, наоборот, ложное – истинным. Логическое отрицание (инверсия) делает истинное выражение ложным и, наоборот, ложное – истинным. В официальных заданиях ЕГЭ инверсия обозначается символом « ». Логическое следование (импликация) A B A B ложно только тогда, когда А истинно, а В ложно. Импликация выражается через дизъюнкцию и отрицание: A B = A B

Таблица истинности для основных логических функций AB A инверсия A инверсия A B дизъюнкция A B конъюнкция A B импликация Приоритет логических операций: 1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация Приоритет логических операций: 1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация

Законы алгебры логики Закон для «ИЛИ» для «И» Коммутативный (переместительный): Логические переменные можно менять местами. A B= B A Ассоциативный (сочетательный): Логические переменные в дизъюнкциях и конъюнкциях можно объединять в группы. (A B) С=A (B C) Дистрибутивный (распределительный) Одинаковые переменные в дизъюнкциях и конъюнкциях можно выносить за скобки. (В отличие от обычной алгебры, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые.) (A B) (A С)=A (B C) Закон непротиворечия: Высказывание не может быть одновременно истинным и ложным. (Если высказывание А истинно, то его отрицание A должно быть ложным. Логическое произведение высказывания и его отрицания ложно.) A A=0

Закон для «ИЛИ» для «И» Закон исключенного третьего: Высказывание может быть только истинным или ложным, третьего не дано. (Результат логического сложения высказывания и его отрицания всегда принимает значение «истина».) A A=1 Законы де Моргана (законы общей инверсии): Общая инверсия двух логических слагаемых равносильна логическому умножению инвертированных переменных. Общая инверсия двух логических сомножителей равносильна логическому сложению инвертированных переменных. (A B)= A B (A B)= A B Закон двойного отрицания: Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание. A=A A=A Идемпотентности A A = A Законы алгебры логики (продолжение)

Закон для «ИЛИ» для «И» Контрапозиции A B = B A Законы склеивания (A B) ( A B)=B Исключение констант A 0=A, A 1=1 A 0=0, A 1=0 Снятие импликации A B= A B Снятие эквивалентности A B = (A B) ( A B) Закон поглощения A (A C) = A Законы алгебры логики (продолжение)

Задачи (ЕГЭ!) 1. Для какого из указанных значений числа Х истинно высказывание: ((X>3) (X>4)) ? ((X>3) (X>4)) ? 1) 22) 3 3) 44) 5 Решение: 1 способ Инверсия целиком применяется к импликации двух логических высказываний: ((X>3) (X>4)). Значит, для решения задачи нам надо такое значение X, при котором импликация будет ложна, тогда инверсия от нее будет истинна. Таблица истинности для основных логических функций По таблице истинности импликации видим, что она будет ложной в одном в одном-единственном случае: когда первое высказывание истинно, а второе ложно. Первое высказывание (X>3) может быть истинно только при X=4 или X=5. Второе высказывание принимает значение ЛОЖЬ только при X=4. Ответ: 3) 4 AB A A B способ Метод последовательной подстановки 1) Х=2 ((2>3) (2>4))= (0 0)= (1)=0 2) X=3 ((3>3) (3>4))= (0 0)= (1)=0 3) X=4 ((4>3) (4>4))= (1 0)= (0)=1 4) X=5 ((5>3) (5>4))= (1 1)= (1)=0 Ответ: 3) 4

2. Какое логическое выражение равносильно выражению A (B C)? 1) A B C2) A B С 3) A B C4) (A B) C) Решение: 1 способ Равносильными (или эквивалентными) называют такие логические высказывания, таблицы истинности для которых совпадают. Равносильными (или эквивалентными) называют такие логические высказывания, таблицы истинности для которых совпадают. Закон де Моргана (закон общей инверсии) Общая инверсия двух логических слагаемых равносильна логическому умножению инвертированных переменных. (A B)= A B Воспользуемся законом де Моргана для логического сложения (дизъюнкции) – раскроем скобки: Воспользуемся законом де Моргана для логического сложения (дизъюнкции) – раскроем скобки: A (B C)= A B C A (B C)= A B C К B и C применяется инверсия и меняется знак дизъюнкции ( ) на конъюнкцию ( ). К B и C применяется инверсия и меняется знак дизъюнкции ( ) на конъюнкцию ( ). Ответ: 3) A B C

Все переменные связаны дизъюнкциями (логическим сложением), значит, выражение будет истинно в случае истинности хотя бы одной переменной. В нашем случае ложность выражения возможна в единственном случае, когда А=1 ( А=0), В=1 ( В=0) и С=0. Таблицы не совпали, вариант ответа неверный. ABС A (B C) A (B C) способ Построим таблицу истинности для заданного выражения: Сразу видно, что при А=0 ( А=1) значение переменных В и С не имеет значения, так как после А идет дизъюнкция (логическое сложение), и по таблице ее истинности видим, что значение всего выражения будет равно 1. Построим аналогичные таблицы для предложенных четырех вариантов. ABС A B C A B C ) A B C

По приоритету выполнения логических операций сначала будет выполняться конъюнкция (умножение), а потом дизъюнкция (сложение). Тогда с учетом инверсии выражение всегда истинно в случае А=0 ( А=1). По приоритету выполнения логических операций сначала будет выполняться конъюнкция (умножение), а потом дизъюнкция (сложение). Тогда с учетом инверсии выражение всегда истинно в случае А=0 ( А=1). Таблицы совпали, ответ найден. Таблицы совпали, ответ найден. Ответ: 3) A B C ABС A B С A B С ABС A B C A B C ) A B С 3) A B C Высказывания А, В и С соединены только конъюнкциями (логическим умножением), а значит, все высказывание будет истинным в случае истинности только всех высказываний с учетом инверсий ( А=1, В=1, С=1, т.е. А=0, В=0, С=1) Таблицы не совпали, вариант ответа неверный.

3. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? 1) X Y Z2) X Y Z 3) X Y Z4) X Y Z XYZ X Y Z X Y Z = = = = = = = = = = = = 0 Решение: Выражение 2) X Y Z - это конъюнкция трех переменных, которая при X=1, Y=1, Z=1 принимает значение 1, а в таблице указан 0. То есть, это выражение не может быть ответом. Выражение 3) X Y Z - это дизъюнкция трех переменных, которая при X=1, Y=1, Z=1 принимает значение 1, а в таблице указан 0. То есть, это выражение не может быть ответом. Для двух оставшихся вариантов построим таблицы истинности. 1)XYZ X Y Z X Y Z = = = = = = = = = = = = 0 XYZF Таблица истинности соответствует заданной. Ответ: 4) X Y Z Таблицы не совпали, вариант ответа неверный. 4)

Ответ: 2) Y Y ((X Y) Y) X Y Y ((X Y) Y) X Y Ассоциативный (сочетательный) закон: Логические переменные в дизъюнкциях и конъюнкциях можно объединять в группы (A B) С=A (B C) Y (X (Y Y)) X Y 0 Закон непротиворечия: Высказывание не может быть одновременно истинным и ложным. (Если высказывание А истинно, то его отрицание A должно быть ложным. Логическое произведение высказывания и его отрицания ложно.) A A=0 Y (X 0) X Y Y (X 0) X Y X 0 = X Y X X Y Y X X Y X X=0 (Закон непротиворечия) X X=0 (Закон непротиворечия) Y 0 Y Y 0 Y 0 Y = 0 Y 0 = Y Y 0 = Y 4. Логическое выражение Y ((X Y) Y) X Y максимально упрощается до выражения: 1) X Y2) Y3) X4) 1 Решение: Приоритет логических операций: 1) инверсия 2) конъюнкция 3) дизъюнкция Решение: Приоритет логических операций: 1) инверсия 2) конъюнкция 3) дизъюнкция

Для данной логической схемы значение F=1 невозможно для следующей комбинации входных сигналов: 1) (0;0;1)2) (0;1;1)3) (1;0;0)4) (0;0;0) Решение: 1) A=0, B=0, C=1 ((A B) C) = ((0 0) 1) = 1 2) A=0, B=1, C=1 ((A B) C) = ((0 1) 1) = (1 1) = 0 3) A=1, B=0, C=0 ((A B) C) = ((1 0) 0) = (1 0) = 1 4) A=0, B=0, C=0 ((A B) C) = ((0 0) 0) = (0 0) = 1 Ответ: 2) (0;1;1) ИЛИ И НЕ А (0,0,1,0) В (0,1,0,0) С (1,1,0,0) (0,1,1,0)(0,1,0,0) F (1,0,1,1) 5.

Домашняя работа 8 (ЕГЭ!) 10 задач 1. Какая из данных логических формул является тождественно истинной? 1) A (A B)2) A (A B) 1) A (A B)2) A (A B) 3) (A B) A4) A B A 2. Какая из данных логических формул является тождественно ложной? 1) (A (B A))2) A B3) A B4) B A B 3. Укажите значения переменных A, B, C, D, при которых логическое выражение ( A C) (A (B D)) ложно. Ответ запишите в виде строки из четырех символов: значений переменных A, B, C, D (в указанном порядке). Так, например, строка 1100 соответствует тому что A=1, B=1, C=0, D=0. Ответ запишите в виде строки из четырех символов: значений переменных A, B, C, D (в указанном порядке). Так, например, строка 1100 соответствует тому что A=1, B=1, C=0, D=0.

Структурная формула для данной логической схемы имеет вид: 1) A B C2) A B C3) C A B4) A C B XYZN Символом N обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения N: Какое выражение соответствует N? Какое выражение соответствует N? 1) X Y Z2) X Y Z 3) (X Y) Z4) X Y Z 1) X Y Z2) X Y Z 3) (X Y) Z4) X Y Z F X Y Z НЕ ИЛИ И Для данной логической схемы значение F=0 невозможно для следующей комбинации входных сигналов (X, Y, Z): 1) (0;0;1)2) (0;1;1)3) (1;0;0)4) (0;0;0) F A B C И ИЛИ НЕ

7. Какое логическое выражение равносильно выражению (A B) C? 1) A B C2) ( A B) C 3) ( A B) C4) A B C 8. Логическое выражение (X X) (Y Y) максимально упрощается до выражения: 1) X Y2) Y3) X4) 1 9. Логическое выражение (X Y) (X Y) максимально упрощается до выражения: 1) 02) Y3) X4) Логическое выражение X Y (X Y) X максимально упрощается до выражения: 1) 02) Y3) 14) X