Тема Дискретная математика

05 Исчисление высказываний.

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела дискретная математика

Решаем задачи

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

Задача 1#62076

Построить вывод из аксиом ИВ следующей формулы: $(φ → ψ ) → (φ → φ)$ .

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

1. $φ → (ψ → φ)$ - $A1$ ;
2. $(φ → (ψ → φ)) → ((φ → ψ ) → (φ → φ))$ - $A2$ ;
3.

	$φ → (ψ → φ ), (φ → (ψ → φ)) → ((φ → ψ) → (φ → φ ))$

	$(φ → ψ) → (φ → φ )$

MP 1, 2.

Ответ:

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#62078

Доказать обращение теоремы дедукции. А именно:

Пусть $Γ ⊢ (φ → ψ)$ для каких-то формул $φ$ и $ψ$ . Тогда, если расширить множество гамма формулой фи, то есть рассмотреть $^ Γ = Γ ∪ {φ}$ , то $^ Γ ⊢ ψ$ .

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

Докажем, что если из $Γ$ можно было вывести $φ → ψ$ , то из $Γ$ и добавленной к ней $φ$ можно будет вывести $ψ$ .

По условию нам дано, что $Γ ⊢ (φ → ψ )$ .

Давайте фиксируем этот вывод.

1. $φ 1$
2. $φ2$
...
n. $φ → ψ$ .

Где на каждом шаге каждая $φi$ - это либо аксиома, либо гипотеза из $Γ$ , либо $φi$ получена из предыдущих формул по правилу $M P$ .

Но теперь мы должны выести $ψ$ из множества гипотез $^Γ = Γ ∪{ φ}$ . Значит, мы можем теперь пользоваться нашей $φ$ как гипотезой.

Давайте допишем её следующим шагом как гипотезу к нашему выводу:

1. $φ1$
2. $φ2$
...
n. $φ → ψ$ ;
n+1. $φ$ .

Далее, мы можем применить к формулам с шагов n и n+1 Modus Ponens:

1. $φ1$
2. $φ2$
...
n. $φ → ψ$ ;
n+1. $φ$ ;
n+2.

	$φ, φ → ψ$

	$ψ$

MP.

То что у нас получилось - это вывод $ψ$ , но уже из множества гипотез $Γ ∪ {φ}$ .

Ответ:

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

Задача 3#62079

Доказать правило силлогизма:

Γ = {φ → ψ, ψ → 𝜃} ⊢ φ → 𝜃

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

Давайте вначале построим вывод

{φ → ψ, ψ → 𝜃,φ} ⊢ 𝜃

1. $φ → ψ$ - гипотеза;
2. $ψ → 𝜃$ - гипотеза;
3. $φ$ - гипотеза;
4.

	$φ, φ → ψ$

	$ψ$

MP 3, 1.
5.

	$ψ, ψ → 𝜃$

	$𝜃$

MP 4, 2.

И мы получили вывод формулы $𝜃$ из множества гипотез

{φ → ψ, ψ → 𝜃,φ }

Но тогда по теореме о дедукции отсюда следует, что можно вывести ${φ → ψ, ψ → 𝜃} ⊢ φ → 𝜃$ .

Ответ:

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

Задача 4#62080

Пусть $ψ$ - любая формула. Доказать, что

{φ, ¬φ} ⊢ ψ

(То есть если в гипотезах у нас есть какая-то формула вместе со своим отрицанием, то из такого множества гипотез можно вывести абсолютно любую формулу).

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

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.

Ответ:

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

Задача 5#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.

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

{¬ φ,φ} ⊢ ψ

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

{¬ φ} ⊢ φ → ψ

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

⊢ ¬φ → (φ → ψ )

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

Ответ: