Кукон давлат педагогика институти

Бу ерда куйдаги нарсани эслатиб утиш лозим: баъзи холларда баъзи предикатлар бир хил тупламлардан тенг кучли булиб, бошка тупламларда тенг кучли булмаслиги мумкин. Масалан: Р(х,у)==15 Q(x,y)==15 бу предикатлар барча мусбат сонлар тупламда каралса тенг кучли эмас.

Таъриф: М₁ М₂...М_n тупламларда аникланган n- уринли Q(х₁,х₂,...,х_n) предикат шу тупламда аникланган Р(х₁,х₂,...,х_n) келтириб чикарилган дейилади, агар Р предикат Q предикат рост буладиган кийматларда рост мулохазага айлансин. Бошкачи килиб айтганда Q дан Р келтириб чикарилган дейилади, агар Q Р булса. Q дан Р келтириб чикарилганллик QP каби белгиланади.

Мисол: P(n): “n натурал сон 3 га булинади.” Р={3k kN}

Q(n): “n натурал сон 6 га булинади.” Q={6k kN}

Q Р бунда QР

Предикатни ростлик сохаси тушинчаси ёрдамида тенг кучлилик ва келтириб чикарилганлик уртасида узаро богланишни урганишимиз мумкин: 2 предикат тенг кучли булади, факат ва факат хар бир предикат иккинчисидан келтириб чикарилган булса. Яъни QР агар Q Р ва Р Q булса. Бундан ташкари куйдаги теоремани куриш мумкин.

Теорема: Бир хил тупламда аникланган айнан рост (айнан ёлгон) предикатларнинг тенг кучлидир, яъни Q=М Q= ва аксинча айнан рост (айнан ёлгон) предикат Р=М Р=  га тенг кучли булган предикат айнан рост (айнан ёлгон) булиши мумкин.

Теорема. Ъар ыандай n-щринли айнан рост предикат ъудди шу тщпламда аниыланган бошыа ихтиёрий n-щринли предикатдан келтириб чиыарилган бщлади.

Ъар ыандай n-щринли предикат шу тщпламда аниыланган ихтиёрий айнан ёльон n-щринли предикат келтириб чиыарилган бщлади.

Теорема. Р(x₁,x₂,..x_n) ва Q(x₁,x₂,..x_n) бир хил тщпламда аниыланган иккита n-щринли предикат бщлсин ъамда РQ щринли бщлсин. У ъолда:

а) агар Р айнан рост (бажарилувчи) предикат бщлса, у ъам айнан рост (бажарилувчи) предикат бщлади.

б) агар Q айнан ёльон (инкор ыилинувчи) предикат бщлса, у ъолда Р ъам айнан ёльон (инкор ыилинувчи) предикат бщлади.