Краткая методичка по логике
> Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания a1,…, tn нумеруются последовательно от 1 до k+е+m+n. Вспомним, что правила порождения теорем являются правилами вывода, что конечная индуктивная последовательность теорем является доказательством и что следующие девять правил, называемых основными, образуют достаточный набор правил вывода из аксиом: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости.
Такая форма изложения делает доказательство легко проверяемым, но практически не применяется из-за ее громоздкости.
Способы более компактного изложения формальной теории.
1. Последовательность a1,…, re не записывается, потому что при достаточном навыке термы и формулы распознаются без построения их индуктивных последовательностей.
2. В последовательность t1,…, tn включаются теоремы из других доказательных текстов.
3. Для двухместного функционального или предикатного знака v используется операционная форма записи: вместо v(a,b) пишут (a)v(b).
4. При операционной форме записи принимается соглашение об упразднении некоторых пар скобок в соответствии с соглашением об убывании силы связи в последовательности: одноместный функциональный знак, двухместный функциональный знак, одноместный предикатный знак, двухместный предикатный знак, логический знак.
5. Используются специальные начертания для функциональных и предикатных знаков. Например в теории чисел: 0, 1, 2, 3 - нульместные функциональные знаки; , sin, cos - одноместные функциональные знаки; +, -, , - двухместные функциональные знаки; - двухместные предикатные знаки.
6. Используются знаковые фигуры. Например, х=3х обозначает сумму 3+4+5.
7. Вводится определяющая аксиома g(х1,...,х11) р для нового n-местного предикатного символа g. Здесь переменные х1,...,хn попарно различны, а высказывание р не имеет свободных вхождений переменных, отличных от х1,...,хn.
8. Вводится определяющая аксиома рх, ( х1,...,хn) для нового n - местного функционального символа в тех случаях, когда формула рх является теоремой. Здесь переменные х, х1,...,хn попарно различны, а р не имеет свободное вхождение переменных, отличных от х, х1,...,хn.
Теорема об определениях: если теория Т2 получена из теории Т1 путем добавления определяющей аксиомы для нового функционального или предикатного символа v то для каждой теоремы теории Т2 существует равносильная ей теорема теории Т1.
9. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнкта pg, р и правило присоединения дизъюнкта р, pg.
10. Применяются известные методы доказательства. Обоснование таких методов дается в учебниках логики. Например метод доказательства от противного основан на следующей теореме.
Теорема о доказательстве методом от противного: если формальная теория Т2 получена путем добавления аксиомы р к аксиомам теории Т1 и если формулы q, q являются теоремами теории Т2, то формула р является теоремой теории Т1.
Формальная арифметика формализует систему знаний о целых неотрицательных числах, использует в качестве исходных четыре функциональных и два предикатных знака
|
|
|
|
g |
g |
0 | 1 | + | | = | |
интерпретируемых в соответствии с их известными со школы специальными начертаниями, имеет такие аксиомы
1=0
х + 1= y + x = y
x + 0 = x
x + (y + 1) = (x + y) + 1
x0 = 0
x(y + 1) = xy + x
x 0
x y + 1 x y x = y
p x, 0(px, x + 1) p
Здесь при записи аксиом использованы ранее перечисленные соглашения о компактизации изложения и известное соглашение о том, что знак умножения связывает сильнее знака сложения. Если такие соглашения не принимать, то к примеру первую аксиому следовало бы записать в виде (g(, )).
Пример определяющих аксиом для новых нульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатных знаков , :
2 = 1 + 1 |
12 2<1 |
3 = 2 + 1 |
12 1 2 1 = 2 |
4 = 3 + 1 |
12 1 2 1 = 2 |
5 = 4 + 1 |
12 1 = 2 |
Заметим, что знак можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы 12 3(3 = 0 1+ 3 = 2).
Пример доказательного текста в формальной арифметике (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 11 = 0 |
Правило подтверждения |
12 |
1 = 0 |
Аксиома |
13 |
11 = 0 |
Правило отд. для 12, 11 |
Словесный вариант: «Если единица не равна нулю, то тем самым существует не равное нулю число. Но единица не равна нулю. Следовательно, существует число, не равное нулю».
Тема 7. Множества и функции.
В этой теме A, B, C, D, E, F, G, X, Y, Z, X1, Z1,…, Xn, Yn, Zn обозначают попарно различные переменные. Множество – это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xA означает, что объект х есть элемент множества A. Отрицание соотношения xA записывается в виде xA. Соотношение АВ означает, что А есть подмножество множества В, т.е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АВ записывается в виде АВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается через ap. Множество xA(xA)} называется пустым множеством и обозначается символом Ш. Множество {x|x = x1…x = xn} обозначается через {x1,…,xn}. Множество {x|xAxB} называется объединением множеств А, В и обозначается через АВ. Множество {x|xAxB} называется пересечением множеств А, В и обозначается через АВ. Множество {x|xAxB} называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через АВ.
Простейшие теоремы: 3{9, 7, 3}, {x+5x2 = 4} = {3, 7], AA, AA, …
Обозначения для некоторых множеств:
N - множество натуральных чисел
Z - множество целых чисел
R - множество действительных чисел
Упорядоченная n-ка объектов x1,…,xn обозначается через (x1,…,xn) и определяется так: (x1) = x1
(x1, x2) = {{x1}, { x1, x2}}
(x1, x2, x3) = ((x1, x2), x3)
(x1, x2, x3,x4) = ((x1, x2, x3), x4)
………………………………..
Упорядоченная n-ка называется еще n-мерным упорядоченным набором, вектором, точкой, кортежем. Объект x1 называется k-той компонентой или координатой n-мерного набора (x1,…,xn) и обозначается через koor(x1,…,xn). Множество x1,…,xn x1z1… xnzn} называется декартовым произведением множеств z1,…,zn и обозначается через z1…zn. Если А - множество упорядоченных n-ок, то множество xk(x1,…,xnA} называется k-той проекцией n-мерного множества А и обозначается через πА. Через Аn обозначается множество А…А (n множителей). Соглашение: знаки , , связывают сильнее чем , .
Простейшие теоремы: (x1,…,xn) = (y1,…,yn) x1= y1… xn= yn, (9, 9, 9) (9, 9), (ABCDE) = C, {5. 7}2 = {(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}5 = {(4, 4, 4, 4, 4)}, {(1, 2, 3), (1, 3, 2), (2, 3, 4)} = {2, 3}. ABC = (AB)C.
Функцией называется множество, любой элемент которого есть упорядоченная двойка. Множество πF называется областью определения или доменом функции F и обозначается dom F. Множество πF называется областью значений или ранжиром функции F и обозначается ran F. Если (x,y)F, то y называется значением функции F в x и обозначается F(x). Если А domF, то множество {yA(x, y)F)} называется образом множества А относительно функции F и обозначается FА. Функция F в случае dom F = A и ran FB / 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((x1,…,xn)) используют более короткое обозначение F(x1,…,xn). Функция F называется однозначной, если из (x, y)F и (x, z)F следует y=z. Функция называется взаимно однозначной или биективной, если она сама и обратная к ней функция являются однозначными. Последовательностью называется однозначная функция F т.ч. dom F = N. Если F есть последовательность и nN, то F(n) называется n-м членом последовательности и обычно обозначается через Fn.
Множество А называется бесконечным, если существует биективное отображение множества N в множество А. Множество называется конечным, если оно не является бесконечным.
Простейшие теоремы: cos(0)=1, cos{0} = {1}, Аrccos и cos обратны друг к другу, функция arccos не является обратной к cos и является обратной к сужению функции cos на множество ran arccos.
ЗАДАЧНИК-МИНИМУМ ПО ЛОГИКЕ
В квадратных скобках дается ответ к задаче, Д означает ДА, Н означает НЕТ, все высказывания о числах в задачах 1.1 – 6.4 являются арифметическими, т.е. высказываниями о целых неотрицательных числах.
Указать истинное значение для высказываний 5=5, 55, 55, 55, 55, 55, Х0, Х+25, Х+Х6, Х-Х=0, Х0, X+Z=Z+X [ИЛЛИИЛЛППИИИ] и для каждых двух соседних высказываний выяснить, являются ли они равносильными [НДНДНДНДНДД].
Для каждой из трех последовательностей 2, 3; 3, 2, 4, 5; 3, 2, 3, 6 выяснить, является ли она индуктивной относительно набора правил 3; Х, Х-1; Х,Z,X+[НДД].
Выяснить, являются ли аb, ab+3; ab, b0, a0 правилами вывода [ДД].
2.1 Для каждого из пяти знакосочетаний ; g; f f f; 48 f g; выяснить следуют ли в нем его знаки в алфавитном порядке [ДНДНД].
2.2 Для терма f(f(1), f, f(f, 1, f(f))) составить индуктивную последовательность термов [f, 1, f(f), f(f, 1, f(f) f(f(1), f, f(f, 1, f(f)))].
2.3 Пусть p, q, r обозначают нульместные предикаты. Для высказывания pqrpqr составить индуктивную последовательность высказываний [p, q, r, (q), ((q)(r), (p)(((q))(r)), (q)(r), (p)((q)(r)), ((p)(((q))(r)))((p)((q)(r)))].
2.4 Для высказывания 5g(1, f(2), 1) составить индуктивную последовательность термов и высказываний [1, 2, f(2), g(1, f(2), 1), 5 (g(1, f(2), 1))].
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 В высказывании pqrp восстановить все скобки [(p)((q)(((r))((p))))].
2.8 В высказываниях pqrprp, pq(rpr)p восстановить все скобки с помощью нумерации логических знаков и скобок в порядке их восстановления.
((p)(((q))(r)))(((p)(r))((p))), (p)((((q))((r)((p)(r)))((p)))
76p666422q2444r4677753p333r355511p1577p77776544q45552r2221p111r12566633p367
2.9 Пусть p обозначает высказывание (12g(2, f(1, 2)))g(f, f (2))gg(1). Индукцией по построению высказывания определить его истинностное значение на универсуме при такой интерпретации функциональных и предикатных знаков.
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 Указать истинностные значения высказываний 22Х3, Х3+4Х9, 7Х9Х=8, Х3Х3, Х(Х3)5=3, 12(21), 21 (21) [ИПИИИЛИ].
2.11 Для каждого из правил p, q, r, pqr; p, pp; pp, p ; pq, 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