Логические операции (связки) над множествами

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

1. Дизъюнкция : высказывание (читается: " или ") истинно тогда и только тогда, когда истинно хотя бы одно из высказываний и .

2. Конъюнкция : высказывание (читается: " и ") истинно тогда и только тогда, когда истинны оба высказывания и .

3. Отрицание : высказывание (читается: "не ") истинно тогда и только тогда, когда ложно.

4. Импликация : высказывание (читается: "если , то " или " влечет ") истинно тогда и только тогда, когда истинно высказывание или оба высказывания ложны.

5. Эквивалентность (или равносильность) : высказывание (читается: " , если и только если ") истинно тогда и только тогда, когда оба высказывания и либо одновременно истинны, либо одновременно ложны. Любые два высказывания и , такие, что истинно , называют логически эквивалентными или равносильными.

Записывая высказывания с помощью логических операций, мы предполагаем, что очередность выполнения всех операций определяется расстановкой скобок. Для упрощения записи скобки зачастую опускают, принимая при этом определенный порядок выполнения операций ("соглашение о приоритетах").

Операция отрицания всегда выполняется первой, и потому ее в скобки не заключают. Второй выполняется операция конъюнкции, затем дизъюнкции и, наконец, импликации и эквивалентности. Например, высказывание записывают так: . Это высказывание есть дизъюнкция двух высказываний: первое является отрицанием , а второе — . В отличие от него высказывание есть отрицание дизъюнкции высказываний и .

Например, высказывание после расстановки скобок в соответствии с приоритетами примет вид

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

Равносильность есть не что иное, как "двусторонняя импликация", т.е. равносильно . Это означает, что из истинности следует истинность и, наоборот, из истинности следует истинность .

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

В первых двух столбцах таблицы записывают все возможные наборы значений, которые могут принимать высказывания и . Истинность высказывания обозначают буквой "И" или цифрой 1, а ложность — буквой "Л" или цифрой 0. Остальные столбцы заполняют слева направо. Так для каждого набора значений и находят соответствующие значения высказываний.

Наиболее простой вид имеют таблицы истинности логических операций (табл. 1.1-1.5).

Рассмотрим сложное высказывание . Для удобства вычислений обозначим высказывание через , высказывание через , а исходное высказывание запишем в виде . Таблица истинности этого высказывания состоит из столбцов и (табл. 1.6).