Boolean algebra. algebra ng lohika. Mga elemento ng matematikal na lohika

Sa mundo ngayon unting ginagamit namin ang isang iba't ibang mga machine at mga gadget. At hindi lamang kapag ito ay kinakailangan upang ilapat ang literal mahigit sa tao lakas. Ilipat ang load na itaas ito sa taas, maghukay mahaba at malalim na lagyan ng trintsera, at iba pa D. Kotse araw na mangolekta ng mga robot, pagkain ay niluto Multivarki at elementarya kalkulasyon arithmetic makabuo ng calculators. Parami nang parami ang madalas na marinig namin ang pariralang "Boolean algebra". Marahil na ang oras ay dumating upang maunawaan ang papel na ginagampanan ng mga tao sa paglikha ng mga robot at machine ang kakayahan upang malutas ang hindi lamang sa matematika, ngunit din lohikal na mga problema.

lohika

Sa Greek logic - isang order ng sistema ng pag-iisip na lumilikha ng ang relasyon sa pagitan ng mga ibinigay na mga kondisyon at nagbibigay-daan sa iyo upang gumawa ng inferences batay sa pagpapalagay at mga pagtatantya. Medyo madalas, hinihiling namin sa isa't isa: "Ito ay lohikal na" reply Ang Kinukumpirma ang aming mga palagay o criticizes ang tren ng pag-iisip. Ngunit ang proseso ay hindi itigil doon: patuloy naming makipag-usap.

Minsan ang bilang ng mga kundisyon (input) ay kaya mahusay, at ang ugnayan sa pagitan ng mga ito ay kaya nakalilito at kumplikadong na ang utak ng tao ay hindi kayang "digest" sabay-sabay. Maaaring kailanganin ng higit sa isang buwan (linggo, taon) para sa pag-unawa sa kung ano ang nangyayari. Ngunit modernong buhay ay hindi nagbibigay sa amin ang mga agwat ng oras upang gumawa ng mga desisyon. At resort namin sa tulong ng mga computer. At ito ay dito na may isang algebra at lohika, kasama ang mga batas at mga katangian. Pagkatapos ng pag-download ng lahat ng orihinal na data, pinapayagan namin ang computer upang makilala ang lahat ng mga relasyon, upang puksain ang mga contradictions at upang makahanap ng isang kasiya-siya solusyon.

Matematika at lohika

Mga Sikat na Gotfrid Vilgelm Leybnits formulated ang konsepto ng "mathematical logic", na gawain ay madaling maunawaan lamang ng isang maliit na bilog ng mga iskolar. Ng mga partikular na interes ay ang mga direksyon ay di naging sanhi, at sa gitna ng siglo XIX ng mathematical logic na kilala ng ilan.

Ang dakilang interes sa mga pang-agham na komunidad ay dulot ng hindi pagkakaunawaan kung saan ang Englishman Dzhordzh Bul ipinahayag ang kanyang intensyon upang magtatag ng isang sangay ng matematika, hindi pagkakaroon ganap na walang praktikal na gamitin. Tulad ng alam namin mula sa kasaysayan, sa oras na ito ay aktibong pagbuo ng pang-industriya produksyon, bumuo kami ng lahat ng uri ng auxiliary machine, t. E. Ang lahat ng pang-agham na tuklas ay nagkaroon ng mga praktikal na orientation.

Naghahanap ng maaga, sabihin natin na ang isang Boolean algebra - ang pinakaginagamit na sa mundo ngayon bahagi ng matematika. Kaya ang iyong argumento Buhl mawawala.

Dzhordzh Bul

Ang personalidad ng may-akda nararapat espesyal na pansin. Kahit na ibinigay ang katunayan na sa nakalipas na mga tao ay lumago up bago sa amin, pa rin ito ay dapat na nabanggit na sa 16 taon ni Juan. Buhl nagturo sa village paaralan, at sa 20 taon binuksan ang kanyang sariling paaralan sa Lincoln. Mathematician perpektong pinagkadalubhasaan limang mga banyagang wika, at sa kanyang bakanteng oras, nagbabasa ng mga gawa ng Newton at Lagrange. At ang lahat ng ito - sa anak na lalaki ng isang ordinaryong manggagawa!

Noong 1839, Buhl ay nagpadala ng kanyang unang pang-agham papeles sa Cambridge matematiko Journal. Scientist naka-24 taon. Boole 's trabaho ay kaya interesado mga kasapi ng Royal Society, noong 1844 siya ay nakatanggap ng isang medalya para sa kanyang mga kontribusyon sa pag-unlad ng matematikal na pagsusuri. Ang ilang mga nai-publish na mga papeles na kung saan ang mga elemento ng matematikal na lohika, matematika pinapayagan ang mga batang gawin ang mga post ng mga propesor sa College of Cork County ay inilarawan. Sariwain sa alaala na sa pinakadulo Boole edukasyon ay hindi.

idea

Sa prinsipyo, Boolean algebra ay napaka-simple. May mga pahayag (lohikal na expression) na, mula sa punto ng view ng matematika, maaari lamang na tinukoy sa dalawang salita: "totoo" o "false". Halimbawa, puno sa tagsibol Bloom - ang katotohanan, sa tag-init ito snows - isang kasinungalingan. Ang kagandahan ng matematika ay na ito ay hindi mahigpit na kinakailangan upang gamitin lamang mga numero. Para sa algebra hatol lubos na magkasya sa anumang mga pahayag na may mga natatanging kahulugan.

Kaya, ang algebra ng lohika ay maaaring magamit literal sa lahat ng dako: sa pag-iiskedyul at pagsusulat ng pagtuturo, pag-aaral ng mga nagsasalungatang impormasyon tungkol sa mga kaganapan at ang pagpapasiya ng ang pagkakasunod-sunod ng mga aksyon. Ang pinaka-mahalagang bagay - upang mapagtanto na ito ay hindi mahalaga kung paano namin matukoy ang katotohanan o kasinungalingan ng mga pahayag. Mula sa mga "paano" at "bakit" kailangan mong huwag pansinin. Ano ang mahalaga ay lamang ng isang pahayag ng katotohanan: ang katotohanan ay isang kasinungalingan.

Of course, programming ang pinaka-mahalagang mga function ng algebra ng lohika na ay naitala na may naaangkop na mga palatandaan at mga simbolo. At alamin ang mga ito - ang ibig sabihin nito upang malaman ng isang bagong banyagang wika. Wala ay imposible.

Basic concepts at mga kahulugan

Walang nangyayari sa lalim, kami ay haharapin ang mga terminolohiya. Kaya, Boolean algebra presupposes:

• pahayag;
• lohikal na operasyon;
• function at mga batas.

Mga Pahayag - anumang positibong expression na maaari mangahulugan dalawang-nagkakahalaga. Ang mga ito ay isinulat ng mga numero (5> 3) o formulated pamilyar salita (elephant - ang pinakamalaking mammal). Sa kasong ito, ang pariralang "leeg ng giraffe ay hindi" ay mayroon ding karapatan na umiiral, lamang ang Boolean algebra tukuyin ito bilang "isang kasinungalingan."

Ang lahat ng mga pahayag ay dapat na hindi malabo, ngunit maaaring sila ay basic o looban. Kamakailang paggamit lohikal na bundle. E. Sa algebra pahayag hatol tambalang nabuo sa pamamagitan ng pagdaragdag ng elementarya operasyon logic.

Boolean operasyon algebra

Kami ay mayroon na tandaan na ang mga operasyon sa algebra ng hatol - lohikal. Tulad ng algebra ng mga numero gamit ang arithmetic operations upang idagdag, ibawas, o ihambing ang mga numero, matematika elemento logic payagan upang gumawa ng komplikadong mga pahayag, upang tanggihan o upang makalkula ang pangwakas na resulta.

Logic pagpapatakbo para sa pormalisasyon at pagiging simple ipinahayag sa pamamagitan ng mga formula, pamilyar sa amin sa arithmetic. Mga katangian ng Boolean algebra equation gawing posible upang i-record at makalkula ang hindi kilala. Lohikal na operasyon ay karaniwang naitala sa pamamagitan ng talahanayan katotohanan. mga elemento nito tukuyin ang mga hanay at computing operasyon na kung saan ay ginanap sa mga ito, at ang mga hilera ipakita ang resulta ng mga kalkulasyon.

Basic logic ng pagkilos

Ang pinaka-karaniwan sa mga Boolean operasyon algebra ay hindi pagsang-(HINDI), at ang lohikal AT at O. Kaya ito ay posible upang ilarawan ang halos lahat ng mga hakbang sa algebra hatol. Kami ay nag-aral sa detalye ang bawat isa sa tatlong mga operasyon.

Ang hindi pagsang-ayon (hindi) ay inilapat sa lamang ng isang elemento (operand). Samakatuwid, ang operasyon ay tinatawag na isang unary pagsang-ayon. Upang i-record ang konsepto ng "Hindi isang" gamit tulad ng mga simbolo: ¬A, A o A !. Sa hugis ng mga talaan form na ito ganito ang hitsura:

Ang pag-andar ng pagtanggi tipikal ng ganitong pahayag: kung A ay totoo, at pagkatapos ay A - ay hindi totoo. Halimbawa, ang buwan revolves sa paligid ng Earth - ang katotohanan; Daigdig revolves sa paligid ng buwan - isang kasinungalingan.

Lohiko pagpaparami at karagdagan

Lohiko AT operasyon ay tinatawag na isang kasabay. Ano ang ibig sabihin? Una, maaari itong ilapat sa dalawang operands, ibig sabihin, I - .. Binary operasyon. Pangalawa, ito ay lamang sa kaso ng ang katotohanan ng parehong mga operands (parehong A at B) ay totoo at ang expression mismo. Sinasabi ng kawikaan, "Ang tiyaga at isang maliit na pagsisikap" ay nagpapahiwatig na tanging dalawang mga kadahilanan ay maaaring makatulong sa isang tao makaya na may mga kahirapan.

mga simbolo ay ginagamit para sa pag-record: A∧B, A⋅B o A && B.

Kasabay ay katulad sa pagpaparami sa aritmetika. Kung minsan at sabihin - lohikal multiplication. Kung ikaw ay paramihin ang mga elemento ng hilera ng talahanayan, makakakuha tayo ng isang resulta na katulad ng lohikal na pag-iisip.

Pagtanggal ay isang lohikal O operasyon. Ito ay TRUE kung hindi bababa sa isa sa mga pahayag ay totoo (alinman sa A o B). Nasusulat na katulad nito: A∨B, A + B o A || B. ang katotohanan talahanayan para sa mga operasyon ay ang mga:

Pagtanggal katulad na arithmetic karagdagan. lohikal na karagdagan na operasyon ay may lamang ng isang paghihigpit: 1 + 1 = 1. Ngunit tandaan natin na sa isang digital na format ay limitado sa matematikal na lohika 0 at 1 (kung saan ang 1 - sa katotohanan, 0 - maling). Halimbawa, ang pahayag na "sa museo maaari mong makita ang isang obra maestra o makahanap ng isang mahusay na kumpanya" ay nangangahulugang kung ano ang maaari mong makita ang mga gawa ng sining, at ito ay posible upang matugunan ang isang kawili-wiling tao. Kasabay nito, huwag mamuno out ang posibilidad ng sabay-sabay na katuparan ng parehong kaganapan.

Pag-andar at mga batas

Kaya, namin na malaman kung ano ang lohikal na operasyon gamit Boolean algebra. Pag-andar ilarawan ang lahat ng mga katangian ng ang mga elemento ng matematikal na lohika, at magbibigay-daan sa amin upang gawing simple kumplikadong compound pahayag. Ang pinaka-malinaw at simple tila pagtanggi ari-arian ng mga operasyon derivatives. Sa pamamagitan ng derivatives ay nauunawaan XOR, implikasyon at pagkapareho. Tulad ng nabasa ko lang namin na may mga pangunahing mga operasyon, at pagkatapos ay ang ari-arian ay din lamang isaalang-alang ang mga ito.

Associativity Nangangahulugan ito na sa mga pahayag tulad ng "parehong A at B, at B 'sequence listahan ng mga operands ay hindi mahalaga. Ang formula ay nakasulat na tulad ng sumusunod:

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

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

Tulad ng iyong nakikita, ito ay hindi natatangi sa pagsama ngunit isang pagtanggal.

Commutativity argues na ang resulta ng pagsama o pagtanggal ay hindi nakadepende sa kung aling item ay itinuturing sa simula:

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

Distributivity nagbibigay-daan sa ibunyag ang mga braket sa kumplikadong lohikal na expression. Panuntunan ay katulad sa ang pagbubukas panaklong sa pagpaparami at karagdagan sa algebra:

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

properties unit at scratch, na kung saan ay maaaring maging isa sa mga operands ay katulad sa algebraic pagpaparami sa pamamagitan ng zero o ng isa, at pagdaragdag ng isang yunit ng:

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

Idempotency nagsasabi sa amin na kung medyo dalawang pantay na operands ang resulta ng operasyon ay ang parehong, maaari mong "throw" ang labis na makapagpalubha pagdadahilan operands. At ang pagsama at pagtanggal operasyon ay idempotent.

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

Acquisition ay nagpapahintulot din sa amin upang gawing simple ang equation. Pagsipsip ipinapahayag na kapag ang mga expression ay nilalapat sa isang operand, isa pang operasyon na may parehong elemento ng resulta operand ay sumisipsip ng operasyon.

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

pagkakasunod-sunod ng mga operasyon

Ang pagkakasunod-sunod ng mga operasyon ay ng malaking kahalagahan. Sa totoo lang, tulad ng para sa algebra, mayroong isang priority function na ay gumagamit ng isang Boolean algebra. Formula ay maaaring pinasimple na mangyayari lamang kung ang kabuluhan ng mga operasyon. Ranking sa mga pinaka-makabuluhang upang bale-wala, makuha namin ang mga sumusunod na pagkakasunod-sunod:

1. Denial.

2. kasabay.

3. Ang pagtanggal, XOR.

4. Ang implikasyon, pagkapareho.

Tulad ng iyong nakikita, tanging ang pagsang-ayon ng kasabay at hindi ay may pantay na priority. Ang isang priority ng pagtanggal at XOR ay pantay-pantay, pati na rin ang mga prayoridad ng pagkakasangkot at pagkapareho.

Mga Pag-andar ng mga implikasyon at equivalence

Bilang namin ang sinabi, bilang karagdagan sa mga pangunahing mga lohikal na mga pagpapatakbo, matematikal na lohika at teorya ng algorithm gamit derivatives. Ito ay pinaka-madalas na ang implikasyon at pagkapareho.

Ang implikasyon o lohikal na kinahinatnan - ang pahayag na ito, kung saan ang isang aksyon ay isang kalagayan, at ang iba pang mga - ang resulta ng pagpapatupad nito. Sa ibang salita, ang panukalang ito sa mga pagkukunwari ng "kung ... pagkatapos ay". "Pagkatapos ng hapunan ay dumating ang pagtutuos." E. Para sa pagmamaneho sa tightened sa sled burol. Kung walang pagnanais upang ilipat pababa mula sa bundok, at pagkatapos ay i-drag ang sled ay hindi kinakailangan. Nasusulat kaya: Isang → B o A⇒B.

Pagpareho ay nagpapahiwatig na ang net na epekto ay nangyayari lamang kapag ang parehong mga operands ay totoo. Halimbawa, gabi ay nagbibigay sa paraan upang sa araw pagkatapos (at lamang pagkatapos), kapag ang araw ay sumisikat sa ibabaw ng abot-tanaw. Sa wika ng mga mathematical logic ng pahayag na ito ay isinulat bilang A≡B, A⇔B, Isang == B.

Ibang mga batas ng Boolean algebra

Algebra paghatol bubuo, at marami na interesado siyentipiko upang bumalangkas ng mga bagong batas. Ang pinaka-tanyag ay isinasaalang-alang postulates Scottish matematiko O. De Morgan. Napansin siya at nagbigay ng isang kahulugan ng mga naturang ari-arian na malapit pagsang-ayon, karagdagan at i-double negatibo.

Isara pagtanggi ay nagmumungkahi na sa harap ng panaklong ay walang pagtangging sumampalataya: Hindi (A o B) = Hindi A o B. HINDI

Kapag ang operand ay tinanggihan, hindi alintana ng kanyang halaga, sinasabi tungkol karagdagan:

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

At sa wakas, ang double negation mismo compensates. ibig sabihin, bago mag-operand hindi pagsang mawala o nananatiling isa lamang.

Paano upang malutas ang mga pagsubok

Logic ay nagpapahiwatig ng pagpapasimple paunang-natukoy na equation. Tulad sa pagsinungalingan algebra, ito ay kinakailangan upang maximally na pangasiwaan ang unang kundisyon (sa kumuha alisan ng kumplikadong mga pagpapatakbo ng pag-input, at sa kanila), at pagkatapos ay simulan ang naghahanap para sa isang tamang sagot.

Ano ang dapat gawin upang gawing simple? I-convert ang lahat ng mga derivatives sa isang simpleng operasyon. Pagkatapos ay magpugay ang lahat ng mga bracket (o vice versa, upang gumawa ng mga bracket upang mabawasan ang elementong ito). Ang susunod na hakbang ay dapat na upang gamitin ang Boolean algebra properties sa kasanayan (katangian ng pagsipsip zero at isa, at t.).

Sa paglaon, ang equation ay dapat binubuo ng isang minimum na bilang ng mga unknowns, pinagsama na may simpleng operasyon. Ang pinakamadaling paraan upang tumingin para sa isang solusyon, kung gumawa ka ng isang malaking bilang ng mga malapit na mga negatibo. Pagkatapos ay ang sagot ay pop up bilang kung sa pamamagitan ng mismo.