Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
3. НЕКОТОРЫЕ ЗАКОНЫ ЛОГИКИ ПРЕДИКАТОВ
1. Все частные случаи тавтологий и тождественно-истинных формул (A=A, законы Де Моргана и проч.) логики высказываний являются общезначимыми формулами Л.П.
2. Взаимовыразимость кванторов:
∀αA ⇔ ¬∃α¬A
∃αA ⇔ ¬∀α¬A
3. Отрицание кванторов:
¬∀αA ⇔ ∃α¬A
¬∃αA ⇔ ∀α¬A
4. Перестановка кванторов:
∀α∀βA ⇔ ∀β∀αA
∃α∃βA ⇔ ∃β∃αA
∃α∀βA → ∀β∃αA
5. * Кванторные аксиомы:
∀αA → At, где At есть A(α/t)
At → ∃αA, где At есть A(α/t)
6. Вырожденные кванторы:
∀αA ⇔ A, если A не содержит свободных вхождений α (*)
∃αA ⇔ A, если A не содержит свободных вхождений α (*)
7. Законы пронесения и вынесения кванторов:
а) конъюнкция:
∀α(A ∧ B) ⇔ (∀αA ∧ ∀αB)
∃α(A ∧ B) → (∃αA ∧ ∃αB)
∃α(A ∧ B) ⇔ (A ∧ ∃αB), если A не содержит свободных вхождений α (*)
б) дизъюнкция:
∃α(A ∨ B) ⇔ (∃αA ∨ ∃αB)
(∀αA ∨ ∀αB) → ∀α(A ∨ B)
∀α(A ∨ B) ⇔ (A ∨ ∀αB), если А не содержит свободных вхождений α (*)
в) импликация:
∀α(A → B) → (∀αA → ∀αB)
∀α(A → B) ⇔ (A → ∀α B), если А не содержит свободных вхождений α (*)
∀α(A → B) ⇔ (∃αA → B), если B не содержит свободных вхождений α (*)
(∃αA → ∃αB) → ∃α(A → B)
∃α(A → B) ⇔ (A → ∃αB) , если А не содержит свободных вхождений α (*)
∃α(A → B) ⇔ (∀αA → B), если B не содержит свободных вхождений α (*).
Чтобы доказать общезначимость формулы <Ф> (например) , делаем предположение о необщезначимости формулы; говорим, что существует модель М при означивании v, в которых неверно, что <Ф>. Тогда , пользуясь определением истинности (один – для импл., другой – для эквив. и т.д.) и семантическими леммами, получаем несколько возможных вариантов. Если на выходе в варианте получилось противоречие, значит получить непротиворечивую модель M при означивании v, где <Ф> не является общезначимой, не удалось. Т.о. формула <Ф> истинна в любой модели М при любом означивании v, т.е. она общезначима (т.е. истинна вне зависимости от ?семантики).
Есть и другой путь доказательства. Например, закон взаимовыразимости кванторов ∀αA ⇔ ¬∃α¬A доказывается тем образом, что если нарисовать круг (формулу А), и сказать: «Любое α принадлежит А»
Для доказательства общезначимости кванторных аксиом требуется также лемма о формулах и означиваниях. Для доказательства законов логики предикатов, в которых оговаривается, что некоторая переменная не входит в ту или иную подформулу (*), потребуется лемма о переменных и означиваниях.
Лемма о формулах и означивании:
Пусть At – результат постановки в формулу А вместо свободной переменной α терма t. Обозначаем так: At=A(α/t). Тогда для любого терма t и любых означиваний v и v’ таких, что v’=v(α t[v]); имеет место
M, v’ |= A ⇔ M, v |= At.
Лемма о переменных и означиваниях:
Пусть формула А не содержит свободную переменную x, тогда для любого v’=v(α) имеет место
M, v |= A ⇔ M, v’ |= A.