18 задание егэ информатика объяснение

1. Пример из демонстрационного варианта

(первая буква согласная → вторая буква согласная) / (предпоследняя буква гласная → последняя буква гласная)

1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

Набросок решения Импликация a → b равносильна выражению ¬a / b.

Первая импликация верна для слов КРИСТИНА и СТЕПАН. Из этих слов вторая импликация верна только для слова КРИСТИНА.

Ответ: 1. КРИСТИНА

2.Еще два примера

Пример 1 (открытый сегмент банка ФИПИ)

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

(первая буква согласная → первая буква гласная) / (последняя буква гласная → последняя буква согласная)

1. ИРИНА 2. МАКСИМ 3. АРТЁМ 4. МАРИЯ

Набросок решения . Импликация a → b равносильна выражению ¬a / b. Это выражение истинно если или выражение a ложно, или оба выражения a и b истинны. Поскольку в нашем случае ни в одной из импликаций оба выражения одновременно истинными быть не могут, то должны быть ложными утверждения «первая буква согласная» и «последняя буква гласная», то есть нам нужно слово, у которого первая буква гласная, а последняя - согласная.

Ответ: 3. АРТЁМ.

Пример 2. Для какого из указанных значений числа X истинно высказывание

(X < 4)→(X >15)

1) 1 2) 2 3) 3 4) 4

Решение. Никакое число не может быть одновременно меньше 4 и больше 15. Поэтому импликация истинна только, если посылка X < 4 ложна.

Ответ 4.

2. Задачи в формате ЕГЭ 2013-2014 гг.

2.1. Демо-версия 2013 г.

На числовой прямой даны два отрезка: P = и Q = .

Выберите такой отрезок A, что формула

1) 2) 3) 4)

2.2. Демо-версия 2014 г.

На числовой прямой даны два отрезка: P = и Q = . Выберите из предложенных отрезков такой отрезок A, что логическое выражение

((x ∈ P) → ¬ (x ∈ Q))→ ¬ (x ∈ А)

тождественно истинно, то есть принимает значение 1 при любом значении переменной

Варианты ответов: 1) 2) 3) 4)

Решение. Преобразуем выражение, используя . Имеем:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ А)) - замена импликации дизъюнкцией;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ А)) - замена импликации дизъюнкцией;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ А)) - правило де Моргана и снятие двойного отрицания;

(x ∈ А) → ((x ∈ P) ∧ (x ∈ Q)) - замена дизъюнкции импликацией

Последнее выражение является тождественно истинным тогда и только тогда, когда A ⊆ P∩ Q = ∩ = (см. ). Из четырех данных отрезков этому условию удовлетворяет только отрезок - вариант №2.

Ответ: - вариант №2

3. Задачи в формате ЕГЭ 2015-2016 гг.

3.1. Задача 1.

На числовой прямой даны два отрезка: P = и Q = .

Известно, что границы отрезка A - целочисленные точки и для отрезка A, формула

((x ∈ А) → (x ∈ P)) \/ (x ∈ Q)

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

Какова наибольшая возможная длина отрезка A?

Правильный ответ: 10

Решение:

Преобразуем выражение – заменим импликацию дизъюнкцией. Получим:

(¬(x ∈ А)) \/ ((x ∈ P)) \/ (x ∈ Q)

Выражение ((x ∈ P)) \/ (x ∈ Q) истинно для тех только тех x, которые лежат либо в P, либо в Q, иными словами – для x ∈ R = P ∪ Q = ∪ . Выражение

(¬(x ∈ А)) \/ (x ∈ R)

тождественно истинно тогда и только тогда, когда A ∈ R. Так как A – отрезок, то A ∈ R тогда и только тогда, когда A ∈ P или A ∈ Q. Так как отрезок Q длиннее отрезка P, то наибольшая длина отрезка A достигается, когда A = Q = . Длина отрезка A в этом случае равна 30 – 20 = 10.

3.2. Задача 2.

Обозначим через m &n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14&5 = 1110 2 &0101 2 = 0100 2 = 4. Для какого наименьшего неотрицательного целого числа А формула

