3.4 Синтаксис и семантика на предикатната логика

Синтаксис на предикатната логика

В „1.3 Таблици за истинност. Синтаксис и семантика“ говорихме за синтаксиса и семантиката на езика на пропозиционалната логика. Пропозиционалната логика е част от предикатната, затова синтаксисът и семантиката ѝ са част от тези на предикатната логика. Главната функция на синтаксиса на един формален език, какъвто е езикът на всяка логическа система, е да разграничи граматически правилните от неправилните поредици от символи на езика, а главната задача на семантиката му е да определи кога едно (граматически правилно) изречение на езика е истинно, и кога не. Синтаксисът и семантиката дават възможност строго да се дефинират понятията за логическо следване, логическа еквивалентност, противоречивост и непротиворечивост, логическа валидност и др.

Синтаксисът се формулира посредством синтактични правила, които определят всички възможни начини за конструиране на граматически правилни изрази от езика, като по този начин дават рекурсивна дефиниция на понятието за правилно-образуван израз. Всяка рекурсивна дефиниция1 функционира, като посочва най-простите елементи от множеството от нещата, които попадат под дефинираното понятие, след което посочва правила, чрез които от по-простите елементи на множеството се получават по-сложните, така че никой да не бъде изпуснат. Важно свойство на долната рекурсивна дефиниция е, че може да бъде използвана като алгоритъм за определяне на това, дали произволна поредица от символи от „азбуката“ на езика е правилно-образуван израз, или не.

Дефиниция на правилно-образуваните изрази (формулите2) на предикатната логика:

Синтактичното правило i. се отнася до атомарните формули на предикатната логика – непосредствени свързвания между общи и единични термини (т.е. между букви за предикати и индивидни константи или променливи). С тях се представят символно преди всичко прости твърдения или прости отворени изречения от естествените езици, като твърдението „Сократ е учител на Платон“ („Gab“) или отвореното изречение „Сократ е учител на x“ („Gax“).

Правило ii. обхваща синтактичните правила на пропозиционалната логика. Когато излагахме нейния синтаксис (в „1.3 Таблици за истинност. Синтаксис и семантика“ ), за всеки от логическите съюзи имаше отделно правило – по едно за отрицанието, конюнкцията и т.н. За по-кратко тук всичките са обединени в едно. Въз основа на това синтактично правило например от формулата „Gax“ (която в примера по-горе отговаряше на отвореното изречение „Сократ е учител на x“) бихме могли да образуваме формулата „¬Gax“(„Сократ не е учител на x“). Според правилото винаги когато образуваме формула чрез някой от двуместните логически съюзи (на конюнкцията, дизюнкцията, импликацията или еквивалентността), трябва да я заграждаме в скоби (включително и когато не е част от друга формула – тогава не пишем външните скоби за удобство, но официално ги има). В 1.3 обяснихме защо е така. За по-лесно четене и неформално обикновените скобите понякога се заменят с правоъгълни или къдрави скоби (формално последните не са част от синтаксиса ни).

Посредством синтактичното правило iii. от отворени изречения се образуват твърдения с помощта на квантори. Така например, ако си мислим за формулата „¬Gax“ (която получихме посредством първите две правила), като отговаряща на отвореното изречение „Сократ не е учител на x“, въз основа на iii. от нея бихме могли да получим „∃x¬Gax“, която вече отговаря не на отворено изречение, а на твърдение – „Сократ не е учител на някого“ или „Съществува някой, на когото Сократ не е учител“.

На базата на синтактичните правила (формално и строго) се дефинират понятията обхват на квантор, свободна и свързана променлива, свободно и свързано участие на променлива, отворено изречение и твърдение, които в 3.2 въведохме неформално.

Ако „∀xα“ (съответно „∃xα“) е формула (правилно образуван израз) и „x“ е произволна променлива, то α се нарича обхват на „∀x“ (съответно на „∃x“).

