Консультация 2 27 март 2012 Информатика и ИКТ ЕГЭ 2012

Основы логики таблицы истинности основных логических операций (инверсия, конъюнкция, дизъюнкция), а также импликации, тождество знание и применение основных законов логики (преобразование логических выражений) построение таблиц истинности и логических схем для логического выражения

Таблицы истинности логических операций AB Отрицание Инверсия (НЕ) ¬ A Конъюнкция Логическое умножение (И) A /\ B Дизъюнкция Логическое сложение (ИЛИ) A \/ B Следование импликация A B Тождество A Ξ B

Основные законы алгебры логики

Пример 1. Укажите, какое логическое выражение равносильно выражению ¬(A \/ ¬ B \/ C) 1) ¬A \/ B \/ ¬C 2) A /\ ¬B /\ C 3)¬A \/ ¬B \/ ¬C 4) ¬A /\ B /\ ¬C

Пример 1. Укажите, какое логическое выражение равносильно выражению ¬(A \/ ¬ B \/ C) 1) ¬A \/ B \/ ¬C 2) A /\ ¬B /\ C 3)¬A \/ ¬B \/ ¬C 4) ¬A /\ B /\ ¬C Решение: ¬(A \/ B)= ¬A /\ ¬B ¬(¬ A) = A

Пример 1. Укажите, какое логическое выражение равносильно выражению ¬(A \/ ¬ B \/ C) 1) ¬A \/ B \/ ¬C 2) A /\ ¬B /\ C 3)¬A \/ ¬B \/ ¬C 4) ¬A /\ B /\ ¬C Решение: ¬(A \/ B)= ¬A /\ ¬B ¬(¬ A) = A ¬(A \/ ¬ B \/ C) = ¬A /\ ¬(¬B) /\ ¬C =

Пример 1. Укажите, какое логическое выражение равносильно выражению ¬(A \/ ¬ B \/ C) 1) ¬A \/ B \/ ¬C 2) A /\ ¬B /\ C 3)¬A \/ ¬B \/ ¬C 4) ¬A /\ B /\ ¬C Решение: ¬(A \/ B)= ¬A /\ ¬B ¬(¬ A) = A ¬(A \/ ¬ B \/ C) = ¬A /\ ¬(¬B) /\ ¬C = ¬A /\ B /\ ¬C Ответ 4

Пример 2. Сколько различных решений имеет уравнение ((K /\L) –> (L /\ M \/ N)) = 1, где K, L, M, N – логические переменные?

KLMN ((K /\L) –> (L /\ M \/ N)) = Сколько различных решений имеет уравнение

KLMN ((K /\L) –> (L /\ M \/ N)) = Сколько различных решений имеет уравнение

KLMN ((K /\L) –> (L /\ M \/ N)) = Сколько различных решений имеет уравнение

KLMN ((K /\L) –> (L /\ M \/ N)) = Сколько различных решений имеет уравнение

KLMN ((K /\L) –> (L /\ M \/ N)) = Ответ: 15 Сколько различных решений имеет уравнение

Пример 4. Для какого целого X истинно высказывание¬ ((X>2) (X>3))?

Решение: ¬ ((X>2) (X>3))= 1 (X>2) (X>3) = 0

Пример 4. Для какого целого X истинно высказывание¬ ((X>2) (X>3))? Решение: ¬ ((X>2) (X>3))= 1 (X>2) (X>3) = = 0

Пример 4. Для какого целого X истинно высказывание¬ ((X>2) (X>3))? Решение: ¬ ((X>2) (X>3))= 1 (X>2) (X>3) = = 0 X >2и X

Пример 4. Для какого целого X истинно высказывание¬ ((X>2) (X>3))? Решение: ¬ ((X>2) (X>3))= 1 (X>2) (X>3) = = 0 X >2и X

Пример 6. Каково наибольшее целое число X, при котором истинно высказывание (50 (X+1)·(X+1)) Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1 1 = = = 1

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 2.(X 2 >50) = 0 (X+1) 2 < 50 = 1 3.(X 2 >50) = 0 (X+1) 2 < 50 = 0

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1)

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1)

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1)

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1) 50) = 0 (X+1) 2 < 50 = 1

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1) 50) = 0 (X+1) 2 < 50 = 1 [-7; 7] [-8; 6) [-7; 6)

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1) 50) = 0 (X+1) 2 < 50 = 1 [-7; 7] [-8; 6) [-7; 6) 3.(X 2 >50) = 0 (X+1) 2 < 50 = 0

Решение: (50 (X+1) 2 ) = 1 Из таблицы истинности импликации 1.(X 2 >50) = 1 (X+1) 2 < 50 = 1 x < (x+1) 50) = 0 (X+1) 2 < 50 = 1 X 2

