Основы компьютерной логики

              Логические законы и правила

преобразования логических выражений

        Логические выражения называются равносильными, если их истинностные значения совпадают при любых значениях, входящих в них логических переменных.   В алгебре логики имеется ряд законов,  позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.

1. Закон двойного отрицания:

 А = .         Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

        — для логического сложения:              А к B = B к A;

        — для логического умножения:          A&B = B&A.

        Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

        В обычной алгебре a + b = b + a,        a Д b = b Д a.

3. Сочетательный (ассоциативный)  закон:

        — для логического сложения:      (A к B) к C = A к (B к C);

        — для логического умножения:   (A&B)&C = A&(B&C).

        При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

        В обычной алгебре:   (a + b) + c = a + (b + c) = a + b + c,

                                             а Д (b Д c) = a Д (b Д c) = a Д b Д c.

4. Распределительный (дистрибутивный) закон:

        — для логического сложения:         (A к B)&C  = (A&C) к (B&C);

        — для логического умножения:      (A&B) к C = (A к C)&(B к C).

        Определяет правило выноса общего высказывания за скобку.

        В обычной алгебре:      (a + b) Д c = a Д c + b Д c.

5. Закон общей инверсии (законы де Моргана):

        — для логического сложения          = & ;

        — для логического умножения:      =  к

 6. Закон идемпотентности ( от латинских слов idem — тот же самый и potens —сильный; дословно — равносильный):

        — для логического сложения:      A к A = A;

        — для логического умножения:    A&A = A.

        Закон означает отсутствие показателей степени.

7. Законы исключения констант:

        — для логического сложения:      A к 1 = 1,      A к 0 = A;

        — для логического умножения:   A&1 = A,     A&0 = 0.

8. Закон противоречия:          A& = 0.

        Невозможно, чтобы противоречащие высказывания были одновременно истинными.

        9. Закон исключения третьего:      A к = 1.

        Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

10. Закон поглощения:

        — для логического сложения:       A к (A&B) = A;

        — для логического умножения:    A&(A к B) = A.

11. Закон исключения (склеивания):

        — для логического сложения:      (A&B) к ( &B) = B;

        — для логического умножения:    (A к B)&( к B) = B.

12. Закон контрапозиции (правило перевертывания):      (A л  B) = (Bл  A).

        Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.

        Пример. Найдите X, если к = В.

Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

( & ) к ( &A)

Согласно распределительному закону для логического сложения:

&( к A)

Согласно закону исключения третьего и закона исключения констант:

&1 =

Полученную левую часть приравняем правой:

*= В

            Окончательно получим, что   X =  .

        Пример 2. Упростите логическое выражение (A к B к C)&

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

Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:

(A к B к C)& = (A к B к C)&( &B& )

Согласно распределительному (дистрибутивному) закону для логического сложения:

(A к B к C)&( &B& ) = (A& ) к (B& ) к (C& ) к (A&B) к (B&B) к (C&B) к (A& ) к (B& ) к (C& )

Согласно закона противоречия:        (A& ) = 0; (C& ) = 0 

 

Согласно закона идемпотентности   (B&B) = B

 

Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:

0 к (A&B) к ( &B) к B к (C&B) к ( &B) к (C& ) к (A& ) к 0

Согласно закона исключения (склеивания)

(A&B) к ( &B) = B

(C&B) к ( &B) = B

Подставляем значения и получаем:

0 к B к B к B к (C& ) к (A& ) к 0

 

Согласно закона исключения констант для логического сложения и закона идемпотентности:

  0 к B к 0 к B к B = B

Подставляем значения и получаем:

B к (C& ) к (A& )

Согласно распределительному (дистрибутивному) закону для логического умножения:

 (C& ) к (A& ) = (C к A)&(C к )&( к A)&( к )

Согласно закона исключения третьего:      (C к ) = 1      ( к A) = 1

 

Подставляем значения и окончательно получаем:     B& & .

 

Наверх

Hosted by uCoz