39. Алгебра логики
Под
высказыванием
понимается
предложение, относительно которого
можно сказать истинно оно или ложно.
Вводятся обозначения: 1 – “истинно”,
0 – “ложно”.Переменная, принимающая
значения из множества {0, 1}, называется
высказывательной
переменной.
Вводятся обозначения:
.
Алгебраические операции, определённые
на множестве {0, 1}, называютсялогическими
операциями.
-
арная логическая операция:
Логические
операции.
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
Отрицанием
высказывания
называется высказывание, истинное,
когда высказывание
ложно, и ложное – в противном случае.
Конъюнкцией
двух
высказываний
и
называется
высказывание, истинное, когда оба
высказывания истинны, и ложное – во
всех других случаях. Конъюнкция
называется логическим умножением.
;
=min{
,
}Дизъюнкцией
двух
высказываний
и
называется
высказывание, ложное в случае, когда
оба высказывания ложны, и истинное –
во всех других случаях. Дизъюнкция
называется логическим сложением.
;
=max{
,
}Импликацией
двух высказываний
и
называется
высказывание, ложное, когда
истинно, а
ложно; во
всех других случаях - истинное.
(если
,
то
).Эквиваленцией
двух высказываний
и
называется
высказывание, истинное, когда истинностные
значения
и
совпадают, и ложное - в противном
случае.
(тогда
и только тогда, когда).
Альтернативной
дизъюнкцией двух
высказываний
и
называется
высказывание, истинное, когда истинностные
значения
и
не совпадают,
и ложное - в противном случае.
(или
,
или
).
=
-
отрицание эквиваленции.
=
-
сложение по модулю 2.
-
стрелка Пирса.
=
-
отрицание дизъюнкции.
-
штрих Шеффера.
=
-
отрицание конъюнкции.
Формулы алгебры высказываний - это некоторые конструкции, построенные с помощью логических операций и высказывательных переменных, которые имеют смысл. Высказывания и высказывательные переменные являются формулами.
Установим порядок выполнения операций в логических формулах:
1)
,
2)
,
потом дизъюнкция
,
,
,
.
Формула называется тождественно истинной (тождественно ложной), если она принимает значение 1 (0) при всех значениях высказывательных переменных, входящих в эту форму.
Формула, не являющаяся ни тождественно истинной, ни тождественно ложной, называется выполнимой.
Формулы называются эквивалентными, если они принимают одинаковые значения истинности при одинаковых наборах значений истинности, содержащихся в них высказывательных переменных.
Формулы, в которые входят конъюнкция, дизъюнкция, отрицание, причём отрицание относится только к высказывательным переменным, называются приведёнными формулами.
Теорема. Для любой формулы алгебры высказывания существует эквивалентная (равносильная) ей приведённая формула.