Дискретная математика: Учебное пособие. Часть I - Основания дискретной математики, страница 13

Эквивалентные преобразования формул. Опираясь на законы алгебры множеств, можно выполнять эквивалентные преобразования формул, упрощая их описание. При преобразовании алгебраических выражений необходтмо прежде всего устранить операторы разности – “\” и симметрической разности “D”, т. е. использовать только основную сигнатуру алгебры множеств - {ù, Ç, È}.

При написании сложного алгебраического выражения следует помнить, что

·  “ù” относится к непосредственно следующей формуле F;

·  “ù” следует прежде всего опустить от формулы n-го порядка к элементарной формуле по правилу ù(AÇB)=ùAÈùB или ù(AÈB)=ùAÇùB;

·  “Ç” относится к непосредственно окружающим формулам;

·  “È” относится к непосредственно окружающим формулам;

операция “Ç” сильнее “È”, что позволяет опускать скобки “(“  и “)”, например, (AÇBÇCÇùD)È(ùAÇC)=AÇBÇCÇùDÈùAÇC.

Пример: Пусть F=(AÇBÇCÇùD)È(ùAÇC)È(ùBÇC)È(CÇD).

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

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=(ADB)D(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).

Таким образом (ADB)D(AÇB)=(AÈB).

Прямое произведение отображений есть отображение, кортежи которого формируются в результате присоединения справа к каждому кортежу первого отображения каждого кортежа второго отображения.