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

Теорема: Мулохазалар алгебрасидаги F ва H формулалар тенг кучли булишлиги учун FH формулаларнинг тавтология булиши зарур ва етарли . Яoни F  HFH

Шуни эслатиб утиш керакки, F  H ифода мулохазалар алгебрасида формулани англатмайди, балки мулохазалар алгебрасидаги формулалар уртасидаги муносабатни билдиради холос. Куйдаги келтириладиган натижада формулалар тенг кучлилиги баъзи бир хоссалари келтириб утилади.

Натижа: Формулалар тенг кучлилиги эквивалентлик муносабатидир , яoни куйдаги хоссаларга эга:

1.рефлексиф: FF

2.симметрик: агар FH у холда HF

3.транзитив: агар FH ва HG булса, у холда FG.

Хар кандай эквивалентлик муносабати каби  муносабат мулохазалар алгебрасидаги формулани узаро кесишмайдиган эквивалент синифларга ажратиш имкониятини яратади. Бу ерда хар бир эквивалент синфларда узаро тенг кучли булган формулалар ётади. Масалан: Шундай синфлардан бири мулохазалар алгебрасидаги барча тавтологияларни уз ичига олади. Мулохазалар алгебрасида бундан ташкари жуда куп эквивалент синфларни курсатишимиз мумкин.

Тенг кучли формулаларга мисоллар: Куйида келтириладиган тенг кучли формулаларга мисоллар юкорида келтирилган 3.1-3.4 тавтологиялардан хосил килингандур.

4.4

1)   P  P

2) PQ   Q P

3) PQ   P Q

4) P(QR) (PQ)R

5) (PR) (QR)  (PQ)R

6) PPP

7) PQQP

8) PQQP

9) P(QR) (PQ) R

10) P(QR) (PQ)R

11) P(QR) (PQ) (PR)

12) P (QR) (PQ)  (PR)

13) P(PQ) P

14) P (PQ) P

15)  (PQ)  P Q

16)  (PQ)  P Q

17) PQ QP

18) PQ  P Q

19) PQ  (P Q)

20) PQ   (P Q)

21) PQ   PQ

22) PQ( PQ) (QP)

23) P P1 P P0

24) P11 P1P

25) P 0P P00

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

Лемма(алмаштириш хакида): Агар H(У,У,...,У)  G(У,У,...,У) тенг кучли булса, у холда мулохазалар алгебрасидаги итиёрий булган F(х,х