Краткая методичка по логике

>      

Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания a₁,…, t_n нумеруются последовательно от 1 до k+е+m+n. Вспомним, что правила порождения теорем являются правилами вывода, что конечная индуктивная последовательность теорем является доказательством и что следующие девять правил, называемых основными, образуют достаточный набор правил вывода из аксиом: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости.

Такая форма изложения делает доказательство легко проверяемым, но практически не применяется из-за ее громоздкости.

Способы более компактного изложения формальной теории.

1. Последовательность a₁,…, r_e не записывается, потому что при достаточном навыке термы и формулы распознаются без построения их индуктивных последовательностей.

2. В последовательность t₁,…, t_n включаются теоремы из других доказательных текстов.

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. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнкта  pg, р и правило присоединения дизъюнкта р, 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	12  2<1
3 = 2 + 1	12  1  2  1 = 2
4 = 3 + 1	12  1  2  1 = 2
5 = 4 + 1	12  1 = 2

Заметим, что знак  можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы ₁₂  ₃(₃ = 0  ₁+ ₃ = ₂).

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

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

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

11	1 = 0 11 = 0	Правило подтверждения
12	1 = 0	Аксиома
13	11 = 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), (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)}, {(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. Указать истинное значение для высказываний 5=5, 55, 55, 55, 55, 55, Х0, Х+25, Х+Х6, Х-Х=0, Х0, X+Z=Z+X [ИЛЛИИЛЛППИИИ] и для каждых двух соседних высказываний выяснить, являются ли они равносильными [НДНДНДНДНДД].

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

3. Выяснить, являются ли аb, ab+3; ab, b0, a0 правилами вывода [ДД].

2.1 Для каждого из пяти знакосочетаний ; g; f f f; ₄₈ f g;  выяснить следуют ли в нем его знаки в алфавитном порядке [ДНДНД].

2.2 Для терма f(f(₁), f_, f(f_, _1, f(f))) составить индуктивную последовательность термов [f_, _1, f(f), f(f, _1, f(f) f(f(₁), f_, f(f_, _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 Для высказывания ₅g(₁, f(₂), ₁) составить индуктивную последовательность термов и высказываний [₁, ₂, f(₂), g(₁, f(₂), ₁), ₅ (g(₁, f(₂), ₁))].

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 обозначает высказывание (₁₂g(_2, f(₁, ₂)))g(f, f (₂))gg(₁). Индукцией по построению высказывания определить его истинностное значение на универсуме при такой интерпретации функциональных и предикатных знаков.

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	Л

Ответ:

2	p
3	Л
4	И

2.10 Указать истинностные значения высказываний 22Х3, Х3+4Х9, 7Х9Х=8, Х3Х3, Х(Х3)5=3, ₁₂(₂₁), ₂₁ (₂₁) [ИПИИИЛИ].

2.11 Для каждого из правил p, q, r, pqr; p, pp; pp, p ; pq, p, q; p, p; p, XP; XP, P; P, XP; 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