Задача №15. Использование основных понятий математической логики. Логические высказывания, числовые отрезки

Две трети выпускников проваливают 18 задание ЕГЭ по информатике. Как же его решать? Нужно знать особый подход. Давайте разберемся, как эффективно справиться с этим коварным заданием.

В этой статье:

Первая сложность в 18 задании ЕГЭ по информатикеВторая сложность в 18 задании ЕГЭ по информатикеКак упростить выражение? Что такое «красная зона»?Примеры 18 задания ЕГЭ по информатикеПодведем итоги

В ЕГЭ по информатике есть четыре задания на математическую логику. Сегодня речь пойдёт о задании №18, которое связано с анализом логического высказывания. Статистика ужасна: по оценке ФИПИ с ним справляются чуть меньше 1/3 сдающих. Почему 18 задание ЕГЭ по информатике вызывает сложности? Давайте разберемся, что надо знать, понимать и уметь, чтобы их избежать.

А если вас интересуют и другие задания, эффективно подготовиться к ЕГЭ по информатике можно на наших курсах.

Первая сложность в 18 задании ЕГЭ по информатике

Вам нужны знания не только математической логики, но и просто математики. В качестве логической переменной (которая может быть истина или ложна) выступают не просто некие x, y, z, а математические высказывания. В ответе надо определить значения некоторого параметра, зависящего от этих переменных. Что-то напоминает? Да, почти как в задании 18 из профильной математики, но тут будет намного проще. Например, логической переменной может выступать выражение «x>10» или суждение о том, что x кратен 5. Рассмотрим, как подходить к такому виду логической переменной.

Если логическая переменная — неравенство

Если логическая переменная — утверждение

Вторая сложность в 18 задании ЕГЭ по информатике

Когда такие переменные рассматриваются отдельно, все выглядит просто. Но в 18 задании у вас будет целое логическое высказывание, содержащее несколько переменных и параметр, значение которого вам надо определить.

Это и есть вторая сложность данного задания — надо знать, как правильно подходить к анализу выражения. Для этого нужно помнить о двух принципиальных шагах:

1. Упрости, если есть возможность.
2. Определи «красную зону»

18 задание ЕГЭ по информатике важно решать постепенно. Сначала поговорим об упрощении, так как без этого шага очень сложно начать анализ. Затем обсудим, что такое «красная зона».

Как упростить выражение?

Смысл
этого шага в двух моментах:

1. Введите обозначения для удобства записи. Иначе некоторые переменные получаются слишком громоздкими.
2. Упростите зависимости логических переменных. Выражение, где смешаны несколько уровней скобок и логических функций, сложно анализировать. А вот идентичное ему выражение, в котором три переменных связаны дизъюнкцией, намного проще.

Для большинства заданий вам нужно знать несколько формул матлогики. Сохраните эту картинку, пригодится.

Что такое «красная зона»?

В задании нужно определить значения параметра, чтобы логическое высказывание было тождественно истинно при любых значениях переменной x. При этом мы не можем брать произвольно большой набор значений для искомого параметра, это также определяется условием задания. Поэтому нужно подбирать такие значения параметра, чтобы они закрывали только определённый ряд случаев, не больше и не меньше. Этот ряд случаев назовем «красной зоной», теми значениями переменной x, когда логическое высказывание не будет истинно при любых значениях параметра.

Простой пример. Возьмем логическое высказывание: (X < 50) V (X > A).

Нам не важно значение параметра А. У нас есть одно логическое слагаемое, которое истинно. Второе может быть ложно — дизъюнкция все равно в итоге даст истину. Значит «красная зона» — это все х≥50. Подбирать значение для параметра А необходимо только для случаев, когда х≥50, чтобы за счет второго слагаемого (где содержится А) обеспечить истинность всего выражения, когда первая скобка ложна.

Для правильного анализа красной зоны важно помнить об основных
моментах анализа некоторых логических функций:

1. Конъюнкция нескольких переменных будет истинна, только если каждый множитель истинен, и ложна, если хотя бы один множитель ложен.
2. Дизъюнкция нескольких переменных будет истинна, если хотя бы одно слагаемое истинно, и ложна, только если ложны все слагаемые.
3. Импликация ложна только в единственном случае — когда из истины следует ложь.

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

Рассмотрим правильный подход на различных прототипах данного задания.

В данном логическом высказывании не требуется упрощений, так как у нас простой для анализа случай: дизъюнкция трёх переменных. Поэтому перейдём сразу к анализу и определению «красной зоны».

Вторая и третья скобки не зависят от А и обеспечат истинность всего выражения, независимо от параметра, если X>15 или Y>30. Тогда красной зоной будет ситуация, когда не выполняются ОБА из этих условий, то есть и вторая, и третья скобки одновременно ложны. Опишем этот случай системой:

В этой ситуации нам необходимо обеспечить истинность первой скобки, которая зависит от параметра. Дополним систему ещё одним условием.

Теперь мы свели задание к решению системы простейших неравенств. Определим границы для параметра А при помощи работы с неравенствами. Первое неравенство умножим на 2, затем сложим новое неравенство со вторым и сведём это всё к одному двойному неравенству за счёт одинакового выражения Y+2X.

Осталось вернуться к формулировке вопроса. Вас всегда будут спрашивать что-то конкретное относительно значений параметра А! В данном случае нам надо найти наименьшее целое значение. В случае A > 60 наименьшим подходящим целым значением будет 61. Внимание! Всегда отслеживайте строгость и нестрогость знаков, значение 60 не подходит под условие A > 60, так как 60 равно 60, но не как не больше.

Пример 2

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

Выражение сразу выглядит намного проще.

Теперь применим формулу для раскрытия импликации на базовые функции.

Далее воспользуемся формулой де Моргана.

Уберём двойное отрицание и лишние скобки.

И финальным шагом уберём тавтологию.

Сравните с тем, что было в условии. Стало проще, правда? Дальше мы будем анализировать именно это выражение.

«Красная зона» будет также определяться из случая, когда дизъюнкция будет истинна не из-за переменных, которые не зависят от А, а исключительно из-за переменной с параметром. Получается, для этого первое и второе слагаемые должны быть ложны.  Получаем, что P = 1 и Q = 1, в таком случае и A = 1. Теперь вернёмся от наших обозначений к исходным описаниям переменных.

Значит наша «красная зона» — это пересечение отрезков P и Q. Чтобы покрыть ровно эту часть числовой прямой, отрезок А должен ровняться пересечению отрезков P и Q.

В ответ надо указать минимально возможную длину отрезка. Мы подбирали значение отрезка А так, чтобы сразу закрыть им только необходимое и не больше, поэтому полученный отрезок и есть отрезок минимальной длинны.

Длина отрезка считается очень просто: из большей границы вычитается меньшая. Длина отрезка А = 171 – 150 = 21.

Пример 3

В данном примере тоже нужно упростить выражение. Введём обозначения:

Дальше потребуется только раскрыть импликации, убрать двойное отрицание и лишние скобки.

Теперь переходим к определению «красной зоны». Когда D6=1 и D4 = 1, то и DA должно быть истинно.

Вернемся к математическому смыслу наших переменных. Получаем условие: числа, которые кратны 4 и 6 одновременно, должны быть кратны и А. Пользуясь понятием наименьшего общего кратного (НОК) из математики, получаем, что числа, которые одновременно кратны 4 и 6 – это числа, кратные 12.

Переформулируем условие: числа, которые кратны 12, должны быть кратны А. Отсюда уже понятно, что А = 12. Если мы возьмём число меньшее, например 2, выражение будет истинно, но это не максимальное возможное значение, которое просят по условию. А если возьмём число больше, например 24, для x=12 выражение окажется ложным. Кратность 4 и 6 будет обнулять второе и третье слагаемое, а первое окажется ложно, так как 12 не кратно 24, а наоборот 24 кратно 12.

Пример 4

