Важнейшие свойства общезначимых формул

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Контрольные вопросы

Виды формул алгебры высказываний

Формула А называется

· общезначимой (тождественно истинной, тавтологией), если во всех своих интерпретациях она принимает значение И

· невыполнимой(тождественно ложной, противоречием), если во всех своих интерпретациях она принимает значение Л

· нейтральной, если она не является ни общезначимой, ни невыполнимой

· выполнимой, если она общезначимая или нейтральная

· необщезначимой, если она невыполнимая или нейтральная.

 

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

 

Только И	Хотя бы одно И,и хотя бы одноЛ	Только Л
общезначимые	нейтральные	невыполнимые
выполнимые	невыполнимые
общезначимые	необщезначимые

1. Сформулируйте определения отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции, операций штрих Шеффера и стрелка Пирса.

2. Какие основные символы используются в логике высказываний?

3. Какое выражение называется пропозициональной формулой логики высказываний?

3. Что такое таблица истинности формулы логики высказываний и как она строится?

4. Дайте определение истинностной функции.

5. Сколько существует одноместных, двухместных, трехместных, четырехместных истинностных функций?

6. Перечислите основные шаги построения формулы логики высказываний по таблице истинности на основе алгоритма СДНФ.

7. Основные шаги построения формулы логики высказываний по таблице истинности на основе алгоритма СКНФ.

8. В чем отличие алгоритмов СДНФ и СКНФ?

9. Какая система истинностных функций называется полной?

10. Перечислите существующие полные системы истинностных функций состоящие из трех, двух и одной функции.

11. Как функции штрих Шеффера и стрелка Пирса связаны с отрицанием?

12. Какая формула называется общезначимой, нейтральной выполнимой, тавтологией, противоречием?

13. Приведите примеры тавтологий.

14. Какие формулы называются равносильными?

 

Лекция 3. Основные логические законы

3.1 Важнейшие свойства общезначимых формул

3.2 Важнейшие общезначимые формулы

3.3 Методы установления общезначимости формул.

3.3.1 Метод истинностных таблиц.

3.3.2 Метод аналитических таблиц.

3.3.3. Метод от противного.

3.3.4 Равносильные преобразования формул

3.4. Отношение логического следования

 

 

 

Общезначимые формулы играют особую роль в логике: они на языке алгебры высказываний выражают законы логики. Общезначимые формулы истинны в силу своей структуры, независимо от истинностных значений составляющих их формул. Например, для любой формулы А формульная схема АÚ¬А принимает значение И независимо от значения формулы А. В самом деле, если А=И, то дизъюнкция АÚ¬А принимает значение И. Если же А=Л, то тогда АÚ¬А=И, а дизъюнкция АÚ¬А опять принимает значение И. Рассмотренная формульная схема выражает один из законов логики - закон исключенного третьего.

Для утверждения «Формула Е общезначима» введем обозначение |= Е. По выше доказанному: |= АÚ¬А. Последняя запись означает, что всякая получаемая из формульной схемы АÚ¬А формула общезначима. Например, формула (АÙВÞС)Ú¬ (АÙВÞС) общезначима.

Теорема. Если Е — общезначимая формула, содержащая атомы P₁, ..., Р_п, то формула Е*, получающаяся из Е одновременной подстановкой формул А₁, ..., А_пвместо атомов P₁, ..., Р_псоответственно, также общезначимая.

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

Теорема. Если |=А и|=АÞВ, то |=В.

□ Рассмотрим произвольный набор значений атомов, входящих хотя бы в одну из формул А или В. В силу общезначимости формулы А и АÞВ примут значениеИ.Значение И при рассматриваемом наборе должна иметь и формула В, так как если бы формула Вимела значение Л, то, по определению импликации, значение Л имела бы и формула АÞВ. ■

Теорема. |= А~В тогда и только тогда, когда А=В.

Теорема. |= Е тогда и только тогда, когда ¬Е — противоречие.