Algoritmlarning mantiqiy asoslari

ALGORITMLARNING MANTIQIY ASOSLARI
Mantiq - fikrlash shakllari va usullari haqidagi fan.
Tafakkurning asosiy shakllari tushuncha, bayon va xulosadir.
Tushuncha - ob'ektning asosiy, muhim belgilarini (masalan, to'rtburchak, kompyuter) o'rnatadigan fikrlash shakli.
Mulohaza - bu fikrlash shakli bo'lib, unda biror narsa tasdiqlanadi yoki inkor etiladi, atrofdagi dunyo haqidagi tushunchasini shakllantirish (masalan, printer - chop etish moslamasi, "a" harfi - unli tovush).
Xulosa - bu fikrlash shakli bo'lib, uning yordamida bir yoki bir nechta mulohazalardan yangi mulohaza - xulosa chiqarish mumkin (masalan, teng yonli uchburchakning barcha burchaklari teng → bu teng tomonli uchburchak).
Algoritmlarning tarkibiy qismlari mantiqiy shartlar bo'lib, ularning qiymatlarini hisoblash mantiq algebrasining aksiomalariga muvofiq amalga oshiriladi.
Formal mantiqning asoschisi Aristotel (miloddan avvalgi IV) boʻlib, matematik mantiq asoslarini ingliz matematigi Jorj Bul ishlab chiqqan. Matematik mantiqning asosini mulohazalar algebrasi tashkil qiladi. Mantiq algebrasi EHMning asosiy komponentlarini - kodlovchi, dekoder, summatorni qurishda qo'llaniladi.
Mantiqiy mulohaza - bu aniq yoki noto'g'ri deb aytish mumkin bo'lgan har qanday rasmiy jumla.
Faqat bitta fikrni o'z ichiga olgan oddiy mulohaza mantiqiy o'zgaruvchidir. U lotin alifbosining bosh (katta) harflari bilan belgilanadi (masalan, A, B, C) va faqat ikkita TRUE (1) va FALSE (0) qiymatlarini qabul qilishi mumkin.
Mulohazalarda ma'lum mantiqiy amallar bajarilishi mumkin, buning natijasida yangi birikma (murakkab) gaplar olinadi.
Mantiqiy amallar mantiqiy harakatlardir. Bularga quyidagilar kiradi:
1. Kon'yunktsiya, ya’ni birlashtiruvchi (mantiqiy ko'paytirish - VA) - "&" va "˄" belgisi. Natija rost bo'ladi, agar ikkala asl mulohaza ham rost bo'lsa.

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

2. Dizyunksiya (mantiqiy qo‘shish - OR) - "˅" belgisi. Natija hech bo'lmaganda bittasi rost bo'lsa, rost bo'ladi.

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

3. Inversiya (mantiqiy inkor - EMAS) - "¬" va "¯" (Ā) belgilari. Agar dastlabki mulohaza yolg’on bo'lsa, natija rost bo'ladi va aksincha, agar dastlabki mulohaza rost bo'lsa, natija yolg’on bo'ladi.

А	Ā
0	1
1	0

4. Ekvivalentlik – “~” belgisi. Ikkala mulohaza ham rost yoki yolg’on bo'lsa, natija rost bo'ladi.

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

5. Implikatsiya (mantiqiy oqibat) - "→" belgisi. Natija yolg'on bo'ladi, qachonki faqat rost mulohazadan keyin yolg’on mulohaza kelib chiqsa. Qolgan payt hammasi rost bo’ladi.

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

Mantiqiy amallarni bajarishda ularni bajarishning quyidagi tartibi aniqlanadi: inversiya, konyunksiya, diszyunksiya. Belgilangan tartibni o'zgartirish uchun qavslar ishlatiladi.

Masalan, A ۷ B & C → (A ۷ B) & C
Har bir qo‘shma mulohaza mantiqiy ifoda (formula) sifatida ifodalanishi mumkin, u mulohazalarni bildiruvchi mantiqiy o‘zgaruvchilar va mantiqiy funksiyalarni bildiruvchi mantiqiy amallarning belgilarini o‘z ichiga oladi.
Mantiqiy ifodalarning yechimi haqiqat jadvallari - jadvallar shaklida qayd etiladi, ulardagi harakatlar mantiqiy ifoda o'zgaruvchilarning barcha mumkin bo'lgan to'plamlari uchun qanday qiymatlarni olishini ko'rsatadi.
Haqiqat jadvallarini tuzish uchun sizga kerak bo'ladi:

• 
  jadvaldagi qatorlar sonini aniqlash ( 2ⁿ, n - o'zgaruvchilar soni);
  
• 
  jadvaldagi ustunlar sonini aniqlash (= mantiqiy o‘zgaruvchilar soni + mantiqiy amallar soni);
  
• 
  mantiqiy amallarni bajarish ketma-ketligini belgilash;
  
• 
  ustunlar nomlari va boshlang'ich mantiqiy o'zgaruvchilarning mumkin bo'lgan qiymatlari to'plamini ko'rsatadigan jadval tuzish;
  
• 
  haqiqat jadvalini ustunlar bo‘yicha to‘ldirish.
  

Haqiqat jadvallarining oxirgi ustunlari bir xil bo'lgan mantiqiy ifodalar teng kuchli deb ataladi va "=" kabi belgilanadi.
Mulohazalar algebrasida mantiqiy amallarning quyidagi xossalarini qo'llagan holda, ba'zi mulohazalarni ekvivalentlari bilan boshqa mulohazalar bilan almashtirib, bir xil o'zgarishlarni amalga oshirish mumkin:

1.