3.7 Логически преобразувания в предикатната логика

В 1.6 въведохме принципа за заменимост на еквивалентните, съгласно който, ако заменяме изрази с логически еквивалентни на тях, не настъпва промяна в истинностната стойност на изреченията, от които тези изрази са част. В пропозиционалната логика използвахме принципа в естествената дедукция (1.8) и в логическите преобразувания (1.9). Използвахме го и в доказателствената процедура на предикатната логика (3.5). В последната например изразът „¬∀“ можеше винаги да се замени с „∃¬“, защото всяка формула от вида „¬∀…“ е логически еквивалентна на „∃¬…“. Сега ще продължим с използването на принципа, като в рамките на предикатната логика ще получим процедура, аналогична на логическите преобразувания в пропозиционалната логика.

Някои от схемите еквивалентности, които ще използваме, бяха въведени в 3.5:

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

Правила за преминаване

Една следваща група схеми еквивалентности, които ще използваме, се наричат правила за преминаване.

Ако „р“ стои на мястото на произволно твърдение (да кажем „Сократ е смъртен“), а „F“ – на мястото на произволен (прост или съставен) предикат, е налице следната логическа еквивалентност:

От значение е, че р е твърдение, а не отворено изречение. Това означава, че в p не участват свободни променливи и значи няма и свободни участия на променливата „х“, поради което кванторът „∃x“ е ирелевантен по отношение на p и може да „премине“ през p, без да се промени смисълът на цялото изречение. Например, ако „p“ e „Сократ е смъртен“, а F е предикатът „котка“, твърдението „Съществува нещо, за което е изпълнено, че е котка и че Сократ е смъртен“ („∃x(Fх ∧ p)“) ще е истинно точно тогава, когато е истинно, че съществува поне една котка и че Сократ е смъртен, т.е. когато е истинно изречението „Съществуват котки и Сократ е смъртен“ („∃xFх ∧ p“). Схемата еквивалентност ще е логически валидна и ако „р“ не е твърдение, а е отворено изречение, стига само в него да няма свободни участия на „х“. Тогава кванторът отново ще е ирелевантен по отношение на p и обхватът му ще може да премине през p без да се промени смисълът на цялото изречение. Например валидна е следната схема еквивалентност:

Да се каже, че съществува нещо, за което е изпълнено (като цяло), че е котка (F) и че y е човек (G), е същото като да се каже, че съществуват котки (поне една) и че y е човек.

Така че налице е следната обща, логически валидна схема еквивалентност:

α(x) e израз, в който може да има свободно „x“, a β е израз, в който може да има или да няма свободни променливи, но няма свободно „x“. Разбира се, на мястото на „x“ може да е всяка друга променлива.

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

Първо доказваме, че от „∃x[α(х) ∧ β]“ следва „∃xα(х) ∧ β“:

Доказателство, че от „∃xα(х) ∧ β“ следва „∃x[α(х) ∧ β]“:

Нека видим защо (1) може да не валидно, ако в β участва свободно „x“. Например нека α(x) е „Fx“, а β е „Gx“. Да интерпретираме тогава „F“ като „…е кръгло“, а „G“ – като „…е квадратно“. Изречението „∃x(Fх ∧ Gх)“ ще е неистинно, тъй като ни казва, че нещо е (едновременно) кръгло и квадратно. От друга страна „∃xFх ∧ Gх“ отговаря на отвореното изречение „Нещо е кръгло и х е квадратно“. Когато „х“ приеме като стойност произволно квадратно нещо, това изречение става истинно. Следователно двата израза не са логически еквивалентни – ако бяха, нямаше да е възможно единият да е истинен, а другият не.

Продължаваме нататък с правилата за преминаване. Следната схема еквивалентност също е логически валидна:

Доказателството е подобно на това на (1).

Редът на членовете на конюнкцията и дизюнкцията в (1) и (2) очевидно е без значение – „∃x[β ∧ α(х)]“ ⇔ „β ∧ ∃xα(х)“ и „∃x[β ∨ α(х)]“ ⇔ „β ∨ ∃xα(х)“ са също логически валидни схеми еквивалентности, когато в β няма свободно „х“.

(1) и (2) ни позволяват да преместваме обхвата на екзистенциалния квантор през единия от членовете на произволна конюнкция или дизюнкция, когато в него няма свободно участие на променливата на квантора.

Същото можем да правим и с универсалния квантор, защото следните две схеми еквивалентности също са логически валидни:

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

От своя страна (4) може да бъде изведена от (1) чрез следната поредица от еквивалентности:

Схемите еквивалентности (3) и (4) ни позволяват да преместваме обхвата на универсалния квантор през единия от членовете на произволна конюнкция или дизюнкция, когато в него няма свободно участие на променливата на квантора. И тук както при аналогичните правила за екзистенциалния квантор редът на членовете на дизюнкцията или конюнкцията е без значение – все едно е дали β е на първо, или на второ място. Нещата обаче се променят при правилата за преминаване през антецедент или консеквент на импликация, които ще разгледаме сега.

Това са правилата за преминаване през антецедент на импликация – едното за екзистенциалния, другото за универсалния квантор:

(5) се извежда от (2) чрез следната поредица от еквивалентности:

(6) се извежда от (4) чрез следната поредица от еквивалентности:

