Boolean aljibra. aljibra la mabaka. Metsoako ea mabaka a thuto ea lipalo

Lefatšeng la kajeno le re ka ho eketsehileng ho sebelisa mefuta e fapaneng ya mechine le lisebelisoa. 'Me a sa feela ha e ke ho hlokahala hore ho etsa kopo matla ka ho toba le phahametseng: susumelletsa hore mojaro ho e tsosa ho phahameng, cheka e telele le tebileng foro, joalo-joalo Cars kajeno bokella liroboto, lijo e phehiloe Multivarki le dipalelo mathomo mentlele hlahisa dipalo ka sebaleledi ... More 'me hangata ho feta re utloa mantsoe a reng "Boolean aljibra". Mohlomong u ka nako e fihlile ea hore u utloisise karolo e phethoang ke batho ka ho bōptjoa ha liroboto le mechine e le matla a ho rarolla e seng feela thuto ea lipalo, empa hape mathata utloahalang.

sea utloahala kapa che

Ka mabaka a Segerike - e ile a laela tsamaiso ea ho nahanoa hore baka kamano e pakeng tsa maemo a fanoeng le lumella u ho etsa inferences e thehiloeng likhopolong le likhakanyo. hangata ha ho, re botsa e mong le tse ling: "Ho ke ho utloahalang ho" The karabo e tiisa likhopolong tsa rona kapa criticizes terene oa ho nahana. Empa ho etsa joalo ha a fella moo: re ka tsoela pele ho bua.

Ka linako tse ling palo ea maemo a (input) ke e le moholo, 'me kamano e pakeng tsa bona e joalo a ferekanyang le a rarahaneng hore boko ba motho ke sa khone ho "silehe" tsohle hang-hang. O 'na ha hlokahala khoeli ho feta feta a le mong (beke, selemo) bakeng sa kutloisiso ea se etsahalang. Empa bophelo ba kajeno ha e re fa dikgao nako tsena ho etsa liqeto. Mme re retelehela ho thuso ea lik'homphieutha. 'Me e ke mona hore ho na le aljibra le utloahalang, le melao ea eona le thepa. Mora Downloading tsohle tsa ya data pele, re lumella k'homphieutha ho hlokomela likamano tsa bohle, ho felisa likhanyetsano le ho fumana tharollo e khotsofatsang.

Thuto ea lipalo le ho utloahalang

Famous Gotfrid Vilgelm Leybnits rerileng taba ea "libetsa thuto ea lipalo", eo mesebetsi ne ho le bonolo ho utloisisa feela le selikalikoe se senyenyane sa litsebi. Tsa thahasella ka ho khetheha ke tataiso ea ha aa ka a etsa hore, le ho bohareng ba XIX lekholong la lilemo la ba mabaka a thuto ea lipalo tsejoa ka tse seng kae.

The thahasello e khōlō ka-rasaense ho entse hore phehisano eo Lenyesemane Dzhordzh Bul bolela hore o ikemiselitse ho theha lekala ea lipalo, ho se be le feletseng ha ho sebelisoa molemo. Ha re ntse re tseba ho tloha histori, ka nako ena ka mafolofolo ho ntshetsa pele tlhahiso ea liindasteri, re ntshetswa pele mefuta eohle ea mechine ea thusang, 't. E. tse sibolotsoeng All saense e bile le dikamano e sebetsang.

Sheba pele, re ka bolela hore e Boolean aljibra - ka ho fetisisa tse neng li sebelisoa ka lefatše kajeno e le karolo ea thuto ea lipalo. Kahoo khang hao Buhl lahlehile.

Dzhordzh Bul

Botho ba mongoli e tšoaneloa ke tlhokomelo e khethehileng. Esita le fuoa ha e le hantle hore ka hara batho ba nakong e fetileng a ntse a hōla ka pel'a rōna, ntse re lokela ho hlokomela hore ka lilemo tse 16 ea Johanne. Buhl ruta ka sekolong motse, 'me o ile a bula lilemo ho 20 sekolong sa hae Lincoln. Setsebi sa lipalo ka ho phethahetseng tseba lipuo tse hlano tsoang linaheng tse ling, 'me ka nako ea hae a qenehela, o ne a bala mesebetsi ea Newton le Lagrange. Le tsohle ena - ka mora e mosebeletsi tlwaelehileng ya!

