Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 1
8, 21, 24, 27, 30}. Известно, что выражение ( (x Î A) → (x Î P) ) /\ ( (x Î Q) → ¬(x Î A) ) истинно (то есть принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов в множестве A.
((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 ∧<span> P. </span> Выражение ¬A ∨ ¬Q ∧ P должно быть равно 1 ¬Q ∧ P будет равно 1 если <span>x ∈ {2, 4, 8, 10, 14, 16, 20} </span>¬А будет равно 1 при любом значении кроме ¬Q ∧ P Отсюда, максимальное количество в множестве А будет включать в себя все элементы множества ¬Q ∧ P, их 7
Нарисуем на диаграмме, при каких 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 равно семи.
4 стр/мин значит 5*4=20 стр за пять минут
65536 - мощ. алфавита, 65536=2^16=16 бит на символ
20*40*50=40000 символов всего
40000*16=640000 бит инф объём
640000/8/1024~=78кб