Математикалық логика. Буль алгебрасы

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

«Астана Медициналық Университеті»АҚ

Медбиофизика курсы мен математика, информатика

Тақырыбы: Буль алгебрасы

Орындаған:

Қабылдаған:

Астана 2012

Мазмұны

1. Математикалық логика . . . 4

2. Математикалық логиканың негізгі функциялары және

Логикалық функцияларының кестесінің мәндері . . . 5

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

4. Қорытынды . . . 9

5. Пйдаланылған әдебиет . . . 10

Кіріспе

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

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

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. Математикалық логиканың негізгі функциялары және

Логикалық функцияларының кестесінің мәндері.

1) ДИЗЪЮНКЦИЯ (Disjunction) -

1) тек екі аргументінің мәні бір мезгілде «жалған» болған кезде ғана мәні «жалған болатын екі айнымалының бүл функциясы. Логикалық «қосу» операциясьша барабар;

2) «немесе»

Кемел дизъюнктивті нормаль қалып

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

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

(**)

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

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

2) КОНЪЮНКЦИЯ (лат. conjunctіo - одақ, байланыс) - логикалық байланымдар, екі пікірдің бірігуінен логикалық “және” жалғауы арқылы пікір құратын логикалық операция (символдық жазылуы: ALB) . Осылай құрылған күрделі пікір оған енетін барлық пікірлер ақиқат болғанда және тек сол жағдайда ақиқат, ал қалған жағдайлардың бәрінде жалған болады.

3) ИНВЕРСИЯ - цифрлық сигналдар үшін логикалық терістеу амалын (“емес”) орындайтын электрондық элемент. Сонымен қатар инвертор мәлімет өңдейтін және тасымалдайтын компьютер құрылғыларында электр сигналдарын қалыптастырып күшейтеді. Әдетте, интегралдық сұлбалар құрамында болып, транзисторлық элементтерден тұрады. Потенциалдық және импульстік инверторлар болып ажыратылады. Потенциалдық инверторде кірісіндегі кернеудің жоғары деңгейі шығысында төменгі деңгейге түрленеді және керісінше. Оның кіріс сигналы мен шығыс сигналының арасындағы байланыс логикалық “емес” функциясына сәйкес келеді. Импульстік инверторде кірісіне сигнал келген сәтте оның шығысында полярлығы кірісіндегіге қарама-қарсы сигнал қалыптасады. Инвертор компьютерлердің логикалық элементтерінің негізгілерінің бірі болып табылады. Интегралдық сұлбаларда инвертор өзіндік тәуелсіз міндет атқармай, күрделі логикалық сұлбалардың құрамына кіретін қарапайым элемент қызметін атқарады.