Osnovy_filosofii_uchebnik_dlya_bakalavrov
.pdfЛогика
Вопросы для самоконтроля
1.Что такое терм?
2.Что такое модель перво порядковой логи ки преди катов?
3.Дайте опре деление форму лы? Обра тите внима ние, что оно строит ся индук тивно.
4.Сформу лируйте усло вия истин ности для логи ки преди катов перво го поряд ка.
5.Объяс ните значение того, что опре деление истин ности фор мулы поко ится на класси ческой теории исти ны.
6.Сформу лируйте усло вия ложно сти форму лы в моде ли язы ка логи ки преди катов.
Литература
1.Боча ров В. А., Маркин В. И. Осно вы логи ки. М., 1998, 1999, 2000, 2002, 2004. Гл. 3, § 1, 2.
2.Войшвил ло Е. К.Симво лическая логи ка. Класси ческая и реле вант ная. М., 1989. Гл. 2.
3.Клини С. Мате матическая логи ка. М., 1973. Гл. 2, § 16–20.
4.Мендель сон Э. Введе ние в мате матическую логи ку. М., 1976, 1984.
Гл. 2, § 1–3.
5.Соло духин О. А. Логи ка. Ростов н/Д, 2000. Гл. 5, (5.1–5.2).
5. Теория доказательств
Аксиоматическая система логики предикатов первого порядка
Форма лизовать логи ку преди катов в виде аксио матической систе мы озна чает:
– указать систе му акси ом;
– дать прави ла выво да;
– сформу лировать поня тия дока зательства и дока зуемой фор мулы .
Аксио мами класси ческой логи ки преди катов явля ются схемы
акси ом логи ки выска зываний и схемы акси ом собст венно логи ки преди катов.
Аксиомы логики высказываний
А1. А → (В → А); А2. (А → (В → С)) → ((А → В) → (А → С)); А3. А В → А; А4. А В → В;
151
Раздел I. Основы фундаментальной философии
А5. (А → В) → ((А → С) → (А → В С)); А6. А → А В; А7. В → А В;
А8. (А → С) → ((В → С) → (А В → С));
А9. (А → В) → ( В → А); А10. А → А; А11. А → А.
Аксиомы логики предикатов
Ак1. А (t) → xA (x), терм t свобо ден для х в А (х). Ак2. xA (x) → A (t), терм t свобо ден для х в А (х).
Ак3. х (А (х) → В) → ( хА (х) → В), х не входит свобод но в форму лу В.
Ак4. х (В → А (х)) → (В → хА (х)), х не входит свобод но в форму лу В.
Правила вывода (мета знак «d» озна чает, что форму ла дока зуема ).
П1. (модус поненс )
d А, d А → В . d В
П2. (обобще ния )
d А (х) . d хА (х)
П3. (подста новки). В любую из аксио му А1. – А11. вместо вхо жде ния како го-то симво ла выска зывания разре шается подста вить произ вольную форму лу логи ки преди катов соблю дая такое усло вие: одна и та же форму ла логи ки преди катов должна подстав ляться на место каж дого вхож дения фикси рованного симво ла вы сказы вания в аксио му.
Коммен та рий к П3. Напри мер , в А8. символ «С» входит три жды . Тогда при подста нов ке каж дое вхож де ние симво ла С заме няет ся одной и той же форму лой логи ки преди ка тов .
Коммен тарий к Ак1и Ак2. Требо вание «терм t свобо ден для х в А (х)» суще ственно. Напом ним, что терм – это констан та или инди видная пере менная. Если мы нару шим это требо вание, то из истин ной форму лы можем полу чить ложную форму лу. Возьмем арифме тические утвер ждения, представ ленные в языке логи ки преди катов, и нару шим указан ное требо вание:
152
Логика
х у (х = у)) → у (у = у).
В левой части импли кации имеем обще значимое форму лу (лю бые два различ ных числа не явля ются равны ми), в правой час ти – ложная форму ла (любое число не равно само му себе ). Ана логич но можно подоб рать пример Ак1.:
у (5 < у) → у (у < у).
Левая часть импли ка ции – истин ная форму ла , где «5» – чи словая констан та , а правая часть импли ка ции – ложная (так как утвер жда ет суще ст во ва ние числа меньшо го само го себя ). Заме тим, что в приме рах знаки = и < – это двухме ст ные арифме ти ческие преди ка ты .
Определение 1 (дока за тель ст ва ). Дока за тель ст вом назы ва ет ся такая после до ва тель ность формул , в кото рой любая форму ла яв ляет ся либо аксио мой , либо форму лой , полу чен ной из преды ду щих по одно му из правил выво да .
Определение 2(дока зуемой форму лы). Послед няя форму ла в по следо вательности формул , назы ваемой дока зательством, явля ется дока зуемой форму лой.
Аксио ма ти че ская систе ма должна удовле тво рять неко то рым ме тодо ло ги че ским требо ва ни ям , форму ли руе мым в виде мета те о рем , т. е. теоре мах об аксио ма ти че ской систе ме .
Теорема 1 (о непро тиворечивости). Аксио матическая систе ма перво порядковой логи ки непро тиворечива, т. е. не суще ствует фор мулы такой , что d А и d А.
Теорема 2 (коррект но сти ). Любая дока зуе мая форму ла в этой систе ме – обще зна чи ма .
Теорема 3 (о полно те). Любая обще значимая форму ла в этой систе ме – дока зуема.
Дока за тель ст во этих теорем приво дит ся в более обшир ных кур сах логи ки .
Заме чание.Влоги ческой лите ратуре исполь зуется и другая тер мино логия: теоре мой о полно те назы вается объе динение двух тео рем – теоре мы 2 и теоре мы 3.
Натуральное исчисление логики предикатов
Постро ить нату раль ное исчис ле ние для логи ки преди ка тов оз нача ет :
– дать прави ла выво да;
153
Раздел I. Основы фундаментальной философии
– сформу лировать поня тия выво да и выво димой форму лы.
К прави лам выво да логи ки выска зываний добав ляются собст венно прави ла выво да логи ки преди катов.
Правила вывода
Прави ла выво да делят ся на прави ла введе ния логи ческих связок и кванто ров и удале ния логи ческих связок и кванто ров. В форму лиров ке правил «В:» сокра щает слово «Введе ние», а «У:» – «Удале ние».
В: А |
; |
|
В: В |
|
|
; |
У: Г, А В; Г, А d С Г, В d С ; |
||||||||||||||
|
А В |
|
|
|
|
|
А В |
|
|
|
|
|
|
|
Г d С |
|
|||||
В: А, В |
|
; |
У: А В ; |
У: А В ; |
|||||||||||||||||
|
|
|
А В |
|
|
|
|
|
А |
|
|
|
|
|
|
|
В |
|
|||
В: → |
Г, А d В |
; У: → |
А, А → В |
; |
|
||||||||||||||||
|
|
|
Г d А → В |
|
|
|
|
|
|
В |
|
|
|||||||||
У: А; |
|
|
В: |
Г, А d В; Г, А d В |
; |
||||||||||||||||
|
|
|
А |
|
|
|
|
|
|
|
Г d В |
|
У (слабое ): А, А
|
|
|
В |
В: |
Г d А (х) |
; |
|
|
Г d хА (х) |
|
;
У: хА (х) ;
А (t)
В: А (t) |
; |
У: Г, А (х) d С . |
||||
|
хА (х) |
|
|
|
Г, хА (х) d С |
|
В прави лах У: и В: термин t свобо ден для х в А (х); в пра виле В: пере мен ная х не входит свобод но в форму лы из множе ства Г; в прави ле У: пере мен ная х не водит свобод но в форму лу С и форму лы из множе ст ва Г.
Определение 1 (выво да ). Выво дом назы ва ет ся после до ва тель ность формул , в кото рой любая форму ла явля ет ся либо посыл кой , либо форму лой , полу чен ной из преды ду щих по прави лам выво да .
Определение 2 (выво димой форму лы). Послед няя форму ла в вы воде назы вается выво димой форму лой.
Коммен та рии к прави лам выво да
Над чертой прави ла – это посыл ки, под чертой прави ла – за ключе ние. Прави ла делят ся на прави ла прямо го выво да и прави
154
Логика
ла косвен но го выво да . В прави лах косвен но го выво да в посыл ках исполь зу ет ся знак выво ди мо сти «d», кото рый озна ча ет , что стро ятся вспомо га тель ные выво ды . Прави ло В: → предпо ла га ет дока затель ст во теоре мы дедук ции .
Методические рекомендации
1.Изучи те все опре деления, и разбе рите их на конкрет ных приме рах.
2.На конкрет ных приме рах разбе рите огра ничения вхож де ния терма в аксио мы и соот ветствующие прави ла выво да, а так же огра ничения на пере менную «х» в соот ветствующих прави лах выво да.
3.На семи нарских заня тиях научи тесь пользо ваться аксио ма ми и прави лами нату рального выво да, т. е. научи тесь строить до каза тельства и выво ды.
Вопросы для самоконтроля
1.Что назы вается дока зуемой и выво димой форму лой?
2.Как устрое на аксио матическая систе ма?
3.Какой смысл мето дологических теорем об аксио матической систе ме?
4.Чем отли чаются косвен ные прави ла выво да от прямых ?
Литература
1. Войшвил ло Е. К.Симво ли че ская логи ка . Класси че ская и реле вант
ная. М., 1989. Гл. 4.
3.Клини С. Мате матическая логи ка. М., 1973. Гл. 2, § 21–27.
4.Мендель сон Э. Введе ние в мате матическую логи ку. М., 1976, 1984.
Гл. 2. § 3–7.
5.Соло духин О. А. Логи ка. Ростов н/Д, 2000. Гл. 5, (5.3).
6.Формализация логики предикатов методом аналитических таблиц
Метод анали ти че ских таблиц явля ет ся опро вер гаю щей проце дурой . Поиск обосно ва ния обще зна чи мо сти форму лы осуще ст в ля ется по опре де лен ным прави лам и начи на ет ся с предпо ло же ния , что форму ла не обще зна чи ма . Это предпо ло же ние ведет к проти воре чию , если форму ла на самом деле обще зна чи ма .
155
Раздел I. Основы фундаментальной философии
Логи ка преди катов нераз решима: не суще ствует эффек тив ной проце дуры (алго ритма), кото рый позво ляет в конеч ное чис ло шагов прове рить обще значимость формул логи ки преди катов. Это объяс няется тем, что надо рассмот реть все моде ли, каж дая из кото рых может содер жать беско нечную область и всевоз мож ные припи сывания значе ний пере менным, на каж дом из кото рых форму ла прини мает значе ние «истин но». Но логи ка выска зыва ний разре шима на осно вании таблиц истин ности. Анали ти ческие табли цы на осно вании рассу ждения от против ного позво ляют найти модель с конеч ной обла стью, в кото рой форму ла оп ровер гается, если она обще значима.
Прави ла редук ции логи ки преди катов надстраи ваются над прави лами редук ции логи ки выска зываний, так как и в логи ке преди катов мы исполь зуем логи ческие связки .
Правила редукции
: А В ; |
|
|
( ) →: (А В); |
: А В |
; |
( ): (А В); |
( ): А ; |
|
||||||||||||
|
|
А, В |
|
|
|
|
|
А | В |
|
А | В |
|
|
|
|
А, В |
|
А |
|
|
|
→: А →В |
; |
(→): (А →В) |
; |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
А | В |
|
|
|
|
А, В |
|
|
|
|
|
|
|
|
|
|
|
|
|
: хА (х) |
; |
( ): хА (х); : хА (х) ; |
( ): |
хА (х) |
. |
|||||||||||||||
|
|
хА (х), А (а ) |
|
А (в) |
|
|
А (в) |
|
|
хА (х), А (а ) |
|
|||||||||
|
|
|
|
|
|
к |
|
|
|
|
|
|
|
|
|
|
|
|
к |
|
Форму ла, распо ложенная над чертой прави ла, назы вается по сылкой прави ла редук ции, а форму ла под чертой прави ла – назы вает ся заклю чением прави ла. Верти кальная черта в заклю чении прави ла озна чает ветвле ние резуль тата приме нения прави ла ре дукции (прави ла с ветвле нием). Каж дое прави ло редук ции, кро ме правил : и ( ):, разби вает форму лу посыл ки на подфор мулы за счет устра нения логи ческой связки .
Прави ла ( ): и : вводят (при построе нии анали тической таб лицы форму лы) новые констан ты. Прави ла : и ( ): исполь зуют старые (преж де введен ные) констан ты. Если структу ра форму лы та кова , что выну ждает приме нить внача ле прави ло : или ( ):, то мы вводим произ вольную констан ту, а дальше дейст вуем на осно вании осталь ных правил , т. е. вводим на осно вании правил ( ): и : новые констан ты. В ходе построе ния анали тической табли цы
156
Логика
неко то рой форму лы она разла га ет ся на списки формул , представ ляющие собой подфор му лы исход ной форму лы .
Определение 1(анали ти че ской табли цы ). Анали ти че ской таб лицей назы ва ет ся конеч ная или беско неч ная после до ва тель ность строк С1, … Ск, … списков формул такая , что каж дая после дую щая строка полу ча ет ся из преды ду щей примене ни ем прави ла редук ции .
Заме чание. Отме тим, что если мы приме няем прави ло редук ции с ветвле нием, то мы полу чаем два списка формул .
Определение 2 (замкну то го списка формул ). Список формул на зыва ет ся замкну тым , если в нем встреча ет ся неко то рая форму ла и ее отри ца ние , т. е. А и А (проти во ре чие ).
Определение 3 (завер шенного списка ). Список формул назы вает ся завер шенным, если к форму лам этого списка невоз можно при менять прави ла редук ции, т. е в списке встреча ются атомар ные форму лы или отри цание атомар ных формул .
Определение 4 (замкну той табли цы ). Анали ти че ская табли ца замкну та , если все ее списки формул замкну ты (проти во ре чивы ).
Определение 5 (завер шенной табли цы). Анали тическая табли ца назы вается завер шенной, если она замкну та или имеет завер шенные списки формул .
Определение 6 (обще зна чи мой форму лы в терми нах анали ти ческой табли цы ). Форму ла А назы ва ет ся обще зна чи мой , если ее анали ти че ская замкну та .
Заме чание. Завер шенный список или завер шенная табли ца не обяза тельно замкну та, т. е. может быть замкну той, но не являть ся проти воречивой. Доста точно постро ить анали тическую табли цу для выпол нимой форму лы, чтобы в этом убедить ся.
Методические рекомендации
1.Надо обна ружить связь анали тических таблиц логи ки выска зыва ний с обыкно венными табли цами истин ности.
2.Усвой те разли чие меж ду прави лами, кото рые вводят новые констан ты и прави лами, кото рые не вводят новых констант , а ис пользу ют преж де введен ные констан ты.
3.Усвой те опре деления и подбе рите соот ветствующие этим оп реде лениям приме ры.
157
Раздел I. Основы фундаментальной философии
Вопросы для самоконтроля
1.Что такое анали тическая табли ца?
2.В чем разли чие меж ду прави лами с ветвле нием и прави ла ми без ветвле ния?
3.Может ли список формул быть завер шенным, но не быть проти воречивым?
4.Что полу чится, если мы постро им анали тическую табли цу для проти воречивой форму лы, но не будем рассу ждать от против ного , т. е не поста вим отри цание перед форму лой.
Литература
1.Боча ров В. А., Маркин В. И. Осно вы логи ки. М., 1998, 1999, 2000, 2002, 2004. Гл. 3, § 3.
2.Войшвил ло Е. К.Симво лическая логи ка. Класси ческая и реле вант ная. М., 1989. Гл. 2, § 4, 5.
7. Неклассическая логика
Основ ные виды неклас сических логик : модаль ные, много знач ные, интуи ционистская, реле вантная логи ки.
7.1. Алетическая модальная логика высказываний
Основ ные виды модаль ных логик : алети че ская , эписте ми че ская, деон ти че ская . Опишем только алети че скую логи ку выска зыва ний .
Язык алети ческой модаль ной логи ки
1.Счетное множе ство пропо зициональных пере менных: p, g,
r, …;
2.Логи ческие связки (конъюнк ция и др.);
3.Опера торы модаль ной логи ки: – чита ется «необ ходимо, что…», ◊– чита ется «возмож но, что…».
Определение 1 (правиль но постро енной форму лы – п. п. ф.).
1.Любая пропо зициональная форму ла есть п. п. ф.;
2.Если А – произ вольная п. п. ф., то А, А и ◊А – п. п. ф.;
3.Если А и В произ вольные п. п. ф., то А * В также п. п. ф.,
где * = { , , →, ↔}.
Опера торы возмож ности и необ ходимости взаимо определи
мы:
А = df ◊A.
◊A = df A.
158
Логика
Взаимо определимость модаль ных опера торов озна чает, что в дедук тивном или семан тическом изуче нии модаль ной логи ки мы можем обойтись каким -то одним опера тором.
Аксиоматическое построение модальной логики
Рассмот рим 4-е модаль ных аксио ма ти че ских |
систем . |
|||||
Систе ма М. |
|
|
|
|
|
|
А1. |
А → А. |
|
|
|
|
|
А2. |
(А → В) → (А → В). |
|
||||
R1. |
(мод. поненс ) |
|
A, A → B |
. |
|
|
|
|
|
B |
|
||
R2. |
(прави ло Геде ля) |
|
A |
. |
|
|
|
|
|
|
|
||
|
|
|
A |
|
R5. (прави ло подста новки). Обычная форму лировка.
Прави ло Геде ля указы вает, что если форму ла А дока зуема, то А тоже дока зуема.
Сиcтема S4.
К аксио мам и прави лам выво да систе мы М доба вим аксио му: А3. А → А.
Сиcтема Br (Брауэра ).
К аксио мам и прави лам выво да систе мы М доба вим аксио му :
А3. А → ◊А.
Сиcтема S5.
К аксио мам и прави лам выво да систе мы М доба вим аксио му :
А4. ◊А → ◊А.
Определение 2 (дока за тель ст ва ). Дока за тель ст вом в систе мах М, S4, S5, Br назы ва ет ся такая после до ва тель ность формул , каж дая из кото рых явля ет ся либо аксио мой , либо форму лой , полу чен ной из осталь ных посред ст вом правил выво да .
Дедук тивное отно шение меж ду систе мами предста вим следую щей схемой :
Br
МS5
S4
159
Раздел I. Основы фундаментальной философии
Она пока зы ва ет , что каж дая дока зуе мая форму ла систе мы М дока зуе мая также в систе мах S4, S5 и Br, но не наобо рот , т. е. в каж дой из систем S4, S5, Brимеют ся дока зуе мые форму лы , кото рые недо ка зуе мы в систе ме М. Каж дая дока зуе мая форму ла сис тем S4 либо Brдока зуе ма в систе ме S5, но не наобо рот . Таким об разом , самой сильной систе мой явля ет ся систе ма S5.
Теория моде лей для модаль ных систем : М, S4, S5, Br
Модаль ные опера торы не явля ются функцио нально-истин ност ными опера торами, т. е истин ностное значе ние опера тора опре де ляет ся по его подфор муле. Напри мер, истин ностное значе ние А полно стью опре деляется истин ностным значе нием форму лы А, так как опера тор явля ется истин ностно-функцио нальным. Это зна чит, что в модаль ных форму лах А или ◊А, если извест ны истин ност ные значе ния форму лы А, то по нему невоз можно опре делить истин ностное значе ние А или ◊А.
Модель есть упоря до чен ная тройка M = K, R, ν: К– непус тое множе ст во возмож ных миров ;
R –отно шение меж ду мира ми, назы ваемое отно шением дости жимо сти или альтер нативности.
ν – двуар гу мент ная функция интер пре та ции : значе ние одно го аргу мен та ν– форму ла , второ го – возмож ные миры ; область зна чения ν функции – истин но ст ные значе ния (истин но , ложно ).
Заме чание. Иногда специ ально выде ляется реаль ный мир @ среди множе ства возмож ных миров .
Содер жа тель но отно ше ние дости жи мо сти R можно пони мать сле дующим обра зом : пусть даны два произ воль ных возмож ных мира
к1 и к2 из К, кото рые нахо дятся в отно шении дости жимости к1Rк2: мир к2 дости жим из мира к1. Это озна чает в терми нах истин ности –
выска зы ва ние , истин ное в мире к2 явля ет ся возмож ным в мире к1. Идея семан ти ки как истин но ст ное отно ше ние меж ду мира ми была выска за на Лейбни цем , кото рый пола гал , что необ хо ди мо истин ным явля ет ся то, что истин но во всех возмож ных мирах .
Отно шение R должно быть рефлек сивным, т. е. каж дый мир возмо жен отно сительно само го себя , т. е. каж дое выска зывание истин ное в возмож ном мире , тем самым возмож но в этом мире .
Опре де лим истин но ст ное значе ние форму лы (без модаль но го опера то ра ) отно си тель но возмож но го мира при задан ной интер прета ции .
160