Информатика. 10 класс (Повышенный уровень)

С помощью логических переменных и логических операций любое составное логическое высказывание можно формализовать, т. е. заменить логическим выражением. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу (пример 26.10). Смысл высказываний не учитывается, рассматривается только их истинность или ложность.

В логических выражениях должен соблюдаться следующий порядок выполнения операций (пример 26.11):

1)    действия в скобках;

2)    инверсия;

3)    конъюнкция;

4)    дизъюнкция;

5)    импликация;

6)    эквивалентность.

Значение логического выражения можно определить, построив таблицу истинности для этого выражения. Для построения таблицы истинности необходимо выполнить следующие действия (пример 26.12):

1)    подсчитать число переменных в выражении (n);

2)    подсчитать число логических операций в выражении (p);

3)    установить последовательность выполнения логических операций в выражении с учетом скобок и приоритетов;

4)    вычислить количество столбцов в таблице (n + p);

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

6)    вычислить количество строк в таблице (m = 2ⁿ);

7)    записать в таблице все возможные наборы значений переменных;

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

Для преобразования и упрощения формул в алгебре логики производятся эквивалентные преобразования, опирающиеся на основные логические законы (пример 26.13). Некоторые из этих законов формулируются и записываются так же, как аналогичные законы в арифметике и алгебре, другие выглядят непривычно.

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

Пример 26.14. Упростить логическое выражение  и построить логическую схему, соответствующую результату.

Выполним эквивалентные преобразования выражения в соответствии с законами логики:

1. Импликации.
2. Де Моргана.
3. Инволюции.
4. Дистрибутивности.