Въз основа на схемите (5) и (6) обхватът на екзистенциалния или универсалния квантор може да преминава през антецедента на импликация, когато в него няма свободни участия на променливата на квантора. Те са аналогични на правилата за конюнкцията и дизюнкцията. Правилата за преминаване през консеквент на импликация са по-различни, защото при преминаване на обхватът му през консеквент, кванторът се обръща – ако е бил екзистенциален, става универсален, и обратно. Т.е. валидни са следните две схеми еквивалентности:

(7) се извежда от (2) чрез следната поредица от еквивалентности:

(8) се извежда от (4) чрез следната поредица от еквивалентности:

Следната таблица обобщава правилата за преминаване:

Нека видим как чрез въведените логически еквивалентности можем да преобразуваме изрази на предикатната логика в доста по-различни по-форма изрази, които обаче изразяват същото. Ще покажем, че формулите „∀y¬Fy → (¬∃xGаx ∨ ¬∀yHаy)“ и „∀х∃y[Fy ∨ (Gax → ¬Hay)]“ са логически еквивалентни, като преобразуваме първата във втората:

Пренекс форма

Правилата за преминаване позволяват всяка формула на предикатната логика да бъде преобразувана в такава логически еквивалентна на нея формула, в която всички квантори са в началото на израза. Това става чрез поредица от логически преобразувания, в която кванторите постепенно се изместват напред, докато всичките се окажат в началото. За такава формула, в която всички квантори са отпред, ще казваме, че е в пренекс форма. Ето един пример:

Последният израз е в пренекс форма.

В зависимост от реда, по който кванторите се преместват напред, един израз може да бъде трансформиран в различни пренекс форми. В горния пример можехме първо да преместим напред „∃y“ и „∀z“ и след това „∃x“, в резултат на което накрая щяхме да получим различната, но логически еквивалентна формула в пренекс форма „∃y∀z∃x{Fx → [Gya ∨ (Fyz ∧ Gzy)]}“.

Изразът след кванторите в една формула в пренекс форма се нарича „матрица“. Например матрицата на „∃x∃y∀z{Fx → [Gya ∨ (Fyz ∧ Gzy)]}“ е „Fx → [Gya ∨ (Fyz ∧ Gzy)]“.

Всеки израз може да бъде преобразуван в пренекс форма. Понякога обаче е необходимо да се направят някои предварителни приготовления. Те са два вида. Първият вид приготовление се налага, когато в израза участва материална еквивалентност и в поне едната от формулите, които тя свързва, участва квантор. Тогава, тъй като нямаме правило за преминаване през материална еквивалентност, кванторите ще се окажат „заключени“ от едната страна на еквивалентността и няма да могат да се придвижат напред. Изходът е да заместим еквивалентността с конюнкция от импликации по познатата ни схема „α↔β“ ⇔ „(α→β) ∧ (β→α)“. Тогава правилата за преминаване стават приложими.

Вторият вид приготовление се налага в случаите, когато в израза има два (или повече) квантора с една и съща променлива, или когато квантор има същата променлива като променлива, която е свободна в израза. Тогава трябва да сменим променливи на квантори с нови променливи, докато тези две неща престанат да бъдат факт. Такива смени не променят смисъла на началния израз. Между формулите „∃хFx“, „∃yFy“ и „∃zFz“ например няма никаква смислова разлика – това което ни казват и трите е, че има нещо, което е F. При смяната на променлива на квантор трябва разбира се да сменяме и всички променливи, които кванторът свързва. Ако искаме да сменим например променливата на квантора в „∃х(Fx ∨ ¬Gx)“ с „у“, трябва да заместим с „у“ и участията на „х“ в скобите, в резултат на което ще получим „∃у(Fу ∨ ¬Gу)“.

Да разгледаме случай, при който във формула участва квантор, който има същата променлива като променлива, която е свободна във формулата. Така например стоят нещата с формулата „Fx → ∀xGx“. Участието на „х“ в антецедента на импликацията е свободно в рамките на целия израз, като в същото време в израза има квантор, чиято променлива също е „х“. Това пречи изразът да се сведе до пренекс форма, защото кванторът не може да премине напред поради свободното участие на „х“ в „Fx“. Ако обаче сменим променливата на квантора с нова променлива, която не участва в израза, например с „у“, вече няма да имаме проблем – кванторът „∀у“ в „Fx → ∀уGу“ може да мине напред, тъй като в „Fx“ няма свободно „у“.

Така трябва да постъпим и когато в една формула има квантори с една и съща променлива. Да разгледаме например израза „∀х(Fx → ∃xGxa)“. В него участват универсален и екзистенциален квантор с една и съща променлива. Като резултат „∃x“ не може да излезе напред, защото в „Fx“ има свободно „х“. Ако обаче сменим променливата на единия от кванторите, да кажем на втория, с „у“, вече няма да има проблем. Кванторът „∃у“ в „∀х(Fx → ∃уGуa)“ може да излезе напред, защото в антецедента на импликацията няма свободно „у“. Резултатът е пренекс формата „∀х∃у(Fx → Gуa)“.

Накрая нека преобразуваме в пренекс форма израз, в който са налице и двете неща – участие на материална еквивалентност и квантори с една и съща променлива:

Задачи