1. Основы математической логики

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

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

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

Обозначать высказывания будем большими буквами. Если высказывание А истинное, то будем писать "А = 1" и говорить: "А - истинно". Если высказывание Х ложно, то будем писать "Х = 0" и говорить "Х - ложно".

Примеры

А = "Солнце светит для всех." = 1 - истинное высказывание

Б = "Все студенты любят информатику" , Б= 0 - ложное высказывание

В = "А ты любишь информатику?" - не высказывание, т.к. не является повествовательным предложением.

Г = "2 * Х - 5 > 0" - не высказывание, т.к. для некоторых значений Х это выражение будет верным, а для других - нет.

В алгебре логики над высказываниями можно производить различные операции (как и в алгебре действительных чисел определены операции сложения, деления, возведения в степень)

1.2. Основные логические операции

1. Логическое отрицание (инверсия) – образуется из исходного высказывания с помощью добавления частицы НЕ к сказуемому или использованием оборота речи «неверно. что…»

Примеры.

Высказывание А: «у меня есть игровая приставка»

Инверсия А: «У меня нет игровой приставки»

Инверсия обозначается : не А; ¬А; not A, .

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

таблица 1

таблица истинности инверсии

А		Читается
0	1	если А ложно, то не А истинно
1	0	если А истинно, но не А ложно

Примечание. Дважды или четырежды отрицавшееся высказывание имеет то же самое значение истинности, что и соответствующие не отрицавшееся высказывание, трижды отрицавшееся – что и отрицавшееся один раз.

2. Логическое умножение (конъюнкция)-образуется соединением двух высказываний в одно с помощью союза «И».

Пример. Допустим, из окна видна автостоянка, на которой обычно стоят машины двух марок: «Мерседес» и «Жигули», но может находиться и какая-то одна из них, или не быть ни одной. Обозначим высказывания:

А = На автостоянке стоит «Мерседес»

В = На автостоянке стоят «Жигули»

А конъюнкция В = На автостоянке стоят «Мерседес» и «Жигули»

Операция конъюнкции обозначается: Λ; &; *; and; и.

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

Таблица 2

Таблица истинности конъюнкции

А	B	AΛB	Пояснение	Стоят “Мерседес” и “Жигули”
0	0	0	“Мерседес” не стоит, “Жигули” не стоят	ЛОЖЬ
0	1	0	“Мерседес” не стоит, “Жигули” стоят	ЛОЖЬ
1	0	0	“Мерседес” стоит, “Жигули” не стоят	ЛОЖЬ
1	1	1	“Мерседес” стоит, “Жигули” стоят	ИСТИНА

3. Логическое сложение (дизъюнкция) образуется соединением двух высказываний в одно с помощью союза ИЛИ. Дизъюнкция обозначается: А или В; А OR В; А|В; А V В.

Пример. Допустим, из окна видна автостоянка, на которой обычно стоят машины двух марок: «Мерседес» и «Жигули», но может находиться и какая-то одна из них, или не быть ни одной. Обозначим высказывания:

А = На автостоянке стоит «Мерседес»

В = На автостоянке стоят «Жигули»

А дизъюнкция В = На автостоянке стоят «Мерседес» или «Жигули»

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

Таблица 3

таблица истинности дизъюнкции

А	B	AVB	Пояснение	Стоят “Мерседес” или “Жигули”
0	0	0	“Мерседес” не стоит, “Жигули” не стоят	ЛОЖЬ
0	1	1	“Мерседес” не стоит, “Жигули” стоят	ИСТИНА
1	0	1	“Мерседес” стоит, “Жигули” не стоят	ИСТИНА
1	1	1	“Мерседес” стоит, “Жигули” стоят	ИСТИНА

Примечание: дизъюнкция – это логическое сложение, очевидно,

0 + 0 = 0,

0 + 1= 1,

1 + 0 = 1,

но в логике: 1 V 1 = 1.

4. Логическое следование (импликация) – образуется соединением двух высказываний в одно с помощью оборота речи «ЕСЛИ …, ТО…»

Говорят: «Если А, то В», «А имплицирует В», «А влечет В», «В следует из А».

5. Логическое равенство (эквивалентность) – образуется соединением двух высказываний в одно при помощи оборота речи «… ТОГДА И ТОЛЬКО ТОГДА, КОГДА …». Например:

“Две прямые параллельны тогда и только тогда, когда они не пересекаются”

Эквивалентность обозначается: А = В; А ~ В

При изучении высшей математики читатель сталкивался с утверждениями, названными критериями. Эти утверждения есть, также, суть эквивалентные высказывания.

Пример. Пусть даны два высказывания:

А = “Число делится на 3 без остатка (кратно трём)”

В = “Сумма цифр числа делится нацело на 32”.

А эквивалентно В = «Число делится на 3 без остатка тогда и только тогда, когда сумма цифр данного числа делится нацело на 3».