Една и съща променлива може да се среща повече от един път в една формула, затова говорим за различни нейни „участия“. (Променливите на кванторите не се броят като участия.) Едно участие на променлива е свободно в дадена формула, ако не е част от обхвата на квантор със същата променлива. В противен случай (ако е част от обхвата на квантор със същата променлива) е свързано. Един квантор свързва дадено участие на променлива, ако има същата променлива, участието на променливата е в обхвата му и е свободно в него. Добавянето на последното условие се налага, защото едно участие на променлива може да е в обхвата на квантор със същата променлива, но да не е свързано от него, ако вече е свързано от друг квантор в обхвата на първия. Например във формулата „∀x(∃xFxGxa)“ въпреки че участието на „x“ веднага след „F“ се намира в обхвата на универсалния квантор и променливата на последния е „x“, то не е свързано от него, защото вече е свързано от екзистенциалния квантор, който е в обхвата на универсалния.

Важно е да имаме предвид, че говорим за свободни или свързани участия на променлива винаги по отношение на даден израз. Едно участие на променлива може да е свързано в една формула и свободно в подформула на тази формула. Например участието на променливата „x“ в „∃xyFxy“ е свързано, но участието ѝ в подформулата „∀yFxy“ на същата формула е свободно.

Една променлива е свободна в дадена формула, когато има поне едно свободно участие в нея. Например „x“ е свободна във формулата „∃xFxGxa“ заради второто ѝ участие, което е свободно, въпреки че първото ѝ участие е свързано. Съответно една променлива е свързана в дадена формула, когато всичките ѝ участия във формулата са свързани.

Ако в една формула има свободни променливи, тя е отворено изречение. В противен случай е твърдение.

Правило iii. допуска съществуването на квантори, които не свързват променливи. Например, прилагайки към „Fx“ iii., получаваме формулата „∃xFx“, в която няма свободни променливи. Тъй като „∃xFx“ е правилно-образуван израз, въз основа на iii. „∀xxFx“ също е правилно-образуван израз. За универсалния квантор в тази формула обаче няма свободна променлива, към която да се отнесе. Въпреки че изглеждат странно, такива формули се разглеждат като правилно-образувани изрази, за да не се усложняват синтактичните правила. Те са безобидни, тъй като според семантиката на предикатната логика са логически еквивалентни на формулите, които се получават като махнем въпросните квантори (например формулата „∀xxFx“ е логически еквивалентна на „∃xFx“). Така че можем просто да се абстрахираме от такива квантори.

Синтактичното правило iv. е по-особено, защото в него се споменават другите синтактични правила, т.е. то е „мета-правило“, според което, ако един израз може да бъде получен чрез (многократно) прилагане на правила i.-iii., той е формула на предикатната логика, и че ако не може да бъде получен по такъв начин, не е формула на предикатната логика. Например „∀x((FxGx)∨Ga)“ е формула на предикатната логика, защото въз основа на i. имаме, че „Fx“, „Gx“ и „Ga“ са формули. От там, като приложим два пъти ii., получаваме, че и „((FxGx)∨Ga)“ е формула, от което пък въз основа на iii. следва, че и „∀x((FxGx)∨Ga)“ е формула. Напротив изразът „∀x(FxGxGa)“ не е формула на предикатната логика, защото е получен въз основа на iii. от „(FxGxGa)“. Последният израз обаче няма как да бъде получен чрез правило ii., което се отнася до логическите съюзи. Съдържателно този израз е двусмислен, тъй като не е ясно дали е импликация между „Fx“ и дизюнкцията „GxGa“, или е дизюнкция между импликацията „FxGx“ и „Ga“. Чрез прилагането на ii. от „Fx“, „Gx“ и „Ga“ можем да получим или „(Fx→(GxGa))“, или „((FxGx)∨Ga)“, не и „(FxGxGa)“.

Семантика на предикатната логика

Формулите на предикатната логика се интерпретират по отношение на област от обекти, наричана „универсум на дискурса“, която означаваме с „D“.

За да интерпретираме дадена формула като някакво конкретно твърдение (или отворено изречение), освен от определянето на универсума на дискурса се нуждаем и от интерпретиране на буквите за предикати и индивидните константи във формулата. Интерпретирането на една индивидна константа се състои в определянето на това, кой e обектът от D, който тя обозначава. Например, ако D е множеството на хората (съществувалите и съществуващите), можем да интерпретираме индивидната константа „а“, така че да има значението на собственото име „Сократ“, като определим, че обозначава (реферира) човека Сократ.

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

Що се отнася до интерпретацията на буквите за предикати, когато интерпретираме такава буква като едноместен предикат, интерпретацията ѝ се състои в определянето на това, за кои неща от универсума на дискурса D е истинна, и за кои не3; когато я интерпретираме като двуместен предикат – в определянето на това, за кои двойки от неща от D е истинна, и за кои не; когато я интерпретираме като триместен предикат – за кои тройки и т.н. Например ако D е множеството на хората и искаме да интерпретираме буквата за предикат „F“ като предиката „[1] е философ“, определяме, че „F“ е истинна за философите и неистинна за хората, които не са философи. Ако искаме да я интерпретираме като двуместния предикат „[1] е учител на [2]“, определяме, че е истинна за тези и само за тези наредени двойки от хора, за които е изпълнено, че първият е учител на втория. Тогава „F“ ще е истинна например за двойката (Сократ, Платон), защото Сократ е учител на Платон, и неистинна например за двойката (Платон, Сократ) или за двойката (Аристотел, Сократ), защото нито Платон, нито Аристотел са учители на Сократ. Ако искаме да интерпретираме „F“ като триместния предикат „[1] е дъщеря на [2] и [3]“, определяме, че „F“ е истинна за тези и само за тези наредени тройки от хора (m, n, l), за които важи, че m е дъщеря на n и l; … и т.н. за четириместните и изобщо за n-местните предикати.

Така че под интерпретация в даден универсум на дискурса D на една или повече формули ще разбираме: 1) за всяка от участващите в тях индивидни константи да се определи какво обозначават в D и 2) за всеки от участващите в тях букви за предикати да се определи множеството от нещата в D (или множеството от наредени двойки от неща в D, или множеството от наредени тройки от неща в D и т.н.), за които са истинни.

Определянето на универсум на дискурса D и интерпретация I за една или повече формули, в които няма свободни променливи (т.е. които са твърдения), автоматично определя тяхната истинностна стойност в този универсум на дискурса за тази интерпретация. Съвкупността (наредената двойка) от универсум на дискурса и интерпретация (D, I) се нарича „структура“. Формулите на предикатната логика са истинни или неистинни винаги по отношение на някаква структура. Структурите в семантиката на предикатната логика са еквивалента на редовете на таблиците за истинност в семантиката на пропозиционалната логика. За разлика от редовете в една таблица за истинност обаче моделите са безкрайно много. Когато всяка формула от едно множество от формули (което може и да е безкрайно) е истинна в една структура, за структурата се казва, че е модел на тези формули. В частност, ако една формула е истинна в дадена структура, за структурата се казва, че е неин модел.

Ако в дадена формула или множество от формули има свободни променливи (т.е. ако формулите не са твърдения, а отворени изречения), те получават истинностна стойност в дадена структура (D, I) само ако свободните променливи в тях получат определени стойности – някакви неща от D. Ще наричаме „даване на стойности“ всяко едно определяне на стойности за свободните променливи. Когато към една структура добавим определено даване на стойности на свободните променливи, не само твърденията, но и отворените изречения получават определена истинностна стойност в нея. Нека обърнем внимание, че когато определяме някакъв универсум на дискурса, някаква интерпретация и (евентуално) някакво даване на стойности на свободните променливи, с това формулите не биват отнесени към изречения от естествения език (в качеството им на техни преводи), а към определена действителност (тази на универсума на дискурса). Посредством такова отнасяне към действителността, а не посредством отнасянето им към друг език, те стават истинни или неистинни.

След като вече разполагаме с понятията за структура, универсум на дискурса, интерпретация и даване на стойности на свободните променливи, можем да формулираме семантичните правила на предикатната логика. Те са следните:

За всяка структура (D, I) важи следното:

Всяко от семантичните правила съответства на едно от синтактичните. Целта е съставните изрази да получават своите условия за истинност посредством условията за истинност на участващите в тях по-прости изрази.

Правило I. се отнася до атомарните формули4. Ако в тях участват променливи, те са свободни, защото в атомарните формули не участват квантори. Тогава формулите са отворени изречения и са истинни или неистинни само за определени стойности на променливите. Например, ако D е множеството на хората и интерпретацията I отнася „F“ към множеството от наредени двойки, в които първият елемент е учител на втория, a „a“ – към Сократ (човека Сократ, не името „Сократ“), то атомарната формула „Fax“ би била истинна, ако „x“ приеме като стойност Платон и неистинна, ако приеме като стойност Аристотел (отново хората, не имената). Атомарните формули, в които участват само индивидни константи, са твърдения и правилото гарантира, че ще бъдат или истинни, или неистинни в съответната структура. Ако например същата интерпретация I отнася „b“ към Платон, „Fab“ би била истинна в тази структура. По този начин въз основа на семантичното правило I. всяка атомарна формула получава или стойност И, или стойност Н (никога и двете) в която и да е структура при което и да е даване на стойности на свободните променливи (ако има такива).

