Математическая Логика, решение задач/variant 2004

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Содержание

[править] Построение предиката по утверждению

[править] Условные обозначения

  • почти все = все, кроме конечного числа;

[править] Доступные предикаты

  • R(x) — вещественное число;
  • N(x) — натуральное число;
  • S(y) — y — последовательность действительных чисел;
  • E(x, n, y) — x — элемент y с номером n;
  • A(p, y) — p — предельная точка последовательности y;
  • M(x, y) — x — предел последовательности y;
  • x < y, x = y — сравнение и равенство.

[править] Задача 1

Какова бы ни была последовательность действительных чисел и отрезок [a, b] действительных чисел, если бесконечно много элементов этой последовательности содержится в данном отрезке, то хотя бы одна предельная точка данной последовательности также сожержится в этом отрезке.

φ1 = (R(a) & R(b) & (a ≤ b))
φ2 = ∀ n1 (N(n1) & ∃ n2 (N(n2) & (n2 ≥ n1) & ∃ x1 (E(x1, n2, y) & ((a ≤ x1) & (x1 ≤ b))))
φ3 = ∃ p (A(p, y) & ((a ≤ p) & (p ≤ b)))

∀ a ∀ b ∀ y (S(y) & φ1 & φ2 & (S(y) & φ1 & φ2 → φ3))

[править] Задача 2

Какова бы ни была последовательность действительных чисел, найдется отрезок, содержащий все ее предельные точки.

∀ y  S(y) & ∃ a ∃ b (R(a) & R(b) & (a ≤ b) ∀ p (A(p, y) & (a ≤ p) & (p ≤ b))))

[править] Задача 3

Каков бы ни был отрезок [a,b] действительных чисел, если почти все элементы произвольной последовательности действительных чисел лежат вне этого отрезка, то и все предельные точки этой последовательности лежат вне этого отрезка.

φ1 = (R(a) & R(b) & (a ≤ b))
φ2 = ∃ n1 (N(n1) & ∀ n2 (N(n2) & (n2 ≥ n1) & ∀ x1 (E(x1, n2, y) & ((a > x1) ∨ (x1 > b))))
φ3 = ∀ p (A(p, y) & ((a > p) & (p > b)))

∀ a ∀ b ∀ y (S(y) & φ1 & φ2 & (S(y) & φ1 & φ2 → φ3))

[править] Задача 4

Какова бы ни была последовательность действительных чисел, если эта последовательность содержит отрицательный элемент, то найдется хотя бы одна неположительная предельная точка этой последовательности.

φ1 = ∃ x ∃ n (R(x) & N(n) & E(x, n, y) & (x < 0))
φ2 = ∃ p (A(p, y) & (p ≤ 0))

∀ y (S(y) & φ1 & (S(y) & φ1 → φ2))

[править] Задача 5

Каковы бы ни были две последовательности действительных чисел такие, что первая одна из них → 0, а другая ограничена, тогда из произведение тоже → 0.

φ1 = ∃ M (R(M) & ∀ n (N(n) & ∃ x (R(x) & E(x, n, y) & (|x| < M))))
φ2 = ∃ y3 (S(y3) & ∀ n (N(n) ∃ x1 ∃ x2 ∃ x3 (E(x1, n, y1) & E(x2, n, y2) & E(x3, n, y3) & (x3 = x1 × x2))))

∀ y1 ∀ y2 (S(y1) & S(y2) & M(0, y1) & φ1 & φ2 & (S(y1) & S(y2) & M(0, y) & φ1 & φ2 → M(0, y3)))

[править] Задача 6

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

φ1(y) = S(y) & ∃ m (R(m) & M(m, y))
φ2(y1, y2, y3) = (S(y3) & ∀ n (N(n) ∃ x1 ∃ x2 ∃ x3 (E(x1, n, y1) & E(x2, n, y2) & E(x3, n, y3) & (x3 = x1 + x2))))

¬(∃ y31(y) & ∀ y1 ∀ y21(y1) & φ1(y2) & ¬φ2(y1, y2, y3))))

[править] Табличный вывод

