Логические выражения с параметром

Логическое выражение с переменными описывает утверждение, истинность которого зависит от подстановки. Параметр задаёт общее условие для всех этих подстановок: например, числовую границу или отрезок. Найти подходящий параметр означает установить, почему ни одна разрешённая подстановка не нарушает формулу.

Переменная, параметр и область значений

В выражении x<A обе буквы обозначают числа, но выполняют разные роли. Значение параметра A выбирается один раз. После этого переменная x может принимать любое значение из указанной области. Требование «для всех» нельзя заменить подбором своего параметра для каждого нового значения переменной.

Квантор всеобщности обозначается \forall. Если формула обозначена F(x,A), а область переменной — D, требование записывается так:

\forall x\in D\quad F(x,A)=1.

Число 1 здесь означает истину, 0 — ложь. При двух переменных проверяются все разрешённые пары, а не только пары с равными компонентами. Область важна: положительные целые начинаются с единицы, неотрицательные — с нуля; на вещественной прямой между соседними целыми есть другие точки.

Логические операции и их ложность

Пусть P и Q — утверждения. Отрицание \neg P читается «не P» и истинно ровно тогда, когда P ложно. Операции над двумя утверждениями связывают их следующим образом:

• Конъюнкция P\land Q читается «P и Q»: оба утверждения должны быть истинны.
• Дизъюнкция P\lor Q читается «P или Q»: достаточно хотя бы одного истинного утверждения, в том числе подходят два истинных.
• Импликация P\to Q читается «если P, то Q»: при истинном условии P следствие Q должно быть истинно.
• Эквивалентность P\equiv Q означает, что значения утверждений совпадают: оба истинны или оба ложны.

Таблицы показывают результат каждой операции при всех четырёх сочетаниях исходных значений:

Для поиска неподходящих значений полезно выделить случаи ложности. Конъюнкция ложна, если ложна хотя бы одна часть; дизъюнкция — только если ложны обе. Импликация ложна только при истинном условии и ложном следствии. Если условие ложно, импликация истинна: она не требует истинности самого условия. Эквивалентность ложна, когда значения двух утверждений различаются.

Условие ложности позволяет заменить импликацию другими операциями: (P\to Q)\equiv(\neg P\lor Q). Обе части ложны только при P=1,Q=0, а в остальных случаях истинны. Поэтому в Python импликацию можно записать как (not p) or q, где p и q хранят логические значения соответствующих утверждений. Такое равносильное преобразование сохраняет значение формулы при каждой подстановке.

Контрпример и доказательство границы

Универсальное утверждение опровергается одним разрешённым случаем, где оно ложно. Такой случай называется контрпримером. Напротив, несколько удачных проверок сами по себе не доказывают истинность для бесконечной области.

Для минимального параметра нужны два основания: найденное значение подходит для всей области, а меньшее уже не может подойти. Иногда достаточно проверить соседнее значение и объяснить монотонность. Например, в формуле (t<A)\lor P\lor Q, где t,P,Q не зависят от A, уменьшение A не может сделать ложную формулу истинной. Контрпример для соседнего меньшего значения тогда опровергает и все ещё меньшие. Без такого свойства проверка соседа не заменяет доказательства минимума.

Поиск ложности часто выделяет меньшую область. У дизъюнкции (t<A)\lor P\lor Q первая часть обязана работать только там, где P и Q ложны. Вне этой области истинность уже обеспечена. Если в ней существует наибольшее целое значение t=M, строгое условие требует A\ge M+1.

Утверждения о принадлежности и множества

Запись x\in P означает, что точка принадлежит множеству P. Связки между такими утверждениями описывают операции над множествами:

• (x\in P)\land(x\in Q) — общая часть, или пересечение P\cap Q.
• (x\in P)\lor(x\in Q) — объединение P\cup Q.
• (x\in P)\land\neg(x\in Q) — разность P\setminus Q.

Эквивалентность принадлежностей ложна там, где точка входит ровно в одно множество. Такая область называется симметрической разностью. Она может состоять из двух раздельных частей. Если обе должны войти в один отрезок, в него входит и весь промежуток между ними.

Отрезок [l;r] включает оба конца и все точки между ними; его длина r-l. Полуинтервал (l;r] не включает левый конец. Однако замкнутый отрезок, содержащий весь этот полуинтервал, не может начинаться правее l: между новым началом и l останутся потерянные точки.

Делимость как отношение между наборами чисел

Утверждение \text{ДЕЛ}(n,m) означает существование целого k, для которого n=mk; делитель m положителен. Общие положительные кратные двух чисел — кратные их наименьшего общего кратного, НОК. Поэтому требование «каждое общее кратное делится на A» равносильно требованию, чтобы на A делился сам НОК.

Необходимость получается подстановкой наименьшего общего кратного. Достаточность — умножением: если это число делится на A, делятся и все его кратные. Если же дан конечный непустой набор обязательных положительных чисел, наибольший общий делитель для них — НОД. Выбор между НОК и НОД определяется направлением делимости в формуле.

Разряды вместо логических значений чисел

Побитовая конъюнкция m\mathbin{\&}n сохраняет единицы в общих разрядах двоичных записей. Например, 14\mathbin{\&}5=1110_2\mathbin{\&}0101_2=0100_2=4. Результат операции — число; сравнение этого результата с нулём уже является логическим утверждением.

Число с выбранными единичными разрядами называют маской. Условие x\mathbin{\&}m=0 запрещает у x единицы в разрядах маски m. Старшие разряды вне маски не влияют на эту проверку. Это позволяет доказывать свойства всех чисел через конечный набор разрядов, но ограничения на неизвестную маску тоже необходимо обосновать.

Как по ложности формулы выделить все пары, определяющие минимальный параметр? Когда отрезок должен покрыть пересечение, а когда — две раздельные части? Законченные применения приведены в статье «Задание №15. Поиск параметра в логическом условии».