Задание 15
тема 2 из 7

Тождественная истинность

В задании 15 ищут параметр A, при котором выражение с переменной x истинно при любом x. Выражение приводят к дизъюнкции, находят все x, где ложна часть без A, и подбирают A так, чтобы при этих x была истинна часть с A. Для делимости ответ даёт НОК или НОД, для отрезков — крайние точки множества, а программа перебирает A и проверяет все x.

Главная тема в задании15На карте навыков

Как найти параметр A

Выражение тождественно истинно, если оно равно 1 при любом значении переменной xx. Параметр AA подбирают так, чтобы это выполнялось.

  • Замените импликацию: P→Q=¬P∨QP \to Q = \neg P \lor Q. Выражение станет дизъюнкцией: часть с AA или остальная часть.
  • Найдите множество MM: все xx, при которых остальная часть ложна. При каждом xx из MM часть с AA должна быть истинна.
  • ДЕЛ(x,A)\text{ДЕЛ}(x, A) истинно при всех кратных числа LL, только если AA — делитель LL. Наибольшее такое A=LA = L.
  • Отрезок AA должен накрыть всё множество MM. Наименьшая длина — от левой точки MM до правой.
  • Программа перебирает AA и для каждого AA проверяет выражение при всех xx из достаточно широкого диапазона.

Тождественная истинность и множество проверки

Тождественно истинное выражение равно 1 при любом значении переменной. Тождественно ложное выражение равно 0 при любом значении, то есть его отрицание тождественно истинно. Чтобы опровергнуть тождественную истинность, достаточно одного xx, при котором выражение ложно.

Дизъюнкция P∨QP \lor Q ложна, только если ложны обе части. Поэтому P∨QP \lor Q тождественно истинна, если PP истинно при всех xx, где QQ ложно. Эти xx — множество проверки MM. В задании 15 часть PP содержит параметр AA, а QQ от AA не зависит. Значения операций — в таблицах истинности операций.

Пример

ДЕЛ(x,m)\text{ДЕЛ}(x, m) означает «xx делится на mm без остатка». Тождественно ли истинны выражения ДЕЛ(x,2)∨¬ДЕЛ(x,4)\text{ДЕЛ}(x, 2) \lor \neg \text{ДЕЛ}(x, 4) и ДЕЛ(x,4)∨¬ДЕЛ(x,2)\text{ДЕЛ}(x, 4) \lor \neg \text{ДЕЛ}(x, 2) при натуральных xx?

  1. 1.Первое выражение: ¬ДЕЛ(x,4)\neg \text{ДЕЛ}(x, 4) ложно при xx, кратных 4. Это множество MM.
  2. 2.Каждое число, кратное 4, чётное, поэтому при всех xx из MM верно ДЕЛ(x,2)\text{ДЕЛ}(x, 2). Первое выражение тождественно истинно.
  3. 3.Второе выражение: MM — чётные xx. При x=2x = 2 часть ДЕЛ(2,4)\text{ДЕЛ}(2, 4) ложна, и всё выражение ложно.

Ответ: первое — да, второе — нет

Замена импликации и отрицания

Импликацию заменяют дизъюнкцией P→Q=¬P∨QP \to Q = \neg P \lor Q (импликация через ИЛИ), отрицание скобки раскрывают по законам де Моргана, двойное отрицание ¬¬P=P\neg \neg P = P снимают. Вложенная импликация даёт три части: P→(Q→R)=¬P∨¬Q∨RP \to (Q \to R) = \neg P \lor \neg Q \lor R.

После замены выражение — дизъюнкция простых условий, и множество MM видно сразу: это xx, при которых ложны все условия без AA.

Пример

Запишите выражение ¬ДЕЛ(x,A)→(ДЕЛ(x,6)→¬ДЕЛ(x,10))\neg \text{ДЕЛ}(x, A) \to (\text{ДЕЛ}(x, 6) \to \neg \text{ДЕЛ}(x, 10)) в виде дизъюнкции.

  1. 1.Внешняя импликация: ¬¬ДЕЛ(x,A)∨(ДЕЛ(x,6)→¬ДЕЛ(x,10))\neg \neg \text{ДЕЛ}(x, A) \lor (\text{ДЕЛ}(x, 6) \to \neg \text{ДЕЛ}(x, 10)), двойное отрицание снимаем.
  2. 2.Внутренняя импликация: ¬ДЕЛ(x,6)∨¬ДЕЛ(x,10)\neg \text{ДЕЛ}(x, 6) \lor \neg \text{ДЕЛ}(x, 10).

Ответ: ДЕЛ(x,A)∨¬ДЕЛ(x,6)∨¬ДЕЛ(x,10)\text{ДЕЛ}(x, A) \lor \neg \text{ДЕЛ}(x, 6) \lor \neg \text{ДЕЛ}(x, 10)

Делимость: наибольшее A равно НОК

ДЕЛ(n, m) — утверждение «натуральное число nn делится без остатка на натуральное число mm». Условие ¬ДЕЛ(x,m)∨¬ДЕЛ(x,k)\neg \text{ДЕЛ}(x, m) \lor \neg \text{ДЕЛ}(x, k) ложно, если xx делится и на mm, и на kk, то есть кратно их наименьшему общему кратному L=НОК(m,k)L = \text{НОК}(m, k). Значит, MM — все кратные LL.

ДЕЛ(x,A)\text{ДЕЛ}(x, A) должно быть истинно при x=L,2L,3L,…x = L, 2L, 3L, \ldots. Это так, только если AA — делитель LL. Наибольший делитель — само LL. НОК находят через разложение на простые множители: каждый множитель берут в наибольшей степени. НОК(m,k)=m⋅k\text{НОК}(m, k) = m \cdot k, только если у mm и kk нет общих простых множителей. У 26 и 169 общий множитель 13: 26=2⋅1326 = 2 \cdot 13, 169=132169 = 13^2, поэтому НОК(26,169)=2⋅132=338\text{НОК}(26, 169) = 2 \cdot 13^2 = 338, а не 26⋅16926 \cdot 169. В Python НОК даёт math.lcm(m, k).

Пример

Для какого наибольшего натурального AA выражение ¬ДЕЛ(x,A)→(ДЕЛ(x,6)→¬ДЕЛ(x,10))\neg \text{ДЕЛ}(x, A) \to (\text{ДЕЛ}(x, 6) \to \neg \text{ДЕЛ}(x, 10)) тождественно истинно при натуральных xx?

  1. 1.Выражение равно ДЕЛ(x,A)∨¬ДЕЛ(x,6)∨¬ДЕЛ(x,10)\text{ДЕЛ}(x, A) \lor \neg \text{ДЕЛ}(x, 6) \lor \neg \text{ДЕЛ}(x, 10): замена импликации.
  2. 2.Часть без AA ложна, если xx кратно 6 и 10. 6=2⋅36 = 2 \cdot 3, 10=2⋅510 = 2 \cdot 5, НОК(6,10)=2⋅3⋅5=30\text{НОК}(6, 10) = 2 \cdot 3 \cdot 5 = 30.
  3. 3.AA должно делить 30. Наибольшее A=30A = 30.

Ответ: 3030

Делимость и неравенство: наименьшее A

В выражении вида (ДЕЛ(x,m)→¬ДЕЛ(x,k))∨(x+A≥N)(\text{ДЕЛ}(x, m) \to \neg \text{ДЕЛ}(x, k)) \lor (x + A \geq N) параметр стоит в неравенстве. Первая скобка ложна при xx, кратных L=НОК(m,k)L = \text{НОК}(m, k). При всех этих xx должно быть x+A≥Nx + A \geq N.

Труднее всего выполнить неравенство при самом маленьком xx из MM, то есть при x=Lx = L. Отсюда A≥N−LA \geq N - L, и наименьшее A=N−LA = N - L. Если L≥NL \geq N, подходит любое натуральное AA.

Пример

Для какого наименьшего натурального AA выражение (ДЕЛ(x,4)→¬ДЕЛ(x,6))∨(x+A≥50)(\text{ДЕЛ}(x, 4) \to \neg \text{ДЕЛ}(x, 6)) \lor (x + A \geq 50) тождественно истинно при натуральных xx?

  1. 1.Первая скобка ложна, если xx кратно 4 и 6, то есть кратно НОК(4,6)=12\text{НОК}(4, 6) = 12.
  2. 2.Самое маленькое такое x=12x = 12. Нужно 12+A≥5012 + A \geq 50, то есть A≥38A \geq 38.
  3. 3.При A=38A = 38 и x=24,36,…x = 24, 36, \ldots сумма тем более не меньше 50.

Ответ: 3838

Условие ДЕЛ(c, x): x — делитель числа

Если переменная стоит вторым аргументом, ДЕЛ(c,x)\text{ДЕЛ}(c, x), то условие говорит «xx — делитель числа cc». Таких xx конечное число. Вместе с ДЕЛ(x,m)\text{ДЕЛ}(x, m) множество MM — делители cc, которые кратны mm. Выпишите их все.

ДЕЛ(x,A)\text{ДЕЛ}(x, A) должно быть истинно при каждом xx из MM, поэтому AA — общий делитель всех чисел MM. Наибольшее AA — их наибольший общий делитель (НОД). В Python НОД даёт math.gcd(a, b).

Пример задания

Открытый банк ФИПИ

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула
¬ДЕЛ(x,А)→(ДЕЛ(x,54)→¬ДЕЛ(162,x))\neg ДЕЛ ( x , А ) \rightarrow ( ДЕЛ ( x , 54 ) \rightarrow \neg ДЕЛ ( 162 , x ) )
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Программа: перебор A и x

Функция d(n, m) возвращает n % m == 0. Импликацию P→QP \to Q пишут как not P or Q, эквивалентность — как P == Q. Функция all(...) проверяет условие при всех xx из range. Для наибольшего AA запоминают последнее подходящее значение, для наименьшего — печатают первое и останавливают цикл через break.

Диапазон xx берут с запасом, чтобы в нём было несколько чисел из MM: range(1, 1000). Натуральные xx начинаются с 1, а при x=0x = 0 условие 162 % x остановит программу ошибкой деления на ноль. Если ответ совпал с границей перебора AA, расширьте диапазон и запустите снова.

Пример

Пусть B=[70;90]B = [70; 90]. Для какого наибольшего натурального AA выражение ДЕЛ(x,A)∨((x∈B)→¬ДЕЛ(x,22))\text{ДЕЛ}(x, A) \lor ((x \in B) \to \neg \text{ДЕЛ}(x, 22)) истинно при любом натуральном xx?

  1. 1.Вручную: вторая часть ложна, если xx лежит в BB и кратно 22. Такое xx одно: 88. AA должно делить 88, наибольшее A=88A = 88.
  2. 2.Программа: (x∈B)→¬ДЕЛ(x,22)(x \in B) \to \neg \text{ДЕЛ}(x, 22) записываем как not (70 <= x <= 90) or not d(x, 22).
  3. 3.Цикл по AA запоминает последнее AA, при котором выражение истинно для всех xx. Программа печатает 88.

Ответ: 8888

Отрезки: логические операции и множества

Высказывание x∈Bx \in B истинно, если точка xx лежит на отрезке BB. Отрезок [a;b][a; b] включает концы, его длина равна b−ab - a. Логическим операциям отвечают операции над множествами: ∧\land — пересечение, ∨\lor — объединение, ¬\neg — дополнение (все точки прямой вне отрезка).

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

Пример

B=[10;30]B = [10; 30], C=[20;40]C = [20; 40]. При каких xx истинно (x∈B)∧¬(x∈C)(x \in B) \land \neg (x \in C)?

  1. 1.Условие — пересечение BB с дополнением CC: точки BB, которые не лежат в CC.
  2. 2.CC начинается в точке 20 и включает её, поэтому точка 20 не подходит.
  3. 3.Остаются точки от 10 до 20, без самой точки 20.

Ответ: x∈[10;20)x \in [10; 20)

Наименьшая длина отрезка A

Приведите выражение к виду (x∈A)∨Q(x \in A) \lor Q. Множество MM — точки, где QQ ложно. Отрезок AA должен содержать все точки MM. Отрезок — один сплошной кусок, поэтому он накрывает и промежутки между частями MM. Наименьшая длина равна расстоянию от самой левой точки MM до самой правой.

Если у MM открытый конец, например M=[17;29)M = [17; 29), длину считают до этого конца: A=[17;29]A = [17; 29] и длина 12. Если сказано, что выражение тождественно ложно, сначала возьмите его отрицание: оно тождественно истинно.

Пример

B=[5;12]B = [5; 12], C=[18;30]C = [18; 30]. Укажите наименьшую длину отрезка AA, для которого выражение ¬(((x∈B)∨(x∈C))→(x∈A))\neg (((x \in B) \lor (x \in C)) \to (x \in A)) ложно при любом xx.

  1. 1.Отрицание выражения тождественно истинно: ((x∈B)∨(x∈C))→(x∈A)((x \in B) \lor (x \in C)) \to (x \in A).
  2. 2.Заменяем импликацию: (x∈A)∨¬((x∈B)∨(x∈C))(x \in A) \lor \neg ((x \in B) \lor (x \in C)). Вторая часть ложна на M=B∪CM = B \cup C.
  3. 3.AA накрывает [5;12][5; 12] и [18;30][18; 30], значит A=[5;30]A = [5; 30]. Длина 30−5=2530 - 5 = 25.

Ответ: 2525

Программа для отрезков

Принадлежность отрезку пишут двойным сравнением: 10 <= x <= 40. Концы aa и bb отрезка AA перебирают двумя вложенными циклами и для каждой пары проверяют выражение во всех точках. Среди подходящих пар берут наименьшую длину b - a.

Точка xx на прямой не обязательно целая. Если проверять только целые xx, программа не увидит открытый конец множества MM и даст длину на 1 меньше. Поэтому проверяют точки с шагом 0,5: x = k / 2.

Пример

D=[10;40]D = [10; 40], C=[25;60]C = [25; 60]. Укажите наименьшую длину отрезка AA, для которого выражение (x∈D)→((x∈C)∨(x∈A))(x \in D) \to ((x \in C) \lor (x \in A)) истинно при любом xx.

  1. 1.Вручную: выражение равно ¬(x∈D)∨(x∈C)∨(x∈A)\neg (x \in D) \lor (x \in C) \lor (x \in A). MM — точки DD вне CC, то есть [10;25)[10; 25). Длина AA равна 25−10=1525 - 10 = 15.
  2. 2.Программа: функция f вычисляет выражение в точке x для отрезка [a;b][a; b].
  3. 3.Проверка с шагом 0,5 находит точку 24,5 в MM, поэтому правый конец не меньше 25. Программа печатает 15.

Ответ: 1515

Эквивалентность: точки, где отрезки различаются

(x∈B)≡(x∈C)(x \in B) \equiv (x \in C) истинно, если xx лежит в обоих отрезках или ни в одном. Оно ложно, если xx лежит ровно в одном отрезке. Поэтому в выражении ¬(x∈A)→((x∈B)≡(x∈C))\neg (x \in A) \to ((x \in B) \equiv (x \in C)), то есть (x∈A)∨((x∈B)≡(x∈C))(x \in A) \lor ((x \in B) \equiv (x \in C)), множество MM — точки BB вне CC и точки CC вне BB.

Для пересекающихся отрезков MM состоит из двух кусков по краям, а общая часть BB и CC в него не входит. Отрезок AA всё равно накрывает MM целиком: от самого левого конца BB и CC до самого правого.

Пример задания

Открытый банк ФИПИ

На числовой прямой даны два отрезка: В=[4;18]В = [ 4 ; 18 \left]\right. и С=[12;40].С = [ 12 ; 40 \left]\right. . Укажите наименьшую возможную длину такого отрезка А, для которого логическое выражение
¬(x∈А)→((x∈В)≡(x∈С))\neg ( x \in А ) \rightarrow ( ( x \in В ) \equiv ( x \in С ) )
истинно (т. е. принимает значение 1) при любом значении переменной х.

Потренируйте навык

Все задания на этот навык

Решать