x &25 ≠ 0 → (x &33 ≠ 0 → x &А ≠ 0)

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

Правильный ответ: 57

Решение:

Преобразуем выражение – заменим импликации дизъюнкциями. Получим:

¬(x &25 ≠ 0) ∨ (¬(x &33 ≠ 0) ∨ x &А ≠ 0)

Раскроем скобки и заменим отрицания неравенств равенствами:

x &25 = 0 ∨ x &33 = 0 ∨ x &А ≠ 0 (*)

Имеем: 25 = 11001 2 и 33 = 100001 2 . Поэтому формула

x &25 = 0 ∨ x &33 = 0

ложна тогда и только тогда, когда двоичная запись числа x содержит 1 хотя бы в одном из следующих двоичных разрядов: 100000 (32), 10000 (16), 1000 (8) и 1.

Чтобы формула (*) была истинна при всех таких x необходимо и достаточно, чтобы двоичная запись числа A содержала 1 во всех этих разрядах. Наименьшее такое число – это число 32+16+8+1 = 57.

Известно, что выражение

((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))

истинно (то есть принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов в множестве A.

Решение.

Введем обозначения:

(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ · ; ∨ ≡ +.

Тогда, применив преобразование импликации, получаем:

(¬A + P) · (¬Q + ¬A) ⇔ ¬A · ¬Q + ¬Q · P + ¬A + ¬A · P ⇔

⇔ ¬A · (¬Q + P + 1) + ¬Q · P ⇔ ¬A + ¬Q · P.

Требуется чтобы ¬A + ¬Q · P = 1. Выражение ¬Q · P истинно когда x ∈ {2, 4, 8, 10, 14, 16, 20}. Тогда ¬A должно быть истинным когда x ∈ {1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...}.

Следовательно, максимальное количество элементов в множестве A будет, если A включает в себя все элементы множества ¬Q · P, таких элементов семь.

Ответ: 7.

Ответ: 7

Элементами множества А являются натуральные числа. Известно, что выражение

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))

Решение.

Введем обозначения:

(x ∈ {2, 4, 6, 8, 10, 12}) ≡ P; (x ∈ {3, 6, 9, 12, 15}) ≡ Q; (x ∈ A) ≡ A.

Преобразовав, получаем:

P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ ¬Q ∨ А.

Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Выражение ¬P ∨ ¬Q истинно при всех значениях x, кроме значений 6 и 12. Следовательно, промежуток А должны содержать точки 6 и 12. То есть минимальный набор точек в промежутке А ≡ {6, 12}. Сумма элементов множества А равна 18.

Ответ: 18.

Ответ: 18

Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Известно, что выражение

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение.

Упростим:

¬(x ∈ P) ∨ ¬(x ∈ Q) дают 0 только, когда число лежит в обоих множествах. Значит, чтобы все выражение было истинно нам нужно все числа лежащие в P и Q занести в А. Такие числа 6, 12, 18. Их сумма 36.

Ответ: 36.

Ответ: 36

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Элементами множеств А, 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 A) → (x P)) ∨ (¬(x Q) → ¬(x A))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве A.

Решение.

Преобразуем данное выражение:

((x A) → (x P)) ∨ ((x Q) → (x A))

((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))

(x A) ∨ (x P) ∨ (x Q)

Таким образом элемент должен либо входить в P или Q, либо не входить в А. Таким образом в А могут быть лишь элементы из P и Q. И всего в этих двух множествах 17 неповторяющихся элементов.

Ответ: 17

Элементами множеств А, P, Q являются натуральные числа, причём P = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение

((x ∈ P) → (x ∈ A)) ∨ (¬(x ∈ A) → ¬(x ∈ Q))

Решение.

Раскроем две импликации. Получим:

(¬(x ∈ P) ∨ (x ∈ A)) ∨ ((x ∈ A) ∨ ¬(x ∈ Q))

Упростим:

(¬(x ∈ P) ∨ (x ∈ A) ∨ ¬(x ∈ Q))

¬(x ∈ P) ∨ ¬(x ∈ Q) дают 0, только когда число лежит в обоих множествах. Значит, чтобы все выражение было истинно, нужно все числа, лежащие в P и Q, занести в А. Такие числа 3, 9, 15 и 21. Их сумма 48.

