Osnovy_filosofii_uchebnik_dlya_bakalavrov
.pdfЛогика
ская форма данно го рассу ждения гаран тирует, что при истин но сти посы лок заклю чение тоже всегда будет истин ным.
Определение 3(разре шимости логи ческой теории ). Логи ческая теория назы вается разре шимой, если суще ствует эффек тивная проце дура (алго ритм), позво ляющая для любой форму лы языка теории в конеч ное число шагов опре делить, явля ется ли эта фор мула логи ческим зако ном или нет.
Класси че ская логи ка выска зы ва ний явля ет ся разре ши мой тео рией , и для нее суще ст ву ет несколь ко разре шаю щих проце дур . Одну из них представ ля ет таблич ный способ опре де ле ния истин ност ных значе ний формул .
Каж дая отдель ная пропо зициональная пере менная, заме щаю щая собой простое выска зывание, может быть истин ной или лож ной. Это обозна чается, соот ветственно, (1) и (0). Истин ность или ложность сложных формул зави сит от истин ностных значе ний входя щих в них пере менных. Эта зави симость представ лена в следую щей табли це:
А |
В |
А &В |
А В |
А В |
А →В |
А ≡В |
|
А |
¬А |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
1 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Алгоритм построения таблицы истинности
Опре де лить число строк в табли це , исполь зуя форму лу k = 2n, где k – число строк в табли це , а n – число пропо зи цио наль ных пере мен ных , входя щих в форму лу .
Задать все комби нации совме стной истин ности/ложно сти про пози циональных пере менных.
Уста но вить после до ва тель ность опре де ле ния значе ний связок (поря док дейст вий ), при этом послед няя связка назы ва ет ся глав ной, так как ее значе ния указы ва ют на вид форму лы .
Вычис лить (построч но) значе ние каж дой подфор мулы и форму лы в целом , исполь зуя данное выше таблич ное опре деление про пози циональных связок .
Заме ча ние . В логи ке выска зы ва ний логи че ские зако ны пред ставля ют собой класс тож де ст вен ных формул . А в рассу ж де ни ях ,
141
Раздел I. Основы фундаментальной философии
имеющих форму логи че ских зако нов , меж ду посыл ка ми и заклю чени ем уста нав ли ва ет ся отно ше ние логи че ско го следо ва ния . Та ким обра зом , логи ка выска зы ва ния , постро ен ная таблич ным спо собом , дает возмож ность опре де лить правиль ность (коррект ность ) рассу ж де ния , т. е. нали чие в рассу ж де нии отно ше ния логи че ско го следо ва ния .
§ 3. Форма лизация логи ки выска зываний мето дом анали тиче ских таблиц
Метод анали тических таблиц явля ется еще одной разре шаю щей проце дурой. По суще ству, она представ ляет собой неко то рое уточне ние указан ного выше сокра щенного мето да уста нов ления обще значимости формул . Поиск обосно вания обще значи мости форму лы осуще ствляется по опре деленным прави лам ре дукции и начи нается с предпо ложения, что форму ла не обще значи ма. Это предпо ложение ведет к проти воречию, если форму ла на самом деле обще значима. Анали тические табли цы на ос нова нии рассу ждения от против ного позво ляют найти модель с конеч ной обла стью, в кото рой форму ла опро вергается, если она обще значима.
Правила редукции
: А В ; |
( ) →: |
(А В) ; |
|
: А В ; |
( ): (А В); |
|||||||||
|
А, В |
|
|
|
А | В |
|
|
|
А | В |
|
А, В |
|||
|
( ): |
А |
; |
→: А → В |
; |
|
(→): |
(А → В) . |
||||||
|
|
|
А |
|
|
А | В |
|
|
|
|
|
А, В |
|
Форму ла, распо ложенная над чертой прави ла, назы вается по сылкой прави ла редук ции, а форму ла под чертой прави ла – на зыва ется заклю чением прави ла. Верти кальная черта в заклю че нии прави ла озна чает ветвле ние резуль тата приме нения прави ла редук ции (прави ла с ветвле нием).
Опре деление 1 (анали тической табли цы). Анали тической таб лицей назы вается конеч ная или беско нечная после довательность строк С1, … Ск, … списков формул такая , что каж дая после дую щая строка полу чается из преды дущей приме нением прави ла ре дукции .
142
Логика
Заме ча ние . Отме тим , что если мы приме ня ем прави ло редук ции с ветвле ни ем , то мы полу ча ем два списка формул .
Опре де ле ние 2 (замкну то го списка формул ). Список формул на зыва ет ся замкну тым , если в списке встреча ет ся неко то рая форму ла и ее отри ца ние , т. е. А и А (проти во ре чие ).
Опре деление 3 (завер шенного списка ). Список формул назы вает ся завер шенным, если к форму лам этого списка невоз можно при менять прави ла редук ции, т. е в списке встреча ются атомар ные форму лы или отри цание атомар ных формул .
Опре де ле ние 4 (замкну той табли цы ). Анали ти че ская табли ца замкну та , если все ее списки формул замкну ты (проти во ре чи вы ).
Опре деление 5 (завер шенной табли цы). Анали тическая табли ца назы вается завер шенной, если она замкну та или имеет завер шенные списки формул .
Опре де ле ние 6 (обще зна чи мой форму лы в терми нах анали ти ческой табли цы ). Форму ла А назы ва ет ся обще зна чи мой , если ее анали ти че ская замкну та .
Заме чание. Завер шенный список или завер шенная табли ца не обяза тельно замкну та, т. е. может быть замкну той, но не являть ся проти воречивой. Доста точно постро ить анали тическую табли цу для выпол нимой форму лы, чтобы в этом убедить ся.
§ 4. Нату ральное исчис ление выска зываний Опре деление 1 (исчис ления). Исчис лениями назы ваются теории ,
содер жание кото рых фикси руется на специ ально создан ном сим воли ческом языке , а все допус тимые преоб разования (в том чис ле и рассу ждения) строят ся как преоб разования одних после дова тельно стей симво лов в другие их после довательности.
Заме ча ние .Внату раль ном исчис ле нии преоб ра зо ва ния формул строят ся только на осно ве правил . Алфа вит языка этого исчис ле ния и опре де ле ние правиль но постро ен ной форму лы совпа да ет с алфа ви том и поня ти ем форму лы логи ки выска зы ва ний , задан ных выше . А поня ти ям логи че ско го зако на и логи че ско го следо ва ния здесь вводят ся синтак си че ские анало ги – поня тие теоре мы и по нятие выво ди мо сти .
Для построе ния нату рального исчис ления для логи ки выска зыва ний необ ходимо:
– задать прави ла выво да;
– сформу лировать поня тия выво да и выво димой форму лы.
143
Раздел I. Основы фундаментальной философии
Прави ла выво да
Прави ла выво да делят ся на прави ла введе ния логи че ских свя зок и удале ние логи че ских связок и в форму ли ров ке правил «В:» сокра ща ет слово «Введе ние », а «У:» – «Удале ние ».
В: А |
; |
|
|
|
|
В: В |
|
; |
|
У: Г, А В; Г, А С Г, В С ; |
|||||||||||||||
|
|
А В |
|
|
|
|
|
|
|
|
А В |
|
|
|
|
|
|
|
|
|
Г С |
|
|||
|
|
В: А, В |
; |
|
|
|
У: А В ; |
У: А В ; |
|||||||||||||||||
|
|
|
|
|
А В |
|
|
|
|
|
|
|
|
А |
|
|
|
|
В |
|
|||||
В: → |
Г, А В |
; |
|
|
|
|
|
У: → А, А → В |
|
; |
|
|
|
||||||||||||
|
|
Г А → В |
|
|
|
|
|
|
|
|
|
|
|
В |
|
|
|
|
|
||||||
У: |
А |
; |
|
|
|
В: |
Г, А В; Г, А В |
; |
|
|
|
|
|
||||||||||||
|
А |
|
|
|
|
|
|
|
|
|
Г В |
|
|
|
|
|
|
|
|
|
|
||||
У (слабое ): |
|
А, А |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Опре де ле ние 2 (выво да ). Выво дом назы ва ет ся непус тая конеч ная после до ва тель ность формул , в кото рой любая форму ла явля ется либо посыл кой , либо форму лой полу чен ной из преды ду щих по прави лам выво да .
Опре де ле ние 2 (выво ди мой форму лы ). Послед няя форму ла в вы воде назы ва ет ся выво ди мой форму лой .
Коммен тарии к прави лам выво да.Над чертой прави ла – по сылки , под чертой прави ла – заклю чение. Прави ла делят ся на одно посылочные (над чертой пишет ся одна форму ла) и двухпо сылоч ные (над чертой пишут ся две форму лы). Прави ла делят ся на прави ла прямо го выво да и прави ла косвен ного выво да. В прави лах косвен ного выво да в посыл ках исполь зуется знак выво димости «d», кото рый озна чает, что строят ся вспомо гатель ные выво ды. Прави ло В: → предпо лагает дока зательство теоре мы дедук ции.
Методические рекомендации
Разбе рите на семи нарских заня тиях приме ры построе ния сокра щенной табли цы истин ности, в кото рых идет разбор по случа ям.
144
Логика
Сопос тавьте построе ние анали тических таблиц логи ки выска зыва ний с обыкно венными табли цами истин ности.
Изучи те все опре деления и разбе рите их на конкрет ных при мерах .
Вопросы для самоконтроля
Что изуча ет класси че ская логи ка выска зы ва ний ?
Как разли чаются виды формул КЛВ по усло виям истин ности ?
Какие разре шаю щие проце ду ры суще ст ву ют в логи ке выска зыва ний ?
Как уста новить нали чие логи ческого следо вания в рассу жде нии таблич ным построе нием логи ки выска зывания?
Что такое анали ти че ская табли ца ?
В чем разли чие меж ду прави лами с ветвле нием и прави ла ми без ветвле ния?
Что назы ва ет ся исчис ле ни ем ? Како ва специ фи ка нату раль но го исчис ле ния выска зы ва ний ?
Что назы вается выво дом и выво димой форму лой в нату раль ном исчис лении выска зываний?
Литература
Боча ров В. А., Маркин В. И. Осно вы логи ки. М., 1998, 1999, 2000, 2002, 2004. Гл. II, IV, § 1.
Войшвил ло Е. К. Симво ли че ская логи ка . Класси че ская и реле вант
ная. М. 1989. Гл. 3.
Клини С. Мате ма ти че ская логи ка . М., 1973. Гл. 1, § 1, 2, 8, 9, 11, 13, 14.
Мендель сон Э. Введе ние в мате матическую логи ку. М., 1976, 1984.
Гл. 1. § 1, 2.
Соло духин О. А. Логи ка. Ростов н/Д, 2000. Гл. 3, 4, (4.1, 4.2).
Войшвил ло Е. К., Дегтя рев М. Г.Логи ка как часть теории позна ния и
науч ной мето дологии. М., 1994. Книга I. Гл.4, § 15. Гл. 6, § 20. Формаль ная логи ка. Л., 1977. Ч. 2, Гл. I, III, § 16, 17.
4. Первопорядковая логика предикатов
Логи ка преди ка тов перво го поряд ка явля ет ся расши ре ни ем ло гики выска зы ва ний : к языку логи ки выска зы ва ний добав ля ют ся следую щие кате го рии симво лов – инди вид ные констан ты , инди
145
Раздел I. Основы фундаментальной философии
видные пере мен ные , преди ка ты и кванто ры . Тем самым предпо
лага ет ся , что студент полно стью усво ил мате ри ал из класси ческой логи ки выска зы ва ний .
Синтаксис и семантика логики предикатов § 1. Синтаксис логики предикатов
Пункта ми 1) – 6) зада дим язык логи ки преди ка тов перво го поряд ка .
1. Логи ческие связки (констан ты): – (конъюнк ция); – (дизъ юнкция ); – (отри цание); →– (импли кация), ↔– (экви вален ция).
2. Конеч ное или счетное множе ст во инди вид ных констант : а,
в, с, а1, в1, с1,… 3. Конеч ное или счетное множе ство инди видных пере менных: х,
у, z, х1, у1, z1,…
4. Конеч ное или счетное множе ство преди катных симво лов: P01,…, Pn0, P11,…, P1n,…, P1k,…, Pkn,…, где верхний индекс указы вает чис ло аргу ментных мест преди ката; нульме стный преди кат P0 есть пропо зициональная пере менная, т. е. симво лы выска зываний. Преди каты, у кото рых не меньше двух аргу ментов, часто на зыва ют отно шениями.
5. Кванто ры : всеобщ но сти – (для всех, для каж до го ), суще ст вова ния – (суще ст ву ет , для неко то рых ).
6. Техни ческие (вспомо гательные) знаки : «(»– левая скобка , «)» – правая скобка .
Определение 1. Термом |
назы ва ет ся наимень |
шее |
множе ст во , |
||||||
удовле тво ряю щее |
следую щим |
усло ви ям : |
|
|
|||||
– любая |
инди |
вид |
ная |
констан |
та есть терм; |
|
|
||
– любая |
инди |
вид |
ная |
пере мен ная |
есть терм. |
|
|
Ничто иное, кроме того , что указа но в пунктах 1. и 2 не мо жет быть терми ном.
Усло вимся обозна чать произ вольный терм (инди видную кон станту или инди видную пере менную) симво лом t, если они раз личны , то это будем отме чать различ ными нижни ми индек са ми, напри мер t1, t2.
Определение 2 (форму лы ):
1. Атомар ной форму лой назы вается выра жение вида P(t1,…, tk), где к число аргу ментов атомар ной форму лы, 1 ≤к ≤n.
2. Любая атомар ная форму ла языка логи ки преди ка тов перво го поряд ка явля ет ся форму лой .
146
Логика
3. Если А произ вольная форму ла логи ки преди катов перво го по рядка , то А – форму ла.
4. Если А и В произ вольные форму лы языка логи ки преди катов перво го поряд ка, то А В, А В, А →В, А ↔В тоже форму лы.
5. Если А (х) – произ воль ная форму ла , то хА (х), хА (х) то же форму лы . Вхож де ние пере мен ной «х» в форму лы хА (х),хА(х) назы ва ют ся связан ны ми (кванто ра ми ).
Методическое указание. Обра тите внима ние, что в отли чие от логи ки выска зываний, в логи ке преди катов атомар ная форму ла опре деляется. «А» и «В» – это мета переменные для формул , т. е. они, могут обозна чать произ вольную форму лу языка логи ки преди катов перво го поряд ка.
Определение 3 (свобод но го вхож де ние пере мен ной в форму лу ): 1. Все пере мен ные атомар ной форму лы явля ют ся свобод ны ми
вхож дениями пере менной в атомар ную форму лу.
2. Если пере мен ная «у» входит свобод но в форму лу А (т. е. А имеет вид А(у)), то пере мен ная «у» входит свобод но и в фор мулу А.
3. Если пере менная «у» свобод но входит в форму лу А или В, то она свобод но входит и в форму лы А В, А В, А→В, А↔В.
4. Если пере мен ная «у» входит свобод но в форму лу А, то она сво бодно входит в форму лы хА(х), хА(х), при усло вии , что пе ремен ные «у» и «х» различ ны .
Пере менная назы вается связан ной (кванто ром), если она не явля ется свобод ной.
Определение 4.Предло же ни ем (замкну той форму лой – другое назва ние ) назы ва ет ся форму ла языка логи ки преди ка тов , кото рая не имеет свобод ных вхож де ний пере мен ной .
Определение 5 (правиль ной подста новки терми на на место свобод ной пере менной).
Подста нов ка есть отобра же ние δиз множе ст ва пере мен ных в множе ст во термов .
Пусть δ– подста новка. Через δхобозна чим подста новку, кото рая отли чатся от подста новки δтем, что не заме щает пере менной «х» ника ким терми ном, т. е. для любой пере менной «у» имеем :
δ(у), если у ≠х
δх(у) =
х, если у =х
147
Раздел I. Основы фундаментальной философии
Распро страним поня тие подста новки на форму лу:
1. δ(P(t1,…,tn)) = P(δ(t1),…,δ(tn)), где P(t1,…,tn) атомар ная форму
ла.
2. δ( А) = δ(А).
3. δ(А → В) = δ(А) → δ(В).
4. δ( А(х)) = х(δхА(х)).
5. δ( А(х)) = х(δхА(х)), т. е. δх не затра гивает связан ную пере менную х.
Подста нов ка назы ва ет ся правиль ной (свобод ной ), если резуль тат фикси ро ван ной подста нов ки не содер жит ни одной пере мен ной, нахо дя щей ся в облас ти дейст вия кванто ра .
1. |
δ свобод |
на для формул |
А, если А – атомар ная |
форму ла . |
|
||||||
2. |
δ свобод |
на для А, если δ свобод на для А. |
|
|
|||||||
3. |
δ свобод |
на для А→В, А В, А В, А↔В если |
δ свобод на |
для |
|||||||
|
А и δ свобод на для В. |
|
|
|
|
|
|||||
4. |
δ свобод |
на для формул |
хА(х) и хА(х), если |
δ свобод на |
для |
||||||
|
А(х), т. е. пере мен ная |
у, у≠х, свобод на для А(х). Напри мер , |
|||||||||
|
в форму ле с конкрет |
ным |
двуме ст ным |
преди ка том х(у<х) мы |
|||||||
|
не можем |
подста вить |
на место свобод ной пере мен ной у связан |
||||||||
|
ную пере мен ную |
х, т. е. х(х<х). |
|
|
|
§ 2. Первопорядковая семантика (теория моделей)
Определение 1 (моде ли). Модель языка логи ки преди катов пер вого поряд ка есть пара M= D, I , где:
D– непус тое множе ст во объек тов , назы вае мое обла стью интер прета ции ;
I – есть отобра жение, назы вае мое интер пре та ци ей , кото рое : 1. Каж дой инди вид ной констан те а С сопос тав ля ет элемент
аI D.
2. Каж дому преди катному симво лу Pn R сопос тавляет подмно жест ва Dn.
Заме тим , что каж до му объек ту облас ти интер пре та ции соот ветст ву ет только одна констан та и каж дая констан та обозна ча ет только один элемент , т. е. в класси че ской логи ке преди ка тов не допус ка ют ся констан ты , кото рые ниче го не обозна ча ют (пустые по значе нию констан ты ).
Определение 2 (оценки , припи сывание) в моде ли M = D, I .
148
Логика
Оценка есть отобра же ние f из множе ст ва пере мен ных в мно жест во элемен тов D. Значе ни ем оценки пере мен ной явля ет ся про изволь ный элемент облас ти D, кото рый будем обозна чать , напри мер, для пере мен ной х через хf.
Обра тим внима ние , что функция интер пре та ции I припи сы ва ет значе ние деск рип тив ным терми нам языка логи ки преди ка тов в облас ти интер пре та ции , т. е. инди вид ным констан там и преди ка там. Функция оценки f припи сы ва ет значе ние пере мен ным в об ласти интер пре та ции .
Напом ним, что терми ном явля ется констан та или пере менная. Дальше , когда будем опре делять истин ность форму лы в моде ли, нам надо будет учиты вать значе ние терми на.
Определение 3 (значе ние терми на в D).
1. Для констан ты: aI, f = aI, т. е. функция f не опре делена на кон стантах .
2. Для пере мен ной : xI,f = xf, т. е. функция I не опре де ле на на пе ремен ных .
Определение 3 позво ля ет компакт но опре де лить истин ность форму лы в моде ли , чтобы не опре де лять истин ность форму лы от дельно для констант и отдель но для пере мен ных , а также комби нации констант и пере мен ных .
Определение 4 (истин ности форму лы в моде ли).Пусть M = D, I
модель языка перво по ряд ко вой логи ки , и пусть f – функция оценки . С каж дой форму лой А наше го языка свяжем истин но стное значе ние АI,f (исти ну или ложь) посред ст вом следую щих усло вий .
Обозна чим исти ну через «1», а ложь через «0». Будем исполь зовать мета знак для обозна чения экви валентности левой и пра вой части опре делений. Опре деление истин ности форму лы опре де ляет ся не в самом языке перво порядковой логи ки, а в мета язы ке, т. е. языке , в кото ром мы дела ем утвер ждения о языке ло гики преди катов (объект ном языке ). Подоб но тому , когда изуча ют иностран ный язык, изучае мый язык назы вается объект ным, а родной язык, посред ством кото рого изуча ют иностран ный, яв ляет ся мета языком.
1. Для атомар ной форму лы : А(t ,…,t )I,f = 1 |
tI,f,…, tI,f АI. |
||
2. ( А) I, f (А) I, f. |
1 n |
1 |
n |
|
|
|
149
Раздел I. Основы фундаментальной философии
3. (A * B) I,f (AI,f * BI,f), где * заме ня ет ся одной из логи че ских
связок , указан ных в фигур ных скобках , т. е.* = {→, , ,
↔}.
4. ( хА (х)) I,f = 1 А (х) I,f= 1 для каж до го припи сы ва ния fзна чений пере мен ной х, т. е. форму ла А(х) истин на для каж до го элемен та облас ти интер пре та ции D.
5. ( хА (х)) I,f = 1 А (х) I,f = 1 для неко торого припи сывания f значе ниям пере менной х, т. е. форму ла А (х) истин на для не кото рого элемен та облас ти интер претации D.
Мето ди че ские указа ния . В пункте 1 дана симво ли че ская за пись коррес пон дент ской (класси че ской , аристо те лев ской ) теории исти ны . Форму ла истин на (левая часть опре де ле ния ) при данной интер пре та ции Iв моде ли M = D, I , если и только если (правая часть опре де ле ния ) предме ты облас ти D, соот вет ст вую щие кон
стантам t1, …, tnвходят в объем преди ката А. В пункте 4 запись А (х) I,f= 1 по опре делению озна чает: А (а1) = 1, А (а2) = 1, …, А (ак) = = 1, …, где а1, а2, …, ак, инди видные констан ты, обозна чающие
элемен ты облас ти интер пре та ции . А в пункте 5 запись А (х)I,f= 1 по опре де ле нию озна ча ет : что хотя бы для одно го элемен та облас ти интер пре та ции , обозна чен но го неко то рой констан той аj, фор мула А (аj)I,f = 1.
Определение 5. Форму ла А выпол нима в моде ли, если имеет ся припи сывание f, при кото ром форму ла А прини мает значе ние «истин но».
Определение 6.Форму ла А истин на в моде ли , если для любо го припи сы ва ние f форму ла А прини ма ет значе ние «истин но ».
Определение 7. Форму ла А обще значима, если она истин на в любой моде ли, т. е. при любой облас ти интер претации (их число беско нечно).
Законы де Моргана для кванторов:
1. хА (х) ↔ А (х). 2. хА (х) ↔ А (х).
Методические рекомендации
1.Изучить все опре деления.
2.Подоб рать приме ры, кото рые демон стрируют рабо ту этих оп реде лений.
150