Математическая логика

Простыми словами

Правило «если идёт дождь, я беру зонт» нарушается только в одном случае: дождь идёт, а зонта нет. Задание 15 — подобрать такой параметр $A$, чтобы формула ни при одном $x$ не оказалась нарушенной.

Задачи с отрезками

$P=[6;17]$, $Q=[28;41]$. Наибольшая длина отрезка $A$, при которой $((x\in A)\to (x\in P))\vee (x\in Q)$ тождественно истинна?

1. Формула ложна, когда $x\in A$, $x\notin P$ и $x\notin Q$.
2. Чтобы такого $x$ не было, всё, что попало в $A$, должно лежать в $P$ или в $Q$: $A\subseteq P\cup Q$.
3. $P$ и $Q$ не пересекаются, а $A$ — один отрезок, поэтому он целиком внутри $P$ (длина $17-6=11$) или внутри $Q$ (длина $41-28=13$). Ответ: 13.

Задачи с делимостью (ДЕЛ)

ДЕЛ$(n,m)$ — «$n$ делится на $m$ без остатка». Наименьшее $A$, при котором ДЕЛ$(x,A)\to ($ДЕЛ$(x,30)\vee$ ДЕЛ$(x,14))$ тождественно истинна?

1. Ложна, когда $x$ кратно $A$, но не кратно ни 30, ни 14.
2. Возьмём $x=A$: тогда $A$ само обязано делиться на 30 или на 14.
3. Наименьшее такое $A$ — 14. Проверка: любое кратное 14 делится на 14 ✓

Поразрядная конъюнкция

$x\&A$ — поразрядное «И» двоичных записей. $x\&A\ne 0$ — «у $x$ есть хотя бы один общий единичный бит с $A$».

def F(x, A):
    return (not (x & 29 != 0)) or (x & 12 != 0) or (x & A != 0)

for A in range(1, 1000):
    if all(F(x, A) for x in range(1, 1024)):
        print(A)   # 17
        break