15.02 Множества

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

Преобразуем импликацию и уберём лишнее:

Отрицаем известную часть:

Истина для отрицаемой части достигается, если не принадлежит множествам и .

Значит, так как , множество А может быть пустым. Тогда минимальное количество элементов в данном множестве – 0.

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

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

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

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