Тождественная истинность
Параметр A в неравенствах находят по худшему значению переменных: по точке, где выполнить условие с A труднее всего. Сначала выделяют область, где ложны условия без A, затем ищут на ней наибольшее или наименьшее значение выражения. Для поразрядной конъюнкции рассуждают по отдельным битам, а программа перебирает A и все значения x и y.
Параметр в неравенстве
Выражение тождественно истинно, если оно равно 1 при любых значениях переменных. Тождественно ложно — если его отрицание тождественно истинно.
- Приведите выражение к дизъюнкции: , .
- Найдите область : значения переменных, при которых ложны все условия без .
- Найдите на худшую точку — ту, где условие с выполнить труднее всего. Из неё получите границу для .
- Для целых чисел строгое неравенство сдвигает границу на 1: из следует .
- — у нет единиц в тех разрядах, где они есть у .
- Программа перебирает и проверяет выражение при всех и из диапазона, который накрывает .
Худшее значение переменной
Пусть выражение — дизъюнкция условия с и условий без . Условие с должно быть истинно при всех значениях из области , где ложны остальные условия. Достаточно проверить худшее значение — точку , где условие с выполнить труднее всего. Если условие выполнено там, оно выполнено во всей области.
Для условия худшая точка — та, где наибольшее, и тогда больше этого наибольшего значения. Для условия худшая точка — та, где наименьшее. Следите за тем, какие значения переменных разрешены: «целые неотрицательные» начинаются с 0, «целые положительные» и «натуральные» — с 1.
Пример
Для какого наименьшего целого выражение тождественно истинно при любом целом неотрицательном ?
- 1.Условие ложно при . Это область .
- 2. наибольшее при : . Нужно .
- 3.Наименьшее целое , которое больше 57, — это 58.
Ответ:
Две переменные и произведение x · y
Выражение тождественно ложно, если его отрицание тождественно истинно. Область — пары, где и , то есть .
Произведение наибольшее при . Значит, нужно . Найдите наибольшее целое число, квадрат которого не больше , и прибавьте 1.
Пример задания
Открытый банк ФИПИ
Для какого наибольшего целого неотрицательного числа А выражение
тождественио ложно, т. е. принимает значение 0 при любых целых положительных x и y?
Линейное выражение на области
Если условий без несколько, область — фигура на плоскости : прямоугольник, треугольник или четверть круга. Линейное выражение с положительными и растёт вправо и вверх, поэтому его наибольшее значение — в дальнем углу области. Для условия вида нужна граница : ищите наименьшее значение , то есть самое маленькое и самое большое .
Если граница области — окружность , переберите целые точки около окружности и выберите лучшую. Например, при сумма наибольшая в точке : .
Пример
Для какого наименьшего целого выражение тождественно истинно при любых целых неотрицательных и ?
- 1.Условия без ложны, если и . Область — треугольник с вершинами , , .
- 2. наибольшее в углу : .
- 3.Нужно , наименьшее целое .
Ответ:
Программа: перебор A и пар (x, y)
Если входит в два условия или область сложная, проще перебрать. Внешний цикл идёт по , а all(...) с двумя for проверяет выражение для всех пар и . Знаки <, >= и логические and, or, not пишут так же, как в условии.
Диапазон переменных должен накрывать область с запасом: вне неё условия без истинны, и проверка там ничего не меняет. Если сказано «целое », перебор начинают с отрицательных чисел: range(-100, 100). Если ответ совпал с границей перебора, расширьте её.
Пример
Для какого наименьшего целого выражение тождественно истинно при любых целых неотрицательных и ?
- 1.Вручную: в области , выражение ложно, если . Этот промежуток шире всего при : .
- 2.При подходит , выражение ложно. При промежуток не содержит целых чисел.
- 3.Программа перебирает от , печатает первое подходящее значение и останавливается: 4.
Ответ:
Предикат из условия: ТРЕУГ и МАКС
Иногда условие задаёт свой предикат. ТРЕУГ(n, m, k) — «существует невырожденный треугольник со сторонами , , ». Он истинен, если каждая сторона меньше суммы двух других. Для сторон , , при это . МАКС(a, b) — большее из двух чисел, равно .
Вручную разбейте ось на участки по границам всех предикатов и найдите на каждом значение частей без . В программе предикат — функция: treug сортирует стороны и сравнивает сумму двух меньших с большей, МАКС — встроенная max.
Пример
Для какого наибольшего натурального выражение тождественно истинно при натуральных ?
- 1. истинно при , то есть при . Вторая часть эквивалентности истинна при .
- 2.Эквивалентность истинна при и при . При этих должно быть ложно .
- 3. истинно при : это три числа , , . Они должны лежать среди 1, 2, 3, 4 или 11, 12, 13. Наибольшее .
- 4.Программа печатает 12.
Ответ:
Поразрядная конъюнкция: рассуждение по битам
— поразрядная конъюнкция: , если у нули во всех разрядах, где у единица, и , если хотя бы в одном таком разряде у единица: конъюнкция с маской.
Запишите числа из условия в двоичной системе и найдите как набор требований к битам . Если в есть числа, у которых ровно одна единица, условие требует, чтобы у была единица в этом разряде. Наименьшее — сумма всех обязательных степеней двойки.
Пример
Для какого наименьшего неотрицательного целого выражение тождественно истинно при любом неотрицательном целом ?
- 1., . Первые две части ложны, если у нули в разрядах 1 и 2 и единица в разряде 0 или 3.
- 2.В есть и . Значит, у единицы в разрядах 0 и 3: .
- 3.При каждое из имеет общую единицу с .
Ответ:
Программа для поразрядной конъюнкции
В Python поразрядная конъюнкция — знак &. Он выполняется раньше сравнения, поэтому x & 52 != 0 значит (x & 52) != 0. Скобки всё равно делают запись понятнее.
Если числа в условии меньше 64, они занимают разряды от 0 до 5. Старшие разряды тогда не влияют на ответ, поэтому достаточно проверить x в range(0, 1024). перебирают от 0 и печатают первое подходящее значение.
Пример задания
Открытый банк ФИПИ
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А логическое выражение
((x & 52 ≠ 0) ∧ (x & 48 = 0)) → ¬(x & A = 0)
истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?