15.02 Множества

Решение руками:

Раскрываем импликацию:

Найдем иксы, при которых известная часть не выполняется, для этого выполним инверсию известной части:

Нужно найти случаи, когда это выражение будет истинно, потому что для этих случаев в исходном выражении известная часть будет давать ложь. Данное выражение будет давать истину в тех случаях, когда не принадлежит отрезку и не принадлежит отрезку . Такие находятся вне множеств и . Следовательно, все эти точки должны НЕ входить в множество , тогда множество это объединение множеств и , а именно Количество элементов в нем равно 17.

Решение программой:

Для нахождения наибольшего количества элементов множества , при котором выражение

тождественно истинно для всех натуральных , используем программный перебор. Идея заключается в том, чтобы изначально взять множество , содержащее все кандидаты (например, числа от до ). Для каждого проверяем, выполняется ли выражение с текущим множеством . Если для некоторого выражение ложно, удаляем из . Таким образом формируем максимальное множество , которое обеспечивает тождественную истинность выражения.

# функция проверяет выполнение выражения для конкретного x и множества A
def f(x, P, Q, A):
    return ((x in A) <= (x in P)) or ((not (x in Q)) <= (not (x in A)))

# создаём множество P - все чётные числа от 2 до 20 включительно
P = set([x for x in range(2, 21, 2)])
# создаём множество Q - все кратные 3 числа от 3 до 30 включительно
Q = set([x for x in range(3, 31, 3)])
# изначально множество A содержит все кандидаты
A = set(x for x in range(40))
# перебираем кандидатов на удаление из множества A
for x in range(40):
    # если выражение ложно для текущего x, удаляем x из A
    if not f(x, P, Q, A):
        A.remove(x)
# выводим максимальное количество элементов множества A
print(len(A))