Teng kuchli formulalar va asosiy teng kuchliliklar Ta’rif
Download 139 Kb.
|
диск 6 дан 18гача (1)
- Bu sahifa navigatsiya:
- Asosiy teng kuchli formulalar .
- Mulohazalar algebrasi formulasining normal shakllari. Mukammal dizyunktiv va konyunktiv normal formalar. Mulohazalar algebrasini tatbiqlari
- Ta’rif 1.
- Ta’rif 2.
- Asosiy mantiqiy amallarning chinlik to‘plamlari.
- Bul funksiyalari. Bul ayniyatlari. Formulalarning teng kuchliligi. Predikatlar. Umumiylik va mavjudlik kvantorla
|
Teng kuchli formulalar va asosiy teng kuchliliklar Ta’rif: Tarkibidagi xi(i=) o’zgaruvchilarning mumkin bo’lgan barcha qiymatlar tizimida A(x1, x2, …, xn) va B(x1, x2, …, xn) formulalarning qiymatlari ustuni bir xil bo’lsa, u holda bu formulalar o’zaro teng kuchli formulalar deyiladi va uni A(x1, x2, …, xn)≡B(x1, x2, …, xn) ko’rinishda belgilanadi. Misol:
Agar va formulalar teng kuchli bo’lsalar, u holda va lar aynan rost formulalar bo’lishi ravshandir. Aksincha, qandaydir va (bir xil propozitsional o’zgaruvchilarga ega bo’lgan) formulalar uchun va lar aynan rost furmulalar bo’lsa, u holda bo’ladi. va formulalar teng kuhli formulalar ekanini ko’rsataylik:
Shunday qilib, bu tengkuchliliklarnda ko’rinadiki, bo’lishi uchun formula aynan rost formula bo’lishi zarur va yetarlidir. Teng kuchli bo’lish munosabati ekvivalent binary munosabat ekanligi ravshandir, ya’ni bu munosabat –refleksivlik. Agar bo’lsa, u holda bo’ladi – simmetriklik va Agar va bo’lsa, u holda bo’ladi – tanzitivlik xossalariga egadir. Asosiy teng kuchli formulalar. A Ù A º A (kon’yunksiyaning idempotentlik qonunii). A Ú A º A (diz’yunksiyaning idempotentlik qonunii). A Ù 1 º A . A Ú 1 º 1. A Ù 0 º 0 . A Ú 0 º A . A Ú ù A º 1 – uchinchisini inkor qilish qonunii. A Ù ù A º 0 - ziddiyatga keltirish qonunii. ù ( ù A ) º A - qo‘sh inkor qonunii. A Ù ( V Ú A ) º A . A Ú ( V Ù A ) º A . A Û V º ( A Þ V ) Ù ( V Þ A ). A Þ V º ù A Ú V . ù ( A Ù V ) º ù A Ú ù V . ù ( A Ú V ) º ù A Ù ù V . A Ù V º ù ( ù A Ù ù V ). A Ú V º ù ( ù A Ù ù V ). A Ù V º V Ù A – kon’yunksiyaning kommutativlik qonunii. A Ú V º V Ú A – diz’yunksiyaning kommutativlik qonunii. A Ù ( V Ú S ) º ( A Ù V ) Ú ( A Ù S ) - Ù ning Ú ga nisbatan distributivlik qonunii. A Ú ( V Ù S ) º ( A Ú V ) Ù ( A Ú S ) - Ú ning Ù ga nisbatan distributivlik qonunii. A Ù ( V Ù S ) º ( A Ù V ) Ù S – kon’yunksiyaning assotsiativlik qonunii. A Ú ( V Ú S ) º ( A Ú V ) Ú S – diz’yunksiyaning assotsiativlik qonunii. Mulohazalar algebrasi formulasining normal shakllari. Mukammal dizyunktiv va konyunktiv normal formalar. Mulohazalar algebrasini tatbiqlari Mukammal diz’yunktiv va kon’yunktiv normal shakllar. Normal shakllar. Har bir fikr algebrasi formulasi uchun unga teng kuchli bo‘lgan va faqatgina inkor ⌐, kon’yunksiya &, diz’yunksiya \/ amallarini o‘z ichiga olgan formulani keltirish mumkin. Buning uchun implikasiya va ekvivalensiyadan qutulish qoidalaridan foydalanish kifoya. Ta’rif 1. A1, A2, …, An fikr o‘zgaruvchilarining kon’yunktiv bir hadi deb, ushbu o‘zgaruvchilar yoki ularning teskarilarining kon’yunksiyasiga aytiladi. Masalan: ⌐A1&A2&A3, ⌐A1&A2&A3&⌐A4 Ta’rif 2. A1, A2, …, An fikr o‘zgaruvchilarining diz’yunktiv bir hadi deb, ushbu o‘zgaruvchilarning yoki ularning teskarilarining diz’yunksiyasiga aytiladi. Masalan: ⌐A1\/A2\/A3 Ta’rif 3. Diz’yunktiv normal shakl (DNSh)deb, kon’yunktiv bir hadlar diz’yunksiyaga aytiladi, ya’ni ai , i=1, 2, …, k kon’yunktiv bir hadlar bo‘lsa a1\/a2\/…\/an - ifodaga Diz’yunktiv normal shakl deyiladi. Ta’rif 4. Kon’yunktiv normal shakl (KNSh) deb, dizyunktiv bir hadlar kon’yunksiyasiga ayiladi, ya’ni bi , i=1, 2, …,l kon’yunktiv bir hadlar bo‘lsa, b1&b2&…&bn – ifoda KNSh deyiladi. Har bir formula uchun cheksiz ko‘p KNSh, DNSh lari mavjud. Mukammal normal shakllar Ta’rif 5. Agar bir hadga Ai yoki ⌐Ai formulalar juftligidan faqat bittasi kirgan bo‘lsa, A1, A2, …, An fikr o‘zgaruvchilarining kon’yunktiv yoki diz’yunktiv bir hadlari mukammal deyiladi. Ta‘rif 6. Agar KNSh yoki DNSh larda A1, A2, …, An o‘zgaruvchilarning takrorlanmaydigan mukammal bir hadlari kirgan bo‘lsa, A1, A2, …, An fikr o‘zgaruvchilarining KNSh yoki DNSh lari mukammal deyiladi. Masalan: A&B\/⌐A&B\/A&⌐B – A va B fikr o‘zgaruvchilarining Mukammal diz’yunktiv normal shakli (MDNSh) bo‘ladi. A\/B – esa MKNSh bo‘ladi. Teorema 1. Har bir ayniy yolg‘on bo‘lmagan formula yagona MDNF ega bo‘ladi. Teorema 2. Har bir tavtologiya bo‘lmagan fikrlar algebrasi formulasi, yagona MKNSh ga ega bo‘ladi.\ Asosiy mantiqiy amallarning chinlik to‘plamlari. Chinlik to‘plamlari mos ravishda va bo‘lgan va formulalar berilgan bo‘lsin. Kon’yunksiyaning chinlik to‘plami. va formulalar kon’yunksiyasining chinlik to‘plami bo‘ladi. Haqiqatdan ham, kon’yunksiya ta’rifiga asosan, formula va formulalarning ikkalasi ham chin bo‘lgandagina chindir. Shuning uchun, formulaning chinlik to‘plami va to‘plamlarning umumiy elementlaridan tuzilgan kesishmasidan iborat bo‘ladi. Demak, mulohazalar mantiqidagi kon’yunksiya amaliga ( belgiga) to‘plamlar nazariyasidagi kesishma amali ( belgi) mos keladi Bul funksiyalari. Bul ayniyatlari. Formulalarning teng kuchliligi. Predikatlar.Umumiylik va mavjudlik kvantorla Kalit so’zlar:Bul funksiyalar, Bul algebrasi, ahamiyatli va ahamiyatsizo’zgaruvchilar, formula, ikkilamchi funksiya, ikkilamchi prinsipi.Ma’lumki, mantiqiy amallar mulohazalar algebrasi nuqtai nazardan chinlikjadvallari bilan to’liq xarakterlanadi. Agarda funskiyaning jadval shaklda berilishiniesga olsak, u vaqtda mulohazalar algebrasida ham funksiya tushunchasinianiqlashimiz mumkin.Ta’rif. x1, x2, … ,xnmulohazalar algerbasining x1, x2, … ,xnargumentli f(x1, x2,… ,xn) funksiyasi deb nol va bir qiymat qabul funksiyaga aytiladi va uning x1, x2, …,xnargumentlari ham nol va bir qiymatlar qabul qilinadi.Ta’rif. F:{0,1}n-> {0,1} funksiya mantiqiy algebraning funksiyasi yoki Bulfunksiyasi deyiladi. N-o’zgaruvchili Bul funksiyalar to’plaminiPnorqali belgilaymiz,ya’ni 𝑃?= {?; ?: {0,1}?→ {0,1}}Bir o’zgaruvchili funksiyalar 4 ta bo’lib, ular quyidagilar1.f0(x)=0–aynan nolga teng funksiya yoki aynan yolg’on funksiya2.f1(x)=x–aynan funksiya3.?2(?) = ?̅ = ¬? = ?′- inkor funksiya4.f3(x)=1–aynan birga teng funksiya yoki aynan chin funksiya Download 139 Kb. Do'stlaringiz bilan baham: 
|