3. Логические операции
3.1. Основные понятия
Математическая логика изучает различные способы построения логических рассуждений, т.е. исследует соотношения между основными понятиями математики, на базе которых доказываются математические утверждения. Начальным разделом математической логики является алгебра высказываний.
Высказыванием
называется повествовательное предложение,
о котором можно сказать истинно оно или
ложно. Возможность одновременной
истинности и ложности высказывания в
классической математической логике
исключается. Высказывания обозначают
прописными буквами латинского алфавита
A, B,
Х, P, Q
и т.д. Например, предложения
«Воронеж - столица России» и
«семь – простое число» являются
высказываниями, причем первое высказывание
оказалось ложным, а второе – истинным.
На высказывание можно смотреть как
на величину, которая может принимать
только одно из двух значений: «истина»
(другие варианты: «И», «1»)
или «ложь» (другие варианты: «Л», «0»). В
логике высказываний главное – не
содержание высказывания, а его истинность
или ложность.
Высказывания, верные в одних ситуациях и ложные в других ситуациях, называются переменными высказываниями.
Множество
или
называется множеством
истинностных значений.
Использование 0 и 1 позволяет развить
алгебру высказываний в виде двоичной
(булевой) алгебры, заданной на множестве
элементов: 0 и 1. Переменные, принимающие
значения на множестве 0 и 1, называются
булевыми переменными.
3.2. Простейшие связки (операции)
Алгебра высказываний изучает различные способы сочетания отдельных высказываний для построения новых высказываний. Эти новое высказывание называется составным, в то время как высказывания, из которых они образованы, называются простыми (элементарными) составляющими, компонентами, «пропозициональными переменными». Любое высказывание, даже такое, которое на самом деле является сложным, может быть использовано в качестве одного из простых составляющих какого-то другого составного высказывания.
Значение истинности составного высказывания определяется значениями истинности его компонент.
Формулой высказывания называется выражение, составленное из простых высказываний с помощью операций над высказываниями и скобок, обращающееся в конкретное высказывание при подстановке вместо переменных высказываний конкретных высказываний.
Среди операций над компонентами основными считаются дизъюнкция, конъюнкция, отрицание, импликация, эквивалентность.
Дизъюнкцией (логической суммой,
операцией «ИЛИ») высказываний
и
называется высказывание, обозначаемое
,
ложное, когда оба высказывания ложны,
и истинное во всех других случаях.
Дизъюнкция, например, может быть
использована для записи логической
формулы высказывания «идет
дождь или снег». В качестве простых
высказываний используются высказывания
=«идет
дождь»,
=«идет
снег». Высказыванию «идет дождь или
снег» соответствует формула
.
Действие всех логических операций удобно иллюстрируется с помощью таблиц истинности. В частности, дизъюнкции высказываний соответствует следующая таблица истинности:
Таблица 1.
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Например, имеются два высказывания P=«два - делитель пяти» и Q=«шесть - простое число». Дизъюнкция данных высказываний является ложным высказыванием.
Конъюнкцией (логическим произведением,
операцией «И») высказываний
и
называется высказывание, обозначаемое
,
истинное, когда оба высказывания истинны,
и ложное во всех других случаях. Конъюнкции
соответствует следующая таблица
истинности:
Таблица 2.
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Например, имеются два высказывания P= «дважды два четыре» и Q= «регистрация фирмы требует наличия устава». Конъюнкция данных высказываний является истинным высказыванием.
Отрицанием (инверсией)
высказывания
называется высказывание
,
ложное при истинности высказывания
и истинное при ложности высказывания
.
Таблицы истинности для отрицания имеет
вид:
Таблица 3.
-
0
1
1
0
Импликацией (логическим
следованием) двух высказываний
и
называется высказывание
,
ложное, когда
истинно, а
ложно. Во всех других случаях высказывание
истинно. Таблица истинности для импликации
имеет вид:
Таблица 4.
-
0
0
1
0
1
1
1
0
0
1
1
1
В разговорной речи импликация высказываний соответствует составлению высказывания вида: «из следует », «если , то », « достаточно для », « необходимо для », « тогда, когда ». Высказывание называется посылкой импликации, а высказывание - заключением.
Пример 3.1. Представить
логической формулой высказывание: «Если
идет дождь, то деревья мокрые». Высказывание
- «идет дождь», высказывание
- «деревья мокрые». Высказыванию «Если
идет дождь, то деревья мокрые» соответствует
формула
.
Импликация двух высказываний несимметрична. Действительно, P→Q не соответствует высказыванию Q→P. Высказывание Q→P называется конверсией высказывания P→Q. Многие из наиболее распространенных ошибок в рассуждениях происходят от смешивания какого – либо высказывания с его конверсией. Интересно поэтому рассмотреть те импликации, которые могут быть образованы из высказываний P и Q.
В таблице истинности представлены четыре импликации и их названия.
Таблица 5.
P |
Q |
|
|
Импликация
|
Конверсия импликации Q→P |
Конверсия контрапози-
ции
|
Контра-
позиция
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Из таблицы
видно, что P→Q
эквивалентно
.
Последнее называется контрапозицией
первого. Контрапозиция является удобной
формой импликации во многих рассуждениях.
Аналогичное высказывание
представляет собой конверсию контрапозиции.
Так как контрапозиция эквивалентна
,
то конверсия этой контрапозиции
эквивалентна конверсии этой импликации.
Эквивалентностью высказываний
и
называется высказывание
,
которое истинно тогда и только тогда,
когда
и
оба истинны или оба ложны(когда
истинностные значения высказываний Х
и Y совпадают).
Таблица истинности для эквивалентности имеет вид:
Таблица 6.
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
В разговорной речи эквивалентность двух высказываний соответствует составлению нового высказывания вида «Х эквивалентно Y», «Х тогда и только тогда, когда Y», «Х необходимо и достаточно для Y».
Для образования
составных высказываний наряду с единичным
использованием каждой основной связки
можно пользоваться основными связками
многократно, получая более сложные
составные высказывания - аналогично
тому, как с помощью основных арифметических
операций образуются сложные алгебраические
выражения. Например, составными будут
высказывания: (
);
;
.
Порядок прочтения составных выражений при наличии скобок соответствует принципу «изнутри наружу», подобно алгебраическим выражениям, в которых сначала группируются величины, заключенные в самые внутренние скобки, затем эти скобки в с вою очередь группируются и т.д.. Если скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Каждое составное высказывание имеет свою таблицу истинности, которая может быть построена стандартным образом.
Пример 3.2. Записать логической формулой сложное высказывание « Если поздно ложишься спать и при этом пьешь много кофе, то утром присыпаешься в плохом настроении или с головной болью».
Составное
высказывание состоит из простых
высказываний:
«поздно ложишься спать»,
«пьешь много кофе»,
«утром просыпаешься в плохом настроении»,
«утром встаешь с головной болью». Сложное
высказывание « Если поздно ложишься
спать и при этом пьешь много кофе, то
утром присыпаешься в плохом настроении
или с головной болью» записывается
формулой
.