15.02 Множества

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

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

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

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

Значит, так как , во множестве А должны оказаться числа: 3, 9, 15, 21, 24, 27, 30. Тогда минимальное количество элементов в данном множестве – 7.

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

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

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

# функция проверяет выполнение выражения для конкретного x и множества A
def f(x, P, Q, A):
    return ((not(x in A)) <= (x in P)) or ((x in Q) <= (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()
# перебираем кандидатов на элементы множества A
for x in range(40):
    # если выражение ложно для текущего x, добавляем x в A
    if not f(x, P, Q, A):
        A.add(x)
# выводим минимальное количество элементов множества A
print(len(A))