Algjebër Boolean. algjebër e logjikës. Elemente të logjikës matematike

Në botën e sotme ne janë gjithnjë duke përdorur një shumëllojshmëri të makinave dhe Gadgets. Dhe jo vetëm kur është e nevojshme për të aplikuar forcën e vërtetë mbinjerëzore: Masa e ngarkesës për të ngritur atë në lartësinë, gërmoj hendek të gjatë dhe të thellë, etj Cars sot mbledhur robots, ushqimi është i gatuar Multivarki dhe llogaritjet elementare aritmetike prodhojnë calculators ... Gjithnjë e më shpesh dëgjojmë shprehjen "algjebër Boolean". Ndoshta ka ardhur koha për të kuptuar rolin e qenieve njerëzore në krijimin e robotëve dhe makina aftësinë për të zgjidhur jo vetëm matematikore, por edhe probleme logjike.

logjikë

Në logjikën greke - një sistem i urdhëroi të mendimit që krijon marrëdhënien ndërmjet kushteve të dhëna dhe ju lejon të bëni konkluzione bazuar në supozimet dhe vlerësimet. Shumë shpesh, ne kërkojmë njëri-tjetrit: "Është logjike që të" Përgjigja konfirmon supozimet tona ose kritikon vijën e mendimit. Por procesi nuk ndalet këtu: ne vazhdojmë të flasim.

Ndonjëherë numri i kushteve (input) është aq e madhe, dhe marrëdhënia mes tyre është aq konfuze dhe komplekse se truri i njeriut nuk është në gjendje të "tretet" të gjitha në të njëjtën kohë. Ju mund të kenë nevojë më shumë se një muaj (javë, vit) për të kuptuar se çfarë po ndodh. Por jeta moderne nuk na jep këto intervale kohore për të marrë vendime. Dhe ne të mbështetet në ndihmën e kompjuterëve. Dhe është këtu që ka një algjebër dhe logjikë, me ligjet dhe pronat e saj. Pas shkarkimit të gjitha të dhënat origjinale, ne të lejojë kompjuterin që të njohë të gjitha marrëdhëniet, për të eliminuar kontradikta dhe për të gjetur një zgjidhje të kënaqshme.

Matematika dhe Logjika

Famous Gotfrid Vilgelm Leybnits formuluar konceptin e "logjikës matematike", i cili detyrat ishin të lehtë për të kuptuar se vetëm një rreth të vogël të dijetarëve. Me interes të veçantë është drejtimi nuk ka shkaktuar, dhe në mes të shekullit XIX e logjikës matematikore të njohur nga pak.

Interesi i madh në komunitetin shkencor ka shkaktuar një mosmarrëveshje në të cilën anglez Dzhordzh Bul deklaruar synimin e tij për të krijuar një degë e matematikës, nuk ka absolutisht asnjë përdorim praktik. Siç e dimë nga historia, në këtë kohë në mënyrë aktive zhvillimin e prodhimit industrial, ne kemi zhvilluar të gjitha llojet e makinave ndihmëse, t. E. Të gjitha zbulimet shkencore kanë pasur një orientim praktik.

Duke parë përpara, ne themi se një algjebër Boolean - më i përdorur në sot pjesë e matematikës botës. Pra, argumenti juaj Buhl humbur.

Dzhordzh Bul

Personaliteti i autorit meriton vëmendje të veçantë. Edhe duke pasur parasysh faktin se në të kaluarën njerëzit u rrit para nesh, ende duhet theksuar se në 16 vitet e Gjonit. Buhl mësim në shkollën e fshatit, dhe deri në 20 vjet hapi shkollën e tij në Lincoln. Matematikan zotëruar të përkryer pesë gjuhë të huaja, dhe në kohën e tij të lirë, po lexonte veprat e Njutonit dhe Lagranzhit. Dhe e gjithë kjo - në djalit një punëtor i zakonshëm!

