Элементарные высказывания обозначаются строчными буквами латинского алфавита: а, b, p, q и т.д. Из высказываний с помощью логических связок образуются новые высказывания. Истинность или ложность высказываний, полученных в результате логических операций над другими, зависит от истинности или ложности исходных высказываний, а также от характера производных логических операций. По аналогии с арифметической ( например, таблицы умножения и сложения) в алгебре высказываний также существуют таблицы истинности тех или иных логических операций, которыми они и определяются.
Первой из простейших логических операций является отрицание, выражаемое словесно частицей “не”.
Отрицанием некоторого высказывания р называется такое высказывание ( читается “не р” ), которое истинно, если данное высказывание ложно, и ложно, если данное высказывание истинно ( рис.1 )
Рис. 1
Например: 1) р: ( 6 делится на 3 ) – истинно, : ( 6 не делится на 3 ) – ложно.
Обозначим цифрой 1 – истинность, а цифрой 0 – ложность некоторого высказывания. Тогда, определение отрицания можно выразить следующей таблицей ,которую называют таблицей истинности ( табл. 1 )
Табл. 1
р
Табл. 2
р
q
Теперь можно познакомиться и с простейшими законами логики высказываний. Высказывание = р таково, что оба составляющие его высказывания и р одновременно истинны или одновременно ложны. Они имеют одно и тоже значение истинности, т.е. эквивалентны. Равенство = р выражает один из законов логики высказываний – закон двойного отрицания, позволяющее заменять сложное высказывание простым р.
Конъюнкцией ( логическим умножением ) двух высказываний р и q называется такое высказывание ( читается р и q ), которое истинно тогда и только тогда ,когда истинны оба составляющих его высказывания ( рис. 2 )
Конъюнкция нескольких высказываний в математических утверждениях часто выражается:
а). принадлежность двух или нескольких признаков одному объекту ( например, число 12 делится на 2, и на 3, и на 4, и на 6, и на 12 );
б). принадлежность одного признака двум или нескольким объектам ( например, ромб и квадрат – параллелограммы).
Ясно, что высказывание всегда ложно (закон противоречия).
Заметим, что операция “конъюнкции” происходит от латинского слова conjunction, означающее связь, союз.
Из определения конъюнкции следует ,
В повседневной речи союз “ или ” используется в двух различных смыслах: разделительном и соединительном. Например: “Вектор работает или отдыхает” – обе рассмотренные возможности исключают друг друга. “Если будет дождь или Алексей будет нездоров, то встреча не состоится”. Обе возможности объединяются в качестве некоторой причины.
В первом случае о двоичном “или”: или он работает, или отдыхает. Во втором – о простом “или”: решение будет принято, если осуществиться любая из возможностей, либо обе вместе.
Простое “или” используется для обозначения логической операции “дизъюнкции” ( от латинского слова disjunctio - различие ).
Дизъюнкцией (логическим сложением)двух высказываний p и q называется такое высказывание ( читается: p и q ), которое истинно тогда и только тогда, когда истинно хотя бы одно из составляющих его высказываний ( рис.3 ).
Логические значения дизъюнкции описываются в табл. 3.
Рис. 3
Таблица 3.
p
q
В различных предложениях, а в математическом довольно часто, используется союз – связка “если …, то …”. Союз “если …, то …” соответствует логической операции, называемой “импликацией” ( от латинского слова implico - связываю).
Импликациейдвух высказываний p и q называется такое высказывание, которое считается ложным, когда p истинно, а q ложно, и истинным во всех остальных случаях. Обозначается или , читается “если p, то q” или “из p следует q”.
Высказывание p называется условием, посылкой или антецедентом, высказывание q – следствием, заключением или консеквентом.
Определение импликации выражается следующей таблицей истинности ( табл. 4 ).
Таблица 4.
p
q
Попробуем разобрать с этой логической операцией. С первой ее строкой как будто все в порядке: истинно p, истинно q и истинно импликацией .
Рассмотрим пример. Если равносторонний, то все его углы равны q. Значение истинности второго высказывания зависит от истинности второго высказывания зависит от истинности первого:
- если - равносторонний, то q – истинно,
- если - не равносторонний, то q – ложно.
Однако импликация истинна и в первом, и во втором случае.
Рассмотрим теперь пример, приведенный в книге голландского математика Х. Фрейденталя, чтобы проиллюстрировать смысл третьей и четвертой строк таблицы истинности. Если некоторый поезд прибывает на станцию, то падает сигнал: “путь закрыт”.
Существуют четыре возможности значений истинности p и q. Рассмотрим их комбинацию и оценим истинность импликации с точки зрения здравого смысла. Для наглядности используем следующую таблицу.
б).поезд не прибывает, сигнал “путь открыт” ( 0; 0; 1).
в).поезд не прибывает, сигнал “путь закрыт” (0; 1; 1).
Ведь в тексте ничего не говорится о том, какой сигнал надо подать, если поезд не прибывает ( путь можно закрыть и по другой причине, аварии не будет ).
Если подходить формально к рассмотрению импликации, то истинными окажутся высказывания, которые на практике обычно называются бессмысленными. Например, если , то в любом треугольнике 3 угла. Здесь никакого следования одного q из другого p нет. Поэтому обычно рассматривают те импликации, которые связаны содержательно, хотя это условие в определении импликации формально не зафиксировано.
Очень часто различные утверждения конструируются при помощи довольно сложных связок: “те и только те”, “тогда и только тогда”, “если и только если”, “необходимо и достаточно”. С помощью этих союзов строятся высказывания, называемые эквивалентностью ( от латинского слова acquivalens – равноценное, равнозначащее), или двойной импликацией. Например, любой четырехугольник – параллелограмм тогда и только тогда, когда его диагонали в точке пересечения делятся пополам.
Эквивалентностью ( эквиваленцией, логической эквивалентностью) двух высказываний p и q называется такое высказывание, которое истинно тогда и только тогда, когда оба высказывания p и q либо истинны, либо оба – ложны, и ложно во всех остальных случаях.
Обозначается ( ), читается “для того чтобы p, необходимо и достаточно, чтобы q ” или “pтогда и только тогда, когда q”.
Таблица истинности эквивалентности имеет вид
Таблица 6.
p
q
Если сравнить определения импликации и эквивалентности, то нетрудно обнаружить следующий логический закон их связи
Эквивалентность играет значительную роль в математических доказательствах. Например, большое число теорем формируется в форме необходимых и достаточных условиях.
Используемые в математической логике символы называются пропозициональными связками или связками исчисления высказываний. Отметим, что часто различные по виду знаки означают одно и тоже высказывание. Например, для обозначения эквивалентности могут быть использованы символы для конъюнкции , (причем точку часто опускают; для отрицания употребляют знаки , -).
Логическим связкам приписываются ранги в следующем порядке убывания старшинства: Таким образом, связка более высокого ранга имеет большую область действия.
Таблицы истинности называются также интерпретациями логических операций и составляют семантику формул ( т.е. придание смысла формулам) в отличие от синтаксиса формул ( т.е. формальных законов их построения, данных в определении формулы).
Следует заметить, что рассмотренным набором не исчерпываются все логические связки. Например, существуют такие операции как штрих Шеффера, стрелка Пирса, кольцевая сумма.
Штрих Шеффера обозначается символом и определяется следующей таблицей истинности (табл.7).
Таблица 7.
p
q
Операция штрих Шеффера характерна тем, что с ее помощью может быть выражена любая из пяти операций. Например, Таблица истинности для этой формулы имеет вид (табл. 8).
Таблица 8.
p
p
По определению, штрих Шеффера или антиконъюнкция,равна
Для операции конъюнкции, например, выражение через штрих Шеффера имеет вид
а таблица истинности – вид (табл.9).
Таблица 9.
p
q
(p/q)
(p/q)
(p/q)/(p/q)
Стрелка Пирса или антидизъюнкция обозначается так . По определению
= .
Таблица истинности имеет вид (табл.10).
Таблица 10.
p
q
Кольцевая сумма обозначается так . По определению
Таблица истинности имеет вид (табл. 11)
Таблица 11
p
q
Исходя из таблицы истинности для логических операций, можно строить таблицы истинности для произвольных формул.
Пример 1.Построить таблицу истинности для формулы
Решение.Будем строить таблицу истинности в соответствии с шагами построения . (табл. 12).
Таблица 12.
p
q
r
Нетрудно заметить, что таблица истинности для совпадает с таблицей истинности для .
Как видно из рассмотренного примера, даже при составления сложных формул, возникает обилие скобок. Чтобы избежать этого, в алгебре логики приняты некоторые соглашения относительно расстановки скобок.
1. Внешние скобки не пишутся. Например, вместо высказывания пишется .
2. На множестве вводится транзитивное отношение “быть более сильным” и отношение эквивалентности ~ “быть равносильным” по правилам, показанным на рис. 4.
Рис. 4
Согласно этим отношениям недостающие скобки в формуле расставляются последовательно, начиная с наиболее сильных связок и кончая наиболее слабыми, а для равносильных связок расстановка скобок выполняется слева на право.
Пример 2. В формуле скобки расставляются следующим образом: в формуле , в формуле
Отметим, что, например, в формуле скобки убирать нельзя, поскольку в силу наших соглашений формуле соответствует формула .
Итак, с помощью логических операций можно строить более сложные высказывания, причем порядок операций обычно указывается скобками. Чтобы подвести итог, определим понятие формулы логики высказываний. Начнем с языка. Язык определен, если установлен алфавит и его символы.
Алфавитомназывают любое не пустое множество, элементы которого являются символами данного алфавита.
Любая конечная последовательность символов алфавита называется словом иливыражениемданного языка. Алфавит логики высказываний содержит такие символы: буквы латинского алфавита с индексом или без него, логические связки, разделители.
Всякое сложное высказывание, которое можно получить из элементарных высказываний с помощью логических связок, называется формулой алгебры логики.
( читается “не р” ), которое истинно, если данное высказывание ложно, и ложно, если данное высказывание истинно ( рис.1 )
= р таково, что оба составляющие его высказывания 
всегда ложно (закон противоречия).
, 
( читается: p и q ), которое истинно тогда и только тогда, когда истинно хотя бы одно из составляющих его высказываний ( рис.3 ).
или 
, читается “если p, то q” или “из p следует q”.
равносторонний, то все его углы равны q. Значение истинности второго высказывания зависит от истинности второго высказывания зависит от истинности первого:
, то в любом треугольнике 3 угла. Здесь никакого следования одного q из другого p нет. Поэтому обычно рассматривают те импликации, которые связаны содержательно, хотя это условие в определении импликации формально не зафиксировано.
( 
), читается “для того чтобы p, необходимо и достаточно, чтобы q ” или “pтогда и только тогда, когда q”.
для конъюнкции 
, 
(причем точку часто опускают; для отрицания употребляют знаки 
, -).
Таким образом, связка более высокого ранга имеет большую область действия.
и определяется следующей таблицей истинности (табл.7).
Таблица истинности для этой формулы имеет вид (табл. 8).
. По определению
.
. По определению
. (табл. 12).
пишется 
.
вводится транзитивное отношение 
“быть более сильным” и отношение эквивалентности ~ “быть равносильным” по правилам, показанным на рис. 4.
скобки расставляются следующим образом: 
в формуле 
, в формуле 
скобки убирать нельзя, поскольку в силу наших соглашений формуле 
соответствует формула 
.