Презентация на тему: "Презентация по информатике на тему "Методы решения задач ЕГЭ №2" по информатике (11 класс)"

Подготовка к КЕГЭ по информатике в 2022г.
Методы решения задачи ЕГЭ №2
Учитель информатики
МАОУ «МСОШ №16»
г. Миасс
Горяинов С.И.
Миасс, 2022

Задание №2
(базовый уровень, время 3 минуты)
Тема: Алгебра логики

Спецификация: Умение строить таблицы истинности и логические схемы

Алгебра логики
Что проверяется:
1.5.1. Высказывания, логические операции, кванторы, истинность высказывания
1.1.6. Уметь строить и анализировать таблицы истинности для логического высказывания
Что нужно знать:
Таблицы истинности основных логических операций: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность
Правила преобразования логических выражений
Приоритеты логических операций

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

Правила преобразования логических выражений
𝐴∙ 𝐴 =0, 𝐴+ 𝐴 =1
𝐴∙1=𝐴,𝐴∙0=0,𝐴+1=1, 𝐴+0=𝐴
𝐴∙𝐴=𝐴, 𝐴+𝐴=𝐴
𝐴+𝐵𝐶= 𝐴+𝐵 ∙ 𝐴+𝐶
𝐴∙ 𝐵+𝐶 =𝐴∙𝐵+𝐴∙𝐶
𝐴+𝐴∙𝐵=𝐴,𝐴∙ 𝐴+𝐵 =𝐴
𝐴∙𝐵 = 𝐴 + 𝐵 , 𝐴+𝐵 = 𝐴 ∙ 𝐵

Приоритеты логических операций
Действия в скобках;
Отрицание;
Логическое умножение;
Логическое сложение;
Импликация;
Эквивалентность.

Пример задания

Алгоритм решения
Составляем полную таблицу истинности, в которой порядок переменных определен;
Оставляем только те строки, в которых значение функции совпадает со значением функции из таблицы в формулировке задания;
Сопоставляем две таблицы, опираясь на количество нулей и единиц в столбцах и строках.

Составляем таблицу истинности вручную
𝐹= 𝑌→𝑋 + 𝑍→𝑊 + 𝑍

Сопоставление таблиц
Z может находиться только в третьем столбце – только там можно поставить три единицы;
W может находиться только в четвёртом столбце – только там можно поставить три нуля;
Заполним нули и единицы в частично заполненной таблице:




Сопоставим строки: в заполненной таблице есть строка с двумя единицами и двумя нулями. При этом столбцы Z и W уже определены. Это значит, что, сравнивая вторые строки обоих таблиц, получаем, что X – это второй столбец (в нём стоит 1), а Y – это первый столбец (в нём стоит 0).
Ответ: YXZW

Построение таблицы истинности кодом
Строить таблицу истинности вручную достаточно долго, плюс увеличивается вероятность ошибки, поэтому:
Преобразуем выражение, избавляясь от импликаций и раскрывая отрицания. Это позволит упростить логическое выражение, записываемое на языке программирования, а также не допустить ошибки в расставлении скобок для соблюдения приоритета операций:
𝐹= 𝑌→𝑋 + 𝑍→𝑊 + 𝑍 = 𝑌 +𝑋 + 𝑍 +𝑊+ 𝑍 =𝑌∙ 𝑋 + 𝑍 +𝑊
Реализуем перебор всех возможных значений X, Y, Z, W на каком-либо языке программирования и проверяем, что значение функции при этих наборах значений ложно.

Универсальный вариант кода
Он заключается в переборе всех возможных значений переменных в нескольких циклах:
Реализация на Python:




Реализация на С++:

Реализация на Python
На языке Python реализовать рассмотренный выше код можно немного компактней: