§ 26. Алгебра логики

Процессор компьютера выполняет арифметические и логические операции над двоичными кодами.

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

Для понимания принципа работы таких элементов рассмотрим основные понятия алгебры логики.

Аналогию между алгеброй и логикой положил в основу своего логического учения основоположник алгебры логики английский математик и логик Дж. Буль (1815–1864).

Любое высказывание Буль записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов.

Современная алгебра логики является разделом математической логики и изучает логические операции над высказываниями с точки зрения их истинностного значения.

Истинность или ложность высказываний зависит от истинности и ложности исходных (простых) высказываний и смысла логических операций над высказываниями (пример 26.1). Таким образом, определение истинности некоторого логического выражения — это определение значения некоторой логической функции.

Способы задания логической функции:

1)    словесное описание;

2)    таблица истинности;

3)    формула, записанная с помощью букв, знаков логических операций и скобок;

4)    комбинационная схема, составленная из логических элементов;

5)    координатный способ (карта Карно);

6)    диаграмма Венна (Эйлера).

(Рассмотрите пример 26.2.)

Области применения алгебры логики:

1)    в качестве средства алгоритмического описания в языках программирования для определения логических условий;

2)    для формирования логических высказываний в математической логике, лингвистике, теории искусственного интеллекта;

3)    в разработке и описании дискретных технических систем;

4)    при анализе и синтезе логических устройств.

Рассмотрим основные логические операции — варианты обозначения (пример 26.3), таблицы истинности и логические элементы для каждой из логических операций (примеры 26.4 — 26.9).

Логическое отрицание, или инверсия (лат. inversion — переворачивание), — логическая операция, которая меняет значение исходного высказывания на противоположное.

Инверсия — унарная логическая операция, т. к. выполняется относительно одного высказывания (пример 26.4).

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

Логическое умножение, или конъюнкция (лат. conjunctio — соединение), — операция, соединяющая два или более высказываний при помощи логической связки ИЛИ. Результат операции может быть истинным только в том случае, если одновременно истинны исходные высказывания (пример 26.5).

Логическое сложение, или дизъюнкция (лат. disjunction — разделение), — операция, соединяющая два или более высказываний при помощи логической связки ИЛИ. Результат операции будет истинным, если истинно хотя бы одно из исходных высказываний (пример 26.6).

Дизъюнкция строгая (сложение по модулю два) — операция, соединяющая два высказывания ( А и В)  при помощи логической связки ИЛИ, употребленной в исключающем смысле, и читается: «либо , либо ». Результат операции будет истинным, если истинно только одно из исходных высказываний (пример 26.7).

Логическое следование, или импликация (лат. implisito — тесно связываю), — операция, соединяющая два высказывания (А и В), из которых первое является условием, а второе — следствием из этого условия. Читается: «Если А, то В», «А влечет В», «Из А следует В». Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь (пример 26.8).

С помощью логических переменных и логических операций любое составное логическое высказывание можно формализовать, т. е. заменить логическим выражением. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу (пример 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. Дистрибутивности.

1. Что изучает алгебра логики?

2. Какими объектами оперирует алгебра логики?

3. Какие значения могут принимать объекты алгебры логики?

4. Какими способами можно отразить логическую функцию?

5. Какая логическая операция является унарной? Почему? В чем ее смысл?

6. В каком случае результатом конъюнкции будет истина?

7. В каком случае результатом дизъюнкции будет ложь?

8. В чем разница между дизъюнкцией и строгой дизъюнкцией?

9. Как выполняется импликация? Приведите примеры.

10. В каких случаях результатом эквивалентности будет истина? Приведите примеры.

11. В виде каких логических элементов реализованы логические операции: инверсия, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация, эквивалентность?

12. Что такое логическое выражение? В чем состоит формализация составного логического высказывания?

13. По каким правилам строится таблица истинности для логического выражения?

14. Для чего в алгебре логики используются эквивалентные преобразования логических формул?

15. Какие законы используются при эквивалентных преобразованиях логических формул?

16. Каких логических операций достаточно для представления любой логической функции?