15.02 Множества

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

Упростим начальное выражение:

Методом сковородки отрицаем известную часть:

Получаем, что – любые числа кроме тех, что входят во множества и . Но множество должно быть таким, чтобы ему не принадлежало. Поэтому нужно взять все элементы этих двух множеств: {2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 25, 30, 35, 40, 45, 50}. Их количество – 18.

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

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

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

# создаём множество P - все чётные числа от 2 до 20 включительно
p = [i for i in range(2, 21, 2)]
# создаём множество Q - все кратные 5 числа от 5 до 50 включительно
q = [i for i in range(5, 51, 5)]
# изначально множество A наполняется числами от 0 до 99
a = [i for i in range(100)]
# перебираем все кандидаты на элементы A
for i in range(100):
    for x in range(1000):
        # проверяем логическое выражение для текущих x и элемента i
        if (((x == i) <= (x in p)) or ((x not in q) <= (x != i))) == 0:
            # если выражение ложно, удаляем элемент из множества A
            a.remove(i)
# выводим максимальное количество элементов в множестве A
print(len(a))

Первым шагом раскроем импликацию:

Раскроем правую часть по правилу (

Упростим с помощью двух правил и :

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

Инвертированное выражение дает истину (а исходное, соответственно, ложь), для тех , которые принадлежат одновременно и множеству , и множеству . Такие . Тогда, множество должно содержать как минимум эти элементы, получаем что . Количество элементов в этом множестве – 2.

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

Вспомним, что и получим:

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

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

Значит, так как , во множестве А должны оказаться числа 3 и 5. Тогда минимальное количество элементов в данном множестве – 2.

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

Вспомним, что и получим:

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

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

Значит, так как , во множестве А должно оказаться число 1. Тогда минимальное количество элементов в данном множестве – 1.

Первым шагом раскроем импликацию:

Уберем повторяющуюся часть , в итоге получаем выражение:

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

Инвертированное выражение дает истину (а исходное, соответственно ложь), для тех , которые принадлежат одновременно и множеству , и множеству . Такие . Тогда, множество должно содержать как минимум эти элементы, получаем что . Количество элементов в этом множестве – 4.

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

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

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

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

Значит, так как , во множестве А должны оказаться числа: 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))

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

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

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

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

Значит, так как , множество А может быть пустым. Тогда минимальное количество элементов в данном множестве – 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))

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

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

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

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

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

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

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

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

Первым шагом преобразуем выражение, чтобы с ним было проще работать: раскроем импликацию и отрицание.

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

Нужно найти случаи, когда это выражение будет истинно, потому что для этих случаев в исходном выражении известная часть будет давать ложь. Данное выражение будет давать истину в тех случаях, когда x принадлежит отрезку P и принадлежит отрезку Q одновременно. Следовательно, все эти точки должны входить в множество A, тогда множество A это пересечение множеств P и Q , а именно A = 5,12,15. Сумма элементов этого множества равна . Это и будет являться ответом.

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

Пусть .

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

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

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

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

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

def f(x, A):
    first = [2, 4, 6, 8, 10, 12]
    second = [3, 6, 9, 12, 15]
    return (x not in first) or (((x in second) and (x not in A)) <= (x not in first))
def podh(A):
    for x in range(1, 100):
        if not f(x, A):
            return False
    return True
arr = [2, 4, 6, 8, 10, 12, 15, 9, 3]
minim = 100
for i in range(2 ** len(arr)):
    A = []
    t = i
    for j in range(len(arr)):
        if t % 2 == 1:
            A.append(arr[j])
        t //= 2
    if podh(A):
        minim = min(minim, len(A))
print(minim)

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

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

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

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

Значит, так как , во множестве А должны оказаться числа: 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))

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

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

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

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

Значит, так как , во множестве А должны оказаться числа, принадлежащие или . Тогда наибольшее возможное количество элементов в данном множестве – 18.

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

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

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

# создаём множество P - все чётные числа от 2 до 20 включительно
p = [i for i in range(2, 21, 2)]
# создаём множество Q - все кратные 5 числа от 5 до 50 включительно
q = [i for i in range(5, 51, 5)]
# начинаем с максимально возможного множества A
a = [i for i in range(100)]

# перебираем кандидатов на удаление из множества A
for i in range(100):
    for x in range(1000):
        # если выражение ложно для текущего i и x, удаляем i из множества A
        if (((x == i) <= (x in p)) or ((x not in q) <= (x != i))) == 0:
            a.remove(i)

# выводим количество элементов множества A после удаления всех неподходящих
print(len(a))

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

Пусть .

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

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

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

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

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

def f(x, A):
    first = [2, 4, 6, 8, 10, 12]
    second = [3, 6, 9, 12, 15]
    return (x not in first) <= (((x in second) and (x not in A)) <= (x in first))

def podh(A):
    for x in range(1, 100):
        if not f(x, A):
            return False
    return True

arr = [2, 3, 4, 6, 8, 9, 10, 12, 15]
ans = 100
for i in range(2 ** len(arr)):
    A = []
    t = i
    for j in range(len(arr)):
        if t % 2 == 1:
            A.append(arr[j])
        t //= 2
    if podh(A):
        if ans > len(A):
            print(A)
        ans = min(ans, len(A))
print(ans)

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

Сделаем отрицание известной части, чтобы определить, при каких исходное выражение ложно:

Это выражение истино (а исходное, соответственно, ложно) при , которые принадлежат и множеству и множеству одновременно. Получаем что, при исходное выражение ложно. Тогда, множество должно содержать как минимум эти . Так как в задании просят определить наименьшее возможное значение суммы элементов множества , то в этом множестве будут только эти два элемента: . Отсюда получаем ответ .

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

Сделаем отрицание известной части, чтобы определить, при каких исходное выражение ложно:

Это выражение истино (а исходное, соответственно, ложно) при , которые принадлежат и множеству и множеству одновременно. Получаем что, при исходное выражение ложно. Тогда, множество должно содержать как минимум эти . Так как в задании просят определить наименьшее возможное значение суммы элементов множества , то в этом множестве будут только эти два элемента: . Отсюда получаем ответ .

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

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

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

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

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

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

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

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

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

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

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

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

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