Решение задания ЕГЭ 15. Таблица истинности логических операций

1.

Решение задания ЕГЭ 15
«руками» и программой
Учитель МАОУ гимназия №40
им. Ю.А. Гагарина
Медведькова Н.А.
Калининград, 2022г.

2.

Таблица истинности логических операций
– таблица НЕ;
– таблица И;
– импликационная таблица;
– таблица ИЛИ;
– таблица эквиваленции.
A
B
A
A&B
A B
A B
A B
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
1

3.

Порядок выполнения логических операций
– в первую очередь выполняется отрицание ;
– во вторую очередь – конъюнкция &;
– затем – дизъюнкция ;
.
– потом импликация ;
– и, наконец, низший приоритет имеет эквиваленция

4.

5.

Основные формулы преобразования

6.

Упростить выражения
Задание 1
Выразить эквиваленцию p q через отрицание, конъюнкцию,
дизъюнкцию и раскрыть скобки
ОТВЕТ
Задание 2
Упростить логическую формулу ( x & y) (x y) & x
ОТВЕТ

7.

ЕГЭ 15 сегодня
В ЕГЭ15 на сегодняшний день всего 5 типов задач:
задачи с отрезками, задачи с множествами, задачи на делимость,
на конъюнкцию и задачи на графики
• «Руками» очень удобно решаются задачи с отрезками, задачи с
множествами, решаются задачи на делимость, на конъюнкцию.
• Программой удобно решать задачи на графики

8.

Алгоритм решения ЕГЭ15 «руками»
1. Обозначить логические высказывания.
2. Упростить логическое выражение до импликации (A B) и
«читаемого» вида.
3. «Прочитать» логическое выражение.
4. Найти ответ на задание.

9.

Задачи ЕГЭ 15
Элементами множества А являются натуральные числа. Известно, что
выражение
¬(x {2, 4, 8, 12, 16}) ¬(x {3, 6, 7, 15}) ¬(x {3, 6, 7, 15}) (x A)
истинно (т. е. принимает значение 1) при любом значении
переменной х.
Определите наименьшее возможное количество элементов множества
A.
Ответ: 4

10.

Задачи ЕГЭ 15
Элементами множеств А, P, Q являются натуральные числа,
причём
P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20},
Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.
Известно, что выражение
( (x P) → (x A) ) (¬(x A) → ¬(x Q) )
истинно (т. е. принимает значение 1) при любом значении
переменной х.
Определите наименьшее возможное количество элементов в
множестве A.
Ответ: 3

11.

Задачи ЕГЭ 15
На числовой прямой даны два отрезка: P = [12, 24]
Отрезок A таков, что формула
и
Q = [18 ,30].
(x A) → ((x P) → (x Q))
истинна при любом значении переменной x.
Какое наименьшее количество точек, соответствующих нечётным
целым числам, может содержать отрезок A?
Ответ: 3

12.

Алгоритм решения ЕГЭ15 «руками»
1. Обозначить логические высказывания.
2. Упростить логическое выражение до импликации (A B) и
«читаемого» вида.
3. «Прочитать» логическое выражение.
4. Найти ответ на задание.

13.

«Читаем» логические выражения
(задания для отработки навыка)
1. ((x ∈ B) ∨ (x ∈ C) → (x ∈ A))
2. (x ∈ D) → (x ∈ C) ∨ (x ∈ A)
3. (x ∈ P) & (x ∈ Q) → (x ∈ A)
4. ((x ∈ {1, 3, 5, 7, 9, 11}) &(x ∈ {3, 6, 9, 12})) → (x ∈ A)
5. (x ∈ {3, 6, 9, 12}) & (x ∈ {1, 2, 3, 4, 5, 6}) → (x ∈ A)
6. (x ∈ A) → ((x ∈ P) & ¬(x ∈ Q))

14.

Задачи ЕГЭ15
Введём выражение m&n, обозначающее поразрядную конъюнкцию m и
n (логическое «И» между соответствующими битами двоичной записи).
Определите наименьшее натуральное число A, такое что выражение
(X & 107 = 0) → ((X & 55 ≠ 0) → (X & A ≠ 0))
тождественно истинно (то есть принимает значение 1 при любом
натуральном значении переменной X)?

15.

Программа
#(X & 107 = 0) → ((X & 55 ≠ 0) → (X & A ≠ 0))
def f(x,a):
return (x&107==0) <= ((x&55!=0) <= (x&a!=0))
for a in range(1,1000):
if all(f(x,a)==1 for x in range(1,10000)):
print(a); break
#Ответ: 20

16.

