Тема . Дискретная математика
.05 Исчисление высказываний.
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела дискретная математика
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#62081

Показать, что система аксиом ИВ в гильбертовской форме избыточна. А именно, показать, что аксиома

A  : ¬ φ → (φ → ψ)
  8

следует уже из остальных аксиом.

Показать ответ и решение

Выведем сначала

{¬ φ,φ} ⊢ ψ

1. φ  - гипотеза;
2. φ → (¬ ψ → φ )  - A1   ;
3. ¬φ  - гипотеза;
4. ¬φ →  (¬ψ →  ¬φ)  - A1   ;
5.

φ, φ →  (¬ψ →  φ)

¬ ψ → φ

MP 1, 2.
6.

¬ φ, ¬φ →  (¬ ψ →  ¬φ)

¬ ψ → ¬ φ

MP 3, 4.
7. (¬ψ →  φ) → ((¬ψ →  ¬φ ) → ¬¬ψ )  - A7   ;
8.

¬ ψ → φ, (¬ ψ → φ ) → ((¬ ψ → ¬ φ) → ¬¬ ψ)

(¬ψ →  ¬φ ) → ¬¬ ψ

MP 5, 7.
9.

¬ ψ → ¬ φ, (¬ψ →  ¬φ) → ¬ ¬ψ

¬ ¬ψ

MP 6, 8.
10. ¬¬ ψ → ψ  - A9   ;
11.

¬¬ ψ, ¬¬ψ →  ψ

ψ

MP 9, 10.

Таким образом, мы вывели

{¬ φ,φ} ⊢ ψ

Но тогда по теореме о дедукции

{¬ φ} ⊢ φ → ψ

И ещё раз по теореме о дедукции

⊢ ¬φ →  (φ → ψ )

То есть эта последняя формула ¬ φ → (φ →  ψ)  выводится из пустого множества гипотез - чисто из аксиом ИВ.

Ответ:

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!