1. To'plamlar, ularning berilish usullari va ular ustida amallar

ta’rif.

_{x } _<sup>x,

</sup>^x,

аgаr аgаr

• 
   chin,
  
• 
   yo lg`on.
  

x^1  x^{ 2}  x^{ n (1)}
1 2 n

ko‘rinishdagi formulaga elementar kon’yunksiya deb aytamiz. Bu yerda

  { ₁ , ₂ ,...,  _n }
bo‘lishi mumkin.

2. ta’rif.

ixtiyoriy qiymatlar satri va
x_i o‘zgaruvchilar orasida bir xillari

x^1  x^2     x^{n (2)}
1 2 n

ko‘rinishdagi formulaga elementar diz’yunksiya deb aytamiz. Bu erda ham

 ₁  { ₁ , ₂ ,...,  _n } ixtiyoriy qiymatlar satri va bo‘lishi mumkin.
x_i o‘zgaruvchilar orasida bir xillari

3. 
   ta’rif. Elementar diz’yunksiyalarning kon’yunksiyasiga formulaning kon’yunktiv normal shakli (KNSH) va elementar kon’yunksiyalarning diz’yunksiyasiga formulaning diz’yunktiv normal shakli (DNSH) deb aytiladi.
   

^KNSHga (x  y)  (x  z)  (x  y  z)
formula misol bo‘la oladi.
^{formula va DNSHga} x y  xz  x yz

1. 
   teorema. Elementar mulohazalarning har bir P formulasiga teng kuchli kon’yunktiv normal shakldagi Q formula mavjud.
   

Bu teoremani isbotlashda ushbu teng kuchliliklardan foydalanamiz: 1. ^{A  B  A  B} ; 2. ^{A  B  A  B} ;
3. A  B  A  B ; 4. A  B  A  B ; (3)
^5. A  B  (A  B)  (A  B) ^{; 6.} A  B  ( A  B)  ( A  B)
P formulasi tavtologiya ekanligini chinlik jadvaliga murojaat qilmay turib aniqlash mumkinmi degan savolga quyidagi chinlik alomati deb atalgan teorema ijobiy javob beradi.

2. 
   teorema. P formula doimo chin bo‘lishi uchun uning KNSH dagi har bir elementar diz’yunktiv hadida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham mavjud bo‘lishi zarur va yetarli.
   

Isbot: a) P formulaning

P  A₁  A₂  ...  A_n (5)

KNSH dagi har bir A_i hadida kamida bitta elementar mulohaza bilan birga bu

mulohazaning inkori ham mavjud bo‘lsin, ya’ni A_i  x  x  y  u
shaklida

bo‘lsin, u holda ^{x  x  J}

bo‘ladi.
va J  A  J
larga asosan ^A_i ^{ J  (y .... u  V )  J}

Demak,
P  J  J ...  J  J
bo‘ladi, ya’ni aynan chin formula bo‘ladi.

b) Endi P - tavtologiya bo‘lsin va A_i uning KNSH dagi shunday elementar
diz’yunktiv hadi bo‘lsinki, unda birorta elementar mulohaza bilan birga uning
^{inkori qatnashmagan bo‘lsin. Masalan,} A_i  x  y  u
shaklida bo‘lsin. Endi,
elementar mulohazalarning shunday qiymatlar satrini olaylikki, bu satrda ^x ning qiymati yo, y ning qiymati ch, z ning qiymati yo,......, ^u ning qiymati yo bo‘lsin. U vaqtda
Demak,
A_i  x  y ..... u  ^yo  ^ch ..... ^{yo = yo}  .... ^{yo = yo.}
P  A₁  A₂  ...  A_n ning qiymati ham yolg‘on bo‘ladi. Ammo, teoremaningshartiga asosan P ning qiymati aynan chindir. Natijada qarama-qarshilikka keldik. Demak, elementar diz’yunksiyalarning har bir hadida birorta mulohaza o‘zi va o‘zining inkori bilan qatnashishi shart.






Misol. 1. ^{P  x  x  y  y  x  x  y  y  x  x  y  y} .


P  x  x  y  y ^{- aynan chindir.}

2. 
   ^{x  x  (y  y  z)  (x  x)  (y  y)  z  P(x  x)  (y  y  z)} - aynan chin formuladir.
   

Diz’yunktiv normal shakl

Eslatib o‘tamizki, elementar kon’yunksiyalarning diz’yunksiyasiga formulaning diz’yunktiv normal shakli (DNSH) deb aytiladi.

1. 
   teorema. Elementar mulohazalarning istalgan P formulasini DNSHga keltirish mumkin.
   

Isbot. Buning uchun ^P formulani KNSHga keltiramiz:

P  A₁  A₂ ...  A_m

va so‘ngra ^P ning inkorini topganimizda formula DNSH ko‘rinishiga keladi:

P  P  A₁ A₂ ...... A_m  A₁  A₂  A_m .
Endi yolg‘onlik alomati deb atalgan teoremani isbotlaymiz.

2. 
   teorema. P formula aynan yolg‘on bo‘lishi uchun, uning diz’yunktiv normal shaklidagi har bir elementar kon’yunksiya ifodasida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham mavjud bo‘lishi zarur va yetarli.
   

Isbot. a) P -doimo yolg‘on bo‘lsa, u holda ^P - aynan chin bo‘ladi. Demak,
^P ning KNSH dagi har bir elementar diz’yunksiya ifodasida kamida bitta

elementar mulohaza bilan birga uning inkori ham mavjud bo‘ladi. Shuning uchun
P  P ^{ning DNSH dagi har bir kon’yunktiv hadida kamida bitta elementar}
mulohaza va uning inkori mavjud bo‘ladi.
b) Endi har bir elementar kon’yunksiya ifodasida kamida bitta elementar mulohaza va uning inkori mavjud bo‘lsin, ya’ni

^A_i ^{ x}_i  x_i  ^y_i  .....  ^z_i bo‘lsin, u vaqtda A_i  0 va

P  0  0  ...  0  0.
Demak, P doimo yolg‘on formuladir.





Misol. P  (x  x)  y  y  (x  x)  y  y  (x  x)  y  y  (x  x)  ( y  y)
P  (x  x)  (y  y) - aynan chin.

P  (x  x)  (y  y) ^{- aynan yolg‘on.}

3. 
   teorema. Elementar mulohazalarning har bir P formulasi uchun yechilish muammosi yechiladigandir.
   

Isbot. 1. P ni KNSHga keltirgandan keyin, aynan chin bo‘lish - bo‘lmasligi darhol aniqlanadi.

2. 
   P aynan chin bo‘lmasa, uni DNSH ga keltirib, aynan yolg‘on bo‘lish - bo‘lmasligini aniqlaymiz.
   
3. 
   P doimo chin va doimo yolg‘on bo‘lish shartlarini qanoatlantirmasa, u holda bu formula bajariluvchi bo‘ladi.
   

Demak, elementar mulohazalar formulasining aynan chin, aynan yolg‘on yoki bajariluvchi formula bo‘lishini chekli qadamlar protsessida aniqlash mumkin. Shuning uchun echilish muammosi doimo ijobiy hal bo‘ladi.

54. Mantiqiy to'rlar.

Mantiqiy amallar, mantiqiy operatsiyalar — berilgan hadlari va natijasi mulohaza (fikr) dan iborat amallar. Berilgan hadlar soniga qarab Mantiqiy amallar bir oʻrinli, ikki oʻrinli va h.k. deb yuritiladi. Bir oʻrinli Mantiqiy amallar soni toʻrtta: berilgan fikrdan qatʼi nazar natijasi doim chin (aynan haqiqat) amal, natijasi doim yolgʻon (aynan yolgʻon) amal, natijasi berilgan fikr bilan mos tushadigan amal va, nihoyat, berilgan fikr chin boʻlsa, natijasi yolgʻon, berilgan fikr yolgʻon boʻlsa, natijasi chin boʻladigan amal. Soʻnggi mantiqiy amal bir oʻrinli Mantiqiy amallardan eng muhimi boʻlib, u inkor amal deyiladi. A fikrning inkori ~hA kabi belgilanib, "A emas" deb oʻqiladi. Mas, 1 Oy sayyora — "Oy sayyora emas", (] 2*2=4) — ikki karra ikki toʻrt emas.
Ikkilik kodda yozilgan mashina soʻzlari ustida Mantiqiy amallar mos razryadlar boʻyicha bajarilib, i oʻrniga 1, l oʻrniga 0 olinadi, matn shakliga aylantiriladi va maʼlumot koʻrinishida chiqish qurilmasiga beriladi. Mantiq-informatsion mashina tez ishlashi, "xotira" hajmining kattaligi bilan oddiy hisoblash mashinalaridan farq qiladi. Mantiq-informatsion mashina i. t. natijalarini ishlash, adabiyot topishni avtomatlashtirish, sanoat, qishloq xoʻjaligi va transportga oid statistik maʼlumotlarni, davolash muassasalarida bemorlarni kuzatishdan olingan natijalarni, meteorologik, seysmologik stansiyalardan, Yer sunʼiy yoʻldoshlaridan olingan maʼlumotni ishlash va tarjima ishlarida qoʻllaniladi.

55. Mantiq to'rlarini minimallashtirish.

Mukammal diz’yunktiv normal shakllarni minimallashtirishda Bul ifodalarida bir-biriga qo’shni hadlarni topish va bu hadlarni birlashtirish katta mehnat talab qiladi. Bu esa soddalashtirishda analitik usulning kamchiligi hisoblanadi.
Amaliyotda mantiq funktsiyalarini minimallashtirish uchun mantiqiy o’zgaruvchilar soni kamroq bo’lsa, jadval usuli birmuncha qulay hisoblanadi. Jadval usulining ustunligi:

1. 
   birlashtiriladigan hadlarni izlash oson;
   
2. 
   topilgan hadlarni birlashtirish oson;
   
3. 
   funktsiyaning barcha minimal shakllarini topish mumkin.
   

57. Karno kartalar

Karno kartalari
1953 yil Moris Karno Bul ifodalarini soddalashtirish va grafik tasvirlash
tizimini ishlab chiqqanligi haqida maqola e‟lon qildi. Hozirda bu metod
Karno kartalari metodi deb yuritiladi.