15.02 Множества

Составим систему для врагов:

Мечты врагов такие: «Вот бы любой элемент множества не являлся элементом множеств и ». Тогда друзья, наоборот, хотят, чтобы любой элемент множества являлся элементом множеств и . Наибольшее возможное число элементов множества — объединение множеств и (т. е. все их элементы). Таких различных элементов .

Враги хотят подобрать такие чтобы они были не в и в и в , т.е. все иксы что лежат в и . Это: .

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

Враги хотят чтобы был в , в и при этом не в . Тогда .

Друзья хотят чтобы эти были в , тогда и .

Враги хотят чтобы одновременно был в , в , не в . Такой подходящий .

Друзья хотят чтобы этот был в и было как можно меньше. Тогда и .

Враги хотят чтобы одновременно был в , в , не в . Тогда .

Друзья хотят чтобы эти были в и было как можно меньше. Тогда и .

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

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

Нужно найти случаи, когда это выражение будет истинно, потому что для этих случаев в исходном выражении известная часть будет давать ложь. Данное выражение будет давать истину в тех случаях, когда не принадлежит отрезку и не принадлежит отрезку . Такие находятся вне множеств и . Следовательно, все эти точки должны НЕ входить в множество , тогда множество это объединение множеств и , а именно . Количество элементов в нем равно 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))

Решение (ручками):

Составим систему для тех случаев, когда выражение тождественно ложно:

Рассмотрим те , которые не принадлежат объединению , то есть . Для того чтобы выражение было всегда истина необходимо чтобы все эти пренадлежали . Тогда ( будет подмножеством объединения ).

Максимальное . Это множество содержит элементов, запишем это значение в ответ.

Решение (прогой):

p = [i for i in range(2, 21, 2)]
q = [i for i in range(5, 51, 5)]
a = [i for i in range(100)]

for i in range(100):
    for x in range(1000):
        if (((x == i) <= (x in p)) or ((x not in q) <= (x != i))) == 0:
            a.remove(i)
print(len(a))

Система для врагов:

Враги мечтают чтобы были в и в и они не были в A.

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

Система для врагов:

Враги мечтают чтобы были в и в , то есть , и они не были в A.

Друзья хотят чтобы эти иксы были в A и хотят сделать A с минимальной суммой элементов, тогда они возьмут все элементы из пересечения и , тогда ответ .

Для краткости записи заменим: , тогда получается . Упростим это выражение, раскрыв импликацию: .

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

Для краткости записи заменим: , тогда получается . Упростим это выражение, раскрыв импликацию и уберем повторяющееся : .

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

Тогда искомое множество будет состоять из элементов . Всего в нем 17 элементов.

Для краткости записи заменим: , тогда получается .

Из этой формулы видно, что множество должно перекрыть множество, которое не перекрыто множеством . Тогда минимальное количество элементов в множестве будет, когда оно состоит из элементов, которые есть в с и в b, то есть {}. Ответ 9.

Для краткости записи заменим: , тогда получается . Упростим это выражение, раскрыв импликацию: .

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

Тогда, чтобы получить ответ, необходимо перемножить эти элементы: . Ответ 15.

Упростим выражение, раскрыв импликацию:

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

Тогда искомое минимальное множество будет состоять из элементов . Всего в нем 3 элемента.