Учебник 2.0

Разбор заданий/учимся решать

Решаем задания типа 2, 5, 12, 15

Модуль: Решаем задания типа 2, 5, 12, 15

3. Как "правильно" решать задание типа 15 из ЕГЭ

Задание типа 15 - Знание основных понятий и законов математической логики
Повышенный уровень сложности. На выполнение задания отводиться 3 минуты (по спецификации КЕГЭ)

По формулировкам, задания можно разбить на несколько типов (иногда встречаются смешанные типы):

О (отрезки) - предпочтительно решать "ручным" способом
Б (битовые операции) - предпочтительно решать "программным" способом
Д (делители) - предпочтительно решать "программным" способом
Г (графики) - предпочтительно решать "программным" способом

Задания 15 тип О (отрезки)
Оптимальный (по времени) способ решения - преобразование формулы,
создание схемы отрезков и выбор требуемого результата.
Рекомендуемый способ решения - "ручной"
Пример задания (пробник, май 2022)
На числовой прямой даны три отрезка: P = [15; 37], Q = [41; 71] и R = [21; 53].
Укажите наименьшую возможную длину такого отрезка А, что формула
((x∉P)→(x∈Q))∧(x∈R)∧(x∉A)
тождественно ложна, то есть принимает значение 0 при любых целых неотрицательных значения x?

Задания 15 типа Б (битовые операции)
Наиболее "неудобный" тип для "ручного" способа решения.
Наличие в Питоне соответствующих операций делает "программный" способ очень простым
Рекомендуемый способ - "программный"
Пример задания (из открытого банка ФИПИ)
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&39 = 0 \/ (x&11 = 0 → x&А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Задание 15 типа Д (делители)
Несложная реализация делает предпочтительным "программный" способ решения.
Однако, умение решать "ручным" способом, решает проблемы "определения диапазонов проверки" для переменных
Рекомендуемый способ решения - "программный" (со знанием "ручного")
Пример задания (открытый вариант 2022)
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
(ДЕЛ(x, 3) → ¬ДЕЛ(x, 5)) \/ (x + A ≥ 90)
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?

Задания 15 типа Г (графики)
Для пользователя с хорошей математической подготовкой нет проблем "ручного" решения
При "программном" способе решения нет проблем с реализацией,
но возникает проблема "определения диапазонов проверки"
При решении заданий этого типа надо представлять ход решения "ручным" способом,
но решать "программным" способом
Пример задания (из открытого банка ФИПИ)
Для какого наименьшего целого неотрицательного числа A выражение
(x < A) \/ (y < A) \/ (x + 2y > 50)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?

Что надо знать для решения заданий типа 15?

Модель проверки "для всех" поясним примером для задания
Для какого наименьшего неотрицательного целого числа А формула
x&39 = 0 \/ (x&11 = 0 → x&А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

def f15(x,A): #программа проверки истинности для фиксированных x, A
  # вычисление и возврат значения логического выражения
  return ( (x & 39 ) == 0 ) or ( ( x & 11 ) != 0 ) or ( ( x & A ) != 0 )
def g15(A) : # проверка истинности для "всех" x при фиксированном A
  for x in range (1000000) : # здесь "все" это миллион :))) А достаточно ...?
    if f15(x,A) == False : # есть исключение - значит не "для всех"
      return False
  return True
# основной блок - перебор A (можно разными способами)
A=0 # начальное значение 
while g15(A) == False : # поиск до первого успеха
  A+=1 # переход к следующему значению
print (A) # вывод результата

Пример иллюстрирует модель "для всех ..." при требовании найти минимальное значение

Разбор заданий 15 типа В (битовые операции)
Как понять, какой диапазоном по х достаточно проверять? В примере взяли до миллиона, а до какого значения НАДО?
В чем состоят "повышенные знания" (кроме упрощения формулы)
Изменим программу и попробуем проверить диапазон значений по A

def f15(x,A): #программа проверки истинности для фиксированных x, A
  # вычисление и возврат значения логического выражения
  return ( (x & 39 ) == 0 ) or ( ( x & 11 ) != 0 ) or ( ( x & A ) != 0 )
def g15(A) : # проверка истинности для "всех" x при фиксированном A
  for x in range (1000) : # здесь "все" сократим до 1000 А достаточно ...?
    if f15(x,A) == False : # есть исключение - значит не "для всех"
      return False
  return True
# основной блок - перебор A 
for A in range(int(input())):
  if g15(A) == True : # значение найденопоиск до первого успеха
    print (A) # вывод результата

Заметим, что диапазон подходящий значений по A составляет [36;63] - значит вопрос мог быть поставлен и
о нахождении максимального значения (понять, что оно такое - тоже "повышенные знания")
Изменим константы в задаче и посмотрим на результаты.

def f15(x,A): #программа проверки истинности для фиксированных x, A
  # вычисление и возврат значения логического выражения
  return ( (x & 119 ) == 0 ) or ( ( x & 101 ) != 0 ) or ( ( x & A ) != 0 )
def g15(A) : # проверка истинности для "всех" x при фиксированном A
  for x in range (1000) : # здесь "все" сократим до 1000 А достаточно ...?
    if f15(x,A) == False : # есть исключение - значит не "для всех"
      return False
  return True
# основной блок - перебор A 
for A in range(int(input())):
  if g15(A) == True : # значение найденопоиск до первого успеха
    print (A) # вывод результата

Нетрудно убедиться, что значения по A уже не составляют непрерывный интервал и их количество неограничено,
хотя они составляют периодическую последовательность (если взять остатки по модулю 32)
Попробуем изменить знак неравенства в ( (x&A) !=0 ) на знак равенства

def f15(x,A): #программа проверки истинности для фиксированных x, A
  # вычисление и возврат значения логического выражения
  return ( (x & 119 ) == 0 ) or ( ( x & 101 ) != 0 ) or ( ( x & A ) == 0 )
def g15(A) : # проверка истинности для "всех" x при фиксированном A
  for x in range (1000) : # здесь "все" сократим до 1000 А достаточно ...?
    if f15(x,A) == False : # есть исключение - значит не "для всех"
      return False
  return True
# основной блок - перебор A 
for A in range(int(input())):
  if g15(A) == True : # значение найденопоиск до первого успеха
    print (A) # вывод результата

Подведем итог по заданию 15 типа Б (битовые операции)

диапазон значений для проверки определяется степенью числа 2, "поглащающей" все константы
задания могут формулировать как на поиск "наименьшего", "наибольшего", "количества таких А",
возможно увеличение числа неизвестных (добавление у)
возможно использование с условиями на отрезки

Решаем задание 15 типа Д (делители)
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
(ДЕЛ(x, 3) → ¬ДЕЛ(x, 5)) \/ (x + A ≥ 90)
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
Простата "программного" способа решения определяется тем, что

x и A принимаю только натуральные значения
"легкостью" понимания что "при x>=90" или "A>=90" формула будет принимать значение True

Вначале разберем "ручное" (аналитическое) решение.
Формула составлена по шаблону (K → ¬L) \/ M = (¬K \/ ¬L) \/ M
удобно преобразовать в ¬(K /\ L) \/ M, так как (K /\ L) есть ДЕЛ(x, 3) /\ ДЕЛ(x, 5) = ДЕЛ(x, 15)
и в итоге получим ¬ДЕЛ(x, 15) \/ (x + A ≥ 90)
следовательно неравенство x + A ≥ 90 должно быть верным для всех натуральных x, кратных 15.
Значит А ≥ 75
Для решения задания были применены "повышенные знания"

"Программное" решение несложное (аналогично тем, что выше)
!!! Главное - не забыть, что x - натуральное (исключить 0 из просмотра)

def f15(x,A): #программа проверки истинности для фиксированных x, A
  # вычисление и возврат значения логического выражения
  return ( (x % 3 == 0) <= ( x % 5 != 0 )) or ( (x + A) >= 90)
def g15(A) : # проверка истинности для "всех" x при фиксированном A
  for x in range (1, 100) : # здесь "все" это 100 (чтобы невыбирать между 90 и 91 :))) 
    if f15(x,A) == False : # есть исключение - значит не "для всех"
      return False
  return True
# основной блок - перебор A (можно разными способами)
A=0 # начальное значение 
while g15(A) == False : # поиск до первого успеха
  A+=1 # переход к следующему значению
print (A) # вывод результата

Рассмотрим еще одно задание 15 типа Д
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Сложность в том, что нет явной подсказки относительно диапазонов проверки по x и A (возможно, кроме догадки 6*4=24)
Формула составлена по шаблону ¬K → ( L → ¬M ) = K \/ (¬L \/ ¬M) = K \/ ¬( L /\ M)
В нашем случае получаем ДЕЛ(x, А) \/ ¬(ДЕЛ(x, 6) /\ ДЕЛ(x, 4)) = ДЕЛ(x, А) \/ ¬ДЕЛ(x, НОК(6,4))ДЕЛ(x, А) \/ ¬ДЕЛ(x, 12)
Нетрудно видеть, что максимальное значение для A равно 12
Решение несложное, но можно допустить простую ошибку и, например, взять значение 24=6*4
"Программное" решение избавить нас от этого. Для переборов можно взять "широкие" диапазоны и получить небольшое значение А.

Подведем итог по заданию 15 типа Д (делители)

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

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

Решаем задание 15 типа Г (графики)
Для какого наименьшего целого неотрицательного числа A выражение
(x < A) \/ (y < A) \/ (x + 2y > 50)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Задание несложное:

условия хорошо кодируются
значения целые - значит легко перебираются
диапазоны по x и у легко определяютсся (нет смысла перебироть x>50 и у>25)
поиск наименьшего A трудностей не вызывает

"Ручное" (аналитическое) решение более трудоемкое, чем "программное" (строим график x+2y=50 и "двигаем" A),
хотя можно понять, что надо найти пересечение линий x=50-2y и x=y ( найдем x =50/3 и для ответа взять ... 16 или 17)
Просто пишем программу и получаем ответ

def f15(x,y,A): #программа проверки истинности для фиксированных x, y, A
  # вычисление и возврат значения логического выражения
  return ( x< A ) or ( y < A ) or ( ( x + 2 * y ) > 50 )
def g15(A) : # проверка истинности для "всех" x при фиксированном A
  for x in range (100) : # здесь "все" это 100 :)))
    for y in range (100) : # здесь "все" это 100 :)))
      if f15(x,y,A) == False : # есть исключение - значит не "для всех"
        return False
  return True
# основной блок - перебор A (можно разными способами)
A=0 # начальное значение 
while g15(A) == False : # поиск до первого успеха
  A+=1 # переход к следующему значению
print (A) # вывод результата

Подведем итог по заданию 15 типа Г (графики)

Легко понять диапазон проверяемых значений переменных
Наличие двух переменных (x, y) немного усложняет проверку (использование вложенного цикла)

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

Решаем задание 15 типа О (отрезки)
На числовой прямой даны три отрезка: P = [15; 37], Q = [41; 71] и R = [21; 53].
Укажите наименьшую возможную длину такого отрезка А, что формула
((x∉P)→(x∈Q))∧(x∈R)∧(x∉A)
тождественно ложна, то есть принимает значение 0 при любом значении переменной x?
Сложность "программного" решения задания в том, что не очень понятно как перебирать отрезки (два края) и
как проверять "любые значения пременной x" (то есть вещественные). Несложно найти такие способы,
но их трудоемкость и вероятность ошибиться (с границами) делают их не очень эффективными.
"Ручное" (аналитическое) решение в этом случае предпочтительнее (хотя и требует "повышенные знания")
Для этого надо превести формулу к виду с тремя операциями (отрицанием, конъюкцией и дизъюнкцией), но сначала
Шаблон формулы есть ( ¬P → Q) ∧ R ∧ ¬A = ¬A ∧ R ∧ ( P \/ Q) = ¬A ∧ (R ∧ P \/ R ∧ Q),
значит ¬A не должно иметь общих точек с (R ∧ P \/ R ∧ Q), то есть (R ∧ P \/ R ∧ Q) должно быть внутри отрезка A
(R ∧ P \/ R ∧ Q) = [21;37] U [41;53], откуда получаем А =[21; 53] и ответ 32
(полезно нарисовать схему - решение аналогичное "методу интервалов" в математике)

Общие итоги задания типа 15

Сложность - в лимите времени, наличие нескольких типов заданий (которые могут комбинироваться)
Простота - в однотипности "программного" решения, наличие лимита времени на задание не позволит
составителям создавать задания со сложной проверкой
При разборе заданий рекомендуется преобразовывать/упрощать начальный вид формулы - это упростит
понимание этого задания и задания типа 2 (на таблицы истинности)

Задание ДОЛЖНО решаться за три минуты (максимум за пять)

time 1000 ms
memory 256 Mb

Комментарий учителя

Обсуждения (0)

Чтобы оставить комментарий нужна авторизация

Решения (0)

Решения:

Нет доступных решений