Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный горный университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

МАТ_ ЛОГИКА / МАТЕМАТИЧЕСКАЯ ЛОГИКА_ЛК3_30_01_2012

.doc

Скачиваний:

Добавлен:

06.06.2015

Размер:

413.18 Кб

Скачать

☆

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При любом выборе формул А, В, С нижеследующие формульные схемы представляют собой общезначимые формулы.

Формулы (1)—(13) составляют одну из возможных полных, независимых аксиоматик логики высказываний. В то же время они являются одним из способов выражения важнейших (и простейших) схем рассуждений.

Формулы (14) и (15) позволяют равносильным образом избавляться от эквиваленции и импликаций.

В связи с формулами (21) — (26) обращаем внимание на то, что импликация не является ни коммутативной, ни ассоциативной операцией. С некоммутативностью импликации, в частности, связано наличие у нее специальных имен для первого и второго членов — антецедент и консеквент. В силу коммутативности и ассоциативности операций конъюнкции, дизъюнкции (и эквиваленции) члены этих операций можно при равносильных преобразованиях произвольным образом объединять скобками в группы, производя при необходимости требуемые перестановки. Учитывая ассоциативность конъюнкции (дизъюнкции, эквиваленции), многочленные конъюнкции (дизъюнкции, эквиваленции) можно писать без скобок.

Отметим еще, что из четырех бинарных операций конъюнкции, дизъюнкции, импликации и эквиваленции дизъюнкция и импликация дистрибутивны относительно трех остальных, конъюнкция дистрибутивна только относительно дизъюнкции, а эквиваленция не дистрибутивна ни относительно одной из остальных операций (формулы (27) - (33)).

Общезначимость каждой из 50 формул можно установить, например, составив истинностную таблицу для конкретной формулы и убедившись в том, что последний столбец каждой такой таблицы состоит только из одних И.

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

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

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

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

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

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

Составляется истинностная таблица формулы. Если в своем последнем столбце она содержит только значения И, значит, эта формула общезначима, в противном случае – необщезначима.

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

Аналитические таблицы строятся по аналитическим правилам.

Введем обозначения: Т-«true»- истина; F-«false»- ложь.

Правила для логических операций (два правила для каждой операции)


T_		F_

Пример. Установить, является ли формула

общезначимой.

Выпишем итоговые таблицы:

1){TA,FB,TA,FB} незамкнутая;

2){TA,FB,FA,TB} замкнутая;

3){FB,TA,FB} незамкнутая;

4){TA,TA,FB} незамкнутая;

5){FA,FA,TB} замкнутая;

6){TA,FB,TB} замкнутая.

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

Если все итоговые таблицы формулы с индексом F-замкнуты, то формула является общезначимой.

Пример. Проверить, является ли логическим противоречием формула ?

1){FA} незамкнута;

2){TB,FA,TA} замкнута. Следовательно, - не есть логическое противоречие

Замечание: Метод аналитических таблиц используется обычно для формул, в которых число атомов больше трех-четырех (тогда не строятся таблицы истинности).

Пример. Доказать, что формула общезначима

1) {FA,TB,FC,FA,FB} – замкнутая;

2) {FA,TB,FC,TA} – замкнутая;

3) {FA,TB,FC,TC} – замкнутая;

4) {TA,TA,FA,FC} – замкнутая;

5) {TA,TB,FA,FC} – замкнутая;

6) {FB,TA,FA,FC} – замкнутая;

7) {TC,TA,FA,FC} – замкнутая;

8) {FB,TB,FA,FC} – замкнутая;

9) {TC,TB,FA,FC} – замкнутая.

Все таблицы замкнутые, значит, формула является общезначимой.

Если при исследовании формул на общезначимость, итоговые таблицы этой формулы с индексом F все замкнуты, то она является общезначимой. Аналогично, если формула исследуется с индексом Т и все итоговые таблицы замкнуты, то она является противоречием. В противном случае формула является нейтральной.

3.3.3 Метод от противного связан с решением логических уравнений.

Логическое уравнение - это равенство вида: Ф=Ф, где Ф и Ф - формулы алгебры высказываний, или одно из значений «И», «Л». Решить логическое уравнение - означает найти все те наборы истинностных значений атомов, входящих в хотя бы одну из формул Ф и Ф, при котором имеет равенство:

Ф=Ф.

Пример: проверить, общезначима ли формула (АВ)  ((В С) (АС)).

Предположим противное. Пусть формула не является общезначимой, т.е. существует набор атомов, на котором она принимает значение Л:

(АВ)  ((В С) (АС))=Л.

Полученное противоречие свидетельствует о том, что формула «И» во всех интерпретациях, т.е. общезначима.

3.3.4 Метод равносильных преобразований

Отметим, что на общезначимые эквиваленции из формул 1-50 можно смотреть как на равносильности.

Пример. Рассмотрим формулу (15)

можно заменить на

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

а также упрощения на основе формул

Пример. С помощью метода равносильных преобразований установить, общезначима ли формула .

Формула общезначима

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

Рассмотрим таблицы истинности формул и :

Р	Q
И	И	Л	Л
И	Л	И	И
Л	И	И	И
Л	Л	Л	И

Из таблиц видно, что при всех наборах значений P и Q , при которых формула принимает значение «И», это же значение «И» принимает и формула .

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

Логическое следование обозначают: А╞В.

╞

А╞В

Из формул логически следует формула В (т.е. ╞В), если формула В имеет значение «И» по крайней мере при всех тех значениях атома, входящих в формулы , при которых значение «И» имеют формулы одновременно.

Th. ╞В, тогда и только тогда, когда ╞.

Это утверждение доказывается методом от противного.

3.5 Отношение совместности

Формулы А и В называются совместными, если их эквиваленция выполнима, т.е.

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