1. Предикатлар мантики формуласининг нормал шакли

11-МАЪРУЗА
РЕЖА:

1. 
   Предикатлар мантики формуласининг нормал шакли.
   
2. 
   Бажарилувчи ва умумкийматли формулалар.
   

11.1 Предикатлар мантики формуласининг нормал шакли.
Формуланинг деярли нормал шакли. Формуланинг нормал шакли. Хар кандай формулани нормал шаклга келтириш. Бажарилувчи формулалар. Умумкийматли формулалар.  Айнан чин формула. Айнан ёлгон формула. Мантик конуни. Умумкийматли ва бажарилувчи формулалар хакидаги теоремалар.
1-таъриф. Агар предикатлар мантики формуласи ифодасида факат инкор, конъюнкция, дизъюнкция  амаллари ва кванторли амаллар катнашиб, инкор амали элементар формулаларга (предмет узгарувчилар ва узгарувчи предикатларга) тегишли булса, бундай формула деярли нормал шаклда дейилади.
Равшанки, предикатлар мантики ва мулохазалар алгебрасидаги асосий тенгкучлиликлардан фойдаланиб, предикатлар мантикининг хар бир формуласини деярли нормал шаклга келтириш мумкин. Масалан,

формулани деярли нормал шаклга келтирайлик.

 
Демак,
.
Предикатлар мантикининг деярли нормал шаклдаги формулалари орасида нормал шаклдаги формулалари мухим рол уйнайди.
Бу формулаларда кванторли амаллар ёки бутунлай катнашмайди, ёки улар мулохазалар алгебрасининг хамма амалларидан кейин бажарилади, яъни нормал шаклдаги формула куйидаги куринишда булади:
, ,
бунда  символи урнига  ёки  кванторларнинг бири тушунилади ва  формула ифодасида кванторлар булмайди.
1-теорема. Предикатлар мантикининг хар кандай формуласини нормал шаклга келтириш мумкин.
Исбот. Формула деярли нормал шаклга келтирилган деб хисоблаймиз ва уни нормал шаклга келтириш мумкинлигини курсатамиз.
Агар бу формула элементар формула булса, у холда унинг ифодасида кванторлар булмайди ва, демак, у нормал шакл куринишида булади.
Энди фараз киламизки, теорема купи билан  амални камраган формула учун тугри булсин ва уни шу фараз асосида  амални камраган формула учун исбот киламиз.
амални уз ичига олган формула ва унинг куриниши  шаклда булсин. Бу ерда  кванторларнинг бирини ифодалайди.
 формула  амални уз ичига олганлиги туфайли уни нормал шаклга келтирилган деб хисоблаймиз. У вактда  формула таърифга асосан нормал шаклда булади.
 формула  куринишда булсин, бунда  формула нормал шаклга келтирилган ва  амални уз ичига олган деб хисобланади. У холда
ва
тенгкучлиликлардан фойдаланиб, инкор амалини предикатлар устига туширамиз. Натижада  формулани нормал шаклга келтирган буламиз.
Энди  формула  куринишда булсин. Бу ерда  ва  лар нормал шаклга келтирилган формулалар деб каралади.
 формулада богланган предмет узгарувчиларни шундай кайта номлаймизки,  ва  формулалардаги хамма богланган предмет узгарувчилар хар хил булсин. У вактда  ва  формулаларни куйидаги куринишда ёзиш мумкин:
, ,
, .
 ва
тенгкучлиликлардан фойдаланиб,  формулани  квантор амаллари остига киритамиз, яъни  формулани ушбу куринишга келтирамиз:
.
Сунгра  формулани

квантор амаллари остига киритамиз. Натижада  формуланинг нормал шаклини хосил киламиз:
.
 куринишидаги  формулани нормал шаклга келтиришнинг исботи худди юкорида каби булади.
Агар формулани нормал шаклга келтириш жараёнида  ёки  куринишдаги ифодаларни куришга тугри келса, у холда
 ва  
тенгкучлиликлардан фойдаланиш керак булади.