Краткая методичка по логике (стр. 7 из 10)

Ø1=0

х + 1= y + Þx = y

x + 0 = x

x + (y + 1) = (x + y) + 1

x×0 = 0

x×(y + 1) = x×y + x

Øx < 0

x < y + 1 Û x < y Ú x = y

p íx, 0ýÚ"(pÞíx, x + 1ý)Þ p

Здесь при записи аксиом использованы ранее перечисленные соглашения о компактизации изложения и известное соглашение о том, что знак умножения связывает сильнее знака сложения. Если такие соглашения не принимать, то к примеру первую аксиому следовало бы записать в виде Ø(g

(¦ ,¦ )).

Пример определяющих аксиом для новых нульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатных знаков >, £,³,¹ :

2 = 1 + 1	c1>c2 Ûc2<c1
3 = 2 + 1	c1£c2Ûc1<c2 Úc1 = c2
4 = 3 + 1	c1³c2Ûc1>c2 Úc1 = c2
5 = 4 + 1	c1¹c2ÛØc1 = c2

Заметим, что знак < можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы c₁<c₂ Û$c₃(Øc₃ = 0 Ùc₁+ c₃ = c₂).

Пример доказательного текста в формальной арифметике (k = 3, е = 6, m = 1, n = 3):

1	¦ ----------------------------------------------	Константа
2	¦ -----------------------------------	Константа
3	c1--------------------------------------------------	Переменная
4	g (¦ ,¦ )---------------------------------------	Предикат от 2,1
5	Ø(g (¦ ,¦ ))-----------------------------------	Отрицание 4
6	g (c1,¦ )----------------------------------------	Предикат от 3,1
7	Ø(g (c1,¦ ))-----------------------------------	Отрицание 6
8	$c1(g (c1,¦ )))--------------------------------	Подтверждение 7 по c1
9	(Ø(g (¦ ,¦ )))Þ$c1(Ø(g (c1,¦ ))))----	Импликация 5,8
10	Ø(g (¦ ,¦ ))-----------------------------------	5: аксиома
11	(Ø( g (¦ ,¦ )))Þ$c1(Ø(g (c1,¦ ))))----	9: пр. подт. 7, c1, 2
12	Ø(g (¦ ,¦ ))-----------------------------------	5: аксиома 10
13	$c1(Ø( g (c1,¦ )))----------------------------	8: пр. отделения для 12, 11

Компактизированный текст:

11	Ø1 = 0 Þ$c1Øc1 = 0-------------------------	Правило подтверждения
12	Ø1 = 0--------------------------------------------	Аксиома
13	$c1Øc1 = 0--------------------------------------	Правило отд. для 12, 11

Словесный вариант: «Если единица не равна нулю, то тем самым существует не равное нулю число. Но единица не равна нулю. Следовательно, существует число, не равное нулю».

Тема 7. Множества и функции.

В этой теме A, B, C, D, E, F, G, X, Y, Z, X₁, Z₁,…, X_n, Y_n, Z_n обозначают попарно различные переменные. Множество – это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xÎA означает, что объект х есть элемент множества A. Отрицание соотношения xÎA записывается в виде xÏA. Соотношение АÌВ означает, что А есть подмножество множества В, т.е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АÌВ записывается в виде АËВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается через {a|p}. Множество {x|"A(xÏA)} называется пустым множеством и обозначается символом Ø. Множество {x|x = x₁Ú…Úx = x_n} обозначается через {x₁,…,x_n}. Множество {x|xÎAÚxÎB} называется объединением множеств А, В и обозначается через АÈВ. Множество {x|xÎAÙxÎB} называется пересечением множеств А, В и обозначается через АÇВ. Множество {x|xÎAÙxÏB} называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через А&bsol;В.

Простейшиетеоремы: 3Ï{9, 7, 3}, {x+5|x² = 4} = {3, 7], AÏA, AÌA, …

Обозначения для некоторых множеств:

N - множество натуральных чисел

Z - множество целых чисел

R - множество действительных чисел

Упорядоченная n-ка объектов x₁,…,x_n обозначается через (x₁,…,x_n) и определяется так: (x₁) = x₁

(x₁, x₂) = {{x₁}, { x₁, x₂}}

(x₁, x_2, x₃) = ((x₁, x₂), x₃)

(x₁, x_2, x₃,x₄) = ((x₁, x₂, x₃), x₄)

………………………………..

Упорядоченная n-ка называется еще n-мерным упорядоченным набором, вектором, точкой, кортежем. Объект x₁ называется k-той компонентой или координатой n-мерного набора (x₁,…,x_n) и обозначается через koor

(x₁,…,x_n). Множество {x₁,…,x_n| x₁Îz₁Ù…Ù x_nÎz_n} называется декартовым произведением множеств z₁,…,z_n и обозначается через z₁´…´z_n. Если А - множество упорядоченных n-ок, то множество {x_k|(x₁,…,x_nÎA} называется k-той проекцией n-мерного множества А и обозначается через π А. Через Аⁿ обозначается множество А´…´А (n множителей). Соглашение: знаки ´, Ç, связывают сильнее чем È, &bsol;.

Простейшие теоремы: (x₁,…,x_n) = (y₁,…,y_n)Û x₁= y₁Ù…Ùx_n= y_n, (9, 9, 9)¹ (9, 9), p

(A´B´C´D´E) = C, {5. 7}² = {(5, 5), (5, 7), (7, 5), (7, 7)}, koor (5, 7, 9) = 9, koor (5, 7, 9) = koor (5, 7, 9) = koor (5, 7, 9) = H, {7}´{8, 5}´{9} = {(7, 8, 9), (7, 5,9)}. {4}⁵ = {(4, 4, 4, 4, 4)}, p {(1, 2, 3), (1, 3, 2), (2, 3, 4)} = {2, 3}. A´B´C = (A´B)´C.

Функцией называется множество, любой элемент которого есть упорядоченная двойка. Множество π

F называется областью определения или доменом функции F и обозначается dom F. Множество π F называется областью значений или ранжиром функции F и обозначается ran F. Если (x,y)ÎF, то y называется значением функции F в x и обозначается F(x). Если АÌdomF, то множество {y|$ÎAÙ(x, y)ÎF)} называется образом множества А относительно функции F и обозначается F[А]. Функция F в случае dom F = A и ran FÌB / ranF=B называется еще отображением множества А в/на множество В. Запись F:А®В означает что F есть отображение множества А в множество В. Функция F называется сужением функции G (на множество dom F), а функция G называется расширением функции F (на множество dom G), если F есть результат удаления из G всех тех (x, y), для которых xÏ dom F. Если F есть функция, то {(y, x)ï (x, y)ÎF} тоже есть функция, называемая обратной по отношению к F. Очевидно, что если функция G является обратной по отношению к функции F, то F является обратной по отношению к G. Если dom F есть множество упорядоченных n-ок, то функция F называется n-аргументной и вместо F((x₁,…,x_n)) используют более короткое обозначение F(x₁,…,x_n). Функция F называется однозначной, если из (x, y)ÎF и (x, z)ÎF следует y=z. Функция называется взаимно однозначной или биективной, если она сама и обратная к ней функция являются однозначными. Последовательностью называется однозначная функция F т.ч. dom F = N. Если F есть последовательность и nÎN, то F(n) называется n-м членом последовательности и обычно обозначается через F_n.