Буль математикасы

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 17 бет
Таңдаулыға:

Қазақстан Республикасы Білім және Ғылым министрлігі

Д. СЕРІКБАЕВ атындағы ШЫҒЫС ҚАЗАҚСТАН МЕМЛЕКЕТТІК

ТЕХНИКАЛЫҚ УНИВЕРСИТЕТІ

ФАКУЛЬТЕТІ: ИНФОРМАЦИОНДЫҚ ТЕХНОЛОГИЯ ЖӘНЕ

ЭНЕРГЕТИКА

КАФЕДРА: МАТЕМАТИКАЛЫҚ ЖӘНЕ КОМПЬЮТЕРЛІК

МОДЕРЛЕРЛЕУ

Тақырыбы: Буль математикасы

Орындаған: Ілияс Айсұлтан

Тобы: 11 ГДк-1

Қабылдаған: Нұрсадықова Р. Қ

Өскемен 2012

Мазмұны

Кіріспе . . . 3

Логика

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

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

Толықтық және тұйықтық . . . 7

Жегалкин теоремасы . . . 8

Маңызды жабық сыныптар. Толықтық туралы теорема . . . 9

Пост нәтижелері . . . 10

Буль функцияларының жалған және елеулі айнымалылары . . . 10

Буль функцияларының жалған және елеулі

айнымалыларын программада жүзеге асыру . . . 14

Қорытынды . . . 19

Қлданылған әдебиеттер тізімі . . . 20

Кіріспе

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

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

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

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

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

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

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

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

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

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

xx: _x x

0 0: 0 0

11: 11

xx: xx

xx: 00

0 0: 00

11: 11

xx: 00

: 11

xx: 11

0 0: 00

11: 11

xx: 11

: 00

x1x2: x ₁ x ₂

(х1&х2): (х ₁ &х ₂ )

(x1∨x2): (x ₁ ∨x ₂ )

(х1→х2): (х ₁ →х ₂ )

(x1⊕x2): (x ₁ ⊕x ₂ )

(x1\x2): (x ₁ \x ₂ )

(x1~x2): (x ₁ ~x ₂ )

(х1↓x2): (х ₁ ↓x ₂ )

x1x2:

0 0

0 1

(х1&х2):

(x1∨x2):

(х1→х2):

(x1⊕x2):

(x1\x2):

(x1~x2):

(х1↓x2):

x1x2: 0 1

(х1&х2): 0

(x1∨x2): 1

(х1→х2): 0

(x1⊕x2): 1

(x1\x2): 1

(x1~x2): 0

(х1↓x2): 0

x1x2: 1 1

(х1&х2): 1

(x1∨x2): 1

(х1→х2): 1

(x1⊕x2): 0

(x1\x2): 0

(x1~x2): 1

(х1↓x2): 0

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

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

болсын.

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

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

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

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

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

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

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

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

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

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

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

Анықтама. F және G формулалары β жиынында эквивалентті деп аталады, егер оларға сәйкес функциялар тең болса: ƒ _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, Equation. 3 =( Equation. 3 ∨ Equation. 3 ), Equation. 3 =( Equation. 3 & Equation. 3 )

5) (x& Equation. 3 ) =0, (x∨ Equation. 3 ) =1,

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

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

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

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

0 функциясы 1 функцияға қосалқы,

1 функциясы 0 функциясына қосалқы,

x функциясы х функциясына қосалқы,
функциясыфункциясына қосалқы,
х&х2функциясы х1vх2функциясына қосалқы,

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

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

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

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

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

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

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

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

x ^σ =

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

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

ƒ (х ₁ , . . . , x _m , x _m+1 , …, x _n ) = x ₁ ^σ ₁ &…& x _m ^σ _m ƒ(σ ₁ , …, σ _m , x _m+1 , …, x _n ),

(*)

мұнда дизъюнкция х ₁ , . . . , х _m айньмалыларының барлық мүмкін болатын мәндері бойынша алынады.

Бұл көрініс функцияның х ₁ , . . . , х _m айнымалылары бойынша жіктелінуі деп аталады.

Салдар ретінде жіктеудің арнайы екі түрін аламыз.

Айнымалы бойынша жіктелу:

ƒ (х ₁ , . . . , х _n-1 , х _n ) = х _n & ƒ (x ₁ , …, x _n-1 , 1) v & ƒ(x ₁ , …, x _n-1 , 0) .

ƒ (х ₁ , . ., х _n-1 , 0) және ƒ(х ₁ , . . . , x _n-1 , 1) функциялары жіктеудің құрамдас бөліктері деп аталады.

Барлық айньмалылар бойынша жіктеу:

ƒ (х ₁ , . . . , x _n ) = x ₁ ^σ ₁ &…& x _n ^σ _n ƒ(σ ₁ , …, σ _n ) .

ƒ (х ₁ , . . . , x _n ) ≡0 орындалғанда жіктеу келесі түрге айналады

x ₁ ^σ ₁ &…& x _n ^σ _n ƒ(σ ₁ , …, σ _n ) = x ₁ ^σ ₁ &…& x _n ^σ _n

Нәтижесінде

ƒ (х ₁ , . . . , x _n ) = x ₁ ^σ ₁ &…& x _n ^σ _n

(**)

екендігін аламыз.

Мұндай жіктелу кемел дизъюнктивті нормалъ қалып деп аталады (кемел д. н. ф. ) .

Теорема . Логика алгебрасының әрбір функциясы жоққа шығару, конъюнщия және дизъюнкция арқылы формула түрінде өрнектеле алады. Мысал. x ₁ v х ₂ функциясының кемел д. н. ф. -ін табу керек болсын.

Функцияның мәні бірге тең болатын үш жинақ бар: (0, 1), (1, 0), (1, 1) . Сондықтан

x ₁ v x ₂ = x ₁ ⁰ & x ₂ ¹ v x ₁ ¹ & x ₂ ⁰ v x ₁ ¹ & x ₂ ¹ = & x ₁ v x ₁ & v x ₁ & x ₂ .

Конъюнктивті нормаль қалып деп аталатын жіктеуді аламыз (кемел к. н. ф. ) :

ƒ (х ₁ , . . . , x _n ) =

конъюнктивті нормаль калып деп аталатын жіктеуді аламыз (кемел к. н. ф. )

5. Толықтық және тұйықтық

Анықтама. Егер кез-келген Буль функциясы осы жүйенің функциялары арқылы формула түрінде жазылатын болса, онда Р ₂ жиынындағы { f ₁ , f ₂ , …, f _s , … }функциялар жүйесі толық деп аталады.

Толық жүйелердің мысалдары:

1. Р ₂ жүйесі- барлық Буль функцияларынын жиыны -толық жүйе болып табылады.

2. G = { , x ₁ & х ₂ , x ₁ vx ₂ } жүйесі толық жүйе.

Кез-келген жүйе толық бола бермейді, мысалы G = {0, 1} жүйесі толық емес. Келесі теорема бір жүйенің толықтығын негізге ала отырып екінші жүйенің толықтығын анықтауға мүмкіндік береді.

Теорема. Айталық Р ₂ жиынында екі функциялар жүйесі берілсін:

G={ f ₁ , f ₂ , … }, (I)

D={ g ₁ , g ₂ , … }, (II)

олар туралы мына жағдай белгілі: (I) жүйе толық және оның әрбір функциясы (II) жүйенің функциялары арқылы формула түрінде өрнектелген. Онда (II) жүйе толық.

Мысал:

D ={ , x ₁ &x ₂ } жүйесінің толық екендігін дәлелдеңіз.

Дәлелдеу: (I) жүйе ретінде 2 мысалдағы жүйені аламыз:

{ , x ₁ & х ₂ , x ₁ vx ₂ }, ал (II) жүйе ретінде - D жүйесін аламыз.

x ₁ vx ₂ = тепе-теңдігін пайдаланамыз (элементар функциялардың касиетінен) .

Сонымен, (I) жүйенің әрбір функциясы (II) жүйенің функциялары арқылы формула түрінде өрнектеледі. Яғни, (II) жүйе: { , х ₁ &х ₂ } толық жүйе болып табылады.

6. Жегалкин теоремасы.

Р ₂ жиынындағы әрбір функция mod 2 бойынша көпмүшенің көмегімен өрнектеле алады (Жегалкин көпмүшесі бойынша) :

Мысал: (х ₁ v х ₂ ) функциясын Жегалкин көпмүшесі түрінде өрнектеңіз.

(x ₁ vx ₂ ) =ax ₁ x ₂ +bx ₁ +cx ₂ +d.

(0, 0) жинағында: x ₁ =x ₂ =0⇒0=a•0+b•0+c•0+d⇒d=0.

(0, 1) : x ₁ =0, x ₁ =1⇒1=a•0+b•0+c•1+d⇒c=1.

(1, 0) : x ₁ =1, x ₂ =0⇒1=a•0+b•1+c•0+d⇒b=1.

(1, 1) : x ₁ =1, x ₂ =1⇒1=a•1+b•1+c•1+d⇒a=1.

(x ₁ vx ₂ ) =x ₁ x ₂ +x ₁ +x ₂

Толықтық ұғымымен тұйықтау және тұйык сыныптар ұғымдары тығыз байланысты.

Анықтама. Айталық М- Р ₂ жиынындағы функциялар ішжиыны болсын. М-нің тұйықтауы деп М жиынының функциялары арқылы формула түрінде беріле алатын барлық буль функцияларының жиыны аталады, [М] арқылы белгіленеді.

Мысал.

1) М = Р ₂ . Бұл жағдайда [М] = Р ₂ .

2) М = {1, х ₁ +х ₂ } . [М] - L барлық сызықты функциялар сыныбы:

f (х ₁ , . . . , х _в ) = с ₀ +с ₁ х ₁ + . . . +с _n x _n , мұндағы с= 0, 1(i =0, . ., n), маңызды айнымалылар коэффициенті бірге тең де, жалған айнымалылар коэффициенті нөлге тең.

Тұйъқтаудыц қасиеттері

1) M⊆[M] .

2) [[M] ] =[M] .

3) егер М ₁ ⊆М ₂ , онда [М ₁ ] ⊆[М ₂ ] .

4) [M ₁ ∪М ₂ ] ⊇[М ₁ ] ∪[М ₂ ] .

Анықтама. М сыныбы (жиыны) тұйық деп аталады, егер [М] = М.

Мысал.

1) М = Р ₂ сыныбы түйық сынып.

2) М = {1, x ₁ + х ₂ } сыныбы тұйық емес.

Толықтық анықтамасы бастапқыға эквивалентті : М - толық жүйе, егер [M] = Р ₂ .

7. Маңызды жабық сыныптар. Толықтық туралы теорема.

Р ₂ жиыньшдағы маңызды түйық сыныптарды қарастырайық.

1. T ₀ арқылы барлық f (x ₁ , …, x _n ) буль функцияларының тұрақты нөлді сақтайтын сыныбын белгілейік, яғни f (0, . . . , 0) = 0 орындалатын функцияларды.

0, х, x ₁ &х ₂ , х ₁ v х ₂ , x ₁ ⊕x ₂ ∈T ₀ ,

1, ∉T ₀ .