Задание 8. 8.1. Требуется доказать секвенцию |¾ ù ( А Þ В ) Þ А.

Решение: Здесь используются следующие свойства секвенций:

1) вывод секвенции Г |¾ АВ равносилен выводу двух секвенций:

Г |¾ А и Г |¾ В;

2) секвенция Г |¾ А Ú В равносильна секвенции Г, ù А |¾ В;

3) секвенция Г, А Ú В |¾ С равносильна секвенции Г, ù А Þ В |¾ С;

4) если Г |¾ А, то для любого В верна секвенция Г |¾ А.

Сначала ставим знак вопроса, так как секвенция не доказана.

|¾ А Ú (В Þ ù (АВ))?

Далее: ù А |¾ В Þ ù (АВ)?

ù А, В |¾ ù (АВ)?

ù А, В, АВ |¾?

ù А, В, А, В |¾?

Уже видим, что А, ù А |¾ (без знака вопроса). Поэтому “обратным ходом” получаем: ù А, А, В |¾ или АВ, ù А |¾, откуда

ù А, В, АВ |¾;

ù А, В |¾ ù (АВ);

ù А |¾ В Þ ù (АВ);

|¾ А Ú (В Þ ù (АВ)).

8.3. Требуется доказать равносильность формулы (ù А Þ В) º ù (ù А × ù В).

Решение: Наряду с предыдущими правилами используется свойство равносильных формул, а именно: А = В, если одновременно А Þ В и В Þ А.

В данном случае нужно доказать

а) |¾ (ù А Þ В) º ù (ù А × ù В)?

Последовательно записываем:

ù А Þ В |¾ ù (ù А × ù В)?

ù А Þ В, ù А × ù В |¾?

ù А Þ В, ù А, ù В |¾?

Видим, что можно применить правило т. р., поэтому вывод предложенной секвенции осуществляем так:

В, ù В |¾;

добавляем “лишние” формулы:

ù А Þ В, ù А, В, ù В |¾,

удаляем выводимую формулу В и далее “обратным” ходом получаем формулу а).

б) |¾ ù (ù А × ù В) Þ (ù А Þ В)?

ù (ù А × ù В) |¾ (ù А Þ В)?

ù (ù А × ù В), ù А |¾ В?

ù (ù А × ù В), ù А, ù В |¾?

ù А, ù В |¾ ù А × ù В?

ù А × ù В |¾ ù А × ù В.

Эта формула уже верна (так как А |¾ А). Поэтому обратным ходом получаем формулу б), а вместе с ней и нужную равносильность.