Задача к ЕГЭ по информатике на тему «Множества» №3

Просмотров 9 Комментарии 0

На числовой прямой даны два отрезка:

Элементами множеств A, P, Q являются натуральные числа, причем

$P = {2,4,6,8,10,12,14,16,18,20},Q = {3,6,9,12,15,21,24,27,30}.$

Известно, что выражение

$((x ∈ A ) → (x ∈ P ))∨ ((¬(x ∈ Q )) → ¬ (x ∈ A))$

истинно (т.е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве $A$ .

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

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

(x ∕∈ A)∨ (x ∈ P )∨(x ∈ Q)

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

(x ∕∈ P) ∧(x ∕∈ Q )

Нужно найти случаи, когда это выражение будет истинно, потому что для этих случаев в исходном выражении известная часть будет давать ложь. Данное выражение будет давать истину в тех случаях, когда $x$ не принадлежит отрезку $P$ и не принадлежит отрезку $Q$ . Такие $x$ находятся вне множеств $P$ и $Q$ . Следовательно, все эти точки должны НЕ входить в множество $A$ , тогда множество $A$ это объединение множеств $P$ и $Q$ , а именно $A = {2,4,6,8,10,12,14,16,18,20,3,9,15,21,24,27,30}.$ Количество элементов в нем равно 17.

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

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

P = set([x for x in range(2, 21, 2)])
Q = set([x for x in range(3, 31, 3)])
A = set(x for x in range(40))
for x in range(40):
    if not f(x, P, Q, A):
        A.remove(x)
print(len(A))

Ответ: 17