18 задание егэ информатика отрицательные числа

ЕГЭ информатика 18 задание разбор, теория, как решать.

Динамическое программирование в электронных таблицах. Робот-сборщик монет, (П) — 1 балл

Е18.16 Определите максимальную и минимальную денежные суммы

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут …

Читать далее

Е18.20 количество недоступных клеток, в которые робот не сможет попасть из-за нехватки энергии

Робот с тоит в левом н ижнем углу прямоугольного поля, в каждой клетке которого записано целое число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Выходить за пределы поля робот не может. Числа показывают изменение запаса энергии робота при прохождении соответствующей клетки. Если число отрицательно, запас энергии уменьшается …

Читать далее

Е18.19 Посетив клетку, Робот забирает монету с собой

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут …

Читать далее

Е18.18 Определите количество способов, которыми Робот может попасть из левой верхней клетки в правую нижнюю.

Квадрат разлинован на МхМ клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке пересечь границы квадрата (внутренние, обозначенные жирной линией, или внешние) Робот …

Читать далее

Е18.17 Проходя через клетку, Сборщик собирает все монеты, лежащие на ней

Квадрат разлинован на N×N клеток (2 < N < 21). В каждой клетке записано целое положительное число – количество монет. Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, …

Читать далее

Е18.16 включается в сумму, если оно больше числа в предыдущей клетке на пути робота

Дан квадрат 15×15 клеток, в каждой клетке которого записано целое число. В левом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит …

Читать далее

Е18.15 Между соседними клетками квадрата также могут быть внутренние стены.

Между соседними клетками квадрата также могут быть внутренние стены. Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат …

Читать далее

Е18.14 За посещение клетки A взимается плата 1 монета

За посещение клетки A взимается плата 1 монета Квадрат разлинован на N x N клеток (1 < N < 20). Исполнитель Буквоед может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Буквоед перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке …

Читать далее

Е18.13 каждое следующее число отличалось от предыдущего не более чем на 10

каждое следующее число отличалось от предыдущего не более чем на 10 Дана последовательность вещественных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число отличалось от предыдущего не более чем на 10. Какую максимальную сумму могут иметь выбранные числа? В ответе запишите только целую часть максимально возможной суммы. Исходная последовательность записана …

Читать далее

Е18.12 Два исполнителя – ПРАВО и ЛЕВО – существуют в рамках одного поля.

Два исполнителя – ПРАВО и ЛЕВО – существуют в рамках одного поля. Квадрат разлинован на N×N клеток (2 < N < 20), N – нечетное число. В каждой клетке лежат монеты, количество которых соответствует записанному числу. Количество монет не может быть меньше 1. Два исполнителя – ПРАВО и ЛЕВО – существуют в рамках одного поля. …

Читать далее

Привет! Мы добрались до 18 задания из ЕГЭ по информатике 2021.

Это задание снова решается с помощью компьютера.

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

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

Задача (Стандартная)

Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монеты с собой; это также относится к начальной и конечной клетке маршрута Робота.

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

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

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

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

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

Решение:

Открываем файл к данной задачке.

В начале найдём максимальную сумму.

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

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

В каждой ячейке этой области будет лежать максимальная cумма, которую может собрать Робот, дойдя до этой клетки. Т.к. Робот идёт в верхнюю правую клетку, то, соответственно, в ячейке K12 будет находится нужный нам ответ.

Наш Робот идёт из левой нижней клетки. Поэтому формулу, решающую эту задачу, составим сначала для ячейки B21.

Кликаем на ячейку B21 и пишем формулу:

=МАКС(A21;B22)+B10

Примечание: Чтобы в ячейке начать писать формулу, нужно поставить знак «=».

В любую ячейку нашей области можно попасть либо слева, либо снизу (Т.к. составляем формулу для любой ячейки, то не играет роли, что в данная ячейка угловая). Поэтому для ячейки B21 мы берём предыдущий результат — либо из левой ячейки, либо из правой ячейки, в зависимости от того, где собранная сумма больше.

Эту роль исполняет функция МАКС(). Она помогает выбрать откуда нужно идти, чтобы сумма всегда была максимальна.

Плюс, мы должны добавить сумму для данной ячейки к максимальной сумме предыдущей клетки. Поэтому в формулу дописываем ячейку B10

После того, как составили формулу для одной ячейки B21, можно распространить формулу на всю область.

Подносим мышку к правому нижнему углу. Как только появился чёрный крестик, кликаем левую кнопку мыши, и тянем вверх на 10 строчек вверх.

После того, как столбец готов, выделяем этот столбец, и аналогично, распространяем его на всё пространство.

В итоге получается такая картина:

Видим, что в ячейке K12 значение 1298. Это значение нам и нужно.

Аналогичным образом ищется минимальное значение, только в формуле вместо функции МАКС будет использоваться функция МИН.

Минимальное значение получилось 589.

Ответ: 1298589

Посмотрим ещё одну интересную задачу из примерны задач ЕГЭ по информатике нового образца 2021.

Задача (со стенками)

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может
перемещаться по клеткам, выполняя за одно перемещение одну из двух
команд: вправо или вниз. По команде вправо Робот перемещается
в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата
также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета
достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой;
это также относится к начальной и конечной клеткам маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые
может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа – сначала максимальную сумму, затем
минимальную.

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

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

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

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

Решение:

Открываем файл в программе Excel.

Выделим все ячейки с числами, нажмём «вырезать», используя контекстное меню. Вставим данные на 1 столбец вправо. Это делаем потому, что будем использовать для решения формулу, которая будет обращаться к ячейке слева.

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

Отметим особым цветом те ячейки, которые «спрятаны» от движения Робота стенками.

Для этих ячеек будем составлять другие формулы, в отличии от обычных ячеек.

Цвет ячейки можно поменять, нажав на кнопку «Цвет заливки» на главной вкладке программы.

Т.к. Робот направляется из левой верхней ячейки, то мы сначала и напишем формулу для этой ячейки. Пишем для ячейки B22:

=МАКС(B21;A22)+B1

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

Распространим формулу на всё пространство, не трогая закрашенные клетки.

Получается такая картина:

В ячейки для первой закрашенной области, Робот может попасть только сверху! Поэтому пишем формулу для ячейки H25:

=H24+H4

Распространяем формулу по всему закрашенному столбцу.

В ячейки для второй закрашенной области, Робот может попасть только слева! Поэтому пишем формулу для ячейки М39:

=L39+M18

Распространяем формулу по всей закрашенной строчке.

В правом нижнем углу нашего рабочего пространства получается максимальное количество монет, которое может собрать Робот. В ячейке U41 получается число 721.

Чтобы получить минимальную возможную сумму, в главной формуле функцию МАКС нужно заменить на МИН!

Удобно воспользоваться автоматической заменой через Ctrl+F.

Минимальная сумма равна 640.

Ответ:

Задача (Два Робота)

Квадрат разлинован на N×N клеток (2 < N < 19). В каждой клетке лежат
монеты, количество которых соответствует записанному числу. Количество
монет не может быть меньше 1.

Два исполнителя – ВЕРХ и НИЗ – существуют на одинаковых полях. Первый
имеет две команды – вверх и вправо, второй – вниз и вправо, которые,
соответственно, перемещают исполнитель на одну клетку вверх, вниз или
вправо. Исполнитель ВЕРХ начинает движение в левой нижней ячейке,
исполнитель НИЗ – в левой верхней.

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

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

Пример:

1	8	8	4	10
10	1	1	3	2
1	3	12	2	8
2	3	5	6	11
3	19	14	11	5

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

ВЕРХ84

Решение:

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

Найдём, сколько соберёт монет исполнитель ВЕРХ.

Исполнитель «ВЕРХ» начинает идти с левой нижней клетки. Поэтому первую формулу мы зададим для клетки B27. Эта ячейка является нижней левой клеткой для области, где мы будем составлять решение.

Напишем в ячейке B27:

=МАКС(A27;B28)+B13

Распространим формулу на всё пространство.

Когда исполнитель пройдёт всё поле, в ячейке N15 будет находится ответ. Максимальное количество монет, которое может собрать исполнитель ВЕРХ будет 1743.

Теперь найдём максимальное количество монет, которое может собрать исполнитель НИЗ.

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

Т.к. исполнитель НИЗ стартует с левой верхней клетки, то мы сначала составим формулу для ячейки B15. Эта клетка олицетворяет левую верхнюю ячейку для области, где будет происходить решение.

=МАКС(B14;A15)+B1

В любую ячейку мы можем попасть либо сверху, либо слева. Это не относится к боковым и угловым ячейкам, но формула будет работать и для них.

При составлении максимальной суммы для любой ячейки, мы выбираем максимальное значение суммы из двух предыдущих ячеек + добавляем значение для этой ячейки.

Распространим формулу на всё пространство.

В ячейке N27 будет максимальное значение для исполнителя НИЗ. Получилось 1686.

Видим, что у исполнителя ВЕРХ получилось собрать больше монет.

Ответ: ВЕРХ1743

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

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

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

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

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

Все просто. Выражение «x>10» истинно для всех х, которые являются решением данного неравенства, то есть для x от 10 до +∞. И это выражение ложно для всех x, которые можно описать неравенством (x≤10) или x∈(+∞; 10]. Обратите внимание на число 10, когда x=10, логическая переменная (x>10) ложна.

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

Допустим, наша переменная — «x делится на 5». Тогда она истинна для всех х, которые кратны 5 (0, 5, 10, 15,…). Обратите внимание на то, что 0 кратен любому числу, а значит кратен 5 и тоже даст истинное значение. Методом исключения, данная логическая переменная ложна при всех х, которые не делятся на 5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 1

Решение

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

Вторая и третья скобки не зависят от А и обеспечат истинность всего выражения, независимо от параметра, если 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.

Получаем: A = [150; 171].

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

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

Ответ: 21

Пример 3

Решение

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

Получаем выражение

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

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

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

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

Ответ:
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₁₀.

Ответ: 6

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

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

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

Скачать материал

Скачать материал

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Автор:
  учитель информатики МБОУ «Лицей»
  первой квалификационной категории
  Мурзина Ольга Ивановна
  МБОУ «Лицей» г. Арзамас
  МКУ ГИМК
  Теория и практика решения задания 18 ЕГЭ по информатике
  Арзамас, 2017

• 

  2 слайд

  Мнемоническое правило
  Один из ее главных принципов – дополнение до целого (дополнение противоположностью)
  Соционика – это информационная психология

• 

• 

  4 слайд

  Решающая формула
  А  ¬А = 1
  А  ¬А = 0
  В алгебре логики есть формула дополнения до целого:
  В некоторых задачах мы будем использовать вместо этой формулы умножение противоположностей:

• 

  5 слайд

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

• 

  6 слайд

  Задания на отрезки
  (№ 376) На числовой прямой даны два отрезка: P=[4,15] и Q=[12,20]. Укажите наименьшую возможную длину такого отрезка A, что формула
  ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)
  тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
  Источник — сайт Полякова К.Ю.

• 

  7 слайд

  Решающая формула
  А  ¬А = 1
  Для выбора решающей формулы важно внимательно прочитать требование задачи.
  В нашей задаче в требовании сказано:
  принимает значение 1 при любом значении переменной х.
  Выбор решающей формулы очевиден:

• 

  8 слайд

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

• 

  9 слайд

  Решение задачи на отрезки
  Легенда – это удобные нам условные обозначения, которые мы будем использовать при решении.
  Введем следующие обозначения:
  P = x  P
  Q = x  Q
  A = x  A

• 

  10 слайд

  Решение задачи на отрезки
  2) Формализация условия – перепишем формулу из условия задачи в соответствие с легендой.
  Было:
  ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) = 1
  Стало:
  (P ∧ Q) → A = 1

• 

  11 слайд

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

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

• 

  12 слайд

  Решение задачи на отрезки
  3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В:
  (P ∧ Q) → A = 1

  ¬(P ∧ Q)  A = 1

• 

  13 слайд

  Решение задачи на отрезки
  3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А  ¬А = ¬А  А) :
  ¬(P ∧ Q)  A = 1, отсюда
  ¬А = ¬(P ∧ Q)
  Ответом в логическом уравнении будет:
  А = P ∧ Q.

• 

  14 слайд

  Решение задачи на отрезки
  4) Интерпретация полученного результата.
  Наш ответ: А = P ∧ Q.
  В алгебре логики это выражение означает пересечение объемов двух логических объектов. По условию нашей задачи – это пересечение отрезков P и Q.

• 

  15 слайд

  Решение задачи на отрезки
  Пересечение отрезков P и Q можно визуализировать: P=[4,15] и Q=[12,20].
  4
  12
  15
  20
  По условию нашей задачи, нам нужна минимальная длина отрезка А. Находим ее: 15 – 12 = 3.
  Ответ: 3.
  Ответ на сайте Полякова К.Ю.: 3

• 

  16 слайд

  Задания на отрезки
  (№ 360) На числовой прямой даны три отрезка: P=[10,25], Q=[15,30] и R=[25,40]. Какова максимальная длина отрезка A, при котором формула
  ((x ∈ Q) → (x ∉ R) ) ∧ (x ∈ A) ∧ (x ∉ P)
  тождественно ложна, то есть принимает значение 0 при любом значении переменной х?
  Источник — сайт Полякова К.Ю.

• 

  17 слайд

  Решающая формула
  А  ¬А = 0
  Для выбора решающей формулы важно внимательно прочитать требование задачи.
  В нашей задаче в требовании сказано:
  принимает значение 0 при любом значении переменной х.
  Выбор решающей формулы очевиден:

• 

  18 слайд

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

• 

  19 слайд

  Решение задачи на отрезки
  Легенда
  R = x  R
  Q = x  Q
  A = x  A
  P = x  P

• 

  20 слайд

  Решение задачи на отрезки
  2) Формализация условия
  Было:
  ((x ∈ Q) → (x ∉ R) ) ∧ (x ∈ A) ∧ (x ∉ P) = 0
  Стало:
  ( Q → ¬R ) ∧ A ∧ ¬ P = 0

• 

  21 слайд

  Решение задачи на отрезки
  3) Решение логического уравнения
  ( Q → ¬R ) ∧ A ∧ ¬ P = 0
  3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В, и переставим множители согласно закону коммутативности умножения:
  A ∧ (¬ Q  ¬R ) ∧ ¬ P = 0

• 

  22 слайд

  Решение задачи на отрезки
  3) Решение логического уравнения
  A ∧ (¬ Q  ¬R ) ∧ ¬ P = 0
  3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 0 и найдем, чему равно ¬А :
  ¬А = (¬ Q  ¬R ) ∧ ¬ P

• 

  23 слайд

  Решение задачи на отрезки
  3) Решение логического уравнения
  ¬А = (¬ Q  ¬R ) ∧ ¬ P
  3.3. Упростим выражение для ¬А по закону де Моргана ¬А¬В=¬(АВ):
  ¬А = ¬ (Q  R ) ∧ ¬ P,
  и по другому закону де Моргана ¬А¬В=¬(АВ):
  ¬А = ¬ (Q  R  P)

• 

  24 слайд

  Решение задачи на отрезки
  3) Решение логического уравнения
  ¬А = ¬ (Q  R  P)

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

  А = Q  R  P

• 

  25 слайд

  Решение задачи на отрезки
  4) Интерпретация полученного результата
  А = Q  R  P
  Отрезок А – это пересечение отрезков Q и R и его объединение с отрезком Р.

• 

  26 слайд

  Решение задачи на отрезки
  Пересечение отрезков R и Q можно визуализировать: Q=[15,30] и R=[25,40].
  15
  25
  30
  40
  Отрезок P=[10,25] нанесем на наш чертеж и объединим с пересечением:
  15
  25
  30
  40
  10

• 

  27 слайд

  Решение задачи на отрезки
  15
  25
  30
  40
  10
  По условию нашей задачи, нам нужна максимальная длина отрезка А. Находим ее: 30 – 10 = 20.
  Ответ: 20.
  А = Q  R  P
  Ответ на сайте Полякова К.Ю.: 20

• 

  28 слайд

  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.
  Источник — сайт Полякова К.Ю.

• 

  29 слайд

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

• 

  30 слайд

  Решение задачи на множества
  Легенда
  A = x ∈ A
  P = x ∈ P
  Q = x ∈ Q

• 

  31 слайд

  Решение задачи на множества
  2) Формализация условия
  Было:
  (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q) = 1
  Стало:
  ¬ A → (¬P ∧ Q)  ¬ Q = 1

• 

  32 слайд

  Решение задачи на множества
  3) Решение логического уравнения
  ¬ A → (¬P ∧ Q)  ¬ Q = 1
  3.1. Представим логическое следование в базовых логических операциях и сгруппируем:
  A  ((¬P ∧ Q)  ¬ Q) = 1

• 

  33 слайд

  Решение задачи на множества
  A  ((¬P ∧ Q)  ¬Q) = 1
  3.2. Сведем получившееся выражение к решающей формуле:
  А  ¬А = 1
  и найдем, чему равно ¬А :
  ¬А = (¬P ∧ Q)  ¬Q

• 

  34 слайд

  Решение задачи на множества
  ¬А = (¬P ∧ Q)  ¬Q
  3.3. Упростим выражение для ¬А, раскрыв скобки по закону дистрибутивности сложения:
  ¬А = (¬P  ¬Q)  (Q  ¬Q)
  Q  ¬Q = 1
  ¬А = (¬P  ¬Q)

• 

  35 слайд

  Решение задачи на множества
  ¬А = (¬P  ¬Q)
  По закону де Моргана:
  ¬А = ¬(P  Q)
  3.4. Очевидно, что
  А = P  Q

• 

  36 слайд

  Решение задачи на множества
  А = P  Q
  4) Интерпретация полученного результата
  Искомое множество А представляет собой пересечение множеств P и Q.

• 

  37 слайд

  Решение задачи на множества
  Искомое множество А есть пересечение множеств
  P = 1, 2, 3, 4, 5, 6 и Q ={3, 5,15}, таким образом A ={3, 5}
  и содержит только 2 элемента.
  Ответ: 2
  Ответ на сайте Полякова: 2

• 

  38 слайд

  2. Задания на множества
  (№ 368) Элементами множеств А, P, Q являются натуральные числа, причём P={2,4,6,8,10,12} и Q={4,8,12,116}. Известно, что выражение
  (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))
  истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
  Источник — сайт Полякова К.Ю.

• 

  39 слайд

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

• 

  40 слайд

  Легенда
  A = x ∈ A
  P = x ∈ P
  Q = x ∈ Q
  Решение задачи на множества

• 

  41 слайд

  2) Формализация условия
  Было:
  (x ∈ P)→(((x ∈ Q) ∧ (x ∉ A))→(x ∉ P)) = 1
  Стало:
  P → ((Q ∧ ¬A) → ¬P) = 1
  Решение задачи на множества

• 

  42 слайд

  Решение задачи на множества
  3) Решение логического уравнения
  P → ((Q ∧ ¬A) → ¬P) = 1
  3.1. Представим первое логическое следование (в скобках) в базовых логических операциях :
  P → (¬(Q ∧ ¬A)  ¬P) = 1

• 

  43 слайд

  Решение задачи на множества
  P → (¬(Q ∧ ¬A)  ¬P) = 1
  Представим второе логическое следование в базовых логических операциях, применим закон де Моргана и перегруппируем:
  ¬P (¬(Q ∧ ¬A)  ¬P) = 1
  ¬P ¬Q  A  ¬P = 1

• 

  44 слайд

  Решение задачи на множества
  A  (¬P ¬Q  ¬P) = 1
  3.2. Сведем получившееся выражение к решающей формуле:
  А  ¬А = 1
  и найдем, чему равно ¬А :
  ¬А = (¬P ¬Q  ¬P)

• 

  45 слайд

  Решение задачи на множества
  ¬А = ¬P ¬Q  ¬P
  3.3. Упростим выражение для ¬А по формуле А  А = А:
  ¬А = ¬P ¬Q
  Далее, по закону де Моргана получаем:
  ¬А = ¬(P Q)

• 

  46 слайд

  Решение задачи на множества
  ¬А = ¬(P Q)
  3.4. Очевидно, что
  А = P Q
  4) Интерпретация полученного результата
  Искомое множество А представляет собой пересечение множеств P и Q.