В этом примере встречается поразрядная конъюнкция. Суть этого вычислительного действия проста: мы выполняем логическое умножение чисел, записанных двоичным кодом, по разрядам (нулевой с нулевым, первый с первым и т.д.). Подробнее на поразрядную конъюнкцию взглянем уже при анализе выражения. Для начала упростим то, что надо анализировать. Введём обозначения:

Дальше потребуется только раскрыть импликацию и убрать лишние скобки

Теперь переходим к определению «красной зоны». Она возникает, когда Z39 = 0 и Z41 = 1, и ZA должно быть ложно.

Переходим
обратно к математическому смыслу наших переменных. Запишем условия следующим
образом: для х, для которых поразрядная конъюнкция с 41 даёт 0, а с 39 даёт не
0, поразрядная конъюнкция с А должна давать не 0.

Определим, что такое х из «красной зоны».

Посмотрим
на первое условие: поразрядная конъюнкция с 41 даёт 0. Чтобы посчитать
поразрядную конъюнкцию переводим 41 в двоичную систему счисления и получаем
101001₂.

Чтобы в итоге поразрядной конъюнкции получился ноль, в тех разрядах, где в числе 41 стоят единицы, у числа х должны обязательно стоять нули. Там же, где в числе 41 стоят нули – в числе х может быть всё что угодно, так как одного нуля для обнуления произведения достаточно. Изобразим это схематически.

Мы получили некоторый «макет» чисел «красной зоны». Но он пока не полный. Переходим ко второму условию: поразрядная конъюнкция с 39 даёт не 0. Также необходимо перевести число в двоичную систему счисления. 39₁₀ = 100111₂. Чтобы в итоге поразрядной конъюнкции получить не 0, хотя бы один из разрядов, где у 39 стоят единицы, в х тоже должен содержать единицу. Достаточно одной, но она может быть на любом из доступных мест (кроме, тех, где из-за анализа первого условия мы уже поставили 0).

Теперь у нас есть полная схема чисел, которые представляют собой «красную зону». У таких чисел в нулевом, третьем, пятом разряде точно стоят нули, а в первом или во втором (или и в том и том) стоят единицы.

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

Последнее, что осталось сделать — перевести число А в десятичную систему счисления. 110₂ = 6₁₀.

Подведем итоги

Теперь вы умеете решать 18 задание ЕГЭ по информатике. Такой подход с упрощением выражения и постепенным анализом позволяет разбить длительную работу с заданием на небольшие этапы. Вы постепенно составляете выводы о том, каким же должен быть параметр в этом задании.

Остается закрепить знания на практике. Напомню, что эффективно подготовиться к ЕГЭ по информатике можно на наших курсах. Используйте промокод BLOG0320 до 31 марта 2020 года включительно и получите первый месяц онлайн-подготовки со скидкой 50%.

12 задание ЕГЭ по информатике обычно решает только половина выпускников. Оно правда такое сложное? Нет, если заранее изучить каждый из трех прототипов. Из этой статьи вы узнаете, как справиться с Редактором, Роботом и Чертежником — и как можно сделать это еще проще, используя программирование.

В этой статье:

Прототипы задания 12 и их сложностиРедактор — как решать?Робот — как решать?Прототип Чертежник — как решать?Что нужно запомнить?

До ЕГЭ все меньше времени, и 11-классники уже на финишной прямой. Усилить подготовку и написать на максимальный балл поможет «ЕГЭ-гонка» 🏁 На экспресс-марафоне вы повторите ключевые разделы предмета, прорешаете множество заданий и попробуете симуляцию экзамена, а также узнаете все секреты ЕГЭ-2023 от преподавателей, написавших работу в досрочный период. Записывайтесь на марафон и придите первыми в гонке ЕГЭ!

Прототипы задания 12 и их сложности

12 задание ЕГЭ по информатике относится к повышенному уровню сложности. На экзамене за него можно получить один первичный балл.

Это задание — часть блога «Алгоритмизация». Чтобы решить его, нужно уметь работать с алгоритмами и анализировать их. В этом задании могут встретиться три прототипа заданий: Редактор, Робот и Чертежник. Причем Редактор встречается на экзамене в последнее время чаще других прототипов.

Редактор — это прототип на работу с цепочками цифр или букв. Нам дают алгоритм и строку, содержащую некоторое количество знаков. Нужно узнать, какая строка получится после выполнения программы или посчитать количество символов в строке. 

Если решать подобные задания аналитически, нужно искать закономерности изменения цепочки, чтобы получить ответ. Именно в этом и заключается сложность задания, ведь не все могут правильно найти нужную закономерность. 

Робот — прототип на работу с клетчатой плоскостью и алгоритмом. Вам дают алгоритм и плоскость, содержащую 36 клеток. Нужно найти количество клеток, удовлетворяющее определенному условию. Сложность в том, что ученики начинают проверять все 36 клеток. Делать это не нужно, если проанализировать алгоритм из условия.

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

Редактор — как решать?

Задания с прототипом «Редактор» можно решать как аналитически, так и с помощью компьютера, если у вас все хорошо с программированием. Мы рассмотрим с вами оба способа решения и убедимся, что они дают одинаковые ответы.

Пример 1 (Редактор)

Исполнитель Редактор получает на вход строку цифр и преобразовывает ее.

Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 88 идущих подряд цифр 4? В ответе запишите полученную строку.

Аналитическое решение

Алгоритм сначала заменяет в цепочке цифр все четверки на единицы. Потом начинает заменять назад единицы на четверки, но как только в цепочке образуются 3 четверки, алгоритм заменяет их на единицу. Порядок замены имеет значение при поиске ответа, поэтому его нужно обязательно учитывать. Также важно, что замена выполняется всегда в начале цепочки.

Сначала уберем по возможности все четверки из цепочки.

88 / 3 = 29 и 1 в остатке. 

Получается, что из цепочки уйдет 29 блоков по 3 четверки и образуется 29 единиц, 1 четверка останется в цепочке в самом конце.

Теперь будем последовательно убирать единицы из цепочки.

29 “1” + 1 “4”

1 “4” + 27 “1” + 1 “4”

2 “4” + 25 “1” + 1 “4”

3 “4” + 23 “1” + 1 “4”

24 “1” + 1 “4”

Как только в цепочке появились 3 четверки, алгоритм заменил их назад на единицу. Суммарно из цепочки ушло 5 единиц. Это действие будет повторяться циклически, поэтому можно посчитать, сколько блоков по 5 единиц уйдет из цепочки.

29 / 5 = 5 и 4 в остатке

Получается, что в цепочке останется 4 единицы и 1 четверка.

В итоге в цепочке останется только единица.

Решение с помощью компьютера 

В самом задании у нас уже написана программа. Остается перевести ее на конкретный язык программирования. Напишем программу на Python.

Она будет выглядеть следующим образом:

Создаем строку, содержащую 88 четверок. Далее запускаем цикл, который будет проверять, есть ли в строке 3 четверки или 2 единицы. Пропиваем условие и замену в строке. Важно в методе replace() указать третий параметр, который отмечает, сколько замен нужно выполнить. По умолчанию replace() сразу заменит все цифры в строке, а нам нужно выполнять замены по одной.

При запуске данной программы мы также получим ответ 1.

Пример 2 (Редактор)

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А)  заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)     нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

На вход приведенной ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 25 цифр 1, 45 цифр 2 и 10 цифр 3, расположенных в произвольном порядке.

Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.

Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200.

Аналитическое решение 

Цифры 1, 2 и 3 находятся в строке в произвольном порядке. Все, что нам нужно сделать, чтобы получить ответ — это понять, сколько цифр образовалось в результате замен. 

Каждую единицу алгоритм заменит на тройку. Если изначально было 25 единиц, то в результате замен образуется 25 троек, и их сумма будет равна 25 * 3 = 75.

Каждую двойку алгоритм заменит на 2 единицы. Изначально было 45 двоек, значит, в результате замен образуется 90 единиц. Их сумма будет равна 90.

Каждую тройку алгоритм заменит на 2 тройки. Было 10 троек, станет 20. Сумма составит 20 * 3 = 60.

Итоговая сумма всех цифр цепочки будет равна 75 + 90 + 60 = 225.

Решение с помощью компьютера

Перенесем алгоритм на язык программирования Python.

Получаем следующую программу:

Сначала мы задали строку, содержащую знак “>” и нужное количество всех цифр. Далее в цикле проверяем наличие знака “>” и цифр и выполняем замену. Как только программа вышла из цикла, считаем количество единиц, двоек и троек в строке — и находим сумму. При запуске программы также получается ответ 225.

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

Робот — как решать?

Второй прототип, который включает в себя 12 задание ЕГЭ по информатике — Робот. Этот прототип точно придётся решать аналитически, поэтому давайте разбираться, как сделать это с минимальными затратами времени.

Пример 3 (Робот)

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия. 

Команды-приказы: вверх, вниз, влево, вправо

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервется.

Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно

ПОКА < условие > команда

Выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Если РОБОТ начнет движение в сторону стены, то он разрушится, и программа прервется. 

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?

ПОКА < снизу свободно > вправо

ПОКА < справа свободно > вверх

ПОКА < сверху свободно > влево

ПОКА < слева свободно > вниз

Решение

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

Проверяем по алгоритму 12 отмеченных клеток. 

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

Прототип Чертежник — как решать?

Последний прототип, который составители включили в 12 задание ЕГЭ по информатике — это Чертежник. Здесь при решении важно правильно составить систему уравнений и найти наибольший/наименьший делитель двух чисел. Посмотрим, как это сделать.

Пример 4 (Чертежник)

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b).

Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

ПОВТОРИ число РАЗ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и величины смещения в первой из повторяемых команд неизвестны):

Решение

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

Далее составим систему уравнений. Нам известно, как перемещался Чертежник, и сказано, что он вернулся в начальную точку. Получается, его перемещение равно 0.

Теперь мы можем найти n — наибольшее количество повторений цикла. Число n должно быть делителем как 24, так и 16, то есть нам нужно найти НОД(24, 16). Он равен 8. Это и будет ответом к заданию.

Что нужно запомнить?

1. Если вам попадется Редактор, можете написать программу, которая найдет ответ вместо вас. Но всегда рассчитывайте, что будет рациональнее: аналитическое решение или компьютерное. Если останется время, можно проверить себя вторым способом.
2. Решая задание с Роботом, не нужно проверять все клетки — это долго. Проанализируйте алгоритм и проверяйте только те клетки, которые действительно могут подойти под условия.
3. Чтобы разобраться с Чертежником, внимательно составляйте систему уравнений. Ищите НОД, если нужно найти наибольшее количество повторений цикла. 
4. Если в конце экзамена осталось время, вернитесь к заданию и проверьте его — ребята часто теряют баллы из-за невнимательности. Особенно рекомендую перепроверить Робота — решите его заново. 

Теперь вы знаете, как решать 12 задание ЕГЭ по информатике! Обязательно прочитайте наш гайд по этому экзамену, если хотите разобраться с остальными темами и заданиями. Там вы найдете структуру экзамена, актуальные прототипы, тематические блоки и лайфхаки от наших преподавателей. Желаем удачи в подготовке 🙂

Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».

Давайте разберем поразрядную конъюнкцию. Это задача, которая несколько лет была на ЕГЭ и на всех СтатГрадах, и она как-то исторически вызывает неприятные эмоции у учеников. На самом деле, ничего сложного.

Что такое поразрядная конъюнкция? Это перевод чисел в двоичную систему, а потом разряд с разрядом умножаем. Например, 7 х 4. 7 перевожу в двоичную систему – 1 1 1. 4 перевожу в двоичную систему – 1 0 0. И умножаю разряд с разрядом – 111 х 100=100.

Давайте порешаем задачи.

«Введем выражение М & К, обозначающие поразрядную конъюнкцию М и К (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число А, такое, что выражение

Начнем с короткого обозначения. Выражение Х х 56 =0 обозначим как Х₅₆, в коротком виде. Первое уравнение принимает вид . Нам нужно найти наименьшее натуральное А.

Избавляемся от импликации. Формулу напоминать не буду, наверное, ее уже все знают наизусть.

Теперь мой любимый прием – известная часть пусть будет нулем (0), тогда искомая часть обязана быть единицей (1)

На какой-то момент я забываю про предметную область, я занимаюсь преобразованием до системы.

С нулем работать не очень приятно, поэтому сделаю отрицание и будет единица.

На что мне надо умножить 48, чтобы получились одни нули?

У X должны быть в первом разряде нули, чтобы обнулить единицы у 48, а остальное не важно

И те же самые X я должна умножить на 56 и не получить ноль. Чтобы не получить ноль, мне нужно здесь поставить единицу, чтобы она зацепила единицу от 56

Дальше может стоять что угодно. Все такие X являются решением этого уравнения.

На первой и второй позиции у А может стоять что угодно. Три последние позиции тоже без разницы. Нужно поймать единственную единицу.

Если у А будет здесь единица, я умножу А и Х и ноль не получу. Вот такое А должно быть.
Нужно найти наименьшее. Тогда остальные пусть будут нули.

А это значит 8 в десятичной системе.

Спасибо за то, что пользуйтесь нашими статьями.
Информация на странице «Поразрядная конъюнкция задачи 3» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать необходимые и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из разделов нашего сайта.

Публикация обновлена:
07.05.2023

Автор материалов — Лада Борисовна Есакова.

Законы алгебры логики

Поиск слова, удовлетворяющего условию логического высказывания

Для какого имени истинно высказывание:

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

Поочередно подставим в высказывание значения выражений для имен 2 и 4:

Вторая буква гласная = 1

Первая буква гласная = 0

Последняя буква согласная = 1

Вторая буква гласная = 0

Первая буква гласная = 0

Последняя буква согласная = 1

Поиск числа, удовлетворяющего условию логического высказывания

Для ка­ко­го из при­ведённых чисел X ис­тин­но ло­ги­че­ское усло­вие:

Т.е. число Х должно быть кратно 5, но не кратно 25.

Этому условию удовлетворяет только число под но­ме­ром 3 (65).

Для наглядности введем обозначения: A ≡ (x&A ≠ 0); B ≡ (x&25 ≠ 0); C ≡ (x&17 = 0).

Заменяем импликацию в скобках: ¬В \/ (¬C \/ A) = 1

В результате имеем: ¬В \/ ¬C \/ A = 1

x&25 = 0 \/ x&17 ≠ 0 \/ x&A ≠ 0 = 1

Выражение является дизъюнкцией трех операндов. Дизъюнкция истинна, когда хотя бы один операнд принимает значение истина (1).

Значит, A должно быть таким, чтобы конъюнкция с оставшимися числами x не была равна нулю, т.е. в 3-м разряде двоичной записи числа A должна стоять единица. Наименьшим таким числом является 1000₂ = 8₁₀.

Поиск числового отрезка, удовлетворяющего условию логического высказывания

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

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

При­ме­нив пре­об­ра­зо­ва­ние им­пли­ка­ции, по­лу­ча­ем:

¬A ∨ P ∨ ¬ Q.

Изобразим множества P и ¬ Q на числовой прямой:

Пра­виль­ный ответ ука­зан под но­ме­ром 4.

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

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

Тогда формула примет вид:

Пре­об­ра­зу­ем дан­ное вы­ра­же­ние (заменим импликацию):

¬  (A ∨ ¬ P) ∨ (¬ A ∨ Q)

(¬ A ∧ P) ∨ ¬ A ∨ Q

((¬ A ∧ P) ∨ ¬ A) ∨ Q

¬ A ∨ Q

Поиск множества чисел, удовлетворяющего условию логического высказывания

Эле­мен­та­ми мно­жеств А, P, Q яв­ля­ют­ся на­ту­раль­ные числа, причём

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

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

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

Тогда выражение примет вид:

Преобразуем выражение (заменим импликацию):

(¬ A ∨ P) ∨ ( Q  ∨ ¬ A)

¬ A ∨ P ∨ Q

Чтобы выражение было истинно при любом зна­че­нии пе­ре­мен­ной х, все натуральные числа должны либо входить в P, либо входить в Q, либо не входить в A. Т.е. ¬ A – это все числа, не входящие ни в P, ни в Q. Значит A – это числа, входящие в P или Q. Наи­боль­шее воз­мож­ное ко­ли­че­ство эле­мен­тов в мно­же­стве A – это количество всех различных элементов множеств P и Q. Таких элементов 17.

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

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

Тогда выражение примет вид:

Преобразуем выражение (заменим импликацию):

¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P)

