Главная » Хвойные в дизайне » Информатика 18 задание способ решения.

Информатика 18 задание способ решения.

Белова Т.В.
как научить решать задание 18 егэ по информатике

муниципальное бюджетное общеобразовательное учреждение «Лицей»,

г. Арзамас, ya . bellova . tatyana @ yandex . ru

Перед тем как приступать к решению заданий 18 «Проверка истинности логического выражения» экзаменационной работы по информатике, нужно объяснить (или вспомнить) учащимся, что такое понятие «объединение» и «пересечение» нескольких множеств. И так как задание 18 связано с определением отрезков, то и лучше всего эти понятия объяснять на отрезках. Но связать необходимо эти понятия с понятиями алгебры логики – «конъюнкция» и «дизъюнкция», ну и, конечно же, «инверсия». Приведу это все на примере. Для начала рассмотрим инверсию отрезка, или, проще говоря, отрицание отрезка.

Дан отрезок P=. Найти отрезки, которые будут инверсией отрезка P=. Рассмотрим координатную прямую (рис. 1):

рис. 1

На прямой отмечаем отрезок P (синяя область), тогда понятно, что промежутки не P будут промежутки и (зеленая область) – рис. 1. Обращая внимание, что точки 6 и 15 в инверсию отрезка входить не будут.

Рассмотрим еще пример: даны два отрезка P= и Q={приведены те же обозначения, что и в задании ЕГЭ, чтобы учащиеся сразу привыкали к обозначениям}. Найти отрезок, который будет обозначать конъюнкцию (объединение) и дизъюнкцию (пересечение) этих отрезков

Рисуем отрезки на координатной прямой (рис. 2):

рис. 2

Сначала отмечаем области на координатной прямой, которые обозначают отрезки P (синий цвет) и Q (желтый цвет). Затем определяем, какая часть координатной прямой будет служить конъюнкцией этих двух отрезков. Здесь вспоминаем, что конъюнкция – это логическая операция, которая объединяем два простых высказывания в сложное с помощью логической связки «и», и сложное высказывание будет приобретать значение «истина» тогда и только тогда, когда истины оба исходных простых высказывания. Таким образом, получаем, что нужно найти области, где и отрезок P и отрезок Q имеют место, а такая область только одна – отрезок (красный цвет). Более подробно исследуем все отрезки прямой, чтобы учащимся было нагляднее и понятнее воспринимать материал, итак:

Теперь аналогичным образом разберемся с дизъюнкцией этих отрезков. Опять же обратимся к определению этой логической операции – «дизъюнкцией называется логическая операция, которая в соответствии двум и более логическим высказываниям ставит новое, которое истинно тогда и только тогда, когда истинно хотя бы одно из входящих исходных высказываний». То есть другими словами, нам надо найти на координатной прямой такие промежутки, где есть хотя бы один из исходных наших отрезков, этот искомый промежуток будет – зеленый цвет (рис. 2). Также разберем каждый из промежутков и покажем, что это действительно так:

Объединяя найденные промежутки, получаем что искомый отрезок, обозначающий дизъюнкцию исходных отрезков – это отрезок – зеленый цвет (рис. 2).

После разбора данного примера, можно дать учащимся попробовать найти различные сочетания логических операций – дизъюнкции, конъюнкции и отрицания. Например, даны два отрезка P=[-4,10] и Q=. Найти отрезок, который будет обозначать следующие логические операции: , , (можно придумать и другие различные сочетания этих логических операций).

рис. 3

рис. 4

рис. 5

Когда разобраны все примеры, то у учащихся не возникнет трудностей с пониманием и решением задания №18 из экзаменационной работы единого государственного экзамена по информатике.

Приведем примеры решений нескольких заданий:

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

(x  A ) → ((x  P ) → (x  Q )) тождественно истинна, то есть принимает значение 1 при любом значении переменной х . Возможные варианты ответов:

1) 2) 3) 4)

Решение (рис. 6): чтобы упростить понимание выражения, обозначим отдельные высказывания буквами - A : x  А, P : x  P, Q : x  Q. Таким образом, получаем следующее выражение с учетом замены: → ( P → )=1. Равенство выражения 1 говорит о том, что какое бы значение переменной х мы не взяли, наше логическое выражение принимает значение 1, то есть на всей числовой прямой. Вспомним некоторые логические законы и равенства и преобразуем наше выражение: =1. В итоге получаем, что нам надо построить дизъюнкцию трех отрезков, два из которых нам известны. Их то мы и построим (рис. 7). Для начала, как и во всех выше приведенных примерах, мы должны построить инверсии отрезков P (оранжевый цвет) и Q (красный цвет). Затем из всего выражения мы можем определить промежутки дизъюнкции =1 (зеленые области рис. 7). Таким образом получаем, что у нас на координатной прямой есть «свободная» часть - . Эту часть прямой и должен перекрыть искомый отрезок А .

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

