Мазмұны

 

Кіріспе..................................................................................3 

 

     Кіріспе

   Жалпы алғанда  буль функцияларының жалған және елеулі айнымалыларының дискреттік математикада ойнайтын рөлі өте зор. Бірінші оларды теориялық тұрғыдан қарастырайық. Буль функцияларының жалған және елеулі айнымалылары деп .............. атайды.

Бұл айнымалылардың маңызы өте зор. Мысалы, функция көп  айнымалы болса, кейбір айнымалыларын (жалған айнымалыларды) алып тастауға болады. Ол бізге барлық параметрлер  бойынша үнемдеуге мүмкіндік  береді. Сондықтан осы үнемдеуді жүзеге асыратын программдық пакет құру актуалды мәселе. Бұл жұмыста қойылған мақсат бойынша бірінші теориялық, одан кейін программалық жүзеге асыру жүргізілді. 

     ЛОГИКА  АЛГЕБРАСЫ

     1. Логика алгебрасының  функциялары 

_A

йталық U-{u₁,и₂,...,и_m,...} - айнымалылардың бастапқы алфавиті болсын. Аргументтері E₂={О,1} жиынында анықталған және а_iÎЕ₂(і = 1,2,...,n), егер а_iÎЕ₂(і = 1,2,...,п) шартын қанағаттандыратын ƒ(u ,u ,…,u ) функциялары қарастырылады.

     Бұл функциялар логика алгебрасыныц функциялары немесе буль фунщиялары деп аталады. Р₂ арқылы U алфавитінде берілген, сондай-ақ 0 және 1 тұрақтыларын қамтитын барлық логика алгебрасының функциялар жүйесін белгілейміз.

     Теорема. х₁,х₂,...,х_n п айнымалыға тәуелді Р₂ жиынындағы барлық

функциялар  саны P₂ (n) - 2² -ге тең.                                                             

     Логика  алгебрасы функцияларың мысалдары: 

1. ƒ₁(x) =0 -тұрақты 0
2. ƒ₂(x) =1-тұрақты 1;                                       
3. ƒ₃(x)=x –тепе-тең функция;
4. ƒ₄(x)= - х -ті жоққа шығару;
5. ƒ₅(x₁,x₂)= (x₁&x₂) - x₁ мен x₂ –нің конъюнкциясы (логикалық көбейту);
6. ƒ₆(x₁,x₂)= (x₁∨x₂) - x₁ мен x₂ –нің дизъюнкциясы (логикальщ қосу);
7. ƒ₆(x₁,x₂)=Бұл функциялардың мәні.

 
 

     2. Формулалар. Формулаларды функциялармен жузеге асыру

       Анықтама. Айталық b- Р₂ жиынындағы  функциялар ішжиыны

     болсын.

     а) Индукция базисі. b ішжиынындағы әрбір   ƒ (x₁,…,x_m) функция    b-ғы формула деп аталады.

     b) Индуктивті өту. Айталық ƒ (x₁,…,x_m) - b жиынындағы функция болсын және A₁,…,A_m-b жиынындағы формула немесе U жиынындағы айнымалылар символы болатын өрнек болсын. Онда ƒ (A₁,..., А_m) өрнегі b жиынындагы формула деп аталады.

     с) Формуланың индуктивті анықтамасына сүйене отырып, b-дағы әрбір F(х₁,...,x_n) функциясына Р₂ жиынындағы ƒ (х₁,...,x_n)  функциясын сәйкес қоямыз.

     d) Индукция базисі. Егер.  F(х₁,...,x_n)  = ƒ (х₁,...,x_n), мүндағы ƒ Îb, онда F(х₁,...,х_n) формуласына ƒ (х₁,...,x_n) функциясын сәйкес қоямыз.

     e) Индуктиві өту.     Айталық F(х₁,...,x_n)=ƒ (х₁,...,x_n)       мұндағы А_i(і = 1,...,m) b-дағы формула немесе х_j(i) айнымалысыньщ белгісі.

     Онда  индуктивті  болжам  бойьнша      А_i-ге   Р_г   жиынындағы   ƒ_i

функциясы   немесе   ƒ =х_j(i)    тепе-тең   функция   сәйкес   қойылған.

     F(х₁,...,x_n) формуласына           ƒ (х₁,...,x_n)= ƒ₀ (ƒ ₁,..., ƒ _m)       функциясын сәйкес қоямыз.

     Егер  ƒ функциясы F формуласына сәйкес келсе , онда   F формуласы ƒ функциясын жүзеге асырады дейді.

     F формуласына сәйкес келетін ƒ функциясы b-дағы функциялардың суперпозициясы деп, ал ƒ функциясын b -дан алу үрдісі суперпозиция операциясы деп аталады. 

     3.Формулалардың эквиваленттігі. Қосалқылык принципі

     Анықтама. F және G формулалары b жиынында эквивалентті деп аталады, егер оларға сәйкес функциялар тең болса: ƒ_F= ƒ_G.

     (х₁◦х₂) арқылы (x₁&x₂), (x₁∨x₂), (х₁+х₂) функцияларының кез-келгенін белгілейік.

     Логика  алгебрасы фунщияларыныц  цасиеттері

     1)   (x₁◦х₂) функциясы ассоциативтілік қасиетке ие:

     ((x₁◦x₂) ◦ x₃ ) = (x₁◦(x₂◦x₃)).

     2)   (х₁◦х₂) функциясы коммутативтілік қасиетке ие :

           (x₁◦x₂)=(x₂◦x₁)

     3) Конъюнкция және дизъюнкция үшін  дистрибутивтілік заң орындалады :

     ((x₁∨x₂) & x₃) = ((x₁&x₃) ∨(x₂&x₃))

     ((x₁&x₂) ∨ x₃)=((x₁∨x₂) &(x₂∨x₃)

     4) =x , =( ∨ ), =( & )

     5) (x& )=0, (x∨ )=1,

         (x&0)=0, (x∨0)=x,

         (x&1)=0, (x∨1)=x. 

     Анықтама.    [ƒ (х₁,...,x_n)]*= ( ,…, ) функциясы ƒ (х₁,...,x_n)

функциясына қосалқы функция деп аталады.

• 0 функциясы 1 функцияға қосалқы,                  
• 1 функциясы 0 функциясына қосалқы,
• x функциясы х функциясына қосалқы,
• функциясы функциясына қосалқы,
• х&х₂ функциясы х₁vх₂ функциясына қосалқы,

     x₁vх₂ функциясы х₁&х₂ функциясына қосалқы.

     Қосалқылықтың анықтамасынан ƒ ^** =( ƒ ^*)^* = ƒ екендігі шығады, яғни функция ƒ ^* функциясына қосалқы.

     Қосалқылық  принципі. Егер F=С[ƒ₁,..., ƒ _s] формуласы ƒ (х₁,...,x_n)

функциясын  жүзеге асырса, онда F формуласынан ƒ₁,..., ƒ _s функциясын

ƒ₁^*,..., ƒ_s^* функциясына ауыстыру аркылы алынған С[ƒ₁^*,..., ƒ_s^*] формуласы , ƒ^* (х,,...,х_n) функциясын жүзеге асырады.

     Бұл формуланы F формуласына қосалқы формула деп атайды және F^* арқылы белгілейді. Егер Ғ = С[0,1, ,х₁&х₂, (x₁∨x₂), онда F^* =С[0,1, , (x₁∨x₂),x₁&х₂]. 

     4.Буль  функцияларын айнымалыларға жіктеу. Кемел дизъюнктивті нормаль қалып

     х =хσ∨хσ белгілеуін енгізейік, мұндағы σ - нөлге немесе бірге тең параметр.

     x^σ =

     х^σ = 1 тек сол жағдайда, егер   х = σ болса екендігіне оңай көз жеткізуге болады.

     Теорема (Буль функцияларын айнымалыларға жіктеу туралы). Әрбір ƒ(х₁,...,x_n) логика алгебрасының функциясын кез-келген т(1 т п) үшін келесі түрде беруге болады :