Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

ЕГЭ по информатике - Задание 18 (Простым языком)



Сегодняшний урок посвящён 18 заданию из ЕГЭ по информатике.


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


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



Перейдём к практике решения задач 18 задания из ЕГЭ по информатике.


Задача (Количество чисел)

Какое количество натуральных чисел удовлетворяет логическому условию:


¬(X2 ≥ 9) ∨ ¬((X < 7) ∨ (X ≥ 10)) ?

Решение:

Натуральные числа - это целые, положительные числа. Например: 1, 2, 3, 4, и т. д.


Преобразуем первое выражение ¬(X2 ≥ 9) = (X2 < 9). Отрицание внесли в скобки. В этом случае знак, который находится в скобках, нужно поменять на противоположный.


Важно: Если было строгое неравенство, то оно станет нестрогим, и наоборот, если было неравенство нестрогим, то оно станет строгим.


Получается, что выражение (X2 < 9) будет истинно только при двух значениях: X = 1, X = 2.


Во втором выражении ¬((X < 7) ∨ (X ≥ 10)) удобно применить формулу Де Моргана.



Формула де Моргана:
¬(A ∨ B) = ¬A ∧ ¬B
¬(A ∧ B) = ¬A ∨ ¬B

Преобразуем выражение по формуле де Моргана и внесём отрицание в скобки:


¬((X < 7) ∨ (X ≥ 10)) = ¬(X < 7) ∧ ¬(X ≥ 10) = (X ≥ 7) ∧ (X < 10)

Получилось выражение (X ≥ 7) ∧ (X < 10). Между двумя выражениями стоит логическое умножение. Значит, одновременно должны выполняться и первое неравенство, и второе. Таким образом, получается, что подходят три значение для выражения (X ≥ 7) ∧ (X < 10). Это X = 7, X = 8, X = 9.


Обратимся к самому начальному логическому условию. Там два выражения соединятся логическим сложением. Значит, мы должны объединить те случаи, когда у нас первое выражение становится истинным (X=1, X=2), и те случаи, когда второе выражение становится истинным (X = 7, X = 8, X = 9).


Получается всего 5 натуральных чисел удовлетворяют изначальному логическому условию.


Ответ: 5

Разберём ещё одну разминочную задачу для подготовки к ЕГЭ по информатике.


Задача (Наибольшее число)

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


(x ≥ A) ∨ (y ≥ A) ∨ (x * y ≤ 205)

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


Решение:

Здесь есть три выражения в скобках, которые соединены логическим сложением. При логическом сложении достаточно хотя бы одного выражения, где будет истина, чтобы всё общее выражение было истинно.


Если мы сделаем A слишком большим, к примеру A = 250, то найдутся такие x = 16, y = 16, при которых все три условия в скобках не будут выполняться, и, значит, всё общее выражение будет ложным.


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


Сделаем так: пока x и y меньше A, должно "работать" третье выражение в скобках. Как только x или y сравняются с A - начинают "работать" первое или второе выражение.


До какого же максимального значения могут дойти x и y, чтобы перемножение этих двух чисел было меньше или равно 205 (x * y <= 205) ?


15 * 15 = 225
14 * 14 = 196

Получается, пока числа x и y меньше 15, "выручает" третье выражение (x * y ≤ 205), как только станут x ≥ 15 и y ≥ 15, будут "работать" первое и второе выражение.


Отсюда получаем, что максимальное число A = 15


Ответ: 15


Задача (Наибольшее число + формула де Моргана)

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


(x < A) ∧ (y < A) ∧ (x * y > 603)

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


Решение:

В этой задаче нужно, чтобы общее выражение было ложно!


Если мы поставим отрицание над всем выражением, то можно искать такое максимальное A, при котором всё выражение тождественно истинно, а не ложно!


¬((x < A) ∧ (y < A) ∧ (x * y > 603)) = ¬(x < A) ∨ ¬(y < A) ∨ ¬(x * y > 603)

Здесь применили формулу де Моргона! Т.е. каждое подвыражение получило отрицание + соединительная логическая операция (логическое умножение) сменилась на противоположную операцию (логическое сложение).


Внесём отрицание в скобки. Получается:


(x ≥ A) ∨ (y ≥ A) ∨ (x * y ≤ 603)

Получили ситуацию, как в прошлой задаче! Напомню, что теперь нужно, чтобы общее выражение было истинно.


Найдём максимальное число, до которого могут "подняться" x и y, чтобы ещё работало третье выражение!


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


Поэтому вспоминаем таблицу квадратов.


25 * 25 = 625
24 * 24 = 576

Получается, что максимальное число до которого могут "дойти" x и y, чтобы "работало" третье выражение, равно 24.


Тогда, начиная с 25 для x и y, должны работать первое и второе выражение.


Получается, что максимальное число для A равно 25.


Ответ: 25

