В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы. 1. Закон двойного отрицания: А= Двойное отрицание исключает отрицание. 2. Переместительный (коммутативный) закон: — для логического сложения: A B = B A — для логического умножения: А&В = В&А Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания. В обычной алгебре а + b = b + a, axb = bха. 3. Сочетательный (ассоциативный) закон: — для логического сложения: (A B) C= A (B C) — для логического умножения: (А&В)&С = А&(В&С) При одинаковых знаках скобки можно ставить произвольно или вообще опускать. В обычной алгебре (а + b) + с = а + (b + с) = а + b + с, а х (b х с) = а х (b х с) = а х b x с. 4. Распределительный (дистрибутивный) закон: — для логического сложения: (A B)&C = (A&C) (B&C); — для логического умножения: (А&В) C = (A C)&(B C). Определяет правило выноса общего высказывания за скобку. В обычной алгебре (а + b) хс = ахс + bхс. 5. Закон общей инверсии (законы де Моргана): — для логического сложения A В = ; для логического умножения: = 6. Закон равносильности — для логического сложения: A A=A; — для логического умножения: А&А =А. Закон означает отсутствие показателей степени. 7. Законы исключения констант: —для логического сложения: A l=l, A O = A; — для логического умножения: A&1 = А, А&О = 0. 8. Закон противоречия: А& =0 Невозможно, чтобы противоречащие высказывания были одновременно истинными. 9. Закон исключения третьего: A = 1 Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано. 10. Закон поглощения: — для логического сложения: A (A&B) =А; — для логического умножения: A&(A B)= A. 11. Закон исключения (склеивания): — для логического сложения: (A&B) ( &B) = В — для логического умножения: (A B)&( B) =B Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут. Пример 1. Пусть нам необходимо упростить логическое выражение: (А &. В) + (A & ¬В). 1.Воспользуемся правилом дистрибутивности и вынесем за скобки А: (А & В) + (А & ¬В) = А & (В + ¬В). 2.По закону исключенного третьего В + ¬В = 1, следовательно: А & (В + ¬B) = А & 1 = А. Пример 2. Пусть нам необходимо упростить логическое выражение: ¬(A +¬B)+¬(A+ B)+ A & B 1. сначала раскрываем инверсию сложных выражений, используя законы де Моргана: ¬(A +¬B)+¬(A+ B)+ A & B=¬A&B + ¬A&¬B + A& B 2. выносим за скобки в первых двух слагаемых и используем закон исключения третьего В + ¬В = 1: ¬A&B + ¬A&¬B + A& B=¬A&(B+¬B)+A&B=¬A+A&B 3. наконец, применяем распределительный закон для операции «И» и еще раз закон исключения третьего A+ ¬A = 1, следовательно: ¬A+A&B=(¬A+A)&(¬A+B)=¬A+B Пример 3. Пусть нам необходимо упростить логическое выражение: (А + В) & (А + С). Раскроем скобки: (А + В) & (А + С) = A & A + A & C + B & A + B & C; Так как A & A =A, следовательно, A & A + A & C + B & A + B & C = A + A & C + B & A + B & C; В высказываниях А и А & C вынесем за скобки А и используя свойство А + 1= 1, получим A + A & C + B & A + B & C = A & (1 + C) + B & A + B & C = A + B & A + B & C; Аналогично предыдущему пункту вынесем за скобки высказывание А. A + B & A + B & C = A & (1 + B) + B & C = A + B & C. |