• 

  47 слайд

  Решение задачи на множества
  Искомое множество А есть пересечение множеств
  P = 2, 4, 6, 8, 10, 12 и
  Q ={4, 8, 12, 16}, таким образом
  A ={4, 8, 12}
  и содержит только 3 элемента, сумма которых 4+8+12=24 .
  Ответ: 24
  Ответ на сайте Полякова: 24

• 

  48 слайд

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

• 

  49 слайд

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

• 

  50 слайд

  Легенда
  Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:
  B = (x & 29 ≠ 0) 
  C = (x & 12  ≠  0)
  A = (x & А ≠ 0)
  Решение задачи на поразрядную конъюнкцию

• 

  51 слайд

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

• 

  52 слайд

  2) Формализация условия
  Было:
  (x & 29 ≠ 0)→((x & 12 = 0)→(x & А ≠ 0))=1
  Стало:
  В → (¬С → А) = 1
  Решение задачи на поразрядную конъюнкцию

• 

  53 слайд

  3) Решение логического уравнения
  В → (¬С → А) = 1
  В → (С А) = 1
  (¬В  С) А = 1
  ¬А = ¬В  С
  ¬А = ¬(В ¬ С)
  Очевидно, что
  А = В ¬ С
  Решение задачи на поразрядную конъюнкцию

• 

  54 слайд

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

• 

  55 слайд

  Решение задачи на поразрядную конъюнкцию
  B = (x & 29 ≠ 0)
  В или 29 = 111012 
  C = (x & 12  ≠  0)
  12 = 11002
  ¬С или инверсия 12 = 00112

• 

  56 слайд

  Решение задачи на поразрядную конъюнкцию
  В или 29 = 111012 
  ¬С или инверсия 12 = 00112
  А = В ¬ С
  х111012
  00112
  100012
  А = 100012 = 17

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

• 

  57 слайд

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

• 

  58 слайд

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

• 

  59 слайд

  Легенда
  Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:
  B = (x & 49 ≠ 0) 
  C = (x & 33 ≠  0)
  A = (x & А ≠ 0)
  Решение задачи на поразрядную конъюнкцию

• 

  60 слайд

  2) Формализация условия
  Было:
  (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1
  Стало:
  В → (¬С → А) = 1
  Решение задачи на поразрядную конъюнкцию

• 

  61 слайд

  3) Решение логического уравнения
  В → (¬С → А) = 1
  В → (С  А) = 1
  (¬В  С)  А = 1
  ¬А = (¬В  С)
  Очевидно:
  А = В ¬С
  Решение задачи на поразрядную конъюнкцию

• 

  62 слайд

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

• 

  63 слайд

  Решение задачи на поразрядную конъюнкцию
  B = (x & 49 ≠ 0)
  В или 49 = 1100012 
  C = (x & 33  ≠  0)
  33 = 1000012
  ¬С или инверсия 33 = 0111102

• 

  64 слайд

  Решение задачи на поразрядную конъюнкцию
  В или 49 = 1100012
  ¬С или инверсия 33 = 0111102
  А = В ¬ С
  х1100012
  0111102
  0100002
  А = 100002 = 16

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

• 

  65 слайд

  4. Задания на условие делимости
  (№ 372) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула
  ¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))
  тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
  Источник — сайт Полякова К.Ю.

• 

  66 слайд

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

• 

  67 слайд

  Легенда
  Решение задачи
  на условие делимости
  Легенда простая:
  А = ДЕЛ(x,А)
  21 = ДЕЛ(х,21)
  35 = ДЕЛ(x,35)

• 

  68 слайд

  2) Формализация условия
  Решение задачи
  на условие делимости
  Было:

  ¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))
  ¬А → (¬21 ∧ ¬35) = 1
  тождественно истинна (то есть принимает значение 1)

  Стало:

• 

  69 слайд

  3) Решение логического уравнения
  Решение задачи
  на условие делимости
  ¬А → (¬21 ∧ ¬35) = 1
  А (¬21 ∧ ¬35) = 1
  ¬А = ¬21 ∧ ¬35
  Очевидно, что
  А = 21  35

• 

  70 слайд

  4) Интерпретация полученного результата
  А = 21  35
  В данной задаче это самый сложный этап решения. Нужно понять, что же представляет из себя число А – НОК или НОД или …
  Решение задачи
  на условие делимости

