Формулы алгебры логики
С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками.
Пример.
1)
– дизъюнкция
конъюнкции x, y и отрицания высказывания z;
2)
– импликация, посылкой
которой является высказывание x, а заключением – отрицание дизъюнкции высказывания y и
конъюнкции высказываний x, z.
Определение. Всякое
сложное высказывание, которое может быть получено из элементарных высказываний
посредством применения логических операций, называется формулой алгебры логики.
Обозначение: формулы
алгебры логики обозначаются заглавными буквами латинского алфавита A, B, C…
Для
упрощения записи формул принят ряд соглашений. Скобки можно опускать,
придерживаясь следующего порядка действий:
1)
Отрицание;
2)
Конъюнкция;
3)
Дизъюнкция;
4)
Импликация;
5)
Эквиваленция.
Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний.
Пример.
Пусть x=1, y=1, z=0. Тогда 
=1, так как
|
x |
y |
z |
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности.
Пример.
Составить
таблицу истинности формулы A=
.
|
x |
y |
|
|
|
|
A |
|
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 |
Утверждение. Если
формула содержит n элементарных
высказываний, то она принимает 2n значений,
состоящих из 0 и 1, или, что то же самое, таблица
истинности содержит 2n
строк.