Что проверяет задание

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

Определения

Тождественная истинность, выражение истинно при всех допустимых значениях переменных. На языке логики: ∀x F(x, A) истинно.

Импликация P → Q ложна только когда P истинно, а Q ложно. Поэтому требование «импликация всегда истинна» равносильно: нет такого x, для которого P истинно и Q ложно.

Квантор всеобщности ∀x, «для каждого x». Квантор существования ∃x, «существует хотя бы один x».

Отрезок / промежуток на прямой, множество чисел между двумя границами. Для целых x это набор целых точек, для действительных, континуум; на экзамене часто достаточно мыслить отрезками на прямой.

Пересечение отрезков, числа, принадлежащие обоим. Объединение, числа, принадлежащие хотя бы одному.

Делимость как предикат, высказывание вида «x делится на k». Для параметра A это даёт арифметические ограничения, а не геометрию отрезков.

Минимальное A, среди всех A, делающих высказывание тождественно истинным, выбирают наименьшее. Аналогично для максимального. Иногда A, длина отрезка, сумма границ или само множество.

Логика отрезков

Высказывание «x ∈ A → x ∈ B» означает A ⊆ B: каждый элемент A лежит в B.

Высказывание «x ∈ A → (x ∈ B ∨ x ∈ C)» означает A ⊆ B ∪ C.

Двойственная форма с конъюнкцией в посылке описывает вложение пересечения.

Если x пробегает целые, достаточно проверить целые точки, но длина отрезка и число точек, разные величины.

Общий алгоритм решения

1. Переписать условие как «выражение истинно для всех x (и y)».
2. Раскрыть импликации: запретить единственный ложный случай.
3. Перевести предикаты на язык отрезков, делимости или числовых неравенств.
4. Получить условие на параметр A.
5. Среди всех A, удовлетворяющих условию, выбрать требуемый экстремум или сумму.
6. Проверить граничные точки: входят ли концы отрезков, выполняется ли равенство в делимости.

Программа построчно

В задании 15 формула должна быть тождественно истинной - верной при любых x (и y). Нужно подобрать число A. Программа делает это перебором: для каждого кандидата A проверяет формулу на множестве значений x и берёт первое A, при котором ложных случаев нет.

Разберём программу на условии:

Для какого наименьшего неотрицательного целого числа A формула ((x & 52 ≠ 0) ∧ (x & 48 = 0)) → ¬(x & A = 0) тождественно истинна при любом неотрицательном x?

def f(x, A):
    return ((x & 52 != 0) and (x & 48 == 0)) <= (not (x & A == 0))

for A in range(256):
    if all(f(x, A) for x in range(256)):
        print(A)
        break

def f(x, A): - записываем формулу как функцию: при данных x и A она возвращает True (истина) или False (ложь). Подробно - в разделе «Формула как функция».

return ((x & 52 != 0) and (x & 48 == 0)) <= (not (x & A == 0)) - сама формула, переписанная знаками Python: ∧ - and, ¬ - not, импликация → - знак <=. Подробно - в разделе «Логические операции в Python».

for A in range(256): - перебираем кандидатов A по возрастанию: 0, 1, 2, … Подробно - в разделе «Перебор A».

if all(f(x, A) for x in range(256)): - проверяем, что формула верна для всех x от 0 до 255. Подробно - в разделе «Проверка «при любом x»: all».

print(A) / break - первое подходящее A наименьшее: печатаем и останавливаемся.

Логические операции в Python

Каждый логический знак формулы заменяется так:

• ∧ (И, конъюнкция) → and;
• ∨ (ИЛИ, дизъюнкция) → or;
• ¬ (НЕ, отрицание) → not;
• → (импликация) → <=;
• ≡ (эквивалентность) → ==.

Почему импликация - это <=. Импликация a → b ложна только в одном случае: a истинно, а b ложно. В Python True - это 1, False - 0. Сравнение a <= b ложно только при a = 1 и b = 0 (1 ≤ 0 неверно), во всех остальных случаях верно. Таблица истинности совпадает с импликацией.

Скобки обязательны. Знак <= в Python «сильнее» not, and и or: запись not a <= b понимается как not (a <= b). Поэтому каждую часть импликации берут в скобки: (not a) <= (b). Скобки из условия переносят как есть.

Знаки внутри утверждений:

• ≤ → <=, ≥ → >=, ≠ → !=, = → == (одиночное = в Python - присваивание);
• умножение пишется явно: 3x → 3 * x, x² → x * x;
• & - поразрядная конъюнкция, пишется так же: x & 52.

Формула как функция

def f(x, A):
    return (x & 52 != 0) <= (x & A != 0)

• def f(x, A): - функция с двумя аргументами: значение переменной x и проверяемое число A. Если в формуле есть y, аргументов три: def f(x, y, A):;
• return … - функция возвращает значение формулы: True или False;
• функцию можно вызывать для любых x и A: f(5, 12) - верна ли формула при x = 5 и A = 12.

Перебор A

• наименьшее A - перебираем снизу вверх и останавливаемся на первом подходящем:

for A in range(0, 1000):
    if проверка:
        print(A)
        break

• наибольшее A - сверху вниз: for A in range(1000, -1, -1): (третий аргумент -1 - шаг вниз). Первое подходящее - наибольшее;
• «сколько существует значений A» - проходим все кандидаты и считаем подходящие счётчиком count += 1, без break.

Границу перебора берут с запасом: больше всех чисел формулы. Если программа печатает самую границу диапазона (например, 1000 при поиске наибольшего), значит, граница мала - её увеличивают.

Проверка «при любом x»: all

all(f(x, A) for x in range(256))

all(…) возвращает True, только если все значения внутри истинны. Запись в скобках - короткий цикл: «для каждого x от 0 до 255 вычислить f(x, A)». Как только встречается ложное значение, all сразу останавливается и возвращает False.

Это то же самое, что цикл с флажком:

ok = True
for x in range(256):
    if not f(x, A):
        ok = False
        break

Для двух переменных перебирают все пары: all(f(x, y, A) for x in range(100) for y in range(100)).

Сколько x проверять:

• для поразрядных операций - до ближайшей степени двойки, большей всех чисел формулы: если числа меньше 256, хватает range(256) - старшие биты x на результат не влияют;
• для ДЕЛ - с запасом, в несколько раз больше наименьшего общего кратного чисел формулы;
• для координатной плоскости - чуть больше всех чисел формулы.

Делимость: DEL

def DEL(n, m):
    return n % m == 0

ДЕЛ(n, m) - «n делится на m без остатка». В Python это проверка остатка: n % m - остаток от деления n на m; делится, если он равен 0. Функцию объявляют один раз над f, а в формуле пишут DEL(x, A) - так же, как в условии.

• «делится на 3» → x % 3 == 0;
• «не делится на 3» → x % 3 != 0.

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

m & n сравнивает двоичные записи чисел разряд за разрядом и оставляет 1 только там, где единица в обоих числах:

14 = 1110
 5 = 0101
14 & 5 = 0100 = 4

• x & 52 != 0 - у x есть хотя бы одна единица в тех разрядах, где единицы у 52;
• x & 48 == 0 - у x нет единиц ни в одном разряде, где единицы у 48;
• (x & 3) == 3 - у x есть все единицы числа 3 (два младших разряда).

Подсчёт перебором

Если нужно просто посчитать числа или точки с условием, перебирают их все и считают подходящие:

count = 0
for x in range(1, 51):
    if x % 7 == 0 and x % 3 != 0:
        count += 1
print(count)

• range(1, 51) - отрезок [1; 50]: правая граница на 1 больше;
• для точек на плоскости - два вложенных цикла: внешний по x, внутренний по y, каждая пара - точка.

Отрезки в Python

«x ∈ P», где P = [3; 13], - это двойное неравенство:

P = 3 <= x <= 13

Переменная P получает True, если x лежит на отрезке (концы включены), и False иначе. После этого в формуле пишут просто P, not P и т. д. Отрезок A с неизвестными концами a1 и a2 записывают так же: A = a1 <= x <= a2.

Перебор концов отрезка

def f(x, a1, a2):
    P = 3 <= x <= 13
    Q = 28 <= x <= 44
    A = a1 <= x <= a2
    return (P <= (not Q)) and (A <= P)

xs = [i / 2 for i in range(95)]
lengths = []
for a1 in range(48):
    for a2 in range(a1, 48):
        if all(f(x, a1, a2) for x in xs):
            lengths.append(a2 - a1)
print(max(lengths))

• x в условии - любое действительное число, а не только целое. Проверяем x с шагом 0,5: [i / 2 for i in range(95)] - это 0; 0,5; 1; …; 47. Так программа проверяет и концы отрезков, и точки между целыми числами (важно, когда концы отрезков «выколоты» отрицанием);
• концы A целые: перебираем все пары a1 ≤ a2;
• каждая подходящая пара даёт длину a2 - a1; в конце берём max или min - что спрашивают.

Множества строк

from itertools import product

U = ["".join(w) for w in product("01", repeat=6)]

• product("01", repeat=6) выдаёт все наборы из шести символов 0 и 1: ('0','0','0','0','0','0'), …, ('1','1','1','1','1','1') - всего 2⁶ = 64;
• "".join(w) склеивает набор в строку '000000';
• U - список всех строк, «элементов множеств».

Свойства строк:

• «чётное число единиц» → x.count("1") % 2 == 0;
• «начинается с 00» → x.startswith("00");
• «оканчивается на 00» → x.endswith("00").

В функции f(x) каждое множество - переменная True/False: P = x.count("1") % 2 == 0, а «x ∈ A» - проверка x in A.

Наименьшее множество A

