3.5 Доказателствена процедура

Ще въведем доказателствена процедура, чрез която да доказваме, че от някакви формули на предикатната логика логически следват други. Чрез нея ще можем да доказваме и че две формули са логически еквивалентни, тъй като логическата еквивалентност се свежда до взаимно логическо следване. За целта първо ще видим каква е смисловата връзка между екзистенциалния и универсалния квантор и ще въведем понятията за екзистенциална и универсална инстанциация.

Връзка между кванторите

Интуитивно универсалните твърдения (тези, които започват с универсален квантор) изглеждат по-общи от екзистенциалните (тези, започващи с екзистенциален квантор) доколкото думата „всичко“ изглежда като отнасяща се до повече неща от думата „поне едно“. От логическа гледна точка обаче това не е така, защото смисълът и на двете съдържа отнасяне към всички неща (от универсума на дискурса). Едно универсално твърдение ни казва, че всички неща изпълняват определено условие, а едно екзистенциално – че сред всички неща има поне едно, което изпълнява определено условие. За да се установи, че едно универсално твърдение е истинно, трябва да се установи, че определено условие е изпълнено за всички неща. За да се установи, че едно екзистенциално твърдение е неистинно, отново трябва да се установи, че определено условие е изпълнено за всички неща – а именно да не отговарят на определено условие. Определянето на истинностната им стойност изисква в еднаква степен отнасяне към всичко.

Между екзистенциалния и универсалния квантор съществува смислова връзка, която позволява всичко, което може да се изрази чрез единия, да се изрази и чрез другия.

Да се каже, че не съществува нещо, което е F, е същото като да се каже, че всичко е не-F. Например, да се каже, че не съществуват съвършени неща („¬∃хFх“), е същото като да се каже, че всички неща са несъвършени („∀х¬“). Следователно между двата квантора е налице следната връзка (на мястото на „x“ може да е всяка друга променлива):

(1) „¬∃х…“ има същия смисъл като „∀х¬…“

Освен това, да се каже, че не всичко е F („¬∀хFх“), е същото като да се каже, че нещо не е F („∃х¬“) – например, да се каже, че не всички неща са съвършени, е същото като да се каже, че някои неща не са съвършени. Така че между екзистенциалния и универсалния квантор съществува също следната връзка:

(2) „¬∀х…“ има същия смисъл като „∃х¬…“

Двете връзки могат да бъдат обобщени така:

Когато от едната страна на един квантор има отрицание, то може да мине от другата му страна, като кванторът се обърне – ако е бил екзистенциален, стане универсален; и ако бил универсален, стане екзистенциален.

Въз основа на (1) „¬∃х¬…“ ще има същия смисъл като „∀х¬¬…“ („¬∃х“ в първото е заменено с „∀х¬“). Като махнем двойното отрицание в „∀х¬¬…“, получаваме, че „¬∃х¬…“ има същия смисъл като „∀х…“ – например, да се каже, че не съществуват неща, които не са съвършени („¬∃х¬Fx“), е същото като да се каже, че всички неща са съвършени („∀хFx“). Така че имаме още следното:

(3) „∀х…“ има същия смисъл като „¬∃х¬…“

От (3) следва, че всичко, което може да бъде изразено чрез универсален квантор, може да бъде изразено и чрез екзистенциален квантор и отрицание – просто можем навсякъде да заменим „∀х“ с „¬∃х¬“.

Въз основа на (2) „¬∀х¬…“ казва същото като „∃х¬¬…“ ( „¬∀х“ в първото е заменено с „∃х¬“). Като махнем двойното отрицание в „∃х¬¬…“, получаваме, че „¬∀х¬…“ има същия смисъл като „∃х…“ – да се каже например, че не всичко е несъвършено, е същото като да се каже, че нещо е съвършено. Така че налице е също следната връзка между кванторите:

(4) „∃х…“ има същия смисъл като „¬∀х¬…“

От (4) следва, че всичко, което може да бъде казано с екзистенциален квантор, може да бъде казано и с универсален квантор и отрицание – можем да заменим навсякъде „∃х“ с „¬∀х¬“. Следната таблица обобщава връзката между кванторите.

За всяко нещо важи, че не е... x¬(...x...) ¬∃x(...x...) Не съществува нещо, което е...
Не всяко нещо е... ¬∀x(...x...) x¬(...x...) Съществува нещо, което не е...
Не е вярно, че всяко нещо не е... ¬∀x¬(...x...) ∃x(...x...) Съществува нещо, което е...
Всяко нещо е... x(...x...) ¬∃x¬(...x...) Не съществува нещо, което не е...

Нека видим как бихме могли да използваме връзката между кванторите. Да разгледаме израза

хуFху

Заради връзката между кванторите той е логически еквивалентен на „¬∃х¬∃уFху“ („∀х“ е заменено с „¬∃х¬“), както и на „∀х¬∀у¬Fху“ („∃у“ е заменено с „¬∀у¬“), както и на „¬∃ху¬Fху“ („∀х“ е заменено с „¬∃х¬“, а „∃у“ – с „¬∀у¬“, получавайки „¬∃х¬¬∀у¬Fху“, след което двойното отрицание е махнато).

