Буль алгебрасы

Автор: Пользователь скрыл имя, 12 Ноября 2011 в 09:20, реферат

Описание работы

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

Содержание

Кіріспе..................................................................................3
Мазмұны 1
Кіріспе 2
Буль функцияларының жалған және елеулі айнымалылары 10
Есеп шығару мысалы 10
Буль функцияларының жалған және елеулі 12
айнымалыларын программада жүзеге асыру 12

Работа содержит 1 файл

Анар Омирбаева Информатика.doc

— 280.50 Кб (Скачать)

     Мазмұны

 

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

 

     Кіріспе

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

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

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

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

A

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

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

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

функциялар  саны P2 (n) - 22 -ге тең.                                                             

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

  1. ƒ1(x) =0 -тұрақты 0
  2. ƒ2(x) =1-тұрақты 1;                                       
  3. ƒ3(x)=x –тепе-тең функция;
  4. ƒ4(x)= - х -ті жоққа шығару;
  5. ƒ5(x1,x2)= (x1&x2) - x1 мен x2 –нің конъюнкциясы (логикалық көбейту);
  6. ƒ6(x1,x2)= (x1∨x2) - x1 мен x2 –нің дизъюнкциясы (логикальщ қосу);
  7. ƒ6(x1,x2)=Бұл функциялардың мәні.
     xx      0 0      11      xx        
     00      00      11      00      11
     11      00      11      11      00
 
x1      x2 12) (x1∨x2) 1→х2) (x1Åx2) (x1\x2) (x1 ~x2) 1↓x2)
0     0

0     1

     0

     0

     0

     1

     1

     1

     0

     1

     1

     1

     1

     0

     1

     0

0     1      0      1      0      1      1      0      0
1     1        1      1      1      0      0      1      0
 

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

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

     болсын.

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

     b) Индуктивті өту. Айталық ƒ (x1,…,xm) - b жиынындағы функция болсын және A1,…,Am-b жиынындағы формула немесе U жиынындағы айнымалылар символы болатын өрнек болсын. Онда ƒ (A1,..., Аm) өрнегі b жиынындагы формула деп аталады.

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

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

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

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

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

     F(х1,...,xn) формуласына           ƒ (х1,...,xn)= ƒ0 1,..., ƒ m)       функциясын сәйкес қоямыз.

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

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

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

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

     1◦х2) арқылы (x1&x2), (x1∨x2), (х12) функцияларының кез-келгенін белгілейік.

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

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

     ((x1◦x2) ◦ x3 ) = (x1◦(x2◦x3)).

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

           (x1◦x2)=(x2◦x1)

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

     ((x1∨x2) & x3) = ((x1&x3) ∨(x2&x3))

     ((x1&x2) ∨ x3)=((x1∨x2) &(x2∨x3)

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

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

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

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

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

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

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

     x12 функциясы х12 функциясына қосалқы.

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

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

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

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

     Бұл формуланы F формуласына қосалқы формула деп атайды және F* арқылы белгілейді. Егер Ғ = С[0,1, 12, (x1∨x2), онда F* =С[0,1, , (x1∨x2),x12]. 

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

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

     xσ =

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

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

Информация о работе Буль алгебрасы