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

H(P,Q) = PQ

G(P,Q) =  PQ

PQ =  PQ

S(X,Y,Z)  (XY) Z

S(X,H(P,Q)Z)  (X(PQ)) Z

S(X,G(P,Q),Z)  (X( PQ)) Z

(X(PQ)) Z(X( PQ)) Z

Бу берилган леммаларга кура бир формуладан унга тенг кучли булган бошка формулаларга утиб олишимиз имконияти яратилади.Буни одатда формулаларни тенг кучли алмаштириш деб аталади. Формулаларни тенг кучли алмаштириш куп холларда уларни соддалаштириш учун ишлатилинади.

Масалан:  (х х) (х х)( х х) ( х х)

( х х) ( х х) ( х х)  х  х хх

Тенг кучли алмаштиришда баъзи холларда берилган формулаларни махсус куринишга (нормал формулалар) келтириш учун хам хизмат килади.

Юкорида келтирилган натижалардан шу нарса куринадики, агар кандайдир формула тавтология булса, у холда унга тенг кучли булган хар кандай формула хам тавтология эканлиги куринади. Яъни F ва HF, у холда H бу килинган изох шуни курсатадики, тенг кучли алмаштиришлар у ёки бу формулаларнинг айнан рост эканлигини исботлашда хам кулланилади.
Назорат учун саволлар.
1. Тенг кучли формулалар тушунчаси таoрифини келтиринг.

2. Формулалар тенг кучлилигининг аломати ыандай?

3. Формулалар тенг кучлилиги муносабати ыандай хоссаларни ыаноатлантиради?

4. Тенг кучли формулаларга мисоллар келтиринг.

5. Алмаштириш ъаыидаги леммани келтиринг.

6. Формулаларни тенг кучли алмаштириш деганда нимани тушунасиз?

7. Формулаларнинг айнан ростлигини (яoни тавтология эканлигини) кщрсатиш учун тенг кучлилик муносабатидан ыандай фойдаланилади?

8. (Р  Q)  ... бщш щринга ыандай формулани ыщйсак тенг кучлилик муносабати щрили бщлади?

9. ((РQ)  (Q Р) формулани тенг кучли алмаштиришлар ёрдамида иложи борича энг содда кщринишга келтиринг.

10. X (YZ) X формулани тенг кучли алмаштириш ёрдамида фаыат  ва  амаллар иштирок этган формула кщринишга келтиринг.