 |
|
Краткая методичка по логике
(( (1(g[pic]((1))) являются свободными, а третье и четвертое – связанными. Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f[pic]((5) является допустимым заменителем для (6 в высказывании g[pic](((5, ((6), и не является допустимым заменителем для (6 в высказывании ((5 (g[pic]((5, (6)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных. Теорема о всезначности переменной: р = И тттк (хр = И Теорема об отрицании обобщения и подтверждения: ((хр равносильно (х(р ((хр равносильно (х(р Теорема о взаимоисключении кванторов: (хр равносильно ((х(р (хр равносильно ((х(р Теорема о перестановочности кванторов: (х(ур равносильно (у(хр (х(ур равносильно (у(хр Типовые кванторы. Запись (qхр обозначает высказывание (х(q(р), а запись (qхр обозначает высказывание (х(q(р). Теорема о равносильной замене: пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r1 на высказывание r2; тогда если r1 и r2 равносильны, то р и q тоже равносильны. Позитивным высказыванием называется такое, которое не имеет вхождений знака (. Позитивной формой высказывания р называется любое равносильное ему позитивное высказывание . Теорема о позитивной форме: если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q; высказывание q можно построить с помощью теоремы о равносильной замене, теорем об исключении операций (, ( и теорем об отрицании для операций (, (, (, (, (. Пример построения позитивной формы отрицания высказывания: «для каждого положительного числа е существует положительное число ( т.ч. для каждого числа х из х<( следует, что х<е или х(1». ((е(((х(х<((х<е(х(1 = (e(((х((х<((х1) = « существует положительное число е т.ч. для каждого положительного числа ( существует число х т.ч. х<( и х(e и х>1». Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р0 является кванторологическим следствием из p1,…,pn тттк р0 может быть получено из р1,…,рn с помощью этих шести правил: ( t – правило тавтологии ( s, s ( r, r – правило отделения ((хр(p{x, a} – правило обобщения ( p{x, a} (( xp – правило подтверждения ( q(r, q ((хr – правило общевнесения ( r(q, ( xr(q – правило сущевнесения где t есть тавтология, q не имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n = 0. Тема 5. Эгалитарная логика или логика предикатов с равенством, т.е. с двухместным предикатным символом g20, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g20(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g[pic] интерпретируется как знак равенства. Запись p1, …, pn|=q1, …, qm означает, что каждое из высказываний q1, …, qm является логическим следствием из высказываний p1, …, pn т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p1, …, pn. Высказывание p называется логически истинным, если |=p т.е. если p является истинным в любой эгалитарной интерпретации. Правилами тождества, равенства, неотличимости называются следующие три правила соответственно: (g[pic](x, x) (g[pic](x1, y1)(…( g[pic](xn, yn)(g[pic](f(x1, …, xn), f(y1, …, yn)) (g2 (x1, y1)(…( g[pic](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 то для каждой теоремы теории
| |  скачать работу |
Краткая методичка по логике |
|
|
|
Погода в Алматы |
на 10 дней |
другой город |
|
