Ózbekstan Respublikası Joqarı hám orta arnawlı Bilimlendiriw ministirligi Berdaq atındaǵı Qaraqalpaq mámleketlik universiteti

Bul algebrası

Zamanagóy kompyuterlerde keń qollanılatuǵın hám ekilik sanaq sistemasına tiykarlanǵan logikalıq ózgeriwshiler ústinde matematikalıq ámeller orınlaw kompleksi. Bul algebrasi, bul pán sipatinda qáliplestirgen matematikalıq alım Jorj Bul (1815-1864) húrmetine onıń atı menen atalǵan. Bul algebrasida tiykarınan logikalıq kóbeytiw, logikalıq qosıw hám ayrish, hám de, biykar funktsiyaları ústinde ámeller atqarıladı. Bul ámeller arqalı bolsa qálegen basqa bul ámellerin keltirip shıǵarıw (dúziw) múmkin.

Tiykarǵı operatsiyalar: Bul algebraniń tiykarǵı operatsiyaları kon'yunkciya, ajıratiw hám biykarlaw etiw bolıp tabıladı. Bul logikalıq operatsiyalar tiyisli ekilik operatorlar hám yamasa, sonıń menen birge, logikalıq operatorlar dep atalatuǵın birden-bir operator tárepinen ańlatiladı. X hám Y ózgeriwshileri menen tiykarǵı logikalıq operatsiyalar tómendegishe anıqlanadı:

Logikaliq ańlatpalar	Operator	Belgilew
Birigiw	Hám	х ∧ у
Dizunkciya	Yaki	х ∨ у
Biykarlaw	yaq	¬ х

Eger haqıyqat 0 hám 1 bahaları retinde aytilsa, bul operatsiyalar ápiwayı arifmetik operatsiyalar menen ańlatılıwı múmkin (bul jerde x + y qosımsha isletiledi hám xy kóbeyiwden paydalanadı ) yamasa maksimal minimal funktsiyalar:

Tek ǵana biykar etiw hám basqa eki operatsiyalardan biri tómendegi identifikaciya qılıw ushın tiykar bolıp xızmet etedi, bul bolsa kon'yunktsiyani biykar etiw hám ajırasıw kózqarasınan anıqlawǵa múmkinshilik beredi hám kerisinshe ( De Morgan nızamları ):

Monoton nızamlar

Bul algebrasi ádetdegi algebra menen birdey nızamlardı qandiradi, eger siz qosılsa hám ko'beytirilse. Atap aytqanda, tómendegi nızamlar hár eki algebra túri ushın da keń tarqalgan.

Tómendegi nızamlar ádetegi algebra emes, bálkim Bul algebrasında ámelge asırıladı:





Joqarıdaǵı hám keyingi súwretlerde keltirilgen ápiwayı logikalıq funktsiyalardı ámelge asırıwshı júdá kishi elektron apparatlar-ventillar dep ataladı.Ventillar-tranzistorlar tiykarında qurıladı:

Bull funktsiyalarında, ádetdegi algebra funktsiyaları sıyaqlı bir, eki, ush hám taǵı basqa sandaǵı ózgeriwshilerge ıyelewi múmkin. Mısalı : ápiwayı bir funktsiya f-ni tómendegishe anıqlawtirishimiz múmkin, f (A) =1, eger A=0 bolsa, f (A) = 0, eger A=1 bolsa. Bunday funktsiya NE funktsiyası boladı.

n-ta ózgeriwshige baylanıslı bolǵan bull funktsiyası ózgeriwshileriniń ámeldegi kombinatsiyaları sanı 2 n-taga teń boladı. Bull funktsiyanıń barlıq bahaların bolsa, 2 n-ta qatarǵa iye bolǵan keste járdeminde jazıp shıǵıw múmkin, bunday keste Bul' algebrasida xaqiqat kestesi dep ataladı. Joqarıda kórip ótilgen elementler menen birge keltirilgen kesteler, olardıń xaqiqat kesteleri esaplanadı. НЕ funktsiyası bir ózgeriwshili, И hám ИЛИ funktsiyaları bolsa eki ózgeriwshili funktsiyalar bolıp tabıladı. Eki ózgeriwshili funktsiyalardıń xaqiqat kestelerinde, ózgeriwshilerdiń kombinatsiyaları ádetde 00, 01, 10 hám 11 izbe-izlilikde jazıladı. Bunday funtsiyalarni tolıq xarakteristikalaw ushın 22=4 razryadlı ekilik san kerek boladı hám ol xaqikat kestesiniń nátiyjeler ústinin vertikal' tárzde oqıw menen payda etinadi. Sonday etip, И - bul 0001, ИЛИ - 0111, НЕ-И - 1110 hám НЕ-ИЛИ - 1000 boladı. 4 razryadlı ekilik sanlar izbe-izlining 16 qıylı (0000, 0001, 0010, …, 1111) kombinatsiyasın jazıw múmkin, bul bolsa eki ózgeriwshili funktsiyanıń 16 -ti turi ámeldegi ekenligin ańlatadı. Ádetdegi algebrada bolsa eki ózgeriwshili funktsiyanıń sheksiz sandaǵı xillari bar. Bunday funktsiyalardı xesh birin, ózgeriwshileriniń barlıq múmkin bolǵan bahaları kestesi járdeminde jazıp bolmaydı, sebebi bul ózgeriwshilerdiń bahaları sanı da - sheksiz boladı.

Úsh ózgeriwshili M=f (A, V, S) bul' funktsiyasın joqarıda kórip ótilgen sxemalar járdeminde qanday ámelge asırıw múmkinligin kórip shıǵamız. Shárt - bul funktsiyanıń ma`nisi, onıń ózgeriwshileri quramında qaysı bir baha kóbirek bolsa, solnga teń bolsın. Aldın xaqiqat kestein tuzib alamız. Funktsiyanıń 1-ga teń bolǵan bahaları tiykarında tómendegishe jazıwdı payda etemiz.

Yaǵnıy ózgeriwshilerdiń kombinatsiyaları 011, 101, 110 hám 111 bolsa, funktsiya 1 bahanı (true), qalǵan xolatlarda bolsa 0 bahanı (false) qabıl eter eken. Bul funktsiyanı ámelge asırıw ushın ush kiriwge iye bolǵan ush I elementi, tórtew kiriwge iye bolǵan bir ИЛИ elementi hám ush ózgeriwshilerdi biykarların payda etip alıw ushın ush НЕ elementi kerek boladı. yaǵnıy ózgeriwshilerdiń kombinatsiyaları 011, 101, 110 hám 111 bolsa, funktsiya 1 bahanı (true), qalǵan basqa halarda bolsa 0 bahanı (false) qabıl eter eken. Bull funktsiyanı ámelge asırıw ushın ush kiriwge iye bolǵan ush elementi, tórtew kiriwge iye bolǵan bir ИЛИ elementi hám ush ózgeriwshilerdi biykarların payda etip alıw ushın ush НЕ elementi kerek boladı.

A	B	C	M
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

И, ИЛИ, НЕ elementlerden paydalanǵan túrde ózgeriwshileri kóp bolmaǵan qálegen bul funktsiyasınıń logikalıq sxemasın payda etiw izbe-izligin tómendegishe ańlatıw múmkin:

1. Berilgen funktsiyanıń shinliq kestesi tuzib alınadı.

2. Hár bir ózgeriwshiniń biykarın payda etip alıw ushın sxemaǵa invertorlar kiritiledi.

3. Xaqiqat kestesiniń 1-ga teń hár bir qatarı ushın sxemaǵa И elementleri kiritiledi.

4.И elementleriniń kiriwlerine kesteniń 1-ga teń qatarlarına sáykes keletuǵın ózgeriwshiler jalǵanadı.

5. Barlıq И elementleriniń shıǵıwların, ИЛИ elementiniń kiriwlerine jalǵanadı.

Bull izbe-izlik bul' funktsiyası (1) ańlatpa kórinisinde, yaǵnıy kóbeytpelaring-jıyındısı formasında keltirilgen qal ushın orınlı bolıp tabıladı. Bul mısalda, bul' funktsiyasın И, ИЛИ, НЕ elementlerden paydalanǵan túrde qanday ámelge asırıw kórip chiqilidi. Ámeliyatda bolsa, ádetde birdey ventillardan paydalanǵan halda, yaǵnıy birdey bazislar tiykarında sxemalardı qurıw ámelge asıriladı [2]. Sebebi integral sxemalardı islep shıǵıwda sonday jol tutılǵan. Bunıń kóp paydalı tárepleri bar. Kompyuterlerde logikalıq sxemalardı ámelge asırıwshı integral sxemalar НЕ, ИЛИ hám НЕ-ИЛИ bazislari tiykarında islep shıǵılǵan.

Logikalıq ámeller oy-pikirler algebrasi noqatı názerden shınlıq kesteleri menen tolıq xarakterlenedi. Egerde funskiyaning keste formada beriliwin eske alsaq, ol waqıtta oy-pikirler algebrasida da funksiya túsinigin anıqlawımız múmkin.

Táriyp: x₁, x₂, …, x_n oy-pikirler algerbasinin’ х₁, x₂, …, x_n argumentli f (X₁, x₂, …, x_n) funksiyası dep nol hám bir baha qabıl etetuǵın funksiyaǵa aytıladı jáne onıń X₁, x2, …, x_n argumentlarida nol hám bir bahalar qabıl etiledi.

Táriyp: F:{0, 1}n -> {o, 1} funksiya logikalıq algebraning funksiyası yamasa Bul funksiyası kompleksi Pn arqalı belgileymiz. Bir ózgeriwshili funksiyalar 4 bolıp, olar.Bir ózgeriwshili funksiyalar 4 bolıp, olar tómendegiler:

1. f₀ (x) =0 - áyne nolǵa teń funksiya yamasa áyne ótirik funksiya

2. f₁ (x) =x - áyne funksiya

3.- biykar funksiya

4. f (x) =1 - áyne birge teń funksiya yamasa áyne shın funksiya

Táriyp: Eger ózgeriwshiniń sonday a₁, a₂,.. ., a_i-1, a_i,.. ., a_n bahalar kompleksi ámeldegi bolıp, f (a₁, a₂,.. ., a_i-2; 1 a_i,.. ., a_n) =f (a₁, a₂,.. ., a_i-2; 0 a_i,.. ., a_n) munasábet atqarılsa, ol waqıtta xi ózgeriwshige f (x₁, x₂, …, x_n) funksiyanıń nomuhim (sohta) ózgeriwshisi, eger f (a₁, a₂,.. ., a_i-2; 1 a_i,.. ., a_n) ≠f (a₁, a₂,.. ., a_i-2; 0 a_i,.. ., a_n) munasábet atqarılsa, ol waqıtta xi ózgeriwshige f (x₁, x₂, …, x_n) funksiyanıń zárúrli (sohta emes) ózgeriwshisi dep ataladı.

Táriyp: Eger ózgeriwshiniń sonday a₁, a₂,.. ., a_i-2; 1 a_i,.. ., a_n bahalar kompleksi ámeldegi bolıp, f (a₁, a₂,.. ., a_i-2; 1 a_i,.. ., a_n) =f (a₁, a₂,.. ., a_i-2; 0 a_i,.. ., a_n) munasábet atqarılsa, ol waqıtta xi ózgeriwshige f (x₁, x₂, …, x_n) funksiyanıń nomuhim (sohta) ózgeriwshisi, eger f (a₁, a₂,.. ., a_i-2; 1 a_i,.. ., a_n) ≠f (a₁, a₂,.. ., a_i-2; 0 a_i,.. ., a_n) munasábet atqarılsa, ol waqıtta x_i ózgeriwshige f (x₁, x₂, …, x_n) funksiyanıń zárúrli (sohta emes) ózgeriwshisi dep ataladı.

F={f₁, f₂,.. ., f_n} Bul funksiyalar kompleksi berilgen bolsın.

F={ f₁, f₂,.. ., f_n f₁, f₂,.. ., f_n } Bul funksiyalar kompleksi berilgen bolsın.

Táriyp: F jıynaq ústinde anıqlanǵan formula dep, F (F) =f (t₁, t₂,.. ., t_n) ańlatpaǵa aytıladı, bul jerde fϵF hám t F ústindegi yamasa ózgeriwshi, yamasa formula. F jıynaq bazis, f sırtqı funksiya, ti lar bolsa bólim formulalar dep ataladı.Hár qanday F formulaǵa bir bahalı qandayda bir f Bul funksiyası sáykes keledi. Bul halda F formula f funksiyanı ańlatadı dep ataladı hám f=funcF kórinisinde belgilenedi.

Bazis penenfunksiyaların shınlıq kestein bilgen halda, bul formula ańlatatuǵın funksiyanıń shınlıq kestein esaplawımız múmkin. Ekenin aytıw kerek, logikalıq ámeller oy-pikirler algebrasi noqatı ázerden shınlıq kesteleri menen tolıq xarakterlenedi. Egerde funskiyaning keste formada beriliwin eske alsaq, ol waqıtta oy-pikirler algebrasida da funksiya túsinigin anıqlawımız múmkin.