Упражнение 4

Доказать утверждения:

1. А тавтология, если и только если А невыполнимо;

2. А выполнимо, если и только если А не тавтология;

3. А и В эквивалентны тогда и только тогда, когда А  В – тавтология.

4. тавтологии и исчисления высказываний являются тавтологиями модальной логики;

5. А эквивалентно А;

6.  (А  В) эквивалентно (А & В).

Теорема (о нормальности). Для любых формул А и В имеет место тавтология:

(А  В)  (А  В).

Доказательство. Пусть M = (W, R, h) – модель Крипке, t  W – мир. Предположим выполнение M, t |= (А  В). Докажем, что А  В верно в мире t. С этой целью докажем, что из M, t |= А следует M, t |= В. Пусть u  W – мир, для которого (t, u)  R. Если верно M, t |= А, то M, u |= А. По предположению, M, t |= |= (А  В), значит, M, u |= А  В. Получаем из M, u |= А и M, u |= А  В, что M, u |= |= В. Теорема доказана.