§2. Формулы алгебры высказываний. Законы логики п.1. Определение формул алгебры высказываний.

Переменные высказывания часто называют элементарными вы­сказываниями. Они принимают логические значения истина или ложь. Иногда переменные высказывания называются элементарными форму­лами или атомами или пропозиционарными переменными.

Определение. Формулой алгебры высказываний называется такая формула, для которой выполнены следующие условия:

1. каждый атом – формула;

2. если и - формулы, то , , , , - тоже формулы;

3. только те формулы являются формулами алгебры логики, кото­рые удовлетворяют условию 1) и 2).

Порядок выполнения операций в формуле задаётся скобками. Число скобок в формулах можно уменьшить, введя соглашение:

1. в сложных формулах будем опускать внешнюю пару скобок;

2. упорядочим знаки логических операций по старшинству: . В этом списке имеет самую большую область дей­ствия, а самую маленькую.

П.2. Законы логики.

Существуют формулы, которые принимают значение «истина» независимо от того, какие значения принимают входящие в них атомы. Такие формулы называются законами алгебры логики высказываний.

Определение. Формула алгебры логики называется законом ал­гебры логики высказываний или тождественно истинной формулой или тавтологией, если при любых значениях атомов, входящих в эту фор­мулу, значение этой формулы «истина».

Примеры законов алгебры логики высказываний.

1. Закон контрапозиции: .

Доказательство: составим таблицу истинности

и	и	л	л	и	и	и
и	л	л	и	л	л	и
л	и	и	л	и	и	и
л	л	и	и	и	и	и

Формула принимает значение «истина», при любых значениях переменных и , значит, является законом алгебры логики.

2. Закон исключенного третьего: .

Доказательство: составим таблицу истинности

и	л	и
л	и	и

Формула 2 принимает значение «истина», при любых значениях переменных , значит, является законом алгебры логики.

3. Закон двойного отрицания: .

Доказательство: составим таблицу истинности

и	л	и	и
л	и	л	и

Формула 3 принимает значение «истина», при любых значениях переменных , значит, является законом алгебры логики.

4. Закон коммутативности конъюнкции: .

Доказательство: составим таблицу истинности

и	и	и	и	и
и	л	л	л	и
л	и	л	л	и
л	л	л	л	и

Формула 4 принимает значение «истина», при любых значениях переменных и , значит, является законом алгебры логики.

5. Закон ассоциативности конъюнкции: .

Доказательство: составим таблицу истинности

и	и	и	и	и	и	и	и
и	и	л	л	л	л	л	и
и	л	и	л	л	л	л	и
л	и	и	и	и	л	л	и
и	л	л	л	л	л	л	и
л	и	л	л	л	л	л	и
л	л	и	л	л	л	л	и
л	л	л	л	л	л	л	и

Формула 5 принимает значение «истина», при любых значениях переменных , и , значит, является законом алгебры логики.

6. Закон коммутативности дизъюнкции: .

Доказательство: составим таблицу истинности

и	и	и	и	и
и	л	и	и	и
л	и	и	и	и
л	л	л	л	и

Формула 6 принимает значение «истина», при любых значениях переменных и , значит, является законом алгебры логики.

7. Закон ассоциативности дизъюнкции: .

Доказательство: составим таблицу истинности

и	и	и	и	и	и	и	и
и	и	л	и	и	и	и	и
и	л	и	и	и	и	и	и
л	и	и	и	и	и	и	и
и	л	л	л	и	и	л	и
л	и	л	и	и	и	и	и
л	л	и	и	л	и	и	и
л	л	л	л	л	л	л	и

формула 7 принимает значение «истина», при любых значениях переменных , и , значит, является законом алгебры логики.

8. Закон дистрибутивности конъюнкции относительно дизъ­юнкции: .

Доказательство: составим таблицу истинности

и	и	и	и	и	и	и	и	и
и	и	л	и	и	и	л	и	и
и	л	и	и	и	л	и	и	и
л	и	и	и	л	л	л	л	и
и	л	л	л	л	л	л	л	и
л	и	л	и	л	л	л	л	и
л	л	и	и	л	л	л	л	и
л	л	л	л	л	л	л	л	и

Формула 8 принимает значение «истина», при любых значениях переменных , и , значит, является законом алгебры логики.

9. Закон дистрибутивности дизъюнкции относительно конъ­юнкции: .

Доказательство: составим таблицу истинности

и	и	и	и	и	и	и	и	л
и	и	л	л	и	и	и	и	л
и	л	и	л	и	и	и	и	л
л	и	и	и	и	и	и	и	л
и	л	л	л	и	и	и	и	л
л	и	л	л	л	и	л	л	л
л	л	и	л	л	л	и	л	л
л	л	л	л	л	л	л	л	л

Формула 9 принимает значение «истина», при любых значениях переменных , и , значит, является законом алгебры логики.

10. Закон построения отрицания конъюнкции: .

Доказательство: составим таблицу истинности

и	и	и	л	л	л	л	и
и	л	л	и	л	и	и	и
л	и	л	и	и	л	и	и
л	л	л	и	и	и	и	и

Формула 10 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.

11. Закон построения отрицания дизъюнкции: .

Доказательство: составим таблицу истинности

и	и	и	л	л	л	л	и
и	л	и	л	л	и	л	и
л	и	и	л	и	л	л	и
л	л	л	и	и	и	и	и

Формула 11 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.

12. .

Доказательство: составим таблицу истинности

и	и	и	л	и	и
и	л	л	л	л	и
л	и	и	и	и	и
л	л	и	и	и	и

Формула 12 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.

13. Закон отрицания импликации: .

Доказательство: составим таблицу истинности

и	и	и	л	л	л	и
и	л	л	и	и	и	и
л	и	и	л	л	л	и
л	л	и	л	и	л	и

Формула 13 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.

14. .

Доказательство: составим таблицу истинности

и	и	и	л	л	и	и
и	л	л	л	и	л	и
л	и	л	и	л	л	и
л	л	и	и	и	и	и

Формула 14 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.

15. .

Доказательство: составим таблицу истинности

					(
и	и	и	и	и	и	и
и	л	л	л	и	л	и
л	и	л	и	л	л	и
л	л	и	и	и	и	и

Формула 15 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.

16. .

Доказательство: составим таблицу истинности

и	и	и	л	л	л	л	л	л	и
и	л	л	и	и	л	и	л	и	и
л	и	л	и	л	и	л	и	и	и
л	л	и	л	и	и	л	л	л	и

Формула 16 принимает значение «истина», при любых значениях перемен­ных и , значит, является законом алгебры логики.