Diskret matematika va matematik mantiq

ab  ba , (ab)c  a(bc) ;

• mantiqiy qo‘shish amalini «+» belgi bilan begilash, bu operatsiya ham kommutativlik va assotsiativlik xossalariga ega:

x  y  y  x , (x  y)  z  x  ( y  z) ;

• hech qanday mazmunga ega bo‘lmagan sifat formasini 0 (mantiqiy 0) bilan belgilash;
• mumkin bo‘lgan sinflarni o‘z ichiga olgan sifat formasini 1 (mantiqiy 1) bilan belgilash; 0 va 1 ushbu xossalarga ega:

a  0  a , a 1  a ;

• a sinfning inkorini a1 sinf bilan belgilash;
• qo‘shish, ko‘paytirish va inkor amallaridan tashqari ekvivalentlik amalini kiritilgan va uni «=» simvol bilan belgilangan. Bu amal uchta qoidaga bo‘ysunadi:

a) agar a  b tenglikning chap va o‘ng tomonlariga bir xil sinflarni qo‘shsak, u holda tenglik o‘rinli, ya’ni a  c  b  c bo‘ladi; b) agar, a  b bo‘lsa, u holda ad  bd bo‘ladi; d) agar, a  b bo‘lsa, u holda a1  b1 bo‘ladi, bu yerda a1  a emas , b1  b emas .

XIX asrning oxirida matematik nazariyalar shunday rivojlandiki, endi mantiq masalalari matematikaning o‘zida ham muhim ahamiyatga ega bo‘lib, mavjud mantiqiy qurollar matematika talablariga javob bera olmay qoldi. Ayrim matematik muammolarni yechishdagi qiyinchiliklar ularning mantiqiy tabiatiga bog‘liqligi aniqlandi. Shuning uchun ham matematik mantiq tor algebraik doiradan chiqib, jadal rivojlana boshladi. Bu yo‘nalishda birinchi bo‘lib G.Fryoge

matematigi J.Peano (1858-1932) tadqiqotlar olib borishdi, ular mantiqni arifmetika va to‘plamlar nazariyasini asoslash uchun

va italyan matematik qo‘lladilar.

Matematik mantiqning keyingi taraqqiyoti uchun B.Rassel va A.Uaytxedning uch tomlik «Matematika prinsiplari» (1910-1913 y.), D.Gilbertning ishlari, hamda K.Gyodelning tadqiqotlari juda muhim ahamiyatga ega bo‘ldi. Matematik mantiqning rivojlanishida Rossiya matematiklari I.I.Jegalkin, V.I.Glivenko, A.N.Kolmogorov, P.S.Novikov, A.A.Markov va boshqalar o‘zlarining ulkan hissalarini qo‘shdilar.

1903 yili B.Rasselning Londonda nashr etilgan «Matematika prinsiplari» kitobida mulohazalar va sinflar hisob nazariyasi ishlab chiqildi. B.Rasselning A.Uaytxed bilan hamkorlikda yozilgan 3 tomlik «Matematika prinsiplari» kitoblari matematik mantiq fanining rivojlanishida katta rol o‘ynadi. Bu kitoblarda mulohaza, sinf va predikatlar hisobi deyarli to‘liq aksiomalashtirilgandi va

formallashtirildi. Ular hozirgi vaqtda o‘rganilayotgan matematik mantiq ko‘rinishini yaratdilar.

D.Gilbert va nemis olimi V.Akkerman 1928 yilda chop etilgan «Nazariy mantiqning asosiy xususiyatlari» kitoblari matematik mantiqning yanada rivojlanishida muhim ahamiyat kasb etdi. Bu kitobning mualliflari mantiqiy amallarda formallashtirish metodini tatbiq etib katta yutuqqa erishdilar.

Bul, Shryoder va Poreskiyning mantiq algebrasiga tayanib, I.I.Jegalkin logik qo‘shish va logik ko‘paytirish amallarini quyidagicha aniqladi:

1) 0  0  0 , 0 1  1, 1 0  1, 11  0 ;

2) 0 0  0 , 01  0 , 1 0  0 , 11  1.

a  a  0 va a  a  a kelib

Jegalkin

sistemasida

Logik (mantiqiy) qo‘shish va ko‘paytirish amalidan chiqadi.

Mantiqiy operatsiyalarning simvolik ko‘rinishlari quyidagicha bo‘ladi:

p  p 1; p  p ; p  q  p  q  pq ;

kvantori

degan

p  q  1 p  pq ; p  q  1 p  q .

Jegalkin simvolik mantiqqa umumiylik va mavjudlik tushunchalarni ham kiritdi va predikatlar algebrasini yaratdi.

XX asrning 50- yillarida ko‘p qiymatli mantiq sohasida ilmiy izlanishlar olib borildi. Ko‘p qiymatli mantiqda mulohazalar chekli (3 va undan ko‘p) va cheksiz chinlik qiymatlari oladi. Matematik mantiqning bu bo‘limining asoschilaridan biri

polyak olimi Ya.Lukasevich (1878-1954) hisoblanadi. U dastlab (1920) uch qiymatli, 1954 yilda to‘rt qiymatli va nihoyat cheksiz qiymatli mantiqni yaratdi.

Ko‘p qiymatli mantiq problemalari (muammolari) bilan E.Post, S.Yaskovskiy, D.Vebb, A.Geyting, A.N.Kolmogorov, D.A.Bochvar, V.I.Shestakov, G.Reyxenbax, S.K.Klini, P.Detush-Fevriye va boshqa olimlar shug‘ullanganlar.

Konstruktiv matematikaning rivojlanishi konstruktiv mantiq masalalarini yechish usullarini ishlab chiqish vazifasini qo‘ydi. Bu sohada A.A.Markov, N.A.Shanin hamda shogirdlarining xizmatlari kattadir.

Diskret matematikaning katta bo‘limlaridan biri algoritmlar nazariyasi hisoblanadi. Algoritm so‘zi IX asrda yashagan o‘z zamonasining buyuk

matematigi vatandoshimiz Muhammad al-Xorazmiy ismining lotincha Algorithmi formasidan kelib chiqqan.

Algoritmlar nazariyasi algoritmlarning umumiy xususiyatlarini o‘rgatuvchi diskret matematikaning bir bo‘limidir.

XX asrning 20- yillarida birinchi bo‘lib intuitsionistlar vakillari L.Brauer va olmon olimi G.Veyler (1934) algoritm tushunchasini o‘rganishga kirishganlar. Algoritmlar nazariyasining asoschilaridan biri bo‘lgan A.Chyorch 1936 yilda hisoblanuvchi fuksiya tushunchasiga dastlabki aniqlikni kiritdi va quyidagi tezisni ilgari surdi: natural argumentlarning barcha qiymatlarida hamma joyda aniqlangan hisoblanuvchi funksiyalar bilan umumiy rekursiv funksiyalar ekvivalentdir (bir xildir). U hisoblanuvchi funksiya bo‘lmagan funksiyani ko‘rsatdi.

Algoritmlar nazariyasining keyingi rivojlanishiga amerikalik olimlar