Логические операции над высказываниями

Стр 1 из 8Следующая ⇒

Значение истинности составного высказывания определяется значениями истинности его компонент. Высказывания будем обозначать прописными буквами латинского алфавита X, Y, Z ....

Составные высказывания будем получать из простых с помощью логических операций: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность, которые осуществляются при помощи логических связок: ‾ ; Наименования и обозначения логических операций представлены в таблице 1.1.

Таблица 1.1 – Обозначение логических операций

Название	Прочтение	Обозначение
Отрицание	не	‾
Конъюнкция	и
Дизъюнкция	или	∨
Импликация	если…то	→
Эквивалентность	тогда и только тогда, когда	↔

При рассмотрении той или иной связки мы хотим знать, каким именно образом истинность составного высказывания, порожденного этой связкой, зависит от истинности его компонент. Очень удобно изображать эту зависимость, пользуясь таблицами истинности, которые называются также интерпретациями логических операций. Каждой строке таблицы истинности взаимно однозначно соответствует набор составляющих высказываний и соответствующее значение составного высказывания. Наборы из нулей и единиц, соответствующих составляющим высказываниям, в каждой строке таблицы истинности имеют стандартное расположение, т.е. расположены в лексикографическом порядке (порядке возрастания).

Пусть даны два произвольных высказывания X и Y.

Отрицанием высказывания X называется высказывание , которое истинно, когда X ложно, и ложно, когда X истинно.

Таблица истинности для отрицания.

X

Конъюнкцией двух высказываний X и Y называется высказывание X Y, которое истинно только в том случае, когда X и Y оба истинны.

Таблица истинности для конъюнкций.

X	Y	X Y

Дизъюнкцией двух высказываний X и Y называется высказывание X Y, которое истинно, когда хотя бы одно из них истинно.

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

X	Y	X Y

Импликацией двух высказываний X и Y называется высказывание X → Y, которое ложно тогда и только тогда, когда X истинно, а Y ложно.

Таблица истинности для импликации.

X	Y	X → Y

Эквивалентностью высказываний X и Y называется высказывание X ↔ Y, которое истинно тогда и только тогда, когда X и Y оба истинны или ложны.

Таблица истинности для эквивалентности.

X	Y	X ↔ Y

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

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

Их следует читать «изнутри наружу», подобно алгебраическим выражениям, в которых сначала группируются величины, заключенные в самые внутренние скобки, затем эти скобки в свою очередь группируются и т. д. Если скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Каждое составное высказывание имеет свою таблицу истинности, которая может быть построена стандартным образом.

Новые высказывания могут быть образованы при помощи нескольких логических операций и составлять формулы, некоторые из которых рассматриваются как логические операции, осуществляемые при помощи других логических связок:

Название	Прочтение	Обозначение
Штрих Шеффера	Антиконъюнкция	∣
Стрелка Пирса	Антидизъюнкция	↓
Сумма по модулю два	Антиэквивалентность	⊕

Штрих Шеффера, X ∣ Y или антиконъюнкция, по определению .

Таблица истинности штриха Шеффера.

X	Y	X ∣ Y

Стрелка Пирса, или антидизъюнкция, по определению .

Таблица истинности стрелки Пирса.

X	Y	X ↓ Y

Сумма по модулю два, или антиэквивалентность, по определению .

Таблица истинности суммы по модулю два.

X	Y	X ⊕ Y

Заметим, что таблицы истинности логических операций содержат 2^пстрок, где п — число простых высказываний.

Логические отношения

Иногда бывает желательно рассмотреть взаимоотношение двух высказываний. Наиболее интересное из таких отношений имеет место, когда из одного высказывания логически следует другое. Если из X следует Y, мы говорим также, что Y является следствием X или что Y логически выводимо из X. Исходя из анализа логических возможностей для пары высказываний X и Y, отношение следствия можно охарактеризовать таким образом: из X следует Y, если Y истинно всякий раз, когда истинно X, т. е. если Y истинно во всех логически возможных случаях, в которых X истинно.

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

Следующая таблица иллюстрирует этот метод:

X	Y	X ↔ Y	X → Y	X ∨ Y

Высказывание X ↔ Y истинно в первом и четвертом случаях и в обоих этих случаях истинно также высказывание X → Y. Мы видим, что из Х ↔ Y следует высказывание X → Y. Сравнение двух последних столбцов показывает, что из высказывания X → Y не следует X ∨ Y, из X ∨ Y не следует X → Y.

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

Из следующей таблицы истинности видно, что X → Y эквивалентно .

X	Y	X → Y

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

Варианты импликации

Импликация двух высказываний отличается от эквивалентности, а также от дизъюнкции и конъюнкции тем, что она несимметрична. Так X ∨ Y эквивалентно Y ∨ X; X ∧ Y эквивалентно Y ∧ X; X ↔ Y эквивалентно Y ↔ X, но X → Y не эквивалентно Y → X. Высказывание Y → X называется конверсией высказывания X → Y. Многие из наиболее распространенных ошибок в рассуждениях происходят от смешивания какого-либо высказывания с его конверсией. Интересно поэтому рассмотреть те импликации, которые могут быть образованы из высказываний X и У.

В таблице истинности представлены четыре импликации и их названия.

X	Y	X → Y	Y → X

Из таблицы видно, что X → Y эквивалентно . Последнее называется контрапозицией первого. Контрапозиция является удобной формой импликации во многих рассуждениях. Аналогично, высказывание представляет собой конверсию контрапозиции. Так как контрапозиция эквивалентна , то конверсия этой контрапозиции эквивалентна конверсии этой импликации.

С импликацией связано постоянное упоминание математиками «необходимое условие» и «достаточное условие».

X является достаточным условием для Y	Если имеет место X, то Y также будет иметь место	Импликация X → Y
X является необходимым условием для Y	Если имеет место Y, то X также будет иметь место	Конверсия достаточного условия X → Y
X является необходимым и достаточным условием для Y	X имеет место, если и только если имеет место Y	Двойная импликация X ↔ Y эквивалентность

12 3 4 5 6 7 8 Следующая ⇒