Навигация по странице
О задании
Задание 15 ЕГЭ по информатике направлено на проверку знаний основных понятий и законов математической логики. Суть данного задания заключается в том, что вам необходимо проанализировать представленное логическое выражение и переписать его, используя синтаксис языка Python.
После этого обычно требуется перебрать все возможные значения неизвестной переменной, при которых данное логическое выражение будет истинным. В ответ требуется дать наименьшее или наибольшее значение этой переменной.
Задания данного типа могут решаться как аналитическим методом, то есть вручную, так и программным, на любом доступном вам языке программирования. Хоть данная статья и будет посвящена программным методам решения задания 15, но мы также рассмотрим и базовые элементы математической логики, которые вам понадобятся при ручном решении.
Элементы математической логики
Начнём с определения такой науки, как математическая логика. Можно сказать, что математическая логика — это наука о правильных рассуждениях. В математической логике, в отличие от обычной логики, используются строгие формальные методы, которые позволяют избежать двусмысленности и неоднозначности высказывания.
Это означает, что любое логическое высказывание при заданных величинах должно возвращать только одно значение — истину или ложь.
Примером логического высказывания может быть следующее выражение: «Идёт дождь». Это простое высказывание, которое констатирует факт о том, какая погода за окном. Если действительно на улице идёт дождь, то это высказывание истинно. Если же там солнечная погода — высказывание ложно.
Это элементарное логическое высказывание. То есть мы не можем разбить его на более мелкие части. Но из таких элементарных высказываний можно собрать составное: «Если идёт дождь, то земля мокрая». Здесь мы имеем два элементарных высказывания, которые соединяются логической операцией. В данном случае такой логической операцией является импликация (логическое следование).
Каждая логическая операция имеет своё обозначение на письме. Долго на логических операциях останавливаться не будем. Мы их уже разбирали в прошлой статье. Там же вы можете узнать о порядке операций в алгебре логики и в Python.
Можно составлять сложные логические высказывания, которые состоят сразу из нескольких элементарных. Например, составим такое выражение:
F = (A ∧ ¬B) → (C ∨ D)
Пусть буквами будут обозначены следующие высказывания:
- A: «Идет дождь»
- B: «Я промок»
- C: «Я взял зонт»
- D: «Я остался дома»
Разберём логические операции в нашем выражении:
- Инверсия ¬B: «Я НЕ промок»
- Конъюнкция A ∧ ¬B: «Идет дождь, И я не промок»
- Дизъюнкция C ∨ D: «Я взял зонт ИЛИ остался дома»
- Импликация (A ∧ ¬B) → (C ∨ D): «ЕСЛИ идет дождь, и я не промок, ТО я взял зонт или остался дома»
Стоит отметить очевидный факт: чем сложнее выражение, тем сложнее его анализировать. Но сложные логические выражения мы можем упростить и оптимизировать, что позволит значительно облегчить его анализ и найти эффективный способ его решения (решить выражение — значит сделать вывод: истинное оно или ложное). Для этого используются преобразования логических операций, основанные на законах алгебры логики.
Законы алгебры логики
Закон двойного отрицания
Звучит этот закон следующим образом: «двойное отрицание высказывания эквивалентно самому высказыванию». То есть если мы дважды отрицаем высказывание, то в результате получаем исходное высказывание.
Записать этот закон можно так:
¬(¬A) = A
Давайте вернёмся к нашему дождливому дню. Пусть высказывание «А» такое: «Сегодня идёт дождь». Тогда отрицанием «А» (¬A) будет такое высказывание: «Сегодня НЕ идёт дождь».
Согласитесь, фраза «Сегодня НЕ не идёт дождь», которая является двойным отрицанием «А», будет выглядеть немного странно. Вместо этого мы можем просто вернуться к исходному высказыванию, что и будет подтверждаться законом двойного отрицания.
Законы де Моргана
Законы де Моргана позволяют преобразовать отрицание конъюнкции в дизъюнкцию отрицаний и наоборот — отрицание дизъюнкции в конъюнкцию отрицаний.
Звучит довольно запутанно, так что проще будет показать это в виде двух формул:
¬( A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B)= ¬A ∧ ¬B
То есть мы «раскрываем скобки» у конъюнкции или дизъюнкции.
Давайте разберёмся на примере. Представьте, что прогноз погоды на сегодня такой: «+22℃, Ясно.». Пусть у нас будут такие пессимистичные высказывания:
А — «Сегодня идёт дождь»
B — «Сегодня холодно»
Составим из них выражение ¬(A ∨ B): «Неверно, что сегодня идёт дождь ИЛИ холодно». Звучит такое выражение вполне себе истинно. Но нам оно совсем неясно, приходится поломать голову, прежде чем понять, что же там за погода на улице.
Применим к выражению закон де Моргана и преобразуем отрицание дизъюнкции в конъюнкцию отрицаний — ¬A ∧ ¬B: «Сегодня не идёт дождь И сегодня не холодно». Вот теперь все стало ясно, понятно.
Дистрибутивные Законы
Дистрибутивные законы алгебры логики работают так же, как и дистрибутивные законы в привычной вам алгебре. Особенно это становится очевидным, если учесть, что конъюнкцию и дизъюнкцию можно назвать логическим умножением и сложением.
В рамках школьной математики вам этот закон должен быть известен под именем «распределительный закон». Вспомним, как он работает относительно умножения:
(a + b) * c = a * c + b * c
Теперь заменим операции сложения и умножения на логические — дизъюнкцию и конъюнкцию. Тем самым получим формулы дистрибутивных законов алгебры логики:
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
Вторую строку, откровенно говоря, сложно интерпретировать в обычной алгебре. Но с логическими операциями такое равенство работает отлично.
Давайте теперь приведём пример, иллюстрирующий работу дистрибутивных законов.
Пусть у нас будут такие высказывания:
A — «Я пойду гулять»
B — «На улице тепло»
C — «Светит солнце»
Наконец, примеры с дождём закончились, так что теперь сможем составить такое выражение A ∧ (B ∨ C): «Я пойду гулять И (на улице тепло ИЛИ светит солнце)». Собственно, здесь мы не привередливые, нам достаточно, чтобы на улице либо было тепло, либо хотя бы солнце светило. В любом из этих случаев нас ждёт увлекательная прогулка.
Значит, можем преобразовать это логическое высказывание согласно закону дистрибутивности: «(Я пойду гулять И на улице тепло) ИЛИ (Я пойду гулять И светит солнце)».
Ассоциативные законы
Как и дистрибутивные законы, ассоциативные полностью повторяют работу аналогичных законов из алгебры. Согласно ассоциативному (или сочетательному) закону, мы можем переставлять скобки внутри выражения с одинаковыми операциями.
Как это было в алгебре:
(2 + 3) + 5 = 2 + (3+ 5) = 10
Также и в алгебре логики работают следующие формулы:
(A ∧ B) ∧ C = A ∧ (B ∧ C)
(A ∨ B) ∨ C = A ∨ (B ∨ C)
Порядок группировки этих высказываний никак не повлияет на итоговый результат.
Коммутативные законы
И последняя пара законов, которая пришла напрямую из алгебры — это коммутативные законы. Вам они также могут быть известны под названием «переместительные законы». И совсем детская их интерпретация гласит: «от перемены мест слагаемых, сумма не меняется».
В нашем же случае формулировка звучит немного серьезнее: «порядок операндов не влияет на результат». Записываются эти законы так:
A ∧ B = B ∧ A
A ∨ B = B ∨ A
Действительно, высказывания «Светит солнце И дует ветер» и «Дует ветер И светит солнце» эквивалентны по смыслу, и порядок их операндов никоим образом не повлияет на конечный результат.
Закон идемпотентности
За таким интересным названием скрывается довольно простой закон, который утверждает, что применение одной и той же операции к одному и тому же высказыванию не меняет результат.
Записать его можно так:
A ∧ A = A
A ∨ A = A
Рассмотрим пример с высказыванием «Сегодня понедельник». Если мы скажем «Сегодня понедельник И сегодня понедельник» или «Сегодня понедельник ИЛИ сегодня понедельник», смысл не изменится – сегодня, как был понедельник, так он и останется, сколько раз это не повтори.
Законы дополнения
Законы дополнения показывают, что конъюнкция высказывания с его отрицанием даёт ложь. А дизъюнкция высказывания с его отрицанием, наоборот, в результате даёт истину. В виде формул это выглядит так:
A ∧ ¬A = 0
A ∨ ¬A = 1
Доказать эти законы очень просто. Пусть будет высказывание «Сегодня идёт дождь», тогда логично предположить, что его отрицанием будет «Сегодня НЕ идёт дождь».
Рассмотрим конъюнкцию этих высказываний: «Сегодня идёт дождь И сегодня не идёт дождь». Звучит как бред, так что тут нас явно обманывают.
А теперь представим их дизъюнкцию: «Сегодня идёт дождь ИЛИ сегодня не идёт дождь». Звучит уж очень по-философски, таким высказыванием можно описать буквально каждый день в году, и оно всегда будет истинным.
Законы поглощения
Ну и последние законы в нашем списке — это законы поглощения. Эти законы показывают, что конъюнкция или дизъюнкция высказывания с самим собой поглощает другое высказывание.
Записать их можно так:
A ∨ (A ∧ B) = A
A ∧ (A ∨ B) = A
В качестве примера рассмотрим такие высказывания:
A — «У меня есть компьютер»
B — «У меня есть принтер»
Составим из них такое выражение A ∨ (A ∧ B): «У меня есть компьютер ИЛИ (у меня есть компьютер И у меня есть принтер)». Наличие принтера, конечно, замечательно. Это полезная вещь, а вот без компьютера толку от него будет мало. Так что наше выражение, согласно закону поглощения, можно упросить до такого: «У меня есть компьютер». Наличие дополнительного условия с принтером никак не повлияет на истинность всего выражения.
Поразрядная конъюнкция
В одном из типов задания 15 ЕГЭ вам предстоит работать с поразрядной конъюнкцией. Также она вам понадобится при ручном решении 13 задания ЕГЭ по информатике. Давайте разберёмся, что это за операция и как она выполняется.
Поразрядная конъюнкция — это логическая операция, которая выполняется над числами в их двоичном представлении путем применения операции конъюнкции к каждой паре соответствующих битов.
Выполняется она по такому алгоритму:
- Переводим числа в двоичную систему счисления
- Выравниваем числа по правому краю, при необходимости добавляем ведущие нули
- Справа налево применяем конъюнкцию к каждой паре битов
- Получившийся результат переводим обратно в десятичную систему
Например, выполним поразрядную конъюнкцию чисел 12 и 10. Число 12 в двоично системе записывается как «1100», а число 10 как «1010». Записываем значение десятки под значением 12 и выполняем конъюнкцию:
- 0 ∧ 0 =0
- 0 ∧ 1 = 0
- 1 ∧ 0 = 0
- 1 ∧ 1 = 1
В результате получаем число «1000» или 8 в десятичной системе счисления.
Конечно, при написании программы на Python вам нет нужды проводить все операции вручную. Операция поразрядной конъюнкции уже встроена в язык и обозначается оператором &.
Так, проведённые выше вычисления можно выполнить в языке Python всего за одну строчку:
print(12 & 10)
>>>8
Алгоритм решения
Перед тем как перейдём к разбору алгоритма решения задания 15, давайте заострим внимание на некоторых основных моментах.
В формулировках 15 заданий часто будут встречаться слова «натуральные» или «целые» числа. Давайте вспомним, какие бывают множества чисел.
Начнём с самого малого — множества натуральных чисел. Натуральными называются числа, которые получаются при естественном счёте: 1, 2, 3 и так далее. То есть диапазон натуральных чисел N содержит числа от 1 до +∞. Здесь мы говорим только о целых числах, то есть не содержащих дробную часть!
Далее можно рассмотреть множество неотрицательных чисел. Неотрицательные числа включают в себя натуральные числа и 0. То есть содержат все числа от 0 до +∞.
Ну и последнее множество, которое будет использоваться в данных заданиях, — целые числа. Множество целых чисел представляет собой объединение натуральных чисел с противоположными им (1 и -1, 2 и -2), а также с нулём. То есть все числа от –∞ до +∞ (без дробной части).
Следовательно, если требуется составить диапазон значений натуральных чисел до 100, то это можно сделать такой записью в Python: range(1, 100). Диапазон неотрицательных чисел до 100 можно записать так: range(0, 100). Все целые числа от -100 до 100 формируются следующим диапазоном: range(-100, 100).
Теперь же перейдём к разбору основных типов задания 15.
Тип 1
По правде говоря, разделить задание 15 можно всего на 2 типа: задания на поиск целого значения А из неравенств и задания на поиск длины отрезка А. Также существует и некий гибрид этих двух типов. В таких заданиях предстоит работать как с отрезками, так и с неравенствами в логических выражениях. Причем «гибридные» задания вполне могут попасться вам на экзамене.
Но на практике задания на поиск целого значения можно разбить еще на 3 типа. Решения этих типов хоть и похожи в значительной мере, но имеют некоторые различия в формулировках, которые могут запутать неподготовленного человека.
Первым на очереди у нас будет такой тип, в котором логическое выражение содержит 2 неизвестных. Рассмотрим такую формулировку:
Задание 1500
«Для какого наименьшего целого неотрицательного числа A выражение
(x -3y < A) ∨ (y > 400) ∨ (x > 56)
тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y?»
Как и в задании 2, начнём с того, что определим функцию, в которую перепишем логическое выражение из условия:
def f(x, y, A):
return (x - 3 * y < A) or (y > 400) or (x > 56)
Далее нам нужно перебрать все неотрицательные значения А, при которых все значения функции будут истинными, при переборе различных значений переменных x и y.
То есть составляем цикл для перебора А в диапазоне от 0 до 100. В дальнейшем можно увеличивать правую границу этого диапазона, если значения в пределах этого не будут удовлетворять условию.
for A in range(0, 100):
Внутри цикла будем проверять условие: перебираем значения x и y от 1 до 100, если функция всегда будет принимать истинные значения, то выводим первое же значение переменной А и останавливаем цикл.
Полный код решения этого задания можно записать так:
def f(x, y, A):
return (x - 3 * y < A) or (y > 400) or (x > 56)
for A in range(0, 100):
if all(f(x, y, A)
for x in range(1, 100)
for y in range(1, 100)):
print(A)
break
Обратите внимание, что здесь мы пользуемся не вложенными циклами, а генераторным выражением. А проверяем истинность всех значений с помощью встроенной функции all(). Тем самым добиваемся максимально быстрой работы нашей программы. Для еще большего ускорения, можете попробовать изменить значения диапазонов, главное делайте это осторожно, чтобы не пропустить нужное значение!
В результате работы нашей программы получаем ответ на это задание — 54.
Пример 1
Задание 1501
«Для какого наибольшего целого неотрицательного числа A выражение
(x + y <= 30) ∨ (y <= x + 2) ∨ (y >=A)
тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y?»
Переписываем логическое выражение из условия:
def f(x, y, A):
return (x + y <= 30) or (y <= x+2) or (y >= A)
Здесь можем выбрать диапазоны для А, x и y меньше, чем в прошлой задаче. Скажем, что правую границу диапазонов можно сдвинуть до 50. Главный момент в решении здесь следующий: нам нужно найти наибольшее целое значение А. В таком случае быстрее будет пойти с конца диапазона, применив срез [::-1].
Вы можете работать и без среза, изменив аргументы функции range(). Но помните, что использовать более двух значений в формировании диапазонов — плохой тон!
Представьте, что нужно вывести числа от 49 до 0 включительно. Это можно сделать любым из двух следующих циклов:
for i in range(49, -1, -1):
print(i)
for i in range(0, 50)[::-1]:
print(i)
На наш взгляд, вторая запись выглядит гораздо более читаемой. Мы помним, что range() генерирует последовательность от 0 до 50 не включительно ([0, 1, 2, …, 48, 49]). А уже привычный нам срез [::-1] переворачивает эту последовательность. Все действия понятны и естественны, нет необходимости выдумывать новые значения аргументов range(), с ненужным риском ошибиться в них.
В остальном же, цикл перебора такой же, как и в прошлом задании.
def f(x, y, A):
return (x + y <= 30) or (y <= x+2) or (y >= A)
for A in range(0, 50)[::-1]:
if all(f(x, y, A)
for x in range(1, 50)
for y in range(1, 50)):
print(A)
break
В конце работы программы получаем число 17.
Если честно, то во всех заданиях 15, кроме типа с отрезками, вторая часть кода будет одинакова. Все, что вам придётся менять — это логическое выражение и иногда диапазоны для переменных.
Ниже выделим красным те части кода, которые будут меняться (в случае с одной переменной, цикл для y пропадёт):
def f(x, y, A):
return (x + y <= 30) or (y <= x+2) or (y >= A)
for A in range(0, 50)[::-1]:
if all(f(x, y, A)
for x in range(1, 50)
for y in range(1, 50)):
print(A)
break
Тип 2
Задания данного типа примечательны тем, что здесь нам предстоит реализовать какую-то функцию, которая не представлена среди базовых логических операций. В подавляющем большинстве заданий такой функцией будет «ДЕЛ(n, m)».
Эта функция обозначает утверждение «натуральное число n делится без остатка на натуральное число m». То есть можем записать её таким выражением:
n % m == 0
Вы можете вынести это выражение в отдельную функцию или просто подставлять его в логическое выражение из условия. Мы пойдём вторым путём. Инверсию функции ДЕЛ(n, m) будем записывать через знак «не равно»:
n % m != 0
Рассмотрим такую формулировку:
Задание 1502
«Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A логическое выражение
(ДЕЛ(x, 9) → ¬ ДЕЛ(x, 6)) ∨ (x + A ≥ 100)
истинно (т.е. принимает значение 1) при любом целом положительном значении переменной x?»
Переписываем выражение в виде функции:
def f(x, A):
return ((x % 9 == 0) <= (x % 6 != 0)) or (x + A >= 100)
И, как мы уже выяснили ранее, практически ничего не изменяем в цикле далее. Разве что поменяем диапазоны для A и x и уберём цикл для переменной y.
def f(x, A):
return ((x % 9 == 0) <= (x % 6 != 0)) or (x + A >= 100)
for A in range(1, 500):
if all(f(x, A) for x in range(1, 500)):
print(A)
break
Получаем ответ на это задание — 82.
Пример 2
Задание 1503
«Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А логическое выражение
¬ДЕЛ(x, А) → (ДЕЛ(x, 28) → ¬ДЕЛ(x, 49))
истинно (т.е. принимает значение 1) при любом натуральном значении переменной х?»
Решение аналогично предыдущему заданию. Только теперь ищем наибольшее значение A, значит диапазон для него нужно будет перевернуть.
def f(x, A):
return (x % A != 0) <= ((x % 28 == 0) <= (x % 49 != 0))
for A in range(1, 200)[::-1]:
if all(f(x, A) for x in range(1, 1000)):
print(A)
break
Ответ: 196
Тип 3
К третьему типу относятся задания, в условиях которых фигурирует операция побитовой конъюнкции. Но это не меняет нашего алгоритма решения от слова совсем. Так что подробно останавливаться на них не будем.
Базовая формулировка здесь следующая:
Задание 1504
«Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наибольшего целого положительного числа А выражение
(x & А = 0) ∨ ¬(x & 37 = 0) ∨ ¬(x & 12 = 0)
тождественно истинно (т.е. принимает значение 1) при любом целом значении переменной х?»
Формулировка задания выглядит громоздко, еще и пример поразрядной конъюнкции добавили. Но мы с вами уже знаем, как она работает и каким символом обозначается в Python.
Так что не стоит пугаться, подход здесь будет прежним: переписываем логическое выражение в функцию и перебираем значения для А.
def f(x, A):
return (x & A == 0) or (not (x & 37 == 0)) or (not (x & 12 == 0))
for A in range(1, 100)[::-1]:
if all(f(x, A) for x in range(1, 100)):
print(A)
break
Ответом в этом задании будет число 45.
Пример 3
И еще одно задание на поразрядную конъюнкцию.
Задание 1505
«Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А выражение
x & 39 = 0 ∨ (x & 11 = 0 → ¬(x & А = 0))
тождественно истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?»
Все, как и в прошлом решении, но теперь без переворота диапазона, ведь в этот раз ищем наименьшее значение A.
def f(x, A):
return (x & 39 == 0) or ((x & 11 == 0) <= (not (x & A == 0)))
for A in range(0, 100):
if all(f(x, A) for x in range(0, 100)):
print(A)
break
После работы данной программы получаем ответ на это задание: число 36.
Тип 4
Наконец, мы переходим к самому интересному типу заданий 15. Этот тип еще называют «задание с отрезками».
В таких заданиях обычно даются два отрезка и требуется найти наименьшую или наибольшую длину некоторого отрезка А, для которого будет истинно логическое выражение.
Для примера возьмём такую формулировку:
Задание 1506
«На числовой прямой даны два отрезка:
B = [24; 90] и C = [47; 115]
Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(x ∈ C) → ((¬(x ∈ A) ∧ (x ∈ B)) → ¬(x ∈ C))
истинно (т.е. принимает значение 1) при любом значении переменной х.»
Давайте подумаем, чем этот тип отличается от предыдущих. Первое, что бросается в глаза, здесь мы будем работать с отрезками или же со множествами точек. Будем проверять принадлежность переменной x к этим множествам.
Нам нужно будет как-то сформировать граничные значения для отрезка A, учитывая выколотые точки.
Ну и перебирать здесь будем не одно значение в цикле, а сразу 2, которые означают обе границы отрезка A. В остальном же логика решения этого типа будет такой же, как и во всех предыдущих.
Начнём с отрезков. Помним же, что мы их представляем в виде множеств? Почему так?
Вы могли встретить решения в интернете, где отрезки формируются путём двойных неравенств. Например, здесь это могли быть такие отрезки:
B = 24 <= x <= 90
C = 47 <= x <=115
Мы же будем использовать неизменяемые множества вместо двойных неравенств:
B = frozenset(range(24, 91))
C = frozenset(range(47, 116))
Во-первых, такой код будет более читаемый. Мы будем проверять выражение «x принадлежит С», что эквивалентно операции «x in С» (в переводе «x в С»).
Во-вторых, создать незименяемое множество мы можем перед функцией, в которой будем использовать значения из него. А выполнять операции сравнения для B и C нам придётся именно внутри функции, в которую мы перепишем логическое выражение (из-за того, что переменная x будет иметь локальную область видимости)
И каждый раз, при вызове этой функции, будет вычисляться значение неравенств для B и для C с переданным x. Что занимет больше времени, чем проверка вхождения элемента x во одно из этих множеств.
Привыкайте к тому, что если вы создаёте контейнеры, которые не планируете изменять, то следует использовать для них соответствующие типы данных (кортеж, неизменяемое множество).
А если нужно проверить, находится ли элемент в каком-либо небольшом диапазоне значений (например, является строчной буквой), то лучше храните этот диапазон в виде множества, а вхождение проверяйте оператором in.
Но не пытайтесь таким способом проверить, например, что число семизначное и т.п.! Операции сравнения в таком случае будут работать гораздо быстрее, чем формирование множества всех семизначных чисел.
Вернёмся к нашей задаче. Отрезки мы сформировали, значит, теперь можем переписать логическое выражение. Границы отрезка A (А1 и А2) мы будем создавать сразу внутри функции:
def f(x, A1, A2):
A = A1 <= x <= A2
return (x in C) <= (((not A) and (x in B)) <= (x not in C))
Далее же идёт интересный момент, неправильная реализация которого может увеличить время работы функции до 30 раз.
Нам нужно сформировать последовательность значений, в которых могут находиться границы отрезка А. Понятно, что минимальные и максимальные значения здесь уже определены отрезками B и C: минимальное здесь 24, а максимальное — 115.
Но мы не можем просто взять все целые значения между минимальным и максимальным. Дело в том, что некоторые точки у нас могут быть выколотыми.
Давайте рассмотрим такую ситуацию: есть отрезок P [10, 60] (оранжевые значения) и Q [20, 50] (зелёные значения)
И такое логическое выражение: P != Q ∨ ¬A = 1.
Левая часть этого выражения означает, что когда P истинно, тогда Q ложно и наоборот. Предположим, что у нас P истинно. В таком случае нам подходит область от 10 до 20 и от 50 до 60 (заштрихована оранжевым).
Но, стоит отметить то, что точки 20 и 50 принадлежат как отрезку P, так и отрезку Q. А это означает, что выражение P != Q будет ложным, что нам не подходит. То есть эти точки будут выколотыми. А подходящими будут такие отрезки: [10; 20) и (50; 60], то есть не включая точки 20 и 50.
В таком случае, поскольку у нас в левой части стоит выражение ¬A = 1, то мы будем искать границы отрезка А в пределах от 10 не включительно до 20 включительно: (10: 20] и от 50 включительно до 60: [50; 60).
Чтобы дальше не запутаться, давайте остановимся на таком высказывании: при решении будут некоторые точки, значения которых не будут удовлетворять логическому высказыванию, но они будут входить в границу искомого отрезка.
То есть подставить саму точку в выражение мы не можем. Как быть? Нужно подставить значение, достаточно близкое к этой точке, чтобы выражение приняло истинное значение, но и на длину искомого отрезка это значение не сильно повлияло.
Допустим, такой будет точка 20. Тогда мы не можем использовать её в качестве одной из границ. Но можем использовать ближайшее к ней меньшее или большее значение.
Как определить это ближайшее? В курсе математического анализа вы узнаете, что существует такое понятие, как ε-окрестность (эпсилон-окрестность) точки.
ε-окрестностью точки х0 называется множество всех точек х, расстояние от которых до точки х0 меньше некоторого положительного числа ε. Это понятие как раз и помогает выразить в математической форме наше интуитивное представление о близости некоторых точек на числовой прямой.
Пример ε-окрестности для x0 представлен ниже:
Таким образом, получается, что нам помимо числа 20 необходимо взять число 20 – ε и 20 + ε. Каким взять это значение ε?
Правильно здесь было бы использовать бесконечно малое приращение. В программировании, разумеется, нет бесконечно малого числа, но есть понятие «машинный эпсилон» (видео по теме), которое обозначает минимальное значение для различия двух чисел (1 + ε > 1).
Звучит сложно? Да, вдаваться в столь сложные материи мы здесь не будем. Для решения 15 задания ЕГЭ вполне достаточно использовать значение ε = 0,1.
Тогда генерировать 2 числа в окрестности целых чисел в диапазоне от 24 до 115 мы можем следующим кодом:
arr = [x + eps for x in range(24, 115) for eps in (0, 0.1, 0.9)]
То есть в списке arr у нас будут числа: 24, 24.1, 24.9, 25, 25.1, 25.9 и так далее.
Далее идёт последний блок кода. Это будет цикл, в котором будем перебирать числа, которые могут быть границами отрезка А. С помощью функции combinations() из модуля itertools будем выбирать по 2 числа из списка arr и подставлять их в функцию с нашим логическим выражением.
Если вы не помните, что делает функция combinations(), то она предназначена для генерации всех возможных сочетаний элементов заданной длины.
Пример её работы:
from itertools import combinations
print(*combinations('ABCD', 2))
>>> ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'C') ('B', 'D') ('C', 'D')
Тогда цикл для перебора значений границ отрезка А можно написать так:
ans = []
arr = [x + eps for x in range(24, 115) for eps in (0, 0.1, 0.9)]
for A1, A2 in combinations(arr, 2):
if all(f(x, A1, A2) for x in arr):
ans.append(A2 - A1)
В ответ мы будем давать минимальное или максимальное значение из списка. В нашем случае — минимальное.
Полный код решения этого задания представлен ниже:
from itertools import combinations
B = frozenset(range(24, 91))
C = frozenset(range(47, 116))
def f(x, A1, A2):
A = A1 <= x <= A2
return (x in C) <= (((not A) and (x in B)) <= (x not in C))
ans = []
arr = [x + eps for x in range(24, 115) for eps in (0, 0.1, 0.9)]
for A1, A2 in combinations(arr, 2):
if all(f(x, A1, A2) for x in arr):
ans.append(A2 - A1)
print(min(ans))
В результате получаем ответ 43.
Пример 4
Задание 1507
«На числовой прямой даны два отрезка:
P = [15; 40] и Q = [21; 63]
Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно (т.е. принимает значение 1) при любом значении переменной х.»
Формируем множества:
P = frozenset(range(15, 41))
Q = frozenset(range(21, 64))
Переписываем логическое выражение:
def f(x, A1, A2):
A = A1 <= x <= A2
return (x in P) <= (((x in Q) and (not A)) <= (x not in P))
Формируем диапазон значений и перебираем их комбинации в цикле:
ans = []
arr = [x + eps for x in range(15, 63) for eps in (0, 0.1, 0.9)]
for A1, A2 in combinations(arr, 2):
if all(f(x, A1, A2) for x in arr):
ans.append(A2 - A1)
Полный код будет такой:
from itertools import combinations
P = frozenset(range(15, 41))
Q = frozenset(range(21, 64))
def f(x, A1, A2):
A = A1 <= x <= A2
return (x in P) <= (((x in Q) and (not A)) <= (x not in P))
ans = []
arr = [x + eps for x in range(15, 63) for eps in (0, 0.1, 0.9)]
for A1, A2 in combinations(arr, 2):
if all(f(x, A1, A2) for x in arr):
ans.append(A2 - A1)
print(min(ans))
В результате работы программы получаем число 19.