Законы логики высказываний. Построение таблиц истинности для формул логики высказываний.

Пусть Х,Y,Z,…- переменные высказывания (высказывания, которые могут принимать значения истина или ложь).

Формулой логики высказываний называется:

1) каждое отдельно взятое переменное высказывание;

2) если А, В - формулы логики высказываний, то формулами будут:

(А˄В), (А В), (А В), (А В),( )

3) других формул нет.

Формулы А и В называют равносильными (обозначают А ≡ В), если они принимают одинаковые значения истинности на одних и тех же наборах значений переменных высказываний.

Замечание: Равносильные формулы имеют одинаковые таблицы истинности.

Наиболее часто используемые равносильные формулы получили название законов логики высказываний.

Законы логики высказываний:

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

1.

Коммутативность конъюнкции и дизъюнкции

2. 3.

Ассоциативность конъюнкции и дизъюнкции

4. 5.

Дистрибутивность

6. 7.

Законы де Моргана

8. 9.

Законы идемпотентности конъюнкции и дизъюнкции

10. 11.

Законы поглощения

12. 13.

Законы дополнительности

14. 15. 16.

17. 18. 19.

Законы склеивания

20. 21.

Другие равносильные формулы

22. 23.

24. 25.

26. 27. 28. 29.

30. 31.

32.

33. 34. 35. 36.

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

Формула называется тождественно ложной, если она принимает значение ложь, при любом наборе значений переменных высказываний.

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

Замечание: Любое тождественно истинное высказывание является

выполнимым, обратное неверно.

Вывод: Установить является ли формула логики высказываний тождественно истинной, тождественно ложной или только выполнимой можно с помощью:

- построения таблиц истинности;

- равносильных преобразований.

Таблица истинности формул логики высказываний

Для формулы логики высказываний можно найти логические значения всех тех переменных высказываний, в которые формула превращается при подстановке вместо всех ее переменных различных конкретных высказываний. При этом говорят о логическом значении самой формулы и о логических значениях ее переменных высказываний (пропозициональных переменных). При нахождении логических значений формулы, соответствующих всевозможным наборам значений ее пропозициональных переменных, удобной формой записи является табличная форма.

Если формула логики высказываний зависит от n переменных, то таблица истинности, построенная для этой формулы, содержит строк.

Замечание: Равносильные формулы имеют одинаковые таблицы истинности.

Пример: Дана формула логики высказываний: . С помощью таблицы истинности выясните, какая эта формула, тождественно истинная, тождественно ложная или только выполнимая.

Решение: Построим таблицу истинности данной формулы

A	B

Так как в последнем столбце таблицы все значения истины, следовательно, формула тождественно истина.