Ka 1839, Buhl romeloa la hae la pele lipampiri tsa saense ka Cambridge thuto ea lipalo Journal. Scientist reteleha lilemo li 24. mosebetsi Boole ke kahoo le thahasello litho tsa Royal Society, e 1844 o ile a fumana khau bakeng sa monehelo hae ho ntshetsopele ya and analysis lipalo. A tse seng kae tse hatisitsoeng lipampiri oo metsoako ea mabaka a thuto ea lipalo, ea lipalo lumelloa eo e monyenyane hore nka poso ea moprofesa ka College of Cork County ne a hlalosa. Hopola hore ka thuto Boole haholo e ne e ha ho joalo.

maikutlo

Ha e le hantle, Boolean aljibra haholo bonolo. Ho na le lipolelo tse (utloahalang lipoleloana) eo, ho tloha ntlheng ea ho lebaka la thuto ea lipalo, e ka feela ka hlalosoa ka mantsoe a mabeli: " 'nete" kapa "ba bohata". Ka mohlala, lifate ka selemo palesa - 'nete, ka ho ea lehlabula e lehloa le khetheha - leshano. Botle ba thuto ea lipalo e le hore ho ke ke ha ka tieo ho hlokahala hore ho sebelisa linomoro feela. Bakeng sa likahlolo tsa ho aljibra haholo lumellane lipolelo tse leha e le efe nang le morero e ikhethang.

Kahoo, aljibra la mabaka a ka sebelisoa ka ho toba le hohle: ka kemiso le ho ngola amohele taeo, ho hlahloba lesedi hanyetsanang mabapi le liketsahalo 'me boikemisetso ba tatelano ya liketso. Ntho ea bohlokoa ka ho fetisisa - ka hlokomela hore ha ho tsotellehe hore na re beha 'nete kapa falsity tsa lipolelo tse. From tsena "joang" le "ke hobane'ng ha" u lokela ho hlokomoloha. Ntho ea bohlokoa ke feela tlaleho ea ha e le hantle: 'nete ke leshano.

Ya e le hantle, mananeo a mesebetsi bohlokoa ka ho fetisisa tsa aljibra la mabaka eo li tlalehiloe ka lipontšo le matshwaonyana loketseng. Le ithute tsona - e ho bolela ho ithuta puo e ncha 'ngoe. Ha ho letho le ke ke ha khoneha.

bopa dikgopolo tsa mantlha le litlhaloso

Ntle ho kena botebo, re sebetsana le terminologicos. Ho joalo, Boolean alejibra presupposes:

• lipolelo tse;
• utloahalang tshebetso;
• mesebetsi le melao.

Lipolelo tse - ho hlahisa maikutlo leha e le efe e tingwa hore ka hlalosoa peli bohlokoa. Li ngotsoe ka linomoro (5> 3) kapa rerileng mantsoe le tlwaetsego (tlou - the phoofolo e anyesang kholo ka ho fetisisa). Tabeng ena, polelo e reng "molaleng Giraffe hase" o boetse o na le tokelo ea ho ba teng, feela Boolean aljibra hlalosa e le "leshano."

lipolelo tse tsohle e lokela ho ba ferekanye, empa ba ka 'na ba mantlha kapa motsoako. tšebeliso tsa morao tjena e utloahalang eo e sosobaneng. E. Ka aljibra lipolelo tse likahlolo komponeng thehoa ka go tlaleletsa ka tshebetso mathomo sea utloahala kapa che.

Boolean tshebetso aljibra

Re se hopola hore tshebetso ka aljibra likahlolo - utloahalang. Feela joalokaha aljibra ea linomoro sebedisa tshebetso mentlele ho eketsa, ho tlosa, kapa bapisa linomoro, thuto ea lipalo likarolo mabaka lumella ho etsa lipolelo tse rarahaneng, ho latola kapa ho a bale lebaka qetela.

Sea utloahala kapa che tshebetso bakeng sa rulaganngwa sentle le tsela e bonolo bontšoa ke moralo wa, tloaetseng re ka mentlele. Properties tsa ditekanyo Boolean alejibra etsa hore ho be bonolo hore a tlalehe 'me a bale e sa tsejoeng. tshebetso utloahalang atisa tlalehiloeng ke tafole 'nete. likarolo tsa lona hlalosa litšiea le dikhomphiutha tshebetso eo o etsoa ka ho bona, 'me le mela e bontša ka lebaka la balelela.

Basic sea utloahala kapa che bohato

