Равносильность формул логики высказываний
Определение. Пусть А и В – две формулы, зависящие от одного и того же списка переменных. Будем называть их равносильными, если для любого набора значений переменных они принимают одинаковые значения.
Рассмотрим основные равносильности логики высказываний.
Пусть А, В, С – произвольные формулы. Тогда справедливы следующие свойства логических операций (табл. 11):
Таблица 11
|
1. Идемпотентность |
||
|
А Щ А = А |
А Ъ А = А |
|
|
2. Коммутативность |
||
|
А Щ В = В Щ А |
А Ъ В = В Ъ А |
|
|
3. Ассоциативность |
||
|
А Щ (В Щ С) = (А Щ В) Щ С |
А Ъ (В Ъ С) = (А Ъ В) Ъ С |
|
|
4. Правила поглощения |
||
|
А Щ (А Ъ В) = А |
А Ъ (А Щ В) = А |
|
|
5. Дистрибутивность |
||
|
А Щ (В Ъ С) = (А Щ В) Ъ (А Щ С) |
А Ъ (В Щ С) = (А Ъ В) Щ (А Ъ С) |
|
|
6. Правила де Моргана |
||
|
|
|
|
|
7. Свойства констант |
||
|
А Щ 1 = А А Щ 0 = 0 |
А Ъ 0 = А А Ъ 1 = 1 |
|
|
8. Закон исключения третьего и закон противоречия |
||
|
|
|
|
|
9. Снятие двойного отрицания |
||
|
|
||
|
10. Формулы расщепления (склеивания) |
||
|
|
|
|
|
11. Связь дизъюнкции, конъюнкции, отрицания и импликации |
||
|
|
||
|
12. Выражение эквивалентности |
||
|
|
||
Любая из этих равносильностей легко может быть доказана с помощью таблицы истинности.
предыдущаяследующая