Информатика егэ 18 задание формулы
Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".
- От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
- Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках.
- Давайте вспомним таблицу истинности для импликации:
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.
Для успешного написания экзаменационной работы необходимо четкое владение теорией
и постоянная практика в решении
задач.
Твоя формула успеха
Труд + работа над ошибками + внимательно читать вопрос от начала и до конца, чтобы избежать ошибок = максимальный балл на ЕГЭ по информатике.
Задание 18 Каталог заданий. Логические высказывания
1. Задание 18 № 701. Для какого имени ложно высказывание:
(Первая буква имени гласная → Четвертая буква имени согласная).
1) ЕЛЕНА
2) ВАДИМ
3) АНТОН
4) ФЕДОР
Пояснение.
Импликация ложна тогда и только тогда, когда посылка истинна, а следствие ложно. В нашем случае - если первая буква имени гласная и четвертая буква гласная. Этому условию удовлетворяет имя Антон.
Примечание.
Тот же результат следует из следующих преобразований: ¬ (A → B) = ¬ (¬ A ∨ B) = A ∧ (¬ B).
Правильный ответ указан под номером 3.
2. Задание 18 № 8666. На числовой прямой даны два отрезка: P = и Q = . Укажите наибольшую возможную длину промежутка A, для которого формула
(¬ (x A) → (x P)) → ((x A) → (x Q))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Пояснение.
Преобразуем данное выражение:
(¬ ( x A ) → ( x P )) → (( x A ) → ( x Q ))
((x A) ∨ (x P)) → ((x не A) ∨ (x Q))
¬(( x принадл A ) ∨ ( x принадл P )) ∨ (( x не принадл A ) ∨ ( x принадл Q ))
( x не принадл A ) ∧ ( x не принадл P ) ∨ ( x принадл A ) ∨ ( x не принадл Q )
( x не принадл A ) ∨ ( x принадл Q )
Таким образом, либо x должен принадлежать Q, либо не принадлежать A. Это значит, что для достижения истинности для всех x, необходимо, чтобы A полностью содержался в Q. Тогда максимум, каким он сможет стать, это всем Q, то есть длиной 15.
3. Задание 18 № 9170. На числовой прямой даны два отрезка: P = и Q = .
Укажите наибольшую возможную длину отрезка A, для которого формула
((x A) → ¬(x P)) → ((x A) → (x Q))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х .
Пояснение.
Преобразуем данное выражение.
(( x € A ) → ¬( x принадл P )) → (( x принадл A ) → ( x принадл Q ))
(( x не принадл A ) ∨ ( x не принадл P )) → (( x не принадл A ) ∨ ( x принадл Q ))
¬((x не принадл A) ∨ (x не принадл P)) ∨ ((x не принадл A) ∨ (x принадл Q))
Верно, что A ∧ B ∨ ¬A = ¬A ∨ B. Применим это здесь, получим:
(x принадл P) ∨ (x не принадл A) ∨ (x принадл Q)
То есть либо точка должна принадлежать Q, либо принадлежать P, либо не принадлежать А. Это значит, что А может покрывать все точки, которые покрывают P и Q. То есть A = P Q = = . |A| = 48 - 10 = 38.
4. Задание 18 № 9202. Элементами множеств А, 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) при любом значении переменной х.
5. Задание 18 № 9310. Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}.
Известно, что выражение
((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))
истинно (т.е. принимает значение 1) при любом значении переменной х.
Определите наибольшее возможное количество элементов в множестве A.
6. Задание 18 № 9321. Обозначим через ДЕЛ ( n, m ) утверждение «натуральное число n делится без остатка на натуральное число m ». Для какого наибольшего натурального числа А формула
¬ ДЕЛ ( x, А ) → (¬ ДЕЛ ( x , 21) ∧ ¬ ДЕЛ ( x , 35))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x )?
(Задание М. В. Кузнецовой)
7. Задание 18 № 9768. Обозначим через m & n m и n 2 & 0101 2 = 0100 2 А формула
x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х )?
8. Задание 18 № 9804. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. Для какого наименьшего неотрицательного целого числа А формула
x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x )?
9. Задание 18 № 723. Для какого имени истинно высказывание:
Третья буква гласная → ¬ (Первая буква согласная \/ В слове 4 гласных буквы)?
1) Римма
2) Анатолий
3) Светлана
4) Дмитрий
Пояснение.
Применим преобразование импликации:
Третья буква Согласная ∨ (Первая буква Гласная ∧ В слове НЕ 4 гласных буквы)
Дизъюнкция истинна, когда истинно хотя бы одно высказывание. Следовательно, подходит только вариант 1.
10. Задание 18 № 4581. Какое из приведённых имён удовлетворяет логическому условию:
(первая буква согласная → последняя буква согласная) /\ (первая буква гласная → последняя буква гласная)?
Если таких слов несколько, укажите самое длинное из них.
1) АННА
2) БЕЛЛА
3) АНТОН
4) БОРИС
Пояснение.
Логическое И истинно только тогда, когда истинны оба утверждения.(1)
Импликация ложна только тогда,когда из истины следует ложь.(2)
Вариант 1 подходит по всем условиям.
Вариант 2 не подходит из за условия (2).
Вариант 3 не подходит из за условия (2).
Вариант 4 подходит по всем условиям.
Необходимо указать самое длинное из слов, следовательно, ответ 4.
Задания для самостоятельного решения
1. Задание 18 № 711. Какое из приведенных названий стран удовлетворяет следующему логическому условию: ((последняя буква согласная) \/ (первая буква согласная)) → (название содержит букву «п») ?
1) Бразилия
2) Мексика
3) Аргентина
4) Куба
2. Задание 18 № 709. Какое из приведённых имен удовлетворяет логическому условию:
(Первая буква гласная) ∧ ((Четвёртая буква согласная) ∨ (B слове четыре буквы))?
1) Сергей
2) Вадим
3) Антон
4) Илья
№3
№4 
№5. Задание 18 № 736. Какое из приведённых имен удовлетворяет логическому условию
Первая буква гласная ∧ Четвёртая буква согласная ∨ В слове четыре буквы?
1) Сергей
2) Вадим
3) Антон
4) Илья
