Для двухместного функционального или предикатного знака v используется операционная форма записи: вместо v(a,b) пишут (a)v(b)

3. Для двухместного функционального или предикатного знака v используется операционная форма записи: вместо v(a,b) пишут (a)v(b).

4. При операционной форме записи принимается соглашение об упразднении некоторых пар скобок в соответствии с соглашением об убывании силы связи в последовательности: одноместный функциональный знак, двухместный функциональный знак, одноместный предикатный знак, двухместный предикатный знак, логический знак.

5. Используются специальные начертания для функциональных и предикатных знаков. Например в теории чисел: 0, 1, 2, 3 - нульместные функциональные знаки; Ö, sin, cos - одноместные функциональные знаки; +, -, ´, /,­ - двухместные функциональные знаки; <, >, £, ³ - двухместные предикатные знаки.

6. Используются знаковые фигуры. Например, å_х=3х обозначает сумму 3+4+5.

7. Вводится определяющая аксиома g(х₁,...,х₁₁)Û р для нового n-местного предикатного символа g. Здесь переменные х₁,...,х_nпопарно различны, а высказывание р не имеет свободных вхождений переменных, отличных от х₁,...,х_n.

8. Вводится определяющая аксиома р{х, ¦( х₁,...,х_n)} для нового n - местного функционального символа ¦ в тех случаях, когда формула $рх является теоремой. Здесь переменные х, х₁,...,х_nпопарно различны, а р не имеет свободное вхождение переменных, отличных от х, х₁,...,х_n.

Теорема об определениях: если теория Т₂ получена из теории Т₁ путем добавления определяющей аксиомы для нового функционального или предикатного символа v то для каждой теоремы теории Т₂ существует равносильная ей теорема теорииТ₁.

9. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнкта D pÙg, р и правило присоединения дизъюнкта Dр, pÚg.

10. Применяются известные методы доказательства. Обоснование таких методов дается в учебниках логики. Например метод доказательства от противного основан на следующей теореме.

Теорема о доказательстве методом от противного: если формальная теория Т₂ получена путем добавления аксиомы Øр к аксиомам теории Т₁ и если формулы q, Øq являются теоремами теории Т₂, то формула р является теоремой теории Т₁.

Формальная арифметика формализует систему знаний о целых неотрицательных числах, использует в качестве исходных четыре функциональных и два предикатных знака

¦	¦	¦	¦	g	g
0	1	+	×	=	<

интерпретируемых в соответствии с их известными со школы специальными начертаниями, имеет такие аксиомы

Ø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} называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через А\В.

 

Простейшие теоремы: 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 множителей). Соглашение: знаки ´, Ç, связывают сильнее чем È, \.

