Тема 15. Алгебра логики – преобразование логических выражений

15.02 Множества

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела алгебра логики – преобразование логических выражений

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#16317

Элементами множеств $A$ , $P$ и $Q$ являются натуральные числа, причём $P = {2,4,6,$

$8,10,12,14,16,18,20}$ и $Q = {5,10,15,20,25,30,35,40,45,50}$ . Известно, что выражение

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

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

Показать ответ и решение

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

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

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

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

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

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

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

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

p = [i for i in range(2, 21, 2)]
#воссоздаем множество p - это все чётные числа от 2 до 20 включительно
q = [i for i in range(5, 51, 5)]
#воссоздаем множество q - это все кратные 5 числа от 5 до 50 включительно
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))#вывод максимального количества чисел во множестве А

Ответ: 18

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#16318

Элементами множеств $A$ , $P$ и $Q$ являются натуральные числа, причём $P = {1,2,3,4,5,6}$ и $Q = {3,5,15}$ . Известно, что выражение

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

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

Показать ответ и решение

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

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

Раскроем правую часть по правилу ( $A ∧B )∨ C = (A ∨ C) ∧(B ∨ C)$

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

Упростим с помощью двух правил $A ∨ A-= 1$ и $A ∧ 1 = A$ :

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

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

(x ∈ P) ∧(x ∈ Q )

Инвертированное выражение дает истину (а исходное, соответственно, ложь), для тех $x$ , которые принадлежат одновременно и множеству $P$ , и множеству $Q$ . Такие $x = {3,5}$ . Тогда, множество $A$ должно содержать как минимум эти элементы, получаем что $A = {3,5}$ . Количество элементов в этом множестве – 2.

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 3#18144

Элементами множеств $A,P,Q$ являются натуральные числа, причём $P = {1,2,3,4,5,6}$ , $Q = {3,5,15}$ . Известно, что выражение

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

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

Показать ответ и решение

Враги хотят чтобы $x$ был в $P$ , в $Q$ и при этом не в $A$ . Тогда $x ∈ {3,5}$ .

Друзья хотят чтобы эти $x$ были в $A$ , тогда $A = {3,5}$ и $|A| = 2$ .

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 4#18145

Элементами множеств $A,P,Q$ являются натуральные числа, причём $P = {1,3,7}$ , $Q = {1,2,4,5,6}$ . Известно, что выражение

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

Показать ответ и решение

Враги хотят чтобы $x$ одновременно был в $P$ , в $Q$ , не в $A$ . Такой подходящий $x = 1$ .

Друзья хотят чтобы этот $x$ был в $A$ и $|A|$ было как можно меньше. Тогда $A = {1}$ и $|A | = 1$ .

Ответ: 1

Ошибка.
Попробуйте повторить позже

Задача 5#18146

Элементами множеств $A,P,Q$ являются натуральные числа, причём $P = {1,3,4,9,11,13,15,17,19,21}$ , $Q = {3,6,9,12,15,18,21,24,27,30}$ . Известно, что выражение

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

Показать ответ и решение

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

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

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

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

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

(x ∈ P) ∧(x ∈ Q )

Инвертированное выражение дает истину (а исходное, соответственно ложь), для тех $x$ , которые принадлежат одновременно и множеству $P$ , и множеству $Q$ . Такие $x = {3,9,15,21}$ . Тогда, множество $A$ должно содержать как минимум эти элементы, получаем что $A = {3,9,15,21}$ . Количество элементов в этом множестве – 4.

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 6#20055

Элементами множеств 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$ .

Показать ответ и решение

def f(x, P, Q, A):
    return ((not(x in A)) <= (x in P)) or ((x in Q) <= (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()
for x in range(40):
    if not f(x, P, Q, A):
        A.add(x)
print(len(A))

Ответ: 7

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#20056

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

$P = {1,3,5,7,9,11,13,15,17,19,21},Q = {3,6,9,12,15,21,24,27,30}.$

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

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

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

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

Показать ответ и решение

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(1, 22, 2)])
Q = set([x for x in range(3, 31, 3)])
A = set()
for x in range(40):
    if not f(x, P, Q, A):
        A.add(x)
print(len(A))

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 8#20057

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

Элементами множеств 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

Ошибка.
Попробуйте повторить позже

Задача 9#22656

Элементами множества А являются натуральные числа. Известно, что выражение

------------------- ------- ------------------- (x ∈ {2,4,6,8,10,12})∨ (((x ∈ {3,6,9,12,15})∧ (x ∈ A )) → (x ∈ {2,4,6,8,10,12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное количество элементов множества A.

Показать ответ и решение

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)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 10#23190

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

$P = {2,4,6,8,10},Q = {3,6,9,12,15}.$

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

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

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

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

Показать ответ и решение

def f(x, a):
    P = set([i * 2 for i in range(1, 6)])
    Q = set([i * 3 for i in range(1, 6)])
    return ((not(x in a)) <= (x in P)) or ((x in Q) <= (x in a))
a = set()
for x in range(20):
    if not(f(x, a)):
        a.add(x)
print(len(a))

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 11#26977

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

$P = {2,4,6,8,10,12,14,16,18,20},Q = {5,10,15,20,25,30,35,40,45,50}.$

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

------- ------- ((x ∈ A) → (x ∈ P )) ∨((x ∈ Q ) → (x ∈ A ))

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

Показать ответ и решение

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

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

( ||x ∈ A |{ |x ∕∈ P ||( x ∕∈ Q

Рассмотрим те $x$ , которые не принадлежат объединению $P ∪ Q$ , то есть $x ∕∈ {2,4,5,6,8,10,12,14,15,16,18,20,25,30,35,40,45,50}$ . Для того чтобы выражение было всегда истина необходимо чтобы все эти $x$ пренадлежали $A$ . Тогда $A ∈ {2,4,5,6,8,10,12,14,15,16,18,20,25,30,35,40,45,50}$ ( $A$ будет подмножеством объединения $P ∪ Q$ ).

Максимальное $A = P ∪ Q$ . Это множество содержит $18$ элементов, запишем это значение в ответ.

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

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))

Ответ: 18

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#29725

Элементами множества А являются натуральные числа. Известно, что выражение

------------------- ------- ------------------- (x ∈ {2,4,6,8,10,12}) ∨((x ∈ {3,6,9,12,15})∧ (x ∈ A ) → (x ∈ {2,4,6,8,10,12}))

Показать ответ и решение

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)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 13#29726

Элементами множества А являются натуральные числа. Известно, что выражение

------------------- ------- (x ∈ {2,4,6,8,10,12}) → ((x ∈ {3,6,9,12,15})∧(x ∈ A) → (x ∈ {2,4,6,8,10,12}))

Показать ответ и решение

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)

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 14#29727

Элементами множеств $P$ и $Q$ являются натуральные числа, причём
$P = {2,4,8,12,15}$ и $Q = {3,6,8,15}$ . Известно, что выражение

------- (x ∈ P ) → ((x ∈ Q)∨ (x ∈ A ))

тождественно истинно (т.е. принимает значение 1 при любых неотрицательных целых значениях переменной $x$ ). Укажите наименьшее возможное значение произведения элементов множества $A$ .

Показать ответ и решение

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

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

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

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

(x ∈ P) ∧(x ∈ Q )

Это выражение истино (а исходное, соответственно, ложно) при $x$ , которые принадлежат и множеству $P$ и множеству $Q$ одновременно. Получаем что, при $x ∈ {8,15}$ исходное выражение ложно. Тогда, множество $A$ должно содержать как минимум эти $x$ . Так как в задании просят определить наименьшее возможное значение суммы элементов множества $A$ , то в этом множестве будут только эти два элемента: $A = {8,15}$ . Отсюда получаем ответ $8 ∗15 = 120$ .

Ответ: 120

Ошибка.
Попробуйте повторить позже

Задача 15#29728

Элементами множеств $P$ , $Q$ и $A$ являются натуральные неотрицательные числа, причём
$P = {2,4,6,8,10,12}$ и $Q = {3,6,9,12,15}$ . Известно, что выражение

------- ------- (x ∈ P ) → (((x ∈ Q) ∧(x ∈ A )) → (x ∈ P ))

тождественно истинно (т.е. принимает значение 1 при любых неотрицательных целых значениях переменной $x$ ). Укажите наименьшее возможное значение суммы элементов множества $A$ .

Показать ответ и решение

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

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

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

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

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

(x ∈ P) ∧(x ∈ Q )

Это выражение истино (а исходное, соответственно, ложно) при $x$ , которые принадлежат и множеству $P$ и множеству $Q$ одновременно. Получаем что, при $x ∈ {6,12}$ исходное выражение ложно. Тогда, множество $A$ должно содержать как минимум эти $x$ . Так как в задании просят определить наименьшее возможное значение суммы элементов множества $A$ , то в этом множестве будут только эти два элемента: $A = {6,12}$ . Отсюда получаем ответ $6 + 12 = 18$ .

Ответ: 18

Ошибка.
Попробуйте повторить позже

Задача 16#51788

Элементами множеств $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) при любом значении переменной $x$ . Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

Для краткости записи заменим: $a = (x ∈ A ),p = (x ∈ P ),q = (x ∈ Q)$ , тогда получается $-- (a → p)∨ (q → a)$ . Упростим это выражение, раскрыв импликацию: $a∨ p∨ q$ .

Известная часть $p∨ q$ не перекрывает только числа ${3,9,15,21,24,27,30}$ , тогда эти числа необходимо перекрыть множеством $-- A$ . Для того чтобы количество элементов в множестве $A$ было минимальным, то можно взять в него 0 элементов. Тогда множество $-- A$ будет состоять из всей числовой прямой и перекроет необходимые элементы. Следовательно ответ 0.

Ответ: 0

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#51789

Элементами множеств $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 ))

Показать ответ и решение

Для краткости записи заменим: $a = (x ∈ A ),p = (x ∈ P ),q = (x ∈ Q)$ , тогда получается $- -- (a → p)∨ (q → a)$ . Упростим это выражение, раскрыв импликацию и уберем повторяющееся $a$ : $a∨ p∨ q$ .

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

Тогда искомое множество будет состоять из элементов ${2,3,4,6,8,9,10,12,14,15,16,18,20,21,24,27,30}$ . Всего в нем 17 элементов.

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 18#60316

Элементами множества $A$ являются натуральные числа. Известно, что выражение:

¬(x ∈ {1,7,9,12,18})∧ ¬(x ∈ {2,10,13,15}) ∨(x ∈ A )

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

Показать ответ и решение

Для краткости записи заменим: $a = (x ∈ A),b = (x ∈ {1,7,9,12,18}),c = (x ∈ {2,10,13,15})$ , тогда получается $- b∧ c∨ a$ .

Из этой формулы видно, что множество $A$ должно перекрыть множество, которое не перекрыто множеством $- - b∧ c$ . Тогда минимальное количество элементов в множестве $A$ будет, когда оно состоит из элементов, которые есть в с и в b, то есть { $1,2,7,9,10,12,13,15,18$ }. Ответ 9.

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 19#60317

Элементами множества $A$ являются натуральные числа. Известно, что выражение:

(x ∈ A ) → (¬(x ∈ {7,9,11,15,19}) ∧(x ∈ {1,3,5,7,9}))

истинно (т. е. принимает значение 1) при любом значении переменной $x$ . Определите наибольшее возможное значение произведения элементов множества $A$ .

Показать ответ и решение

Для краткости записи заменим: $a = (x ∈ A),b = (x ∈ {7,9,11,15,19}),c = (x ∈ {1,3,5,7,9})$ , тогда получается $- a → (b∧ c)$ . Упростим это выражение, раскрыв импликацию: $- a∨ b∧ c$ .

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

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

Ответ: 15

Ошибка.
Попробуйте повторить позже

Задача 20#62998

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

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

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

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

Показать ответ и решение

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

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

Из этой формулы видно, что множество $A$ должно перекрыть множество, которое не перекрыто множеством $p ∨q$ . Тогда в в множестве $A$ должны находиться элементы, которые содержатся и в множестве $P$ , и в множестве $Q$ . То есть ${6,12,18}$ .

Тогда искомое минимальное множество будет состоять из элементов ${6,12,18}$ . Всего в нем 3 элемента.

Ответ: 3