Ещё одна задачка подобного типа из тренировочных упражнений 18 задания ЕГЭ по информатике.


Задача (Наименьшее число)

Для какого наименьшего целого числа A формула


(3 * x + y < A) ∨ (x < y) ∨ (16 ≤ x)

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


Решение:

Чтобы вся формула была тождественно истинна, нужно, чтобы хотя бы одно выражение "выдавало" истину, т.к. выражения в формуле соединяются с помощью логического сложения!


Взглянем на третье выражение. Пока x ≥ 16, всё идёт как надо. Третье выражение будет истинно, и, значит, вся формула будет истинна.


Но если x ≤ 15, то нужно, чтобы нас "спасало" первое или второе выражение.


Рассмотрим второе выражение. Пока y > x (x ≤ 15) => y > 15, у нас всё нормально, второе выражение будет истинно, и вся формула будет истинна.


Теперь обратим внимание на первое выражение. Оно должно нас "спасать", когда третье и второе выражение "не спасло"! Это возможно, если x ≤ 15 (иначе "спасло" бы третье выражение), а так же y ≤ 15 (иначе "спасало" бы второе выражение).


Но, чтобы первое выражение было всегда истинно при x ≤ 15 и y ≤ 15, мы должны подобрать число A при максимальных x и y (x=15, y=15)! Ведь для более маленьких значений выражение (3 * x + y < A) точно будет истинно.


Получается:


3 * 15 + 15 < A
60 < A

Нужно найти наименьшее число для A, при котором A > 60. Тогда там, где не "спасли" третье и второе выражение, точно "спасёт" первое выражение. Получается A = 61.


Ответ: 61


Задача (ЕГЭ по информатике, Москва, 2020)

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


(x > A) ∨ (y > x) ∨ (2 * y + x < 110)

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


Решение:

Пока y > x, второе подвыражение всегда истинно, значит, и всё выражение истинно.


Теперь будем рассматривать случай y ≤ x.


Рассмотрим третье подвыражение. Найдём максимальные значения для x и для y, которые они одновременно могут принимать, и при которых ещё выполняется третье условие.


Т.к. мы рассматриваем случай y ≤ x, то максимальное число для y будет xmax т.е. ymax = xmax.

Тогда


2 * xmax + xmax < 110

3 * xmax < 110

36 * 3 = 108
37 * 3 = 111

xmax = ymax = 36

Если x "перевалит" за 36, и при этом y ≤ x (иначе "спасает" второе подвыражение), то должно "спасать" первое выражение.


Получается, что наибольшее значение A будет равно 36.


Ответ: 36

Ещё один тип задач 18 задания ЕГЭ по информатике


Задача (числовая прямая)

На числовой прямой даны отрезки P=[5, 13] и Q=[8, 19]. Укажите наименьшую возможную длину такого отрезка A, что формула (¬(x ∈ P) → (x ∈ Q)) → (x ∈ A ) верна при любых значениях x.


Решение:

Если будут такие варианты:


ЕГЭ по информатике - задание 18 (Задача числовая прямая)


То нам беспокоится не о чём. Потому что формула всегда будет истинна! (см. таблицу истинности для следования →)


Нас же будет интересовать этот случай.


ЕГЭ по информатике - задание 18 (Задача числовая прямая, решение)

При таком раскладе вся формула будет ложна! Нам нужно этого не допустить при любом значении x!


Единица получается в первом подвыражении в трёх случаях:


1) Случай
ЕГЭ по информатике - задание 18 (Задача числовая прямая, решение, первый случай)


Выражение ¬(x ∈ P) получается ложно, когда (x ∈ P) будет истинно! Получается при x ∈ [5, 13] выражение ¬(x ∈ P) - ложно!


Выражение (x ∈ Q) ложно, когда x ∉ [8, 19]


Какой же минимальной длины должен быть отрезок A, чтобы этот случай не проходил при любом x ? При этом случае отрезок A должен быть равен [5, 8). Тогда левое выражение пусть и может стать единицей при x ∈ [5, 8), но выражение (x ∈ A) будет также равно 1 при x ∈ [5, 8)! И схема 1 → 0 не пройдёт. Будет 1 → 1.


Для 1 случая A=[5, 8).


2) Случай
ЕГЭ по информатике - задание 18 (Задача числовая прямая, решение, второй случай)


При каких x выражение ¬(x ∈ P) обращается в ноль, мы уже рассматривали: x ∈ [5, 13].


Второе выражение "выдаёт" 1 при x ∈ [8, 19].


Получается, что при при x ∈ [8; 13] первое выражение в скобках в главной формуле будет тождественно истинно!


С помощью отрезка A нужно это нейтрализовать путём превращения второго выражения в скобках в главной формуле в 1, пока x ∈ [8; 13]. Значит, для этого случая A = [8; 13]


3) Случай
ЕГЭ по информатике - задание 18 (Задача числовая прямая, решение, третий случай)


