3.5 Доказателствена процедура
Ще въведем доказателствена процедура, чрез която ще можем да доказваме, че от някакви
формули на предикатната логика логически следват други, че две формули са логически
еквивалентни, както и че дадена формула е логически валидна. По-късно, в
5.1. Пълнота на предикатната логика, ще покажем, че тази доказателствена
процедура е коректна и пълна. Коректността на една доказателствена
процедура означава, че заключението на всяко възможно доказателство с нея наистина
следва логически (от семантична гледна точка) от предпоставките, т.е. във
всяка структура, в която са истинни предпоставките, е истинно и заключението
(за семантичното понятие за логическо следване виж
предишната секция).
Пълнотата е обратното на коректността. Когато една доказателствена процедура е пълна,
имаме гаранцията, че ако една формула следва логически (от семантична гледна
точка) от някакви формули-предпоставки, то в процедурата съществува доказателство,
което тръгва от предпоставките и стига до заключението. Това, че такова доказателство
съществува обаче не означава, че непременно ще можем да го намерим, тъй като в
предикатната логика няма и не може да има общи разрешителни процедури за
логическо следване. За това стана дума в края на
предишната секция.
Връзка между кванторите
Интуитивно универсалните твърдения изглеждат по-общи от екзистенциалните, доколкото
(на пръв поглед) изглежда, че думата „всичко“ се отнася до всички неща, а израза
„поне едно“ не. Всъщност и при двете има отнасяне към всичко нещо. С универсалните
твърдения казваме, че всяко нещо удовлетворява определено условие, а с
екзистенциалните – че измежду всички неща има поне едно, което удовлетворява
определено условие. За да установим, че едно универсално твърдение е истинно,
трябва да установим, че всички неща удовлетворяват въпросното условие. За да
установим, че едно екзистенциално твърдение е неистинно, трябва да установим,
че всички неща не го удовлетворяват. Следователно, определянето на истинностната
стойност и на двата вида твърдения предполага отнасяне към всички неща. Нещо повече,
между екзистенциалния и универсалния квантор съществува смислова връзка, която позволява
всичко, което може да се изрази чрез единия, да се изрази и чрез другия.
Да се каже, че не съществува нещо, което е F, е същото като да се каже, че всичко е не-F. Например, да се каже, че не
съществуват съвършени неща („¬∃хFх“), е същото като да се каже, че всички неща са несъвършени („∀х¬Fх“).
Следователно между двата квантора е налице следната връзка (на мястото на „x“ може да е всяка друга променлива):
Освен това, да се каже, че не всичко е F („¬∀хFх“), е същото като да се каже, че нещо не е F („∃х¬Fх“)
– например, да се каже, че не всички неща са съвършени, е същото като да се каже, че някои неща не са съвършени. Така че между екзистенциалния
и универсалния квантор съществува също следната връзка:
Двете връзки могат да бъдат обобщени така:
|
Когато от едната страна на един квантор има отрицание, то може да мине от другата му страна, като кванторът се обърне
– ако е бил екзистенциален, стане универсален; и ако бил универсален, стане екзистенциален.
|
Въз основа на (1) „¬∃х¬“ има същия смисъл като „∀х¬¬“ („¬∃х“
в предишния израз е заменено с „∀х¬“). Като махнем двойното отрицание в „∀х¬¬“,
получаваме, че „¬∃х¬“ има същия смисъл като „∀х“. Например, да се каже, че
не съществуват неща, които не са съвършени („¬∃х¬Fx“), е същото като да се каже, че всички
неща са съвършени („∀хFx“). Така че имаме още следната еквивалентност:
От (3) следва, че всичко, което може да бъде изразено чрез универсален квантор, може да бъде изразено и чрез екзистенциален квантор
и отрицание – можем навсякъде да заменим „∀х“ с „¬∃х¬“.
Въз основа на (2) „¬∀х¬“ казва същото като „∃х¬¬“
(„¬∀х“ в първия израз е заменено с „∃х¬“). Като махнем двойното
отрицание в „∃х¬¬“, получаваме, че „¬∀х¬“ има същия смисъл като „∃х“.
Например, да се каже, че не всичко е несъвършено, е същото като да се каже, че нещо
е съвършено. Така че налице е също следната връзка между кванторите:
От (4) следва, че всичко, което може да бъде казано с екзистенциален квантор, може да бъде казано и с универсален квантор и
отрицание – можем да заменим навсякъде „∃х“ с „¬∀х¬“.
Следната таблица обобщава връзката между кванторите.
| За всяко нещо важи, че не е ... |
∀x¬(...x...) |
¬∃x(...x...) |
Не съществува нещо, което е ... |
| Не всяко нещо е ... |
¬∀x(...x...) |
∃x¬(...x...) |
Съществува нещо, което не е ... |
| Не е вярно, че всяко нещо не е ... |
¬∀x¬(...x...) |
∃x(...x...) |
Съществува нещо, което е ... |
| Всяко нещо е ... |
∀x(...x...) |
¬∃x¬(...x...) |
Не съществува нещо, което не е ... |
Нека видим как бихме могли да използваме връзката между кванторите. Да разгледаме израза
От връзката между кванторите той е логически еквивалентен на следните изрази:
„¬∃х¬∃уFху“ („∀х“ е заменено с „¬∃х¬“);
„∀х¬∀у¬Fху“ („∃у“ е заменено с „¬∀у¬“);
„¬∃х∀у¬Fху“ (като направим и двете предишни замени, получаваме
„¬∃х¬¬∀у¬Fху“, след което махаме двойното отрицание).
Връзката между кванторите (в частност (1) и (2), които обобщихме в правилото,
че отрицание може да мине от другата страна на един квантор, като кванторът се обърне)
позволява, когато имаме поредица от квантори с отрицание от едната ѝ страна, например
„∃х∀y∃z¬“, отрицанието да мине от другата страна на цялата поредица,
като всеки от кванторите се обърне – екзистенциалните станат универсални, а универсалните
екзистенциални. Така че „∃х∀y∃z¬“ може да се замени
с „¬∀х∃y∀z“. Основанието за това е
следното. Изразът „∃х∀y∃z¬…“ е логически еквивалентен на
„∃х∀y¬∀z…“ („∃z¬“ е заменено с „¬∀z“). От своя страна
последният израз е еквивалентен на „∃х¬∃y∀z…“ („∀y¬“ е заменено
с „¬∃y“), който пък е еквивалентен на „¬∀х∃y∀z…“ („∃х¬“
е заменено с„¬∀х“). По същия начин, тръгвайки от израза
„¬∃х∃y∀z¬…“, може да преместим първото отрицание отзад или второто отпред,
обръщайки кванторите, като в резултат ще стигнем съответно до „∀х∀y∃z¬¬…“
или до „¬¬∀х∀y∃z…“. Като махнем двойното отрицание, и в двата случая получаваме
„∀х∀y∃z…“.
Също така, ако имаме произволна поредица от квантори и отрицания, например
„¬∀х¬∀y∃z¬“, „¬∃х∃y¬∃z“ и т.н.,
тя може да се преобразува в поредица само от квантори (без отрицания между тях),
като евентуално от едната ѝ страна има отрицание. За целта преместваме всички
вътрешни отрицания напред или назад (обръщайки кванторите, през които преминаваме).
Така получаваме една до друга две поредици – само от квантори и само от отрицания.
Ако отрицанията са четен брой, махаме всичките по схемата еквивалентност на
двойното отрицание; ако са нечетен, остава само едно.
Универсална и екзистенциална инстанциация
Универсалната инстанциация
е логически валидна схема за извод, въз основа на която от това, че някакво
условие е изпълнено за всички неща, можем да заключим, че е изпълнено за
едно конкретно от тях.
|
∀хFx
|
|
∀x(Fx → ¬∃yGxy)
|
|
∀х(Fxa → Fxb)
|
|
∀х(Fxa → Fxb)
|
|
Fa
|
|
Fа → ¬∃yGаy
|
|
Fаa → Fаb
|
|
Fba → Fbb
|
В първия пример от това, че всяко нещо е F, се заключава, че конкретното нещо
a е F. Във втория предпоставката е по-сложна, но отново е универсално
твърдение, в което се казва, че за всяко нещо е изпълнено определено условие – а именно,
че ако нещото е F, то не се намира в релацията G към нищо. След като това
условие е изпълнено за всяко едно нещо x, значи ще е изпълнено и за конкретното нещо
а, така че двете участия на „x“ в условието са заместени с „а“ в
заключението. В случаи като този и предишния ще казваме, че променливата на универсалния
квантор „x“ е инстанциирана с индивидната константа „а“. Третият и
четвъртият пример имат една и съща предпоставка, но променливата на универсалния квантор
в първия случай е инстанциирана с „a“, а във втория – с „b“.
Формално, при инстанциацията (както универсалната, така и екзистенциалната) махаме квантора
в началото на израза и заместваме всички (вече) свободни участия на променливата
на квантора с инстанциираната индивидна константа. В случай че участията на променливата са
повече от едно, би било неправилно да не заменим някое от тях с инстанциираната константа. Например по
универсална инстанциация от „∀хFxx“ можем да изведем „Faa“, но не и „Fах“.
Нека „F“ е предиката „…е еднакво с…“. От това, че всяко нещо е еднакво със себе
си, следва, че a е еднакво с a, но не следва, че а е еднакво с х
(„Fах“) – х може да е което и да е нещо и значи може и да е различно от а.
Отделно, „a е еднакво с x“ не е твърдение, а отворено изречение.
Екзистенциалната инстанциация e като универсалната с тази разлика, че кванторът
е екзистенциален. Тя обаче не е логически валидна схема за извод. По екзистенциална
инстанциация от „∃хFx“ бихме получили „Fa“, „Fb“, … и т.н. Това няма
да се логически валидни изводи, защото може да е вярно, че съществува нещо, което е
F, но да не е вярно, че тъкмо конкретното нещо а (съответно b, …)
е F. Въпреки че екзистенциалната инстанциация не е логически валидна схема за извод,
ще я използваме по такъв начин, че да не извеждаме твърдения, които не следват от предпоставките
(ще видим след малко как). Също както при универсалната инстанциация и тук трябва да се
инстанциират всички (вече) свободни участия на променливата, след като кванторът се махне.
Например от „∃х(Fxa→Fxb)“ може да получим „Fсa→Fсb“, но
не и „Fхa→Fсb“ или „Fсa→Fxb“.
Доказателствена процедура в предикатната логика
Доказателствената процедура, която ще използваме в предикатната логика, е разширение
на естествената дедукция в пропозиционалната логика
(виж 1.8 Естествена дедукция). В нея използвахме
определени правила за извод,
схеми еквивалентности (в комбинация с принципа за
заменимост на еквивалентните),
както и процедурите на
индиректното доказателство (доказателство чрез
свеждане до противоречие) и на
условното доказателство. Сега към
схемите за извод ще добавим универсалната инстанциация, а към схемите еквивалентности –
четирите схеми на връзката между кванторите. Последното нещо, което ще добавим е
екзистенциалната инстанциация, но тя ще има особен статут, тъй като не е логически валидна
схема за извод и ще я прилагаме с едно ограничение. Преди да видим какво е то и защо е необходимо,
нека първо кажем няколко думи по отношение на принципа за заменимост на еквивалентните.
Формално ще го използваме по същия начин като в пропозиционалната логика
– когато някаква подформула на вече изведена формула има формата на една от страните на някоя
от схемите еквивалентности, можем да заменим тази подформула с израз, които има формата на
другата страна на схемата. Самият факт обаче, че принципът се използва върху формули на
предикатната логика, го прави по-силен и може би не толкова непосредствено
очевиден. Работата е
там, че заместваните въз основа на принципа изрази биха могли да са отворени изречения,
а не твърдения. Така реално едно с друго се заместват не изречения, а части на изречения.
Например от „∃x¬(Fx∧Gx)“ по Де Морган бихме могли да изведем
„∃x(¬Fx∨¬Gx)“. Основанието зад този извод е, че отвореното изречение
„¬(Fx∧Gx)“ е логически еквивалентно на отвореното изречение „¬Fx∨¬Gx“.
Съответно, ако на „F“ отговаря „скъп“, а на „G“ – „минерал“, въпросното основание
е, че предикатът „…не е скъп минерал“ е логически еквивалентен на предикатът „…не е
скъп или не е минерал“, поради което може да бъде заменен с последния. В пропозиционалната логика
всяка формула има истинностна стойност при някаква интерпретация, затова въз основа на принципа
там се заменят само твърдения с еквивалентни твърдения. В предикатната логика освен това
можем да заменяме и предикати.
Ограничението при екзистенциалната инстанциация е, че
инстанциираната индивидна константа трябва да е нова – да не се среща в предпоставките,
заключението и предхождащите стъпки на доказателството. Благодарение на това ограничение,
доказателствата, в които се използва екзистенциалната инстанциация, ще бъдат коректни, т.е.
заключението ще следва от предпоставките, въпреки че самата схема не е логически валидна. Ето
един пример за коректно доказателство, в което се използва екзистенциална инстанциация. Искаме
да докажем, че от твърдението „Има нещо, което е създало всичко“ логически следва твърдението
„Има нещо, което е създало самото себе си“. Представяме символно предиката „…е създало…“ с „F“ и
целта ни е да докажем, че от формулата „∃х∀уFxy“ следва „∃хFxx“:
Ще използваме доказателство чрез свеждане до противоречие – ще допуснем отрицанието на извода
и ще се стремим да стигнем до противоречие.
От връзката между кванторите „¬∃хFxx“ е логически еквивалентно на „∀х¬Fxx“:
|
3.
∀х¬Fxx
от 2. по връзка между кванторите
|
По принцип ще използваме връзката между кванторите, за да преместваме кванторите
най-отпред, така че изразите да стават екзистенциални или универсални твърдения,
с идеята след това да направим екзистенциална или универсална инстанциация. В случая
в 2. твърдението има формата на отрицание, но в 3. вече е универсално твърдение, от
което може да се правят универсални инстанциации.
Следващата ни стъпка ще е екзистенциална инстанциация – от 1. ∃х∀уFxy
(„Съществува нещо, което е създало всички неща“) ще изведем „∀уFay“ („a
е създало всички неща“). По принцип на екзистенциалната инстанциация отговаря следният
ход в едно разсъждение: изхождайки от това, че съществува нещо, за което е изпълнено
дадено условие, обозначаваме това нещо с произволно, неизползвано досега име (нова индивидна
константа в символния ни език), за да може по-лесно да говорим за него. Ако
има повече такива неща (екзистенциалните твърдения ни казват, че съществува
поне едно нещо, за което е изпълнено някакво условие, а не че съществува
точно едно такова неща), името ще се отнася до някое определено от тях – все едно кое.
В случая, изхождайки от това, че съществува нещо, което е създало всички неща, въвеждаме
неизползваната индивидна константа „a“, за да го обозначава по-нататък в доказателството
(ако повече от едно неща са създали всичко, „a“ ще обозначава
някое определено от тях):
От 4. по универсалната инстанциация можем да изведем „Faa“ (от това, че а
е създало всички неща („∀уFаy“), понеже самото то е някакво нещо, логически
следва, че е създало и самото себе си):
От друга страна от 3. („∀x¬Fxx“) отново по универсална инстанциация следва „¬Faa“, което противоречи на „Fаа“:
|
6.
¬Fаа
от 3. по UI – противоречие с 5.
|
От противоречието извеждаме отрицанието на допуснатото в 2. твърдение („¬∃хFxx“), т.е. получаваме „∃хFxx“, което искахме да докажем:
|
7.
∃хFxx
от 2.-6. по свеждане до противоречие
|
Това, че използваме екзистенциалната инстанциация не като схема за извод, а за да именуваме
нещо, е причината инстанциираната константа да трябва да е нова. Ако например
„а“ се среща по-рано в
някакво доказателство (било то в някоя от предпоставките, било в някое изведено твърдение,
било в твърдението, което се стремим да докажем), тя вече би обозначавала за нас нещо
в дадения контекст. Екзистенциалното твърдение, от което правим
инстанциацията, ни гарантира, че съществува нещо, за което е изпълнено определено условие,
но от него не следва, че това нещо непременно е същото нещо, което вече
обозначаваме с „a“ – би могло и да е друго. Затова трябва да изберем ново,
неизползвано име за да го обозначим, да кажем „b“. b и a може
да са различни неща, а може и да не са. Ако са едно и също нещо, константите
„a“ и „b“ ще функционират като две различни негови имена, така както
„Вечерница“ и „Зорница“ са две различни имена на планетата Венера. Ако са различни неща
обаче, е ключово да бъдат обозначавани с различни имена, откъдето идва и ограничението за
екзистенциалната инстанциация.
Нека видим какво би станало, ако не спазваме ограничението при екзистенциална инстанциация
инстанциираната константа да е нова. Например от истината, че има синеоки хора
(„∃х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“ не е нова.
При универсалната инстанциация нямаме такова ограничение, защото, щом някакво условие е изпълнено за всички неща, то ще е изпълнено за всяко едно нещо, независимо
от това дали сме говорили за него преди, или не.
За разлика от пропозиционалната логика, където в естествената дедукция много често
можеше да се мине без използване на доказателства чрез допускане (доказателство чрез
свеждане до противоречие или условно доказателството), тук почти винаги ще използваме
такива доказателства. Стандартният начин, по който ще си служим с доказателствената
процедура, е да допускаме отрицанието на заключението и да стигаме до противоречие. В
случай, че използваме условно доказателство обаче, трябва да внимаваме заключението да
не съдържа константи, въведени посредством екзистенциална инстанциация
в рамките на същото това условно доказателство. Основанието е отново ограничението
върху екзистенциалната инстанциация. Когато използваме индиректни или условни доказателства
всъщност правим под-доказателства в рамките да главното доказателство, чрез които доказваме,
че определено твърдение следва от предпоставките – въпросното твърдение е заключението
на под-доказателството. Ограничението обаче не позволяваше въведени с ЕI константи в
рамките на едно доказателство да се съдържат в заключението му. Следователно, въведени с
EI в рамките на едно условно доказателство константи не трябва да се съдържат в неговото
заключение. При индиректното доказателство такава опасност няма, защото там заключението
е отрицание на допускането и няма как то да съдържа някаква въведена в последващото доказателство нова
константа. Както показва следващият пример обаче, при условното доказателство има такава
опасност. Формулата „∃xFx→Fa“ не е логически валидна (например изречението
„Ако съществуват патици, то Сократ е патица“ е неистинно, защото патици съществуват, а
Сократ не е патица). Да разгледаме обаче следното „доказателство“, че тази формула е
логически валидна:
|
1.
∃xFx
допускане
|
|
2.
Fa
от 1. по EI
|
|
3.
∃xFx → Fa
oт 1. – 2. по условно доказателство
|
Грешката е, че в заключението на условното доказателство присъства константа, въведена
с EI в рамките на самото условно доказателство. Ограничението върху екзистенциалната
инстанциация забраняваше по принцип въведени в едно доказателство с EI константи да
присъстват в неговото заключение. Така че, когато използваме условно доказателство,
трябва да внимаваме заключението му да не съдържа константи, които са въведени
в самото него с екзистенциална инстанциация (ако са въведени преди това не е
проблем).
Като следващ (вече коректен) пример нека докажем валидността на един силогизъм
– АII-1 (Darii):
|
Всяко M е Р.
|
|
Някои S са М.
|
|
Някои S са Р.
|
Изразен в езика на предикатната логика, той има следния вид:
|
∀х (Mx → Px)
|
|
∃x (Sx ∧ Mx)
|
|
∃x (Sx ∧ Px)
|
Ето едно доказателство, че тази схема за извод е валидна (в скоби са
дадени неформалните разсъждения, които стоят зад използваните инстанциации):
|
1.
∀х(Mx → Px)
|
|
2.
∃x(Sx ∧ Mx)
/ ∃x(Sx ∧ Px)
|
|
3.
¬∃x(Sx ∧ Px)
допускане
|
|
4.
∀x¬(Sx ∧ Px)
от 3. по връзка между кванторите
|
|
5.
Sa ∧ Ma
от 2. по EI (2. ни казва, че има някакво нещо, което е едновременно
S и M – означаваме го с „а“)
|
|
6.
Mа → Pа
от 1. по UI (1. ни казва, че за всяко нещо е изпълнено условието, че ако е M,
то е и P. Tова условие ще e изпълнено и за конкретното нещо a.)
|
|
7.
¬(Sa ∧ Pa)
от 4. по UI (4. ни казва, че за всяко нещо е изпълнено условието
„¬(S... ∧ P...)“. Следователно това условие ще е изпълнено и за a.)
|
|
8.
Mа
от 5. по симплификация
|
|
9.
Pa
от 6. и 8. по модус поненс
|
|
10.
Sa
от 5. по симплификация
|
|
11.
Sa ∧ Pa
от 10. и 9. по конюнкция – противоречие с 7.
|
|
12.
∃x(Sx ∧ Px)
от 3.-11. по свеждане до противоречие
|
Чрез екзистенциалните инстанциации в доказателствата се въвеждат нови индивидни
константи, докато универсалните инстанциации се прилагат върху вече налични
индивидни константи. Затова като правило в едно доказателство първо правим
екзистенциални инстанциации, с което си осигуряваме индивидни константи,
върху които след това можем да направим универсални инстанциации. Например в
горното доказателство отначало нямаше индивидни константи. Затова чрез екзистенциална
инстанциация въведохме константата „а“, по отношение на която след това
в 6. и 7. направихме универсални инстанциации от двете универсални твърдения.
Ако обаче в предпоставките няма индивидни константи и не разполагаме с екзистенциални
твърдения, чрез които да въведем такива, тогава, за
да задвижим процеса, може да направим универсални инстанциации с произволна
индивидна константа (например с „a“). Това е оправдано доколкото
в света (универсума на дискурса) има поне едно нещо. Това, че
съществува поне едно нещо, се приема по конвенция в семантиката на предикатната
логика – свят, в който няма нищо, е логически възможен, но е безинтересен от
логическа и всякаква гледна точка. В езика, който говори за такъв свят, не може
да има индивидни константи и в него всяко универсално твърдение е истинно, а всяко
екзистенциално неистинно.
Освен, че дадени изводи са логически валидни, с въведената доказателствена
процедура можем да доказваме, че дадени формули (твърдения) са логически
валидни. За целта е достатъчно да покажем, че допускането на отрицанието на
формулата (т.е. допускането, че формулата е неистинна) води до противоречие. Тогава
за нея ще е логически невъзможно да е неистинна, което значи, че ще е истинна
във всяка структура,
т.е. ще е логически валидна. В пропозиционалната логика правихме същото, за да
доказваме, че дадени формули са тавтологии.
Като пример ще докажем логическата валидност на
„∀x∃y∃z(Fxy → Fzx)“:
|
1.
¬∀x∃y∃z(Fxy → Fzx)
допускане
|
|
2.
∃x∀y∀z¬(Fxy → Fzx)
от 1. по
връзка между кванторите
|
|
3.
∀y∀z¬(Fay → Fza)
от 2. по EI („x“ е инстанциирано с „а“)
|
|
4.
∀z¬(Faa → Fza)
от 3. по UI („y“ е инстанциирано с „а“)
|
|
5.
¬(Faa → Faa)
от 4. по UI („z“ е инстанциирано с „а“)
|
|
6.
Faa ∧ ¬Faa
от 7. по мат. импликация – противоречие
|
|
7.
∀x∃y∃z(Fxy → Fzx)
от 1.-6. по свеждане до противоречие
|
За да докажем, че две формули са логически еквивалентни, е достатъчно да
докажем, че следват логически една от друга. Като пример, а и защото са важни
сами по себе си, ще докажем валидността на следните две еквивалентности, които
ни позволяват да разпределяме универсалния квантор в конюнкцията и
екзистенциалния в дизюнкцията:
|
∀x(Fx ∧ Gx)
⇔
∀xFx ∧ ∀xGx
|
|
∃x(Fx ∨ Gx)
⇔
∃xFx ∨ ∃xGx
|
Първо доказваме, че от „∀x(Fx ∧ Gx)“ логически следва „∀xFx ∧ ∀xGx“:
|
1.
∀x(Fx ∧ Gx)
/ ∀xFx ∧ ∀xGx
|
|
2.
¬(∀xFx ∧ ∀xGx)
допускане
|
|
3.
¬∀xFx ∨ ¬∀xGx
от 2. по Де Морган
|
|
4.
∃x¬Fx ∨ ∃x¬Gx
от 3. по връзка между кванторите
|
|
5.
∃x¬Fx
допускане
|
|
6.
¬Fa
от 5. по EI
|
|
7.
Fa ∧ Ga
от 1. по UI
|
|
8.
Fa
от 7. по симплификация – противоречие с 6.
|
|
9.
¬∃x¬Fx
5.-8. по свеждане до противоречие
|
|
10.
∃x¬Gx
от 4. и 9. по дизюнктивен силогизъм
|
|
11.
¬Gb
от 10. по EI
|
|
12.
Fb ∧ Gb
от 1. по UI
|
|
13.
Gb
от 12. по симплификация – противоречие с 11.
|
|
14.
∀xFx ∧ ∀xGx
от 2.–13. по свеждане до противоречие
|
След това доказваме, че от „∀xFx ∧ ∀xGx“ следва „∀x(Fx ∧ Gx)“:
|
1.
∀xFx ∧ ∀xGx
/ ∀x(Fx ∧ Gx)
|
|
2.
¬∀x(Fx ∧ Gx)
допускане
|
|
3.
∃x¬(Fx ∧ Gx)
от 2. по връзка между кванторите
|
|
4.
¬(Fa ∧ Ga)
от 3. по EI
|
|
5.
∀xFx
от 1. по симплификация
|
|
6.
∀xGx
от 1. по симплификация
|
|
7.
Fa
от 5. по UI
|
|
8.
Ga
от 6. по UI
|
|
9.
Fa ∧ Ga
от 7. и 8. по конюнкция – противоречие с 4.
|
|
10.
∀x(Fx ∧ Gx)
от 2.-9. по свеждане до противоречие
|
С това логическата еквивалентност на „∀x(Fx∧Gx)“ и
„∀xFx∧∀xGx“ е доказана. Валидността на втората еквивалентност
(при която екзистенциалният квантор се разпределя в дизюнкцията) може да бъде
доказана директно по същия начин, a може да бъде доказана и индиректно, чрез
следното разсъждение. Очевидно е, че навсякъде в горните две доказателства може
да заменим „Fx“ с „¬Fx“ и „Gx“ с „¬Gx“ (можем да си
представим, че „F“ и „G“ са били съкращения за малко по-сложните
изрази „¬F“ и „¬G“). Следователно валидна е и следната еквивалентност:
|
∀x(¬Fx ∧ ¬Gx)
⇔
∀x¬Fx ∧ ∀x¬Gx
|
Когато две формули са логически еквивалентни, техните отрицания също са такива.
Причината е, че две формули да са логически еквивалентни, когато имат еднаква
истинностна стойност във всяка структура (виж
3.4 Синтаксис и семантика на предикатната логика).
Като отречем твърденията, във всяка структура истинностната им стойност ще се смени,
но пак ще остане еднаква за двете. Така че имаме следното:
|
¬∀x(¬Fx ∧ ¬Gx)
⇔
¬(∀x¬Fx ∧ ∀x¬Gx)
|
По Де Морган изразът от лявата страна на „⇔“ е логически еквивалентен
на „¬∀x¬(Fx ∨ Gx)“ („(¬Fx ∧ ¬Gx)“ е
заменено с „¬(Fx ∨ Gx)“),
а този от дясната страна – на „¬∀x¬Fx ∨ ¬∀x¬Gx“:
|
¬∀x¬(Fx ∨ Gx)
⇔
¬∀x¬Fx ∨ ¬∀x¬Gx
|
Заменяйки навсякъде „¬∀x¬“ с „∃x“ въз основа на връзката между
кванторите, получаваме втората търсена логическа еквивалентност:
|
∃x(Fx ∨ Gx)
⇔
∃xFx ∨ ∃xGx
|
Разпределимостта на универсалния квантор в конюнкцията и на екзистенциалния в
дизюнкцията важат за всякакви формули на мястото на „Fx“ и „Gx“.
С други думи, ако α и β са произволни формули, а x е произволна променлива
(т.е. може и да е различна от „x“) следните две схеми еквивалентности са логически
валидни:
|
∃х(α ∨ β)
⇔
∃хα ∨ ∃хβ
|
|
∀х(α ∧ β)
⇔
∀хα ∧ ∀хβ
|
Първата схема ни дава право, когато обхватът на един екзистенциален квантор има формата на дизюнкция, да го разпределим между двата дизюнкта; и обратно – ако пред всеки от
дизюнктите има екзистенциален квантор, да го изкараме пред дизюнкцията. Втората ни позволява да направим същото с всеки универсален квантор, когато обхватът му е конюнкция.
Разпределимостта на екзистенциалния квантор важи само за дизюнкцията, а на
универсалния – само за конюнкцията, т.е. не е вярно нито „∃х(α ∧ β)“
⇔ „∃хα ∧ ∃хβ“, нито „∀x(α ∨ β)“ ⇔ „∀хα ∨
∀хβ“. Че това е така, може да се види с примери. Твърдението
„Има нещо, което е кръгло, и има нещо, което е квадратно“ („∃хFx ∧
∃хGx“) е истинно, докато твърдението „Има нещо, което е кръгло и квадратно“
(„∃х(Fx ∧ Gx)“) не е. По същия начин твърдението „Всяко
нещо е червено или не“ („∀х(Fx ∨¬Fx“) е истинно, докато
твърдението „Всяко нещо е червено или всяко нещо не е червено“ („∀хFx
∨ ∀х¬Fx“) не е.
Формални свойства на отношенията
Ще наричаме двуместните предикати (като „…е учител на…“, „…е по-голямо от…“ и т.н.)
двуместни отношения. Съответно, ако даден двуместен предикат е истинен за
една наредена двойка от неща, ще казваме, че първото се намира във въпросното
отношение към второто. Двуместните отношения имат определени формални
характеристики, които ги подразделят в различни групи. Ще наричаме тези
характеристики „формални свойства на отношенията“. Те са най-различни. Тук ще се спрем
на свойствата рефлексивност, ирефлексивност, симетричност,
асиметричност, транзитивност и интранзитивност.
Едно двуместно отношение е рефлексивно в някакво множество, ако за всяко нещо от множеството е изпълнено, че се намира във въпросното отношение към самото себе си. Рефлексивно
е например отношението на идентичност в което и да е множество, защото за всяко нещо важи, че е идентично със самото себе си. Формалната дефиниция е, че отношението F е
рефлексивно, когато е изпълнено
Едно отношение е ирефлексивно в дадено множество, когато никое от нещата
в множеството не се намира в това отношение към самото себе си. Такова е например
отношението „по-голямо“ в което и да е множество, тъй като нищо не е по-голямо
от себе си. Формалната дефиниция е, че отношението F е ирефлексивно, когато
е изпълнено
Едно отношение е симетрично в дадено множество, когато е изпълнено, че
ако произволен елемент а от множеството се намира в това отношение към
произволен елемент b от множеството, то задължително и b се
намира в това отношение към a. Симетрично е например отношението „роднина“
в множеството на хората, защото, ако някой е роднина на някого, то вторият
също му е роднина. Формалната дефиниция е, че отношението F симетрично,
когато е изпълнено
Едно отношение е асиметрично в дадено множество, когато e изпълнено,
че ако произволен елемент a от множеството се намира в това отношение
към произволен елемент b от множеството, то b не се намира в
това отношение към a. Асиметрично е например отношението „по-възрастен“
в множеството на хората, тъй като, ако някой е по-възрастен от някого, то
вторият не е по-възрастен, а е по-млад от първия. Асиметричността на произволно
отношение F се изразява символно така:
Едно отношение е транзитивно в дадено множество, когато е изпълнено, че
ако произволен елемент а от множеството се намира в това отношение към
произволен елемент b от множеството, а b от своя страна се намира
в това отношение към произволен елемент c от множеството, то задължително
също и a се намира в това отношение към c. Транзитивно е например
отношението „по-висок“ в което и да е множество, защото ако нещо е по-високо от
друго нещо, а другото е по-високо от трето, то задължително първото ще е
по-високо от третото. Транзитивността на произволно отношение F се
изразява символно така:
|
∀x∀y∀z[(Fxy ∧ Fyz) → Fxz]
|
Едно отношение е интранзитивно в дадено множество, когато е изпълнено,
че ако произволен елемент a от множеството се намира в това отношение
към произволен елемент b от множеството, а b от своя страна се
намира в това отношението към произволен елемент c от множеството, то
a задължително не се намира в това отношение към c. Интранзитивно
е например отношението „баща“ в множеството на хората, защото ако някой е баща
на някого, a вторият е баща на трети (трета), то първият не е баща на третия
(третата), а му (ѝ) е дядо. Интранзитивността на произволно отношение F
се изразява символно така:
|
∀x∀y∀z[(Fxy ∧ Fyz)→ ¬Fxz]
|
Всяко отношение има различни комбинации от формални свойства. Например отношението
„равно“ е рефлексивно, симетрично и транзитивно. Отношението „по-висок“ е ирефлексивно,
асиметрично и транзитивно. Отношението „брат“ е ирефлексивно и не е нито симетрично,
нито асиметрично (ако а е брат на b, то b може да му е брат, но
може и да му е сестра, т.е. да не му е брат). Освен това то не е нито транзитивно,
нито е интранзитивно (ако a и b имат само обща майка, а b и
c само общ баща, то a и c нямат общи нито баща, нито майка).
Отношението „харесва“ пък не притежава нито едно от шестте разгледани формални
свойства.
Някои формални свойства следват логически от едно или повече други. Например, ако едно отношение е ирефлексивно и транзитивно, то задължително е асиметрично.
Това може да бъде доказано с нашата доказателствена процедура. За целта приемаме, че за произволно отношение F е изпълнено „∀x¬Fxx“
(условието за ирефлексивност) и „∀x∀y∀z[(Fxy ∧ Fyz) → Fxz]“ (условието за транзитивност) и доказваме, че от това
следва „∀x∀y(Fxy → ¬Fyx)“ (условието за асиметричност):
|
1.
∀х¬Fxx
|
|
2.
∀x∀y∀z[(Fxy ∧ Fyz) → Fxz]
/ ∀x∀y(Fxy → ¬Fyx)
|
|
3.
¬∀x∀y(Fxy → ¬Fyx)
допускане
|
|
4.
∃x∃y¬(Fxy → ¬Fyx)
от 3. по връзка между кванторите
|
|
5.
∃y¬(Fay → ¬Fya)
от 4. по EI
|
|
6.
¬(Fab → ¬Fba)
от 5. по EI
|
|
7.
(Fab ∧ Fba) → Faa
от 2. по UI (три пъти)
|
|
8.
¬Faa
от 1. по UI
|
|
9.
Fab ∧ ¬¬Fba
от 6. по мат. импликация
|
|
10.
Fab ∧ Fba
от 9. по двойно отрицание
|
|
11.
Faa
от 10. и 7. по модус поненс – противоречие с 8.
|
|
12.
∀x∀y(Fxy → ¬Fyx)
от 3.-11. по свеждане до противоречие
|
Задачи
(Изтеглете задачите като pdf.)
|
(1)
Определете дали следните двойки изрази са логически еквивалентни. Ако не се, променете един
от кванторите във втория израз (ако е екзистенциален да стане универсален, и обратно), така
че да станат еквивалентни.
|
|
1)
|
¬∀y
∃y¬
|
|
2)
|
¬∃x¬
¬¬∀x
|
|
3)
|
∀x¬∀y∀z¬
¬∃x∀y¬∀z
|
|
4)
|
∀x¬¬∃y¬
¬∃x∀y
|
|
5)
|
∀x¬∀y∀z¬
∀x∃y∃z
|
|
6)
|
¬∃x∀y∀z
∀x∃y∀z¬
|
|
7)
|
∃x∃y¬∀z∀w¬
∃x∃y∃z∃w
|
|
8)
|
∃x∃y¬∀z∀w¬
¬∀x∀y∀z¬∀w
|
|
9)
|
∃x∃y¬∀z∀w¬
∃x∃y∃z¬∃w¬
|
|
10)
|
∃x∃y∀z∀w¬
¬∀x∀y∀z∃w
|
|
(2)
Правилна ли инстанциацията? Ако не е, къде е грешката?
|
|
1)
|
∀x(Fxa → Gbx)
|
|
Fba → Gbb
|
|
2)
|
∀z(Faz ∧ ¬Fzz) → Fab
|
|
(Fab ∧ ¬Fbb) → Fab
|
|
3)
|
∃x∃y∃z[(Fxa ∧ ¬Fya) → Gxyz]
|
|
∃y∃z[(Fba ∧ ¬Fya) → Gxyz]
|
|
4)
|
∀x∃y[∀zFzxy → ∃zGaz]
|
|
∃y[∀zFzay → ∃zGaz]
|
|
5)
|
∀y(Gay ∨ ¬∀xHbxy)
|
|
Gab ∨ ¬∀xHbxa
|
|
6)
|
¬∀x(Fxa ↔ Gax)
|
|
¬(Fba ↔ Gab)
|
|
7)
|
∃x∀yFxy → ∀y∃xFxy
|
|
∀yFay → ∀yFay
|
|
8)
|
∀x[Fxbx ∧ (¬∃yGxy ↔ Hxbx)]
|
|
Fbbb ∧ (¬∃yGby ↔ Haba)
|
|
(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.
|
∃x∃yFxy
|
|
|
2.
|
∀x∃yGyx
|
|
|
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)
|
∀x(¬Fx → ¬Gx)
|
|
∀xGx
|
|
∃xFx
|
|
2)
|
∀x(Fx ∧ Gx)
|
|
∀xFx ∨ ∀xGx
|
|
4)
|
∀x(Fx ∨ Gx)
|
|
∀x(Fx∨¬Gx)
|
|
∀xFx
|
|
5)
|
∃x(Fx∧Gx) ∨ ∃x(Fx∧¬Gx)
|
|
∃xFx
|
|
6)
|
∀x(Fx → ∀y∃zGxyz)
|
|
∃x∀y¬Gaxy
|
|
¬Fa
|
|
(6)
Докажете валидността на следните изводи, като използвате означенията:
|
|
1)
|
Нито един човек не е съвършен.
|
|
|
Сократ е човек.
|
|
|
Сократ не е съвършен.
|
|
|
F – …е човек, G – …е съвършен, a – Сократ
|
|
2)
|
Сократ е философ.
|
|
|
Сократ е мъдър.
|
|
|
Някой философи са мъдри.
|
|
|
F – …е философ, G – …е мъдър, a – Сократ
|
|
3)
|
Петър или Иван не е учтив.
|
|
|
Ако Иван е учтив, всеки е учтив.
|
|
|
Иван не е учтив.
|
|
|
F – …е учтив, a – Иван, b – Петър, D – хората
|
|
4)
|
Иван може да победи всеки от отбора, който е по-възрастен от него.
|
|
|
Петър не е по-възрастен от никой от отбора, който може да го победи.
|
|
|
Петър не е по-възрастен от Иван.
|
|
|
F – …може да победи…, G – …е по-възрастен от…,
a – Иван, b – Петър, D – отбора
|
|
5)
|
Всички тела се привличат.
|
|
|
а и b са тела.
|
|
|
b привлича a.
|
|
|
F – …привлича…, G – …е тяло
|
|
6)
|
Всяко нещо или съществува във времето и пространството, или е абстрактно.
|
|
|
Числата не съществуват във времето и пространството.
|
|
|
Числата са абстрактни.
|
|
|
F – …е абстрактно, G – …е число, H – …съществува
във времето и пространството
|
|
7)
|
Всеки, който е чел и Хамлет, и Отело, харесва Хамлет.
|
|
|
Някои, които са чели Хамлет, не го харесват.
|
|
|
Някои, които са чели Хамлет, не са чели Отело.
|
|
|
F – …е чел Хамлет, G – …е чел Отело,
H – …харесва Хамлет, D – хората
|
|
8)
|
Нито едно гръбначно животно, което има бъбреци, не е земноводно.
|
|
|
Ако едно земноводно има бъбреци, то е гръбначно.
|
|
|
Никое земноводно няма бъбреци.
|
|
|
F – …е гръбначно, G – …има бъбреци, H –
…е земноводно, D - животните
|
|
9)
|
На прожекцията се допускат само пълнолетни, които са си купили билет.
|
|
|
Някои, които са си купили билет, са непълнолетни.
|
|
|
Някои, които не се допускат на прожекцията, са си купили билет.
|
|
|
F – …се допуска на прожекцията, G – …е пълнолетен,
H – …си е купил билет, D – хората
|
|
10)
|
Всички окръжности са фигури.
|
|
|
Всеки, който чертае окръжност, чертае фигура.
|
|
|
F – …е окръжност, G – …е фигура, H – …чертае…
|
|
11)
|
Има постъпки, които всички хора осъждат.
|
|
|
Всеки човек осъжда една или друга постъпка.
|
|
|
F –…е постъпка, G – …е човек, H – …осъжда…
|
|
12)
|
Всеки от форума харесва Амаркорд.
|
|
|
Или никой от форума не е гледал Амаркорд, или ако някой го е гледал, го харесва.
|
|
|
F – …е от форума, G – …харесва Амаркорд, H
– …е гледал Амаркорд, D – хората
|
|
13)
|
Има постъпки, които са осъждани от всеки, който осъжда някакви постъпки.
|
|
|
Всеки осъжда една или друга постъпка.
|
|
|
Има постъпки, които всички осъждат.
|
|
|
F – …е постъпка, G – …е човек, H – …осъжда…
|
|
14)
|
Харесвам всеки, който се смее на самия себе си.
|
|
|
Мразя всеки, който се смее на всичките си приятели.
|
|
|
Ако мразя някого, аз не го харесвам.
|
|
|
Ако съществува някой, който се смее на всичките си приятели, то съществува някой,
който не е приятел на самия себе си.
|
|
|
F – харесвам…, G – …се смее на…, H – мразя…,
I – …е приятел на…, D – хората
|
|
(7)
Докажете, че следните формули са логически валидни:
|
|
1)
|
∀x(∀yFy → Fx)
|
|
2)
|
∃x(∀yFy → Fx)
|
|
3)
|
∀x(Fx → ∃yFy)
|
|
4)
|
∀x∃y(∀zFyzx → Fyyx)
|
|
(8)
Въз основа на разпределимостта на кванторите в конюнкцията или дизюнкцията,
определете дали следните двойки формули са логически еквивалентни:
|
|
1)
|
∀x(¬Fxa ∨ Gxb)
∀x¬Fxa ∨ ∀xGxb
|
|
2)
|
∀x(Fxa ∧ ¬Gax)
∀xFxa ∧ ¬∃xGax
|
|
3)
|
∃x(¬Fxb ∨ ¬Gxa)
¬∀xFbx ∧ ¬∀xGxz
|
|
4)
|
∃y(¬Gyb ∧ ¬Hay)
¬∀yGyb ∧ ∃y¬Hay
|
|
(9)
Какви са формалните свойства на следните отношения?
|
|
1)
|
„по-малко или равно“ в множеството на естествените числа
|
|
2)
|
„сестра“ в множеството на хората
|
|
3)
|
„съсед“ в множеството на хората
|
|
4)
|
„връстник“ („на същата възраст като“) в множеството на хората
|
|
5)
|
„учител“ в множеството на хората
|
|
6)
|
„майка“ в множеството на хората
|
|
7)
|
„по-голямо с 2“ в множеството на естествените числа
|
|
8)
|
„харесва“ в множеството на хората
|
|
9)
|
„подчинен“ в една армия
|
|
10)
|
„по-богат“ в множеството на хората
|
|
1)
|
Ако едно отношение е асиметрично, то е също ирефлексивно.
|
|
2)
|
Ако едно отношение е интранзитивно, то е също ирефлексивно.
|
