1.6.2. Законы алгебры множеств

Аксиомы общей алгебры формируют законы алгебры множеств, если f_k=”” и f_m=””:

• коммутативности: (AB)=(BA) и (AB)=(BA);

• ассоциативности: A(BC)=(AB)C; A(BC)=(AB)C;

• дистрибутивности: A(BC)=(AB)(AC); A(BC)=(AB)(AC);

• идемпотентности: AA=A и AA=A;

• поглощения: A(AB)=A и A(AB)=A;

• противоречия: AA=, AA=U;

• двойного отрицания: (A)=A;

• закон де Моргана: (AB)= AB и (AB)= AB;

• свойства универсального и пустого множества:

AU=U и AU=A, А=А и АU=A..

1.6.3. Эквивалентные преобразования формул

Если A и B подмножества множества U, то формулами являются F=A, F=B, F=(AB), F=(AB), а также F, (F₁F₂), (F₁F₂). Никаких иных формул нет.

При написании сложных формул следует помнить, что

• “” относится к непосредственно следующей формуле F,

• “” и “” относятся к окружающим формулам,

• если “” относится к формулам (F₁F₂) или (F₁F₂), то прежде всего следует выполнить преобразования: (F₁F₂)=F₁F₂ или (F₁F₂)=F1F₂,

• операция “” сильнее “”, что позволяет опускать скобки.

При эквивалентных преобразованиях следует прежде всего устранить операторы разности “\” и симметрической разности “” по правилам: (А\В)=(АВ) и (АВ)=(АВ)(ВА).

Пример: F=(ABCD)(AC)(BC)(CD).

Упростить формулу F.

• по закону коммутативности:

F=(CABD)(CA)(CB)(CD);

• по закону дистрибутивности:

F=(CABD)(CA)(C(BD));

• по закону дистрибутивности:

F=(CABD)(C(ABD));

• по закону дистрибутивности:

F=C((ABD)(ABD));

• по аксиоме де Моргана:

F=C((ABD)(ABD));

• по закону противоречия:

F=(CU);

• по свойству универсального множества: F=C.

Ответ:(ABCD)(AC)(BC)(CD)=C.

Пример: F=(A\B)(A\C). Упростить выражение.

• устранить символы “\”

F=(AB)(AC);

• по закону дистрибутивности:

F=A(BC);

• по закону де Моргана:

F=A(BC);

• внести символ “\”:

F=A\(BC).

Ответ: (A\B)(A\C)=A\(BC).

Пример: F=(AB)(AB). Упростить выражение.

• устранить символы “”:

F=(((AB)(AB)) (AB)) (((AB)(AB))(AB));

• по закону де Моргана:

F=(((AB)(AB))  (AB)) (((AB)(AB))(AB));

• по закону де Моргана:

F=(((AB)(AB))  (AB)) (((AB)(AB))(AB));

• по закону дистрибутивности:

F=(((AB)(AB)(AB))(AB)(((AB)(AB))(AB));

• по закону дистрибутивности:

F=(ABA)(ABB)(ABA)(ABB)(((AB)

(AB)) (AB));

• по законам идемпотентности и противоречия:

F=((AB)(AB))(((AB)(AB))(AB));

• по закону дистрибутивности:

F=((AB)(AB))(((AA)(AB)(AB)(BB))(AB));

• по закону противоречия:

F=((AB)(AB))((AB)(AB))(AB)));

• по закону дистрибутивности:

F=(AB)(AB)((AB)(AB))((AB)(AB));

• по законам идемпотентности и противоречия:

F=(AB)(AB)(AB));

• по закону дистрибутивности:

F=A(BB)B(AA);

• по закону противоречия:

F=(AB).

Ответ: (AB)(AB)=(AB).