“O’zbekiston temir yo’llari” daтk toshkent temir yo’l muhandislari instituti

   Teorema.  Mulohazalar  algebrasining  har  bir  formulasiga  birorta 

Bullfunksiyasi  mos keladi. 

    Misol. Barch ikki  o’zgaruvchili Bull funksiyalarini  yozing. 

Yechish.   Shartga  ko’ra n=2 bo’lgani uchun  bu funksiyalar  soni o’n oltita. . 

№ 

 

Funksiyaning 

qiymati. 

Funksiyaga  mos 

keluvchi  formula. 

1. 

1 

f=0000 

f=0 

2. 

2 

f=0001 

f=x

1

x

2

 

3. 

3 

f=0010 

f=

2

1

x

x

 

4. 

4 

f=0011 

f=x

1

 

5. 

5 

f=0100 

f=

2

1

х

х

 

6. 

6 

f=0101 

f=x

2

 

7. 

7 

f=0110 

f=x

1

x

2

 

8. 

8 

f=0111 

f=x

1

x

2

 

9. 

9 

f=1000 

f=

2

1

x

x

 

10 

f=1001 

f=

2

1

x

x

 

11 

f=1010 

f=

2

x

 

12 

f=1011 

f=

2

1

х

х

 

13 

f=1100 

f=

1

x

 

14 

f=1101 

f=x

1

x

2

 

15 

f=1110 

f=

2

1

x

x

 

16 

f=1111 

f=1 

28 

 

 

    Teorema.  Aytaylik    f(x

1

,  x

2

,  …,  x

k

)  k-o’rinli  Bull  funksiyasi 

bo’lsin.Agar  f  aynan  nolga  teng  bo’lmasa  uni  ifodalovchi  xuddi  shu 

ro’yxatdagi  o’zgaruvchilardan  tuzilgan  va  bu  ro’yxatga  nisbatan 

MDNShda  bo’lgan  F  formula  mavjud.  F  formula  diz’yunktiv  hadlari  o’rni 

almashishi  aniqligida yagonadir   

 Teorema.  Aytaylik    f(x

1

,  x

2

, …, x

k

)  k-o’rinli  Bull  funksiyasi  bo’lsin.Agar 

f  aynan  nolga  teng  bo’lmasa  uni  ifodalovchi  xuddi  shu  ro’yxatdagi 

o’zgaruvchilardan  tuzilgan  va  bu  ro’yxatga  nisbatan  MKNShda  bo’lgan  F 

formula  mavjud.  F  formula  kon’yunktiv  hadlari  o’rni  almashishi  aniqligida 

yagonadir   

    Yuqorida  aytilgani  bo’yich  Bull  funksiyalari  uchun  MDNSh  va  MKNSh 

yozish qoidalari o’zdarmaydi. 

   Misol.  Berilgan  f(x

1

,  x

2

,  x

3

)=  00101110  Bull  funksiyasi  uchun  MKNSh 

va MDNSh  yozing. 

Yechish.Funksiyaning  qiymatlari jadvalini tuzamiz. 

№  x

1

  x

2

  x

3

  f(x

1

,  x

2

, x

3

) 

0 

0 

0 

0 

0 

1 

0 

0 

1 

0 

2 

0 

1 

0 

1 

3 

0 

1 

1 

0 

4 

1 

0 

0 

1 

5 

1 

0 

1 

1 

6 

1 

1 

0 

1 

7 

1 

1 

1 

0 

MKNSh  (0): № 0, 1, 3, 7 

.

)

,

,

(

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f

 

MDNSh  (1): № 2, 4, 5, 6 

.

,

,

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f

 

Masalalar. 

 1.Berilgan 

  va 

  formulalarning  rostlik  jadvalini  tuzing  va  ularning 

ekvivalentligini  aniqlang: 

1)  

y

x

z

y

y

x

,              

x

z

&

y

; 

2)  

z

y

x

y

x

,  

    

 

)

z

x

(

y

 

3)  

z

y

z

y

x

,      

 

    

y

x

z

y

x

; 

4)  

z

y

x

|

z

~

x

y

x

,     

          

z

x

z

y

x

; 

5)  

z

y

x

y

z

~

x

z

y

x

,    

y

x

&

z

&

y

x

. 

    2.  Berilgan  formulalarning  rostlik  jadvalini  tuzing  va  ularning 

ekvivalentliklarni isbotlang: 

29 

 

1) 

y

y

x

y

x

; 

2) 

x

y

&

y

x

y

~

x

; 

3) 

y

|

y

|

x

|

x

|

y

|

y

|

x

|

x

y

x

; 

4) 

z

x

~

y

x

z

~

y

x

; 

5) 

x

~

z

&

x

~

y

&

x

z

~

y

&

x

; 

    3. V  va  U   formulalar ekvivakentligini  teng  kuchlilik  formulalaridan 

foydalanib  isbotlang: 

1)

y

x

~

y

x

y

x

V

, 

 

 

        

y

x

y

x

U

; 

2)

z

y

x

~

z

y

x

y

x

V

,  

        

z

y

y

x

U

; 

3)

z

y

x

z

y

x

V

,   

 

        

x

z

y

x

U

4)

y

x

z

y

~

x

z

~

x

y

x

V

,    

x

z

y

x

U

5)

x

z

y

y

x

z

y

x

V

, 

       

x

y

y

x

U

.

 

  4. Ushbu  funksiyalar  uchun  MKNSh  yozing: 