Правило II. определя по стандартния начин условията за истинност на логическите съюзи. Правилото включва всички семантични правила на пропозиционалната логика (общо пет – по едно за всеки логически съюз). Тези правила биха могли да бъдат намалени до две – до това за отрицанието заедно с някое от правилата за конюнкцията, дизюнкцията или импликацията, защото останалите логически съюзи могат да бъдат дефинирани чрез двата избрани. Тогава дефинираните логически съюзи щяха да получат същите условия за истинност като следствие от условията за истинност на съюзите, чрез които са дефинирани. Да дефинираме посредством два от логическите съюзи останалите би означавало обаче да променим синтаксиса, защото тогава изразите, в които участват дефинирани съюзи, строго погледнато не биха били формули, а съкращения за формули (посредством дефинициите), в които участват само двата избрани логически съюза. Ето например как дизюнкцията, импликацията и еквивалентността биха могли да се дефинират посредством отрицанието и конюнкцията:

„α∨β“ =def. „¬(¬α∧¬β)“
„α→β“ =def. „¬(α∧¬β)“
„α↔β“ =def. „(α→β)∧(β→α)“5

С таблици за истинност или истинностно-функционален анализ може да се провери, че изразите от двете страни на знакът за дефиниция „=def.“ са логически еквивалентни, поради което имат един и същи смисъл. Възможността за използване на дефиниции и съответно намаляване на семантичните правила обаче беше само отклонение – избрали сме да не дефинираме логически съюзи чрез други и даваме семантично правило за всеки от тях.

Въз основа на семантичното правило II. всички съставни формули от вида „¬α“, „α∧β“, „α∨β“, „α→β“ и „α↔β“ (т.е. всички изрази с формата на отрицание, конюнкция, дизюнкция, импликация и еквивалентност) получават или стойност И, или стойност Н във всяка структура (D, I) (при някакво даване на стойности на свободните променливи в тях, ако има такива), в случай, че α и β вече са получили някакви истинностни стойности в тази структура. В структурата, която използвахме като пример по-горе, формулата „Fab“ беше интерпретирана като еквивалентна на твърдението „Сократ е учител на Платон“ и съответно има стойност И в нея. Ако освен това интерпретацията I на структурата отнася буквата за предикат „G“ към красивите неща в D (т.е. към красивите хора), то атомарната формула „Ga“ би имала смисъла на твърдението „Сократ е красив“ и би получила стойност Н в структурата. Тогава въз основа на правило II. формулата „Fab∧¬Ga“ ще получи стойност И в структурата. Условията за истинност, които правило II. придава на отрицанието и конюнкцията правят тази формула равнозначна на твърдението „Сократ е учител на Платон и не е красив“.

Правило III. се занимава с условията за истинност на универсалните и екзистенциалните твърдения или отворени изречения, т.е. на тези формули, в които главният логически оператор е квантор. Да разгледаме като пример структура, чиито универсум на дискурса e множеството на естествените числа (0, 1, 2, ...) и чиято интерпретация отнася буквата за предикат „F“ към безкрайното множество на всички наредени двойки от естествени числа, за които важи, че първото е по-голямо от второто (с други думи „F“ е еквивалентна на предиката „[1] е по-голямо от [2]“). Освен това нека константата „a“ е интерпретирана като обозначаваща числото 7. Тогава формулата „Fxa“ ще има значението на отвореното изречение „x е по-голямо от 7“. Има поне една стойност на „x“, за която това отворено изречение е истинно, тъй като има поне едно число (всъщност са безкрайно много), което е по-голямо от 7. Тъй като следователно „Fxa“ е истинна за поне една стойност на „x“, въз основа на III. формулата „∃xFxa“ ще е истинна в тази структура. Условията за истинност, които III. дава на израз с формата „∃xα“, правят „∃xFxa“ равнозначна на твърдението „Има по-голямо число от 7“. Като втори пример нека разгледаме формулата „∀xFxy“ в същата структура. Тя има свободна променлива, поради което не е твърдение, а отворено изречение и получава истинностни стойности в структурата само по отношение на някакви давания на стойност на свободната променлива „y“. Да дадем като стойност на „y“ числото 0. Въз основа на III. „∀xFxy“ ще има стойност И за това даване на стойност на „y“, ако и само ако за всяко даване на стойност на „x“ формулата „Fxy“ получава стойност И (при същото даване на стойност на „y“). Въз основа на правило I. това означава, че „∀xFxy“ ще е истинна, ако и само ако всяко естествено число е по-голямо от 0. Последно обаче не е вярно, защото сред естествените числа има число, което не е по-голямо от 0, и това е самото число 0. Следователно при тази интерпретация и при това даване на стойност на свободната променлива „y“ формулата „∀xFxy“ е неистинна в разглежданата структура.

Може да бъде строго доказано, че всички формули в едно множество от формули на предикатната логика (в частност всяка формула сама за себе си), независимо от тяхната сложност и независимо от техния брой (включително и ако са безкрайно много), задължително получават стойност И или Н във всяка структура и за всяко даване на стойности на свободните им променливи, ако има такива. Това е така, тъй като на всяко синтактично правило отговаря семантично, а всеки правилно-образуван израз (формула) е получен чрез последователно прилагане на синтактични правила. Така чрез последователно прилагане на съответстващите им семантични правила всяка формула получава истинностна стойност. Най-простите подформули на една формула са атомарните и те получават истинностна стойност въз основа на правило I. Всяка следваща, по-сложна част на формулата е образувана от по-простите посредством логически съюзи или квантори и по правила II. и III. тя също получава някаква истинностна стойност, докато накрая цялата формула не получи някаква истинностна стойност.

На базата на понятията за истинност и неистинност в структура се дефинират понятията за логическо следване, логическа еквивалентност, логическа валидност, противоречивост и непротиворечивост. Тези ключови за логиката понятия са свързани с формата на изреченията, не със съдържанието им (т.е. с това, за което се говори в тях), поради което не са зависими от конкретен универсума на дискурса и интерпретация (т.е. от конкретна структура). Дефинирането им става чрез отнасяне към всички възможни структури. Дефинициите са следните.

Логическо следване (между твърдения): Ако Δ е множество от твърдения (т.е. множество от формули без свободни променливи), твърдението α (също такава формула) следва логически от тях, ако и само ако във всяка структура, в която формулите от Δ са истинни, е истинна и α (т.е. когато всеки модел на Δ е модел и на α).

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

Логическа еквивалентност (между твърдения): Две твърдения са логически еквивалентни, ако и само ако следват логически една от друга.

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

Логическа еквивалентност (между твърдения – втора дефиниция): Две твърдения са логически еквивалентни, ако и само ако са истинни в едни и същи структури (т.е. ако моделите им са едни и същи).

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

Логическа валидност (на твърдения): Едно твърдение е логически валидно, ако и само ако е истинно във всяка структура (т.е. ако всяка структура му е модел).

Съответно, едно твърдение (или отворено изречение) от естествения език е логически валидно, ако може да се представи символно с логически валидна формула.

Понятието за логическа валидност е аналогът в предикатната логика на понятието за тавтология в пропозиционалната логика. В семантиката на предикатната логика структурите (комбинациите между универсум на дискурса и интерпретация) са аналозите на редовете на таблиците за истинност в семантиката на пропозиционалната логика, но докато редовете във всяка таблицата за истинност са краен брой, структурите за която и да е формула на предикатната логика са безкрайно много. Понятието за логическа валидност е по-широко от това за тавтология, защото всички формули на предикатната логика, които имат формата на тавтологии (например „Fa∨¬Fa“, която има формата „α∨¬α“, или „∃xGxb→∃xGxb“, която има формата „α→α“, и т.н.), са логически валидни (няма как да са неистинни в която и да е структура), но има формули на предикатната логика, които са логически валидни, без да имат формата на тавтологии. Такава е например „∀xFxFa“, която казва, че ако всяко нещо е F, то и a е F. Ясно е, че формулата е истинна във всяка структура (ако всяко нещо от универсума на дискурса на структурата попадат под „F“, то a, което е нещо от универсума на дискурса, също ще попада под „F“) и значи е логически валидна. Тази формула обаче няма формата на тавтология – в пропозиционалната логика би била представена с „pq“.