Në vitin 1839, Buhl dërgoi letrat e tij të parë shkencore në Kembrixh matematike Journal. Scientist kthyer 24 vit. Boole e punës është anëtarë aq e interesuar të Shoqërisë Mbretërore, në 1844 ai mori një medalje për kontributin e tij në zhvillimin e analizës matematike. Disa letra të publikuara në të cilën elementet e logjikës matematikore, matematika lejuar të rinjtë për të marrë postin e profesor në Kolegjin e KS County janë përshkruar. Kujtojnë se në arsim shumë të Boole nuk ishte.

ide

Në parim, algjebër Boolean është shumë e thjeshtë. Ka deklarata (logjike shprehjet) që, nga pikëpamja e matematikës, mund të përcaktohen vetëm në dy fjalë: "e vërtetë" ose "false". Për shembull, pemët në lulëzim pranverë - e vërteta, në verë ajo bie borë - një gënjeshtër. Bukuria e matematikës është se ajo nuk është e domosdoshme që të përdorin vetëm numra. Për gjykimet algjebër mjaft të përshtaten ndonjë deklaratë me kuptim unik.

Kështu, algjebër e logjikës mund të përdoren fjalë për fjalë kudo: në udhëzimin e planifikimin dhe shkrimit, analiza e informacionit kontradiktore në lidhje me ngjarjet dhe përcaktimin e radhës së veprimeve. Gjëja më e rëndësishme - për të kuptuar se kjo nuk ka rëndësi se si ne të përcaktuar të vërtetën apo falsitetin e deklaratave. Nga këto "si" dhe "pse" ju duhet të injorojë. Ajo që ka rëndësi është vetëm një deklaratë e vërtetë: e vërteta është një gënjeshtër.

Sigurisht, programimit funksionet më të rëndësishme të algjebër e logjikës që janë regjistruar me shenja dhe simbole të përshtatshme. Dhe të mësojnë tyre - kjo do të thotë për të mësuar një gjuhë të re të huaj. Asgjë nuk është e pamundur.

Konceptet themelore dhe përkufizimet

Pa hyrë në thellësi, të merremi me terminologjinë. Pra, algjebër Boolean presupozon:

• deklaratat;
• operacionet logjike;
• funksionet dhe ligjet.

Deklaratat - çdo shprehje pozitive që mund të interpretohet dy-vlerësuar. Ato janë të shkruara si numrat (5> 3) ose formuluar fjalë të njohura (elefant - më i madh gjitarëve). Në këtë rast, shprehja "qafa gjirafë nuk është" gjithashtu ka të drejtë të ekzistojë, vetëm algjebër Boolean përcaktuar atë si "një gënjeshtër."

Të gjitha deklaratat duhet të jenë të qartë, por ato mund të jenë bazë apo të përbërë. Përdorimi i fundit pako logjike. E. Në kompleksin deklaratat algjebër gjykimeve formuar nga shtimin e operacioneve elementare logjike.

Operacionet Boolean algjebër

Ne tashmë Mos harroni se operacionet në algjebër e gjykimeve - logjike. Ashtu si algjebër e numrave duke përdorur operacionet aritmetike të shtoni, zbres, ose krahasoni numrat, elementet e logjikës matematikore të lejojë që të bëjë deklarata komplekse, të mohojë apo për të llogaritur rezultatin përfundimtar.

operacionet logjike për formalizimin dhe thjeshtësisë shprehur nga formula, të njohur për ne në aritmetikë. Prona e ekuacioneve Boolean algjebër të bëjë të mundur për të regjistruar dhe për të llogaritur të panjohur. operacionet logjike janë regjistruar zakonisht nga tabela vërtetën. Elementet e saj të përcaktojë kolona dhe funksionimin informatikë i cili është kryer mbi ta, dhe rreshtave të tregojnë rezultatin e llogaritjeve.

logjika themelore e veprimit

Më të zakonshme në operacionet Boolean algjebër janë mohim (jo), dhe logjik AND dhe OR. Pra, kjo është e mundur për të përshkruar praktikisht të gjithë hapat në gjykimet e algjebër. Ne studiuar në detaje secilin nga tre operacioneve.

Mohimi (nuk) është aplikuar për vetëm një element (operandi). Prandaj, operacioni është quajtur një mohim unary. Për të regjistruar konceptin e "jo", duke përdorur simbole të tilla: ¬, A ose A !. Në formë tabelore duket si ky:

Funksioni i mohimit tipike e një deklaratë të tillë: nëse A është e vërtetë, atëherë A - është e rreme. Për shembull, hëna rrotullohet rreth Tokës - të vërtetën; Toka sillet rreth Hënës - një gënjeshtër.

shumëzimit logjike dhe shtesë

Logjike dhe operacioni është quajtur një lidhje. Çfarë do të thotë? Së pari, se ai mund të zbatohet në dy operandëve, pra, unë - .. operacion Binary. Së dyti, kjo është vetëm në rastin e së vërtetës e të dy operandëve (të dy A dhe B) është i vërtetë dhe vetë shprehjes. Proverbi "Durimi dhe një përpjekje e vogël", nënkupton se vetëm dy faktorë mund të ndihmojë një person të përballen me vështirësitë.

Simbolet janë përdorur për regjistrimin: A∧B, A⋅B ose A && B.

Kombinimit është e ngjashme me shumëzimi në aritmetikë. Ndonjëherë dhe thonë - shumëzimin logjik. Nëse ju shumohen elementet e rreshtave të tabelës, ne kemi marrë një rezultat të ngjashëm me të menduarit logjik.

Ndarje është një logjik OR operacion. Është e vërtetë në qoftë se të paktën një nga deklaratat e vërtetë (ose A ose B). Ajo është shkruar si ky: A∨B, A + B ose A || B. Tabela e vërteta për këto operacione janë:

Ndarje shtesë të ngjashme aritmetike. operacion shtesë logjike ka vetëm një kufizim: 1 + 1 = 1. Por ne kujtojmë se në një format dixhital është i kufizuar në logjikën matematikore 0 dhe 1 (ku 1 - e vërteta, 0 - false). Për shembull, deklarata "në muze ju mund të shihni një kryevepër ose të gjejnë një kompani e mirë" do të thotë që ju mund të shihni veprat e artit, dhe është e mundur për të përmbushur një person interesant. Në të njëjtën kohë, nuk e përjashtoi mundësinë e përmbushjes së njëkohshme të dy ngjarjeve.

Funksionet dhe ligje

Pra, ne tashmë e dimë se çfarë operacioni logjike duke përdorur algjebër Boolean. Funksionet përshkruajnë të gjitha vetitë e elementeve të logjikës matematikore, dhe të na lejojë për të lehtësuar deklarata komplekse kompleksit. Më e qartë dhe e thjeshtë duket refuzimit pronë e operacioneve të derivateve. Nga derivate janë kuptuar XOR, implikimin dhe ekuivalencë. Siç e kemi lexuar vetem me operacionet themelore, dhe pastaj prona është gjithashtu vetëm e konsiderojnë ata.

Associativity do të thotë se në deklaratat të tilla si "të dy A dhe B, dhe B 'listë sekuencë prej operandëve nuk ka rëndësi. Formula shkruhet si me poshte:

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

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

Siç mund ta shikoni, kjo nuk është unik në lidhje, por një shkëputje.

Commutativity argumenton se rezultati i lidhur ose shkëputje nuk varet nga të cilat artikull u konsideruar në fillim:

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

Distributivity lejon të ditur kllapa në shprehje komplekse logjike. Rregullat janë të ngjashme me hapjes kllapa në shumëzimin dhe përveç në algjebër:

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

pronat njësi dhe e para, e cila mund të jetë një nga operandëve janë gjithashtu të ngjashme me shumëzimit algjebrike me zero ose një, dhe shtimin e një njësie:

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

Idempotency na tregon se nëse relativisht dy operandët barabarta si rezultat i operacionit është e njëjtë, ju mund të "hedhin" tejkalimi operandëve komplikoj arsyetimit. Dhe operacionet e kombinimit dhe shkëputje janë idempotent.

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

Blerja gjithashtu na lejon për të lehtësuar ekuacion. Absorbimi thekson se kur shprehja është aplikuar në një operandi, një tjetër operacion me të njëjtin element i rezultatit operandit është thithjen operacion.

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

Sekuenca e operacioneve

Sekuenca e operacioneve është e një rëndësie të madhe. Në fakt, si për algjebër, ka një funksion prioritet që përdor një algjebër Boolean. Formulat mund të thjeshtohet nënshtrohet vetëm rëndësinë e operacioneve. Renditja e më të rëndësishme të papërfillshme, ne marrim sekuencën e mëposhtme:

1. Mohimi.

2. Conjunction.

3. shkëputje, XOR.

4. Implikimi, ekuivalenca.

Siç mund ta shikoni, vetëm mohimin e së bashku dhe nuk kanë përparësi të barabartë. Një prioritet i shkëputje dhe XOR janë të barabartë, si dhe prioritetet e implikimit dhe ekuivalencë.

Funksionet e implikimit dhe ekuivalentimin

Siç kemi thënë, përveç operacionet themelore logjike, logjikës matematikore dhe teoria e algoritme që përdorin derivate. Kjo është më shpesh implikimi dhe ekuivalenca.

Implikimi apo pasojë logjike - kjo deklaratë, në të cilën një veprim është një kusht, dhe të tjera - si rezultat i zbatimit të tij. Me fjalë të tjera, ky propozim me pretekstin e "në qoftë se ... atëherë". "Pas darke vjen llogari." E. Për ngarje të shtrënguar në kodër sajë. Nëse nuk ka dëshirë për të lëvizur poshtë nga mali, dhe pastaj terhiq sajë nuk është e nevojshme. Është shkruar kështu: A → B ose A⇒B.

Ekuivalenca nënkupton se efekti neto ndodh vetëm kur të dy operandët janë të vërteta. Për shembull, natën i jep rrugën për ditë më pas (dhe vetëm atëherë), kur dielli ngrihet mbi horizont. Në gjuhën e logjikës matematikore të kësaj deklarate është shkruar si A≡B, A⇔B, A == B.

ligjeve të tjera të algjebër Boolean

Gjykimi Algjebra zhvillon, dhe shumë shkencëtarë të interesuar për të formuluar ligje të reja. Më të famshme janë konsideruar postulon skocez matematikan O. De Morgan. Ai vuri re dhe i dha një përkufizim të pronave të tilla si mohim të ngushtë, përveç dhe negative të dyfishtë.

Mbylle mohimi sugjeron se para kllapa ka mohuar: jo (A ose B) = jo A ose B. NUK

Kur operand është mohuar, pavarësisht nga vlera e saj, thonë se rreth kësaj:

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

Dhe së fundi, mohimi dyfishtë vetë kompenson. dmth para ose mohimi operandi zhduket ose të mbetet vetëm një.

Si për të zgjidhur teste

Logic nënkupton thjeshtimin paracaktuar ekuacione. Ashtu si në algjebër Gënjeshtra, është e nevojshme për të lehtësuar maksimalisht gjendjen e parë (për të hequr qafe e operacioneve të komplikuara të dhëna, dhe me ta), pastaj të fillojmë të shikojmë për një përgjigje të saktë.

Çfarë duhet të bëni për të lehtësuar? Convert të gjitha derivatet në një operacion të thjeshtë. Pastaj të zbulojë të gjitha kllapa (ose anasjelltas, për të bërë kllapa për të zvogëluar këtë element). Hapi i ardhshëm duhet të jetë për të përdorur pronat boolean algjebër në praktikë (pronat thithjen zero dhe një, dhe T.).

Në fund të fundit, ekuacioni duhet të përbëhet nga një numër minimal të panjohura, e kombinuar me operacione të thjeshta. Mënyra më e lehtë për të kërkuar një zgjidhje, në qoftë se ju bëni një numër të madh të negative të ngushtë. Atëherë përgjigja do të hapet sikur në vetvete.