Основные логические операции и их свойства

Предикаты и операции над ними

Алгебры высказываний.

Л е к ц и я 8

В математической логике изучаются высказывания и различные связи между ними. При этом понятие высказывания считается основным, неопределяемым понятием. В качестве пояснения говорят лишь, что высказывание — это утверждение, относительно которого известно, истинно оно или ложно.

Если высказывание а истинно или ложно, то говорят, что оно имеет значение «и» или «л» и пишут

а º и или а º л.

Высказывания а и b, имеющие одинаковые значения, называются равносильными, что обозначается в виде

а º b.

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

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

a & b (a Ù b), a Ú b, a ® b, ` a (ù a)

и называются конъюнкцией, дизъюнкцией, импликацией и отрицанием высказывания а (табл.8.1).

В высказываниях a & b, a Ú b, a и b называются членами, или компонентами, соответственно конъюнкции и дизъюнкции; в высказывании а -> b а называют посылкой, b — заключением импликации.

Обозначим через W = {и, л}. Тогда табл.8.1 может служить определением операций &, Ú, ®,` на множестве W.

Таблица 8.1

a	b	a & b	a Ú b	a ® b	` a
и	и	и	и	и	л
и	л	л	и	л	л
л	и	л	и	и	и
л	л	л	л	и	и

При этом операции &, Ú,` обладают следующими свойствами:

1) операции &, Ú коммутативны, ассоциативны, идемпотентны, дистрибутивны одна относительно другой и связаны законами поглощения: a & (a Ú b) º a, a Ú (a & b) º a;

2) операция отрицания — инволютивна (т.е. ) и связана с операциями &, Ú законами де Моргана: и соотношениями а & а º л, а Ú а º и.

Отсюда следует, что алгебра W(&, Ú,`) является булевой алгеброй. В ней роль 1 и 0 играют соответственно элементы и, л.

Определение 8.1. Двухэлементная булева алгебра W(&, Ú,`) называется алгеброй высказываний.

Из табл.8.1 видно, что импликация (->) также является операцией на множестве W и обладает рядом свойств, связывающих её с другими операциями:

a ® b º` b ®` a (закон контрапозиции),

a ® (b ® a) º и,

ab ® b º и,

a ® b º` a Ú b и другие.

Дата добавления: 2014-12-29