The atileng ka ho fetisisa ka Boolean tshebetso aljibra ke negation (SE), le utloahalang AND le OR. Kahoo, ho ka etsahala ho hlalosa hoo e batlang e le mehato bohle ka likahlolo alejibra. Re ne re ithuta ka ho qaqileng e mong le ya tshebetso ya tse tharo.

The negation (ha) e sebelisoa ho elements le 'ngoe feela (operand). Ka lebaka leo, ke buuoe e bitsoa negation unary. Hore a tlalehe taba ea "ha A" sebedisa matshwaonyana joalo: ¬A, kapa A !. Foromo tafola ho bonahala e kang ena:

Ho sebetsa ha latola tloaelehile polelo e joalo: haeba A ke 'nete, ka nako eo A - ke ba bohata. Ka mohlala, khoeli revolves pota Lefatše - 'nete; Lefatše revolves pota khoeli - leshano.

Utloahalang atisiwa le phaella moo

Utloahalang AND tshebetso e bitsoa kopanelo. E bolela eng? Pele, hore e ka sebelisoa operands tse peli, ke hore,, ke - .. Binary tshebetso. Tabeng ya bobedi, ke feela tabeng ea 'nete ea operands bobeli (ka bobeli A le B) e ea' nete le polelo e reng ka boeona. Maele, "Mamello le ikitlaetsa ho se hokae" ho bontša hore lintho tse peli feela ka thusa motho hore a sebetsane ka katleho le mathata ao.

matshwaonyana ba sebediswa bakeng sa ho rekota: A∧B, A⋅B kapa A && B.

Kopanelo e tšoana le tse di atisitsweng ka mentlele. Ka linako tse ling 'me re - utloahalang atisiwa. Ha o atisa metsoako ea ho mela e tafoleng, re fumana lebaka tšoanang le ho nahana e utloahalang.

Disjunction ke utloahalang OR tshebetso. Ke 'NETE ha bonyane e mong oa lipolelo ke' nete (ka A kapa B). Ho ngoliloe e kang ena: A∨B, A + B kapa A || B. nnete tafole bakeng tshebetso tsena ke:

Disjunction tšoanang phaella moo mentlele. utloahalang phaella moo tshebetso e na le thibelo le 'ngoe feela: 1 + 1 = 1. Empa re hopola hore ka le fomate ditsitithale e felle feela mabaka a thuto ea lipalo 0 le 1 (moo 1 - nnete, 0 - ba bohata). Ka mohlala, polelo "a musiamo eo u ka bona tsoileng matsoho kapa fumana khampani e ntle" e bolela seo u ka bona mesebetsi ea bonono, 'me e ke ho bonolo ho kopana le motho ea thahasellisang. Ka nako e tšoanang, u se ke ua busa tsoa le monyetla oa ho phethahatsoeng ha tsoa hong ea liketsahalo tseo ka bobeli.

Mesebetsi le melao

Ho joalo, re se tseba seo ha e utloahalang tshebetso sebelisa Boolean aljibra. Mesebetsi hlalosang thepa kaofela thepa ea motheo ea mabaka a thuto ea lipalo, le re lumelle ho nolofatsa lipolelo tse rarahaneng komponeng. Ka ho fetisisa e hlakileng le e bonolo bonahala hana thepa ya tshebetso derivatives. Ke derivatives ba utloisisa XOR, boleloang le ditekani. Joalokaha re se re bala feela le tshebetso tsa motheo, 'me joale thepa e boetse ke feela li nka.

Associativity bolela hore ka lipolelo tse kang "bobeli A le B, le B 'tatelano lethathamo la operands e ha ho tsotellehe. moralo e ngotsoeng ka tsela e latelang:

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

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

Joalokaha u ka bona, sena ha se ikhethang oa ho kopanelo ya empa e disjunction.

Commutativity pheha khang ea hore ka lebaka la kopanelo kapa disjunction ha ea itšetleha ka eo ntho e ne e nkoa qalong:

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

Distributivity dumella senola masakaneng ka lipoleloana rarahaneng utloahalang. Melao tse tšoanang le se qalang parenthesis ka atisiwa le phaella moo ka alejibra:

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

thepa Unit le mengoapo, e leng e ka ba e mong oa operands ho boetse ho na le tse tšoanang le tsa katiso aljebra ke lefela kapa e 'ngoe,' me tlaleletsa ka unit trust e:

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

Idempotency e re bolella hore haeba e batlang e ba babeli operands lekanang le ka lebaka la buuoa ke e tšoanang, u ka "lahlela" ho feteletseng thatafatsa ho beha mabaka operands. Le kopanelo le disjunction tshebetso ke idempotent.

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

