Краткая методичка по логике - (шпаргалка)
p>где t есть тавтология, q не имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n = 0.Тема 5. Эгалитарная логика
или логика предикатов с равенством, т. е. с двухместным предикатным символом g20, который интерпретируется как знак равенства. Т. о. в эгалитарной логике предикат g20(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g интерпретируется как знак равенства. Запись p1, …, pn¦=q1, …, qm означает, что каждое из высказываний q1, …, qm является логическим следствием из высказываний p1, …, pn т. е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p1, …, pn. Высказывание p называется логически истинным, если ¦=p т. е. если p является истинным в любой эгалитарной интерпретации. Правиламитождества, равенства, неотличимости называются следующие три правила соответственно:
Dg(x, x)
Dg(x1, y1)Щ…Щ g(xn, yn)Юg(f(x1, …, xn), f(y1, …, yn))
Dg2 (x1, y1)Щ…Щ g(xn, yn)Ю(g f(x1, …, xn)Ю(y1, …, yn))
Теорема об эгалитарной замене: пусть q есть результат замены в p некоторых вхождений терма a термом b; тогда если выражение g20(a, b) является истинным, то p равносильно q.
Теорема о транзитивности логического следствия: если p1, …, pn¦=q1, …, qm и q1, …, qm¦= r1, …, re, то p1, …, pn¦= r1, …, re. Теорема о расширении списка гипотез: если p1, …, pn¦= q, то p0, …, pn¦= q. Теорема дедукции: если высказывания p1, …, pn являются замкнутыми, то p1, …, pn¦= p тогда и только тогда когда к= p1Щ…Щ pnЮp. Теорема о конъюнктивизации гипотез: p1, …, pn¦= p тттк p1Щ…Щpn¦= p. Теорема о выводе в эгалитарной логике: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости образуют достаточный набор правил вывода в эгалитарной логике, т. е. p1, …, pn¦= p тттк p может быть получено из p1, …, pn с помощью этого набора правил. Теорема о сравнительной силе выводов. Если p является тавтологическим следствием из p1, …, pn, то p является кванторологическим следствием из p1, …, pn. Если p является кванторологическим следствием из р1, …, рn, то p является логическим следствием из р1, …, рn. Алгоритм – это…
Теорема о неразрешимости проблемы логического следствия (логической истинности): нельзя придумать алгоритм, который для любых высказываний p0, …, pn позволял бы разрешить вопрос о том, является или нет p0 логическим следствием из p1, …, pn. Полезно обратить внимание на то, что проблема тавтологического следствия является разрешимой с помощью истинностных таблиц.
Замечание последние семь теорем не исключают случай n = 0.
Замечание если не оговорено противное, слово логика понимается как эгалитарная логика.
Тема 6. Формальные теории
предназначены для четкого изложения и развития тех или иных отраслей человеческих знаний. Задать формальную теорию–значит задать ее функциональные и предикатные символы, а также аксиомы, т. е. некоторые из высказываний, которые являются истинными в данной отрасли знаний. Развивать формальную теорию–значит пополнять запас ее теорем, т. е. таких высказываний, которые являются логическими следствиями аксиом.
Изложение любой формальной теории в принципе можно оформить в виде книжек с доказательными текстами:
1
a1 - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
ь индуктивная
э последовательность
ю термов
…
ЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧ
k
ak - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
k+1
r1 - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
ь индуктивная
э последовательность формул
ю на основе a1, …, ak
…
ЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧ
k+е
re - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
k+е+1
s1 - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
ь аксиомы
э s1, …, sm есть
ю среди r1, …, re
…
ЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧ
k+е+m
sm - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
k+е+m+1
t1 - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
ь индуктивная
э последовательность теорем
ю t1, …, tn есть среди r1, …, re
…
ЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧЧ
k+е+m+n
tn - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч - Ч
Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания 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. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнктаD pЩg, р и правило присоединения дизъюнкта Dр, pЪg. 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
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 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
Заметим, что знак
¦ ---------------------------------------------
Константа
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, X1, Z1, …, Xn, Yn, Zn обозначают попарно различные переменные. Множество –это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xОA означает, что объект х есть элемент множества A. Отрицание соотношения xОA записывается в виде xПA. Соотношение АМВ означает, что А есть подмножество множества В, т. е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АМВ записывается в виде АЛВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается черезa. Множество x называется пустым множеством и обозначается символом O. Множество x = x1Ъ…Ъx = xn обозначается через {x1, …, xn}. Множество xОAЪxОB называется объединением множеств А, В и обозначается через АИВ. Множество x называется пересечением множеств А, В и обозначается через АЗВ. Множество x называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через А\В.
Простейшие теоремы: 3П{9, 7, 3}, x+5 = {3, 7], AПA, AМA, … Обозначения для некоторых множеств:
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Оz1Щ…Щ xnОzn называется декартовым произведением множеств z1, …, zn и обозначается через z1ґ…ґzn. Если А - множество упорядоченных n-ок, то множество (x1, …, xnОA называется k-той проекцией n-мерного множества А и обозначается через ? А. Через Аn обозначается множество Аґ…ґА (n множителей). Соглашение: знаки ґ, З, связывают сильнее чем И, \. Простейшие теоремы: (x1, …, xn) = (y1, …, yn)Ы x1= y1Щ…Щ xn= yn, (9, 9, 9)№ (9, 9), p(AґBґCґDґE) = 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)}, 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 называется образом множества А относительно функции 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((x1, …, xn)) используют более короткое обозначение F(x1, …, xn). Функция F называется однозначной, если из (x, y)ОF и (x, z)ОF следует y=z. Функция называется взаимно однозначной или биективной, если она сама и обратная к ней функция являются однозначными. Последовательностью называется однозначная функция F т. ч. dom F =N. Если F есть последовательность и nОN, то F(n) называется n-м членом последовательности и обычно обозначается через Fn.
Множество А называется бесконечным, если существует биективное отображение множестваNв множество А. Множество называется конечным, если оно не является бесконечным.
Простейшие теоремы: cos(0)=1, cos[{0}]= {1}, Аrccos и cos обратны друг к другу, функция arccos не является обратной к cos и является обратной к сужению функции cos на множество ran arccos.
