Законы математической логики

В алгебре логики выполняются следующие основные законы (табл. 16.14), позволяющие осуществлять тождественные преобразования логических выражений.

Таблица 16.14

Основные законы алгебры логики

Закон

Для дизъюнкции

Для конъюнкции

Переместительный

XV у —у V X

XX у - ух X

Сочетательный

XV V z) = (XV у) V Z

х х {у х z) = (х X у) х z

Распределительный

X X (у V z) = (х X у) V (х X z)

XV (ух z) = {XV у) X (xv z)

Де Моргана

XV у = у XX

XX у = yv X

Идемпотенции

XV х—х

XXX—х

Поглощения

X V (х х у) — х

XX (xv у) =х

Склеивания

(xxy)v(xxy) = у

(xvy)x(T V у) = у

Двойного отрицания

II

II н

Операция переменной с ее инверсией

X V X - 1

ххх = 0

Операции с константами

ivO=x

XV 1 = 1

К о II II — о

X X

Если левая и правая части одновременно (при одинаковых наборах значений входящих в них переменных) принимают одинаковые значения, то закон доказан.

Для логических операций рассмотрим ряд теорем и законов.

Коммутативные законы:

Ассоциативные законы:

Дистрибутивные законы:

Операции склеивания:

Большинство теорем, а также аксиом записаны парами. При внимательном изучении пар можно вывести принцип двойственности: если в тождестве произвести взаимные замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если они имеются, то получим также тождество. Такое свойство называется принципом двойственности. Все теоремы могут быть доказаны аналитически или методом перебора (по таблице истинности). Например, докажем тождество х + ху = х + у аналитическим методом:

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

(законы алгебры логики применяются в следующем порядке: правило де Моргана, сочетательный закон, правило операций переменной с ее инверсией и правило операций с константами).

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией).

(повторяется второй сомножитель, что разрешено законом идем- потенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).

(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания).

(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания).

6. Доказать равносильность

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

Пример 1. Выполнить преобразования для упрощения логического выражения

Решение.

1. Удалить всюду логическую связку импликации :

2. Опустить отрицание на элементарные формулы по закону де Моргана:

3. Выполнить преобразование по закону дистрибутивности:

4. Удалить член , так как :

5. Выполнить преобразование по закону дистрибутивности:

6. Удалить член :

7. Применить закон ассоциативности:

8. Приравнять к «истине» значение формулы F, так как (F2vF2) = 1:

Пример 2. Выполнить эквивалентные преобразования для упрощения выражения:

Решение.

1. Удалить всюду логическую связку импликации «—>»:

2. Опустить отрицание на элементарные формулы по закону де Моргана:

3. Выполнить преобразование по закону дистрибутивности:

4. Удалить член , тогда

Пример 3. Дано суждение «или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (Q, или даже Петр поступил, и Семен поступил, и Андрей поступил (В)». Кто поступил в университет?

Решение. Формула сложного высказывания имеет вид

1. Преобразуем, используя закон де Моргана:

2. Применим закон идемпотентности

3. Применим закон дистрибутивности по переменной А:

4. Применим закон дистрибутивности по переменной С:

5. Введем константу 1:

6. Применим закон дистрибутивности для подформулы (Aw В):

7. Удалим

Применив закон поглощения, получим А.

Следовательно, в данном высказывании утверждается только то, что Петр поступил в университет, а об Андрее и Семене никакой информации нет.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >