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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Задача 6)
(Задача 6)
Строка 56: Строка 56:
&phi;<sub>1</sub>(y) = S(y) &amp; &exist; m (R(m) &amp; M(m, y))
&phi;<sub>1</sub>(y) = S(y) &amp; &exist; m (R(m) &amp; M(m, y))
-
&phi;<sub>2</sub>(y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub>) = (S(y<sub>3</sub>) &amp; &forall; n (N(n) &exist; x<sub>1</sub> &exist; x<sub>2</sub> &exist; x<sub>3</sub> (E(x<sub>1</sub>, n, y<sub>1</sub>) &amp; E(x<sub>2</sub>, n, y<sub>2</sub>) &amp; E(x<sub>3</sub>, n, y<sub>3</sub>) &amp; (x<sub>3</sub> = x<sub>1</sub> &times; x<sub>2</sub>))))
+
&phi;<sub>2</sub>(y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub>) = (S(y<sub>3</sub>) &amp; &forall; n (N(n) &exist; x<sub>1</sub> &exist; x<sub>2</sub> &exist; x<sub>3</sub> (E(x<sub>1</sub>, n, y<sub>1</sub>) &amp; E(x<sub>2</sub>, n, y<sub>2</sub>) &amp; E(x<sub>3</sub>, n, y<sub>3</sub>) &amp; (x<sub>3</sub> = x<sub>1</sub> + x<sub>2</sub>))))
&not;(&exist; y (&phi;<sub>1</sub>(y) &amp; &forall; y<sub>1</sub> &forall; y<sub>2</sub> (&phi;<sub>1</sub>(y<sub>1</sub>) &amp; &phi;<sub>1</sub>(y<sub>2</sub>) &amp; &not;&phi;<sub>2</sub>(y<sub>1</sub>, y<sub>2</sub>, y))))
&not;(&exist; y (&phi;<sub>1</sub>(y) &amp; &forall; y<sub>1</sub> &forall; y<sub>2</sub> (&phi;<sub>1</sub>(y<sub>1</sub>) &amp; &phi;<sub>1</sub>(y<sub>2</sub>) &amp; &not;&phi;<sub>2</sub>(y<sub>1</sub>, y<sub>2</sub>, y))))

Версия 19:31, 10 января 2011

Содержание

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

Условные обозначения

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

Доступные предикаты

  • 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))))

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

Табличный вывод

Правила

  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 года | Алгоритмы решения задач

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