Лекция 4. 3. Переместительный законх0 ù х1 = х1 ù х0, х0 ú х1 = х1 ú х0, х0 å х1 = х1 å х0

3. Переместительный закон х₀ Ù х₁ = х₁ Ù х₀, х₀ Ú х₁ = х₁ Ú х₀, х₀ Å х₁ = х₁ Å х₀.

4. Распределительный закон х₀ Ù (х₁ Ú х₂) = (х₀ Ù х₁) Ú (х₀ Ù х₂),
х₀ Ú (х₁ Ù х₂) = (х₀ Ú х₁) Ù (х₀ Ú х₂),
х₀ Ù (х₁ Å х₂) = (х₀ Ù х₁) Å (х₀ Ù х₂).
Докажем второе равенство. Раскрывая скобки его правой части, получаем
х₀х₀ Ú х₀х₂ Ú х₁х₀ Ú х₁х₂ = х₀ Ú х₀х₂ Ú х₁х₀ Ú х₁х₂ = х₀(1 Ú х₂ Ú х₁) Ú х₁х₂ = х₀ Ú х₁х₂, что и следовало доказать. Остальные равенства очевидны.

5. Закон двойственности (правила де Моргана). Этот закон устанавливает связь между дизъюнкцией и конъюнкцией с помощью инверсии:
х₀ Ú х₁ = х₀х₁ = х₀ | х₁, х₀х₁ = х₀ Ú х₁ = х₀ ¯ х₁.

Эти законы справедливы для любого числа аргументов. Следует отметить, что последние 4 закона используются особенно часто для преобразования ФАЛ. К примеру, докажем равенство: х₀ Å х₁ = х₀х₁ Ú х₀х₁.

Представим сумму по модулю два в виде дизъюнкции, конъюнкции и инверсии:х₀х₁ Ú х₀х₁ = (х₀х₁) ¯ (х₀х₁). Применив к полученному выражению второе правило де Моргана, получаем (х₀х₁)(х₀х₁) = (х₀ | x₁)(x₀ | x₁). Теперь к каждому сомножителю применим первое правило де Моргана (х₀ Ú х₁)(х₀ Ú х₁) и воспользуемся распределительным законом: х₀х₀ Ú х₀х₁ Ú х₁х₀ Ú х₁х₁. Согласно пятому тождеству первое и последнее слагаемые обращаются в ноль, т.е. последнее выражение запишется как 0 Ú х₀х₁ Ú х₁х₀ Ú 0 или, согласно десятому тождеству, х₀х₁ Ú х₁х₀. Применив переместительный закон, окончательно получаем х₀х₁ Ú х₀х₁, что и требовалось доказать.

6. Закон поглощения х Ú хz = x, x(x Ú z) = x.

7. Закон склеивания хz Ú xz = x, (x Ú z)(x Ú z) = x.

Справедливость этих двух законов докажите самостоятельно.

2.6. Минимизация ФАЛ.

В большинстве случаев совершенная форма записи ФАЛ не является самой простой для аналитического задания КЦУ. Следовательно, её техническая реализация приведёт к излишне сложному устройству. Поэтому логическое выражение прежде всего следует упростить, не нарушая при этом значения функции.