Логика и упрощения

Преобразования логических выражений даются в школьном курсе информатики далеко не всегда, а между тем, в ЕГЭ они очень даже нужны для некоторых «продвинутых» задач. Давайте посмотрим один из таких примеров.

Даны отрезки \(P=[5,13]\) и \(Q=[8,19]\). При какой наибольшей возможной длине отрезка \(A\) формула \(\neg((x\in P)\to\neg(x\in Q))\lor\neg(x\in A)\) тождественно верна при любом значении \(x\)?

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

\[
(u\to w)\equiv (\bar{u}\lor w).
\]

Во-вторых, это законы отрицания, известные также как законы де Моргана:

\[
\overline{u\lor w}\equiv (\bar{u}\land\bar{w});\qquad \overline{u\land w}\equiv (\bar{u}\lor\bar{w}).
\]

И в-третьих, это закон двойного отрицания \(\bar{\bar{u}}\equiv u\).

Введём для удобства новые переменные: \(u=(x\in P)\) и \(w=(x\in Q)\). В них левая часть предлагаемой формулы примет вид \(\overline{u\to\bar{w}}\). Преобразуем её согласно названным правилам:

\[
\overline{u\to\bar{w}} = \overline{\bar{u}\lor\bar{w}} = u\land w.
\]

Но если \((x\in P)\land(x\in Q)\), то это означает, что \(x\in P\cap Q\), то есть \(x\in[8,13]\). Тогда предлагаемая в условии формула эквивалентна гораздо более простой

\[
(x\in[8,13])\lor(x\notin A).
\]

Она будет тождественной истиной, если \(A\subset[8,13]\) и, таким образом, максимально возможная длина отрезка \(A\) равна пяти.