11-мавзу. Тўлиқ системалар. Мухим ёпиқ синфлар. Режа

11-мавзу. Тўлиқ системалар. Мухим ёпиқ синфлар.


Режа.

1. 
   Тўлиқ системалар, Жегалкин кўпҳади,
   
2. 
   Жегалкин теоремаси.
   
3. 
   Нолни сақловчи функциялар, бирни сақловчи функциялар
   

{0,1} Буль алгебрасидаги ху конъюнкция амали оддий арифметикадаги 0 ва 1 сонлар устидаги кўпайтма амалига мос келади. Аммо 0 ва 1 сонларни қўшиш натижаси {0,1} тўплам доирасидан четга чиқади. Шунинг учун И.И.Жегалкин (3.VIII 1869-28.III 1947) 2 модулига асосан қўшиш амалини киритади (И.И.Жегалкин 30-йилларнинг бошида Москва давлат университетида биринчи бўлиб математик мантиқ бўйича илмий семинар ташкил этган). ва мулоҳазаларнинг 2 модули бўйича қўшишни сифатида белгилаймиз ва у қуйидаги чинлик жадвали билан берилади:

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

Чинлик жадвалидан кўриниб турибдики, = . Мантиқ алгебрасидаги кўпайтма ва 2 модули бўйича қўшиш мантиқ амаллари учун коммутатив, ассоциатив ва дистрибутив арифметик қонунлар ўз кучини сақлайди.
Буль алгебрасидаги асосий мантиқий амалларни киритилган арифметик амаллар орқали қуйидагича ифодалаш мумкин:
1. = ; 2. ; 3. ;
4. ; 5. .
2 модули бўйича қўшиш амалининг таърифига асосан ва .
Мантиқ алгебрасидаги исталган функцияни ягона арифметик кўпҳад шаклига келтириш мумкин. Ҳақиқатан ҳам, биз олдинги параграфларда исталган функцияни конъюнкция ва инкор мантиқий амаллар орқали ифодалаш мумкинлигини кўрган эдик. Юқорида конъюнкция, дизъюнкция ва инкор мантиқий амалларни арифметик амаллар орқали ифодаладик. Демак, исталган функцияни арифметик кўпҳад шаклига келтириш мумкин.
4-таъриф. кўринишидаги кўпҳадга Жегалкин кўпҳади деб айтилади. Бу ерда ҳамма ўзгарувчилар биринчи даражада қатнашади, қийматлар сатрида ҳамма лар ҳар хил бўлади, .
5-таъриф. кўринишидаги функция чизиқли функция деб айтилади. Бу ерда .
Чизиқли функциянинг ифодасидан кўриниб турибдики, аргументли чизиқли функциялар сони 2ⁿ⁺¹ га тенг ва бир аргументли функциялар доимо чизиқли функция бўлади.
Жегалкин кўпҳади кўринишидаги ҳар бир функциянинг аргументлари сохта эмас аргументлар бўлади. Ҳақиқатан ҳам, x₁ шундай аргумент бўлсин. У вақтда ихтиёрий функцияни қуйидаги кўринишда ёзиш мумкин:
.
Бу ерда  функцияси айнан 0 га тенг эмас, акс ҳолда аргумент функциянинг (кўпҳаднинг) аргументлари сафига қўшилмасди.
Энди аргументларнинг шундай қийматларини оламизки, бўлсин. У вақтда функциянинг қиймати аргументнинг қийматига боғлиқ бўлади. Демак, сохта аргумент эмас.
Мантиқ алгебрасидаги ҳамма аргументли чизиқли функциялар тўпламини ҳарфи билан белгилаймиз. Унинг элементларининг сони 2^n-1 га тенг бўлади.
2-теорема. Агар бўлса, у ҳолда ундан аргументлари ўрнига 0 ва 1 константаларни ҳамда ва функцияларни, айрим ҳолда устига ““ инкор амалини қўйиш усули билан функцияни ҳосил этиш мумкин.