[править] Правила

  1. L\neg:\frac{<\neg\phi,\Gamma|\Delta>}{<\Gamma|\phi,\Delta>}
  2. R\neg:\frac{<\Gamma|\neg\phi,\Delta>}{<\phi,\Gamma|\Delta>}
  3. L\and:\frac{<\phi_1\and\phi_2,\Gamma|\Delta>}{<\phi_1,\phi_2,\Gamma|\Delta>}
  4. R\and:\frac{<\Gamma|\phi_1\and\phi_2,\Delta>}{<\Gamma|\phi_1,\Delta><\Gamma|\phi_2,\Delta>}
  5. L\lor:\frac{<\phi_1\lor\phi_2,\Gamma|\Delta>}{<\phi_1,\Gamma|\Delta><\phi_2,\Gamma|\Delta>}
  6. R\lor:\frac{<\Gamma|\phi_1\lor\phi_2,\Delta>}{<\Gamma|\phi_1,\phi_2,\Delta>}
  7. L\to:\frac{<\phi_1\to\phi_2,\Gamma|\Delta>}{<\phi_2,\Gamma|\Delta><\Gamma|\phi_1,\Delta>}
  8. R\to:\frac{<\Gamma|\phi_1\to\phi_2,\Delta>}{<\phi_1,\Gamma|\phi_2,\Delta>}

[править] Дополнительные правила

  1. L\forall:\frac{<\forall x\phi(x),\Gamma|\Delta>}{<\forall x\phi(x),\phi(x)\{^x/_t\},\Gamma|\Delta>}, при условии, что переменная x свободна в φ(x) для терма t.
  2. R\forall:\frac{<\Gamma|\forall x\phi(x),\Delta>}{<\Gamma|\phi(x)\{^x/_c\},\Delta>}, где c — константа, которая не содержитсяв Γ, Δ или φ(x)
  3. L\exist:\frac{<\exist x\phi(x),\Gamma|\Delta>}{<\phi(x)\{^x/_c\},\Gamma|\Delta>}, где c — константа, которая не содержитсяв Γ, Δ или φ(x)
  4. R\exist:\frac{<\Gamma|\exist x\phi(x),\Delta>}{<\Gamma|\exist x\phi(x),\phi(x)\{^x/_t\},\Delta>}, при условии, что переменная x свободна в φ(x) для терма t.

[править] Задача 1

С помощью метода семантических таблиц установить, общезначима ли формула:

\forall{x}\forall{y}(P(x)\to R(y))\to(\exist{y}P(y)\to\forall{x}R(x))

Решение.

\begin{array}{ccc}
<\empty|\forall{x}\forall{y}(P(x)\to R(y))\to(\exist{y}P(y)\to\forall{x}R(x))> \\
\darr R\to \\
<\forall{x}\forall{y}(P(x)\to R(y))|(\exist{y}P(y)\to\forall{x}R(x))> \\
\darr R\to \\
<\forall{x}\forall{y}(P(x)\to R(y)),\exist{y}P(y)|\forall{x}R(x)> \\
\darr R\forall \\
<\forall{x}\forall{y}(P(x)\to R(y)),\exist{y}P(y)|R(c_1)> \\
\darr L\exist \\
<\forall{x}\forall{y}(P(x)\to R(y)),P(c_2)|R(c_1)> \\
\darr L\forall \\
<\forall{x}\forall{y}(P(x)\to R(y)),\forall{y}(P(t_1)\to R(y)),P(c_2)|R(c_1)> \\
\darr L\forall \\
<\forall{x}\forall{y}(P(x)\to R(y)),\forall{y}(P(t_1)\to R(y)),(P(t_1)\to R(t_2)),P(c_2)|R(c_1)> \\
\darr L\to \\
<\forall{x}\forall{y}(P(x)\to R(y)),\forall{y}(P(t_1)\to R(y)),R(t_2),P(c_2)|R(c_1)>, <\forall{x}\forall{y}(P(x)\to R(y)),\forall{y}(P(t_1)\to R(y)),P(c_2)|P(t_1),R(c_1)> \\
\end{array}

