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

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

2 Законы алгебры логики ¬0=1 ¬1=0 1. ЗАКОН ИСКЛЮЧЕНИЯ КОНСТАНТ X ۷ 1 = 1 X ۷ 0 = X X ٨ 1 = X X ٨ 0 = 0

3 Законы алгебры логики 2. ЗАКОН ДВОЙНОГО ОТРИЦАНИЯ ¬¬X = X 3. ЗАКОН ПРОТИВОРЕЧИЯ X ٨ ¬X = 0 4. ЗАКОН ИСКЛЮЧЕНИЯ ТРЕТЬЕГО X ۷ ¬X = 1

4 Законы алгебры логики 5. КОММУТАТИВНЫЙ ЗАКОН X ۷ Y = Y ۷ X X ٨ Y = Y ٨ X 6. АССОЦИАТИВНЫЙ ЗАКОН (X ۷ Y ) ۷ Z = X ۷ (Y ۷ Z) (X ٨ Y) ٨ Z = X ٨ (Y ٨ Z) 7. ДИСТРИБУТИВНЫЙ ЗАКОН (X ۷ Y) ٨ Z = (X ٨ Z) ۷ (Y ٨ Z) (X ٨ Y) ۷ Z = (X ۷ Z) ٨ (Y ۷ Z)

5 Законы алгебры логики 8. ЗАКОН де МОРГАНА ¬(X ۷ Y) = ¬X ٨ ¬Y ¬(X ٨ Y) = ¬X ۷ ¬Y 9. ЗАКОН ИДЕМПОТЕНТНОСТИ X ۷ X = X X ٨ X = X

6 Законы алгебры логики 10. ЗАКОН ПОГЛОЩЕНИЯ X ۷ (X ٨ Y) = X X ٨ (X ۷ Y) = X 11. ЗАКОН СКЛЕИВАНИЯ (X ٨ Y) ۷ (¬X ٨ Y) = Y (X ۷ Y) ٨ (¬X ۷ Y) = Y X ۷ (¬X ٨ Y) = X ۷ Y X ٨ (¬X ۷ Y) = X ٨ Y 13. ЗАКОН КОНТРАПОЗИЦИИ (X Y) = (Y X)

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

8 Докажем закон склеивания (X ٨ Y) ۷ (¬X ٨ Y) = Y табличным способом: Ответ: результирующие столбцы совпали, значит закон склеивания доказан. XYX ٨ Y¬X¬X¬X ٨ Y(X ٨ Y) ۷ (¬X ٨ Y)Y

9 Докажем закон склеивания (X ٨ Y) ۷ (¬X ٨ Y) = Y аналитическим способом: Упростим левую часть, для этого вынесем Y за скобку, используя дистрибутивный закон (X ۷ Y) ٨ Z = (X ٨ Z) ۷ (Y ٨ Z) (X ٨ Y) ۷ (¬X ٨ Y) = (X ۷ ¬X) ٨ Y = > В скобке по закону исключения третьего X ۷ ¬X = 1 получаем 1. => 1 ٨ Y = Y Левая и правая части совпали, т.е. Y=Y. Чтд.