A = set()
for x in U:
    if not f(x):
        A.add(x)
print(len(A))

• начинаем с пустого множества set();
• если для строки x формула ложна, пока x не в A, - x обязана попасть в A, иначе формула не будет тождественно истинной;
• A.add(x) добавляет строку в множество;
• len(A) - мощность (количество элементов).

Для наибольшего множества поступают наоборот: начинают с A = все элементы и удаляют те, для которых формула ложна (A.remove(x)).

Граница перебора

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

• для поразрядной конъюнкции - степень двойки, большая всех чисел формулы (старшие разряды x на x & 52 не влияют);
• для ДЕЛ - с запасом больше наименьшего общего кратного чисел формулы;
• для неравенств с x и y - с запасом дальше всех чисел формулы; если в формуле есть x·y или x², граница нужна больше.

A перебираем до той же границы, что и x: чтобы отбросить большое A, нужен такой же большой x-контрпример.

N = 120

def f(x, y, A):
    return (x > A) or (y > A) or (x + 2 * y < 110)

for A in range(N - 1, -1, -1):
    if all(f(x, y, A) for x in range(N) for y in range(N)):
        print(A)
        break

Как убедиться, что границы хватает: запустить программу ещё раз с удвоенным N (здесь N = 240). Ответ тот же - значит, дальше границы ничего не меняется. Ответ изменился - граница мала, её увеличивают и проверяют снова. Особенно это важно, когда программа печатает число у самой границы перебора.

Тождественно ложная формула

Иногда спрашивают, при каком A формула тождественно ложна - равна 0 при любых x. Программа та же, меняется только проверка:

for A in range(N):
    if all(not f(x, A) for x in range(N)):
        print(A)
        break

• not f(x, A) - True, когда формула ложна;
• all(not f(x, A) for x in …) - формула ложна при всех x.

В шаблоне с множествами и отрезками то же самое записывают как сравнение с нулём: f(x) == 0 - формула ложна, f(x) == 1 - истинна.

Опорные точки отрезков

Когда x - любое действительное число, а концы A заранее не известны, удобен «новый способ» шаблона:

def f(x):
    P = 17 <= x <= 54
    Q = 37 <= x <= 83
    A = a1 <= x <= a2
    return (P) <= ((Q and not A) <= (not P))

ox = [dx for x in (17, 37, 54, 83) for dx in (x, x + 0.1, x - 0.1)]
m = []
for a1 in ox:
    for a2 in ox:
        if a2 >= a1 and all(f(x) == 1 for x in ox):
            m.append(a2 - a1)
print(round(min(m)))

• ox - опорные точки: концы всех отрезков из условия и точки рядом с ними (на 0,1 левее и правее). Между соседними концами ни одно утверждение «x ∈ P» не меняет значения, поэтому достаточно проверить формулу только в этих точках;
• концы A тоже выбираем среди опорных точек: выгодный отрезок A всегда начинается и заканчивается у концов отрезков из условия;
• f берёт a1 и a2 из циклов программы - это текущий отрезок-кандидат;
• all(f(x) == 1 for x in ox) - формула истинна во всех опорных точках (для тождественно ложной - == 0);
• m собирает длины подходящих отрезков, в конце печатаем min(m) или max(m);
• round нужен из-за поправки 0,1: если конец отрезка из условия «выколот», программа сдвигает конец A на 0,1, и длина получается, например, 18,9 вместо 19.

Множества чисел

Если множества заданы перечислением, их так и записывают в Python:

P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
Q = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}

def f(x):
    return ((x in A) <= (x in P)) and ((x in Q) <= (not (x in A)))

A = P | Q

for x in P | Q:
    if f(x) == 0:
        A.remove(x)

print(len(A))

• «x ∈ P» - x in P, «x ∉ P» - x not in P;
• наибольшее A: начинаем со всех чисел из условия (A = P | Q) и убираем те x, при которых формула ложна (A.remove(x));
• наименьшее A: начинаем с пустого A = set() и добавляем x, при которых формула ложна, пока x не в A (A.add(x));
• для тождественно ложной формулы сравнение меняется на f(x) == 1;
• в конце печатают то, что спрашивают: количество len(A), сумму sum(A) или произведение math.prod(A) (нужен import math).

Таблица истинности перебором

Если в формуле только логические переменные (A, B, C или K, L, M, N), их значения - 0 и 1, и все наборы перебирает product:

from itertools import product

def F(K, L, M, N):
    return (K or M) <= (M or (not L) or N)

for K, L, M, N in product([0, 1], repeat=4):
    if F(K, L, M, N) == 0:
        print(K, L, M, N, sep='')

• product([0, 1], repeat=4) - все 16 наборов из нулей и единиц;
• печатаем набор, на котором выражение ложно (или истинно - что спрашивают);
• два выражения равносильны, если совпадают на всех наборах: all(F(*v) == G(*v) for v in product([0, 1], repeat=3)).