2_Uproschenie_logicheskikh_vyrazheniy

1. 2. Упрощение логических выражений

Законы логики.
Равносильные преобразования.

2. Понятие равносильности

• Две формулы F и G называются
равносильными, если на любых равных
наборах переменных значения формул
равны.
• Обозначение: F G
Способы проверки:
1.Построение таблиц истинности
2.С помощью законов алгебры логики
2

3. Построение таблиц истинности

Пример: проверить являются ли формулы
эквивалентными с помощью таблиц
истинности
x y z
и
z x z y

4.

5. Основные логические законы

6. Основные логические законы

7. Основные логические законы

8. Основные логические законы

10.

9. Основные логические законы

11.

10. Упрощение выражений с помощью равносильных преобразований

Основные правила:
1.
2.
3.
4.
5.
С помощью законов [10] перейти к формуле,
содержащей только дизъюнкцию, конъюнкцию и
отрицание.
Пользуясь законами [5] и [8] убрать все отрицания не
выше, чем над переменными.
Раскрыть скобки, пользуясь законами [2,3].
Удалить лишние конъюнкции и повторения в
конъюнкциях, используя законы [4-7,11].
Удалить константы с помощью законов [9].

11. Пример 1

Упростить формулу АЛ и выполнить проверку с помощью ТИ
x y x y
Решение.
8
10
x y x y x y y x x y
10
5,8
x y y x x y x y y x x y
11
x y y x x y
x y
11

12. Пример 2

x y z x
Решение.
x y z x x y z x x z
x y z x x z

13. Пример 3

x y z x
Решение.
x y z x x y z x
x y z x x x y x z x
y x z x x y z .
x y z x x y z x

14. Решить самостоятельно

5. x z x y
6. x y x y z
7. x z y x
8. x y z y
4. z y z y x