Ответ: 48.

Ответ: 48

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10303

А выражение

(y + 2x 30) ∨ (y > 20)

X и y?

Решение.

Заметим, что для тождественной истинности данного выражения выражение (y + 2x Ответ: 81.

Ответ: 81

Источник: ЕГЭ - 2018. Досрочная волна. Вариант 1., ЕГЭ - 2018. Досрочная волна. Вариант 2.

На числовой прямой задан отрезок A. Известно, что формула

((x ∈ A ) → (x 2 ≤ 100)) ∧ ((x 2 ≤ 64) → (x ∈ A ))

тождественно истинна при любом вещественном x . Какую наименьшую длину может иметь отрезок A?

Решение.

Раскрывая импликацию по правилу A → B = ¬A + B, заменяя логическую сумму совокупностью, а логическое произведение системой соотношений, определим значения параметра А , при котором система совокупностей

будет иметь решения для любых вещественных чисел.

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

Решениями неравенства являются все числа из отрезка [−10; 10]. Чтобы совокупность выполнялась для всех вещественных чисел, числа x , не лежащие на указанном отрезке, должны принадлежать отрезку A. Следовательно, отрезок A не должен выходить за пределы отрезка [−10; 10].

Аналогично, решениями неравенства являются числа из лучей и Чтобы совокупность выполнялась для всех вещественных чисел, числа x , не лежащие на указанных лучах, должны лежать на отрезке A. Следовательно, отрезок A должен содержать в себе отрезок [−8; 8].

Тем самым, наименьшая длина отрезка A может быть равна 8 + 8 = 16.

Ответ: 16.

Ответ: 16

A выражение

(y + 2x ≠ 48) ∨ (A x) ∨ (x y)

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

Решение.

A x и y , рассмотрим, в каких случаях условия (y + 2x ≠ 48) и (x y) ложны.

y = 48 − 2x ) и (x ≥ y). Это x в промежутке от 16 до 24 и y в промежутке от 0 до 16. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 16 и y = 16. Тогда A A будет равняться 15.

Ответ: 15.

Ответ: 15

Источник: ЕГЭ по информатике 28.05.2018. Основная волна, вариант А. Имаева - «Котолис».

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

(y + 2x ≠ 48) ∨ (A x) ∨ (A y)

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

Решение.

Чтобы найти наибольшее целое неотрицательное число A , при котором выражение будет x и y , рассмотрим, в каких случаях условие (y + 2x ≠ 48) ложно.

Таким образом, находим все решения, когда (y = 48 − 2x ). Это x в промежутке от 0 до 24 и y в промежутке от 48 до 0. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 16 и y = 16. Тогда A A будет равняться 15.

Ответ: 15.

Ответ: 15

Источник: Демонстрационная версия ЕГЭ-2019 по информатике.

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

(2x + 3y > 30) ∨ (x + y ≤ A )

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

Решение.

A , при котором выражение будет тождественно истинно при любых целых неотрицательных x и y y + 2x > 30) ложно.

y + 2x ≤ 30). Это x в промежутке от 0 до 15 и y в промежутке от 10 до 0. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 15 и y = 0. Тогда 15 + 0 ≤ A . Следовательно, наименьшее целое неотрицательное число A будет равняться 15.

Ответ: 15.

Ответ: 15

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

(2x + 3y x + y ≥ A )

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

Решение.