В выражении ¬(x ∈ P) единица получается, когда в выражении (x ∈ P) получается ноль. Тогда x ∉ [5, 13]!


Чтобы во втором выражении (x ∈ Q) была единица, нужно, чтобы x ∈ [8, 19].


Получается, что 3 случай выполняется, если x ∈ (13, 19].


С помощью отрезка A нужно этому противодействовать! Нужно чтобы выражение (x ∈ A) было всегда 1 при x ∈ (13, 19]. Тогда A должно быть (13, 19].


Следовательно, для третьего случая A=(13, 19].


Нам нельзя допустить ни одного случая! Поэтому, объединив все случаи, получаем, что A=[5, 19].


Длина отрезка равна 14.


Ответ: 14

Ещё одна задача про числовую прямую из банка тренировочных заданий ЕГЭ по информатике.


Задача (Числовая прямая)

На числовой прямой даны отрезки P=[5, 13] и Q=[8, 19]. Укажите наименьшую возможную длину такого отрезка A, что формула ((x ∈ P) ∧ ¬(x ∈ A)) → ((x ∈ Q) ∧ ¬(x ∈ A)) верна при любых значениях x.


Решение:

Формула может быть ложна, когда


ЕГЭ по информатике - задание 18 (Задача числовая прямая, решение 2)

Во всех остальных случаях, формула всегда верна.


Чтобы выражение ((x ∈ P) ∧ ¬(x ∈ A)) было тождественно 1, выражение (x ∈ P) обязательно должно быть тождественно 1. А, значит, x ∈ [5, 13] - это опасная зона, при которой появляется возможность обратить всю формулу в ноль!


Мы можем сразу пресечь эту опасность с помощью отрезка A. Выбрать такой отрезок, чтобы он всегда "выдавал" ложь при x ∈ [5, 13]. Для этого достаточно выбрать A=[5, 13]! Но вдруг его можно сделать ещё более маленьким за счёт правой части формулы ?


Предположим, что отрезок A сделали ещё меньшим. Тогда при каком-то x (x ∈ [5, 13]) выражение ¬(x ∈ A) будет "выдавать" 1! Причём такое же выражение стоит и в правой части формулы! Там тоже будет 1 для выражения ¬(x ∈ A).


Нас же в этом случае должно выручить выражение (x ∈ Q). Если оно "выдаст" 1 в этот "сложный" момент, то мы спасены! Ведь тогда получается, что правая часть всей формулы будет "выдавать" не 0, а 1. Посмотрим при каких x из отрезка [5, 13] приходит это спасение.


Видим, что в интервале x ∈ [8, 13] нас спасает выражение (x ∈ Q).


Значит, отрезок A можно сократить до A=[5, 8).


Длина отрезка будет равна 3!


Ответ: 3

Ещё один важный тип задач 18 задания ЕГЭ по информатике


Задача (Поразрядная конъюнкция)

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102 & 01012 = 4

Для какого наименьшего неотрицательного целого числа A формула


x&51 ≠ 0 → (x&A = 0 → x&25 ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?


Решение:

Переведём числа 51 и 25 в двоичную систему.


51 = 1100112
25 = 110012

Формула будет тождественно ложна, когда


ЕГЭ по информатике - задание 18 (Поразрядная конъюнкция)

Этого допустить нельзя!


При каком x получается в левой выражении формулы истина ? Если у икса в двоичном представлении в тех разрядах, где у числа 51 стоят 1, будет хотя бы в одном месте 1.



Рассмотрим правое выражение формулы. Ноль получается в единственном случае:


ЕГЭ по информатике - задание 18 (Поразрядная конъюнкция)

Рассмотрим выражение x&25 ≠ 0. Чтобы в этом логическом выражении получился ноль, нужно x&25 = 0. Посмотрим на двоичное представление числа 25. В тех разрядах, где стоят единицы, у икс должны быть нули (для x&25 = 0).


Сформулируем окончательное условие для x, при котором возникает опасность превращение общей формулы в ложь.


ЕГЭ по информатике - задание 18 (Поразрядная конъюнкция, схема решения)

Нам нужно "поломать эту песенку" с помощью x&A = 0. Т.е. нельзя допускать, чтобы это выражение было истинно.


Получается, что A = 1000102. Это наименьшее из возможных число, при котором мы точно себя обезопасим от того, что вся формула будет ложна.


A = 1000102 в десятичной системе будет 34.


Ответ: 34

На этом всё! Увидимся в новых уроках по подготовке к ЕГЭ по информатике!






01-08-2020 в 10:18:01





Похожая статья:

ЕГЭ по информатике - Задание 14 (Укрощение Робота)

Продолжаем подготовку к ЕГЭ по информатике, и сегодня тренируемся реша...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ЕГЭ по информатике - Задание 9
ЕГЭ по информатике - Задание 8





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy