Теорема. Всякая формула, получающаяся из тавтологии алгебры высказываний заменой входящих в нее пропозициональных переменных произвольными предикатными переменными, является тавтологией логики предикатов.
Теорема 1. Законы де Моргана для кванторов.
Следующие формулы логики предикатов являются тавтологиями:
Доказательство
Докажем тождественную истинность первой формулы.
Данная формула замкнута, т.е. не имеет свободных предметных переменных. Поэтому подставим в эту формулу вместо предикатной переменной любой конкретный одноместный предикат , определенный на некотором множестве М=>получим высказывание
(*)
-тавтология
Для доказательства его истинности (*) нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны. В самом деле, высказывание истинно тогда и только тогда, когда высказывание ложно, что возможно, на основании определения, тогда и только тогда, когда предикат -опровержим:
Далее, опровержимость предиката означает выполнимость предиката , что равносильно истинности высказывания (по определению)
Итак, высказывание истинно тогда и только тогда, когда высказывание истинно. Следовательно, высказывание (*) истинно, что и доказывает тождественную истинность первой формулы.
Следствие. (из закона двойного отрицания и теоремы 1). Выражение кванторов друг через друга.
Теорема 2. Законы пронесения кванторов через конъюнкцию и дизъюнкцию.
Теорема 3. Законы пронесения кванторов через импликацию.
Do'stlaringiz bilan baham: |
