Buxoro davlat universiteti fizika-matematika fakulteti "matematika" kafedrasi


Download 73.83 Kb.
bet2/4
Sana31.05.2020
Hajmi73.83 Kb.
#112397
1   2   3   4
Bog'liq
Boboxo‘jayeva Nazokat kurs ishi diskret

...


An ,

in

(in


1)


formulaga elementar konyunksiya deyiladi.
  1. ta’ri f:


1,2 ,...,n

o’zgaruvchilarning har biri0 va 1



qiymatlarni qabul qilganlarida


A1

i1

A2



i2

 ... An ,



in

(in


 1)


formulaga elementar dizyunksiya deyiladi.

  1. ta’rif: Elementar dizyunksiyalarning har qanday konyunksiyasidan tashkil topgan formula konyunktiv normal forma (KNSH) yoki konyunktiv normal formadagi formula deyiladi.

Mukammal dizyunktiv va mukammal konyunktiv normal formalar.





  1. ta’rif: Щar bir propozi tsional o’zgar uv chining yo o’zi, yo inkori bir mar tadan or tiq qa tna shmagan elemen tar kon’yunk tsiya to’g’ri elemen tar kon’yunk tsiya deyiladi.




Misollar: Ta’ri fga ko’ra

A, A B,

7A B,

7A B C D

formulalar



to’g’ri elementar konyunksiyalardir.

A 7A,

B B C D D

formulalar esa,



elementar konyunksiyalar bo’lgani holda, to’g’ri elementar konyunksiyalar

emas, chunki

A  7A

elementar konyunksiyada A o’zgaruvchi o’zining inkori



bilan, BBCDD formulada esa B, D propozitsional o’zgaruvchilar ikki martadan qatnashmoqda.

  1. ta’rif: Shar bir propozitsional o’zgaruvchining yo o’zi yo inkori bir martadan ortiq qatnashmagan elementar dizyunksiya to’g’ri elementar dizyunksiya deyiladi.
  1. ta’rif:


A1 , A2 ,. ,An

Propozitsional o’zgaruvchilardan tashkil



topgan to’g’ri elementar konyunksiyada, har bir o’zgaruvchi rosa bir marta

qatnashgan bo’lsa, bu to’g’ri elementar konyunksiya, A1 , A2 ,. ,An

propozitsional o’zgaruvchilarga nisbatan to’liq elementar konyunksiya deyiladi.
  1. ta’rif:


A1,

A2,. ,An

Propozitsional o’zgaruvchilarda tashkil



topgan to’g’ri elementar dizyunksiyada, har bir o’zgaruvchi rosa bir marta

qatnashgan bo’lsa, bu to’g’ri elementar dizyunksiya A1, A2,..,An

propozitsional o’zgaruvchilarga nisbatan to’liq elementar dizyunksiya deyiladi.

  1. ta’ri f: Mulohazalar algebrasining

A1 , A2 ,. ,An

propozi tsional



o’zgaruvchilardan tashkil topgan

F(A1, A2,. ,An )

formulasining mukammal



dizyunktiv normal forma (shakl) (MDNSH)si deb, shu formulaning tarkibida bir xil elementar konyunksiyalar bo’lmagan, hamda barcha elementar

konyunksiyalari

A1 , A2 ,. ,An

o’zgaruvchilarga nisbatan to’g’ri, to’liq bo’lgan



DNSH siga aytiladi.

Ta’rifga binoan, aynan yolg’on formula uchun MDNSH mavjud emas, chunki agar uning uchun MDNSH mavjud bo’ladigan bo’lsa, bunday MDNSH ning tarkibidagi har bir qo’shiluvchi elementar konyunksiya aynan yolg’on bo’lmog’i lozim. Buni bo’lishi MDNSH tarkibidagi elementar konyunksiyalarda propozitsional o’zgaruvchining ham o’zi, ham inkorini qatnashishini taqozo qiladi. Bu holat formula uchun MDNSH ta’rifidagi bir qismni bajarilmasligini bildiradi.



  1. ta’ri f. M ulo xazalar algebrasining

A1 , A2 ,. ,An

propozitsional



o’zgaruvchilardan tashkil topgan

F(A1, A2 , , An)

formulasining mukammal



konyunktiv normal forma(shakl) (MKNSH)si deb, shu formulaning tarkibida bir

xil elementar dizyunksiyalar bo’lmagan, hamda barcha elementar

dizyunksiyalari

A1 , A2 ,. ,An

o’zgaruvchilariga nisbatan to’g’ri va to’liq



bo’lgan KNSH siga aytiladi.

1- teorema: Mulohazalar mantig’ining aynan yolg’on bo’lmagan har

qanday

F( A1 , A2,..,An )

formulasi yagona MDNSHga teng kuchlidir.



  1. natija: Teng kuchli formulalar bir xil MDNSH ga ega bo’ladi.




  1. natija: Tarkibida n ta har xil o’zgaruvchilar qatnashgan formula aynan rost bo’lishi uchun uning MDNSH si rosa 2n ta har xil to’liq konyunksiyalar dizyunksiyasidan iborat bo’lishi zarur va yetarlidir.




  1. natija: Mulohazalar algebrasini har qanday formulasining inkori, shu formula MDNSH siga kirmaydigan to’liq konyunksiyalarning va faqat shularning dizyunksiyasidan iboratdir.

Mulohazalar algebrasini formulalari MKNSH si uchun ham xuddi yuqoridagi kabi ushbu teoremaning o’rinli bo’lishini ko’rsatish mumkin.


2- teorema: Mulohazalar algebrasining aynan rost bo’lmagan har

qanday

F( A1 , A2,..,An )

formulasi yagona MKNSH ga teng kuchlidir.






  1. natija: Teng kuchli formulalar bir xil MKNSH ga ega bo’ladi.




  1. natija: Tarkibida n ta har xil o’zgaruvchilar qatnashgan formula aynan yolg’on bo’lishi uchun uning MKNSH si 2n ta har xil to’liq elementar dizyunksiyalarning konyunksiyasidan iborat bo’lishi zarur va yetarlidir.




  1. natija: Mulohazalar algebrasining har qanday formulasining inkori shu formula MKNSH siga kirmagan to’liq elementar dizyunksiyalarning va faqat shularning konyunksiyasidan iborat bo’ladi.

Yuqorida keltirilgan teoremalar va ularning natijalari yordamida mulohazalar algebrasining har qanday formulasini aynan rost, aynan yolg’on yoki bajariluvchi formula bo’lishini rostlik jadvalidan foydalanmay aniqlash mumkin. Shuningdek, berilgan qiymatlar to’plamiga ko’ra mulohazalar algebrasining formulasini tuzish mumkin.



Umuman, mulohazalar algebrasining ko’pgina masalalarini mukammal normal formalar yordamida oson hal qilish mumkin.

Misol 1.

A&B\/⌐A&B\/A&⌐B

– MDNSh;




(⌐A1\/A2\/A3 )&(A1\/⌐A2\/⌐A3) – MKNSh bo‘ladi.

Misol 2.

 A&B




CB&






formulani DNSh ga keltiramiz.

C

A



  1.  A&BC C A&B A BC C A&B A BC&C A&B



    1. A BC&C A&B A&C B&C C&C A&A&BB&A&B

        1. C&A&B A&B&C&C&AB AC BC C AB0A



          1. ABC ABC&A B AC BC AB ABCC ABC



      1. CAB AB1 AB ABC СBA AACC ABBC














B




BB




– MDNSH.

Download 73.83 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




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