15.02 Множества

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

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

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

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

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

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

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

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

# функция проверяет выполнение выражения для конкретного x и текущего множества A
def f(x, a):
    # создаём множество P - все чётные числа от 2 до 10 включительно
    P = set([i * 2 for i in range(1, 6)])
    # создаём множество Q - все кратные 3 числа от 3 до 15 включительно
    Q = set([i * 3 for i in range(1, 6)])
    # проверяем истинность выражения для данного x и множества A
    return ((not(x in a)) <= (x in P)) or ((x in Q) <= (x in a))

# изначально множество A пустое
a = set()
# перебираем кандидатов на включение в A
for x in range(20):
    # если выражение ложно для текущего x, добавляем x в множество A
    if not(f(x, a)):
        a.add(x)
# выводим минимальное количество элементов множества A
print(len(a))