Упражнения

Упражнение 1

Модель $(M_1, x)$
Модель $(M_1, x)$

Верна ли в отмеченной интуиционсисткой модели Крипке $(M_1, x)$ (рисунок выше) следующая формула?

$p$

$\neg p$

$\neg \neg p$

$p \to q$

Упражнение 2

Модель $(M_2, x)$
Модель $(M_2, x)$

Верна ли в отмеченной интуиционсисткой модели Крипке $(M_2, x)$ (рисунок выше) следующая формула?

$p$

$\neg p$

$\neg \neg p$

$q$

$\neg q$

$\neg \neg q$

$p \to q$

$q \to p$

Упражнение 3

Какие из указанных формул НЕ являются законами интуиционистской логики высказываний?

  1. $\neg \neg p \to p$
  2. $p \to \neg \neg p$
  3. $p \vee \neg p$
  4. $\neg p \vee \neg \neg p$
  5. $\neg (p \wedge \neg p)$
  6. $(p \to q) \to (\neg p \vee q)$
  7. $(\neg p \vee q) \to (p \to q)$
  8. $\neg (p \to q) \to (p \wedge \neg q)$
  9. $(p \wedge \neg q) \to \neg (p \to q)$

Постройте для опровержимых формул контрмодели, а для общезначимых формул найдите доказательство в натуральном исчислении для интуиционистской логики высказываний.

Упражнение 4

Какие из указанных формул НЕ являются законами интуиционистской логики высказываний?

  1. $(p \to q) \to (\neg q \to \neg p)$
  2. $(p \to \neg q) \to (q \to \neg p)$
  3. $(\neg p \to q) \to (\neg q \to p)$
  4. $(\neg p \to \neg q) \to (q \to p)$
  5. $\neg (p \wedge q) \to (\neg p \vee \neg q)$
  6. $(\neg p \vee \neg q) \to \neg (p \wedge q)$
  7. $\neg (\neg p \vee \neg q) \to (p \wedge q)$
  8. $(p \wedge q) \to \neg (\neg p \vee \neg q)$
  9. $\neg (p \vee q) \to (\neg p \wedge \neg q)$
  10. $(\neg p \wedge \neg q) \to \neg (p \vee q)$
  11. $\neg (\neg p \wedge \neg q) \to (p \vee q)$
  12. $(p \vee q) \to \neg (\neg p \wedge \neg q)$

Постройте для опровержимых формул контрмодели, а для общезначимых формул найдите доказательство в натуральном исчислении для интуиционистской логики высказываний.

Упражнение 5

Докажите, что закон Пирса не является законом интуиционистской логики (постройте контрмодель):

\[((p\to q) \to p) \to p\]

Упражнение 6

Найдите доказательство для слабого закона Пирса в натуральном исчислении интуиционистской логики (используя только правила для импликации):

\[((((p\to q) \to p) \to p) \to q) \to q\]

Упражнение 7

Найдите результат перевода в $S4$ для следующих формул интуиционистской логики высказываний:

  1. $\neg p$
  2. $\neg \neg p$
  3. $p \wedge \neg q$
  4. $p \to q$
  5. $p \to \neg \neg p$
  6. $\neg \neg p \to p$