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

1. Отрицание.

Эта логическая операция соответствует в обыденной жизни частице «не».

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

Отрицание высказывания x обозначается и читается не x. Логические значения высказывания модно описать с помощью таблицы, которая называется таблицей истинности:

x
1	0
0	1

Пусть x высказывание. Так как тоже высказывание, то можно образовать отрицание высказывания , то есть высказывание , которое является двойным отрицанием высказывания x. Логические значения высказываний и x совпадают.

2. Дизъюнкция (логическое сложение).

Эта логическая операция соответствует союзу «или».

Определение. Дизъюнкцией двух высказываний x, y называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x или y истинно и ложным, если они оба ложны.

Дизъюнкция высказываний x, y обозначается xy и читается «x или y». Логические значения дизъюнкции описываются таблицей истинности:

x	y	xy
1	1	1
1	0	1
0	1	1
0	0	0

Высказывания x, y называются членами дизъюнкции.

Пример.

x – «5>3», y – «2>4». Тогда xy – «5>3»«2>4» истинно, так как истинно высказывание x.

В алгебре логики союз «или» всегда употребляется в неисключающем смысле. Из определения дизъюнкции и отрицания следует, что высказывание x всегда истинно.

3. Конъюнкция.

Эта логическая операция соответствует союзу «и».

Определение. Конъюнкцией двух высказываний x, y называется новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний x, y обозначается и читается «x и y». Высказывания x, y называются членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей истинности:

x	y
1	1	1
1	0	0
0	1	0
0	0	0

Пример.

x – «6 делится на 2», y – «6 делится на 3». Тогда – «6 делится на 2»«6 делится на 3» истинно.

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

Из определения операций конъюнкции и отрицания следует, что высказывание всегда ложно.

4. Импликация.

Эта логическая операция соответствует словам «если…,то…».

Определение. Импликацией двух высказываний x, y называется новое высказывание, которое считается ложным, если x истинно, а y ложно, и истинным во всех остальных случаях.

Импликация высказываний обозначается x→y и читается «если x, то y» или «из x следует y». Высказывание x называется условием или посылкой, а высказывание y – следствием или заключением. Высказывание x→y называется следованием или импликацией. Логические значения операции импликации описываются следующей таблицей истинности:

x	y	x→y
1	1	1
1	0	0
0	1	1
0	0	1

Пример.

1) x – «12 делится на 6», y – «12 делится на 3». Тогда импликация x→y – «если 12 делится на 6, то оно делится на 3» истинна, так как истинна посылка x, и истинно заключение y.

2) x – «12 делится на 2 и 3», y – «12 делится на 7». Тогда импликация x→y – «если 12 делится на 2 и 3, то оно делится на 7» ложна, так как условие истинно, а заключение ложно.

Употребление слов «если…,то…» в алгебре логики отличается от употребления их в обыденной речи, когда, как правило, считается, что если высказывание x ложно, то высказывание «если x, то y» вообще не имеет смысла. Кроме того, строя предложение «если x, то y» в обыденной речи всегда подразумевается, что предложение y вытекает из предложения x. Употребление слов «если…, то…» в математической логике не требует этого, так как в ней смысл высказываний не рассматривается.

Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «если x, то y». Если при этом известно, что x истинно и доказана истинность импликации x→y то истинно и заключение y. В этом случае пишут xy и говорят, что из x следует y. Это классическое правило вывода постоянно используется в математике.

1. Эквиваленция.

Эта логическая операция соответствует словам «тогда и только тогда, когда».

Определение. Эквиваленцией или эквивалентностью двух высказываний x, y называется новое высказывание, которое считается истинным, если оба высказывания x, y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний x, y обозначается символом x↔y и читается «для того чтобы x, необходимо и достаточно, чтобы y» или «x тогда и только тогда, когда y». Логические значения операции эквиваленции описываются следующей таблицей истинности:

x	y	x↔y
1	1	1
1	0	0
0	1	0
0	0	1

Высказывания x, y называются членами эквиваленции.

Пример.

x – «Треугольник ABC с вершиной A и основанием BC равнобедренный», y – «B=C». Эквиваленция x↔y – «Треугольник ABC с вершиной A и основанием BC равнобедренный тогда и только тогда, когда B=C.» Эквиваленция x↔y истинна, так как высказывания x и y либо одновременно истинны, либо одновременно ложны.

Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в виде необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, делается вывод об истинности или ложности второго члена эквивалентности.