Article_MPCS.DVI


Mathematical Problems of Computer Science 45, 14{18, 2016.

Asymptotic E stimates of the N umber of Solutions of

Systems of E quations with P ar tial B oolean Functions

E d u a r d V . Y e g h ia z a r ya n

Yerevan State University

e-mail: eduardyeg@mail.ru

Abstract

In this paper a class of systems of equations with partial (not everywhere de¯ned)
Boolean functions is investigated. The asymptotic estimate of the number of solutions
of systems of equations is determined for the \typical" case.

Keywords: Boolean equations, Solution of equation, Partial boolean functions.

1 . In t r o d u c t io n

Ma n y p r o b le m s o f d is c r e t e m a t h e m a t ic s , in c lu d in g p r o b le m s wh ic h a r e t r a d it io n a lly c o n -
s id e r e d t o b e c o m p le x, le a d t o t h e s o lu t io n s o f t h e s ys t e m s o f B o o le a n e qu a t io n s o f t h e
fo r m ½

fi ( x1; : : : ; xn ) = 1 ;
i = 1 ; :::; l;

( 1 )

o r t o t h e r e ve a l o f t h o s e c o n d it io n s , u n d e r wh ic h t h e s ys t e m ( 1 ) h a s a s o lu t io n . In g e n e r a l
p r o b le m o f r e a liz in g wh e t h e r t h e s ys t e m ( 1 ) h a s a s o lu t io n o r n o t is N P -c o m p le t e [1 ]. Th e r e -
fo r e , it is o ft e n n e c e s s a r y t o c o n s id e r s p e c ia l c la s s e s o f t h e s ys t e m s o f e qu a t io n s , u s in g t h e ir
s p e c ī c it y, o r e xp lo r e a n u m b e r o f s o lu t io n s fo r t h e " t yp ic a l" c a s e .

2 . D e ¯ n it io n s a n d R e s u lt Fo r m u la t io n

L e t fM ( n) g1n=1 b e t h e c o lle c t io n o f s e t s , s u c h t h a t jM ( n) j ! 1 wh e n n ! 1, ( jMj is t h e
p o we r o f t h e s e t M ) , a n d M s ( n ) is t h e s u b s e t o f a ll t h e e le m e n t s fr o m M ( n) , wh ic h h a ve
t h e p r o p e r t y S. W e s a y, t h a t a lm o s t a ll t h e e le m e n t s o f t h e s e t M ( n) h a ve t h e p r o p e r t yS, if¯̄
M S ( n)

¯̄
= jM ( n) j ! 1 , wh e n n ! 1.

W e d e n o t e b y Sn;l t h e s e t o f a ll t h e s ys t e m s o f t h e fo r m ( 1 ) , wh e r e fi ( x1; : : : ; xn ) ; i =
1 ; :::; l¡ p a ir wis e d i®e r e n t B o o le a n fu n c t io n s o f va r ia b le s x1; x2; :::; xn. It is e a s y t o s e e , t h a t
jSn;lj = Cl22n .

L e t fM ( n ) g1
n=1

b e t h e c o lle c t io n o f s e t s , s u c h t h a t jM ( n) j ! 1 wh e n n ! 1, ( jMj is
t h e p o we r o f t h e s e t M ) , a n d M s ( n) is t h e s u b s e t o f a ll t h e e le m e n t s fr o m M ( n) , wh ic h h a ve
t h e p r o p e r t y S. W e s a y, t h a t a lm o s t a ll t h e e le m e n t s o f t h e s e t M ( n) h a ve t h e p r o p e r t y S,
if

¯̄
M S ( n)

¯̄
= jM ( n) j ! 1 , wh e n n ! 1.

1 4



E. Yeghiazaryan 1 5

W e d e n o t e b y Sn;l t h e s e t o f a ll t h e s ys t e m s o f t h e fo r m ( 1 ) , wh e r e fi ( x1; : : : ; xn ) ; i =
1 ; :::; l¡ p a ir wis e d i®e r e n t B o o le a n fu n c t io n s o f va r ia b le s x1; x2; :::; xn. It is e a s y t o s e e , t h a t
jSn;lj = Cl22n .

L e t B = f 0 ; 1 g,Bn = f ~®= ~® = ( ®1; ®2; :::; ®n ) ; ®i 2 B; 1 · i · ng. Th e ve c t o r ~®i =
( ®1; ®2; :::::; ®n ) 2 Bn is c a lle d a s o lu t io n o f ( 1 ) , if

½
fi ( ®1; ®2; :::::; ®n ) = 1 ;
i = 1 ; :::; l:

W e d e n o t e b y t ( S ) t h e n u m b e r o f t h e s o lu t io n s o f t h e s ys t e m S. In [2 ,3 ] t h e a s ym p t o t ic s
o f t h e n u m b e r o f t h e s o lu t io n s t ( S ) is s h o wn fo r a lm o s t a ll t h e s ys t e m s S o f t h e s e t Sn;l t h e
wh o le r a n g e o f p a r a m e t e r l c h a n g e s , wh e n n ! 1.

In t h is wo r k a c la s s o f s ys t e m s o f e qu a t io n s wit h p a r t ia l ( n o t e ve r ywh e r e d e ¯ n e d ) B o o le a n
fu n c t io n s is c o n s id e r e d . Th e a s ym p t o t ic b e h a vio r o f t h e n u m b e r o f s o lu t io n s o f s ys t e m s o f
e qu a t io n s is fo u n d fo r a \ t yp ic a l" c a s e .

P a r t ia l B o o le a n fu n c t io n f ( x1; : : : ; xn ) o n t h e ve c t o r ~® = ( ®1; ®2; :::::; ®n ) 2 Bn o r is n o t
d e ¯ n e d , o r is 0 o r 1 . L e t Q ( n) d e n o t e t h e s e t o f a ll p a r t ia l B o o le a n fu n c t io n s , d e p e n d in g o n
va r ia b le s x1; x2; :::; xn. Ob vio u s ly, jQ ( n) j = 3 2

n
.

L e t R( n; l ) d e n o t e t h e s e t o f a ll s ys t e m s o f l e qu a t io n s o f t h e fo r m ( 1 ) , wh e r e
fi ( x1; : : : ; xn ) ; i = 1 ; :::; l a r e p a ir wis e d i®e r in g p a r t ia l B o o le a n fu n c t io n s o f t h e va r ia b le s
x1; x2; :::; xn ( fi 6= fj if i 6= j c o n d it io n p e r s is t s ) . It is e a s y t o s e e , t h a t jRn;lj = Cl32n .

Fo r t h e n u m b e r s o f t h e s o lu t io n s t( S ) o f a lm o s t a ll t h e s ys t e m s S o f t h e s e t R ( n; l ) t h e
fo llo win g s t a t e m e n t is t r u e :

T heor em 1:
1. If n¡` lo g 3 ! 1 when n ! 1, then for almost all the systems Sof the set R( n; l ) occurs
t ( S ) » 2 n 3 ¡l.
2. If n ¡ ` lo g 3 ! ¡1 when n ! 1, then almost all the systems Sof the set R( n; l ) have
no solutions.
3. If n¡` lo g 3 is restricted when n ! 1, then for almost all the systems of the set R ( n; l; m )
the number of the solutions t ( S ) is restricted from above by an arbitrary function '( n) , sat-
isfying the condition '( n) ! 1, when n ! 1.

H e r e a n d fu r t h e r f ( n) » g ( n) ; if f ( n) =g ( n) ! 1 wh e n n ! 1, f ( n) = o ( g ( n) ) if
f ( n) =g ( n) ! 0 wh e n n ! 1. E ve r ywh e r e t h e lo g is r e g a r d e d a s a lo g a r it h m t o t h e b a s e 2 .

3 . P r o o f o f Th e o r e m 1

Th e fo llo win g kn o wn o r e a s ily c h e c kin g in e qu a lit ie s h o ld :
1 ) Th e ¯ r s t Ch e b ys h e v in e qu a lit y ( [4 ]) . L e t t h e r a n d o m va r ia b le » t a ke t h e n o n -n e g a t ive
va lu e s a n d h a ve m a t h e m a t ic a l e xp e c t a t io n M». Th e n fo r a n y t > 0 r ig h t ly

P ( » ¸ t) · M»=t:

2 ) Th e s e c o n d Ch e b ys h e v in e qu a lit y ( [4 ]) . L e t t h e a b o ve r a n d o m va r ia b le » h a ve a d is p e r s io n
D». Th e n fo r a n y t > 0 r ig h t ly

P ( j» ¡ M »j ¸ t) · D»=t2:



1 6 Asymptotic Estimates of the Number of Solutions of Systems of Equations with Partial Boolean Functions

3 ) Fo r a n y x > 1 µ
1 ¡ 1

x

¶x
< e¡1 :

4 ) Fo r a n y n a t u r a l n a n d m2 = o( n)

C
m
n »

nm

m!
:

5 ) Fo r a n y n a t u r a l n a n d 1 · m · n

C
m
n <

³ en
m

´m
:

6 ) L e t b ( k; n; p ) = C
k
n p

kqn¡k, wh e r e 0 < p; q < 1 ; p + q = 1 . Th e n fo r r > np

n¡rX

j=0

b( r + j; n; p) < b( r; n; p) ( r + 1 ) q= ( r + 1 ¡ ( n + 1 ) p)

( t h e e s t im a t e o f t h e \ t a il" o f t h e b in o m ia l d is t r ib u t io n ( [4 ]) ) .

L e t S b e a s ys t e m in R ( n; l ) . A r r a n g in g ( t r a n s p o s it io n s b y a ll t h e va r ia t io n s ) t h e e qu a -
t io n s in S , we o b t a in ! n e w s ys t e m s , d i®e r in g fr o m e a c h o t h e r b y t r a n s p o s it io n o f t h e e qu a -
t io n s . Th u s , fr o m t h e s e t R ( n; l ) we o b t a in a n e w s e t R0 ( n; l ) o f o r d e r e d a n d n o n r e p e t it ive
( n o t c o n t a in in g t h e e qu iva le n t e qu a t io n s ) s ys t e m s . It 's e vid e n t t h a t

jR0 ( n; l ) j = jR ( n; l ) jl!: ( 2 )
L e t a lm o s t a ll t h e s ys t e m s o f t h e s e t R0 ( n; l ) h a ve t h e p r o p e r t y E , wh ic h is in va r ia n t fo r

a n y t r a n s p o s it io n o f t h e e qu a t io n s o f t h e s ys t e m . It 's e a s y t o s e e , t h a t a lm o s t a ll t h e s ys t e m s
o f t h e s e t R( n; l ) will a ls o h a ve t h e p r o p e r t y E . Th u s , fo r t h e p r o o f o f t h e Th e o r e m it will b e
e n o u g h t o c o n s id e r t h e s e t R0 ( n; l ) in s t e a d o f R ( n; l ) .

N e xt , we d e n o t e b y R
00
( n; l ) e xp a n s io n o f t h e s e t R0 ( n; l ) - in t h e s ys t e m s fr o m R0 ( n; l )

a llo we d a s a m e e qu a t io n s . It is e a s y t o s e e , t h a t

jR00 ( n; l ) j = 3 l2n : ( 3 )

Fr o m ( 2 ) , ( 3 ) a n d 4 ) we o b t a in , t h a t

jR0 ( n; l ) j
jR00 ( n; l ) j =

l!Cl
32

n

3 l2
n ! 1 ;

wh e n l2 = o
¡
3 2

n ¢
( n ! 1 ) . Th u s , if l2 = o

¡
3 2

n ¢
, a n y a s s e r t io n fo r a lm o s t a ll s ys t e m s o f

t h e s e t R00 ( n; l ) is t r u e fo r a lm o s t a ll t h e s ys t e m s o f t h e s e t R0 ( n; l ) .
W e c o n s id e r R00 ( n; l ) a s a s p a c e o f e ve n t s , wh e r e e ve r y e ve n t S 2 R00 ( n; l ) t a ke s p la c e

wit h t h e p r o b a b ilit y 1 =jR00 ( n; l ) j = 3 ¡l2n .
Co n s id e r t h e r a n d o m va lu e »S ( ~®) , wh ic h is c o n n e c t e d wit h S 2 R0 ( n; l ) a s fo llo ws :

»S ( ~®) = 1 ; if ~® is t h e s o lu t io n o f t h e s ys t e m S , a n d »S ( ~® ) = 0 in a n o t h e r c a s e .
Fr o m t h e d e ¯ n it io n it fo llo ws , t h a t t h e n u m b e r o f t h e s ys t e m S 2 R0 ( n; l ) , fo r wh ic h ~® is

a s o lu t io n , e qu a l t o 3 l(2
n¡1). Fr o m t h is a n d ( 3 ) it fo llo ws , t h a t P ( »S ( ~®) = 1 ) = 3

¡l.



E. Yeghiazaryan 1 7

Co n s id e r a n o t h e r r a n d o m va lu e v =
P

~®2Bn
»S ( ~® ) . R a n d o m va lu e v h a s a b in o m ia l d is t r i-

b u t io n , b e c a u s e
p ( v = j ) = C

j
2n 3

¡lj ( 1 ¡ 3 ¡l ) 2n¡j :
H e n c e , Mv = 2 n 3 ¡l a n d Dv = 2 n 3 ¡l

¡
1 ¡ 3 ¡l

¢
, wh e r e Mv a n d Dv a r e t h e m a t h e m a t ic a l

e xp e c t a t io n a n d d is p e r s io n o f t h e r a n d o m va lu e v, a c c o r d in g ly.
L e t n ¡ ` lo g 3 ! 1 wh e n n ! 1. It m e a n s , t h a t M v = 2 n 3 ¡l = 2 n¡l log 3 ! 1

wh e n n ! 1. U s in g t h e Ch e b is h e v's in e qu a t io n 2 ) wh e n t = Mv=
p

n ¡ l lo g 3 , we o b t a in ,
P

¡
jv ¡ M vj ¸ Mv=

p
n ¡ l lo g 3

¢
· ( n ¡ l lo g 3 ) ( 1 ¡ 3 ¡l ) = 2 n¡l log 3 ! 0 wh e n n ! 1. H e n c e

a n d fr o m t h e d e ¯ n it io n o f r a n d o m va lu e v it fo llo ws , t h a t a lm o s t a ll t h e s ys t e m s o f t h e s e t
R00 ( n; l ) h a ve t h e n u m b e r o f s o lu t io n s , wh ic h a s ym p t o t ic a lly e qu a ls Mv.

S in c e u n d e r n ¡ ` lo g 3 ! 1 is p e r fo r m e d l2 = o
¡
3 2

n ¢
, a lm o s t a ll t h e s ys t e m s o f t h e

s e t R( n; l ) h a ve a ls o n u m b e r o f s o lu t io n s , a s ym p t o t ic a lly e qu a l t o M v = 2 n 3 ¡l. Th e ¯ r s t
s t a t e m e n t o f t h e Th e o r e m is p r o ve d .

L e t n ¡ ` lo g 3 ! ¡1 wh e n n ! 1. Th e n Mv = 2 n 3 ¡l = 2 n¡l log 3 ! 0 ( n ! 1) .
U s in g Ch e b is h e v's ¯ r s t in e qu a t io n wh e n t =l, we o b t a in P ( v ¸ 1 ) ! 0 wh e n n ! 1 a n d
t h e r e fo r e , P ( v = 0 ) ! 1 wh e n n ! 1. H e n c e it fo llo ws , t h a t a lm o s t a ll t h e s ys t e m s S
o f t h e s e t R00 ( n; l ) h a ve n o s o lu t io n . Th e r e fo r e , wh e n l2 = o

¡
3 2

n ¢
t h e s e c o n d s t a t e m e n t

o f t h e Th e o r e m is p r o ve d . It is e a s y t o s e e , t h a t fo r t h e g r e a t e r va lu e s o f t h e p a r a m e t e r l
t h e s t a t e m e n t o f t h e Th e o r e m a ls o h o ld s ( t h e n u m b e r o f s o lu t io n s o f t h e s ys t e m d o e s n o t
in c r e a s e wit h t h e n u m b e r o f e qu a t io n s ) .

N o w le t n ¡ ` lo g 3 b e r e s t r ic t e d , wh e n n ! 1. Th e n Mv = 2 n 3 ¡l = 2 n¡l log 3 is a ls o
r e s t r ic t e d wh e n n ! 1. U s in g t h e in e qu a t io n s 6 ) , 5 ) a n d 3 ) , we o b t a in

P ( v > r ) =
2n¡rX

i=0

Cr+i2n 3
¡l(r+i) ( 1 ¡ 3 ¡l ) 2n¡r¡i · Cr2n 3 ¡lr ( 1 ¡ 3 ¡l ) 2

n¡r£

£ ( r + 1 )
¡
1 ¡ 3 ¡l )

± ¡
r + 1 ¡ ( 2 n + 1 ) 3 ¡l

¢
· ( e 2 n 3 ¡lr¡1 ) r ·

µ
eM v

r

¶
! 0 ;

wh e n r ! 1 , b e c a u s e Mv is r e s t r ic t e d . Th e r e fo r e , fo r a lm o s t a ll t h e s ys t e m s o f t h e
s e t R00 ( n; l ) t h e t h ir d s t a t e m e n t o f t h e Th e o r e m h o ld s . S in c e n ¡ ` lo g 3 is r e s t r ic t e d , t h e n
l2 = o

¡
3 2

n ¢
is p e r fo r m e d , a n d , t h e r e fo r e , fo r a lm o s t a ll t h e s ys t e m s o f t h e s e t R ( n; l ) t h e

t h ir d s t a t e m e n t o f t h e Th e o r e m h o ld s . Th e o r e m is c o m p le t e ly p r o ve d .

Refer ences

[1 ] M. Ge r i a n d D . Jo h n s o n , Computers and Intractability, ( In R u s s ia n ) , Mo s c o w, Mir ,
1 9 8 2 .

[2 ] E . V . Y e g h ia z a r ya n , \ Me t r ic p r o p e r t ie s o f s ys t e m s o f B o o le a n e qu a t io n s " , D AN Arme-
nian SSR ,( In R u s s ia n ) , vo l. 7 2 , n o .2 , p p . 6 7 { 7 2 , 1 9 8 1 .

[3 ] E . V . Y e g h ia z a r ya n , \ E s t im a t e s r e la t e d t o t h e n u m b e r o f s o lu t io n s o f B o o le a n e qu a -
t io n s " , Coll. Tasks of Cybernetics. Combinatorial analysis and graph theory, ( In R u s -
s ia n ) Mo s c o w, p p . 1 2 4 { 1 3 0 , 1 9 8 0 .

[4 ] W . Fe lle r , An Introduction to P robability Theory and Its Applications, ( In R u s s ia n ) , vo l.
1 , Mo s c o w, Mir , 1 9 7 6 .



1 8 Asymptotic Estimates of the Number of Solutions of Systems of Equations with Partial Boolean Functions

Submitted 15.11.2015, accepted 22.01.2016

سëݳÏÇ µáõÉÛ³Ý ýáõÝÏódzݻñáí ѳí³ë³ñáõÙÝ»ñÇ
ѳٳϳñ·»ñÇ ÉáõÍáõÙÝ»ñÇ ù³Ý³ÏÇ ³ëÇÙåïáïÇÏ

·Ý³Ñ³ï³Ï³ÝÝ»ñ

¾. ºÕdz½³ñÛ³Ý

²Ù÷á÷áõÙ

îñíáõÙ »Ý Ù³ëݳÏÇ (áã ³Ù»ñáõñ»ù áñáßí³Í) µáõÉÛ³Ý ýáõÝÏódzݻñÇó ϳ½Ùí³Í
ѳí³ë³ñáõÙÝ»ñÇ Ñ³Ù³Ï³ñ·»ñÇ ÉáõÍáõÙÝ»ñÇ ù³Ý³ÏÇ ³ëÇÙåïáïÇÏ ·Ý³Ñ³ï³Ï³ÝÝ»ñ
§ïÇåÇϦ ¹»åùÇ Ñ³Ù³ñ:

Àñèìïòîòè÷åñêèå îöåíêè ÷èñëà ðåøåíèé ñèñòåì óðàâíåíèé
ñ ÷àñòè÷íûìè áóëåâûìè ôóíêöèÿìè

Ý. Åãèàçàðÿí

Àííîòàöèÿ

Îïðåäåëÿþòñÿ àñèìïòîòè÷åñêèå îöåíêè ÷èñëà ðåøåíèé ñèñòåì óðàâíåíèé ñ
÷àñòè÷íûìè (íå âñþäó îïðåäåëåííûìè) áóëåâûìè ôóíêöèÿìè äëÿ ”òèïè÷íîãî”
ñëó÷àÿ.