Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез

~ 168 ~ 
 
3-теорема            Айталық  дизъюнкция  тізбегінен  құралған  логикалық  формула  берілген 
болсын. Онда 
 
{A
i
}
V
m
 ≡ {A
j
*}
Σ
m1 
 ауыстыру  арқылы  алынған  Жегалкин  полиномы  түріндегі  тізбекті  өрнек  кезектегідей 
шарттар бойынша жіктеледі: 
 
{A
j
*}
Σ
m1
 = Σ (A
i1
σi1
 A
i2
σi2 
…A
ik
σik
 ), 
және   L
Σ
V
(m) =
і=1
Σ
m
 (i . C
m
i
),       K
Σ
V
(m) = 2
m
-1. 
күрделік бағаларға ие болады. 
Дәлелдеу.    B
k
  және  e
k
  арқылы    VA
i
  өрнекті  Жегалкин  полиномына  ауыстырғаннан 
кейінгі формуланы және осы формуладағы элементар конъюнкциялар санын белгілейміз.                                    
Мұнда k = 2 және k = 3 үшін формулаларды өте оңай табамыз: 
 
A
1
 v A
2
 = A
1
A
2
 A
1
A
2
 = B
2
, e
2
 = 3; 
 
A
1
 v A
2
 v A
3
 = B
2
A
3 
 B
2
 A
3
 = A
1
A
2
A
3
 A
1
A
3
 A
2
A
3
 A
1
A
2
A
1
A
2
A
3
 = B
3
,  
e
3
=e
2
+e
2
+1=7.    
Айталық k = n+1 болсын.   Онда 
 
A
1
 v A
2
 v…v A
n
 v A
n+1
 = B
n
 A
n+1
 B
n
A
n+1
,    l
n+1
 = 2l
n
 + 1 
болады. 
 
Егер B
k 
( k = 1,…, n+1)  өрнек үшін элементар конъюнкциялар  санын біртіндеп 
есептесек кезектегі реттелген сандарды аламыз: 
 
K = 1, l
1
 = 1 = 2
1
 – 1, 
 
K = 2, l
2
 = 2l
1
+1 = 3 = 2
2 
- 1, 
 
K = 3, l
3
 = 2l
2
+1 = 7 = 2
3
 – 1, 
 
- - - - - - - - - - - - - - - - - - - -  
 
K = n+1, l
n+1
 = 2l
n+1
 = 2
n+1
-1. 
Сондықтан m айнымалы үшін 
 
l
m
 = K
Σ
V
(m) = 2
m
 – 1. 
теңдік ақиқат екендігін көру қиын емес.  
 
Егер    E
m
2
    және  K
Σ
V
(m)  =  2
m
  -  1екендігін  есепке  алсақ,  онда  формула 
көрінісіндегі  аналитикалық  жіктеу  m  -  өлшемді  кубтың  барлық  мүмкін  болған  бірлік 
координаталарынан  құрастырылатындығын  көреміз.  Мұнда  m  -  өлшемді  кубтың  әр  бір  і-
деңгейінде  C
m
i
      набор  қатысатындығын  және  әр  бір  наборда  полиномдағы  айнымалыларға 
сәйкес келетін і та бірлер болатындығы оңай табылады. Сондықтан {A
j
*}
Σ
m1
 полиномға енетін 
айнымалылар саны:  
              L
Σ
V
(m) = Σ (i .C
m
i
). 
теңдігі арқылы есептеледі. 
 Теорема дәлелденді. 
4-теорема.  D
2
  жүйесінде  тізбекті  импликация  амалы  Жегалкин  полиномында 
кезектегідей жалғыз тәсілмен ауыстырылады: 
i=1
=>
m
 A
i
 ≡ 
i=1
Σ
s1
j=2i
Σ
s2
k=j+1
Σ
s3
 … 
ℓ=n+1
Σ
sm
 A
2i-1 
A
j
A
k
…A
ℓ
 

i=1
Σ
z1
j=2i
Σ
z2
k=j+1
Σ
z3
 … 
ℓ=n+1
Σ
zm
A
2i-1
A
j
A
k
…A
ℓ
C,  
мұндаs
1
=m/2-(t/2-1),  s
2
=m-t+2,  s
3
=m-t+3,  ...,  s
m
=m;  z
1
=m/2-(p-1)/2,  z
2
=m-p+2,  z
3
=m-
p+3,…., z
m
=m,  
 
 
2 , 4 ,…,  m , егер m жұп болса, 
 
t = 
 
 
    1 , 3 , … ,  m, кері жағдайда. 
 

~ 169 ~ 
 
 
 
    1,3,…, m-1, егер m жұп болса, 
 
P = 
 
 
    2,4,…, m-1, кері жағдайда. 
 
  1, егер m жұп болса, және күрделік баға мынадай есептеледі: 
 
 
 1+2/3 (2
m
-1), егер m жұп болса, 
K
Σ
→
(m)  = 
 
 
 1/3 (2
m+1
-1)   кері жағдайда. 
мұнда p,t  элементар конъюнкциядағы аргументтер саны.  
Дәлелі.  Теоремадағы  негізгі  формуланың  дәлелі  2-теореманың  дәлеліне  ұқсас 
болғандықтан оны қарастырып отырмаймыз. Ал оның орнына кез келген  m үшін полиномда 
қатысатын элементар конъюнкциялардың санын есептеу формуласын  дәлелдейміз. 
Мұнда  T
i
(i=1,2,...,m)  арқылы  айнымалылар  саны  1  ден  m  ге  дейін  өскендегі 
полиномның  элементар  конъюнкциялар  санын    белгілейміз.  Қашан  m  =  2  және  m  =  3   
болғанда 
 
A
1
 → A
2
 = A
2
 A
2
 A
1
 1, 
 
A
1 
→ A
2
 → A
3
 = A
1
A
2
A
3
 A
1
A
2 
 A
1
A
3
A
1
A
3
 
формулаларға ие боламыз және T
2
 = 3, T
3
 = 5 екендігі белгілі.  
Егер  полиномды  біртіндеп  тізбекті  құрастыратын  болсақ,  онда  әр  бір  кезектегі 
полиномда қатысатын элементар конъюнкциялар саны алдынғысының екі еселенгендігінен не 
біреу көп, не біреу кем болатындығын байқаймыз. Мұнда, егер m - жұп болса бұл сан біреуге 
көп,  ал  кері  жағдайда  біреуге  кем  болады  екен.  Осы  заңдылыққа  сәйкес  m-    нің  өсуіне 
байланысты  полиномдағы  элементар  конъюнкциялар  санын    айқындайтын  сандар  тізбегін 
құрастыруымыз мүмкін: 
 
 
 
 
2 T
i-1
 + 1, егер i жұп болса, 
 
         T
i
 =  
 
 
 
2 T
i-1
 – 1,  кері жағдайда, 
мұнда i = 2,3,…,m.                                  . 
 
Енді бұл сандар тізбегін  жұп және тақ айнымалылар үшін екі топқа бөлеміз: 
 
T
2k
 : {3,11,43,171,…} , k = 1,2,…,m/2; 
 
T
2k-1 
: {1,5,21,85,341,…} , k = 1,2,…,(m+1)/2 
Осы жерден  
 
T
2k
 = T
2(k-1)
 + 2
2k-1
 
және  
 
T
2k-1
 = T
2(k-1)-1
 + 2
2k-2
 
немесе 
 
T
2k 
= 1+ 2
1
+ 2
3
 + 2
5
 +…+ 2
2k-1
 =  
 
= 1+ 2 (1 + 2
1 
+ 2
4
 +…+ 2
2k-2
) = 
 
= 1+ 2 (1 + 4
1
 + 4
2
 +…+ 4
(k-1)
, 
 
T
2k-1
 = 2
o
 + 2
2
 + 2
4
 +…+ 2
2k-2
 = 1+ 4
1
 + 4
2 
+…+ 4
k-1
 
екендігі келіп шығады. 
Бұл  шекті  тізбектерді  геометриялық  прогрессия  мүшелері  қосындысы  арқылы 
есептесек 
 
T
2k
 = 1 + 2(4
k
-1)/(4-1) = 1+ 2/3 (4
k
-1), 
 
T
2k-1
 = (4
k
-1)/3 = 1/3 (4
k
-1)  

~ 170 ~ 
 
немесе  егер 2k = m  жұп  болғанда және 2k-1= m, 2k=m+1 тақ болғанда, сонымен бірге 
4
k 
= 2
2k
  екендігін  есепке  алсақ кезектегі заңдылыққа ие боламыз: 
1 +2/3 (2
m
-1), егер m жұп болса, 
T
m
 =   
1/3 (2
m+1
-1)     кері жағдайда. 
Теорема дәлелденді. 
 
5-теорема . 
 
 
 
{A
i
}
~
m
 ≡ {A
j
*}
Σ
m1
 
ауыстыру аналитикалық формада жалғыз түрде кезектегідей жіктеледі: 
 
 
 
┐( 
i=1
Σ
m
A
i
) , егер m жұп болса, 
 
i=1

m
A
i
 =  
 
 
 
 
i=1
Σ
m
A
i
 ,кері жағдайда 
 және  
 
               m-1 ,егер        жұп болса, 
                K
Σ
~
(m) =    
 
 
 
 
                                       m , кері жағдайда. 
 
 
 
 
m + 1,  егер      жұп болса, 
               L
Σ
~
(m)= 
                                    m , кері жағдайда. 
 
Ауыстырудағы  формулалар  және  оларға  сәйкес  күрделік  бағаларды  табу 
тривиал болғандықтан теореманың дәлелін келтірмейміз. 
 
Сонымен  бірге  бұл  ауыстыру  үшін  кері  мәселеде    симметриялы  түрде 
орындалады, яғни    ┐( 
i=1

m
 A
i
),  егер m жұп болса, 
i=1
Σ
m
 A
i
 =  
 
i=1

m
 A
i
,          кері жағдайда 
6-теорема . 
 
 
 
{A
i
}
&
m
  ≡ {A
j
*}
Σ
m1
 
аналитикалық  ауыстыру  Жегалкин  полиномында  жалғыз  түрде  кезектегідей 
бейнеленеді:  
 
i=1
&
m
 (┐A
i
) = 
i=1
&
m
A
i

i=1
Σ
2
j=i+1
Σ
3
 … 
k=ℓ+1
Σ
m
A
i
A
j
…A
k
… 
 
…
i=1
Σ
m-1
j=i+1
Σ
m
A
i
A
j

i=1
Σ
m
A
i
1.  
Теореманың    дәлелі  индукция  әдісі  арқылы  өте  оңай  табылады.  Сондықтан  оны 
қарастыруды ізденушінің өзіне қалдырамыз. 
 
Пайдаланылған әдебиеттер тізімі: 
1 А.Новиков. Дискретная математика для программистов.Учебник. Санкт-Петербург, ПИТЕР., 
2000 г. 
2  А.А.Байжуманов.  Дискретті математика және математикалық логика.  Шымкент 2012 ж. 
3  .А.Л.Горелик, В.А.Скрипкин. Методы  распознования. Москва «Высшая школа» 1987. 
4   Журавлев Ю.И, Платоненко И.М, «Об экономном умножении булевых уравнений».- 
ЖВМ и МФ, том-24, 1984г.  
5Дискретті математика және математикалық  логика. Шымкент 2012ж. А.А.Байжұманов 
6    Математикалық    логика  және  алгоритмдер  теориясының  негіздері.  Алматы  2009ж, 
П.Т.Досанбай 

~ 171 ~ 
 
Резюме 
Рассматривается  некоторые  проблемы  систем  логических  уравненийи  важные 
проблемы  минимизации  некоторых  логических  формул  полученных  от  функции  обшей 
функции  Шеффере,  дизъюнкции,  импликации,  эквивалентности    и  конъюнкции  в  виде 
полиномов  Жегалкина  и  оценки  их  сложности.  Постепенно  полиномды  по  сборке  в  случае, 
если  цепной,  то  количество  элементарных  частиц,    либо  кто-то  менее,  что  мы  наблюдаем. 
Поскольку  два  поставленных  вопроса  в  форму,  поэтому  форма  конъюнктивная  нормальные 
дизъюнктив кемель это приводит к проблеме алгебры один логический смысл. Доказательство 
теоремы методом индукции, легко найтти. 
Summary      
It is consideret some problems of minimization of special disjunctive normal forms received 
from polynom  Gegalkine of the second of special classes. Gradually полиномды on assembling  in 
case if chain, that amount of elementary particles participating in two, either someone much of every 
turn  or  someone  less,  that  we  look  after.  As  two  put  questions  in  a  form,  therefore  a  form 
конъюнктивная normal it brings one logical sense over to the problem of algebra. 
Ключевые  слова:  функция,  дискриптивтік,  коэффициент,  аспект,  метрикалық 
аспектілері 
Keywords: function, attribute, coefficient, aspect, metric aspects. 
 
 

жүктеу/скачать 1,67 Mb.

Достарыңызбен бөлісу: