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

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

Содержание 1 Построение предиката по утверждению 1.1 Условные обозначения 1.1.1 Доступные предикаты 1.2 Задача 1 1.3 Задача 2 1.4 Задача 3 1.5 Задача 4 1.6 Задача 5 1.7 Задача 6 2 Табличный вывод 2.1 Правила 2.1.1 Дополнительные правила 2.2 Задача 1 2.3 Задача 2 3 Метод резолюций 3.1 Задача 1

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

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

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

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

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

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

Правила

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 

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

1. , при условии, что переменная x свободна в φ(x) для терма t.
2. , где c — константа, которая не содержитсяв Γ, Δ или φ(x)
3. , где c — константа, которая не содержитсяв Γ, Δ или φ(x)
4. , при условии, что переменная x свободна в φ(x) для терма t.

Задача 1

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

Решение.

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

Задача 2

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

Решение.

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

Метод резолюций

Задача 1

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

Решение.

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