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

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

1.6.1. Алгебра высказываний (булева алгебра) Основные понятия

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

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

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

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

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

A	A
0	1
1	0

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

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

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

A	B	AB
0	0	0
0	1	0
1	0	0
1	1	1

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

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

A	B	AB
0	0	0
0	1	1
1	0	1
1	1	1

Импликацией двух высказыванийA (называетсяпосылкой) иB (называетсязаключением) является новое высказываниеC, которое ложно только тогда, когда посылка истина, а заключение ложно, записываетсяC=AB(при этом говорят, изA следует B). Примером такой операции может быть любое рассуждение типа, если произошло событиеA, то произойдет событиеB, «если идет дождь, то на небе тучи». Очевидно,операция не симметрична, т.е. изBA не всегда истинно, в нашем примере«если на небе тучи, то идет дождь» не всегда истинно.

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

A	B	AB
0	0	1
0	1	1
1	0	0
1	1	1

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

ABBA

AA=1

0A=1

1A=A

A1=1

A0=A

Эквиваленцией двух высказыванийA иB является новое высказываниеC, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записываетсяC=AB (.C=AB)Примером такой операции может быть любое высказывание типа, событиеAравносильно событиюB.

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

A	B	AB
0	0	1
0	1	0
1	0	0
1	1	1

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

AB=BA

AB=BA

A1=A

A0=A