((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 формула превращается в тавтологию для произвольного Х.

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

учитель информатики МБОУ «Лицей»

первой квалификационной категории

Мурзина Ольга Ивановна

МБОУ «Лицей» г. Арзамас

Теория и практика решения задания 18 ЕГЭ по информатике

Арзамас, 2017

Мнемоническое правило

Один из ее главных принципов – дополнение до целого (дополнение противоположностью)

Соционика – это информационная психология

Решающая формула

В алгебре логики есть формула дополнения до целого:

В некоторых задачах мы будем использовать вместо этой формулы умножение противоположностей:

Типы задания 18

Задания на отрезки
Задания на множества
Задания на поразрядную конъюнкцию
Задания на условие делимости

Задания на отрезки

(№ 376) На числовой прямой даны два отрезка: P= и Q=. Укажите наименьшую возможную длину такого отрезка A, что формула ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

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

Решающая формула

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

Решение задачи на отрезки

Легенда
Формализация условия
Решение логического уравнения

Разделим решение задачи на этапы:

Решение задачи на отрезки

Легенда – это удобные нам условные обозначения, которые мы будем использовать при решении.

Введем следующие обозначения:

Решение задачи на отрезки

2) Формализация условия – перепишем формулу из условия задачи в соответствие с легендой.

((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) = 1

(P ∧ Q) → A = 1

Решение задачи на отрезки

3) Решение логического уравнения – вначале это, возможно, самый сложный этап в решении задачи. Но позже, при накоплении опыта, он уже не будет казаться таким уж сложным 

Рассмотрим решение логического уравнения по шагам.

Решение задачи на отрезки

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В:

(P ∧ Q) → A = 1

¬(P ∧ Q)  A = 1

Решение задачи на отрезки

А  ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А  ¬А = ¬А  А) :

¬(P ∧ Q)  A = 1, отсюда

¬А = ¬(P ∧ Q)

Ответом в логическом уравнении будет:

Решение задачи на отрезки

Наш ответ: А = P ∧ Q.

В алгебре логики это выражение означает пересечение объемов двух логических объектов. По условию нашей задачи – это пересечение отрезков P и Q.

Решение задачи на отрезки

Пересечение отрезков P и Q можно визуализировать: P= и Q=.

По условию нашей задачи, нам нужна минимальная длина отрезка А. Находим ее: 15 – 12 = 3.

Ответ на сайте Полякова К.Ю.: 3

Задания на отрезки

(№ 360) На числовой прямой даны три отрезка: P=, Q= и R=. Какова максимальная длина отрезка A, при котором формула ((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P)

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

Источник - сайт Полякова К.Ю.

Решающая формула

Для выбора решающей формулы важно внимательно прочитать требование задачи.

В нашей задаче в требовании сказано:

принимает значение 0 при любом значении переменной х.

Выбор решающей формулы очевиден:

Решение задачи на отрезки

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Решение задачи на отрезки

Легенда

Решение задачи на отрезки

2) Формализация условия

((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P) = 0

(Q → ¬R) ∧ A ∧ ¬ P = 0

Решение задачи на отрезки

(Q → ¬R) ∧ A ∧ ¬ P = 0

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В, и переставим множители согласно закону коммутативности умножения:

A ∧ (¬ Q  ¬R) ∧ ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

A ∧ (¬ Q  ¬R) ∧ ¬ P = 0

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 0 и найдем, чему равно ¬А:

¬А = (¬ Q  ¬R) ∧ ¬ P

Решение задачи на отрезки

3) Решение логического уравнения

¬А = (¬ Q  ¬R) ∧ ¬ P

3.3. Упростим выражение для ¬А по закону де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R) ∧ ¬ P,

и по другому закону де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R  P)

Решение задачи на отрезки

3) Решение логического уравнения

¬А = ¬ (Q  R  P)

3.4. Очевидно, что

А = Q  R  P

Решение задачи на отрезки

4) Интерпретация полученного результата

А = Q  R  P

Отрезок А – это пересечение отрезков Q и R и его объединение с отрезком Р.

Решение задачи на отрезки

Пересечение отрезков R и Q можно визуализировать: Q= и R=.

Отрезок P= нанесем на наш чертеж и объединим с пересечением:

Решение задачи на отрезки

По условию нашей задачи, нам нужна максимальная длина отрезка А. Находим ее: 30 – 10 = 20.

А = Q  R  P

Ответ на сайте Полякова К.Ю.: 20

2. Задания на множества

(№ 386) Элементами множеств А, P, Q являются натуральные числа, причём P={1,2,3,4,5,6}, Q={3,5,15}. Известно, что выражение (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

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

Источник - сайт Полякова К.Ю.

Решение задачи на множества

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Решение задачи на множества

Легенда

Решение задачи на множества

2) Формализация условия

(x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q) = 1

¬ A → (¬P ∧ Q)  ¬ Q = 1

Решение задачи на множества

3) Решение логического уравнения

¬ A → (¬P ∧ Q)  ¬ Q = 1

3.1. Представим логическое следование в базовых логических операциях и сгруппируем:

A  ((¬P ∧ Q)  ¬ Q) = 1

Решение задачи на множества

A  ((¬P ∧ Q)  ¬Q) = 1

3.2. Сведем получившееся выражение к решающей формуле:

и найдем, чему равно ¬А:

¬А = (¬P ∧ Q)  ¬Q

Решение задачи на множества

¬А = (¬P ∧ Q)  ¬Q

3.3. Упростим выражение для ¬А, раскрыв скобки по закону дистрибутивности сложения:

¬А = (¬P  ¬Q)  (Q  ¬Q)

¬А = (¬P  ¬Q)

Решение задачи на множества

¬А = (¬P  ¬Q)

По закону де Моргана:

¬А = ¬(P  Q)

3.4. Очевидно, что

Решение задачи на множества

4) Интерпретация полученного результата

Решение задачи на множества

P = 1, 2, 3, 4, 5, 6 и Q ={3, 5,15}, таким образом A ={3, 5}

и содержит только 2 элемента.

Ответ на сайте Полякова: 2

2. Задания на множества

(№ 368) Элементами множеств А, P, Q являются натуральные числа, причём P={2,4,6,8,10,12} и Q={4,8,12,116}. Известно, что выражение (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

Источник - сайт Полякова К.Ю.

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Решение задачи на множества

Легенда

Решение задачи на множества

2) Формализация условия

(x ∈ P)→(((x ∈ Q) ∧ (x ∉ A))→(x ∉ P)) = 1

P → ((Q ∧ ¬A) → ¬P) = 1

Решение задачи на множества

3) Решение логического уравнения

P → ((Q ∧ ¬A) → ¬P) = 1

3.1. Представим первое логическое следование (в скобках) в базовых логических операциях:

P → (¬(Q ∧ ¬A)  ¬P) = 1

Решение задачи на множества

P → (¬(Q ∧ ¬A)  ¬P) = 1

Представим второе логическое следование в базовых логических операциях, применим закон де Моргана и перегруппируем:

¬P (¬(Q ∧ ¬A)  ¬P) = 1

¬P ¬Q  A  ¬P = 1

Решение задачи на множества

A  (¬P ¬Q  ¬P) = 1

3.2. Сведем получившееся выражение к решающей формуле:

и найдем, чему равно ¬А:

¬А = (¬P ¬Q  ¬P)

Решение задачи на множества

¬А = ¬P ¬Q  ¬P

3.3. Упростим выражение для ¬А по формуле А  А = А:

¬А = ¬(P Q)

Решение задачи на множества

¬А = ¬(P Q)

3.4. Очевидно, что

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P = 2, 4, 6, 8, 10, 12 и

Q ={4, 8, 12, 16}, таким образом

и содержит только 3 элемента, сумма которых 4+8+12=24 .

Ответ на сайте Полякова: 24

(№ 379) Обозначим через m &n пораз-рядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула (x & 29 ≠ 0) → ((x & 12 = 0) → (x & А ≠ 0))

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

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Легенда

B = (x & 29 ≠ 0)

C = (x & 12 ≠ 0)

A = (x & А ≠ 0)

Решение задачи на поразрядную конъюнкцию

Мы принимаем за истинное высказывание поразрядную конъюнкцию, отличную от нуля, иначе поразрядная конъюнкция теряет свой логический смысл, т.к. всегда можно представить Х всеми нулями.

Решение задачи на поразрядную конъюнкцию

2) Формализация условия

(x & 29 ≠ 0)→((x & 12 = 0)→(x & А ≠ 0))=1