Връзката между кванторите (в частност (1) и (2), които обобщихме в правилото, че отрицание може да мине от другата страна на един квантор, като кванторът се обърне) позволява, когато имаме поредица от квантори с отрицание от едната ѝ страна, например „∃хyz¬…“, отрицанието да мине от другата страна на цялата поредица, като всеки от кванторите в нея се обърне – екзистенциалните станат универсални, а универсалните екзистенциални. „∃хyz¬…“ винаги може да се замени с „¬∀хyz…“. Основанието за това е следното. „∃хyz¬…“ има същото значение като (логически еквивалентно е на) „∃хy¬∀z…“ („∃z¬“ в първия израз е заменено с „¬∀z“), което от своя страна е еквивалентно на „∃х¬∃yz…“ („∀y¬“ е заменено с „¬∃y“), което е еквивалентно на „¬∀хyz…“ („∃х¬“ е заменено с„¬∀х“). Аналогично (друг пример), ако сме тръгнали от „¬∃хyz¬…“, може да преместим първото отрицание отзад или второто отпред, обръщайки кванторите, като в резултат ще стигнем съответно до „∀хyz¬¬…“ или до „¬¬∀хyz…“. Като махнем двойното отрицание, и в двата случая получаваме „∀хyz…“.

Също така, ако имаме произволна поредица от разбъркани квантори и отрицания, наприме𠄬∀х¬∀yz¬“, „¬∃хy¬∃z“ и т.н., тя винаги може да се преобразува в поредица само от квантори (без отрицания между тях), като евентуално от едната ѝ страна има отрицание. За целта преместваме всички вътрешни отрицания напред или назад (обръщайки кванторите, през които преминават). Така получаваме една поредица само от квантори и една поредица само от отрицания от едната страна на първата. Ако отрицанията са четен брой, всичките се унищожават по схемата на двойното отрицание; ако са нечетен брой, остава само едно отрицание.

Универсална и екзистенциална инстанциация

Универсалната инстанциация1 е логически валидна схема за извод, чиито смисъл е, че ако някакво условие е изпълнено за всички неща, то е изпълнено и за едно от тях. Ето няколко примера:

хFx x(Fx → ¬∃yGxy) х(FxaFxb) х(FxaFxb)
Fa → ¬∃yGаy FаaFаb FbaFbb

В първия пример от това, че всяко нещо е F, се заключава и че определеното нещо a е F. Във втория предпоставката е по-сложна, но отново има формата на универсално твърдение, в което се казва, че за всяко нещо е изпълнено определено условие – условието, че ако то е F, няма нищо, към което да се намира в релацията G. След като това условие е изпълнено за всяко едно x, значи ще е изпълнено и за а, така че двете участия на „x“ в условието са заместени с „а“ в заключението. В случаи като този и предишния казваме, че променливата на универсалния квантор „x“ е инстанциирана с индивидната константа „а“. Третият и четвъртият пример имат една и съща предпоставка, но променливата на универсалния квантор в първия случай е инстанциирана с „a“, а във втория – с „b“.

Формално, при инстанциацията (не само универсалната, но и екзистенциалната) махаме квантора в началото на израза и заместваме всички (вече) свободни участия на променливата на квантора с инстанциираната индивидна константа. Би било неправилно, ако участията на променливата са повече, да не заменим някое от тях с инстанциираната константа. Например по универсална инстанциация от „∀хFxx“ можем да изведем „Faa“, но не и „Fах“. Ако „F“ отговаря на предиката „[1] е еднакво с [2]“, от това, че всяко нещо е еднакво със себе си, следва, че a е еднакво с a, а не следва, че а е еднакво с х („Fах“) – х може да е което и да е нещо и значи може и да е различно от а. Отделно, „a е еднакво с x“ не е твърдение, а отворено изречение.

Екзистенциалната инстанциация e като универсалната с две съществени разлики. Едната е, че кванторът не е универсален, а екзистенциален. Другата (която е свързана с първата) е, че тя не е логически валидна схема за извод. От „∃хFx“ чрез екзистенциална инстанциация получаваме „Fa“, „Fb“,... и т.н. Това не са логически валидни изводи, защото може да е вярно, че съществува нещо, което е F, но да не е вярно, че тъкмо определеното нещо а (съответно b и т.н.) е F. Въпреки че не е логически валидна схема за извод, ще я използваме за да правим само логически валидни изводи – ще видим след малко как. При екзистенциалната инстанциация, също както при универсалната, трябва да се инстанциират всички (вече) свободни участия на променливата, след като кванторът се махне. От „∃х(FxaFxb)“ например може да получим „FсaFсb“, но не и „FхaFсb“ или „FсaFxb“.

Доказателствена процедура в предикатната логика

Ако към доказателствената процедура на естествената дедукция от пропозиционалната логика2 се добавят връзката между кванторите и универсалната и екзистенциална инстанциации (последната с едно ограничение), се получава доказателствена процедура за предикатната логика, чрез която за всеки логически валиден извод може да бъде доказано, че е такъв.3

Ограничението при екзистенциалната инстанциация е, че инстанциираната индивидна константа трябва да е нова, т.е. да не се среща нито в предпоставките, нито в предишни стъпки на доказателството. Както вече казахме, за разлика от универсалната инстанциация, екзистенциалната не е логически валидна схема за извод. Въпреки това, благодарение на това ограничение, чрез нея могат да бъдат правени логически валидни изводи. Нека видим как. Искаме например да докажем, че от твърдението „Има нещо, което е създало всичко“ следва твърдението „Има нещо, което е създало самото себе си“. Представяме с „F“ „[1] е създало [2]“ и трябва да докажем е, че от „∃хуFxy“ следва „∃хFxx“:

1. хуFxy / ∃хFxx

Ще използваме доказателство чрез свеждане до противоречие – ще допуснем отрицанието на извода и ще се опитаме да стигнем до противоречие.

2. ¬∃хFxx допускане

От връзката между кванторите „¬∃хFxx“ е логически еквивалентно на „∀х¬Fxx“:

3. х¬Fxx от 2. по връзка между кванторите

Както тук, връзката между кванторите ще бъде използвана преди всичко, за да преместим даден квантор най-отпред в един израз. Идеята на тази стъпка е твърдението да стане универсално (а не да е отрицание), за да може след това да се правят инстанциации от него.

Сега ще направим една екзистенциална инстанциация – от 1. ∃хуFxy („Съществува нещо, което е създало всички неща“) ще изведем „∀уFay“ („a е създало всички неща“). По принцип на екзистенциалната инстанциация отговаря следната стъпка в едно разсъждение: изхождайки от това, че съществува нещо, за което е изпълнено дадено условие, обозначаваме това нещо с произволно, неизползвано досега име (нова индивидна константа в нашия случай), за да може по-лесно да говорим за него. Ако има повече такива неща (всяко екзистенциално твърдение ни казва, че съществува поне едно нещо, за което е изпълнено някакво условие, а не че съществува точно едно такова неща), името ще се отнася до някое от тях – все едно кое. В случая, изхождайки от това, че съществува нещо, което е създало всички неща, въвеждаме неизползваната индивидна константа „a“, за да го обозначава по-нататък в доказателството (ако повече от едно неща са създали всичко, „a“ ще обозначава някое от тях, все едно кое):

4. уFаy от 1. по EI4

От 4. по универсалната инстанциация можем да изведем „Faa“ (от това, че а е създало всички неща („∀уFаy“), понеже самото то е някакво нещо, логически следва, че е създало и самото себе си):

5. Fаа от 4. по UI5

От друга страна от 3. („∀x¬Fxx“) отново по универсална инстанциация следва „¬Faa“, което противоречи на „Fаа“:

6. ¬Fаа от 3. по UI – противоречие с 5.

От противоречието извеждаме отрицанието на допуснатото в 2. твърдение („¬∃хFxx“), т.е. получаваме „∃хFxx“, което искахме да докажем:

7. хFxx от 2.-6. по свеждане до противоречие

Видяхме, че екзистенциалната инстанциация се използва не като схема за извод, а за да именуваме нещо, което знаем, че съществува. Това обяснява защо при нея инстанциираната константа трябва да е нова. Ако например „а“ се среща по-рано в едно доказателство (било в някоя от предпоставките, било в изведено твърдение), тя би обозначавала вече нещо в дадения контекст. Екзистенциалното твърдение, от което след това бихме направили екзистенциална инстанциация, ни гарантира, че съществува нещо, за което е изпълнено определено условие, но от него не следва, че това нещо непременно е същото онова нещо а, за което сме говорили по-рано – би могло и да е друго. Затова, ако искаме да го обозначим, трябва да изберем ново, неизползвано име, да кажем „b“. b и a биха могли да са различни неща, а биха могли и да не са. Ако са едно и също нещо, константите „a“ и „b“ ще функционират като две различни негови имена, така както „Вечерница“ и „Зорница“ са две различни имена на планетата Венера. Ако са различни неща обаче, е ключово да бъдат обозначени с различни имена, откъдето идва и правилото за екзистенциалната инстанциация.

Следният пример показва до какво води неспазването на правилото, че при екзистенциална инстанциация инстанциираната константа трябва да е нова. Oт това, че има синеоки хора („∃хFx“, D – хората), бихме могли да „докажем“, че всички хора са синеоки („∀хFx“). Ето едно „доказателство“:

1. хFx / ∀хFx
2. ¬∀хFx допускане
3. х¬Fx от 2. по връзка между кванторите
4. Fa от 1. по EI
5. ¬Fa от 3. по ЕI – противоречие с 4.
6. хFx от 2.-5. по свеждане до противоречие

Грешката в доказателството е в 5., където инстанциираната при екзистенциалната инстанциация константа „a“ не е нова.

При универсалната инстанциация нямаме такова ограничение, защото, щом някакво условие е изпълнено за всички неща, то ще е изпълнено за всяко едно нещо, независимо от това дали сме говорили за него преди, или не.

За разлика от естествената дедукция в пропозиционалната логика, където почти винаги можеше да се мине без използване на доказателство чрез допускане (доказателство чрез свеждане до противоречие или условно доказателството), тук почти винаги ще си служим с такoва доказателствo. Стандартният начин, по който ще използваме сегашната доказателствена процедура, е да допускаме отрицанието на заключението и да стигаме до противоречие.

Като следващ пример нека докажем валидността на един силогизъм – на АII-1 (Darii):

Всяко M е Р.
Някои S са М.
Някои S са Р.

Изразен в езика на предикатната логика, той има следния вид:

х (MxPx)
x (SxMx)
x (SxPx)

Ето едно възможно доказателство на логическата валидност на тази схема за извод (в скоби са дадени неформалните разсъждения, които стоят зад използваните инстанциации):

1. х(MxPx)
2. x(SxMx) / ∃x(SxPx)
3. ¬∃x(SxPx) допускане
4. x¬(SxPx) от 3. по връзка между кванторите
5. SaMa от 2. по EI (2. ни казва, че има някакво нещо, което е едновременно S и M – означаваме го с „а“)
6. от 1. по UI (1. ни казва, че за всяко нещо е изпълнено условието, че ако е S, то е и P. Tова условие ще e изпълнено и за конкретното нещо a.)
7. ¬(SaPa) от 4. по UI (4. ни казва, че за всяко нещо е изпълнено условието „¬(S... ∧ P...)“. Следователно това условие ще е изпълнено и за a.)
8. от 5. по симплификация
9. Pa от 6. и 8. по модус поненс
10. Sa от 5. по симплификация
11. SaPa от 10. и 9. по конюнкция – противоречие с 7.
12. ∃x(SxPx) от 3.-11. по свеждане до противоречие

Чрез екзистенциалните инстанциации в доказателствата се въвеждат нови индивидни константи, докато универсалните инстанциации се прилагат върху вече налични индивидни константи. Затова като правило в едно доказателство първо правим екзистенциални инстанциации, с което си осигуряваме индивидни константи, върху които след това можем да направим универсални инстанциации. Например в горното доказателство отначало нямаше индивидни константи. Затова чрез екзистенциална инстанциация въведохме константата „а“, по отношение на която след това в 6. и 7. направихме универсални инстанциации от двете универсални твърдения.

Ако обаче в предпоставките няма индивидни константи и не разполагаме с екзистенциални твърдения, чрез които да въведем такива, тогава, така да се каже за да задвижим процеса, бихме могли да направим универсални инстанциации с произволна индивидна константа (например с „a“). Това е оправдано доколкото можем да приемем, че в света (в универсума на дискурса) има поне едно нещо. Това, че съществува поне един обект, се приема по конвенция в семантиката на предикатната логика – свят, в който няма нищо, е логически възможен, но е безинтересен от логическа и всякаква гледна точка.

Освен, че определени изводи са логически валидни, с въведената доказателствена процедура можем да доказваме и че определени формули (твърдения) са логически валидни. За целта е достатъчно да покажем, че допускането на отрицанието на формулата (т.е. допускането, че е неистинна) води до противоречие. Тогава ще е логически невъзможно формулата да е неистинна, което значи, че ще е истинна във всяка структура6, т.е. че ще е логически валидна. (В пропозиционалната логика използвахме същия прийом, за да доказваме, че определени формули са тавтологии.)

Като пример ще докажем, че формулата „∀xyz(FxyFzx)“ е логически валидна:

1. ¬∀xyz(FxyFzx) допускане
2. xyz¬(FxyFzx) от 1. по връзка между кванторите7
3. yz¬(FayFza) от 2. по EI („x“ е инстанциирано с „а“)
4. z¬(FaaFza) от 3. по UI („y“ е инстанциирано с „а“)
5. ¬(FaaFaa) от 4. по UI („z“ е инстанциирано с „а“)
6. Faa ∧ ¬Faa от 7. по мат. импликация – противоречие
7. xyz(FxyFzx) от 1.-6. по свеждане до противоречие

За да докажем с нашата доказателствена процедура, че две формули са логически еквивалентни, можем да докажем, че следват логически една от друга. Като пример, а и поради важността им, ще докажем валидността на две логически еквивалентности: това, че универсалният квантор може да се разпределя в конюнкцията, а екзистенциалния квантор – в дизюнкцията:

„∀x(FxGx)“ „∀xFx ∧ ∀xGx
„∃x(FxGx)“ „∃xFx ∨ ∃xGx

Първо доказваме, че от „∀x(FxGx)“ логически следва „∀xFx ∧ ∀xGx“:

1. x(FxGx) / ∀xFx ∧ ∀xGx
2. ¬(∀xFx ∧ ∀xGx) допускане
3. ¬∀xFx ∨ ¬∀xGx от 2. по Де Морган
4. x¬Fx ∨ ∃x¬Gx от 3. по връзка между кванторите
5. x¬Fx допускане
6. ¬Fa от 5. по EI
7. FaGa от 1. по UI
8. Fa от 7. по симплификация – противоречие с 6.
9. ¬∃x¬Fx 5.-8. по свеждане до противоречие
10. x¬Gx от 4. и 9. по дизюнктивен силогизъм
11. ¬Gb от 10. по EI („b“ е нова константа)
12. FbGb от 1. по UI
13. Gb от 12. по симплификация – противоречие с 11.
14. xFx ∧ ∀xGx от 2.–13. по свеждане до противоречие

След това доказваме, че от „∀xFx ∧ ∀xGx“ следва „∀x(FxGx)“:

