Тождественная истинность
В задании 15 ищут параметр A, при котором выражение с переменной x истинно при любом x. Выражение приводят к дизъюнкции, находят все x, где ложна часть без A, и подбирают A так, чтобы при этих x была истинна часть с A. Для делимости ответ даёт НОК или НОД, для отрезков — крайние точки множества, а программа перебирает A и проверяет все x.
Как найти параметр A
Выражение тождественно истинно, если оно равно 1 при любом значении переменной . Параметр подбирают так, чтобы это выполнялось.
- Замените импликацию: . Выражение станет дизъюнкцией: часть с или остальная часть.
- Найдите множество : все , при которых остальная часть ложна. При каждом из часть с должна быть истинна.
- истинно при всех кратных числа , только если — делитель . Наибольшее такое .
- Отрезок должен накрыть всё множество . Наименьшая длина — от левой точки до правой.
- Программа перебирает и для каждого проверяет выражение при всех из достаточно широкого диапазона.
Тождественная истинность и множество проверки
Тождественно истинное выражение равно 1 при любом значении переменной. Тождественно ложное выражение равно 0 при любом значении, то есть его отрицание тождественно истинно. Чтобы опровергнуть тождественную истинность, достаточно одного , при котором выражение ложно.
Дизъюнкция ложна, только если ложны обе части. Поэтому тождественно истинна, если истинно при всех , где ложно. Эти — множество проверки . В задании 15 часть содержит параметр , а от не зависит. Значения операций — в таблицах истинности операций.
Пример
означает « делится на без остатка». Тождественно ли истинны выражения и при натуральных ?
- 1.Первое выражение: ложно при , кратных 4. Это множество .
- 2.Каждое число, кратное 4, чётное, поэтому при всех из верно . Первое выражение тождественно истинно.
- 3.Второе выражение: — чётные . При часть ложна, и всё выражение ложно.
Ответ: первое — да, второе — нет
Замена импликации и отрицания
Импликацию заменяют дизъюнкцией (импликация через ИЛИ), отрицание скобки раскрывают по законам де Моргана, двойное отрицание снимают. Вложенная импликация даёт три части: .
После замены выражение — дизъюнкция простых условий, и множество видно сразу: это , при которых ложны все условия без .
Пример
Запишите выражение в виде дизъюнкции.
- 1.Внешняя импликация: , двойное отрицание снимаем.
- 2.Внутренняя импликация: .
Ответ:
Делимость: наибольшее A равно НОК
ДЕЛ(n, m) — утверждение «натуральное число делится без остатка на натуральное число ». Условие ложно, если делится и на , и на , то есть кратно их наименьшему общему кратному . Значит, — все кратные .
должно быть истинно при . Это так, только если — делитель . Наибольший делитель — само . НОК находят через разложение на простые множители: каждый множитель берут в наибольшей степени. , только если у и нет общих простых множителей. У 26 и 169 общий множитель 13: , , поэтому , а не . В Python НОК даёт math.lcm(m, k).
Пример
Для какого наибольшего натурального выражение тождественно истинно при натуральных ?
- 1.Выражение равно : замена импликации.
- 2.Часть без ложна, если кратно 6 и 10. , , .
- 3. должно делить 30. Наибольшее .
Ответ:
Делимость и неравенство: наименьшее A
В выражении вида параметр стоит в неравенстве. Первая скобка ложна при , кратных . При всех этих должно быть .
Труднее всего выполнить неравенство при самом маленьком из , то есть при . Отсюда , и наименьшее . Если , подходит любое натуральное .
Пример
Для какого наименьшего натурального выражение тождественно истинно при натуральных ?
- 1.Первая скобка ложна, если кратно 4 и 6, то есть кратно .
- 2.Самое маленькое такое . Нужно , то есть .
- 3.При и сумма тем более не меньше 50.
Ответ:
Условие ДЕЛ(c, x): x — делитель числа
Если переменная стоит вторым аргументом, , то условие говорит « — делитель числа ». Таких конечное число. Вместе с множество — делители , которые кратны . Выпишите их все.
должно быть истинно при каждом из , поэтому — общий делитель всех чисел . Наибольшее — их наибольший общий делитель (НОД). В Python НОД даёт math.gcd(a, b).
Пример задания
Открытый банк ФИПИ
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Программа: перебор A и x
Функция d(n, m) возвращает n % m == 0. Импликацию пишут как not P or Q, эквивалентность — как P == Q. Функция all(...) проверяет условие при всех из range. Для наибольшего запоминают последнее подходящее значение, для наименьшего — печатают первое и останавливают цикл через break.
Диапазон берут с запасом, чтобы в нём было несколько чисел из : range(1, 1000). Натуральные начинаются с 1, а при условие 162 % x остановит программу ошибкой деления на ноль. Если ответ совпал с границей перебора , расширьте диапазон и запустите снова.
Пример
Пусть . Для какого наибольшего натурального выражение истинно при любом натуральном ?
- 1.Вручную: вторая часть ложна, если лежит в и кратно 22. Такое одно: 88. должно делить 88, наибольшее .
- 2.Программа: записываем как
not (70 <= x <= 90) or not d(x, 22). - 3.Цикл по запоминает последнее , при котором выражение истинно для всех . Программа печатает 88.
Ответ:
Отрезки: логические операции и множества
Высказывание истинно, если точка лежит на отрезке . Отрезок включает концы, его длина равна . Логическим операциям отвечают операции над множествами: — пересечение, — объединение, — дополнение (все точки прямой вне отрезка).
Чтобы найти, где истинно условие из нескольких отрезков, отметьте их концы на числовой прямой. Концы делят прямую на участки, и на каждом участке значение условия одинаковое. Проверьте по одной точке на каждом участке и отдельно сами концы.
Пример
, . При каких истинно ?
- 1.Условие — пересечение с дополнением : точки , которые не лежат в .
- 2. начинается в точке 20 и включает её, поэтому точка 20 не подходит.
- 3.Остаются точки от 10 до 20, без самой точки 20.
Ответ:
Наименьшая длина отрезка A
Приведите выражение к виду . Множество — точки, где ложно. Отрезок должен содержать все точки . Отрезок — один сплошной кусок, поэтому он накрывает и промежутки между частями . Наименьшая длина равна расстоянию от самой левой точки до самой правой.
Если у открытый конец, например , длину считают до этого конца: и длина 12. Если сказано, что выражение тождественно ложно, сначала возьмите его отрицание: оно тождественно истинно.
Пример
, . Укажите наименьшую длину отрезка , для которого выражение ложно при любом .
- 1.Отрицание выражения тождественно истинно: .
- 2.Заменяем импликацию: . Вторая часть ложна на .
- 3. накрывает и , значит . Длина .
Ответ:
Программа для отрезков
Принадлежность отрезку пишут двойным сравнением: 10 <= x <= 40. Концы и отрезка перебирают двумя вложенными циклами и для каждой пары проверяют выражение во всех точках. Среди подходящих пар берут наименьшую длину b - a.
Точка на прямой не обязательно целая. Если проверять только целые , программа не увидит открытый конец множества и даст длину на 1 меньше. Поэтому проверяют точки с шагом 0,5: x = k / 2.
Пример
, . Укажите наименьшую длину отрезка , для которого выражение истинно при любом .
- 1.Вручную: выражение равно . — точки вне , то есть . Длина равна .
- 2.Программа: функция
fвычисляет выражение в точкеxдля отрезка . - 3.Проверка с шагом 0,5 находит точку 24,5 в , поэтому правый конец не меньше 25. Программа печатает 15.
Ответ:
Эквивалентность: точки, где отрезки различаются
истинно, если лежит в обоих отрезках или ни в одном. Оно ложно, если лежит ровно в одном отрезке. Поэтому в выражении , то есть , множество — точки вне и точки вне .
Для пересекающихся отрезков состоит из двух кусков по краям, а общая часть и в него не входит. Отрезок всё равно накрывает целиком: от самого левого конца и до самого правого.
Пример задания
Открытый банк ФИПИ
На числовой прямой даны два отрезка: и Укажите наименьшую возможную длину такого отрезка А, для которого логическое выражение
истинно (т. е. принимает значение 1) при любом значении переменной х.