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

>


Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания 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(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


Заметим, что знак можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы 12 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 11 = 0

Правило подтверждения
12

1 = 0

Аксиома
13

11 = 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. Множество xA(xA)} называется пустым множеством и обозначается символом Ш. Множество {x|x = x1x = 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 и обозначается через z1zn. Если А - множество упорядоченных 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, то множество {yA(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 являются арифметическими, т.е. высказываниями о целых неотрицательных числах.

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

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

    3. Выяснить, являются ли а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 обозначают нульместные предикаты. Для высказывания pqrpqr составить индуктивную последовательность высказываний [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 В высказывании pqrp восстановить все скобки [(p)((q)(((r))((p))))].

2.8 В высказываниях pqrprp, pq(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