Вторая таблица открыта, следовательно, формула не общезначима. (А разве нельзя провести унификацию терма t_2 = c_1, а t_1 = c_2?)

[править] Задача 2

С помощью метода семантических таблиц установить, общезначима ли формула:

(\exist{y}P(y)\to\forall{x}R(x))\to\forall{x}\forall{y}(P(x)\to R(y))

Решение.

\begin{array}{c}\begin{array}{ccc}
& <\empty|(\exist{y}P(y)\to\forall{x}R(x))\to\forall{x}\forall{y}(P(x)\to R(y))> \\
& \darr R\to \\
& <(\exist{y}P(y)\to\forall{x}R(x))|\forall{x}\forall{y}(P(x)\to R(y))> \\
& \darr L\to \\
<\forall{x}R(x)|\exist{y}P(y),\forall{x}\forall{y}(P(x)\to R(y))> & & <\empty|\exist{y}P(y),\forall{x}\forall{y}(P(x)\to R(y))> \\
\darr L\forall & & \darr R\exist \\
<\forall{x}R(x),R(t_1)|\forall{x}\forall{y}(P(x)\to R(y))> & & <\empty|\exist{y}P(y),P(t_2),\forall{x}\forall{y}(P(x)\to R(y))> \\
\darr R\forall & & \darr R\forall \\
<\forall{x}R(x),R(t_1)|\forall{y}(P(c_1)\to R(y))> & & <\empty|\exist{y}P(y),P(t_2),\forall{y}(P(c_2)\to R(y))> \\
\darr R\forall & & \darr R\forall \\
<\forall{x}R(x),R(t_1)|(P(c_1)\to R(c_3))> & & <\empty|\exist{y}P(y),P(t_2),P(c_2)\to R(c_4)> \\
\darr R\to & & \darr R\to \\
<\forall{x}R(x),R(t_1),P(c_1)|R(c_3)> & & <P(c_2)|\exist{y}P(y),P(t_2),R(c_4)> \\
\end{array}\end{array}

Вторая таблица открыта, следовательно, формула не общезначима. (Аналогично унифицировав t_1 = c_3 и t_2 = c_2 мы получим закрытую таблицу).

[править] Метод резолюций

[править] Задача 1

С помощью метода резолюций исследовать на противоречивость систему дизъюнктов S.

\begin{cases}
D_1 = P(y_1, z_1)\lor\neg R(x_1, b) \\
D_2 = \neg Q(b, x_2)\lor\neg P(z_2, y_2) \\
D_3 = R(c, x_3)\lor P(x_3, g(y_3)) \\
D_4 = Q(y_4, y_4)\lor\neg P(x_4, g(y_4)) \\
D_5 = \neg P(x_5, y_5)\lor Q(f(x_5), y_5)
\end{cases}

Решение.

(2)и(((1)и(5))и(3)) склеить в !(z2, g(b)), (1)и(3) склеить в P(b, g(b)).

\begin{array}{l}
D^'_1 - D_1, D_5: R(x_1, b)\lor Q(f(x_5), x_5) \\
D^'_2 - D^'_1, D_3: P(b, g(y_3))\lor Q(f(x_5), x_5) \\
D^'_3 - D_2, D_4: \neg P(z_2, y_2) \lor \neg P(x_4, g(y_4)) \\
D^'_4 - D^'_3: \neg P(z_2, y_2) \\
D^'_5 - D_1, D_3: P(b, y_3)\lor P(y_1, z_1) \\
D^'_6 - D_1, D_3: P(b, y_3) \\
D^'_7 - D^'_4, D^'_6: []
\end{array}


Математическая Логика


Лекции

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

Сентябрь
24 25 26
Октябрь
02 03 10 17 24 31
Ноябрь
07 14 21 28
Декабрь
05 12 19
Семинары

01 02 03 04 05 06 07


Календарь

Сентябрь
26
Октябрь
10 24
Ноябрь
07 21
Декабрь
05 19

Ссылки
Официальная страница курса | Задачи
Проведение экзамена | Решение задач: Решение задач методички | Решение задач варианта экзамена 2004 года | Алгоритмы решения задач

Личные инструменты
Разделы