В → (¬С → А) = 1

Решение задачи на поразрядную конъюнкцию

3) Решение логического уравнения

В → (¬С → А) = 1

В → (С А) = 1

(¬В  С) А = 1

¬А = ¬В  С

¬А = ¬(В ¬ С)

Очевидно, что

А = В ¬ С

Решение задачи на поразрядную конъюнкцию

4) Интерпретация полученного результата

Решение задачи на поразрядную конъюнкцию

B = (x & 29 ≠ 0)

В или 29 = 111012

C = (x & 12 ≠ 0)

¬С или инверсия 12 = 00112

Решение задачи на поразрядную конъюнкцию

В или 29 = 111012

¬С или инверсия 12 = 00112

А = В ¬ С

А = 100012 = 17

Ответ на сайте Полякова: 17

3. Задания на поразрядную конъюнкцию

(№ 375) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответ-ствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

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

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Решение задачи на поразрядную конъюнкцию

Легенда

Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:

B = (x & 49 ≠ 0)

C = (x & 33 ≠ 0)

A = (x & А ≠ 0)

Решение задачи на поразрядную конъюнкцию

2) Формализация условия

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1

В → (¬С → А) = 1

Решение задачи на поразрядную конъюнкцию

3) Решение логического уравнения

В → (¬С → А) = 1

В → (С  А) = 1

(¬В  С)  А = 1

¬А = (¬В  С)

Очевидно:

Решение задачи на поразрядную конъюнкцию

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С.

Решение задачи на поразрядную конъюнкцию

B = (x & 49 ≠ 0)

В или 49 = 1100012

C = (x & 33 ≠ 0)

¬С или инверсия 33 = 0111102

Решение задачи на поразрядную конъюнкцию

В или 49 = 1100012

¬С или инверсия 33 = 0111102

А = В ¬ С

011110 2

А = 100002 = 16

Ответ на сайте Полякова: 16

(№ 372) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула ¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))

Источник - сайт Полякова К.Ю.

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Решение задачи

на условие делимости

Легенда

Решение задачи

на условие делимости

Легенда простая: А = ДЕЛ(x,А)

21 = ДЕЛ(х,21)

35 = ДЕЛ(x,35)

2) Формализация условия

Решение задачи

на условие делимости

¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))

¬А → (¬21 ∧ ¬35) = 1

тождественно истинна (то есть принимает значение 1)

3) Решение логического уравнения

Решение задачи

на условие делимости

¬А → (¬21 ∧ ¬35) = 1

А (¬21 ∧ ¬35) = 1

¬А = ¬21 ∧ ¬35

Очевидно, что

4) Интерпретация полученного результата

В данной задаче это самый сложный этап решения. Нужно понять, что же представляет из себя число А – НОК или НОД или …

Решение задачи

на условие делимости

4) Интерпретация полученного результата

Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем

А = НОД (21, 35) = 7

Решение задачи

на условие делимости

Ответ на сайте Полякова: 7

4. Задания на условие делимости

(№ 370) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула ¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

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

Источник - сайт Полякова К.Ю.

Легенда
Формализация условия
Решение логического уравнения
Интерпретация полученного результата

Решение задачи

на условие делимости

Легенда

А = ДЕЛ(x,А)

Решение задачи

на условие делимости

2) Формализация условия

Решение задачи

на условие делимости

¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

тождественно истинна (то есть принимает значение 1

¬А → (6 → ¬4) = 1

3) Решение логического уравнения

¬А → (6 → ¬4) = 1

¬А → (¬ 6  ¬4) = 1

А  (¬ 6  ¬4) = 1

¬А = ¬ 6  ¬4

Очевидно:

Решение задачи

на условие делимости

4) Интерпретация полученного результата

Итак, А таково, что Х делится на него без остатка тогда и только тогда, когда Х делится без остатка и на 6, и на 4. Т.е. А = НОК(6, 4) = 12

Ответ на сайте Полякова: 12

Решение задачи

на условие делимости

Сможете ли Вы теперь объяснить решение задания 18 своим ученикам или друзьям?

(да, нет, не знаю).

Спасибо за внимание!

Для эффективной подготовки по информатике для каждого задания дан краткий теоретический материал для выполнения задачи. Подобрано свыше 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.

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

Твоя формула успеха

Труд + работа над ошибками + внимательно читать вопрос от начала и до конца, чтобы избежать ошибок = максимальный балл на ЕГЭ по информатике.

Решение №2

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

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

Твоя формула успеха

Похожие статьи