1. Mantiq amallari: dizyunksiya,konyuksiya inkor

umumrekursiv funksiya bo 'lishi va har qanday umumrekursiv funksiya Я -
aniqlanuvchi funksiya ekanligi tasdiqlandi.
1936-yilda Chyorch quyidagi tezisni e’lon qildi: har qanday intuitiv
effektiv (samarali) hisoblanuvchi funksiyalar umumrekursiv funksiyalar dir.
Bu teorema emas, balki tezisdir: tezis tarkibida intuitiv aniqlangan
effektiv hisoblanuvchi funksiya tushunchasi, aniq matematik atamalarda
aniqlangan umumrekursiv funksiya tushunchasi bilan aynan tenglashti-rilgan. Shuning uchun bu tezisni isbotlash mumkin emas. Ammo Chyorch va
boshqa olimlar tomonidan bu tezisni quvvatlovchi ko‘p dalillar ko‘rsatildi.
1936-1937-yillarda, A.Tyuring3 Chyorch ishlaridan bexabar holda
yangi funksiyalar sinfini kiritdi. Bu funksiyalami «Tyuring bo‘yicha
hisoblanuvchi funksiyalar» deb atadilar. Bu sinf ham yuqorida aytilgan
xossalarga ega edi va buni Tyuring tezisi deb aytamiz. 1937-yilda
1 Stiven Koul Klini (Stephen Cole Kleene, 1909-1994) - AQSh matematigi. U o ‘z familiyasini
“Kleyni” shaklda talaffuz etishiga qaramasdan, sobiq Sovet Ittifoqida uning ilmiy ishlarini rus
tiliga (rus tilidan esa o'zbek tiliga ham) “Klini” nomi bilan tarjima qilishgan.
2 Jak Erbran (Jacques Herbrand, 1908-1931) - fransuz matematigi.
3 Tyuring Alan Matison (Turing Alan Mathison. 1912-1954) - Ingliz matematigi, mantiqchisi,
kriptografi.
www.ziyouz.com kutubxonasi
A.Tyuring uning hisoblanuvchi funksiyalari X-aniqlanuvchi funksiyalarning о ‘zi va, demak, umumrekursiv funksiyalaming xuddi о ‘zi ekanligini
isbotladi. Shuning uchun Chyorch tezisi bilan Tyuring tezisi ekvivalentdir.
1936-yilda E.Post (Tyuring ishlaridan bexabar holda) aynan Tyuring
erishgan natijalarga mos keladigan natijalami e’lon qildi va 1943-yilda,
1920-1922-yillardagi nashr etilmagan ishlariga asoslanib, to‘rtinchi
ekvivalent tezisni nashr etdi. Shunday qilib, algoritm tushunchasini
bevosita aniqlashga va so‘ngra uning yordamida hisoblanuvchi funksiya
tushunchasini aniqlashga birinchi bo'lib bir-biridan bexabar holda E.Post
va A.Tyuring erishdilar.
Post va Tyuring algoritmik jarayonlar ma’lum bir tuzilishga ega bo'lgan «mashina» bajaradigan jarayonlar ekanligini ko'rsatishdi. Ular ushbu
«mashinalar» yordamida barcha hisoblanuvchi funksiyalar sinfi bilan
barcha qismiy rekursiv funksiyalar sinfi bir xil ekanligini ko'rsatdilar va,
demak, Chyorch tezisining yana bitta fundamental tasdig'i yuzaga keldi.

95-savol. Algebra,algebraic Sistema kengaytmasini qurish
An to ‘plamni A ga akslantiradigan har qanday akslantirish
A to‘plamda berilgan «-or yoki n-o‘rinli algebraik amal deyiladi.
Bu yerda n — manfiy bo‘lmagan butun son bo‘lib, algebraik
amalning rangi deyiladi. A * 0 to‘plam va A da bajariladigan algebraik amallar to‘plami Q berilgan bo‘lsin. (A, Q) juftlik algebra
deyiladi.
a) Agar \fa, Ь<еА uchun a * b = b * a bo‘lsa, u holda * amali
A to‘plamida kommutativ algebraik amal deyiladi;
b) Agar Va, b, cgA uchun a* (b * c) — (a* b) * с shart
bajarilsa, * amali A to‘plamida assotsiativ algebraik amal deyiladi;
d) Agar Va&A uchun shunday e^A topilib, e* a = a shart
bajarilsa, e element * amalga nisbatan chap neytral element, agar
a* e = a shart bajarilsa, о ‘ng neytral element, agar ikkala shart
ham bajarilsa neytral element deyiladi.
acA element va VZ>, ceA elementlar uchun a * b = a* с
tenglikdan b—c kelib chiqsa, u holda a element chap regular
element deyiladi.
a&A element uchun shunday a'eA element topilib, a' * a—e
bo‘lsa, a’ element a elementga chap simmetrik element deyiladi.
A to'plamdagi ekvivalentlik munosabati boMsin. Agar av a2,
bv b2sA elementlar uchun alRbl va a2Rb2 shartlardan
(a] * a2)R(bl * b2) kelib chiqsa, u holda R ekvivalentlik munosabati kongruensiya deyiladi,
46
Agar (A, D.) algebra berilgan bo‘lsa, Q to‘plamdagi amallarning ranglaridan iborat to‘plam algebraning turi deyiladi.
А Ф0 to‘plam uchun Q to‘plam A da aniqlangan amallar to‘plami, Q' to‘plam A da aniqlangan munosabatlar to‘plami bo‘lsin.
U holda (A, Q, Q") tartiblangan uchlik algebraik sistema deyiladi.
96-savol. Berilgan algebra, algbraik sistemalar orasida gomomorfizm va izomorfizm o’rnatish
(A, Q), (В, Q') algebralar berilgan bo‘lsin. Q dagi barcha
amallarni saqlaydigan ф:A-^B akslantirish (A, Cl) algebraning
(B, Q) algebraga gomomorfizmi deyiladi.
Ф:A->B akslantirish (A, Q) algebraning (В, Q') algebraga gomomorfizmi bo‘lsin. U holda agar ф inyektiv akslantirish bo‘lsa,
monomorfizm, Ф syuryektiv akslantirish bo‘lsa, epimorfizm,
Ф biyektiv akslantirish bo‘lsa, izomotfizm deyiladi.
Algebrani o‘zini o‘ziga gomomorf akslantirish endomotfizm,
algebrani o‘zini o‘ziga izomorf akslantirish esa avtomorfizm deyiladi.
Ta’rif. (X, ), (X’ , ’) bir xil turli algebralar berilgan bŏlsin.

Agar ixtiyoriy rangi r ga teng bŏlgan f  amal va (x₁ ,x₂ , …, x_r )  X ^r uchun rangi r ga teng bŏlgan f’ ’ amal va  : X  X’ akslantirish mavjud bŏlib, ular uchun

( f (x₁ ,x₂ , …, x_r )) = f’((x₁), (x₂) , …, (x_r ) munosabatlar ŏrinli bŏlsa , u holda (X, ), (X’ , ’) algebralar gomomorf ,  akslantirish esa berilgan algebralar gomomor-fizmi deyiladi.

Ta’rifdan (X, ) dagi neytral va simmetrik elementlarini gomomorf obrazlari (agar mavjud bŏlsa) (X’ , ’) dagi neytral va simmetrik elementlariga teng bŏlishi bevosita kelib chiqadi.

Ta’rif. (X, ), (X’ , ’) gomomorf algebralar berilgan bŏlsin. Agar  : X  X’ gomomorfizm biektsiya bŏlsa, u holda (X, ) va (X’ , ’) algebralar izomorf ,  biektsiya esa berilgan algebralar izomorfizmi deyiladi.

Ravshanki, agar  : X  X’ - izomorfizm bŏlsa, u holda  ^-1 : X  X’ akslantirish ham izomorfizm bŏladi.

(X, ), (X’ , ’) algebralar orasida izomorflik munosabatini biz (X, )  (X’ , ’) kabi belgilaymiz.

Masalan, (R⁺ , ,1) (R ,+, 0) ekanligini kŏrsatish uchun  : R⁺  R sifatida (x) = ln x, x R⁺ , funktsiyani olamiz, u holda x,y R⁺ uchun (xy) = ln(xy)= lnx+lny =(x )+ (y) ŏrinli bŏladi.

Biz isbotlagan biektiv funktsiyalar xossalaridan izomorflik munosabati ekvivalentlik munosabati bŏlishi kelib chiqadi.
Algebraik sistemalar uchun ham tur, gomorfizm va izomorfizm kabi tushunchalarni tabiiy ravishda kiritish mumkin. Demak turli tabiatdagi algebraik sistemalarga yagona nuqtai nazaradan qarash maksadga muvofiqdir. Algebralar va algebraik sistemalarni tadqiq qilish osonlashtirishda izomorfizm tushunchasi katta rol ŏynaydi beradi. Izomorfizm nafaqat asosiy tŏplam tuzilishini, balki algebraik xossalarni strukturasini ŏzgartirmaydi. Izomorf bŏlgan algebraik sistemalarni algebraik xossalarini strukturasi bir xil bŏlgani uchun, ularni tashkil qilgan elementlar tabiatiga e’tibor bermasdan yagona nuqtai nazardan qaralishi mumkin. Bu esa abstrakt algebrani yutug’i deb hisoblanadi va algebrani zamonaviy matematikaning tiliga aylanishiga asosiy sabab bŏldi.