Question

Элементами множеств А, 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 Î A) → (x Î P) ) /\ ( (x Î Q) → ¬(x Î A) ) истинно (то есть принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов в множестве A.

Answer 1

((x ∈ A)→(x ∈ P))∧((x∈Q)→ ¬(x ∈ A))
(A→P)∧(Q→¬A)
Преобразование импликации:
(¬A∨P)∧(¬Q∨¬A) ⇔
⇔ ¬A ∧ ¬Q ∨ ¬Q ∧ P ∨ ¬A ∨ ¬A ∧ P ⇔
⇔ ¬A ∧ (¬Q ∨ P ∨ 1) ∨ ¬Q ∧ P ⇔
⇔ ¬A ∨ ¬Q ∧ P. 

Выражение ¬A ∨ ¬Q ∧ P должно быть равно 1
¬Q ∧ P будет  равно 1 если x ∈ {2, 4, 8, 10, 14, 16, 20}
¬А будет равно 1 при любом значении кроме ¬Q ∧ P
Отсюда, максимальное количество в множестве А будет включать в себя все элементы множества ¬Q ∧ P, их 7

Ответ: 7 

Answer 2

Нарисуем на диаграмме, при каких x выражение ((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A)) истинно. Выражение состоит из двух условий, соединенных логическим и, так что оно будет истинным в том и только в том случае, когда оба условия истинны.

(x ∈ A) → (x ∈ P) истинно всегда, кроме случая x ∈ A, x ∉ P. На рисунке область истинности выделена синей штриховкой.
(x ∈ Q) → ¬(x ∈ A) истинно всегда, кроме случая x ∈ Q, x ∈ A. На рисунке эта область выделена зелёной штриховкой.

Формула истинна, если x принадлежит областям, выделенным обеими штриховками одновременно. Если формула верна при всех x, то области, не выделенные какой-то из штриховок, не содержат элементов, так что всё множество A состоит из элементов, которые есть в P, но которых нет в Q (эта область на рисунке помечена звёздочкой). Подходящих элементов всего 7: P \ Q = {2, 4, 8, 10, 14, 16, 20}, – так что максимальное количество элементов в A равно семи.

Ответ: 7.