Лекция: ВОПРОС 19

Математические основы информатики

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

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

Алгебра высказываний (булева алгебра)

Основные понятия

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о котором можно сказать, истинно оно или ложно (третьего не дано).

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

Логические операции

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

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

Отрицание — унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ. Это правило можно записать в виде следующей таблицы:

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

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

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

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

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

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, которое ложно только тогда, когда посылка истинна, а заключение ложно, записывается С = А —> В (при этом говорят: из А следует В).

Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из В —> А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

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

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

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

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

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

Логические Выражения.

Порядок логический операций

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

Например,

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