Простейшие теоремы: (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.

Множество А называется бесконечным, если существует биективное отображение множества N в множество А. Множество называется конечным, если оно не является бесконечным.

Простейшие теоремы: cos(0)=1, cos[{0}] = {1}, Аrccos и cos обратны друг к другу, функция arccos не является обратной к cos и является обратной к сужению функции cos на множество ran arccos.

ЗАДАЧНИК-МИНИМУМ ПО ЛОГИКЕ

В квадратных скобках дается ответ к задаче, Д означает ДА, Н означает НЕТ, все высказывания о числах в задачах 1.1 – 6.4 являются арифметическими, т.е. высказываниями о целых неотрицательных числах.

1.1       Указать истинное значение для высказываний 5=5, 5¹5, 5>5, 5£5, 5³5, 5<5, Х<0, Х+2<5, Х+Х<6, Х-Х=0, Х³0, X+Z=Z+X [ИЛЛИИЛЛППИИИ] и для каждых двух соседних высказываний выяснить, являются ли они равносильными [НДНДНДНДНДД].

1.2       Для каждой из трех последовательностей 2, 3; 3, 2, 4, 5; 3, 2, 3, 6 выяснить, является ли она индуктивной относительно набора правил D3; DХ, Х-1; DХ,Z,X+[НДД].

1.3       Выяснить, являются ли Dа<b, a<b+3; Da³b, b³0, a³0 правилами вывода [ДД].

2.1 Для каждого из пяти знакосочетаний ØÚ; ¦g$; f f f; c₄c₈f g; "$ØÙÚÞÛ выяснить следуют ли в нем его знаки в алфавитном порядке [ДНДНД].

2.2 Для терма f(f(c₁), f_, f(f_, c_1, f(f))) составить индуктивную последовательность термов [f_, c_1, f(f), f(f, c_1, f(f) f(f(c₁), f_, f(f_, c_1, f(f)))].

2.3 Пусть p, q, r обозначают нульместные предикаты. Для высказывания pÚØqÙrÞpÞqÞr составить индуктивную последовательность высказываний [p, q, r, Ø(q), (Ø(q)Ù(r), (p)Ú((Ø(q))Ù(r)), (q)Þ(r), (p)Þ((q)Þ(r)), ((p)Ú((Ø(q))Ù(r)))Þ((p)Þ((q)Þ(r)))].

2.4 Для высказывания $c₅g(c₁, f(c₂), c₁)составить индуктивную последовательность термов и высказываний [c₁, c₂, f(c₂), g(c₁, f(c₂), c₁), $c₅ (g(c₁, f(c₂), c₁))].

2.5 Для каждого из семи обозначений а: f(a), g(a), g(a, b); Z; $Xg(X, X, Z); "Xf(X, X) выяснить, обозначает ли оно: Терм, Высказывание, Ни-то-ни-другое [TTBHTBH].

2.6 Для каждой из шести скобочных диад в высказывании ((p)Þ(q))Þ((r)Þ(s)) выяснить можно ли ее отбросить без нарушения смысла данного высказывания [HДДДДД].

2.7 В высказывании pÛqÚØrÙØp восстановить все скобки [(p)Û((q)Ú((Ø(r))Ù(Ø(p))))].

2.8 В высказываниях pÚØqÙrÞpÙrÚØp, pÚØqÙ(rÞpÙr)ÚØp восстановить все скобки с помощью нумерации логических знаков и скобок в порядке их восстановления.

é((p)Ú((ù(q))Ù(r)))Þ(((p)Ù(r))Ú(ù(p))), (p)Ú(((ù(q))Ù((r)Þ((p)Ù(r)))Ú(ù(p)))ù

ë76p666422q2444r4677753p333r355511p1577p77776544q45552r2221p111r12566633p367û

2.9 Пусть p обозначает высказывание ("c₁$c₂g(c_2, f(c₁, c₂)))Ùg(f, f (c₂))ÞgÚg(c₁). Индукцией по построению высказывания определить его истинностное значение на универсуме при такой интерпретации функциональных и предикатных знаков.

f	g		X	f(X)	g(X)		X	Y	f(X, Y)	g(X, Y)
3	И		3	4	Л		3	3	3	И
			4	3	И		3	4	4	И
							4	3	4	И
							4	4	4	Л

Ответ:

c2	p
3	Л
4	И

2.10 Указать истинностные значения высказываний 2<2ÞХ>3, Х<3+4ÛХ<9, 7<Х<9ÞХ=8, Х£3ÚХ>3, "Х(Х>3)Þ5=3, $c₁"c₂(c₂<c₁), "c₂$c₁ (c₂<c₁) [ИПИИИЛИ].

2.11 Для каждого из правил Dp, q, r, pÙqÙr; Dp, pÞp; DpÞp, p ; DpÚq, Øp, q; DØØØØp, p; Dp, $XP; D$XP, P; DP, "XP; D"XP; P выяснить является ли оно правилом вывода [ДДНДДДНДД].

2.12 Для каждого из высказываний g(a), "X g(X,C), $X(gÞ g), $XgÞ g, g, Ø g, gÛ g, g выяснить, является ли оно: предикатом [ДНННДННД], элементарным высказыванием [ДДДНДННД].

2.13 Для высказывания "X(gÞ g(X))Úg записать: все его компоненты [g,g(X), gÞg(X), "X(gÞg(X)), "X(gÞg(X))Úg], все его элементарные компоненты , все его пропозициональные компоненты [g, "X(gÞg(X))], все его предикатные компоненты [g, g(X)].

2.14 Записать все пропозициональные компоненты высказываний $XPÙ$ZP, $XPÙØ$ZP. [$XP, $ZP – если X, Z различные переменные, $c_nP – если X, Z обозначают одну и ту же переменную c_n].

3.1 Вычислить:

ИÚØЛÞИÞЛÙИÛИÛЛÚИÚЛÚØИÞЛÙИÙЛÙØИÙØЛÙИÙЛÙØИÙИÙЛ

[И].

3.2 Выяснить, является ли высказывание ØpÙqÙ(rÞs)Û(pÚØqÚrÙØs) тавтологией [Д].

3.3 Пусть p, q, r – различные элементы высказывания. Для каждого из высказываний pÞØrÚqÚp, pÞØr, rÞØpÚq выяснить, является ли оно тавтологией [ДНН] и является ли оно тавтологическим следствием двух других [ДНД].

3.4 Решить истинностное уравнение (pÞq)ÞØqÞp= Л с двумя неизвестными p, q [Л, Л].

 3.5 Из p, q, r составить высказывание, истинное только при p=q=r

[(pÛq) Ù(qÛr)].

4.1 Пусть Р обозначает g(x). Для каждого из высказываний pÞ$XP, $XPÞ P, $XPÞØP выяснить является ли оно кванторологически истинным [ДНН] и является ли оно кванторологическим следствием двух других [ДДН].

4.2 Для каждого вхождения переменной в высказывание из задачи 2.9 выяснить, является ли оно свободным или связанным [связанное, связанное, связанное, связанное, свободное, свободное].

4.3 Записать обозначенное через "c₃g(c_3, c₄) íc₄,¦(c₃)ý высказывание ["c₃g(c_3, ¦(c₃))].

4.4 Пусть P обозначает высказывание $c₃g(c_6, c₃)Ú "c₆g(c_6, c₃) Ú g(c_6, c₄).

Указать высказывания с обозначениями P íc₃, c₆ý, P íc₃, ¦(c₅)ý, P íc₃, c₃ý . [$c₃g(c_6, c₃)Ú "c₆g(c_6, c₆) Ù g(c_6, c₆), $c₃g(c_3, c₃)Ú "c₆g(c_6, c₃) Ù g(c_3, c₃), P, P].

4.5 Для каждого из терминов ¦(c₁), ¦(c₂), ¦(c₈), ¦(c₁, c₅, c₈), ¦ выяснить, является ли он допустимым заменителем для c₈ в высказывании $c₂g(c₈)Ú "c₅g(c₈) [ДНДНД].

4.6 Для каждого из высказываний [$c₁g(c₁), "c₂g(c_2, c₃), g(c_1, c_2, c₃), g(¦) выяснить, является ли оно замкнутым [ДННД] и является ли оно открытым [ННДД].