Diskret matematika va matematik mantiq

K.Gyodel, S.K.Klini (1957), E.L.Post (1943-1947), X.Rodjers (1972), ingliz

olimi A.Tyuring (1936-1937), rus olimlari A.A.Markov (1947-1954, 1958,

1967), A.N.Kolmogorov (1953, 1958, 1965), Yu.L.Yershov (1969-1973),

A.I.Malsev (1965,) D.A.Traxtenbrot (1967, 1970-1974), P.S.Novikov (1952),

Yu.V.Matiyasevich (1970-1972) kabi olimlarning xizmatlari benihoyat kattadir.

Masalan, S.Klini algoritm yordamida hisoblanuvchi qismiy funksiyalar qismiy rekursiv funksiyalardir degan g‘oyani ilgari surdi.

A.Tyuring va E.Post (1936) ideallashtirilgan hisoblash mashinalari atamasida birinchi bo‘lib, bir-biridan bexabar holda, algoritm tushunchasiga aniqlik kiritishdi. Post va Tyuring algoritmik jarayonlar ma’lum bir tuzilishga ega bo‘lgan “mashina” bajaradigan jarayonlar ekanligini ko‘rsatdilar. Ular o‘sha paytdagi

18

matematikada ma’lum bo‘lgan barcha algoritmik jarayonlarni bajara oladigan “mashinalar” sinfini hosil qilib, ularga aniq matematik atamalar yordamida ta’rif berdilar. Post va Tyuring ushbu mashinalar yordamida hisoblanuvchi barcha funksiyalar sinfi barcha qismiy rekursiv funksiyalar sinfi bilan bir xil ekanligini ko‘rsatdilar. Natijada, Chyorch tezisining yana bitta fundamental tasdig‘i hosil bo‘ldi.

S.Klini va E.Post birgalikda rekursivlik nazariyasini yaratdilar va rekursiv funksiyalar nazariyasini taraqqiy ettirdilar. Ular qisman rekursiv funksiyalar tushunchasini kiritishdi.

Dastlab faqat matematik mantiq, algebra, matematik analiz, matematika asoslari, ehtimollar nazariyasi, geometriya, topologiya, sonlar nazariyasi, modellar nazariyasi kabi matematika fanlarida tatbiq etib kelingan algoritmlar nazariyasi

XX asrning 40- yillaridan boshlab hisoblash matematikasi, kiberneteka, axborot nazariyasi, iqtisodiyot, psixologiya, matematik lingvistika, tibbiyot fanlari va diskert texnikada keng qo‘llanilmoqda.

So‘nggi davrlarda matematik mantiqni texnikaga juda samarali tatbiq etish imkoniyatlari borligi ma’lum bo‘ldi.

Matematik mantiqni diskret texnikaga tatbiqi natijasida uning texnik mantiq bo‘limi vujudga keldi. Bu sohada E.Post, V.I.Shestakov, K.Shennon (1916 y.t.), A.Nakashima, M.Xanzava, S.Klini, O.B.Lupanov (1932 y.t.), S.V.Yablonskiy (1924 y.t.), V.B.Kudryavsev, Yu.I.Juravlyov, V.I.Levenshteyn, V.V.Glagolev, F.Ya.Vetuxnovskiy, Yu.L.Vasilyev va boshqa olimlar o‘z ilmiy izlanishlari bilan uning taraqqiy etishiga ulkan hissa qo‘shganlar.

Matematik mantiqni texnikaga qo‘llashni birinchi bo‘lib rus fizigi P.Erenfest (1910) va gidrotexnika qurilishlari bo‘yicha yetuk mutaxassis N.M.Gersevanovlar amalga oshirganlar.

K.Shennon hisoblash mashinalarini yaratishning asosiy metodi sifatida mantiq algebrasini bilgan, u informatsiya va informatsiyani uzatishning matematik nazariyalarni yaratdi, elektron tarmoqlardagi “1” va “0” binar munosabatlar bilan matematik mantiqdagi ikkilik (1 va 0) qiymatlarining mos kelishini va qanday qilib “mantiq mashinasini” yaratishni ko‘rsatdi va hokazo.

Kontakli va rele-kontakli sxemalarga mantiq algebrasini tatbiq etishning isbotini birinchi bo‘lib V.I.Shestakov va K.Shennonlar berdi. A.Nakashima va M.Xanzava matematik mantiqni diskret texnika masalalarini yechishda qo‘llash metodlarini yaratdilar. S.Klini diskret qurilma modelini (chekli avtomat modeli)

yaratgani tufayli, matematik mantiqni xotirali diskret qurilmalarni loyihalashda ishlatish imkoni yuzaga keldi.

Moskva davlat universiteti diskret matematika maktabining asoschilaridan biri O.B.Lupanovning asosiy ishlari matematik kibernetika va matematik mantiqqa

bag‘ishlangan. U murakkab boshqaruvchi sistemalarning qonuniyatlarini, kontakt sxemalar va funksional elementlardan

asimptotik yasalgan

sxemalarni (umuman asosiy boshqaruvchi sistemalarni), eng yaxshi asimptotik sintez metodlarini va lokal kodlash prinsipini ishlab chiqdi.

S.V.Yablonskiy optimal sxemalarni sintez qilish va hisoblash qurilmalarini yasash metodini yaratdi.

Mantiq algebrasi elektr sxemalarni loyihalashda va tekshirishda, avtomatik hisoblash mashinalarini loyihalash va programmalashda, diskret avtomatlarni mantiqiy loyihalashda, EHM elementlari va qismlarini loyihalashda, har xil texnik sistemalar, qurilmalar va avtomatik mashinalarni analiz va sintez qilishda keng miqyosda tatbiq etiladi. Matematik mantiq fani elektron hisoblash mashinalarining vujudga kelishiga va uni mukammallashtirishga katta hissa qo‘shdi.

Kombinatorika muammolari bilan XI-XV asrlarda Sharq olimlari, jumladan, Bxaskara Acharya, Nosir ad-Din-Muhammad at-Tusiy, Ali Qushchi, Umar Hayyom shug‘ullanib, olamshumul ahamiyatga ega bo‘lgan ilmiy natijalar olishgan.

Ilmiy adabiyotda Paskal uchburchagi deb ataluvchi sonlar jadvali Paskal nomi bilan atalishiga qaramasdan, bunday sonlar jadvali juda qadimdan

dunyoning turli mintaqalarida, jumladan, Sharq mamlakatlarida ham ma’lum bo‘lgan: Erondagi Tus shahrida (hozirgi Mashhadda) yashab ijod qilgan Nosir at- Tusiy XIII asrda bu jadvaldan foydalanib, ikkita son yig‘indisining natural darajasini hisoblash usulini o‘zining ilmiy ishlarida keltirgan bo‘lsa, g‘arbda Al- Kashi nomi bilan mashhur Samarqandlik olim Ali Qushchi butun sonning istalgan natural ko‘rsatkichli arifmetik ildizi qiymatini taqribiy hisoblashda bu jadvaldan foydalana bilgan. XVI asrga kelib G‘arbiy Yevropada bu sonlar uchburchagi haqida M. Shtifel arifmetika bo‘yicha qo‘llanmalarida yozgan va u ham butun sondan istalgan natural ko‘rsatkichli arifmetik ildizning taqribiy qiymatini hisoblashda bu uchburchakdan foydalana bilgan. 1556 yilda bu sonlar jadvali bilan N. Tartalya, 1631 yilda U. Otred ham shug‘ullanishgan. Faqatgina 1654

yilga kelib B. Paskal bu sonlar jadvali haqidagi ma’lumotlarni o‘zining “Arifmetik uchburchak haqidagi traktat” nomli asarida e’lon qildi.

Ixtiyoriy a va b haqiqiy sonlar hamda n natural son uchun (a  b)n ifodaning ko‘phad shaklidagi yoyilmasi XVII-XVII asrlarda yashagan Nyuton nomi bilan Nyuton binomi deb yuritiladi. Vaholangki, qadimgi greklar (a  b)n ifodaning qatorga yoyilmasini n ning faqat n  2 bo‘lgan holida bilishgan bo‘lsa, Umar Hayyom (1048-1122) va Ali Qushchi (1436 yilda vafot etgan) bu ifodani n  2 bo‘lgan natural sonlar uchun ham qatorga yoya bilganlar. Nyuton esa 1767 yilda yoyilma formulasini isbotsiz manfiy va kasr n sonlar uchun ham qo‘llagan.

Hozirgi vaqtda kombinatorik tahlil masalalari, asosan, uch turga bo‘linadi. Birinchi tur masalalar elementar kombinatorika masalalari deb yuritiladi va ular, ko‘pincha, berilgan to‘plam elementlari bilan bog‘liq mumkin bo‘lgan yechimlar

sonini aniqlashga keltiriladi. Mumkin bo‘lgan kombinatorik yechimlar, ularning mavjudligi va shu kabi masalalar ikkinchi tur masalalar jumlasiga kiradi. Uchinch tur kombinatorik masalalar vositasida mumkin bo‘lgan kombinatorik yechimlar orasidan qandaydir maqsadni ko‘zlab optimal yechim topish bilan bog‘liq savollarga javob topishga harakat qilinadi.

Kombinatorik tahlil diskret matematikaning nazariy asoslaridan biridir. Bu tahlilni amalga oshirishda tanlashlar sonini bevosita aniqlash usuli, hosil qiluvchi funksiyalar usuli, mantiqiy, ekstremal, geometrik, jadval-sxema va boshqa usullardan foydalaniladi.