Задачи ЕГЭ 15
Введём выражение m&n, обозначающее поразрядную конъюнкцию m и
n (логическое «И» между соответствующими битами двоичной записи).
Определите наибольшее натуральное число A, такое что выражение
(( (X & 13 ≠ 0) ∨ (X & A ≠ 0)) → (X & 13 ≠0)) ∨ ((X & A ≠ 0) ∧ (X & 39 = 0))
тождественно истинно (то есть принимает значение 1 при любом
натуральном значении переменной X)?
Ответ: 8

17.

Программа
# (( (X & 13 ≠ 0) ∨ (X & A ≠ 0)) → (X & 13 ≠0)) ∨ ((X & A ≠ 0) ∧ (X & 39 = 0))
def f(x,a):
return (((x&13!=0) or (x&a!=0)) <= (x&13!=0)) or ((x&a!=0) and
(x&39==0))
for a in range(1000):
if all(f(x,a)==1 for x in range(10000)):
print(a)
#Ответ: 13

18.

Задачи ЕГЭ 15
Обозначим через ДЕЛ(n, m) утверждение «натуральное
число n делится без остатка на m». Для какого наименьшего
натурального числа А формула
(ДЕЛ(x, 15) ∧ ¬ДЕЛ(x, 21)) → (¬ДЕЛ(x, A) ∨ ¬ДЕЛ(x, 15))
тождественно истинна (то есть принимает значение 1 при любом
натуральном значении переменной х)?

19.

Программа
#(ДЕЛ(x, 15) ∧ ¬ДЕЛ(x, 21)) → (¬ДЕЛ(x, A) ∨ ¬ДЕЛ(x, 15))
def f(x,a):
return ((x%15==0) and (x%21!=0)) <= ((x%a!=0) or (x%15!=0))
for a in range(1,100):
if all(f(x,a)==1 for x in range(1,1000)):
print(a);break
#Ответ: 7

20.

Задачи ЕГЭ 15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n
делится без остатка на натуральное число m». Для какого
наименьшего натурального числа A формула
ДЕЛ(A, 7) ∧ (ДЕЛ(240, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(780, x)))
тождественно истинна (то есть принимает значение 1 при любом
натуральном значении переменной х)?

21.

Программа
#ДЕЛ(A, 7) ∧ (ДЕЛ(240, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(780, x)))
def f(x,a):
return (a%7==0) and ((240%x==0) <= ((a%x!=0)<=(780%x!=0)))
for a in range(1,1000):
if all(f(x,a)==1 for x in range(1,10000)):
print(a);break
#Ответ: 420

22.

Задачи ЕГЭ 15
Найдите максимальное значение параметра А, при котором
выражение
(2х + у ≠ 70) ∨ (x < y) ∨ (A < x)
истинно (т.е. принимает значение 1) при любых неотрицательных
значениях x и у.

23.

Программа
#(2х + у ≠ 70) ∨ (x < y) ∨ (A < x)
def f(x,y,a):
return ((2*x+y!=70) or (x<y)or (a<x))
for a in range(1,200):
if all(f(x,y,a) for x in range(1,2000) for y in range(1,2000)):
print(a)
#Ответ: 23

24.

Задачи ЕГЭ 15
Для какого наименьшего целого значения параметра А существует
выражение
(x > 39) ∨ (y > 26) ∨ (2x + 4y < A)
является тождественно истинным, то есть принимает значение 1
при любых целых положительных значениях переменных х и у.

25.

Программа
#(x > 39) ∨ (y > 26) ∨ (2x + 4y < A)
def f(x,y,a):
return ((x>39) or (y>26) or(2*x+4*y<a))
for a in range(1,500):
if all(f(x,y,a) for x in range(1,5000) for y in range(1,5000)):
print(a);break
#Ответ: 183

26.

Ответ: B A & C
((A B) (B C)) == (A + B) (B + C) == (A + B) (B * C) ==
== (A + B) + (B * C) == (A * B) + (B * C) == (A * B) * (B * C) ==
== (A + B) * (B + C) == (A +B) * (B + C) == A * B + B + A * C + B * C ==
== B * (A + 1 + C) + A *C == B * 1 + A *C == B + A * C == B A & C
НАЗАД

27.

Ответ: ( p q) & (p q)
p q ==
== ( p q) & (p q) ==
== (p q) & (q p) ==
== (( p q) & q) (( p q) & p) ==
== ( q & p) 0 0 (p & q) ==
== ( q & p) (p & q) ==
== p & q q & p
НАЗАД

28.

Ответ: x y
( x & y) (x y) & x ==
== ( x y) ( x y) &x ==
== (x y) x &( x y)==
== (x y) (x & x) (x & y)==
== (x y) 0 (x y) ==
== x y x & y ==
== x y y & x == x y
НАЗАД