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

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

Эквиваленция высказываний x,y обозначается символом (или , реже ~), читается “ для того, чтобы x, необходимо и достаточно, чтобы y”, или “ х тогда и только тогда, когда у”. Высказывания x, y называются членами эквиваленции. Логические значения операции эквиваленции описываются следующей таблицей истинности:

x у xy 1 1 1 1 0 0 0 1 0 0 0 0

«Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, высота SМ является медианой» является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ

с вершиной S и основанием PQ высота SМ является медианой» либо одновременно истинны, либо одновременно ложны..

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

Форма высказывания естественного языка

Операция	Соответствующая формула языка алгебры логики	Формула
отрицание	Не А; неверно, что А; А не имеет места
конъюнкция	A и В; как А, так и В; не только А, но и В; А вместе с В; А, несмотря на В; А, в то время как В	АВ
дизъюнкция	А или В; А, или В, или оба	АВ
импликация	Если А, то В; В, если А; А, только если В; А только тогда, когда В; А достаточно для В; А только при условии, что В; В необходимо для А; А, значит В; для В достаточно А; А влечет В; для А необходимо В; все А есть В; из А следует В; В тогда, когда А	А → В
эквиваленция	А эквивалентно В; А тогда и только тогда, когда В; А если и только если В; А необходимо и достаточно для В

Перевести на язык алгебры логики следующие высказывания:

если светит солнце, то дождя не будет

если погода пасмурная и дует ветер, то дождя нет;

неверно, что если погода пасмурная, то нет ветра;

Коля решит задачу, если он вспомнит нужную теорему.

ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ.

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

Порядок выполнения операций в формуле указывается скобками. Например, из трёх высказываний x,y,z можно построить высказывания

(xy) и x .

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

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

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

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

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

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

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

Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в неё переменных.

Формула называется тождественно ложной (или противоречием), если она принимает значение 0 при всех значениях входящих в неё переменных.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула АВ – тавтология, и обратно, если формула АВ – тавтология, то формулы А и В равносильны.