В пропозиционалната логика разполагахме с разрешителна процедура, чрез която да проверяваме дали дадена схема за извод е логически валидна както и дали две формули са логически еквивалентни.6 Тя почиваше на следните два принципа, в които се използва понятието за тавтология:

От формулите α1, α2,… , αn следва логически формулата β, ако и само ако формулата „(α1 ∧ α2 ∧ … ∧ αn) → β“ е тавтология.
Формулите α и β са логически еквивалентни, ако и само ако формулата „α ↔ β“ е тавтология.

Тези два принципа могат да бъдат разглеждани като дефиниции на понятията за логическо следване и логическа еквивалентност посредством понятието за тавтология. В предикатната логика на понятието за тавтология отговаря по-широкото понятие за логическа валидност. Съответно логическото следване и логическата еквивалентност биха могли да се дефинират по същия начин чрез него. По-горе ги дефинирахме директно чрез понятието за истинност в структура. Алтернативните дефиниции чрез понятието за логическа валидност се получават от горните два принципа, като заменим „тавтология“ с „логически валидна“.

Възползвайки се от току що споменатия подход, при който логическото следване и логическата еквивалентност се дефинират посредством понятието за логическа валидност, чрез използването на понятието за универсално затваряне можем да разширим дефинициите за логическото следване и еквивалентност, така че да се отнасят и до отворени изречения (формули със свободни променливи). Универсалното затваряне на една формула се получава, когато всички нейни свободни променливи бъдат свързани с универсални квантори, добавени в началото ѝ. Например универсалното затваряне на „Fx“ е „∀xFx“, на „∃xFxy“ е „∀yxFxy“, на „∀yFxy→¬Gz“ е „∀xz(∀yFxy→¬Gz)“ и т.н. Ако във формулата няма свободни променливи, универсалното ѝ затваряне съвпада с самата нея.

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

Логическо следване (между всякакви формули): От формулите α1, α2,… , αn логически следва формулата β, ако и само ако универсалното затваряне на формулата „(α1 ∧ α2 ∧ … ∧ αn) → β“ е тавтология.

Логическо еквивалентност (между всякакви формули): Формулите α и β са логически еквивалентни, ако и само ако универсалното затваряне на формулата „α ↔ β“ е тавтология.

Противоречивост и непротиворечивост: Едно твърдение е непротиворечиво, ако и само ако е истинно в поне една структура. В противен случай (ако е неистинно във всяка структура) е противоречиво. T.e. непротиворечивостта означава наличие на модел, а противоречивостта – липса на модел. За да включим и отворените изречения към тази дефиниция, трябва да говорим за давания на стойности. Непротиворечиви са формулите, които са истинни в поне една структура, при поне едно даване на стойности на свободните им променливи, а противоречиви – тези които са неистинни във всеки модел при всяко даване на стойности на свободните им променливи.

Едно твърдение (отворено изречение) от естествения език е противоречиво, ако може да се представи символно с противоречива формула, и е непротиворечиво, ако може да се представи символно с непротиворечива формула.

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

Семантиката на предикатната логика възниква благодарение на Тарски (Tarski, 1956) като изследване на възможността за дефиниция на понятието за истина по отношение на теориите, формулирани със символния език на предикатната логика.



1. За рекурсивните дефиниции виж още „1.3 Таблици за истинност. Синтаксис и семантика“. 2. Както беше и при пропозиционалната логика, ще разглеждаме думата „формула“ като синоним на „правилно-образуван израз“. 3. В „3.1 Общи и единични термини“ видяхме, че същественото за предикатите (общите термини) е, че са истинни или неистинни за неща (когато са едноместни), за наредени двойки от неща (когато са двуместни), за наредени тройки от неща (когато са триместни),… и т.н. 4. За атомарните формули виж „3.1 Общи и единични термини“. 5. В дефиницията се използва, че импликацията вече е дефинирана в термините на конюнкция и отрицание от горната дефиниция. 6. Виж „1.6 Логическо следване и логическа еквивалентност“. 7. В „3.5 Доказателствена процедура“ ще формулираме една такава процедура.