Diskret tuzilmalar

Teng kuchli formulalar. Tavtologiya – mantiq qonunii.
I.3.1 - ta’rif. MA ning Á va  formulalari berilgan bo‘lib, bu formulalar tarkibiga kirgan barcha mulohazalar A₁ ,. . ., A_m - lardan iborat bo‘lsin. Agar A₁ , . . . , A _m mulohazalarning barcha qiymatlar tizimlari ( i₁, . . . , i_m ) lar uchun Á va  formulalar bir щil qiymatlar qabul qilsalar, u holda, bu formulalar teng kuchli formulalar deyiladi.
Á va  formulalarning teng kuchliligi Á º  ko‘rinishda ifodalanadi.
I.3.2 - ta’rif. Mulohazalar algebrasining


Á( A₁,. . . , A_n) formulasi A₁ ,. . . , A_n mulohazalarning barcha qiymattizimi ( i₁, . . . , i_n) uchun 1 qiymat qabul qilsa, aynan rost formula yoki tavtologiya yoki mantiq qonunii deyiladi.
Aynan rost formulani qisqacha AR deb belgilaymiz.
I.3.3 - ta’rif. MA ning Á ( A ₁, . . . , A _n ) formulasi

A₁ ,. . . , A_n mulohazalarning barcha qiymattizimi

( i₁ , . . . , i_n ) lar uchun 0 qiymat qabul qilsa, aynan yolg‘on yoki ziddiyat deyiladi
I.3.4 - ta’rif. Agar mulohazalar algebrasining


Á (A₁ , . . . , A_n) formulasi A₁ , . . . , A_n larning kamida bitta ( i₁ , . . . , i_n ) qiymattizimida 1 ga teng qiymat qabul qilsa, u holda bu formula bajariluvchi formula deyiladi.
I.3.5 - teorema. Mulohazalar algebrasining Á va  formulalari teng kuchli formulalar bo‘lishi uchun, Á Û Â formula aynan rost formula bo‘lishi zarur va etarli.


Isbot. Á º  bo‘lsin. U holda Á va  formulalarga kirgan barcha propozitsional o‘zgaruvchilarning barcha qiymattizimlarida Á va  formulalar bir xil qiymatlar qabul qiladilar. YA’ni, Á Û Â = 1 bo‘ladi.
Aksincha, Á Û Â = 1 bo‘lsa, Á = 1 bo‘lganda  = 1 va
Á = 0 bo‘lganda  = 0 bo‘ladi.
I.3.6. Asosiy teng kuchli formulalar.

1. A Ù A º A (kon’yunksiyaning idempotentlik qonunii).

   
   

2. A Ú A º A (diz’yunksiyaning idempotentlik qonunii).

   
   

3. A Ù 1 º A .

   
   

4. A Ú 1 º 1.

   
   

5. A Ù 0 º 0 .

   
   

6. A Ú 0 º A .

   
   

7. A Ú ù A º 1 – uchinchisini inkor qilish qonunii.

   
   

8. A Ù ù A º 0 - ziddiyatga keltirish qonunii.

   
   

9. ù ( ù A ) º A - qo‘sh inkor qonunii.

   
   

10. A Ù ( V Ú A ) º A .

    
    

11. A Ú ( V Ù A ) º A .

    
    

12. A Û V º ( A Þ V ) Ù ( V Þ A ).

    
    

13. A Þ V º ù A Ú V .

    
    

14. ù ( A Ù V ) º ù A Ú ù V .

    
    

15. ù ( A Ú V ) º ù A Ù ù V .

    
    

16. A Ù V º ù ( ù A Ù ù V ).

    
    

17. A Ú V º ù ( ù A Ù ù V ).

    
    

18. A Ù V º V Ù A – kon’yunksiyaning kommutativlik qonunii.

    
    

19. A Ú V º V Ú A – diz’yunksiyaning kommutativlik qonunii.

    
    

20. A Ù ( V Ú S ) º ( A Ù V ) Ú ( A Ù S ) - Ù ning Ú ga nisbatan distributivlik qonunii.

    
    

21. A Ú ( V Ù S ) º ( A Ú V ) Ù ( A Ú S ) - Ú ning Ù ga nisbatan distributivlik qonunii.

    
    

22. A Ù ( V Ù S ) º ( A Ù V ) Ù S – kon’yunksiyaning assotsiativlik qonunii.

    
    

23. A Ú ( V Ú S ) º ( A Ú V ) Ú S – diz’yunksiyaning assotsiativlik qonunii.