Решение задачи ЕГЭ по информатике по теме «Основные понятия математической логики»

Пузырев С. В., учитель информатики МБОУ «СОШ №1»

Менделеевского муниципального района РТ

Решение задачи ЕГЭ по информатике по теме «Основные понятия математической логики»

Демо-вариант ЕГЭ 2020 по информатике

Для какого наименьшего целого неотрицательного числа A выражение

тождественно истинно, т. е. принимает значение 1 при любых целых неотрицательных x и y.

Решение:

Способ 1 (графический).

,

т. е. какие бы целые x, y мы бы не взяли, необходимо, чтобы все выражение было истинным.

Попробуем разобраться на конкретных примерах:

x	y	F
10	20	1
40	50	1
40	20	1
20	10

В трех первых примерах срабатывает вторая, третья скобка данного выражения или же обе сразу. В четвертом примере однозначно сказать, что данное выражение истинно или ложно нельзя, но можно добиться истинности всего выражения, если первая скобка данного выражения окажется истинной.

2) Условно поделим выражение на 2 части: известная – 2-ая и 3-я скобки и неизвестная – зависящая от А.

3) Отрицаем известную часть выраженият. е. будем добиваться истинности первой скобки при ложности второй и третьей скобки данного выражения. Нам необходимо подобрать такое A, чтобы первая скобка всегда давала истину при любых значениях x и y.

Для удобства воспользуемся законом Де Моргана

Построим графики функций:

 

Т. е. для любых точек из данного треугольника, при подстановке x и y мы получаем ложное выражение.

Мы должны добиться, чтобы выражение =1, т. е. наша задача состоит в том, чтобы взять такое А, при котором =1.

Перепишем данное выражение в удобном виде , данное выражение должно выполняться для всех точек x и y.

Наша задача сводится к нахождению наибольшего значения суммы .

x_max=30, y_max=30.

A_min=91.                                  

Способ 2 (подстановка)

31

30

29

…

Количество решений – сумма арифметической прогрессии

x=30, y=30	30+2*30<A,	90<A
x=30, y=29	30+2*29<A,	88<A
…	…	…
x=1, y=1	1+2*1<A,	3<A
x=1, y=0	1+2*0<A,	1<A
x=0, y=0	0+2*0<A,	0<A.

Так как наша задача подобрать A, превращающее в истину первое выражение при любых значениях x, выбираем самое «сильное» из неравенств, т. е. A>90, следовательно, A = 91.

Демо-вариант ЕГЭ 2019 по информатике

Для какого наибольшего целого неотрицательного числа A выражение

тождественно истинно, т. е. принимает значение 1 при любых целых неотрицательных x и y.

Решение:

Способ 1 (подбором).

Поделим данное выражение на 2 части: известную и неизвестную (зависящую от А). Если первая скобка в данном выражении – истина, то данное выражение – истина и выражение не зависит от выбора А. То есть нас интересуют случаи, где первая скобка дает ложь. Если первая скобка – ложь, то вторая часть данного выражения должна давать истину.

Задача сводится к нахождению x, y, таких, что мы получаем ложь в первой части, а затем подбираем к ним А, так, чтобы получить истину.

Если первая часть – ложь, то для нахождения x и y, необходимо решить уравнение в целых числах:

X	y	A<x или A<y	A	Комментарий
24	0	A<24 или A<0	A=23	Например, не подходит для следующей пары чисел x и y: ((23<23)=0 или (23<2) =0)=0
23	2	A<23 или A<2	A=22	Например, не подходит для следующей пары чисел x и y: ((22<22)=0 или (22<4) =0)=0
22	4	A<22 или A<4	A=21	Например, не подходит для следующей пары чисел x и y: ((21<21)=0 или (22<6) =0)=0
…
1	46	A<1 или A<46	A=46	Например, не подходит для следующей пары чисел x и y: ((46<24)=0 или (46<0) =0)=0
0	48	A<0 или A<48	A=47	Например, не подходит для следующей пары чисел x и y: ((47<24)=0 или (47<0) =0)=0

Задача сводится  к нахождению максимально близких x и y.

3x=48

x=16

Проверим наше предположение, возьмем точку x=16, а также точки, близкие к 16.

X	y	A<x или A<y	A	Комментарий
16	16	A<16 или A<16	A=15	Подходит ко всем случаям
15	18	A<15 или A<18	A=17	Например, не подходит для следующей пары чисел x и y: ((17<16)=0 или (17<16) =0)=0
17	14	A<17 или A<14	A=16	Например, не подходит для следующей пары чисел x и y: ((16<16)=0 или (16<16) =0)=0

Ответ: 15.

Способ 2 (графический) (использован материал с сайта Полякова К. Ю.)

Начертим график функции , (нужно учесть, что x и y неотрицательны и добавить ещё два ограничения:)

по условию задачи нужно, чтобы все точки отрезка прямой y = –2x + 48 в первой четверти плоскости оказались в заштрихованной зоне, поэтому все точки образовавшегося квадрата, в том числе и его вершина (A, A), должны находиться строго под этим отрезком; такой квадрат, соответствующий максимальному значению A, выделен на рисунке штриховкой. Находим координаты вершины квадрата: находим точку пересечения прямых y = –2x + 48 и y = x; эта задача сводится к линейному уравнению x = –2x + 48, решение которого – x = 16, значение A должно быть меньше этого x, поэтому максимальное значение A = 15.