Дискрет анал

Мулоҳазалар устида логик операциялар.

Мулоҳазаларнинг хақиқатлилик жадваллари.

Логик операциялар билан танишамиз:

1. 
   “Инкор” операцияси. А мулоҳазага нисбатан ёки билан белгиланади ва “А эмас” ёки “А экани нотуғри” деб ўқилади.
   

мулоҳазанинг ростилик қиймати А мулоҳазанинг ростлик қийматига қарама-қаршидир. Жадвалда қуйидагича ифодаланади:

А
0	1
1	0

2. «Дизъюнкция» операцияси А ва В мулоҳазаларга нисбатан кўринишда белгиланади ва ёки А, ёки В, ёки А ва В деб ўқилади.

Дизъюнкциянинг ростлик жадвали:

А	В
0	1	1
1	0	1
1	1	1
0	0	0

3. «Конъюнкция» операцияси А ва В мулоҳазаларга нисбатан кўринишда белгиланади ҳамда А ва В деб ўқилади.
Конъюнкциянинг ростлик жадвали:

А	В
0	1	0
1	0	0
1	1	1
0	0	0

Конъюнкция факат бир холдагина «рост», яъни А ва В мулоҳазалардан хар иккаласи рост булганда колган холларда «ёлгон» мулохазадир.

4. «Импликация» операцияси А ва В мулоҳазаларга нисбатан А→В кўринишда белгиланади ва А дан В келиб чиқади ёки “ В бўлсагина А бўлади ” деб ўқилади.

Импликациянинг ростлик жадвали.

А	В
0	1	1
1	0	0
1	1	1
0	0	1

5. «Эквиваленция» операцияси А ва В мулоҳазаларга нисбатан А↔В кўринишда белгиланади ва А эквивалент В га деб ўқилади. Эквиваленциянинг ростлик жадвали:

А	В	А↔В
0	1	0
1	0	0
1	1	1
0	0	1

2-маъруза машғулоти

1. 
   Мулоҳазалар формуласи.
   

Энди мулоҳазалар алгебрасининг формулаларини аниқлаштирайлик.
1. Мулоҳазалар, мулоҳазавий ўзгарувчилар, логик ўзгармаслар (0 ва 1) - формулалардир.
2. Агар А ва В формулалар бўлса, , , , , А↔В – формулалардир. Мулоҳазалар алгебрасида бошқа формулалар мавжуд эмас.
Формулаларда операцияларни бажарилиш тартиби қавслар билан аниқланади. Агар логик операцияларни бажарилишини кучлилик жиҳатдан , кўринишда олинса, баъзи қавслар тушириб қолдирилиши мумкин.

2. 
   Тенг кучли мантиқий мулоҳазалар.
   

Таъриф.Агар мулохазалар алгебрасининг ( А₁,А₂,…,А_n) ва ( А₁,А₂,…,А_n) формулалари пропозиционал узгарувчилари кийматларининг барча наборларида бир хил киймат кабул килсалар, бу формулалар тенг кучли формулалар дейилади ва бу = куринишда езилади.

Мисол. СС ва СС формулалар тенг кучли формулалар эканлигини курсатамиз:

А	В	С	А	А	В	(АС	(АС
1	1	1	0	1	1	1	1
1	1	0	0	1	1	0	0
1	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0
0	1	1	1	1	1	1	1
0	1	0	1	1	1	0	0
0	0	1	1	1	1	1	1
0	0	0	1	1	1	0	0

3. 
   Тавтология.
   

Мулоҳазавий ўзгарувчиларнинг ҳар қандай қийматларида “рост” қиймат олувчи формулага «айнан рост» ёки «тавтология» дейилади. Мулоҳазавий ўзгарувчиларнинг ҳар қандай қийматида “ёлғон” қиймат олувчи формулага “айнан – ёлғон” формула дейилади.
«Айнан рост» ёки “Айнан – ёлғон” бўлмаган формула бажарилувчи формула дейилади.


3-маъруза машғулоти

1. 
   Буль ўзгарувчилари ва Буль функциялари.
   

н аргументга нисбатан Буль (логик) функцияси деб, аргументлари {0,1} тасодифий миқдорга ҳамда қийматлари ҳам {0,1} тасодифий миқдорга тегишли бўлган функцияга айтилади.
Мулоҳазалар алгебрасининг формулалари н – ўзгарувчига нисбатан қандайдир логик функцияни аниқлайди, чунки ҳар бир формула {0,1} тасодифи миқдорга тегишли бўлган қиймтни қабул қилади. Логик (пропорзиционал) формулани қисқача “ нф” билан белгилаймиз.

2. 
   Буль алгебраси.
   

Мулоҳазалар алгебрасининг асосий тавтологиялари (қонунлари)ни қуйида келтирамиз:

3. 
   Буль формулалари.
   

Содда ўзгарувчи мулоҳазалар устида фақат , - операциялар қўллаш билан ҳосил қилинадиган нф келтирилган формула дейилади.
Фараз қилайлик У – келтирилган формулалар. У даги ҳар бир операция белгиси га ва операция белгиси га, 0 қиймат 1 га, 1 қиймат 0 га алмаштирлса У га иккиланма У* формула ҳосил бўлади. Агар .

4. 
   Буль функциялари суперпозицияси.
   

Таъриф. Агар ( А₁,А₂,…,А_n) ва ^* ( А₁,А₂,…,А_n) формулалар бир –биридан  ни  га ,  эса  га алмаштириш ердамида хосил килинса, у холда бундай формулалар узаро кушма формулалар дейилади.
Мисол. С формула С формулага кушмадир.
Теорема. ( А₁,А₂,…,А_n) ва ^* ( А₁,А₂,…,А_n) формулалар узаро кушма булиб, А₁,А₂,…,А_n улар тартибига кирган барча пропозиционал узгарувчилар булса, у холда
( А₁,А₂,…,А_n)  ^* (А₁, А₂,…, А_n)
Таъриф.  формулага кирган барча логик операциялар сони унинг ранги дейилади ва r() билан белгиланади. Бунда пропозиционал узгарувчининг ранги 0 га тенг деб хисобланади.
Мисол. r (АС)=5, чунки бу формулага 5 та () логик операция кирган.
Теорема. Агар  булса, у холда ^* ^* дир.
Таъриф. Агар ( А₁,А₂,…,А_n) формула учун ( А₁,А₂,…,А_n) ( А₁, А₂,…, А_n) ^* ( А₁,А₂,…,А_n) уринли булса, у холда бундай формула уз –узига кушма формула дейилади.
Мисол. (А,В,С)СС формула уз-узига кушмадир.

5. 
   Дизъюнктив ва конъюнктив нормал формалар.
   

Берилган Х₁,…Х_н мулоҳазавий ўзгарувчиларнинг ўзини ёки инкорини дизъюнкциясига элементар дизъюнкация дейилади. Масалан: .
Берилган мулоҳазавий ўзгарувчиларнинг ўзини ёки инкорини коъюнкциясига элементар конъюнкция дейилади. Масалан: .
Берилган мулоҳазавий ўзгарувчиларнинг ҳар бирининг ўзини ёки инкорини фақат бир мартадан ўз ичига оладиган элементар дизъюнкация (конъюкция) тўла элементар дизъюнкация (конъюнкция) дейилади. Масалан: .
Элементар дизъюнкацияларнинг конъюнкциясига конъюнктив нормал форма (КНФ) дейилади.
Тўла элементар дизъюнкцияларнинг конъюнкциясига мукаммал конъюктив нормал форма (МКНФ) дейилади.
Элементар конъюнкцияларнинг дизъюнкциясига дизъюнктив нормал форма (ДНФ) дейилади.
Тўла элементар конъюнкциянинг дизъюкциясига мукаммал дизъюнктив нормал форма (МДНФ) дейилади.
4-мавзу. Реле-контакт схемалар (2 соат)
1. Реле-контакт схемалар.
Ўтказгич, калит, кириш, чиқишдан иборат бўлган қурилманинг схема ёрдамида ифодаланиши контакт схема дейилади.

2. 
   Қурилмани схематик тасвири.
   

Калит X , Y ,… , Х₂ ,…билан белгиланади. Калит икки ҳолатдан бирида булиши мумкин: токка уланган ёки уланмаган. Агар Х – токка уланганлик ҳолатини билдирса - токка уланмаганлик ҳолатини, ёки аксинча, билдиради.

3. Формулалар ва схемалар орасидаги ўзаро бир қийматли мослик.
Қуйида формула билан схема ўртасидаги бир қийматли мосликни келтирамиз.

Формула	Схема
Х	Х
	X Y
	X Y
	Х
1
	X
0

4.Схемаларни таҳлили ва синтези
Берилган формула конъюнктив нормал форма ёки дизъюнктив нормал формага келтирилган бўлса, унга мос тузиладиган схема формулага мос содда схемага нисбатан бирмунча мураккаброқ бўлиши мумкин. Схема ток ўтказиши учун мос мулаҳазавий ўзгарувчининг қиймати 1 бўлиши керак.
Схеманинг синтезини ўтказиш – берилган формуланинг ёки ростлик жадвалининг реле-контакт схемасини тузишдан иборат.
Реле – контакт схемага мос келувчи формулага схеманинг ўтказувчанлик функцияси, ростлик жадвали эса схеманинг ишлаш шартлари дейилади.
Бир хил ўтказувчанлик функциясига эга бўлган схемалар тенг кучли схемалар дейилади.
5- мавзу. Мулоҳазалар ҳисоби (4 соат)
1-маъруза машғулоти

1. 
   Мулоҳазалар ҳисобида формулалар.
   

Таъриф.Мулохазалар хисоби алфавити символларининг хар кандай чекли кетма- кетлиги формула дейилади.
Таъриф. а) хар кандай пропозиционал узгарувчи ТТ формуладир.
б) Агар Á ва Â лар формула бўлса, (Á&Â), (ÂÚÁ) , (ÂÞÁ), (ÂÛÁ), (Áù) лар хам формуладир
с) ТТ формулалар факат а) ва б) пунктлар ёрдамида курилади.

2. 
   Аксиомалар системаси.
   

Мулохазалар хисобининг аксиомалари 4 группага булинади:
I группа аксиомалари
I-1. АÞ(ВÞА).
I-2. (АÞ(ВÞС))Þ((АÞВ)Þ(АÞС)).
II группа аксиомалари
II-1.А&ВÞА
II-2. А&ВÞВ
II-3. (АÞВ)Þ((АÞС)Þ(АÞВ&С)).
III группа аксиомалари
III-1. АÞАÚВ,
III-2. ВÞАÚВ,
III-3. (АÞС)Þ((ВÞС)Þ(АÚВÞС)).
IV группа аксиомалари
IV-1. (АÞС)Þ(ùВùÞА)
IV-2. АÞù ùА
IV-3. ù ùАÞА.

3.