Alisher navoiy nomidagi samarqand davlat universiteti mexanika-matematika fakulteti

5-  t a ’ r i f . Agar formulaning MKNShi (MDNShi) ifodasida qatnashuvchi barcha elementar 
mulohazalardan  tuzish  mumkin  bo‘lgan  barcha  elementar  diz’yunksiyalar  (kon’yunksiyalar)  shu 
ifodada ishtirok etsa, u holda bunday MKNSh (MDNSh) to‘liq MKNSh (MDNSh) deb ataladi. 
6 -   m i s o l .  Ushbu 
)
)(
)(
(
y
x
y
x
y
x



 formula 
x  va 
y
 elementar mulohazalarga nisbatan 
MKNShda  bo‘lsada,  u  to‘liq  MKNShda  emas. 
x   va 
y
  elementar  mulohazalarga  nisbatan  to‘liq 
MKNShi ifodasi 
)
)(
)(
)(
(
y
x
y
x
y
x
y
x




 ko‘rinishga ega. 
MDNShdagi 
z
y
x
z
y
x
z
y
x
z
y
x



  formula 
x , 
y
  va 
z  elementar  mulohazalarga nisbatan 
to‘liq MDNShda emas, lekin 
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x







 formula bu elementar 
mulohazalarga nisbatan to‘liq MDNShdagi formuladir. ■ 
 
 
Teng kuchlimas formulalar soni.
 
Endi 
n ta elementar mulohazalarning o‘zaro teng kuchlimas, ya’ni har xil formulalari sonini 
topish masalasini qaraymiz. 
Agar berilgan formula tarkibida faqat bitta (masalan, 
x ) elementar mulohaza ishtirok etsa, u 
holda  bu  formula  uchun  tuzilgan  chinlik  jadvalining  bir-biridan  farqli  mumkin  bo‘lgan  qiymatlar 
satrlari  ikkita  bo‘ladi.  Shuning  uchun 
1

n
  bo‘lsa  jami  4ta  (
n
C
C
C
2
2
2
2
2
1
2
0
2
2
2
2
1





)  turli 
formulalar  bor.  Bitta  elementar  mulohaza  uchun  bu  4ta  turli  formulalarning  tavtologiya  va  aynan 
yolg‘ondan  farqli  bo‘lganlari  (ya’ni,  2tasi)  bajariladigan  formulalardir.  Ularni  MDNShda  ham 
MKNShda  ham,  tavtologiyani  MDNShda,  aynan  yolg‘on  formulani  esa  MKNShda  ifodalansh 
mumkin. 
O‘zgaruvchilar  soni 
2

n
  bo‘lganda  chinlik  jadvalidagi  qiymatlar  satrlari 
4
2
2
2


n
ta 
bo‘ladi. Yuqorida qaralgan chinlik jadvali asosida formulani tiklash masalasini hal qilish jarayonida 
barcha  mumkin  bo‘lgan  imkoniyatlar  uchun  chinlik  jadvalining  ustunlari  tekshirilgan  edi.  Bu  16ta 
ustunlarning  hech  qaysi  ikkitasi  bir  xil  bo‘lmaganligidan,  ularga  mos  ikkita  formulalar  ham  o‘zaro 
teng kuchli emas. Shuning uchun, umimiy soni 
n
C
C
C
C
C
2
2
4
4
4
3
4
2
4
1
4
0
4
2
2
2
2







 bo‘lgan ikki 
o‘zgaruvchili turli formulalar bor. 
Ikkita  elementar  mulohazalar  uchun  bu  16ta  turli  formulalarning  tavtologiya  va  aynan 
yolg‘ondan  farqli  bo‘lganlari  (ya’ni,  14ta  bajariladigan  formula)  MDNShda  ham  MKNShda  ham, 
tavtologiya MDNShda, aynan yolg‘on formula esa MKNShda ifodalanishi mumkin. 

 
 
O‘zgaruvchilar soni 
3

n
 bo‘lganda ham chinlik jadvali asosida formulani tiklash masalasini 
hal  qilish  jarayoniga  tayanib  uchta  elementar  mulohazalarning  256ta  teng  kuchlimas  formulalari 
borligi, 256 esa 
n
i
i
C
2
2
8
8
0
8
2
2
2
3





 ko‘rinishda ifodalanishi mumkinligini ta’kidlaymiz. 
Uchta  elementar  mulohazalar  uchun  bu  256ta  turli  formulalarning  254tasi  (bajariladigan 
formulalar)  MDNShda  ham  MKNShda  ham,  tavtologiya  MDNShda,  aynan  yolg‘on  formula  esa 
MKNShda ifodalanishi mumkin. 
Umuman  olganda,  matematik  induksiya  usulidan  foydalanib  (I  bobga  qarang)  quyidagi 
tasdiqni isbotlash mumkin. 
T e o r e m a . 
n ta elementar mulohazalar uchun teng kuchlimas formulalar soni 
n
2
2 ga teng. 
I s b o t i  o‘quvchiga havola qilinadi. 
Tarkibida 
n ta elementar mulohaza ishtirok etgan 
n
2
2 ta turli formulalardan 
(
2
2
2

n
)tasi  bajariladigan  formulalardir.  Ular  MDNShda  ham  MKNShda  ham,  tavtologiya 
MDNShda, aynan yolg‘on formula esa MKNShda ifodalanishi mumkin. 
3.7.3.  Formulani  qatorga  yoyish.  Yuqorida  keltirilgan  mulohazalardan 
n ta 
n
x
x
x
,...,
,
2
1
 
o‘zgaruvchilarga  bog‘liq,  aynan  yolg‘on  bo‘lmagan  ixtiyoriy 
)
,...,
,
(
2
1
n
x
x
x
A
A 
  formulani 
(funksiyani) MDNShda 
n
n
n
A
n
x
x
x
x
x
x
A






...
)
,...,
,
(
2
1
2
1
2
1
1
)
,...,
,
(
2
1



 
(1) 
yozish mumkinligi kelib chiqadi. (1) teng kuchlilikning o‘ng tomonidagi (tagida 
1
)
,...,
,
(
2
1

n
A



 
yozilgan) 
   belgi  n   o‘zgaruvchili 
n
n
x
x
x



...
2
1
2
1
  kon’yunktiv  konstituyentlar  diz’yunksiyalarini 
bildiradi.  Bu  yerda  diz’yunksiya  amallari 
1
)
,...,
,
(
2
1

n
A



  shartni  qanoatlantiruvchi  barcha 
kon’yunktiv konstituyentlarga nisbatan amalga oshiriladi. 
(1) teng kuchlilikni quyidagicha ham yozish mumkin: 
n
n
n
n
n
x
x
x
A
x
x
x
A









...
)
,...,
,
(
)
,...,
,
(
2
1
2
1
2
1
2
1
)
,...,
,
(
2
1


. 
Bu  teng  kuchlilikning  o‘ng  tomonidagi  diz’yunksiya  amallari  mumkin  bo‘lgan  barcha 
n
2 ta 
n
n
x
x
x



...
2
1
2
1
  kon’yunktiv  konstituyentlar  ustida  bajarilishi  ko‘zda  tutilsada,  aslida,  diz’yunksiyalar 
1
)
,...,
,
(
2
1

n
A



  shartni  qanoatlantiruvchi  kon’yunktiv  konstituyentlarga  nisbatan  amalga 
oshiriladi. 
(1)  yozuvni  matematik  analizdagi  funksiyaning  darajali  qatotga  yoyilishi  tushunchsiga 
qiyoslab, 
)
,...,
,
(
2
1
n
x
x
x
A
 formulaning (funksiyaning) qatorga yoyilishi deb atash mumkin
22
. 
Yuqorida  keltirilgan  mulohazalar  asosida 
n ta 
n
x
x
x
,...,
,
2
1
  o‘zgaruvchilarga  bog‘liq, 
tavtologiyadan  farqli  ixtiyoriy 
)
,...,
,
(
2
1
n
x
x
x
A
A 
  formulani  (funksiyani)  quyidagi  MKNShga 
keltirish mumkin: 
n
n
n
A
n
x
x
x
x
x
x
A












...
)
,...,
,
(
2
1
2
1
2
1
0
)
,...,
,
(
2
1
. 
(2) 
(2) teng kuchlilikni 
n
n
n
n
n
x
x
x
A
x
x
x
A















...
)
,...,
,
(
)
,...,
,
(
2
1
2
1
2
1
2
1
)
,...,
,
(
2
1
 
                                                
 

 
 
ko‘rinishda  ham  yozish  mumkin.  Bu  teng  kuchlilikning  o‘ng  tomonidagi  kon’yunksiya  amallari 
mumkin  bo‘lgan  barcha  (
n
2 ta) 
n
n
x
x
x






...
2
1
2
1
  diz’yunktiv  konstituyentlar  ustida  bajarilishi 
ko‘zda tutiladi, ammo, bu yerda kon’yunksiya amallari 
0
)
,...,
,
(
2
1

n
A



 shartni qanoatlantiruvchi 
diz’yunktiv konstituyentlarga nisbatan amalga oshiriladi. 
Shunday  qilib,  chinlik  jadvalidan  foydalanib  (1)  va  (2)  formulalar  vositasida  aynan  chindan  farqli 
istalgan funksiyani MKNSh va aynan yolg‘ondan farqli istalgan 
funksiyani esa MDNSh ko‘rinishida yozish mumkin. 
 
Formulaning chinlik to‘plami 
Formulaning chinlik to‘plami tushunchasi. Ma’lumki, berilgan 
n ta o‘zgaruvchi elementar 
mulohazalar uchun barcha bir-biridan farqli mumkin bo‘lgan qiymatlar satrlari kombinatsiyalari 
n
2 ta 
(ushbu  bobning  1-  paragrafiga  qarang).  Tarkibida 
n ta  o‘zgaruvchilar  ishtirok  etgan  formula  shu 
n
2 ta qiymatlar satrlarining bir qismida 1, qolgan qismida esa 0 qiymatni qabul qiladi. 
1-  t a ’ r i f .  Berilgan  formula  tarkibidagi  elementar  mulohazalarning  qiymatlaridan 
qandaydir tartibda tuzilgan va shu formulaning 1 qiymatiga mos keluvchi barcha kortejlar to‘plami 
formulaning chinlik to‘plami deb ataladi. 
Ravshanki,  tarkibidagi  o‘zgaruvchilarning  soni  qanday  bo‘lishidan  qat’iy  nazar,  aynan 
yolg‘on formulaning chinlik to‘plami bo‘sh () to‘plamdan iboratdir. 
n ta elementar mulohazalarning mumkin bo‘lgan barcha 
n
2
2 ta teng kuchlimas formulalaridan 
C
n
n
2
1
2

tasi qiymatlar satridagi 
n ta qiymatlardan faqat bittasi 1, qolgan (
1

n
)tasi esa 0 bo‘lganda 
1  qiymat  qabul  qiladi.  Shuning  uchun,  bunday  formulalarning  har  biri  bir  elementli  chinlik 
to‘plamiga ega. 
Xuddi  shuningdek, 
n ta  elementar  mulohazalarning  mumkin  bo‘lgan  barcha  teng  kuchlimas 
formulalaridan 
C
n
2
2
tasi qiymatlar satridagi 
n ta qiymatlardan faqat ikkitasi 1, qolgan (
2

n
)tasi esa 0 
bo‘lganda 1 qiymat qabul qiladi. Shu sababli, bunday formulalarning har biri uchun chinlik to‘plam 
ikkita kortejdan tashkil topgan bo‘ladi. 
Shu  usulda  davom  etsak, 
n
2
2 ta  teng  kuchlimas  formulalardan 
C
n
2
3
tasining  har  biri  uch 
elementli  chinlik  to‘plamiga, 
4
2
n
C
tasining  har  biri  to‘rt  elementli  chinlik  to‘plamiga,  va  hokazo, 
n
n
n
C
2
1
2
2


tasining  har  biri  (
1
2 
n
)  elementli  chinlik  to‘plamiga,  bitta  (
1
2
2

n
n
C
)  formula  esa 
n
2 ta 
elementli chinlik to‘plamiga egaligiga ishonch hosil qilamiz. 
Tarkibida 
n ta elementar mulohazalar ishtirok etgan aynan chin formulaga 
mos  chinlik  to‘plamni  universal  to‘plam  (
U
)  deb  olsak,  tarkibida  shu  elementar  mulohazalar 
qatnashgan mumkin bo‘lgan barcha formulalarning har biriga mos chinlik to‘plamlar 
U
 to‘plamning 
qism 
to‘plamlaridan 
iborat 
va 
bu 
U
 
universal 
to‘plam 
qismlari 
soni 
n
n
n
n
n
n
n
n
C
C
C
C
C
2
2
2
1
2
2
2
2
1
2
0
2
2
......







 bo‘ladi. 
Shunday  qilib,  tarkibida 
n ta  elementar  mulohazalar  ishtirok  etgan  mumkin  bo‘lgan  barcha 
formulalar  bilan  ularning  chinlik  to‘plamlari  orasida  o‘zaro  bir  qiymatli  moslik  o‘rnatildi.  Demak, 
barcha o‘zaro teng kuchli formulalarga faqat bitta chinlik to‘plami mos keladi. 

 
 
1-  m i s o l .  Ikkita  (
2

n
) 
x   va 
y
  elementar  mulohazalarning 
y
y
x
x



)
(
  formulasi 
aynan  chindir  (ushbu  bobning  3-  paragrafidagi  1-  misolga  qarang).  Shuning  uchun  berilgan 
formulaning  chinlik  to‘plami 
4
2
2
2


n
  elementli 
)}
1
,
1
(
),
0
,
1
(
),
1
,
0
(
),
0
,
0
{(
  universal  to‘plamdan 
iboratdir. ■ 
2- m i s o l . Tarkibida uchta 
x , 
y
 va 
z  elementar mulohazalar qatnashgan
z
y
x
 
formula qiymatlar satrlarining faqat bittasida (aniqrog‘i, 
1
,
0
,
1
 satrda) 1 qiymat, qolgan ettitasida esa 
0 qiymat qabul qiladi. Shuning uchun, 
z
y
x
 formulaning chinlik to‘plami 
)}
1
,
0
,
1
{(
, ya’ni bitta 
)
1
,
0
,
1
(
 
kortejdan tashkil topgan bo‘ladi. ■ 
3- 
m i s o l . 
Ushbu 
z
y
x
z
y
x
xyz


 
formula 
tarkibida 
uchta 
kortej 
bo‘lgan 
)}
1
,
0
,
1
(
),
0
,
1
,
0
(
),
1
,
1
,
1
{(
 chinlik to‘plamiga egadir. ■ 
Agar  qandaydir 
A
  formula 
P
  chinlik  to‘plamiga  ega  bo‘lsa,  u  holda  “
A
  formula 
P
 
to‘plamda  chin  qiymat  qabul  qiladi”  (yoki,  qisqacha,  “
A
  formula 
P
  to‘plamda  chin”)  deb  ham 
yuritiladi.  Shunga  o‘xshash,  “
A
  formula 
P   to‘plamda  yolg‘on”  deyish  mumkin,  bu  yerda 
P
P
\
U

, ya’ni 
P
 to‘plamning to‘ldiruvchisi. Agar 
A
 formula 
P
 to‘plamda chin bo‘lsa, u holda 
A   formula  P   to‘plamda  chin, 
P
  to‘plamda  esa  yolg‘on  bo‘ladi.  Xuddi  shu  kabi,  aynan  chin 
J
 
formula 
U
  universal  to‘plamda  chin  va 


U
  to‘plamda  yolg‘on  qiymat  qabul  qiladi.  Aynan 
yolg‘on 
J  formula esa, aksincha, 

 to‘plamda chin va 
U


 to‘plamda yolg‘ondir. 
Formulalar  bilan  chinlik  to‘plamlari  orasidagi  yuqorida  ifodalangan  bog‘lanish  mulohazalar 
mantiqiga  oid  masalani  to‘plamlar  nazariyasi  masalasiga  va,  aksincha,  to‘plamlar  nazariyasidagi 
masalani mulohazalar mantiqiga doir masalaga ko‘chirish imkoniyatini beradi. 
3.8.2.  Asosiy  mantiqiy  amallarning  chinlik  to‘plamlari. Chinlik  to‘plamlari  mos  ravishda 
A
 va 
B
 bo‘lgan 
P
 va 
Q  formulalar berilgan bo‘lsin. 
Kon’yunksiyaning chinlik to‘plami. 
P
 va 
Q  formulalar 
Q
P 
 kon’yunksiyasining chinlik 
to‘plami 
B
A 
  bo‘ladi.  Haqiqatdan  ham,  kon’yunksiya  ta’rifiga  asosan, 
Q
P 
  formula 
P
  va 
Q  
formulalarning ikkalasi ham chin bo‘lgandagina chindir. Shuning uchun, 
Q
P 
 formulaning chinlik 
to‘plami 
A
  va 
B
  to‘plamlarning  umumiy  elementlaridan  tuzilgan 
B
A 
  kesishmasidan  iborat 
bo‘ladi.  Demak,  mulohazalar  mantiqidagi  kon’yunksiya  amaliga  (
   belgiga)  to‘plamlar 
nazariyasidagi kesishma amali (   belgi) mos keladi (I bobning 2- paragrafidagi 2- shaklga qarang). 
4- m i s o l . 
z
y
x
C 
 va 
z
y
x
z
y
x
xyz
D



 formulalarning chinlik to‘plamlari, mos 
ravishda, 
)}
1
,
0
,
1
{(

R
  va 
)}
1
,
0
,
1
(
),
0
,
1
,
0
(
),
1
,
1
,
1
{(

S
  bo‘lgani  uchun  (2-  va  3-  misollarga  qarang) 
D
C 
 kon’yunksiyaning chinlik to‘plami 
)}
1
,
0
,
1
{(

S
R 
 bo‘ladi. ■ 
Diz’yunksiyaning  chinlik  to‘plami. 
P
 va 
Q   formulalar 
Q
P 
 diz’yunksiyasining chinlik 
to‘plami 
B
A 
  bo‘ladi.  Haqiqatdan  ham,  diz’yunksiya  ta’rifiga  asosan, 
Q
P 
  formula 
P
  va 
Q  
formulalarning kamida bittasi chin bo‘lgandagina chindir. Demak, 
B
A 
 to‘plamda 
Q
P 
 formula 
chindir.  Shunday  qilib, 
Q
P 
  formulaning  chinlik  to‘plami 
A
  va 
B
  to‘plamlarning  barcha 
elementlaridan,  ularni  takrorlamasdan,  tuzilgan 
B
A 
  birlashmasidan  iborat  bo‘ladi.  Demak, 
mulohazalar  mantiqidagi  diz’yunksiya  (
 )  amaliga  to‘plamlar  nazariyasidagi  birlashma  (  )  amali 
mos keladi (I bobning 2- paragrafidagi 1- shaklga qarang). 
5-  m i s o l .  4-  misolda  aniqlangan 
C
 va 
D
 formulalar diz’yunksiyasi 
D
C 
 uchun chinlik 
to‘plam 
)}
1
,
0
,
1
(
),
0
,
1
,
0
(
),
1
,
1
,
1
{(

S
R 
 bo‘ladi. ■ 

 
 
Implikasiyaning  chinlik  to‘plami. 
P
  va 
Q   formulalar 
Q
P 
 
implikasiyaning chinlik to‘plamini topamiz. 
P   formulaning chinlik to‘plami  A  va  Q  formulaning 
chinlik  to‘plami 
B
  bo‘lgani  uchun, 
Q
P
Q
P



  teng  kuchlilikka  ko‘ra, 
Q
P 
  formulaning 
chinlik to‘plami 
B
A

 bo‘ladi. 1- shaklda tasvirlangan 
U
 to‘plamning bo‘yalmagan qismi 
Q
P 
 
implikasiyaning chinlik to‘plamiga mos keladi. 
6-  m i s o l .  4-  misolda  aniqlangan 
C
  va 
D
  formulalar  tarkibida  uchtadan 
x , 
y
  va 
z  
elementar  mulohazalar  qatnashgani  uchun, 
D
C 
  implikasiyasining  chinlik  to‘plamini  topish 
maqsadida, dastlab 
)}
0
,
0
,
0
(
),
1
,
0
,
0
(
),
0
,
1
,
0
(
),
1
,
1
,
0
(
),
0
,
0
,
1
(
),
1
,
0
,
1
(
),
0
,
1
,
1
(
),
1
,
1
,
1
{(

U
 
universal  to‘plamni  tuzamiz. 
C
  formulaning  chinlik  to‘plami 
)}
1
,
0
,
1
{(

R
  bo‘lgani  uchun 
C
 
formulaning chinlik to‘plami 
)}
0
,
0
,
0
(
),
1
,
0
,
0
(
),
0
,
1
,
0
(
),
1
,
1
,
0
(
),
0
,
0
,
1
(
),
0
,
1
,
1
(
),
1
,
1
,
1
{(
\


R
R
U
 
bo‘ladi.  Endi 
R   to‘plam  bilan 
B
  formulaning 
)}
1
,
0
,
1
(
),
0
,
1
,
0
(
),
1
,
1
,
1
{(

S
  chinlik  to‘plami 
birlashmasini  aniqlasak, 
U

S
R 
,  ya’ni 
D
C 
  formulaning  chinlik  to‘plami  universal 
to‘plamdan iborat bo‘ladi. Bu yerdan 
J
z
y
x
z
y
x
xyz
z
y
x
D
C






)
(
 xulosani hosil qilamiz. ■