В 1.3 Таблици за истинност говорихме за синтаксиса и семантиката на езика на пропозиционалната логика. Главната функция на синтаксиса на един формален език, какъвто е езикът на всяка логическа система, е да разграничи граматически правилните от неправилните поредици от символи на езика, а главната задача на семантиката му е да определи кога едно (граматически правилно) изречение на езика е истинно, и кога не. Синтаксисът и семантиката дават възможност строго да се дефинират понятията за логическо следване, логическа еквивалентност, противоречивост и непротиворечивост, логическа валидност и др.
Синтаксисът се формулира посредством синтактични правила, които определят всички възможни начини за конструиране на граматически правилни изрази от езика, като по този начин дават рекурсивна дефиниция1 на понятието за правилно-образуван израз (накратко формула) на предикатната логика. Рекурсивната дефиниция функционира, като посочва най-простите елементи от множеството от нещата, които попадат под дефинираното понятие, след което посочва правилата, чрез които от по-простите елементи на множеството се получават по-сложните, така че никой да не бъде изпуснат. Важно свойство на долната рекурсивна дефиниция е, че може да бъде използвана като алгоритъм за определяне на това, дали произволна поредица от „думи“ (символи в нашия случай) е правилно-образуван израз, или не.
Дефиниция на правилно-образуваните изрази (формулите) на предикатната логика :
Синтактичното правило i. се отнася до атомарните формули на предикатната логика – непосредствените свързвания между общи и единични термини (т.е. между букви за предикати и индивидни константи или променливи). Те отговарят на атомарните твърдения или отворени изречения в естествените езици, като твърдението „Сократ е учител на Платон“ („Gab“) или отвореното изречение „Сократ е учител на x“ („Gax“).
В правило ii. се съдържат всички синтактични правила на езика на пропозиционалната логика. Когато (в 1.3 Таблици за истинност) излагахме нейния синтаксис, имаше по едно правило за всеки от логическите съюзи – правило за отрицанието, за конюнкцията и т.н. За по-кратко тук всички те са обединени в едно единствено правило. Въз основа на ii. от формулата „Gax“ (която в примера по-горе отговаряше на отвореното изречение „Сократ е учител на x“) бихме могли да образуваме формулата „¬Gax“(„Сократ не е учител на x“). Според правилото, когато образуваме конюнкции, дизюнкции, импликации или еквивалентности, трябва да ги заграждаме в скоби (включително и когато са цели формули, а не части от формули). В 1.3 Таблици за истинност обяснихме защо е така. За удобство не пишем скобите, заграждащи целия израз, но официално ги има. Освен това използваме правоъгълни или къдрави скоби само неформално, за по-лесно четене; формално те не са част от езика.
Посредством синтактичното правило iii. от отворени изречения можем да образуваме твърдения с помощта на квантори. Например от формулата „¬Gax“ (която получихме посредством първите две правила и за която неформално си представяме, че отговаря на отвореното изречение „Сократ не е учител на x“), въз основа на iii. бихме могли да получим формулата „∃x¬Gax“, която отговаря не на отворено изречение, а на твърдение: в примера „Сократ не е учител на някого“ или „Съществува някой, на когото Сократ не е учител“.
В 3.2 Квантори и променливи въведохме само неформално понятията обхват на квантор, свободна и свързана променлива, свободно и свързано участие на променлива, отворено изречение и твърдение. На базата на синтактичните правила тези понятия се дефинират формално и строго. Ето как.
Ако „∀xα“ (съответно „∃xα“) е формула (правилно образуван израз) и „x“ е произволна променлива, то α се нарича обхват на „∀x“ (съответно на „∃x“).
Една и съща променлива може да се среща повече от един път в една формула, затова говорим за различни нейни „участия“. (Променливите на кванторите, например „x“ в „∀x“, не се броят като участия.) Едно участие на променлива е свободно в дадена формула, ако не е част от обхвата на квантор със същата променлива в тази формула. В противен случай (ако е част от обхвата на квантор със същата променлива) е свързано. Един квантор свързва дадено участие на променлива, ако има същата променлива, участието на променливата е в обхвата му и е свободно в него. Добавянето на последното условие се налага, защото едно участие на променлива може да е в обхвата на квантор със същата променлива, но да не е свързано от него, ако вече е свързано от друг квантор в обхвата на първия. Например във формулата „∀x(∃xFx→Gxa)“ въпреки че участието на „x“ веднага след „F“ се намира в обхвата на универсалния квантор и променливата на последния е „x“, то не е свързано от него, защото вече е свързано от екзистенциалния квантор, който е в обхвата на универсалния.
Важно е да имаме предвид, че говорим за свободни или свързани участия на променлива винаги по отношение на дадена формула. Едно участие на променлива може да е свързано в една формула и свободно във формула, която е подформула на първата. Например участието на променливата „x“ в „∃x∀yFxy“ е свързано, но участието ѝ в подформулата „∀yFxy“ на същата формула е свободно.
Една променлива (не участие на променлива) е свободна в дадена формула, когато има поне едно свободно участие в нея. Например „x“ е свободна във формулата „∃xFx→Gxa“ заради второто ѝ участие, което е свободно, въпреки че първото ѝ участие е свързано. Съответно една променлива е свързана в дадена формула, когато всичките ѝ участия във формулата са свързани.
Ако в една формула има свободни променливи, тя е отворено изречение. В противен случай е твърдение.
Правило iii. допуска съществуването на квантори, които не свързват променливи. Например, прилагайки към „Fx“ iii., получаваме формулата „∃xFx“, в която няма свободни променливи. Тъй като „∃xFx“ е правилно-образуван израз, въз основа на iii. „∀x∃xFx“ също е правилно-образуван израз. За универсалния квантор в тази формула обаче няма свободна променлива, към която да се отнесе. Въпреки че изглеждат странно, такива формули се разглеждат като правилно-образувани изрази, за да не се усложняват синтактичните правила. Те са безобидни, тъй като според семантиката на предикатната логика са логически еквивалентни на формулите, които се получават като махнем въпросните квантори (например формулата „∀x∃xFx“ е логически еквивалентна на „∃xFx“). Така че можем просто да се абстрахираме от такива квантори.
Синтактичното правило iv. е по-особено, защото в него се споменават другите синтактични правила. То е „мета-правило“, съгласно което, ако един израз може да бъде получен чрез (многократно) прилагане на правила i.-iii., той е формула на предикатната логика, и че ако не може да бъде получен по такъв начин, не е формула на предикатната логика. Например „∀x((Fx→Gx)∨Ga)“ е формула на предикатната логика, защото въз основа на i. имаме, че „Fx“, „Gx“ и „Ga“ са формули. От там, като приложим два пъти ii., получаваме, че и „((Fx→Gx)∨Ga)“ е формула, от което пък въз основа на iii. следва, че и „∀x((Fx→Gx)∨Ga)“ е формула. Напротив изразът „∀x(Fx→Gx∨Ga)“ не е формула на предикатната логика, защото е получен въз основа на iii. от „(Fx→Gx∨Ga)“. Последният израз обаче няма как да бъде получен чрез правило ii., което се отнася до логическите съюзи. Съдържателно този израз е двусмислен, тъй като не е ясно дали е импликация между „Fx“ и дизюнкцията „Gx∨Ga“, или е дизюнкция между импликацията „Fx→Gx“ и „Ga“. Чрез прилагането на ii. от „Fx“, „Gx“ и „Ga“ можем да получим „(Fx→(Gx∨Ga))“ или „((Fx→Gx)∨Ga)“, не и „(Fx→Gx∨Ga)“.
Формулите на предикатната логика се интерпретират по отношение на област от обекти, наричана „универсум на дискурса“, която означаваме с „D“.
За да интерпретираме дадена формула като някакво конкретно твърдение (или отворено изречение), освен от определянето на универсума на дискурса се нуждаем и от интерпретиране на буквите за предикати и индивидните константи във формулата. Интерпретирането на една индивидна константа се състои в определянето на това, кой e обектът от D, който тя обозначава. Например, ако D е множеството на хората (съществувалите и съществуващите), можем да интерпретираме индивидната константа „а“, така че да има значението на собственото име „Сократ“, като определим, че обозначава (реферира) човека Сократ.
Едно и също нещо може да бъде обозначавано от различни индивидни константи. Константите са еквивалентът на собствените имена (по-общо – на единичните термини) в естествените езици, в които не е изключение нещо да има различни имена. Например собствените имена „Еверест“ и „Джомолунгма“ обозначават най-високия връх на Земята. Аналогично, в езика на предикатната логика този връх би могъл да бъде обозначаван едновременно от различни индивидни константи – „a“, „b“, „c“,… и т.н.
Що се отнася до интерпретацията на буквите за предикати, когато интерпретираме такава буква като едноместен предикат, интерпретацията ѝ се състои в определянето на това, за кои неща от универсума на дискурса D е истинна, и за кои не2. Когато я интерпретираме като двуместен предикат, интерпретацията се състои в определянето на това, за кои наредени двойки от неща от D е истинна, и за кои не; когато я интерпретираме като триместен предикат – за кои наредени тройки от неща и т.н. Например, ако D е множеството на хората и искаме да интерпретираме буквата за предикат „F“ като предиката „…е философ“, ще определим, че „F“ е истинна за философите и неистинна за хората, които не са философи. Ако искаме да я интерпретираме като двуместния предикат „…е учител на…“, ще определим, че е истинна за тези и само за тези наредени двойки от хора, за които е изпълнено, че първият е учител на втория. Тогава „F“ ще е истинна например за двойката (Сократ, Платон), защото Сократ е учител на Платон, и неистинна например за двойката (Платон, Сократ) или за двойката (Аристотел, Сократ), защото нито Платон, нито Аристотел са учители на Сократ. Ако искаме да интерпретираме „F“ като триместния предикат „…е дъщеря на…и…“, ще определим, че „F“ е истинна за тези и само за тези наредени тройки от хора (m, n, l), за които важи, че m е дъщеря на n и l.
Така че под интерпретация на една или повече формули в даден универсум на дискурса D ще разбираме: 1) за всяка от участващите във формулите индивидни константи да се определи какво обозначават в D и 2) за всеки от участващите във формулите букви за предикати да се определи за кои неща (или наредени двойки от неща, или наредени тройки от неща и т.н.) в D са истинни.
Определянето на универсум на дискурса D и интерпретация I за една или повече формули, в които няма свободни променливи (т.е. които са твърдения), автоматично определя тяхната истинностна стойност в този универсум на дискурса за тази интерпретация. Съвкупността (наредената двойка) от универсум на дискурса и интерпретация (D, I) се нарича структура. Формулите на предикатната логика са истинни или неистинни винаги по отношение на някаква структура. Структурите в семантиката на предикатната логика са еквивалента на редовете на таблиците за истинност в семантиката на пропозиционалната логика. За разлика от редовете в една таблица за истинност обаче структурите са безкрайно много. Когато всяка формула от едно множество от формули (което може и да е безкрайно) е истинна в една структура, за структурата се казва, че е модел на тези формули. В частност, ако една формула е истинна в дадена структура, за структурата се казва, че е неин модел.
Ако в дадена формула или множество от формули има свободни променливи (т.е. ако формулите не са твърдения, а отворени изречения), те получават истинностна стойност в дадена структура (D, I) само ако свободните променливи в тях получат определени стойности – някакви неща от D. Ще наричаме „даване на стойности“ всяко едно определяне на стойности за свободните променливи. Когато към една структура добавим определено даване на стойности на свободните променливи, не само твърденията, но и отворените изречения получават определена истинностна стойност в нея.
Нека обърнем внимание, че когато фиксираме универсум на дискурса, интерпретация и (евентуално) даване на стойности на свободните променливи, с това формулите не биват отнесени към изречения от естествения език (в качеството им на техни преводи), а към определена действителност (тази на универсума на дискурса). Посредством такова отнасяне към действителността, а не посредством отнасянето им към друг език, те стават истинни или неистинни.
След като вече разполагаме с понятията за структура, универсум на дискурса, интерпретация и даване на стойности на свободните променливи, можем да формулираме семантичните правила на предикатната логика. Те са следните.
По отношение на всяка структура (D, I) и всяко даване на стойности на свободните променливи (ако има такива) важи следното:
Всяко от семантичните правила съответства на едно от синтактичните. Целта е по-сложните изрази да получават своите условия за истинност посредством условията за истинност на участващите в тях по-прости изрази.
Правило I. се отнася до атомарните формули. Ако в тях участват променливи, те са свободни, защото в атомарните формули не участват квантори. Тогава формулите са отворени изречения и са истинни или неистинни само за определени стойности на променливите. Например, ако D е множеството на хората и интерпретацията I отнася „F“ към множеството от наредени двойки, в които първият елемент е учител на втория, a „a“ – към Сократ (човека Сократ, не името „Сократ“), то атомарната формула „Fax“ би била истинна, ако „x“ приеме като стойност Платон и неистинна, ако приеме като стойност Аристотел (отново хората, не имената). Атомарните формули, в които участват само индивидни константи, са твърдения и правилото гарантира, че ще бъдат или истинни, или неистинни в съответната структура. Ако например същата интерпретация I отнася „b“ към Платон, „Fab“ би била истинна в тази структура. По този начин въз основа на семантичното правило I. всяка атомарна формула получава или стойност И, или стойност Н (никога и двете) в която и да е структура при което и да е даване на стойности на свободните променливи (ако има такива).
Правило II. определя по стандартния начин условията за истинност на логическите съюзи. Правилото включва всички семантични правила на пропозиционалната логика (общо пет – по едно за всеки логически съюз). Тези правила биха могли да бъдат намалени до две – до това за отрицанието заедно с някое от правилата за конюнкцията, дизюнкцията или импликацията, защото останалите логически съюзи могат да бъдат дефинирани чрез двата избрани. Тогава дефинираните логически съюзи щяха да получат същите условия за истинност като следствие от условията за истинност на съюзите, чрез които са дефинирани. Да дефинираме посредством два от логическите съюзи останалите би означавало обаче да променим синтаксиса, защото тогава изразите, в които участват дефинирани съюзи, строго погледнато не биха били формули, а съкращения за формули (посредством дефинициите), в които участват само двата избрани логически съюза. Ето например как дизюнкцията, импликацията и еквивалентността биха могли да се дефинират посредством отрицанието и конюнкцията:
| „α∨β“ =def. „¬(¬α∧¬β)“ |
| „α→β“ =def. „¬(α∧¬β)“ |
| „α↔β“ =def. „(α→β)∧(β→α)“ |
В дефиницията на еквивалентността се използва, че импликацията вече е дефинирана в термините на конюнкцията и отрицанието. С таблици за истинност или истинностно-функционален анализ може да се провери, че изразите от двете страни на знакът за дефиниция „=def.“ са логически еквивалентни, поради което имат един и същи смисъл. Възможността за използване на дефиниции и съответно намаляване на семантичните правила обаче беше само отклонение – избрали сме да не дефинираме логически съюзи чрез други и затова даваме семантично правило за всеки от тях.
Въз основа на семантичното правило II. всички съставни формули от вида „¬α“, „α∧β“, „α∨β“, „α→β“ и „α↔β“ (т.е. всички изрази с формата на отрицание, конюнкция, дизюнкция, импликация и еквивалентност) получават или стойност И, или стойност Н във всяка структура (D, I) (при някакво даване на стойности на свободните променливи в тях, ако има такива), при условие, че α и β вече са получили някакви истинностни стойности в тази структура. В структурата, която използвахме като пример по-горе, формулата „Fab“ беше интерпретирана като еквивалентна на твърдението „Сократ е учител на Платон“ и съответно има стойност И в нея. Ако освен това интерпретацията I на структурата отнася буквата за предикат „G“ към красивите неща в D (т.е. към красивите хора), то атомарната формула „Ga“ би имала смисъла на твърдението „Сократ е красив“ и би получила стойност Н в структурата. Тогава въз основа на правило II. формулата „Fab∧¬Ga“ ще получи стойност И в структурата. Условията за истинност, които правило II. придава на отрицанието и конюнкцията правят тази формула равнозначна на твърдението „Сократ е учител на Платон и не е красив“.
Правило III. се занимава с условията за истинност на универсалните и екзистенциалните твърдения или отворени изречения, т.е. на тези формули, в които главният логически оператор е квантор. Да разгледаме като пример структура, чиито универсум на дискурса e множеството на естествените числа (0, 1, 2, ...) и чиято интерпретация отнася буквата за предикат „F“ към безкрайното множество на всички наредени двойки от естествени числа, за които важи, че първото е по-голямо от второто (с други думи „F“ е еквивалентна на предиката „…е по-голямо от…“). Освен това нека константата „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. тя също получава някаква истинностна стойност. Накрая цялата формула получава истинностна стойност. Всичко това позволява да се докаже (строго, с индукция), че въз основа на семантичните правила всяка формула на предикатната логика е истинна или не във всяка структура, при всяко даване на стойности на свободните променливи в нея (ако има такива); и че в никоя структура, при никакво даване на стойности не е едновременно истинна и неистина.
Понятията за логическо следване, логическа еквивалентност, логическа валидност, противоречивост и непротиворечивост се дефинират на базата на понятието за истинност в структура на една формула. Тези най-важни за логиката понятия са свързани с формата на изреченията, не със съдържанието им (с това което се говори в тях), поради което не са зависими от конкретни универсуми на дискурса и интерпретации (от конкретни структури). Резултатът е, че в дефинициите се говори за всички структури. Дадените по-долу дефиниции са отнасят до всякакви формули, не само до твърдения (формули без свободни променливи). Ако се ограничим само до твърденията (игнорирайки отворените изречения), даването на стойности на свободните променливи ще е без значение, тъй като в разглежданите формули няма да има такива. По същество, всеки предикат може да бъде разглеждан като отворено изречение, затова, отнасяйки дефинициите на основните логически понятия също и към формулите със свободни променливи, отнасяме понятията за логически следване, логическа еквивалентност, противоречивост и т.н. също и към термините (частите на твърденията), не само към твърденията.
Логическо следване: Една формула α логически следва от едно множество от формули Δ тогава и само тогава когато, ако всички формули в Δ са истинни в някаква структура (за някакво даване на стойности на свободните променливи, ако има такива), то също и α е истинна в тази структура (за това даване на стойности); т.е. когато всеки модел на Δ е модел и на α.
Съответно, ако предпоставките и заключението на един аргумент от естествения език се представят символно с формули, между които е налице логическо следване в смисъла на горната дефиниция, то този аргумент е логически валиден.
Логическа еквивалентност: Две формули са логически еквивалентни тогава и само тогава, когато са истинни в едни и същи структури (за едни и същи давания на стойности на свободните променливи, ако има такива); т.е. когато моделите им са едни и същи.
Два израза (твърдения или отворени изречения) от естествения език са логически еквивалентни, ако могат да се представят символно с логически еквивалентни формули.
Логическа валидност: Една формула е логически валидна тогава и само тогава, когато е истинна във всяка структура (за всяко даване на стойности на свободните променливи, ако има такива); т.е. когато всяка структура ѝ е модел.
Съответно, един израз от естествения език (твърдение или отворено изречение) е логически валидно, когато може да се представи символно с логически валидна формула.
Понятието за логическа валидност в предикатната логика е аналогът на понятието за тавтология в пропозиционалната логика. В семантиката на предикатната логика структурите (комбинациите между универсум на дискурса, интерпретация и евентуално даване на стойности на свободните променливи) са аналозите на редовете на таблиците за истинност в семантиката на пропозиционалната логика. Понятието за логическа валидност обаче е по-широко от това за тавтология, защото всички тавтологии са логически валидни, но не всички логически валидни формули са тавтологии. Например формулите „Fax ∨ ¬Fax“ и „∃xGxb → ∃xGxb“ са тавтологии, защото имат формата „p∨¬p“ и „p→p“ съответно. Като такива те няма как да са неистинни в която и да е структура (за което и да е даване на стойности на свободните променливи), поради което са логически валидни. Но например формулата „∀xFx → Fa“ е логически валидна без да е тавтология (в пропозиционалната логика ѝ отговаря „p→q“). Формулата е истинна във всяка структура, защото ни казва, че ако всяко нещо е F, то и a е F. Ясно е, че, независимо от структурата, ако всяко нещо от универсума ѝ попада под „F“, то и нещото a (което също е елемент на универсума на дискурса) ще попада под „F“.
В пропозиционалната логика разполагахме с разрешителна процедура (виж 1.6 Логическо следване и логическа еквивалентност), с която винаги можехме да проверим дали дадена схема за извод е логически валидна и дали две формули са логически еквивалентни. Тя почиваше на следните две връзки между понятията за логическо следване и еквивалентност, от една страна, и понятието за тавтология:
| Формулата β логически следва от формулите α1, α2, … , αn, ако и само ако формулата „(α1 ∧ α2 ∧ … ∧ αn) → β“ е тавтология. |
| Формулите α и β са логически еквивалентни, ако и само ако формулата „α ↔ β“ е тавтология. |
Тези два принципа могат да се използват като дефиниции на понятията за логическо следване и логическа еквивалентност посредством понятието за тавтология в пропозиционалната логика. В предикатната логика на понятието за тавтология отговаря по-широкото понятие за логическа валидност. Съответно логическото следване и логическата еквивалентност биха могли да се дефинират по същия начин чрез него, като „тавтология“ се замени с „логически валидна“.
Противоречивост: Една формула е противоречива тогава и само тогава, когато е неистина във всяка структура (за всяко даване на стойности на свободните променливи, ако има такива); т.е. когато няма модели.
Непротиворечивост: Една формула е непротиворечива, когато не е противоречива. С други думи, тогава и само тогава, когато е истинна в поне една структура (за поне едно даване на стойности на свободните променливи, ако има такива); т.е. когато има поне един модел.
Едно твърдение или отворено изречение от естествения език е противоречиво, ако може да се представи символно с противоречива формула, и е непротиворечиво, ако може да се представи символно с непротиворечива формула.
В пропозиционалната логика разполагахме с обща разрешителна процедура, чрез която винаги можехме да проверим дали дадена схема за извод или схема еквивалентност са логически валидни. За целта проверявахме (например с таблица за истинност или истинностно-функционален анализ) дали определена формула е тавтология. Ако разполагахме с подобна обща разрешителна процедура за определяне на това, дали произволна формула на предикатната логика е логически валидна, по същия начин щяхме да можем винаги да проверим дали дадена схема за извод или схема еквивалентност на предикатната логика е логически валидна. Такава разрешителна процедура обаче е невъзможно да бъде формулирана. Това е доказано независимо от Тюринг (Turing, 1936) и Чърч (Church, 1936). От друга страна обаче, малко преди това Гьодел доказва, че съществуват доказателствени процедури, чрез които за всяка логически валидна формула на предикатната логика може да бъде доказано, че е такава (Gödel, 1930). Такива доказателствени процедури се наричат пълни. В следващата секция ще въведем такава доказателствена процедура, за която в 5.1 Пълнота на предикатната логика ще покажем, че е пълна. В комбинация двата резултата означават, че ако от някаква теория (т.е. множество от твърдения) логически следва някакво твърдение, то съществува доказателство за това (както се казва, в ума на бога), което обаче ние може никога да не открием. Разрешителните процедури (алгоритмите) са нещо повече от доказателствените процедури, защото ни гарантират, че ако истинността на едно твърдение може да бъде доказана в рамките на една теория, стига да поискаме (и да имаме време3), със сигурност ще открием поне едно такова доказателство.
Исторически, семантиката на предикатната логика води началото си от една студия на Тарски, издадена през 30-те години на 20-ти век (на полски), която изследва възможността за строга дефиниция на понятието за истина по отношение на формалния език на логиката (Tarski, 1956).