Mustaqil ishisi Toshkent 2021 Predikatlar algebrasi, mulohazalar hisobi formulasi



Download 61,15 Kb.
bet1/3
Sana02.01.2022
Hajmi61,15 Kb.
#307300
  1   2   3
Bog'liq
diskrit mustaqil ish


Toshkent axborot texnologiyalari universiteti

Radio va mobil aloqa fakulteti 810-20 gurux

talabasi Sayfiyev Fayozjonning Diskret tuzilmalar

fanidan yozgan Mustaqil ishisi



Toshkent 2021
Predikatlar algebrasi, mulohazalar hisobi formulasi

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



1 - 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.

2 - 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.

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

XX asrning 40 – yillarida algoritm tushunchasiga aniq ta’rif berilganidan so`ng echilish muammosini hal qilish imkoni hosil bo‘ldi. 1936 yilda amerikalik matematik A.CHyorch predikatlar algebrasi uchun echilish muammosi umumiy holda ijobiy hal qilinmasligini isbot qilgan.

Echilish muammosi chekli sohalar uchun ijobiy hal qilinishi ravshan. Ha=iqatdan, agar ℑ (x1, . . . , xn) formula ℳ to`plamning elementlarini x1, . . . , xn o‘zgaruvchi predmetlar o`rniga qo‘yib chiqib, ℑ formulaning qiymatlarini tekshirib chiqamiz. Bu jarayon chekli qadamda yakunlanadi. Kvantor amallarini esa kon’yunksiya, diz’yunksiya amallari bilan almashtirish mumkin.

1 - misol. "x $u ( R ( x, u, z ) Ú Q ( x )) formula

ℳ = { a, b } to`plamda bajariluvchi bo‘lish bo‘lmasligini aniqash uchun avval formula ko‘rinishini asosiy tengkuchliliklar yordamida o‘zgartiramiz :"x $u ( R ( x, u, z ) Ú Q ( x )) º "x ( P ( x, a, z ) Ú Q ( x ) Ú

Ú R ( x, b, z )) º ( P ( a, a, z ) Ú Q ( a ) Ú P ( a, b, z )) Ù

Ú ( P ( b, a, z ) Ú Q ( b ) Ú P ( b, b, z )).
Hosil bo‘lgan formulada z o`rniga a va b qiymatlarni ketma-ket qo‘yib berilgan formulaning bajariluvchi bo‘lish- bo‘lmasligini aniqash mumkin.

3 - ta’rif. Agar predikatlar algebrasining formulasida erkli o‘zgaruvchilar qatnashmasa, bunday formula yopiq formula deyiladi.

2 - misol. "x "u $z ( P ( x, y ) Ú R ( x, z )) – formula yopi= formuladir.

III.6.4 - ta’rif. Agar predikatlar algebrasining

( x1, . . . , xn ) formulasida x1, . . . ,xn – erkli predmet o‘zgaruvchilar qatnashgan bo‘lsa, u holda

" x1 " x2. . . " xn ℑ ( x1, . . . ,xn ) – formula ℑ ( x1, . . . ,xn )

formulaning umumiylik (kvantori orqali) yopi\i,

$ x1 $ x2 . . .$ xn ℑ ( x1, . . . ,xn ) esa berilgan formulaning mavjudlik (kvantori orqali) yopi\i, ikkala $ ," kvantorlar yordamida hosil qilingan yopiq formula - berilgan formulaning aralash yopig‘i deyiladi.

3 - misol. $x R ( x, u, z ) formula berilgan bo‘lsin. U holda "u "z $x R ( x, u, z ) berilgan formulaning umumiylik yopi\i, $u $z $x R ( x, u, z ) – mavjudlik yopi\i,

"u $z $x R ( x, u, z ) – aralash yopig‘i bo‘ladi.

3 – teorema. Predikatlar algebrasining yopiq, normal formasida faqat n ta mavjudlik kvantori qatnashib, umumiylik kvantorlari qatnashmagan bo‘lsin. Agar bu formula ixtiyoriy bir elementli to`plamda rost qiymat qabul qilsa, u holda u umumqiymatli formuladir.

Isbot. Teorema shartiga asosan olingan formula quyidagi ko‘rinishda bo‘lsin :

ℬ = $x1. . . $xn ℑ ( U1, . . . ,Up ; P1, . . . , Pq ; . . .

Q1, . . . , Qt ) ( 1 ).

ℬ formulada Y1,Y2, . . . , Yp – o‘zgaruvchi mulohazalar ;

P1,P2, . . . , Pq – bir o‘rinli predikatlar simvollari va h.k.

Q1, Q2, . . . , Qt - m – o‘rinli predikatlar simvollari;

ℑ - teorema shartiga ko`ra kvantorsiz formuladir.

Teorema shartiga ko`ra ℬ formula ixtiyoriy bir elementli ℳ = { a } to`plamda aynan rost. YA’ni

ℑ ( U1, . . . ,Ur ; R1( a ) , . . . , Rq ( a ) ; Q1( a, . . . , a ), . . .

Qt( a, . . . , a ) ) = 1.

Faraz qilaylik ( 1 ) formula umumqiymatli formula bo‘lmasin. U holda shunday ℳ1 soha, U10, . . . , Ur0 – mulohazalar,

R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 - ℳ1 sohada aniqangan

predikatlar mavjud bo‘lib, ( 1 ) formula « yolg‘on»

qiymat qabul qilsin. YA’ni :

$x1. . . $xn ( ℑ ( U10, . . . , Ur0; R10, . . . , Rq0; . . .

Q10 , . . . , Qt0 )) = 0 ( 3 ).

U holda ù ( $x1. . . $xn ( ℑ ( U10, . . . , Ur0; R10, . . . , Rq0; . . . ;

Q10, . . . , Qt0 ))) = "x1. . . "xn ( ù ( ℑ ( U10, . . . , Ur0;


R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ))) = 1 .

Demak, ù ( ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ;

Q10, . . . , Qt0 )) – formula o‘zgaruvchi predikatlarning ℳ1

to‘plamdagi barcha qiymatuchun aynan rost bo‘ladi.

Xususan, ixtiyoriy ℳ1 = { x0 } – bir elementli to`plam uchun

ℑ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ) = 0 .

Bu esa teorema shartiga zid.

4 – teorema. Predikatlar algebrasining yopiq, keltirilgan normal formulasida faqat n ta umumiylik kvantori qatnashib, mavjudlik kvantorlari qatnashmasin. Agar bu formula elementlari soni n tadan ko‘p bo‘lmagan har qanday to`plamda aynan rost formula bo‘lsa, u holda u umumqiymatli formuladir.




Download 61,15 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish