Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

Отрицанием (инверсией) высказывания называется высказывание , ложное при истинности высказывания и истинное при ложности высказывания . Таблицы истинности для отрицания имеет вид:

Таблица 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 эквивалентно . Последнее называется контрапозицией первого. Контрапозиция является удобной формой импликации во многих рассуждениях. Аналогичное высказывание представляет собой конверсию контрапозиции. Так как контрапозиция эквивалентна , то конверсия этой контрапозиции эквивалентна конверсии этой импликации.

Эквивалентностью высказываний и называется высказывание , которое истинно тогда и только тогда, когда и оба истинны или оба ложны(когда истинностные значения высказываний Х и Y совпадают).

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

Таблица 6.

В разговорной речи эквивалентность двух высказываний соответствует составлению нового высказывания вида «Х эквивалентно Y», «Х тогда и только тогда, когда Y», «Х необходимо и достаточно для Y».

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

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

Пример 3.2. Записать логической формулой сложное высказывание « Если поздно ложишься спать и при этом пьешь много кофе, то утром присыпаешься в плохом настроении или с головной болью».

Составное высказывание состоит из простых высказываний: «поздно ложишься спать», «пьешь много кофе», «утром просыпаешься в плохом настроении», «утром встаешь с головной болью». Сложное высказывание « Если поздно ложишься спать и при этом пьешь много кофе, то утром присыпаешься в плохом настроении или с головной болью» записывается формулой

.

3.3. Другие связки (операции)

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

Штрих Шеффера, или антиконъюнкция обозначается │ и соответствует связке . Таблица истинности штриха Шеффера имеет вид:

Таблица 7.

		│
0	0	1
0	1	1
1	0	1
1	1	0

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

Таблица 8.

0	0	1
0	1	0
1	0	0
1	1	0

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