1Mantiqiy funksiyalarning berilish usullari. Bul algebrasining asoslari

1Mantiqiy funksiyalarning berilish usullari.
2.Bul algebrasining asoslari.
Klassik matematikada funksiya ikki usulda beriladi: analitik (formula yozuvi) va jadval (masalan, lug‘atlarda beriladigan funksiyalar qiymatining jadvali). Mantiqiy funksiyalar ham shunday usullarda berilishi mumkin.

Jadval usulida, argumentlar qiymatining mumkin bo‘lgan o‘rin almashtirishlari va ularga mos keluvchi mantiqiy funksiyalarning qiymatlari ifodalangan rostlik jadvali tuziladi. Bunday o‘rin almashtirishlarning soni chekli bo‘lganligi uchun, rostlik jadvali funksiya qiymatini argumentning ixtiyoriy qiymati uchun aniqlashga imkon beradi (funksiyaning qiymatlarini argumentlarning barcha qiymatlari uchun emas, ba’zi bir qiymatlari uchun aniqlaydigan matematik funksiyalar jadvalidan farqli ravishda).

Bir argumentli mantiqiy funksiyalar uchun rostlik jadvali 9-rasmda keltirilgan. Bir argumentning hammasi bo‘lib to‘rtta funksiyasi mavjud.

X argumenti


Funksiyalar


f0(x)


f1(x)


f2(x)


f3(x)


0

0

0

1

1

1

0

1

0

1

9-rasm


Agar funksiya argumentlarining soni n ga teng bo‘lsa, argument qiymatlarining turli o‘rin almashtirishlari soni 2n ni tashkil qiladi, n argumentning turli funksiyalari soni 22n .Masalan, п= 2 da argumentlar qiymatining o‘rin almashtirishlari soni 22 = 4 ga, funksiyalar soni esa 24 = 16 ga teng. Ikki argumentli funksiya uchun rostlik jadvali 3-jadvalda keltirilgan

Mantiqiy funksiya analitik usulda ham berilishi mumkin. Odatdagi matematikada funksiyani analitik usulda berilishi deganda, funksiyaning argumentlari biror matematik amal orqali bog‘langan matematik ifodalar ko‘rinishida berilishini tushunamiz.

Shunga o‘xshash, mantiqiy funksiyalarni analitik usulda berish uchun funksiya argumentlari ustida mantiqiy amallar qanday tartibda bajarilishini ko‘rsatuvchi mantiqiy ifoda ko‘rinishida yozilishi kerak .

Bir argumentning funksiylari qo‘iydagi ifodalar orqali beriladi:
f0(х), f1(х) va f3(x) funksiyalarini amalga oshiruvchi qurilmalar trivial deyiladi. 10- rasmdan ko‘rinib turibdiki:

f0(х) funksiyani tuzish uchun, sxemaning umumiy nuqtasiga ulanishli chiqish va kirish orasida oraliq bo‘lishi kerak;

f1(х) funksiyani tuzish uchun — kirish va chiqishni ulash;

f3(х) funksiyani tuzish uchun — chiqishning man.1 ga mos keluvchi kuchlanish manba’si bilan ulanish talab qilinadi.
X f0(x) X f1(x) X f3(x)

+


- 10-rasm

Shunday qilib, bir argumentli barcha funksiyalar orasidan faqat f2(x)=x funksiya amaliy axamiyatga ega (mantiqiy YO‘Q).

Rostlik jadvali va funksiya tenglamasidan tashqari Karno kartasi usuli ham mavjud.

Karno kartasi elementlar kirishining barcha mumkin bo‘lgan 2n ta holatiga mos keluvchi 2n holat – kataklardan iborat. Kirishlar ikki guruhga bo‘linadi, va bunda kartaning ustunlariga bir guruhning barcha kombinatsiyalari, qatoriga esa boshqa guruhning kombinatsiyalari mos keladi. Bunda kirish signallarining kombinatsiyalari shunday joylashadiki, qo‘shni bo‘lgan ustun va qatorlar faqat bir kirishning holati bilan farqlanadi. Har bir kirish 1,2,4,Й,.,.,2n vazniga ega bo‘lganligi uchun, har bir qator va ustun berilgan holatda 1 qiymatga teng bo‘lgan kirish talmoqlarining yig‘indisiga teng bo‘lgan og‘irlikka ega bo‘ladi. Har bir katak, shu katakni tashkil qiluvchi ustun va qator vaznlarining yig‘indisiga bo‘lgan nomer bilan birikmaga mos keladi. Chiqishdagi signalning birlik belgilanishi tutash chiziq orqali belgilanadi. Karta kataklarining birikmasi, bitta o‘zgaruvchining qiymati bilan farq qiladigan, qo‘shni to‘plamlarni o‘z ichiga oladi. Quyi o‘ng tomonida joylashgan raqamlar to‘plam nomerini bildiradi. Chetki kataklar ham qo‘shni hisoblanadi. Har bir katakning o‘rta qismida, aniqlanayotgan funksiyaning shu to‘plamda teng bo‘ladigan qiymati ko‘rsatilgan. Karno kartalarining soni kirish o‘zgaruvchilar to‘plamlarining soni bilan aniqlanadi. 11-rasmda 2,3,4 o‘zgaruvchili funksiyalarining berilishi uchun Karno kartalari keltirilgan.


11-rasm


Oldinda aytilganiday barcha raqamli qurilmalar sodda mantiqiy elementlar asosida quriladi. Asosan bu mantiqiy elementlarni mantiqiy algebraning sodda funksiyalari bajaradi. Eng sodda mantiqiy elementlar bir argumentli funksiyalar orqali tavsiflanadi. Eng ko‘p qo‘llaniladigan mantiqiyfunksiyalarni va ularning sxemalardagi tasvirlarini ko‘rib chiqamiz. Barcha bir argumentli funksiyalar orasidan faqat (mantiqiy YOQ) funksiya amaliy axamiyatga ega. Invertor uchun rostlik jadvali quyidagi ko‘rinishda bo‘ladi .

x

f

1

0

0

1

Invertorning grafik tasviri 12-rasmda ko‘rsatilgan.

 

12-rasm.


Ikki argumentli funksiyani amalga oshirish ham katta amaliy axamiyatga ega. Barcha mumkin bo‘lgan funksiyalar 3.3-jadvalda keltirilgan. Biz hammasi bo‘lib 16 ta turli funksiyalarni hosil qilamiz. 13-jadval.


Argumentlar


X1


0

0

1

1

X2


0

1

0

1

Funksiyalar


f0


0

0

0

0

f1


0

0

0

1

f2


0

0

1

0

f3


0

0

1

1

f4


0

1

0

0

f5


0

1

0

1

f6


0

1

1

0

f7


0

1

1

1

f8


1

0

0

0

f9


1

0

0

1

f10


1

0

1

0

f11


1

0

1

1

f12


1

1

0

0

f13


1

1

0

1

f14


1

1

1

0

f15


1

1

1

1

14-jadvalda funksiyalarning nomi, shartli belgilanishi va bu funksiyalarni amalga oshiruvchi mantiqiy elementlarning nomlari keltirilgan.

14. Jadval

Funksiya

Funksiyaning nomlanishi

MND Sh

VA, YOKI, YO’Q bazislarida ifodalanish

Funksiyaning belgilanishi


Mantiqiy elementlarning nomi


Shartli belgilashlar


f0


Doimiy

0

0

Nolning generatori

0

f1


Konunktsiya


x1x2


x1x2


x1x2


VA elementi

x1
x2

f2


Teskari inkor


x1x2


x1x2


x1=x2


Inkor


x1

x2


f3


X ni takrorlash


x1x2 v x1x2


x1


x1

x1

f4


Inkor

x1x2

x1x2


x1=x2


Inkor


x1

x2


f5


X ni takrorlash


x1x2 v x1x2


x2


x2

x2

f6


2 modul asosida qo’shish


x1x2 v x1x2


x1x2 v x1x2

f7


Dizyunktsiya


x1x2 v x1x2

v x1x2

x1x2


x1 v x2


YOKI elementi

1

x1


x2


f8


Veb funktsiya (Pirs strelkasi)


x1x2


x1x2


x1x2


YOKI –YOQ Elementi

1

x1


x2


f9


Ekvivalentlik


x1x2 v x1x2


x1x2 v x1x2


x1=x2


Ekvivalentlik

1

x1


x2


f10


X invers

x1x2 v x1x2

x2


x2


YOQ elementi

x2

16 ta funksiyadan biz uchun f1, f6, f7, f8 и f14 lari asosiy bo‘ladi

Tayanch iboralar: mantiqiy inkor, mantiqiy ko‘paytirish, mantiqiy qo‘shish, mantiqiy ekvivalentlik, kon’yunksiya, dez’nksiya, implekatsiya, mantiqiy elementlar, minitermlar.
Kompyuterlarni loyihalashtirish asosida Bul algebrasi yotadi. Unda mantiqiy ifodalar faqat ikki qiymatni qabul qiladi: “chin” – 1 yoki “yolg‘on” – 0. Mantiqiy ifodalar mantiqiy о‘zgaruvchilarning funksiyasidir, ularni A, V, S vahokazo kabi belgilanadi, ularning har biri 0 yoki 1 qiymatini oladi. K mantiqiy о‘zgaruviga 2K 0 va 1 lardan tashkil topgan mantiqiy kombinatsiya tо‘g‘ri keladi, masalan K = 2 bо‘lganda AV = 00, 01, 10, 11 bо‘ladi. О‘zgaruvchilarning har bir kombinatsiyasi uchun F mantiqiy funksiya 0 yoki 1 qiymatni egallashi mumkin. K о‘zgaruvchi uchun turli mantiqiy funksiyalar mavjud. Agarda K = 2 bо‘lsa, u holda l 2= 16, K = 4 bо‘lganda esa l 4= 65536 bо‘ladi vahokazo.

K mantiqiy funksiya kо‘pligini uchta asosiy mantiqiy operatsiylar yordamida hosil qilish mumkin: 1) mantiqiy inkor ( - ); 2) mantiqiy qо‘shish (+); 3) mantiqiy kо‘paytirish ( ). Mantiqiy ifodalarni ekvivalentligini belgilash uchun (=) belgi ishlatiladi. 2.1 jadvalda keltirilgan mantiqiy operatsiyalarni jadval kо‘rinishidagi ifodalanishi berilgan.

2.1 jadval

A

V

F =A+B

F =A B

0

0

1

1

0

1

0

1

1

1

0

0

1

0

1

0

0

1

1

1

0

0

0

1

Keltirilgan operatsiyalar uchun qator aksioma va qonunlar tegishlidir, ularning asosiylari 2.2 jadvalda keltirildi.

2.2 jadval

Bul algebrasining aksioma va qonunlari

Algebraik ifodasi

Aksiomalar (tengliklar)

1 + A = 1

0 A = 0

0 + A = A

1 A = A

A + A = A

A A = A

Kommutativlik qonuni

A + B = B +A

A B = B A

Assotsiativlik qonuni

A + B + C = A + (B + C)
Kommutativlik qonuni

A B C = A (B C)

Distributivlik qonuni