Algebra Boolean. algebra ee macquulka ah. Qaybaha ee macquulka xisaabeed

In dunida maanta aanu sii kordheysa oo isticmaalaya noocyo kala duwan oo mashiinada iyo qalabka. Iyagoo keliya ma aha marka waxaa lagama maarmaan ah in aad dalbato xoog macno sarreeyaan: guurto load si ay u kicin inay sarajooggiisuna, qodo qoday dheer oo qoto dheer, iwm Baabuurta maanta ururiyaan aalado, cuntada la kariyey Multivarki iyo xisaabinta xisaabta hoose saaro calculators ... More iyo ka badan inta badan waxaan maqli weedha ah "algebra Boolean". Waxaa laga yaabaa in la gaadhay wakhtigii si ay u fahmaan doorka aadanaha Abuuridda aalado iyo mashiinada awood u leh inay xaliyaan xisaabta ma aha oo kaliya, laakiin sidoo kale dhibaatooyin macquul ah.

macquulka ah

In macquulka Greek - nidaam ku amray oo fikirka ah in abuuraa xidhiidhka ka dhexeeya xaaladaha siiyey oo kuu ogolaanaya in aad si ay u sameeyaan go'aano ku salaysan fikrado iyo qiyaasta. Marar badan, waxaan kasta oo kale oo weydii: "Waa macquul in" reply The Oo Xaqiijiyay In fikrado ama naqdiyay tareenka oo fikirka ah. Laakiin habka ma waxaa la joojin doono: waxaan sii wadaynaa in ay ka hadlaan.

Mararka qaarkood tirada xaaladaha (input) waa sidaas u weyn, iyo xiriirka u dhaxeeya waa sidaas wareer iyo adag in maskaxda aadanaha ma awoodo inuu "dheefshiido" oo dhan hal mar. Waxaad u baahan tahay waxaa laga yaabaa in ka badan hal bil (toddobaadkii, sanadka) waxgarashada ee waxa ka dhacaya. Laakiin nolosha casriga ah ma naga siiyo waqti dura, kuwaas oo ay u sameeyaan go'aano. Oo waxaan door biday in ay gargaarka ah ee kombiyuutarada. Oo halkan waa in ay jirto aljabrada iyo macquulka ah, sharciyada iyo hantida. Ka dib markii degsado dhammaan xogta asalka ah, waxaan u ogolaan computer ah in la aqoonsado xidhiidhada oo dhan, si loo baabi'iyo is burinaya oo xal lagu qanci karo la helo.

Xisaabta iyo macquulka ah

Caan Gotfrid Vilgelm Leybnits diyaariyey fikirka ah "macquulka xisaabeed", taas oo hawlo ahaayeen fududahay in la fahmo oo kaliya goobo yar oo ka mid ah culimada. Oo xiiso gaar ah waa jihada ma keeni, iyo in bartamihii qarnigii XIX ee macquulka xisaabeed loo yaqaan by yar.

Xiisaha weyn ee bulshada sayniska ayaa sababay khilaaf ah oo Dzhordzh England Bul ku dhawaaqay inuu doonayo in la dhiso laan ka mid ah xisaabta, adigoo aan gebihaanba ma jirto isticmaalka wax ku ool ah. Sida aan ognahay taariikhda, waqtigan si firfircoon horumarinta wax soo saarka warshadaha, aan horumariyo dhammaan noocyada kala duwan mashiinada kaabayaal, E. t. All daahfurtay in sayniska ayaa hanuuninta a la taaban karo.

Raadinta ka hor, waxaannu nidhaahnaa, aljebra ah Boolean - ugu used ee dunida ka qayb maanta ee xisaabta. Sidaas Xujadiinna Buhl laga badiyay.

Dzhordzh Bul

shakhsiyadda qoraaga mudan yahay fiiro gaar ah. Xitaa siin xaqiiqada ah in dadka la soo dhaafay ku soo koray ina hor, weli waxaa la ogaadaa in ee 16 sano Buhl John. Baray dugsiga tuulada, oo 20 sano furay dugsi u gaar ah ee Lincoln. Xisaabyahan dhammaataan baasana shan luqadaha ajnabiga, iyo in uu waqtiga firaaqada ah, wuxuu akhriyeyey shuqullada Newton iyo Lagrange. Oo waxaas oo dhan - on ina shaqaalaha caadiga ah ee!

In 1839, Buhl ee Xisaabeed Cambridge ee Journal diray waraaqo cilmiyeed ugu horeysay. Saynisyahanka jeestay 24 sano. shaqada Boole ee waa xubno si xiiso of Society Royal ah, in 1844 uu helay biladda kale oo kaalin ka qaato horumarka ee falanqaynta xisaabta. A waraaqaha lagu daabacay dhowr ah oo xubno ka macquulka ah xisaabta, xisaabta loo ogol yahay dhallinyarada in ay qaataan jagada of professor ee College of County Cork ayaa ku tilmaamay. Xusuustaa at waxbarashada aad u Boole ma ahaa.

fikrad

In mabda'a, algebra Boolean waa mid aad u fudud. Waxaa jira statements (macquul ah tibaaxaha) in, ka barta of view of xisaabta, kaliya waxaa lagu qeexi karaa laba erayada: "run" ama "been". Tusaale ahaan, geedaha ubaxyada guga - runta, xagaaga waxaa barafka - Been. Beauty of xisaabta waa in aysan ahayn mid si adag loo baahan yahay in la isticmaalo tiro kaliya. Waayo, xukummadiisii oo algebra ah arrin ku haboon wax war la micno gaar ah.

Sayidka, aljebra ee macquulka ah waxaa loo isticmaali karaa macno ahaan meel kasta, in barashada jadwalka iyo qoraalka ah, falanqaynta macluumaadka khilaafsan oo ku saabsan dhacdooyinka iyo go'aan ka soo baxay isku xigxiga ee falalka. The wax ugu muhiimsan - si ay u ogaadaan in waxa macno ah ma sida aan u ogaado runta ama falsity of statements. From kuwan "sida" iyo "sababta" aad u baahan tahay in ay iska indha. Waxa muhim tahay oo kaliya qoraal ah oo xaqiiqada: runta waa been.

Dabcan, barnaamijyadooda hawlaha ugu muhiimsan ee aljabrada ee macquulka ah in ay diiwaangashan yihiin oo leh calaamado iyo astaamo ku haboon. Oo iyaga barataan - waxaa loola jeedaa si ay u bartaan luqad ajnabi cusub. Wax walba waa suurtogal.

fikradaha aasaasiga ah iyo qeexidda

Aan tegaya qoto dheer, waxaan eraybixinta ka qabtaan. Sidaas daraaddeed, algebra Boolean presupposes:

• statements;
• hawlgallada macquul ah;
• hawlaha iyo shuruucda.

Statements - hadal kasta oo raaca in loo fasiri karaa laba qiimeeyo. Waxay ku qoran yihiin sida tiro (5> 3) ama erayada ay yaqaanaan diyaariyey (maroodiga - naasleey ugu weyn). Xaaladdan oo kale, weedha ah "geri qoorta ma aha" Waxa kale oo uu xaq u leeyahay si uu u jiro, kaliya algebra Boolean ku sharaxay "been."

All statements waa in ay noqdaan aan shaki, laakiin waxa laga yaabaa aasaasiga ah ama xarunta. isticmaalka Recent xidhmo macquul ah. E. In xarunta xukummo statements algebra sameeyay waxaa dheer ee hawlgallada macquulka hoose.

hawlgallada algebra Boolean

Waxaan hore u soo xusuusatid in howlgallada aljabra xukummadaada - macquul ah. Sida algebra ee tirada la isticmaalayo hawlaha xisaabta si ay dar, kala-gooyaan, ama is barbar lambarada, xubno ka macquulka xisaabeed u ogolaan in uu sameeyo odhaah adag, in la diido ama loo xisaabiyo natiijada kama dambaysta ah.

hawlgallada Logic ee bibaabo iyo xog la muujiyay by caanaha, la yaqaan noogu soo xisaab. Guryaha ee isla'egyada aljebrada Boolean dhigi suurto gal si ay u qoraan iyo xisaabiyo oo aan la garaneyn ku. hawlgallada macquul ah waxaa badanaa lagu duubay by miiska runta. xubno ay u qeexaan tiirar iyo hawlgalka Kombuyuutarada oo lagu sameeyo iyaga on, iyo saf ah u muujiyaan natiijada xisaabinta.

macquulka aasaasiga ah garoomada

Kuwa ugu badan ee howlgalka algebra Boolean waa inkiraad (MA), oo macquul ah AND iyo OR. Sidaas waxaa suurtagal ah in ficil ahaan lagu qeexo dhammaan tallaabooyinka ee xukummo aljebra. Waxaan bartay in si faahfaahsan kasta oo ka mid ah saddex hawlood.

inkiraad ah (ma) waxaa laga codsadaa in kaliya hal element (operand). Sidaa darteed, hawlgalka waxaa lagu magacaabaa inkiraad ah unary. Si ay u qoraan fikirka ah "ma A" iyadoo la isticmaalayo calaamadaha sida: ¬A, ama A !. In foomka tabular waxay u egtahay sidan oo kale:

shaqo ee caadiga ah ee diidmada war noocan oo kale ah: haddii A waa run, ka dibna A - waa been. Tusaale ahaan, Dayaxa daba noqonayaa Dhulka - runta; Earth daba noqonayaa dayaxa - Been.

dhufashada macquul ah oo intaa dheer

Macquul IYO hawlgalka waxaa lagu magacaabaa lala a. Maxay ka dhigan tahay? Marka hore, in lagu saleyn karaa laba operands, ie, I - .. hawlgalka Binary. Marka labaad, waa kaliya in ay dhacdo runta ah oo labada operands (labada A iyo B) waxaa run iyo hadalka laftiisa. maahmaahda, "Dulqaad iyo in yar oo dadaal" oo muujinaysa in arrimo kaliya labo caawin kartaa qof ka gudbaan dhibaatooyin ah.

calaamadaha waxaa loo isticmaalaa wax lagu qoro: A∧B, A⋅B ama A && B.

Lala ay la mid tahay isku dhufashada ee xisaabta. Mararka qaarkood oo waxaad ku tidhaahdaa - dhufashada macquul ah. Haddii aad u tarmin waxyaalaha aasaaska ah ee ku saf oo miiska, aan helno natiijo la mid ah fikirka caqli galka ah.

Disjunction waa macquul a AMA hawlgalka. Waa run, haddii ugu yaraan mid ka mid ah weedhaha waa run (labada A ama B). Waa qoran tahay sidan: A∨B, A + B ama A || B. miiska runta hawlgallada waxay kala yihiin:

Disjunction Intaa waxaa dheer xisaabta la mid ah. hawlgalka waxaa dheer macquul ah uu leeyahay oo kaliya hal xadaynta: 1 + 1 = 1. Laakiin waxaannu xusuusan nahay in qaab digital waxaa ku koobnayn macquulka xisaabeed 0 iyo 1 (meesha ay 1 - runta, 0 - been ah). Tusaale ahaan, war "ee matxafka aad ka arki kartaa masterpiece ah ama aan ka helo shirkad wanaagsan" waxaa loola jeedaa waxa aad ka arki kartaa shuqullada tahay, oo ay suurto gal tahay in ay la kulmaan qof oo xiiso leh. Isla mar ahaantaana, ha meesha kama saarayo suurtagalnimada ee fulinta isku mar labada dhacdooyin.

Functions iyo sharciyada

Sidaas daraaddeed, waxaan ognahay waxa hawlgalka macquul ah iyadoo la isticmaalayo algebra Boolean. Functions dhamaan sifooyinka waxyaalaha aasaaska ah ee macquulka ah xisaabta, iyo noo oggolaan in uu u fududayn lahaa statements xarunta adag. The ugu cad oo fudud u muuqataa hantida diidmada oo ka mid ah hawlaha taagayo. By taagayo ayaa la fahamsan yahay Miyeydnaan, Ujeedadiisu iyo isu-. Sida aan akhriyey oo keliya hawlaha aasaasiga ah, ka dibna hantida sidoo kale waa kaliya iyaga ka fiirsan.

Associativity ka dhigan tahay in in weedhaha sida "labada A iyo B, iyo B 'liiska isku xigxiga ee operands ah ma ahan. formula waxaa ku qoran sida soo socota:

(A∧B) ∧V = A∧ (B∧V) = A∧B∧V,

(A∨B) ∨V = A∨ (B∨V) = A∨B∨V.

Sida aad arki karto, tani ma aha mid gaar ah in lala laakiin disjunction ah.

Commutativity doodaysaa in natiijada lala ama disjunction kuma xirna oo item waxaa loo tixgeliyaa at bilowgaba:

A∧B = B∧A; A∨B = B∨A.

Distributivity ogolaanaya bandhigno dhxe ee tibaaxaha macquul ah oo adag. Xeerarka la mid ah qaws furitaanka ee isku dhufashada iyo Intaa waxaa dheer in algebra waa:

A∧ (B∨V) = A∧B∨A∧V; A∨B∧V = (A∨B) ∧ (A∨V).

guryaha Unit oo la xoqo, kaas oo noqon kara mid ka mid ah operands ayaa sidoo kale la mid yihiin isku dhufashada aljebrada by eber ama hal, oo intaa dheer ee unug:

A∧0 = 0, A∧1 = A, A∨0 = A, A∨1 = 1.

Idempotency inoo sheegayaa in haddii loo eego laba operands siman natiijada qalliinka waa isku mid, kartaa in aad "Tuur" ku operands sababaynta adkayn xad-dhaaf ah. Oo hawlgallada lala iyo disjunction waa idempotent.

B∧B = B; B∨B = B.

Qaadashada kale oo noo ogolaadaa in ay fududeeyaan isla'egta. Nuugista sheegayaa in markii muujinta waxaa laga codsadaa in mid ka mid operand, qaliin kale oo leh walxo la mid ah operand natiijada waxaa ahmiyadda hawlgalka.

A∧B∨B = B; (A∨B) ∧B = B.

isku xigxiga ee hawlaha

isku xigxiga ee hawlaha waa muhiimad weyn. Dhab ahaantii, sida aljebra, waxaa jira shaqo mudnaanta isticmaala algebra a Boolean ah. Qaaciidooyinka loo fududeeyey karaa oo keliya ku xiran muhiimadda ay howlgallada. Saraysiinta ee ugu weyn in ay dayac badan, waxaan ka heli isku xigxiga ee soo socda:

1. Diidmada.

2. lala.

3. disjunction The, Miyeydnaan.

4. Tilmaanta, isu-.

Sida aad arki karto, kaliya inkiraad ah ee lala iyo aadan haysan mudnaantoodu ay isku mid. mudnaanta A oo ka mid ah disjunction iyo Miyeydnaan waa u siman yihiin, iyo sidoo kale mudnaanta tusinaysaa iyo isu-.

Hawlaha tusinaysaa iyo isu-

Sida aan ku sheegay, marka lagu daro hawlaha macquul aasaasiga ah, Sababaha macquulka ah xisaabta iyo aragti of algorithms isticmaalaya taagayo. Waxaa inta badan waa ku tusinaysaa iyo isu-.

Tilmaanta ama natiijo macquul ah - bayaankan, taas oo ka mid ah tallaabo waa xaalad, oo kale ah - natiijada hirgelintiisa. In si kale loo dhigo, soo jeedinta la marmarsiiyo ah "haddii ... ka dibna". "Ka dib markii casho yimaado xisaab." E. Waayo wadida in la adkeeyay buurta gaari baraf. Haddii aanu jirin rabitaan buurtii hoos uga soo guurto, ka dibna jiidi gaari baraf loo baahan yahay ma aha. Waxaa sidaas ku qoran: A → B ama A⇒B.

Isu muujinaysa in saamaynta net dhacdaa oo keliya marka labada operands waa run. Tusaale ahaan, habeen siinayaa si ay maalin ka dibna (oo markaas oo keliya), marka qorraxdu soo baxdo in ka badan bidhaamayaan. In luqadda ee macquulka xisaabeed ee bayaankan waxaa qoran sida A≡B, A⇔B, == B. A

Sharciyada kale ee aljabra Boolean

xukun Algebra uu yeesho, iyo saynisyahano badan oo xiiseynaya in ay habeeyaan sharciyo cusub. The ugu caansan waxaa loo tixgeliyaa postulates xisaab Scottish O. De Morgan. Wuxuu ogaaday iyo siiyey qeexidda dhabta ah ee guryaha sida inkiraad dhow, Intaa waxaa dheer iyo negative double.

diidmada Close soo jeedisay in ka hor inta qaws waa wax beenin ma jiro, ma (A ama B) = ma A ama B. MA

Marka operand la diido, iyadoo aan loo eegin qiimaha, yidhaahdo oo ku saabsan sii dheer:

B∧¬B = 0; B∨¬B = 1.

Ugu dambayntiina, inkiraad ah double laftiisa mag. ie ka hor inta inkiraad midkood operand baaba'aa ama weli ah mid ka kaliya.

Sidee si ay u xalliyaan imtixaanada

Logic tilmaamaysaa fududeynta Fundka isla'egyada. Sida aljabra jiifso ah, waxaa lagama maarmaan ah in maximally fududeeyo xaaladda hore (in laga takhaluso hawlgallada talooyin u adag, oo iyaga waxaa la jiray), ka dibna u bilaabaan raadinaya jawaab sax ah.

Maxaa la samaynayaa si loo fududeeyo? Beddelid oo dhan taagayo ee hawlgalka fudud. Markaas oo qows oo dhan u qaawisid (ama qeybsanaan, si ay u sameeyaan oo qows si loo yareeyo element this). Tallaabada xigta waa in ay u isticmaalaan guryaha algebra Boolean ku dhaqanka (guryaha nuugista eber iyo mid ka mid ah, iyo t.).

Ugu dambayntii, isla'egta waa kooban yihiin tirada ugu yar ee dahsoon, weheliso hawlaha fudud. Habka ugu fudud in la raadiyo xal, haddii aad ka dhigi tiro badan oo ah diidmo dhow. Markaas jawaabta arbushin doonaa sidii keligeed.