Формулы алгебры высказываний

Лекция 1. Алгебра высказываний. Логические отношения.

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

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

Раздел предмета «Математическая логика», которые изучаются в данном курсе следующие: 1) алгебра высказываний; 2) булевы функции; 3) исчисление высказываний; 4) предикаты; 5) к-значные логики.

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

Алгебра высказываний (алгебра логики) — раздел математической логики, в котором изучаются логические операции над высказываниями. Любое логическое рассуждение состоит из высказываний. Высказывание – это предложение, которое может быть истинным или ложным. Предложения «8 кратно 3», «19- простое число» являются высказываниями. Предложения «Как доехать до гостиницы?», «Да здравствует математическая логика!» не являются высказываниями.

Высказывание называется тождественно истинным (ложным), если высказывание истинно(ложно) в любой логической ситуации.

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

Все приведенные выше высказывания представляют собой так называемые элементарные высказывания.

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

Элементарные высказывания принято обозначать латинскими буквами

... X, Y, Z.

A, B, C

Конъюнкция. Обозначается A Ù B (A & B, AB), читается: A и B. Получили

сложное высказывание, составленное из двух элементарных. Значение истинности или ложности высказывания, являющегося конъюнкцией двух элементарных высказываний A и B, задается следующей истинностной таблицей 1:

Таблица 1

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

Чаще пользуются более удобным обозначением: «И» - 1, «Л» - 0. В этих обозначениях истинностная таблица конъюнкции будет иметь вид

Таблица 2

Итак, конъюнкция двух элементарных множеств истинна тогда и только тогда, когда оба элементарных высказывания истинны.

Дизъюнкция. Обозначается A Ú B, читается: A или B. При этом разделительный смысл союза «или» исключается. Истинностная таблица

дизъюнкции имеет вид:

Таблица 3

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

Отрицание. Единственная логическая операция, относящаяся к одному высказыванию, - унарная, в отличии от остальных - бинарных. Обозначается: A (Ø A), читается: не A. Истинностная таблица имеет вид:

Таблица 4

A	A

Импликация. Обозначается A ® B (A Ì B), читается: если A, то B. При этом A называют посылкой, B - следствием. Импликация задается следующей истинностной таблице

Импликация ложна тогда и только тогда, когда посылка A истинна, а следствие B - ложь.

Двойная импликация. Обозначается A «B (A ~ B), читается: A тогда и

только тогда, когда B. Задается следующей истинностной таблицей:

Двойная импликация является истинностным высказыванием тогда и только тогда, когда высказывания A и B, ее составляющие, принимают одинаковое значение истинности или ложности.

Пример. Пусть A и B – элементарные высказывания: A – «Этот четырехугольник – параллелограмм», B – «Этот четырехугольник – ромб». Образуем из этих двух элементарных высказываний сложные, используя перечисленные логические связки.

Сложное высказывание A Ù B, очевидно, читается так: «Этот четырехугольник есть параллелограмм и ромб». Значения истинности и

ложности этого высказывания определяется таблицей 2.1.2. Это высказывание считают истинным в том и только в том случае, когда оба высказывания A и B – истинны.

Дизъюнкция указанных высказываний A ∨ B читается: «Этот четырехугольник есть параллелограмм или ромб». Значение истинности и ложности этого высказывания определяется таблицей 2.1.3. Очевидно, для импликации и двойной импликации получим соответственно A ® B: «Если

этот четырехугольник есть параллелограмм, то он – ромб»; A «B «Этот

четырехугольник есть параллелограмм тогда и только тогда, когда он –ромб». Значение истинности или ложности этих высказываний определяется таблицами 2.1.5 и 2.1.6. Отрицание к A, т.е. A, есть высказывание: «Неверно, что этот четырехугольник есть параллелограмм» или «Этот четырехугольник не параллелограмм».

Пользуясь указанными логическими связками, их истинностными таблицами, можно построить сколь угодно сложное высказывание и найти его истинностную таблицу. Заметим, что число строк истинностной таблицы, очевидно, равно 2 ⁿ, где n – число строк равно 4 (таблицы 2.1.2 – 2.1.6).

Формулы алгебры высказываний

Будем пользоваться следующими символами A, B, C... X, Y, Z...

— переменные высказывания, 0, 1, И, Л - const, Ù, Ú, ®, «,

— символы соответствующих логических операций. Дадим определение формулы алгебры высказываний:

1) отдельно стоящая буква A, B, C... X, Y, Z...- формула.

2) если A, B - формулы, то формулами являются и (A), (B), (A Ù B), (A Ú B)

, (A ® B), (A «B).

3) Других формул нет.

Для более компактной записи сложных функций введем следующие соглашения:

1) внешние скобки опускаются;

2) сначала производятся операции в скобках;

3) считается, что приоритет связок убывает в следующем порядке :, (Ù,|,¯),

Ú, (®,Å), «.

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