3 Pravila transformacija

Negacija

¬∀x. A ≡ ∃x. ¬A

¬∃x. A ≡ ∀x. ¬A

Konjukcija i disjunkcija

Primetite da pravila važe isto za oba kvantifikatora

Ako se promenljiva x javlja slobodna u B treba da se izvrši njeno preimenovanje u formuli ∀x.A - umesto x nazovite je y,z... prvo sledeće neupotrebljeno slovo. 

Grupisanje pod kvantifikator

(∃x. A) ∨ (∃x. B) ≡ (∃x. A∨B)

(∀x. A) ∧ (∀x. B) ≡ (∀x. A∧B)

Ali ne smemo da radimo ovo, iako možda deluje isto:

(∃x. A) ∧ (∃x.B) !≡ (∃x.A ∧ B)

to što postoje neki elementi za koje važi A i neki za koje važi B ne mora da znači da su to isti elementi i da za sve njih važi i A i B

(∀x. A) ∨ (∀x.B) !≡ (∀x. A∨B)               

u levom delu tvrdimo da za svako x važi A, ili da za svako x važi B. Dakle, moguća je i varijanta da važi samo A, da nema nijednog x za koje važi B. U desnom delu tvrdimo da za svako x važi A ili B, pa bi za neke x važilo A, za neke druge B, za neke možda i oba. U levom delu tvrdimo da za sve x važi A ili da za sve x važi B, a ne za neke A za neke B.

Ovo može biti ekvivalentno u graničnom slučaju, ali ne mora, u opštem slučaju očekujemo da nije isto.

Grupisanje kvantifikatora ispred celog izraza

Ako imamo izraz koji ima dve formule ali sa različitim kvantifikatorima, onda možemo da kvantifikatore izdvojimo ispred, ali moramo da radimo preimenovanje promenljive u jednom od njih.

∃x.A(x) ∨ ∀x.B(x) ≡ ∃x∀y.A(x)∨B(y)

Moramo da u B(x) preimenujemo x u y, jer bismo inače dobili (∀x. A) ∨ (∀x.B) !≡ (∀x. A∨B)  što nije isto (vidi pravila iznad)

Dalje, ostale kombinacije:

∃x.A(x) ∧ ∀x.B(x) ≡ ∃x∀y.A(x)∧B(y)

∀x.A(x) ∨ ∃x.B(x) ≡ ∀x∃y.A(x)∧B(y)

∀x.A(x) ∧ ∃x.B(x) ≡ ∀x∃y.A(x)∧B(y)

Ako imamo izraz koji ima dve formule, tako da su obe pod jednim kvantifikatorom, a jedna unutar pod drugim kvantifikatorom, možemo da izdvojimo oba kvantifikatora ispred. Ovde treba da vodite računa o tome koje su promenljive vezane za šta.

∀x( A(x) ∨ ∃yB(y) ) ≡ ∀x∃y( A(x) ∨ B(y) )

Isto važi i ako se u B nalazi x, jer je taj x svakako kvantifikovan "spoljnim" kvantifikatorom.

∀x( A(x) ∨ ∃yB(x,y) ) ≡ ∀x∃y( A(x) ∨ B(x,y) )

Ovde možemo da razmišljamo i ovako: imamo međukorak, gde idemo "unazad", razbijamo izraz, pa vidimo da levi deo može da uđe pod desni

∀x( A(x) ∨ ∃yB(x,y) )  ≡  ∀x(A(x)) ∨ ∀x∃y( B(x,y) )  ≡  ∀x∃y ( A(x) ∨ B(x,y) )

Isto važi i za ∧