1. Отрицание. Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно. Отрицание высказывания х обозначается  и читается «не х» или «неверно, что х».

Логические значения высказывания  можно описать с помощью таблицы:

х
1	0
0	1

Таблицы такого вида принято называть таблицами истинности.

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

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

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

Конъюнкция высказываний х, у обозначается символом х&у или ( ), читается «х и у». Высказывания х, у называются членами конъюнкции.

Логические значения конъюнкции описываются следующей таблицей истинности:

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

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

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

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

Дизъюнкция высказываний х, у обозначается символом x у, читается «х или у». Высказывания х, у называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:

х	у	x  y
1	1	1
1	0	1
0	1	1
0	0	0

Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».

В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

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

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

Импликация высказываний х, у обозначается символом х → у, читается «если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у - следствием или заключением, высказывание х→у - следованием или импликацией.

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

х	у
1	1	1
1	0	0
0	1	1
0	0	1

Например, высказывание «Если число 12 делится на 6, то оно делится на 3», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

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

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

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

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

Логические значения операции эквиваленции описываются следующей таблицей истинности:

Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P = Q » является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием Р Q равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ P = Q» либо одновременно истинны, либо одновременно ложны.

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

Формулы алгебры логики

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний х, у, z можно построить высказывания: ( x & y ) и х .

Первое из них есть дизъюнкция конъюнкции х, у и отрицания выказывания z, а второе высказывание есть импликация, посылкой которой является высказывание х, а заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z .

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

Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В, С, ...

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

В связи с этим формулы:

  (х&у)   и х

могут быть записаны так:

   и .

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы  в случае, если х = 1, у = 1, z = 0, будет истина, то есть =1.

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

Например, для формулы  таблица истинности имеет вид:

х	у				х&
1	1	0	0	1	0	0
1	0	0	1	0	1	1
0	1	1	0	1	0	0
0	0	1	1	1	0	0

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