1))

)

(

)

x~

(

f

11001011

3

, 

 

 

 

 

);

(

)

x~

(

g

1011

2

 

2)

)

(

)

x~

(

f

10101100

3

,  

 

 

 

);

(

)

x~

(

g

1000

2

 

3)

)

(

)

x~

(

f

00110010

3

,  

 

 

 

);

(

)

x~

(

g

0110

2

 

4)

)

(

)

x~

(

f

100011

0110110111

4

,   

 

);

(

)

x~

(

g

01100111

3

 

5)

)

(

)

x~

(

f

011011

1111110100

4

, 

 

 

);

(

)

x~

(

g

1001

2

 

5. Ushbu  funksiyalar  uchun  MDNSh  yozing: 

1)

);

(

)

x~

(

f

01010001

3

2)

);

(

)

x~

(

f

01111000

3

3)

);

(

)

x~

(

f

10001111

3

 

4)

);

(

)

x~

(

f

000010

0100100011

4

5)

);

(

)

x~

(

f

110001

1000011100

4

 

6)

);

(

)

x~

(

f

010011

1100100010

4

 

6. Ushbu  funksiyalar  uchun  MKNSh  yozing: 

1)

);

(

)

x~

(

f

01011101

3

 

2)

);

(

)

x~

(

f

00101110

3

 

3)

);

(

)

x~

(

f

110011

0101111101

4

).

(

)

x~

(

f

100101

0110111011

4

 

7. Teng  kuchlilik  formulalaridan  foydalanib  berillgan formula  uchun 

DNSh  yozing: 

 1)

);

x

x

x

(

)

x

x

x

(

)

x~

(

f

3

2

1

3

2

1

3

 

2)

);

x

x

x

(

)

x

x

x

(

)

x~

(

f

2

3

1

3

2

1

3

 

3)

));

x

x

(

x

x

(

)

x

~

x

(

)

x~

(

f

3

2

3

1

2

1

3

 

4)

);

x

)

x

|

x

((

|

)

x

x

x

(

)

x~

(

f

3

2

1

3

2

1

3

 

30 

 

5)

));

x

x

(

|

x

(

)

x

x

(

x

)

x~

(

f

3

2

1

3

2

1

3

 

8. Teng  kuchlilik  formulalaridan  foydalanib  berillgan formula  uchun 

KNSh  yozing: 

1)

1

2

1

2

x

(

)

x

x

((

)

x~

(

f

1

2

x

(

))

x

|

2

~ x

));

x

x

(

2

1

 

2)

)))

x

x

(

x

(

x

(

x

x

)

x~

(

f

2

1

2

1

2

1

2

; 

3)

);

x

x

x

(

x

x

x

x

)

x~

(

f

3

2

1

3

2

2

1

3

 

 

4)

;

x

x

x

))

x

x

(

x

(

)

x~

(

f

3

2

1

3

2

1

3

 

5)

);

x

x

x

(

))

x

x

(

~

x

(

)

x~

(

f

3

1

2

3

2

1

3

 

9. Ushbu 

x

A

x

A

A

 va  

   formulalardan   foydalanib 

berillgan formula  uchun  MDNSh  yozing:   

1)

;

x

x

x

)

x~

(

f

3

2

1

3

 

2)

;

x

x

x

x

x

x

)

x~

(

f

3

1

3

2

2

1

3

 

3)

;

x

x

x

x

x

)

x~

(

f

3

2

3

2

1

3

 

4)

;

)

~

(

3

3

2

2

1

3

x

x

x

x

x

x

f

 

5)

;

x

x

x

x

)

x~

(

f

3

1

2

1

3

.  Ushbu 

)

x

A

(

)

x

A

(

A

 и 

A

A

A

   

formulalardan   foydalanib  berillgan formula  uchun  MDNSh  yozing: 

1)

;

x

)

x

x

(

)

x~

(

f

3

2

1

3

 

2)

;

x

)

x

x

(

)

x

x

(

)

x~

(

f

3

3

2

2

1

3

 

3)

);

x

x

(

)

x

x

(

)

x

x

(

)

x~

(

f

3

2

3

1

2

1

3

 

4)

);

x

x

(

)

x

x

(

x

x

)

x~

(

f

3

1

3

1

2

1

3

 

5)

);

x

x

(

)

x

x

(

x

)

x

x

(

)

x~

(

f

3

2

3

1

2

2

1

3

 

 

11. Distributivlik qonuni 

xz

xy

)

z

y

(

x

 va 

,

x

x

x

,

x

x

0

,

A

0

0

,

A

A 0

  

A

A B

A

 teng  kuchlilik 

formulalaridan  foydalanib DNSh  yozing  vf rele kontakt  sxemasini  chizing: 

1)

);

x

x

(

)

x

x

(

)

x

x

(

)

x~

(

f

3

2

3

1

2

1

3

 

2)

);

x

x

(

)

x

x

x

(

x

)

x~

(

f

3

2

3

2

1

1

3

 

3)

);

x

x

x

(

)

x

x

(

)

x

x

(

)

x~

(

f

3

2

1

3

1

2

1

3

 

4)

);

x

x

(

)

x

x

(

)

x

x

(

)

x

x

(

)

x~

(

f

3

2

3

1

3

1

2

1

3

 

5)

);

x

x

x

(

)

x

x

x

(

)

x

x

x

(

)

x~

(

f

3

2

1

3

2

1

3

2

1

3