3.3. Формулы логики высказываний
Любое составное высказывание образуется из простых высказываний при помощи логических операций. Если каждое простое высказывание заменить некоторой переменной, которую мы назовем пропозиционной, то мы получим некоторую формулу.
Формулой алгебры высказываний является:
а) любая пропозиционная переменная;
б) если
– формулы алгебры высказываний, то
выражения
,
– также являются формулами логики
высказываний;
в) других формул нет.
Например.
,
и т.д.
Таким образом, любое высказывание является интерпретацией некоторой формулы алгебры высказываний.
Для каждой формулы можно составить таблицу истинности. При их составлении необходимо учитывать порядок выполняемых действий. Если в формуле нет скобок, то логические операции выполняются в следующем порядке: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.
Например.
Составить таблицу истинности для формулы
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Исходя из таблицы истинности, можно получить следующую классификацию формул алгебры высказываний:
Формула алгебры высказываний, принимающая логические значение «1» при любых ее интерпретациях называется тавтологией или тождественно-истинной формулой.
Формула алгебры высказываний, принимающая логические значение «1» при некоторых ее интерпретациях называется выполнимой.
Формула алгебры высказываний, принимающая логические значение «0» при любых ее интерпретациях называется противоречием или тождественно-ложной формулой.
Формула алгебры высказываний, принимающая логические значение «0» при некоторых ее интерпретациях называется опровержимой.
Например.
Составить таблицу истинности для формулы
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
В последнем столбце таблицы получили истинное значение формулы, независимо от того, какие значения будут принимать ее переменные, следовательно, формула логики высказываний является тавтологией.
Например.
Составить таблицу истинности для формулы
.
|
|
|
|
|
1 |
0 |
0 |
|
1 |
0 |
0 |
|
0 |
1 |
0 |
|
0 |
1 |
0 |
Исходная формула принимает логическое значение «0», при любых наборах переменных, следовательно эта формула является противоречием.
Две формулы называются равносильными, если они принимают при одинаковых наборах переменных одинаковые истинностные значения.
Логические выражения можно преобразовывать в соответствии с законами алгебры логики.