¬P ∨ ¬Q ∨ А.

Спасибо за то, что пользуйтесь нашими статьями.
Информация на странице «Задача №15. Использование основных понятий математической логики. Логические высказывания, числовые отрезки.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.

Публикация обновлена:
07.05.2023

Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».

Забила необходимые цифры и написала формулу

ту формулу растянула до конца, и теперь мне необходимо просто посчитать числа, и вот у меня получилась сумма

А наибольшее число увидели, наложив фильтр по таблице и посмотрели, что отображено в нижней ячейке. Такое решение тоже можно использовать на экзамене тем, кто хорошо пользуется Excel, но не очень программирует. Наш ответ: количество – 314, а наибольшее число – 8993.

Задача № 18:
«Квадрат разлинован на NxN клеток (1˂N˂20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. При попытке выхода за границы квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета от 1 до 100. Посетив клетку, робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером NxN, каждая ячейка которой соответствует клетке квадрата.

пример входных данных:

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

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

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

В клетке А4 (в первой клетке) сумма собранных монет будет равна сумме монет, которая там лежит, то есть 2.
В клетку

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

В клетку С4 мы можем попасть только из В4, суммируем монеты, 12+9=21.

И наконец в D4 попадаем из С4 и получаем 24 монеты.

То же самое касается клеток столбика А.

В А3 можно попасть только из А4, получаем 8 монет, в клетке А2 получаем 12 монет, а в А1 – 15.

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

Аналогично в клетку С3 можно попасть из клетки С4 или из клетки В3. Больше монет в клетке С4, пойдем через нее и получим 25 монет.

На всех остальных клетках, кроме столбца А и строки 4, у меня стоит выбор взять источник монет слева или снизу. Берем тот, который больше.

Вот именно это я и написала в формуле Excel.
В нижний столбик пишем формулу предыдущего и плюс содержание самой ячейки

В левый пишу формулу нижнего плюс сама ячейка

А вот на этой картинке изображено самое интересное

Здесь у нас формула

Это значит, что если левый сосед больше, суммирую его, если нижний больше, то суммирую его.
Размножаем эту формулу до ячейки D

Вверху у меня в итоге оказалось 1178, это и месть наибольшее количество.

Аналогично делаем второй лист таблицы и считаем наименьшее количество. Делаем формулу наоборот: берем соседнюю клетку, в которой меньше монет. Далее растягиваем формулу до верхнего правого угла и получаем ответ 539.

Ответ задачи: наибольшее количество монет, которе смог собрать Робот – 1178, а наименьшее количество – 539.

Задача №24:
«Текстовый файл состоит не более чем из 1 000 000 символов – цифр т 0 до 9. Определите длину самой длинной возрастающей последовательности (количество подряд идущих цифр, каждая из которых строго больше предыдущей). Для выполнения этого задания следует написать программу.»

Приведу вам пример программы на Pascal

Закачиваем файл, считываем в С1 предыдущее значение, в С2 – последующее значение. В случае, если С2 больше С1, счетчик увеличивается на 1. Как только последовательность перестает возрастать или даже повторно цифра пошла, счетчик обнуляется, но длина цепочки запоминается и сравнивается с максимальным значением.

В k храним текущее значение возрастающей последовательности, а в переменной max храню максимальное значение. Как только последовательность закончила возрастать, k больше не увеличиваем, сравниваем, не стала ли последовательность больше максимального значения, максимальное запоминаем, обнуляем и начинаем сначала.

Тут все очень просто.

Все видео по информатике

Публикация обновлена:
08.05.2023