1. xFx ∧ ∀xGx / ∀x(FxGx)
2. ¬∀x(FxGx) допускане
3. x¬(FxGx) от 2. по връзка между кванторите
4. ¬(FaGa) от 3. по EI
5. xFx от 1. по симплификация
6. xGx от 1. по симплификация
7. Fa от 5. по UI
8. Ga от 6. по UI
9. FaGa от 7. и 8. по конюнкция – противоречие с 4.
10. x(FxGx) от 2.-9. по свеждане до противоречие

С това логическата валидност на схемата еквивалентност „∀x(FxGx)“ ⇔ „∀xFx∧∀xGx“ е доказана. Валидността на другата схема еквивалентност (разпределимостта на екзистенциалния квантор в дизюнкцията) може да бъде доказана директно по същия начин, но може да бъде доказана и индиректно, чрез следното разсъждение. Очевидно е, че навсякъде в горните две доказателства може да заменим „Fx“ с „¬Fx“ и „Gx“ с „¬Gx“ (можем да си представим, че „F“ и „G“ са били съкращения за малко по-сложните изрази „¬F“ и „¬G“). Следователно налице е и следната валидна логическа еквивалентност:

„∀xFx ∧ ¬Gx)“ „∀x¬Fx ∧ ∀x¬Gx

Когато две формули са логически еквивалентни, техните отрицания също са логически еквивалентни. Причината е, че това, две формули да са логически еквивалентни, означава да имат еднаква истинностна стойност във всяка структура8. Като отречем двете твърдения, истинностната им стойност във всяка структура ще се смени и значи пак ще остане еднаква за двете. Така че налице е следната логическа еквивалентност:

„¬∀xFx ∧ ¬Gx)“ „¬(∀x¬Fx ∧ ∀x¬Gx)“

По Де Морган изразът от лявата страна на „⇔“ е логически еквивалентен на „¬∀x¬(FxGx)“ („(¬Fx ∧ ¬Gx)“ е заменено с „¬(FxGx)“), а този от дясната страна – на „¬∀x¬Fx ∨ ¬∀x¬Gx“; така че получаваме

„¬∀x¬(FxGx)“ „¬∀x¬Fx ∨ ¬∀x¬Gx

Като заменим навсякъде „¬∀x¬“ с „∃x“ по връзка между кванторите, получаваме втората търсена логическа еквивалентност

„∃x(FxGx)“ „∃xFx ∨ ∃xGx

Схемите еквивалентности за разпределимостта на универсалния квантор в конюнкцията и на екзистенциалния в дизюнкцията са валидни за всякакви формули – не само за частния случай на „Fx“ и „Gx“, който доказахме. В общ вид те са следните (на мястото на „α“ и „β“ могат да стоят произволни формули и променливата на мястото на „x“ може да е друга):

„∃х(α ∨ β)“ „∃хα ∨ ∃хβ“
„∀х(α ∧ β)“ „∀хα ∧ ∀хβ“

Първата схема ни дава право, когато обхватът на един екзистенциален квантор има формата на дизюнкция, да го разпределим между двата дизюнкта; и обратно – ако пред всеки от дизюнктите има екзистенциален квантор, да го изкараме пред дизюнкцията. Втората ни позволява да направим същото с всеки универсален квантор, когато обхватът му е конюнкция.

Разпределимостта на екзистенциалния квантор важи само по отношение на дизюнкцията, а на универсалния – само по отношение на конюнкцията, т.е. не е вярно нито „∃х(α ∧ β)“ ⇔ „∃хα ∧ ∃хβ“, нито „∀x(α ∨ β)“ ⇔ „∀хα ∨ ∀хβ“. Че това е така, може да се види с примери. Твърдението „Има нещо, което е кръгло, и има нещо, което е квадратно“ („∃хFx ∧ ∃хGx“) е истинно, докато твърдението „Има нещо, което е кръгло и квадратно“ („∃х(FxGx)“) не е. По същия начин твърдението „Всяко нещо е червено или не“ („∀х(Fx ∨¬Fx“) е истинно, докато твърдението „Всяко нещо е червено или всяко нещо не е червено“ („∀хFx ∨ ∀х¬Fx“) не е.

За въведената доказателствена процедура може да се докаже, че е коректна. Това означава, че ако тръгнем от някакви предпоставки и стигнем до някакъв извод в нея, то този извод следва логически от предпоставките от семантична гледна точка (т.е. истинен е във всички структури, в които са истинни предпоставките). За нея също може да се докаже, че е пълна. Това означава, че ако от семантична гледна точка едно твърдение следва от някакви твърдения (т.е. ако е истинно във всички структури, в които те са истинни), в процедурата съществува доказателство, което тръгва от въпросните предпоставки и стига до въпросния извод.9 Това доказателство обаче може никога да не бъде открито. Това, че в предикатната логика съществуват пълни доказателствени процедури, за първи път е доказано от Гьодел (Gödel, 1930). Пълнотата на една доказателствена процедура гарантира, че ако някакъв извод следва логически от някакви предпоставки, то в процедурата съществува доказателство за това, но не ни дава гаранция, че ще успеем да открием това доказателство. В липсата или наличието на такава гаранция се състои разликата между пълните доказателствени процедури и пълните разрешителни процедури, каквито бяха таблиците за истинност и истинностно-функционалния анализ в пропозиционалната логика. В предикатната логика няма пълни разрешителни процедури. Те не просто все още не са открити, а са невъзможни – факт, независимо доказан от Чърч (Church, 1936) и Тюринг (Turing, 1936). Така че, докато пропозиционалната логика е пълна и разрешима, предикатна логика е пълна, но неразрешима. Неразрешимостта на предикатната логика е забележителен факт от философска гледна точка, защото тя съвпада с това, което преди всички се разбира под „логика“ в съвременността. Неразрешимостта ѝ означава, че няма гаранция, че за произволен аргумент може да се разбере дали е логически валиден, или не!

Формални свойства на отношенията

Ще наричаме двуместните предикати (като „[1] е учител на [2]“, „[1] е по-голямо от [2]“ и т.н.) двуместни отношения. Съответно, ако даден двуместен предикат е истинен за някакви неща в определен ред, ще казваме, че първото се намира във въпросното отношение към второто. С това не се ангажираме със съществуването на отношенията, разбирани като абстрактни същности, а само със съществуването на отношенията, разбирани като предикати – неща от езика. Двуместните отношения имат определени формални характеристики, които ги подразделят в различни групи. Ще наричаме тези характеристики „формални свойства на отношенията“. Те могат да бъдат най-различни. Тук ще се спрем на свойствата рефлексивност, ирефлексивност, симетричност, асиметричност, транзитивност и интранзитивност.

Едно двуместно отношение е рефлексивно в някакво множество, ако за всяко нещо от множеството е изпълнено, че се намира във въпросното отношение към самото себе си. Рефлексивно е например отношението на идентичност в което и да е множество, защото за всяко нещо важи, че е идентично със самото себе си. Формалната дефиниция е, че отношението F е рефлексивно, когато е изпълнено

хFxx

Едно отношение е ирефлексивно в дадено множество, когато никое от нещата в множеството не се намира в това отношение към самото себе си. Такова е например отношението по-голямо в което и да е множество, тъй като нищо не е по-голямо от себе си. Формалната дефиниция е, че отношението F е ирефлексивно, когато е изпълнено

х¬Fxx

Едно отношение е симетрично в дадено множество, когато е изпълнено, че ако произволен елемент а от множеството се намира в това отношение към произволен елемент b от множеството, то задължително и b се намира в това отношение към a. Симетрично е например отношението на роднинството в множеството на хората, защото, ако някой е роднина на някого, то вторият също му е роднина. Формалната дефиниция е, че отношението F симетрично, когато е изпълнено

xy(FxyFyx)

Едно отношение е асиметрично в дадено множество, когато e изпълнено, че ако произволен елемент a от множеството се намира в това отношение към произволен елемент b от множеството, то b не се намира в това отношение към a. Асиметрично е например отношението по-възрастен в множеството на хората, тъй като, ако някой е по-възрастен от някого, то вторият не е по-възрастен, а е по-млад от първия. Асиметричността на произволно отношение F се изразява символно така:

xy(Fxy → ¬Fyx)

Едно отношение е транзитивно в дадено множество, когато е изпълнено, че ако произволен елемент а от множеството се намира в това отношение към произволен елемент b от множеството, а b от своя страна се намира в това отношение към произволен елемент c от множеството, то задължително също и a се намира в това отношение към c. Транзитивно е например отношението по-висок в което и да е множество, защото ако нещо е по-високо от друго нещо, а другото е по-високо от трето, то задължително първото ще е по-високо от третото. Транзитивността на произволно отношение F се изразява символно така:

xy[(FxyFyz) → Fxz]

Едно отношение е интранзитивно в дадено множество, когато е изпълнено, че ако произволен елемент a от множеството се намира в това отношение към произволен елемент b от множеството, а b от своя страна се намира в това отношението към произволен елемент c от множеството, то a задължително не се намира в това отношение към c. Интранзитивно е например отношението баща в множеството на хората, защото ако някой е баща на някого, a вторият е баща на трети (трета), то първият не е баща на третия (третата), а му (ѝ) е дядо. Интранзитивността на произволно отношение F се изразява символно така:

xy[(FxyFyz)→ ¬Fxz]

Всяко отношение има различни комбинации от формални свойства. Например отношението равно е рефлексивно, симетрично и транзитивно. Отношението по-висок е ирефлексивно, асиметрично и транзитивно. Отношението брат е ирефлексивно и не е нито симетрично, нито асиметрично (ако а е брат на b, то b може да му е брат, но може и да му е сестра, т.е. да не му е брат). Освен това то не е нито транзитивно, нито е интранзитивно (ако a и b имат само обща майка, а b и c само общ баща, то a и c нямат общи нито баща, нито майка). Отношението харесва пък не притежава нито едно от шестте разгледани формални свойства.

Някои формални свойства следват логически от едно или повече други. Например, ако едно отношение е ирефлексивно и транзитивно, то задължително е асиметрично. Това може да бъде доказано с нашата доказателствена процедура. За целта приемаме, че за произволно отношение F е изпълнено „∀x¬Fxx“ (условието за ирефлексивност) и „∀xyz[(FxyFyz) → Fxz]“ (условието за транзитивност) и доказваме, че от това следва „∀xy(Fxy → ¬Fyx)“ (условието за асиметричност):

1. х¬Fxx
2. xyz[(FxyFyz) → Fxz] / ∀xy(Fxy → ¬Fyx)
3. ¬∀xy(Fxy → ¬Fyx) допускане
4. xy¬(Fxy → ¬Fyx) от 3. по връзка между кванторите
5. y¬(Fay → ¬Fya) от 4. по EI
6. ¬(Fab → ¬Fba) от 5. по EI
7. (FabFba) → Faa от 2. по UI (три пъти)10
8. ¬Faa от 1. по UI
9. Fab ∧ ¬¬Fba от 6. по мат. импликация
10. FabFba от 9. по двойно отрицание
11. Faa от 10. и 7. по модус поненс – противоречие с 8.
12. xy(Fxy → ¬Fyx) от 3.-11. по свеждане до противоречие

Задачи

(Изтеглете задачите като pdf.)

(1) Определете дали следните двойки изрази са логически еквивалентни. Ако не се, променете един от кванторите във втория израз (ако е екзистенциален да стане универсален, и обратно), така че да станат еквивалентни.

1) ¬∀y y¬
2) ¬∃x¬ ¬¬∀x
3) x¬∀yz¬ ¬∃xy¬∀z
3) x¬∀yz¬ ¬∃xy¬∀z
4) x¬¬∃y¬ ¬∃xy
5) x¬∀yz¬ xyz
6) ¬∃xyz xyz¬
7) xy¬∀zw¬ xyzw
8) xy¬∀zw¬ ¬∀xyz¬∀w
9) xy¬∀zw¬ xyz¬∃w¬
10) xyzw¬ ¬∀xyzw

(2) Правилна ли инстанциацията? Ако не е, къде е грешката?

1) x(FxaGbx)
FbaGbb
2) z(Faz ∧ ¬Fzz) → Fab
(Fab ∧ ¬Fbb) → Fab
3) xyz[(Fxa ∧ ¬Fya) → Gxyz]
yz[(Fba ∧ ¬Fya) → Gxyz]
4) xy[∀zFzxy → ∃zGaz]
y[∀zFzay → ∃zGaz]
5) y(Gay ∨ ¬∀xHbxy)
Gab ∨ ¬∀xHbxa
6) ¬∀x(FxaGax)
¬(FbaGab)
7) xyFxy → ∀yxFxy
yFay → ∀yFay
8) x[Fxbx ∧ (¬∃yGxyHxbx)]
Fbbb ∧ (¬∃yGbyHaba)

(3) Отдолу са дадени части от доказателства, в които има инстанциации. Правилни ли са инстанциациите и ако има грешка, къде е тя?

1) 1. ¬∀xFxx
2. zGzz
3. Gaa от 2. по EI
4. ¬Faa от 1. по UI
2) 1. xFxa
2. x¬Gxx
3. ¬Gaa от 2. по EI
4. Faa от 1. по UI
3) 1. xFxb
2. yGay
3. Fbb от 1. по EI
4. Gab от 2. по UI
4) 1. xFax
2. x¬Fax
3. Faa от 1. по UI
4. ¬Fab от 2. по EI
5) 1. ¬∀xFax
2. zGbz
3. Gba от 2. по EI
4. ¬Faa от 1. по UI
6) 1. xyFxy
2. xyGyx
3. yFay от 1. по EI
4. yGya от 2. по UI

(4) Докажете (със средствата на предикатната логика) валидността на следните силогизми:

1) EAE-1
2) AEE-2
3) OAO-3
4) EIO-2
5) EIO-4
6) AOO-2

(5) Докажете валидността на следните изводи:

1) xFx → ¬Gx)
xGx
xFx
2) x(FxGx)
xFx ∨ ∀xGx
3) ухFyx11
хуFyx
4) x(FxGx)
x(Fx∨¬Gx)
xFx
5) x(FxGx) ∨ ∃x(Fx∧¬Gx)
xFx
6) x(Fx → ∀yzGxyz)
xy¬Gaxy
¬Fa

(6) Докажете валидността на следните изводи, като използвате означенията:

1) Нито един човек не е съвършен. F – [1] е човек, G – [1] е съвършен, a – Сократ
Сократ е човек.
Сократ не е съвършен.
2) Сократ е философ. F – [1] е философ, G – [1] е мъдър, a – Сократ
Сократ е мъдър.
Някой философи са мъдри.
3) Петър или Иван не е учтив. F – [1] е учтив, a – Иван, b – Петър, D – хората
Ако Иван е учтив, всеки е учтив.
Иван не е учтив.
4) Иван може да победи всеки от отбора, който е по-възрастен от него. F – [1] може да победи [2], G – [1] е по-възрастен от [2], a – Иван, b – Петър, D – отбора
Петър не е по-възрастен от никой от отбора, който може да го победи.
Петър не е по-възрастен от Иван.
5) Всички тела се привличат.12 F – [1] привлича [2], G – [1] е тяло
а и b са тела.
b привлича a.
6) Всяко нещо или съществува във времето и пространството, или е абстрактно. F – [1] е абстрактно, G – [1] е число, H – [1] съществува във времето и пространството
Числата не съществуват във времето и пространството.
Числата са абстрактни.
7) Всеки, който е чел и Хамлет, и Отело, харесва Хамлет. F – [1] е чел Хамлет, G – [1] е чел Отело, H – [1] харесва Хамлет, D – хората
Някои, които са чели Хамлет, не го харесват.
Някои, които са чели Хамлет, не са чели Отело.
8) Нито едно гръбначно животно, което има бъбреци, не е земноводно. F – [1] е гръбначно, G – [1] има бъбреци, H – [1] е земноводно, D - животните
Ако едно земноводно има бъбреци, то е гръбначно.
Никое земноводно няма бъбреци.
9) На прожекцията се допускат само пълнолетни, които са си купили билет. F – [1] се допуска на прожекцията, G – [1] е пълнолетен, H – [1] си е купил билет, D – хората
Някои, които са си купили билет, са непълнолетни.
Някои, които не се допускат на прожекцията, са си купили билет.
10) Всички окръжности са фигури.13 F – [1] е окръжност, G – [1] е фигура, H – [1] чертае [2]
Всеки, който чертае окръжност, чертае фигура.
11) Има постъпки, които всички хора осъждат. F – [1] е постъпка, G – [1] е човек, H – [1] осъжда [2]
Всеки човек осъжда една или друга постъпка.
12) Всеки от форума харесва Амаркорд. F – [1] е от форума, G – [1] харесва Амаркорд, H – [1] е гледал Амаркорд, D – хората
Или никой от форума не е гледал Амаркорд, или ако някой го е гледал, го харесва.
13) Има постъпки, които са осъждани от всеки, който осъжда някакви постъпки. F – [1] е постъпка, G – [1] е човек, H – [1] осъжда [2]
Всеки осъжда една или друга постъпка.
Има постъпки, които всички осъждат.
14) Харесвам всеки, който се смее на самия себе си. F – харесвам [1], G – [1] се смее на [2], H – мразя [1], I – [1] е приятел на [2]
Мразя всеки, който се смее на всичките си приятели.
Ако мразя някого, аз не го харесвам.
Ако съществува някой, който се смее на всичките си приятели, то съществува някой, който не е приятел на самия себе си.

(7) Докажете, че следните формули са логически валидни:

1) x(∀yFyFx)
2) x(∀yFyFx)
3) x(Fx → ∃yFy)
4) xy(∀zFyzxFyyx)

(8) Въз основа на разпределимостта на кванторите в конюнкцията или дизюнкцията, определете дали следните двойки формули са логически еквивалентни:

1) xFxaGxb) x¬Fxa ∨ ∀xGxb
2) x(Fxa ∧ ¬Gax) xFxa ∧ ¬∃xGax
3) xFxb ∨ ¬Gxa) ¬∀xFbx ∧ ¬∀xGxz
4) yGyb ∧ ¬Hay) ¬∀yGyb ∧ ∃y¬Hay

(9) Какви са формалните свойства на следните отношения?

1) по-малко или равно в множеството на естествените числа
2) сестра в множеството на хората
3) съсед в множеството на хората
4) връстник (имащ същата възраст) във множеството на хората
5) учител в множеството на хората
6) майка в множеството на хората
7) по-голямо с 2 в множеството на естествените числа
8) харесва в множеството на хората
9) подчинен в една армия
10) по-богат в множеството на хората

(10) Докажете че:

1) Ако едно отношение е асиметрично, то е също ирефлексивно.
2) Ако едно отношение е интранзитивно, то е също ирефлексивно.


1. „Инстанциация“ буквално съответства на английската дума „instantiation“, която е свързана с думата „instance“ – „отделен случай“, „пример“. 2. Виж „1.8 Естествена дедукция“. 3. Такива доказателствени процедури се наричат пълни – виж края на „3.4 Синтаксис и семантика на предикатната логика“. 4. „EI“ е съкращение за „екзистенциална инстанциация“. 5. „UI“ е съкращение за „универсална инстанциация“. 6. Виж „3.4 Синтаксис и семантика на предикатната логика“. 7. Тук връзката между кванторите е приложена върху поредица от квантори с отрицание от едната ѝ страна. Като резултат отрицанието отива от другата страна и всички квантори се обръщат. 8. Виж „3.4 Синтаксис и семантика на предикатната логика“. 9. Това важи също и за формулите със свободни променливи – не само за твърденията. Те могат да бъдат заменени с техните универсални затваряния, след което можем да използваме дефиницията за логическо следване, която дадохме в „3.4 Синтаксис и семантика на предикатната логика“. Тя свеждаше логическото следване между формули със свободни променливи, до логическо следване между техните универсални затваряния. 10. „x“ е инстанциирано с „a“, „y“ – с „b“ и „z“ – отново с „a“. 11. Споменахме този извод в „3.3 Възможностите на езика на предикатната логика“. Предпоставката би могла да бъде „Някой обича всички“, а заключението – „Всеки е обичан от някого“. 12. Споменахме този извод в „3.3 Възможностите на езика на предикатната логика“. 13. Споменахме този извод в „3.3 Възможностите на езика на предикатната логика“.