Чтобы найти наибольшее целое неотрицательное число A , при котором выражение будет тождественно истинно при любых целых неотрицательных x и y , рассмотрим, в каких случаях условие (3y + 2x Таким образом, находим все решения, когда (3y + 2x ≥ 30). Это x больше 15 и y больше 10. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 0 и y = 10. Тогда 0 + 10 ≤ A . Следовательно, наибольшее целое неотрицательное число A будет равняться 10.

Ответ: 10.

Ответ: 10

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

(3x + 4y ≠ 70) ∨ (A > x ) ∨ (A > y )

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

Решение.

Чтобы найти наименьшее целое неотрицательное число A , при котором выражение будет тождественно истинно при любых целых неотрицательных x и y , рассмотрим, в каких случаях условие (3x + 4y ≠ 70) ложно.

Таким образом, находим все решения, когда (3x + 4y = 70). Это x в промежутке от 2 до 22 и y в промежутке от 16 до 1. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 10 и y = 10. Тогда A > 10. Следовательно, наименьшее целое неотрицательное число A будет равняться 11.

Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".

От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках.
Давайте вспомним таблицу истинности для импликации:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1
Значит, возможно три варианта, когда это будет истинно. Рассматривать все эти три варианта — это убиться и не жить. Давайте подумаем, можем ли мы пойти "от противного ".
Давайте вместо того, чтобы искать А, попробуем найти x, при котором это выражение ложно.
То есть, возьмём некоторое число А (пока не знаем какое, просто какое-то). Если вдруг мы найдём такое x, при котором всё высказывание ложно, значит, выбранное А — плохое (потому что в условии требуется, чтобы всегда выражение было истинным)!
Таким образом мы сможем получить какие-то ограничение на число А.
Итак, давайте пойдём от противного и вспомним, когда импликация бывает ложной? Когда первая часть истинна, а вторая — ложна.
Значит
\((\mathrm{x}\&25\neq 0)= 1 \\ (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
Что означает, что \((x\&25\neq 0) = 1\) ? Это означает, что действительно \(\mathrm{x}\&25\neq 0\) .
Давайте переведём 25 в двоичную. Получим: 11001 2 .
Какие ограничения это накладывает на x? Раз не равно нулю, значит, при поразрядной конъюнкции должна где-то получиться единица. Но где она может быть? Только там, где в 25 уже есть единица!
Значит, в числе x хотя бы в одном кресте должна быть единица: XX**X.
Отлично, теперь рассмотрим второй множитель: \((\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
Это выражение из себя также представляет импликацию. При этом оно так же ложно.
Значит, его первая часть обязана быть истинной, а вторая — ложной.
Значит
\((\mathrm{x}\&17=0) = 1 \\ ((\mathrm{x}\&\mathrm{A}\neq 0) = 0) = 0\)
Что означает, что \(\mathrm{x}\&17=0\) ? То, что на всех местах, где в 17 стоят единицы, в x должны стоять нули (иначе в результате не получится 0).
Переведём 17 в двоичную: 10001 2 . Значит, в x на последнем с конца и на 5 с конца месте должны стоять нули.
Но стоп, мы же в пункте 13 получили, что на последнем ИЛИ на 4 с конца ИЛИ на 5 с конца должна быть единица.
Раз согласно строке 19 на последнем или 5 с конца местах единицы быть не может, значит, она обязана быть на 4 с конца месте.
То есть, если мы хотим, что при нашем x всё выражение было ложным, на 4 с конца месте обязана стоять единица: XX...XX1XXX 2 .
Отлично, рассмотрим теперь последнее условие: \((\mathrm{x}\&\mathrm{A}\neq 0) = 0\) . Что это означает?
Это означает, что неверно, что \(\mathrm{x}\&\mathrm{A}\neq 0\) .
То есть, на самом деле, \(\mathrm{x}\&\mathrm{A}=0\) .
Что мы знаем про x? Что на 4 с конца месте там единица. Во всём остальном x может быть практически любым.
Если мы хотим, чтобы исходное выражение в условии задачи было всегда истинным, то мы не должны найти х, который бы удовлетворял всем условиям. Ведь, действительно, если бы мы нашли такой x, получилось бы, что исходное выражение не всегда истинно, что противоречит условию задачи.
Значит, вот это самое последнее условие просто обязано не выполняться.
А как оно может не выполняться? Если только мы будем уверены на 100%, что при поразрядной конъюнкции где-то останется единица.
И это возможно: если в А тоже на 4 месте с конца будет единица, то в результате поразрядной конъюнкции на 4 с конца месте останется единица.
Какое минимально возможное двоичное число имеет единицу на 4 с конца месте? Очевидно, что 1000 2 . Значит, это число и будет ответом.
Осталось только перевести его в десятичную: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Ответ: минимально возможное A, удовлетворяющее условиям, равно 8 .

Евгений Смирнов

Эксперт в IT, учитель информатики

Решение №2

Можно предложить несколько более короткий подход. Обозначим наше высказывание как F = (A->(B->C)), где А - это высказывание "Х&25 не равно 0", В= "Х&17=0" и C="X&A не равно 0".

Раскроем импликации, пользуясь известным законом X->Y = не(Х) ИЛИ Y, получим F = A -> (не(В) ИЛИ C) = не(А) ИЛИ не(B) ИЛИ С. Распишем также двоичные значения констант 25 и 17:

Наше выражение - логическое ИЛИ от трёх высказываний:

1) не(А) - это значит, X&25 = 0 (биты 0,3,4 числа Х все равны 0)

2) не(B) - значит, X&17 не равно 0 (биты 0 и 4 числа Х хотя бы один равен 1)

3) C - знаит, X&A не равно 0 (биты, задаваемые маской A, хотя бы 1 равен 1)

Х - произвольное число. Все его биты независимы. Поэтому требовать выполнения какого-то условия на биты произвольного числа можно только в одном единственном случае - когда речь идёт об одной и той же маске (наборе битов). Мы можем заметить, что двоичная маска 17 - почти то же самое, что и 25, только не хватает бита номер 3. Вот если бы дополнить 17 битом номер 3, то выражение (не(В) ИЛИ С) превратилось бы в не(неА), т.е. в А = (X&25 не равно 0). По-другому: допустим, А=8 (бит 3=1). Тогда требование (не(В) B или С) равносильно требованию: (Хотя бы один из битов 4,0 равен 1) ИЛИ (бит 3 равен 1) = (хотя бы один из битов 0,3,4 не равен 1) - т.е. инверсия не(А) = А = (Х&25 не равно 0).

В итоге мы заметили, что если А=8, то наше выражение принимает вид F = не(А) ИЛИ А, что, по закону исключённого третьего, всегда тождественно истинно. При других, меньших, значениях А независимость от значения Х получить не удаётся, т.к. маски выходят разные. Ну, а при наличии в старших битах А единиц в битах выше 4 ничего не меняется, т.к. в остальных масках у нас нули. Получается, что только при А=8 формула превращается в тавтологию для произвольного Х.

Дмитрий Лисин

Для эффективной подготовки по информатике для каждого задания дан краткий теоретический материал для выполнения задачи. Подобрано свыше 10 тренировочных заданий с разбором и ответами, разработанные на основе демоверсии прошлых лет.

Изменений в КИМ ЕГЭ 2019 г. по информатике и ИКТ нет.

Направления, по которым будет проведена проверка знаний:

Программирование;
Алгоритмизация;
Средства ИКТ;
Информационная деятельность;
Информационные процессы.

Необходимые действия при подготовке :

Повторение теоретического курса;
Решение тестов по информатике онлайн ;
Знание языков программирования;
Подтянуть математику и математическую логику;
Использовать более широкий спектр литературы – школьной программы для успеха на ЕГЭ недостаточно.

Структура экзамена

Длительность экзамена – 3 часа 55 минут (255 минут), полтора часа из которых рекомендовано уделить выполнению заданий первой части КИМов.

Задания в билетах разделены на блоки:

Часть 1 - 23 задания с кратким ответом.
Часть 2 - 4 задачи с развернутым ответом.

Из предложенных 23 заданий первой части экзаменационной работы 12 относятся к базовому уровню проверки знаний, 10 – повышенной сложности, 1 – высокому уровню сложности. Три задачи второй части высокого уровня сложности, одна – повышенного.

При решении обязательна запись развернутого ответа (произвольная форма).
В некоторых заданиях текст условия подан сразу на пяти языках программирования – для удобства учеников.

Баллы за задания по информатике

1 балл - за 1-23 задания
2 балла - 25.
З балла - 24, 26.
4 балла - 27.
Всего: 35 баллов.

Для поступления в технический вуз среднего уровня, необходимо набрать не менее 62 баллов. Чтобы поступить в столичный университет, количество баллов должно соответствовать 85-95.

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