Пример 8. Синоптик объявляет погоду на завтра и утверждает следующее: Если не будет ветра, то будет пасмурная погода без дождя Если будет дождь, то будет пасмурно и без ветра Если будет пасмурно, то будет дождь и не будет ветра Какая погода будет завтра? Решение: Выделим простые высказывания В – ветер П – пасмурно Д - дождь

Запишем высказывания Если не будет ветра, то будет пасмурная погода без дождя ¬В П /\ ¬Д

Запишем высказывания Если не будет ветра, то будет пасмурная погода без дождя ¬В П /\ ¬Д Если будет дождь, то будет пасмурно и без ветра Д П /\ ¬В

Запишем высказывания Если не будет ветра, то будет пасмурная погода без дождя ¬В П /\ ¬Д Если будет дождь, то будет пасмурно и без ветра Д П /\ ¬В Если будет пасмурно, то будет дождь и не будет ветра П Д /\ ¬В

ВПД¬В П /\ ¬ДД П /\ ¬ВП Д /\ ¬В

ВПД¬В П /\ ¬ДД П /\ ¬ВП Д /\ ¬В

ВПД¬В П /\ ¬ДД П /\ ¬ВП Д /\ ¬В

ВПД¬В П /\ ¬ДД П /\ ¬ВП Д /\ ¬В

ВПД¬В П /\ ¬ДД П /\ ¬ВП Д /\ ¬В

Простые высказывания В – ветер П – пасмурно Д - дождь В – 1 П – 0 Д – 0 Ответ: погода будет ясная, без дождя, но ветреная

Пример 9.

Решение. Дом 1Дом 2 Дом 3Дом 4

Решение. 1.Слесарь живет левее Учителя С У 2. Парикмахер живет правее Учителя У П 3. Врач живет с краю 4. Врач живет рядом с Парикмахером 5. Борис не Врач и не живет рядом с Врачом 6. Андрей живет рядом с Учителем 7. Иван живет левее Парикмахера И П 8. Иван живет через дом от Андрея

Решение. Дом 1Дом 2 Дом 3Дом 4 1.Слесарь живет левее Учителя С У 2. Парикмахер живет правее Учителя У П

Решение. Дом 1Дом 2 Дом 3Дом 4 1.Слесарь живет левее Учителя С У

Решение. Дом 1Дом 2 Дом 3Дом 4 4. Врач живет рядом с Парикмахером 3. Врач живет с краю

Решение. Дом 1Дом 2 Дом 3Дом 4 5. Борис не Врач и не живет рядом с Врачом

Решение. Дом 1Дом 2 Дом 3Дом 4 6. Андрей живет рядом с Учителем

Решение. Дом 1Дом 2 Дом 3Дом 4 7. Иван живет левее Парикмахера

Решение. Дом 1Дом 2 Дом 3Дом 4 7. Иван живет через дом от Андрея

Решение. Дом 1Дом 2 Дом 3Дом 4 Ответ: СИ, УБ, ПА, ВМ

Решение.

x1, x2, x3 – 6 решений x1, x2, x3, x4 – 8 решений x1, x2, x3, x4, x5 – 10 решений x1, x2, x3, x4, x5, x6 – 12 решений x1, x2, x3, x4, x5, x6, x7 – 14 решений Ответ: 14

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Можно выполнить замену Y1= (X1 X2) Y2= (X3 X4) Y3= (X5 X6) Y4= (X7 X8) Y5 = (X9 X10)

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Можно выполнить замену Y1= (X1 X2) Y2= (X3 X4) Y3= (X5 X6) Y4= (X7 X8) Y5 = (X9 X10) Получаем систему ¬y1 y2 = 1 ¬y2 y3 = 1 ¬y3 y4 = 1 ¬y4 y5 = 1

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Получаем систему ¬y1 y2 = 1 ¬y2 y3 = 1 ¬y3 y4 = 1 ¬y4 y5 = 1

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Получаем систему ¬y1 y2 = 1 ¬y2 y3 = 1 ¬y3 y4 = 1 ¬y4 y5 = 1

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Получаем систему ¬y1 y2 = 1 ¬y2 y3 = 1 ¬y3 y4 = 1 ¬y4 y5 = 1

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Получаем систему ¬y1 y2 = 1 ¬y2 y3 = 1 ¬y3 y4 = 1 ¬y4 y5 = 1 6 решений

Пример. ¬(X1 X2) (X3 X4) = 1 ¬(X3 X4) (X5 X6) = 1 ¬(X5 X6) (X7 X8) = 1 ¬(X7 X8) (X9 X10) = 1 Решение. Y1= (X1 X2) Y2= (X3 X4) Y3= (X5 X6) Y4= (X7 X8) Y5 = (X9 X10) Переменные y1, y2, y3, y4,y5 – независимы Каждая из них дает два решения Всего получаем 2 5 = 32 комбинации исходных переменных для одного решения, а таких решений – 6. Следовательно, всего решений исходной системы 632 = 192 Ответ: 192