Ученики на Учителя.com


Методика решения задач ОГЭ "Системы логических уравнений"

Формулировка задания
Сколько существует различных наборов значений
логических переменных х1, х2,… (y1, y2, …), которые
удовлетворяют всем перечисленным ниже условиям:
…(система логических уравнений)
В ответе не нужно перечислять все различные наборы
х1, х2, … (y1, y2, …), при которых выполняется
данная система равенств. В качестве ответа
необходимо указать количество таких наборов
Спецификация задания №23
согласно КИМ в 2017 ( «ФИПИ»)
Характеристика
Значение
Что проверяется
Умение строить и преобразовывать
логические выражения
Требования к проверяемым
элементам содержания
Высказывания, логические операции,
кванторы, истинность высказывания
Проверяемые требования к
уровню подготовки
Вычислять логическое значение
сложного высказывания по известным
значениям элементарных высказываний
Уровень сложности
Высокий (единственный в 1-й части)
Максимальный балл
1
Примерное время
выполнения
10 мин
Особенности решения
• Задание сложное, его невозможно
формализовать;
• Большое количество приемов и методов
решения;
• Большая сложность при маленьком
количестве баллов (лучше решить №24,
чем №23);
• Требует базовых знаний по
комбинаторике.
Необходимые знания и умения
•
Базовые и дополнительные логические
операции;
•
Законы алгебры логики;
•
Структуры данных – деревья;
•
Метод замены переменных;
•
Метод отображения (динамическое
программирование);
•
Основы комбинаторики;
•
Навыки преобразования и анализа логических
выражений.
Условные обозначения (в порядке
приоритета операций)
•
отрицание (НЕ) : A , А , not A
•
конъюнкция (И) : A ˄ B , A B, AB, А&B,
A and B
•
дизъюнкция (ИЛИ) : A ˅ B , A+ B, A | B,
А or B
•
импликация (следствие) : А → B
•
эквивалентность (равенство): A В,
A B, A B
•
исключающее «или» (сложение по модулю 2) :
A B , A xor B
Базовые логические операции НЕ, И, ИЛИ
Дополнительные логические операции
Исключающее ИЛИ Импликация Эквивалентность
Необходимо знать и словесное описание операций
А
не А
0
1
1
0
A
B
А и B
0
0
0
0
1
0
1
0
0
1
1
1
A
B
А или B
0
0
0
0
1
1
1
0
1
1
1
1
A
B
А B
0
0
0
0
1
1
1
0
1
1
1
0
A
B
А → B
0
0
1
0
1
1
1
0
0
1
1
1
A
B
А ≡ B
0
0
1
0
1
0
1
0
0
1
1
1
!
Основные законы логики
Свойства логических операций
И
ИЛИ
НЕ
Название
Закон в логике
Аналог в алгебре
Переместительный
А ˅ B = B ˅ A
А + B=B + A
А ˄ B = B ˄ A
А * B=B * A
Сочетательный
(А ˅ B) ˅ C =А ˅( B˅ C)
(А + B) + C =А +( B+ C)
(А ˄ B) ˄ C =А ˄ ( B˄ C)
(А*B) * C =А *( B* C)
Распределительный
(А ˅ B) ˄ C = (А ˄ C) ˅ (B ˄ C)
(А +B) *C = (А*C) +(B*C)
(А ˄ B) ˅ C = (А ˅ C ) ˄(B˅ C)
Аналога нет
Основные законы логики
Законы де Моргана:
A B = A + B, A +B = A B
Формулы склеивания:
A B + A B = A (B + B)= A
(A +B) (A + B)= A + (B B)= A
Формулы поглощения:
A + A B = A (1+ B)= A
A (A +B) = A + (A B) = A
A + A B =
A (1+ B)+ A B =
A + A B +
A B =
= A +B (A
+
A)= A +B
Преобразование операций
A → B = A + B = B → A
(A B) =
(A B) =
A B +
A B +
A B
A B
= A B A B
=
(
A
+
B
)
(
A
+B) =
= A A
+
B A
+
A B + B B = B A
+
A B
(A B) = A B
+
A B = (A B) = A B
Метод замены переменных
Применяется, если можно выделить одинаковые
выражения в уравнениях, между которыми нет общих
переменных.
ПРИМЕР:
((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) =1
((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) =1
((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) =1
((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) =1
ЗАМЕНА:
t1 = (x1 x2)
t2 = (x3 x4)
t3 = (x5 x6)
t4 = (x7 x8)
t5 = (x9 x10)
Метод замены переменных
Получаем после преобразования
(
t1
t2
)
(
t1
t2 )= 1
t1 t2
t1 t2 = 1
t1 t2 = 1
(t2
t3) (t2 t3
)
=
1
=>
t2 t3
t2 t3 = 1
=>
t2
t3 = 1
(t3
t4
)
(
t3
t4
)
=
1
t3 t4 t3 t4 = 1
t3 t4 = 1
(t4
t5
)
(
t4
t5
)
=
1
t4 t5
t4 t5 = 1
t4 t5 = 1
Решение в новых переменных (2 набора)
t1
t2
t3
t4
t5
0
1
0
1
0
1
0
1
0
1
Метод замены переменных
Для каждой комбинации из 5-ти
значений t
1
… t
5
существует по 2
решения:
t
1
= (x
1
≡ x
2
)
t
2
= (x
3
≡ x
4
)
если t
1
= 0, то x
1
=1, x
2
=0
или x
1
=0, x
2
=1
t
3
= (x
5
t = (x
≡ x
6
)
≡ x )
если t
1
= 1, то x
1
=1, x
2
=1
или x
1
=0, x
2
=0
4 7 8
t
5
= (x
9
≡ x
10
)
То есть 2 варианта по 5 переменным дают 2
5
=32 решения,
32+32=64
Метод замены переменных
Для закрепления
Информатика и ИКТ. Подготовка к ЕГЭ-2016. 20 тренировочных вариантов по демоверсии на 2016 год: учебно-методическое
пособие / Под ред. Л. Н. Евич, С.Ю. Кулабухова. – Ростов-на-Дону: Легион, 2015.
Построение дерева вариантов
Сколько существует различных наборов
значений логических переменных х1, х2,…х8,
которые удовлетворяют всем перечисленным
ниже условиям:
Информатика и ИКТ. Подготовка к ЕГЭ-2016. 20 тренировочных вариантов по демоверсии на 2016 год: учебно-методическое
пособие / Под ред. Л. Н. Евич, С.Ю. Кулабухова. – Ростов-на-Дону: Легион, 2015.
Построение дерева вариантов
(
x1
(x2
(
x3
...
(x6
x2) (x1
x3) (x2
x4) (x3
x7) (x6
x3) = 0
x4) = 0
x5) = 0
x8) = 0
ИЛИ
(x1 x2) (x1 x3) = 1
(x2 x3) (x2 x4) = 1
(x3 x4) (x3 x5) = 1
...
(x6 x7) (x6 x8) = 1
Построение дерева вариантов
(
x1
x2
)
(
x1
x3
)
=
1
(
x2
...
(
x6
x3
)
(
x2
x7
)
(
x6
x4
)
=
1
x8
)
=
1
Для x1=1 строится точно такое же дерево, только с инвертированными
(противоположными) значениями, поскольку операция эквивалентности
симметрична относительно значений аргументов. Итого решений 34*2=68
Построение дерева вариантов
Плюсы:
-
Универсальность (можно использовать всегда);
-
Наглядность.
Минусы:
-
Громоздкость решения в некоторых случаях;
-
Сложность выявить закономерность при больших
размерностях.
Вывод: максимально упрощать выражения, при
возможности использовать частные методы
решения и логику.
!
Метод отображения
(динамическое программирование)
Используется, когда система состоит из
уравнений, отличающихся только индексами.
(x1 x2) (x1 x3) = 1
(x2
...
(x6
x3
)
x7
)
(x2
(x6
x4) = 1
x8) = 1
Метод отображения
(динамическое программирование)
(
x1
x2) (x1 x3) = 1
Значения пары (x1,x2) определяют
возможные значения переменной x3. Т.к.
другие уравнения аналогичны ,то пары
(x2,x3) влияют на x4 и т.д. Выявим
закономерности получения пар значений
(x1,x2)
(x2,x3)
00
00
01
01
10
10
11
11
x1
x2
X3
0
0
1
1
0
1
1
0
0
1
1
0
Метод отображения
(динамическое программирование)
(x1,x2)
(x2,x3)
00
00
01
01
10
10
11
11
=68
00
01
10
11
(x1,x2)
1
1
1
1
(x2,x3)
1
2
2
1
(x3,x4)
2
3
3
2
(x4,x5)
3
5
5
3
(x5,x6)
5
8
8
5
(x6,x7)
8
13
13
8
(x7,x8)
13
21
21
13
Метод отображения
(динамическое программирование)
Сложность использования: наличие
ограничений.
Проблема: Как исключить из таблицы варианты,
которые не удовлетворяют последнему
уравнению.
x1
x2
x3
0
0
0
1
1
0
1
1
0
1
1
0
1
?
Метод отображения
(динамическое программирование)
Решение: рассмотрим все пары, удовлетворяющие
последнему уравнению, построим отдельные таблицы.
1)
Пара
Количество пар
x
1
, x
2
x
2
, x
3
x
3
, x
4
x
4
, x
5
x
5
, x
6
x
6
, x
7
x
7
, x
8
x
8
, x
9
x
9
, x
10
00
1
1
1
1
1
1
1
1
1
01
1
1
2
0
5
1
6
7
13
10
0
1
2
4
0
5
6
12
19
11
0
1
2
0
0
5
6
12
19
=52
Метод отображения
(динамическое программирование)
При x1=x5=0 количество
решений 52,
При x1=x5=1 – 65
ИТОГО: 117
Пара
Количество пар
x
1
, x
2
x
2
, x
3
x
3
, x
4
x
4
, x
5
x
5
, x
6
x
6
, x
7
x
7
, x
8
x
8
, x
9
x
9
, x
10
00
0
0
0
0
0
0
0
0
0
01
0
1
1
2
0
5
5
10
15
10
1
1
2
0
5
5
10
15
25
11
1
1
2
3
5
5
10
15
25
=65
Задачи
(x1 x2) (x2
1)
(x2 x3) (x3
...
(x6 x7) (x7
x3) (x2 x3) = 0
x4) (x3 x4) = 0
x8) (x7 x8) = 0
Ответ: 149
2)
(x1 → x2) (x2 → x3) (x3 → x4) (x4 → x5) = 1
(
y1
→
y2
)
(
y2
→
y3
)
(
y3
→
y4
)
(
y4
→
y5
)
=
1
Ответ: 73
x1 y1 = 1
3)
(x1 → x2) (x2 → x3) (x3 → x4) (x4 → x5)= 1
(
y1
→
y2
)
(
y2
→
y3
)
(
y3
→
y4
)
(
y4
→
y5
)
=
1
Ответ: 5
(x1 y1) x1 = 1
Задачи
(
x1
4)
(
x2
x2) ((x1 x2) → x3) (x3
x3) ((x2 x3) → x4) (x4
y1)= 1
y2
)
=
1
Ответ: 165
...
(x6 x7) ((x6 x7) → x8) (x8 y6)= 1
(
x7 x8
)
(
y7 y8)= 1
5)
(x1 x2) (x3 ( x1 → x2)) (x1 y1) = 0
(x2 x3) (x4 ( x2 → x3)) (x2 y2) = 0
(x6 x7) (x8 ( x6 → x7)) (x6 y6) = 0
(x7 x8) (x7 y7) = 0
Ответ: 73
x8 y8 = 0
Список использованных источников
1) Информатика и ИКТ. Подготовка к ЕГЭ-2016. 20 тренировочных
вариантов по демоверсии на 2016 год: учебно-методическое
пособие / Под ред. Л. Н. Евич, С.Ю. Кулабухова. – Ростов-на-Дону:
Легион, 2015.
2) Презентация Лимаренко Андрея Ивановича, учителя информатики
гимназии 446 на тему «Мастер класс: Логические задачи. Подготовка
к ЕГЭ, В15»
3) Презентация Мирончик Ел. А., Мирончик Ек. А. на тему «Системы
логических уравнений. Метод отображения.» г. Новокузнецк, 2012.
4) Презентация Вишневской М.П., МАОУ «Гимназия №3» на тему
«Решение задания В15 (системы логических уравнений)» 2013 г., г.
Саратов .
Скачать материал

Математика - еще материалы к урокам: