Отрезки и множества

Что делать, если A — не число, а отрезок на числовой прямой? Например:

«На числовой прямой даны отрезки P = [10; 40] и Q = [25; 55]. Укажите наименьшую возможную длину такого отрезка A, что формула (x ∈ P) → ((x ∈ Q) → (x ∈ A)) тождественно истинна — при любом x».

Вопрос тот же — при каких x всё решает A. Только теперь x — любое число на прямой, и ответ — участок прямой, который A обязан накрыть.

Для краткости пишут P вместо x ∈ P, так же Q и A. Заменим обе стрелки: P → (Q → A) = ¬P ∨ ¬Q ∨ A. Части без A ложны, когда x лежит и в P, и в Q — на их общей части [25; 40]. Там x обязан лежать в A.

Наименьший отрезок, который накрывает [25; 40], — он сам. Длина отрезка — разность его концов: 40 − 25 = 15. Ответ — 15.

А если A стоит слева от стрелки и спрашивают наибольшую длину? Пусть P = [5; 20], Q = [30; 50], а формула ((x ∈ A) → (x ∈ P)) ∨ (x ∈ Q) должна быть истинна при любом x.

Когда A стоит в формуле с отрицанием, в точках, где всё решает A, оно должно быть ложным: такие точки в A брать нельзя. Тогда ищут, где A разрешено быть.

Заменим стрелку: ¬A ∨ P ∨ Q. Части без A ложны, когда x не лежит ни в P, ни в Q. Там нужно ¬A = 1, то есть x не лежит в A. Значит, A может занимать только точки из P и Q.

Отрезок не может перепрыгнуть промежуток между P и Q — тогда он захватит запрещённые точки. Наибольший подходящий отрезок — Q = [30; 50] длины 20. Ответ — 20.

Что, если обязательных участков два и они не касаются? Пусть P = [3; 6], Q = [14; 19], и при любом x истинна формула ((x ∈ P) ∨ (x ∈ Q)) → (x ∈ A). Найдём наименьшую длину A.

Отрезок A — один кусок без дыр. Если он обязан накрыть две части, он накрывает и промежуток между ними.

Стрелка: ¬(P ∨ Q) ∨ A. Часть без A ложна, когда x лежит в P или в Q. Значит, A должен накрыть и [3; 6], и [14; 19].

Одним куском это отрезок от 3 до 19, его длина 19 − 3 = 16. Ответ — 16.

Иногда формула должна быть не истинной, а ложной при любом x. Например: P = [5; 22], найди наименьшую длину A, при которой формула (x ∈ P) ∧ ¬(x ∈ A) ложна при любом x.

Тогда ищут x, при которых формула могла бы стать истинной, и выбирают A так, чтобы этого не случилось.

P ∧ ¬A истинна, когда x лежит в P, но не лежит в A. Чтобы так не случилось ни при одном x, каждая точка P должна лежать в A. Наименьший A — сам P, его длина 22 − 5 = 17.

А если A, P и Q — не отрезки, а наборы чисел? Пусть P = {2, 4, 6, 8, 10, 12}, Q = {3, 6, 9, 12, 15, 18}, а A — набор натуральных чисел, при котором формула ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) тождественно истинна. Какая наименьшая сумма чисел A?

Метод тот же, но числа делят на группы: в P и в Q сразу, только в P, только в Q, ни в одном. Группы удобно видеть на двух кругах — их называют кругами Эйлера.

Стрелка: ¬(P ∧ Q) ∨ A. Часть без A ложна для чисел, которые есть и в P, и в Q, — это 6 и 12. Они обязаны быть в A, остальные можно не брать.

Для наименьшей суммы берём только обязательные числа: A = {6, 12}, сумма 18.

Если же A стоит слева — ((x ∈ A) → (x ∈ P)) ∨ (x ∈ Q) = ¬A ∨ P ∨ Q — то в A можно брать только числа из кругов. Тогда наибольшее количество чисел в A — все 10 чисел из P и Q.

• ЗаписьP вместо x ∈ P
• A справа от стрелкиточки, обязательные для A, — наименьший A
• A с отрицаниемточки, разрешённые для A, — наибольший A
• Две частиA накрывает и промежуток
• Длинаправый конец минус левый
• Ложна при любом xне дать ей стать истинной
• Множествагруппы чисел по кругам Эйлера