Fumana hape ho etsa hore re nolofatsa ka abel. Absorption re ha poleloana e reng e sebelisoa ho operand mong, opereishene e 'ngoe le elements o tšoanang oa ho lebaka la operand e' me le monya tshebetso.

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

tatelano ya tshebetso

Tatelano ya tshebetso e le ea bohlokoa haholo. Ha e le hantle, ha e le aljibra, ho na le ntho ea bohlokoa ho mosebetsi o sebelisa alejibra Boolean. Mekhoa e ka tsela e bonolo e laolwa feela bohlokoa ba tshebetso e. Boemong ba bohlokoa ka ho fetisisa ho hlokomolohuoang, re fumana a latellana joang latelang:

1. latola.

2. kopanelo.

3. The disjunction, XOR.

4. boleloang, ditekani.

Joalokaha u ka bona, feela negation tsa kopanelo le 'me u se ke ua ba le ntho ea bohlokoa ho lekana. A etelletsa pele tsa disjunction le XOR baa lekana, hammoho le lintho tse tlang pele ea boleloang le ditekani.

Mesebetsi ya tlhagiso le ditekani

Joalokaha re se re boletse, ho phaella tsa motheo tshebetso utloahalang, thuto ea lipalo le tlhalohanyo le khopolo ea ho dikgatotharabololong sebelisa derivatives. Ke hangata ka ho fetisisa e bolela'ng le ditekani.

The bolela'ng kapa e utloahalang lebaka - polelo ena, eo ho eona ketso e 'ngoe ke boemo ba motho ba,' me e mong - ka lebaka la ho kenngwa tshebetsong lona. Ka mantsoe a mang, tshisinyo sena ka lebaka la boikaketsi ba "haeba ... ka nako eo". "Ka mor'a lijo tsa mantsiboea e fihla ho ikarabella." E. Ka khanna ho tightened leralleng sled. Haeba ho na le ho na le takatso e matla ea ho fallela theoha thabeng, 'me ka nako eo hula ho sled ha ho hlokahale. E ngotsoeng hoo: A → B kapa A⇒B.

Ditekani bolela hore phello letlooa le hlaha feela ha operands bobeli ke 'nete. Mohlala, bosiu fana tsela le letsatsi ebe (le ka nako eo feela), ha letsatsi le chaba fetang atamela. Ka puo ea mabaka a thuto ea lipalo ha polelo ena e ngotsoeng e le A≡B, A⇔B, A == B.

melao tse ling tsa alejibra Boolean

Aljibra kena kahlolong develops, 'me ba bangata le bo-rasaense le thahasello ho o tlhame melao e ncha. Ka ho fetisisa tummeng li nkoa postulates Scotland setsebi sa lipalo O. De Morgan. O ile a bona 'me a ile a fana ka tlhaloso ea thepa tse kang negation haufi, phaella moo le habeli negative.

Haufi latola bontša hore pele ho parenthesis ho na ho latola: ha (A kapa B) = sa A kapa B. SE

Ha operand e latola, ho sa tsotellehe boleng ba eona, re ka phaella moo:

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

'Me qetellong, le negation habeli ka boeona compensates. ke hore, pele ka negation operand disappears kapa o hlola ka ho e 'ngoe feela.

Tsela ea ho rarolla liteko

Sea utloahala kapa che bolela simplification esale pele ditekanyo. Feela joaloka ho Lie aljibra, ho ke ke ho hlokahala hore ho maximally bebofatsa boemo pele (ho tlosa tshebetso rarahaneng input, 'me le bona), ka nako eo qala ho batla karabo e nepahetseng.

Seo a ka se etsa ho nolofatsa? Sokolla derivatives tsohle ka tshebetso e bonolo. Ebe apola le ka masakaneng tsohle (kapa sekgoeng, ho etsa hore ka masakaneng ho fokotsa elements ena). Mohato o latelang e lokela ho ba ho sebelisa Boolean aljibra thepa ikatisetsa (thepa absorption lefela 'me e mong,' me sa t.).

Qetellong, abel lokela bopilwe ka palo bonyane ba tsebeng, ho kopantswe le tshebetso e bonolo. Ho bobebe tsela ea ho batla tharollo e, haeba u etsa hore palo e khōlō ea negative haufi. Ebe karabo e tla itlhahela joalokaha eka ke ka boeona.