Основы логики

Как было отмечено ранее, информатика — прикладная наука, находящаяся на стыке многих наук. Вместе с тем она опирается на спектр разделов такой фундаментальной науки, как математика. Наи­более важное прикладное значение для информатики имеют булева(я) алгебра, используемая в разработке алгоритмов программ и в синте­зе цифровых устройств, теория множеств и теория графов, исполь­зуемые в описании различных структур.

Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем как попытка изучения логики мышления математиче­скими методами.

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о кото­ром можно сказать, истинно оно или ложно (третьего не дано). Вы­сказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозна­чим 1). Например, содержание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» все­гда есть ЛОЖЬ. В дальнейшем нас не будет интересовать содержа­тельная часть высказываний, а только их истинность. Два высказы­вания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

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

Элементы.Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и уп­равляющие. Первые производят обработку информации, представ­ленной в бинарной форме; вторые служат для передачи бинарной формы информации; третьи выполняют управляющие функции, генерируя соответствующие сигналы. Во всех случаях в тех или иных точках логических схем сигналы двух различных уровней могут представляться бинарными символами {0,1} или логически­ми значениями {Истина (True), Ложь (False)}. Поэтому множество элементов булевой алгебры выбирается бинарным В - {0,1}, а сама алгебра называется бинарной, или переключательной. Ее элемен­ты называются константами, или логическими 0 и 1, которым в ряде случаев соответствуют бинарные цифры, в других случаях — логи­ческие значения, соответственно ложь (False) и истина (True). В дальнейшем для обозначения булевых переменных будем исполь­зовать буквы латинского алфавита — х, у, г... Набор переменных х, у, z... может рассматриваться как n-разрядный двоичный код, раз­рядами которого являются эти переменные.

Операции.Основными, или базовыми, операциями булевой ал­гебры служат (табл. 3.1): И (AND), ИЛИ (OR) и НЕ (NOT). Опе­рация И называется логическим умножением, или конъюнкцией, и обозначается знаком умножения {•, Ù}. Операция ИЛИ называется логическим сложением, или дизъюнкцией, иобозначается знаком сложения {+, Ú}. Операция НЕ называется логическим отрицани­ем, или инверсией (дополнением), и обозначается знаком {—, }.

Таблица 3.1 Базовые логические операции

При выполнении операций применяются отношение эквивалент­ности «=» и скобки «( )», которые определяют порядок выполне­ния операций. Если скобок нет, то операции выполняются в следу­ющей последовательности: логическое отрицание, логическое умножение и логическое сложение.

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

Операцией отрицания А называют высказывание Ā (или -А, го­ворят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «зав­тра будет снег», то Ā «завтра НЕ будет снега», истинность одного утверждения автоматически означает ложность второго. Отрица­ние - унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ.

Это правило можно записать в виде следующей таблицы:

Такая таблица называется таблицей истинности.

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, ког­да истинны оба высказывания, записывается С = А Ù В или С = А & В (при этом говорят С равно А и В). Примером такой операции может быть следующая: пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ши­рина шкафа меньше ширины двери И высота шкафа меньше высо­ты двери», т.е. данная операция применяется, если два высказыва­ния связываются союзом И.

Таблица истинности этой операции, как следует из определения, имеет вид

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A Ú В (при этом говорят: С равно А ИЛИ В). Пример такой операции следующий: пусть вы­сказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на трол­лейбусе», событие С «студент добрался домой на автобусе ИЛИ трол­лейбусе», т.е. данная операция применяется, если два высказывания связываются союзом ИЛИ.

Таблица истинности такой операции следующая:

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, кото­рое ложно только тогда, когда посылка истинна, а заключение лож­но, записывается С = А ® В (при этом говорят: из А следует В). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из В ® А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

Таблица истинности импликации следующая:

Импликация имеет следующие свойства:

А→В ¹ В → А

А→ А= 1

0 →А= 1

1 → А = А

А→ 1 = 1

А→ 0 = А

Эквиваленцией двух высказываний А и В является новое выска­зывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А « В (С = А º В). Примером такой операции может быть любое выска­зывание типа: событие А равносильно событию В.

Таблица истинности:

Эквиваленция имеет следующие свойства:

А↔ В = В ↔ А

А ↔ = ↔Ā

А↔ 1 = А

А ↔ 0 = Ā

С помощью логических операций из простых высказываний (ло­гических переменных и констант) можно построить логические вы­ражения, которые также называются булевскими функциями. Напри­мер, С = ((A Ú В) → В) Ú А.

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

Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.

Зависимости между логическими операциями

Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истин­ности следующие равносильности:

Законы алгебры логики

1. Закон двойного отрицания

2. коммутативный закон для конъюнкции

3. коммутативный закон для дизъюнкции

4. ассоциативный закон для конъюнкции

5. ассоциативный закон для дизъюнкции

6. дистрибутивные законы

7.

8. законы де Моргана

9.

10. закон идемпотенции для конъюнкции

11. закон идемпотенции для дизъюнкции

12. закон единицы для конъюнкции

13. закон нуля для конъюнкции

14. закон единицы для дизъюнкции

15. закон нуля для дизъюнкции

16. закон исключения третьего

17. закон противоречия

18.

19.

20. законы поглощения

21.

22.

23.

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

Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет вид A_l Ú A₂ Ú ... Ú A_n, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например:

В = (А₁ & А₂ & A₃) Ú (А₄ & А₅).

Вторая - конъюнктивная нормальная форма (КНФ), имеет вид А₁ Ù А₂ Ù ... Ù A_n, где каждое из составляющих есть дизъюнк­ция простых высказываний и их отрицаний, например:

В = (A_l ÚА₂ ÚA₃) & (А₄ Ú А₅) & А₆.