Для любого m существует функция f из натуральных чисел в натуральные числа такая, что. 1.34 Существует функция g из w ґ w в w такая, что g(m, 0) = 0, g(m, n + 1) = g(m, n) + m.
| f(0) = 0, |
| f(n + 1) = f(n) + m. |
1.34 Существует функция g из w ґ w в w такая, что
| g(m, 0) = 0, |
| g(m, n + 1) = g(m, n) + m. |
1.35 Такая функция g единственна.
Определение 5 (Произведение). Для этой функции g число g(m, n) называется произведением m и n и обозначается m · n .
Так, для любых натуральных чисел m и n
| m · 0 = 0, | (2) |
| m · (n + 1) = (m · n) + m. |
1.36 2 · 2 = 4.
1.37 m · n = n · m.
1.38 m · n = 0 тогда и только тогда, когда m = 0 или n = 0
Системы Пеано
Определение 6 (Система Пеано). Тройка <W, a, s> , где W – множество, a – элемент из W, а s – функция из W в W называется системой Пеано, если
- для любого x О W: s(x) № a,
- для любых x, y О W: если s(x) = s(y), то x = y,
- для любого подмножества A множества W если
1. a О A и
2. s(x) О A всегда, когда x О A,
тогда A = W.
Используя это определение, аксиомы 1–3 можно сформулировать кратко, сказав, что тройка <w, 0, s0>, где s0 обозначает функцию следования, является системой Пеано.
1.39 Определите систему Пеано <W, a, s> такую, что W = w \ {0}.
1.40 Найдите изоморфизм между системой Пеано <w, 0, s0> и системой Пеано, построенной в решении задачи 1.39.
1.41 Для любой системы Пеано <W, a, s> существует изоморфизм между <w, 0, s0> и <W, a, s>. Ошибка! Недопустимый объект гиперссылки.
Таким образом, любая система Пеано изоморфна системе натуральных чисел. В этом смысле аксиомы 1–3 дают полную характеризацию натуральных чисел.
4.7. Логика высказываний
Для понятия ``высказывание'' иногда используют термин ``пропозиция'', что является калькой с английского. Мы этот термин не используем, но говорим ``пропозициональный'' в смысле относящийся к логике высказываний. Центральными понятиями данной части являются пропозициональные формулы и пропозициональный вывод.
Объектный язык и метаязык
Сначала несколько общих замечаний. В логике важно различать два языка: тот, который является объектом нашего изучения, и тот, который мы используем, чтобы говорить об этом объекте. Первый называется объектным языком, второй – метаязыком. В нашем изложении логики высказываний объектный язык – это формальный язык пропозициональных формул, а метаязык – обычный неформальный язык математики – смесь русского и математических обозначений.
Пропозициональные формулы будут определены как конечные последовательности символов, взятых из определенного алфавита. Можно развить теорию конечных последовательностей на строго аксиоматической основе, но мы не будем здесь делать это. В доказательствах метатеорем мы будем свободны использовать любые хорошо известные свойства натуральных чисел которые нам могут потребоваться, не доказывая их на основе аксиом арифметики (из части 1).
Пропозициональные формулы
Пропозициональная сигнатура – это множество символов, называемых атомами. Символы (отрицание), & (конъюнкция), Ъ (дизъюнкция) и Й (импликация) называются пропозициональными связками; – унарная связка, а другие – бинарные.
Возьмём непустую пропозициональную сигнатуру s , которая не содержит ни пропозициональных связок, ни скобки (, ). Алфавит пропозициональной логики состоит из атомов сигнатуры s, пропозициональных связок и скобок. Под строкой мы понимаем конечную последовательность (строку) символов в этом алфавите.
Дата добавления: 2015-10-05; просмотров: 1012;