Автор: Пользователь скрыл имя, 12 Ноября 2011 в 09:20, реферат
Жалпы алғанда буль функцияларының жалған және елеулі айнымалыларының дискреттік математикада ойнайтын рөлі өте зор. Бірінші оларды теориялық тұрғыдан қарастырайық. Буль функцияларының жалған және елеулі айнымалылары деп .............. атайды.
Бұл айнымалылардың маңызы өте зор. Мысалы, функция көп айнымалы болса, кейбір айнымалыларын (жалған айнымалыларды) алып тастауға болады. Ол бізге барлық параметрлер бойынша үнемдеуге мүмкіндік береді. Сондықтан осы үнемдеуді жүзеге асыратын программдық пакет құру актуалды мәселе. Бұл жұмыста қойылған мақсат бойынша бірінші теориялық, одан кейін программалық жүзеге асыру жүргізілді.
Кіріспе..................................................................................3
Мазмұны 1
Кіріспе 2
Буль функцияларының жалған және елеулі айнымалылары 10
Есеп шығару мысалы 10
Буль функцияларының жалған және елеулі 12
айнымалыларын программада жүзеге асыру 12
Кіріспе.......................
Жалпы алғанда буль функцияларының жалған және елеулі айнымалыларының дискреттік математикада ойнайтын рөлі өте зор. Бірінші оларды теориялық тұрғыдан қарастырайық. Буль функцияларының жалған және елеулі айнымалылары деп .............. атайды.
Бұл айнымалылардың
маңызы өте зор. Мысалы, функция көп
айнымалы болса, кейбір айнымалыларын
(жалған айнымалыларды) алып тастауға
болады. Ол бізге барлық параметрлер
бойынша үнемдеуге мүмкіндік
береді. Сондықтан осы үнемдеуді жүзеге
асыратын программдық пакет құру актуалды
мәселе. Бұл жұмыста қойылған мақсат бойынша
бірінші теориялық, одан кейін программалық
жүзеге асыру жүргізілді.
1.
Логика алгебрасының
функциялары
A
йталық U-{u1,и2,...,иm,...} - айнымалылардың бастапқы алфавиті болсын. Аргументтері E2={О,1} жиынында анықталған және аiÎЕ2(і = 1,2,...,n), егер аiÎЕ2(і = 1,2,...,п) шартын қанағаттандыратын ƒ(u ,u ,…,u ) функциялары қарастырылады.
Бұл функциялар логика алгебрасыныц функциялары немесе буль фунщиялары деп аталады. Р2 арқылы U алфавитінде берілген, сондай-ақ 0 және 1 тұрақтыларын қамтитын барлық логика алгебрасының функциялар жүйесін белгілейміз.
Теорема. х1,х2,...,хn п айнымалыға тәуелді Р2 жиынындағы барлық
функциялар
саны P2 (n) -
22
-ге тең.
Логика алгебрасы функцияларың мысалдары:
xx | 0 0 | 11 | xx | |
00 | 00 | 11 | 00 | 11 |
11 | 00 | 11 | 11 | 00 |
x1 x2 | (х1&х2) | (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), (х1+х2) функцияларының кез-келгенін белгілейік.
Логика алгебрасы фунщияларыныц цасиеттері
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)
функциясына қосалқы функция деп аталады.
x1vх2 функциясы х1&х2 функциясына қосалқы.
Қосалқылықтың анықтамасынан ƒ ** =( ƒ *)* = ƒ екендігі шығады, яғни функция ƒ * функциясына қосалқы.
Қосалқылық принципі. Егер F=С[ƒ1,..., ƒ s] формуласы ƒ (х1,...,xn)
функциясын жүзеге асырса, онда F формуласынан ƒ1,..., ƒ s функциясын
ƒ1*,..., ƒs* функциясына ауыстыру аркылы алынған С[ƒ1*,..., ƒs*] формуласы , ƒ* (х,,...,хn) функциясын жүзеге асырады.
Бұл
формуланы F формуласына қосалқы
формула деп атайды және F*
арқылы белгілейді. Егер Ғ = С[0,1,
,х1&х2,
(x1∨x2), онда F*
=С[0,1,
, (x1∨x2),x1&х2].
4.Буль функцияларын айнымалыларға жіктеу. Кемел дизъюнктивті нормаль қалып
х =хσ∨хσ белгілеуін енгізейік, мұндағы σ - нөлге немесе бірге тең параметр.
xσ =
хσ = 1 тек сол жағдайда, егер х = σ болса екендігіне оңай көз жеткізуге болады.
Теорема (Буль функцияларын айнымалыларға жіктеу туралы). Әрбір ƒ(х1,...,xn) логика алгебрасының функциясын кез-келген т(1 т п) үшін келесі түрде беруге болады :