Математическая Логика, решение задач/variant 2004
Материал из eSyr's wiki.
(→Задача 5) |
м (→Табличный вывод) |
||
Строка 68: | Строка 68: | ||
# <math>L\lor:\frac{<\phi_1\lor\phi_2,\Gamma|\Delta>}{<\phi_1,\Gamma|\Delta><\phi_2,\Gamma|\Delta>}</math> | # <math>L\lor:\frac{<\phi_1\lor\phi_2,\Gamma|\Delta>}{<\phi_1,\Gamma|\Delta><\phi_2,\Gamma|\Delta>}</math> | ||
# <math>R\lor:\frac{<\Gamma|\phi_1\lor\phi_2,\Delta>}{<\Gamma|\phi_1,\phi_2,\Delta>}</math> | # <math>R\lor:\frac{<\Gamma|\phi_1\lor\phi_2,\Delta>}{<\Gamma|\phi_1,\phi_2,\Delta>}</math> | ||
- | # <math>L\to:\frac{<\phi_1\to\phi_2,\Gamma|\Delta>}{<\phi_2,\Gamma|\phi_1,\Delta>}</math> | + | # <math>L\to:\frac{<\phi_1\to\phi_2,\Gamma|\Delta>}{<\phi_2,\Gamma|\Delta><\Gamma|\phi_1,\Delta>}</math> |
# <math>R\to:\frac{<\Gamma|\phi_1\to\phi_2,\Delta>}{<\phi_1,\Gamma|\phi_2,\Delta>}</math> | # <math>R\to:\frac{<\Gamma|\phi_1\to\phi_2,\Delta>}{<\phi_1,\Gamma|\phi_2,\Delta>}</math> | ||
Строка 99: | Строка 99: | ||
<\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)> \\ | <\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 \\ | \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)|P(t_1),R(c_1)> \\ | + | <\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}</math> | \end{array}</math> | ||
- | Пересечение Γ и Δ непусто (при t<sub>1</sub> = c<sub>2</sub> | + | Пересечение Γ и Δ непусто (при t<sub>1</sub> = c<sub>2</sub> и t<sub>2</sub> = c<sub>1</sub>). Получили закрытую таблицу, следовательно, формула общезначима. |
Строка 112: | Строка 112: | ||
'''Решение.''' | '''Решение.''' | ||
- | <math>\begin{array}{ccc} | + | <math>\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))> \\ | + | & <\empty|(\exist{y}P(y)\to\forall{x}R(x))\to\forall{x}\forall{y}(P(x)\to R(y))> \\ |
- | \darr R\to \\ | + | & \darr R\to \\ |
- | <(\exist{y}P(y)\to\forall{x}R(x))|\forall{x}\forall{y}(P(x)\to R(y))> \\ | + | & <(\exist{y}P(y)\to\forall{x}R(x))|\forall{x}\forall{y}(P(x)\to R(y))> \\ |
- | \darr L\to \\ | + | & \darr L\to \\ |
- | <\forall{x}R(x)|\exist{y}P(y),\forall{x}\forall{y}(P(x)\to R(y))> | + | <\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 L\forall \\ | + | \darr R\forall & & \darr R\forall \\ |
- | <\forall{x}R(x),R(t_1)| | + | <\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\forall \\ | + | \darr R\to & & \darr R\to \\ |
- | <\forall{x}R(x),R(t_1)|\exist{y}P(y),P(t_2),\forall{y}(P( | + | <\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)> \\ |
- | \darr R\forall \\ | + | \end{array}\end{array}</math> |
- | <\forall{x}R(x),R(t_1)|\exist{y}P(y),P(t_2), | + | |
- | \darr R\to \\ | + | |
- | <\forall{x}R(x),R(t_1),P(c_1)|\exist{y}P(y),P(t_2),R( | + | |
- | \end{array}</math> | + | |
- | Пересечение Γ и Δ непусто (при t<sub>1</sub> = c<sub> | + | Пересечение Γ и Δ непусто (при t<sub>1</sub> = c<sub>3</sub> и t<sub>2</sub> = c<sub>2</sub>). Получили закрытую таблицу, следовательно, формула общезначима. |
{{Курс Математическая Логика}} | {{Курс Математическая Логика}} |
Версия 09:44, 22 января 2008
Содержание |
Построение предиката по утверждению
Условные обозначения
- почти все = все, кроме конечного числа;
Доступные предикаты
- 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 → φ4))
Задача 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 = ∀ n (N(n) & ∃ x ∃ M (R(M) & 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, 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)))) ¬(∃ y (φ1(y) & ∀ y1 ∀ y2 (φ1(y1) & φ1(y2) & ¬φ2(y1, y2, y))))
Табличный вывод
Правила
Дополнительные правила
- , при условии, что переменная x свободна в φ(x) для терма t.
- , где c — константа, которая не содержитсяв Γ, Δ или φ(x)
- , где c — константа, которая не содержитсяв Γ, Δ или φ(x)
- , при условии, что переменная x свободна в φ(x) для терма t.
Задача 1
С помощью метода семантических таблиц установить, общезначима ли формула:
Решение.
Пересечение Γ и Δ непусто (при t1 = c2 и t2 = c1). Получили закрытую таблицу, следовательно, формула общезначима.
Задача 2
С помощью метода семантических таблиц установить, общезначима ли формула:
Решение.
Пересечение Γ и Δ непусто (при t1 = c3 и t2 = c2). Получили закрытую таблицу, следовательно, формула общезначима.
|
|
Ссылки
Официальная страница курса | Задачи
Проведение экзамена | Решение задач: Решение задач методички | Решение задач варианта экзамена 2004 года | Алгоритмы решения задач