Predikatlar. Kvantorlar. Predikatlar algebrasining tili. Predikatlar hisobi. Formal arifmetika. Predikat tushunchasi. Predikatlar ustida amallar

Keltirilgan normal forma.

III.4.1 - ta’rif. Predikatlar algebrasida inkor amali faqat elementar formulalar oldida kelib, kon’yunksiya, diz’yunksiya, kvantor amallaridan boshqa щech qanday amal qatnashmagan formula normal forma ( formula ) deyiladi.

III.4.2 - teorema. Predikatlar algebrasining ixtiyoriy formulasi yo normal forma, yo unga teng kuchli normal forma mavjud.

Isbot. Haqiqatdan, agar formulada Þ , Û amallari qatnashsa, ularda

Á Þ Â º ù Á Ú Â , Á Û Â º (ù Á Ú Â ) Ù ( Á Ú ù Â )

tengkuchliliklardan foydalanib Þ , Û amallarni ù , Ù , Ú amallari bilan almashtiramiz. Inkor amali faqat elementar formulalargagina tegishli bo‘lishi uchun

ù ( Á Ù Â ) º ù Á Ú ù Â , ù ( Á Ú Â ) º ù Á Ù ù Â ,

ù ( "x R ( x )) º $x ù R ( x ) , ù ( $x R ( x ) º "x ù R ( x )

tengkuchliliklardan foydalanish etarli.

III.4.3 - ta’rif. Predikatlar algebrasining normal formasida kvantorlar qatnashmasa yoki hamma kvantorlar barcha amallardan avval kelsa, bunday forma keltirilgan normal forma yoki preniksli normal forma deyiladi.

III.4.4 - teorema. Predikatlar algebrasining ixtiyoriy formulasi yo keltirilgan normal forma yo unga teng kuchli keltirilgan normal forma mavjud.

Bu teoremaning isbotini III.4.2 – teoremadan va III.3-§ da keltirilgan asosiy tengkuchliliklardan keltirib chiqarish mumkin.