• 

  71 слайд

  4) Интерпретация полученного результата
  А = 21  35
  Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем
  А = НОД (21, 35) = 7
  Решение задачи
  на условие делимости
  Ответ на сайте Полякова: 7

• 

  72 слайд

  4. Задания на условие делимости
  (№ 370) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула
  ¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))
  тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
  Источник — сайт Полякова К.Ю.

• 

  73 слайд

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

• 

  74 слайд

  Легенда

  А = ДЕЛ(x,А)
  6 = ДЕЛ(x,6)
  4 = ДЕЛ(x,4)

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

• 

  75 слайд

  2) Формализация условия
  Решение задачи
  на условие делимости
  Было:

  ¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))
  тождественно истинна (то есть принимает значение 1

  Стало:

  ¬А → (6 → ¬4) = 1

• 

  76 слайд

  3) Решение логического уравнения
  ¬А → (6 → ¬4) = 1
  ¬А → (¬ 6  ¬4) = 1
  А  (¬ 6  ¬4) = 1
  ¬А = ¬ 6  ¬4
  Очевидно:
  А = 64

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

• 

  77 слайд

  4) Интерпретация полученного результата
  А = 64
  Итак, А таково, что Х делится на него без остатка тогда и только тогда, когда Х делится без остатка и на 6, и на 4. Т.е. А = НОК(6, 4) = 12
  Ответ на сайте Полякова: 12
  Решение задачи
  на условие делимости

• 

  78 слайд

  Рефлексия
  Оцените, пожалуйста, свой уровень понимания, достигнутый на занятии, по шкале от 0 до 10.
  Сможете ли Вы теперь объяснить решение задания 18 своим ученикам или друзьям?
  (да, нет, не знаю).

• 

  79 слайд

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

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 152 860 материалов в базе

• Выберите категорию:

• Выберите учебник и тему

• Выберите класс:

• Тип материала:

  • Все материалы

  • Статьи

  • Научные работы

  • Видеоуроки

  • Презентации

  • Конспекты

  • Тесты

  • Рабочие программы

  • Другие методич. материалы

Найти материалы

Вам будут интересны эти курсы:

• Курс повышения квалификации «Основы местного самоуправления и муниципальной службы»

• Курс повышения квалификации «Основы управления проектами в условиях реализации ФГОС»

• Курс повышения квалификации «История и философия науки в условиях реализации ФГОС ВО»

• Курс повышения квалификации «Организация практики студентов в соответствии с требованиями ФГОС юридических направлений подготовки»

• Курс профессиональной переподготовки «Организация деятельности по подбору и оценке персонала (рекрутинг)»

• Курс профессиональной переподготовки «Организация менеджмента в туризме»

• Курс повышения квалификации «Организация маркетинга в туризме»

• Курс повышения квалификации «Финансовые инструменты»

• Курс профессиональной переподготовки «Метрология, стандартизация и сертификация»

• Курс профессиональной переподготовки «Гостиничный менеджмент: организация управления текущей деятельностью»

• Курс профессиональной переподготовки «Организация процесса страхования (перестрахования)»

• Курс профессиональной переподготовки «Организация маркетинговой деятельности»

Л. И. Мазничевская

средняя общеобразовательная школа № 763, Москва

Решение задания 18 ЕГЭ ПО ИНФОРМАТИКЕ С ПОМОЩЬЮ ТАБЛИЦ ИСТИННОСТИ

Аннотация

В статье представлены материалы, предназначенные для использования учителями информатики при подготовке учащихся к ЕГЭ по информатике.

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

В представленных вашему вниманию материалах четыре различных типа задач решаются с помощью составления таблиц истинности. Все задачи выбраны из заданий для тренировки с известного сайта К. Ю. Полякова[1].

Ключевые слова: информатика, таблица истинности, алгоритм, законы алгебры логики, импликация.

Контактная информация

Мазничевская Лариса Ивановна, учитель информатики высшей категории, государственное бюджетное общеобразовательное учреждение города Москвы “Школа № 763”, адрес: 129346, г. Москва, ул. Стартовая, д. 27, к. 3; телефон: (495) 474-90-60; e-mail: mli[email protected]inbox.ru

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

• определение элементарных высказываний

• замена переменных (при необходимости)

• раскрытие импликации или эквивалентности

• преобразование с использованием законов алгебры логики

• построение таблиц истинности

• запись ответа.

Задача 1(105 Поляков)

На числовой прямой даны два отрезка: P = [44; 49] и Q = [28; 53]. Укажите наибольшую возможную длину такого отрезка A, что формула

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

Решение:

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

=P Q

Вся числовая ось распадается на интервалы, построим таблицу истинности для одного из значений заданного интервала для полученной формулы

Интервал	Значение Х	P	Q		А	Итог
(-;28]	20	0	0	1	0	1
[28;44]	30	0	1	любое	любое	1
[44;49]	48	1	1	любое	любое	1
[49;53]	50	0	1	любое	любое	1
[53;+]	54	0	0	1	0	1

Так как нам нужна наибольшая возможная длина такого отрезка A, чтобы формула

была тождественно истинна, то есть принимала значение 1 при любом значении переменной х, то А принимает значение истинно на [28;53], длина этого отрезка равна 53-28=25

Ответ: 25

Задача 2(135 Поляков)

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

ДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))

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

Решение:

Упростим выражение:

ДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))=  ДЕЛ(x, A) ДЕЛ(x, 14)  ДЕЛ(x, 21)

Определим числа, входящие во множество ДЕЛ(x, 14) и ДЕЛ(x, 21): 14, 21, 28, 42, 56,63…

Построим таблицу истинности для формулы  ДЕЛ(x, A) ДЕЛ(x, 14)  ДЕЛ(x, 21)

Число Х	ДЕЛ(x, 14)	ДЕЛ(x,21)	ДЕЛ(x, 14)  ДЕЛ(x, 21)	Х не кратно А	А	Итог
14	1	0	0	1	0	1
21	0	1	0	1	0	1
28	1	0	0	1	0	1
42	1	1	1	любое	любое	1
56	1	0	0	1	0	1

Необходимо выбрать первое значение А, при котором высказывание «Х не кратно А»может принимать любое значение Х=42, оно является наименьшим.

Ответ: 42

Задача 3(150 Поляков)

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

(X & 56  0)  ((X & 48 = 0)  (X & A  0))

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

Решение:

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

56= X & 56  0

48=X & 48  0

A= X & A  0

(X & 56  0)  ((X & 48 = 0)  (X & A  0))=56  ( 48  A ) = А

Переведем в двоичную систему счисления числа 18, 54

56₁₀=111000₂

48₁₀=110000₂

Искомое число х – разрядное слагаемое двоичной системы счисления из множества {1, 2, 4,8,16,32}. Построим таблицу истинности

Число Х, его двоичный код	X & 56 = 0 1110002	X & 48  0 1100002	А X & A  0	Итог
1, 000001	1	0	Любое(0 или1)	1
2, 000010	1	0	Любое(0 или1)	1
4, 000100	1	0	Любое(0 или1)	1
8, 001000	0	0	1	1
16, 010000	0	1	Любое(0 или1)	1
32, 100000	0	1	Любое(0 или1)	1

Из таблицы х=8, оно является наименьшим

Ответ: 8

Задача 4(88 Поляков)

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

(x {2, 4, 6, 8, 10, 12}) → (((x {3, 6, 9, 12, 15})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))

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

Решение:

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

В=x {2, 4, 6, 8, 10, 12}

С= x {3, 6, 9, 12, 15}

А= x A

(x {2, 4, 6, 8, 10, 12}) → (((x {3, 6, 9, 12, 15})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))=B→((C ¬A) → ¬B) = ¬B((C ¬A) → ¬B)= ¬B¬C ¬A) ¬B= ¬B¬C

Построим таблицу истинности

Число Х	¬B	¬C	A	Итог
2	0	1	любое(0 или1)	1
3	1	0	любое(0 или1)	1
4	0	1	любое(0 или1)	1
6	0	0	1	1
8	0	1	любое(0 или1)	1
9	1	0	любое(0 или1)	1
10	0	1	любое(0 или1)	1
12	0	0	1	1
15	1	0	любое(0 или1)	1

6+12=18

Ответ: 8

Литература

1. http://kpolyakov.spb.ru/school/probook.htm