8. Математические основы информатики. Алгебра высказываний (булева алгебра). Логические операции. Таблицы истинности.

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

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

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

Операцией отрицания А называют высказывание А (или -А, говорят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно.

А	- А
1	0
0	1

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания, записывается С = А & В

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

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

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

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

А	В	А V В
0	0	0
0	1	1
1	0	1
1	1	1

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

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

А	В	А --> В
0	0	1
0	1	1
1	0	0
1	1	1

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

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

А	В	А <--> В
0	0	1
0	1	0
1	0	0
1	1	1