Boolova algebra. Algebra logike. Elementi matematične logike

V sodobnem svetu vedno bolj uporabljamo različne stroje in pripomočke. In ne samo takrat, ko je treba uporabiti dobesedno nadnaravno moč: premikanje bremena dvigniti do višine, kopati globoko in globok jarek, itd Avtomobili danes zbrali roboti, je hrana kuhana Multivarki in osnovni izračuni aritmetičnih proizvodnjo računala ... Vse pogosteje slišimo izraz "Boolova algebra". Morda je prišel čas, da razumejo vlogo človeka pri oblikovanju robotov in strojev sposobnost reševanja ne le matematična, ampak logične naloge.

Logika

Prevedeno iz grške, logika je urejen sistem razmišljanja, ki ustvarja odnose med danimi pogoji in omogoča sklepanje na podlagi predpostavk in predpostavk. Pogosto se medsebojno sprašujemo: "Ali je to logično?" Odgovor odgovarja na naše domneve ali kritizira potek misli. Toda proces se ne ustavi: še naprej razumemo.

Včasih je število pogojev (uvodnih) tako veliko in so medsebojne povezave tako zmedene in zapletene, da človeški možgani ne morejo "prebaviti" vse hkrati. Za razumevanje, kaj se dogaja, lahko traja več kot en mesec (teden, leto). Vendar sodobno življenje nam ne daje takšnih časovnih presledkov za odločanje. In se zatežemo na pomoč računalnikov. In tu se pojavlja algebra logike s svojimi zakoni in lastnostmi. Ko prenesemo vse začetne podatke, računalniku omogočamo, da prepozna vsa razmerja, odpravi nasprotja in najde zadovoljivo rešitev.

Matematika in logika

Najbolj znani Gottfried Wilhelm Leibniz je oblikoval koncept »matematične logike«, katere naloge so bile dostopne le ozkim krogom znanstvenikov. Poseben interes v tej smeri ni povzročil, do sredine XIX. Stoletja pa le nekaj o matematični logiki.

Veliko zanimanje za znanstvene skupnosti je sprožil spor, v katerem je angleški človek George Buhl napovedal, da namerava ustvariti del matematike, ki ni imel nikakršne praktične uporabe. Kot se spominjamo iz zgodovine, je takrat industrijska proizvodnja dejavno razvijala, razvili so se vse vrste pomožnih strojev in strojev, torej vsa znanstvena odkritja so imela praktično usmeritev.

Če pogledamo naprej, pravimo, da je Boolova algebra najbolj uporaben del matematike v sodobnem svetu. Tako je spor izgubil Boula.

George Boule

Posebno pozornost si zasluži zelo osebnost avtorja. Tudi ob upoštevanju dejstva, da so v preteklosti ljudje postali starejši, kot mi še vedno ne moremo opozoriti, da je bil pri 16 letih J. Bull poučeval na vasi in do 20. leta odprl svojo šolo v Lincolnu. Matematik je popolnoma obvladal pet tujih jezikov, v prostem času pa je prebrala dela Newtona in Lagrangea. In vse to je o sinu preprostega delavca!

Leta 1839 je Boule najprej poslal znanstvene članke v Cambridge Mathematical Journal. Znanstvenik je bil star 24 let. Delo Boole je bilo tako zanimivo za člane Kraljevskega znanstvenega društva, da je leta 1844 prejela medaljo za svoj prispevek k razvoju matematična analiza. Več drugih objavljenih del, v katerih so opisani elementi matematične logike, so mlademu matematiku omogočili, da je zasedel profesorja na kolegiju Cork County. Spomnimo se, da sam ni bil izobražen.

Ideja

Načeloma je Boolova algebra zelo preprosta. Obstajajo izjave (logično izrazi), ki se z vidika matematike lahko definirajo le z dvema besedama: "resnica" ali "laž". Na primer, spomladi drevesa cvetijo - resnica, poleti pa sneži - laži. Vsa čar tega matematike je, da ni stroge potrebe po uporabi samo številk. Za algebro predlogov so popolnoma primerni vsi stavki z nedvoumnim pomenom.

Tako se lahko logična algebra uporabi povsem povsod: pri načrtovanju in pisanju navodil, analiziranju nasprotujočih si informacij o dogodkih in določanju zaporedja dejanj. Najpomembnejša stvar je razumeti, da ni važno, kako smo določili resnico ali neresničnost izjave. Iz teh "kako" in "zakaj" je treba izvleči. Edina stvar, ki je pomembna, je izjava o dejstvih: resnično-napačno.

Seveda so funkcije algebre logike pomembne za programiranje, ki so napisane z ustreznimi znaki in simboli. In da jih naučijo pomeni obvladati nov tuji jezik. Nič ni nemogoče.

Osnovni pojmi in definicije

Ne bomo šli v globino, razumeli bomo terminologijo. Torej, Boolova algebra prevzame prisotnost:

• izjave;
• logične operacije;
• funkcije in zakoni.

Izjave so vsi pritrdilni izrazi, ki jih ni mogoče razlagati dvojno. Pisane so v obliki številk (5> 3) ali pa so formulirane z običajnimi besedami (slon je največji sesalec). V tem primeru beseda "žirafa nima vratu" ima tudi pravico do obstoja, le Boolova algebra jo bo opredelila kot "laž".

Vse izjave morajo biti nedvoumne, vendar so lahko osnovne in sestavljene. Slednji uporabljajo logične povezave. To pomeni, da so v propozicijskih algebrskih izračunih sestavljene z dodajanjem elementarnih elementov skozi logične operacije.

Operacije Boolove algebre

Že vemo, da so operacije v algebri predlogov logične. Tako kot algebra številk uporablja aritmetične operacije za dodajanje, odštevanje ali primerjavo števil, elementi matematične logike omogočajo sestavljanje kompleksnih izjav, zanikanje ali izračun končnega rezultata.

Logične operacije za formalizacijo in preprostost so zapisane s formulami, ki so običajne za nas v aritmetiki. Lastnosti Boolove algebre omogočajo pisanje enačb in izračun neznanih. Logične operacije so običajno napisane z uporabo tabele resnic. Njeni stolpci določajo elemente za izračun in operacijo, ki se izvaja na njih, vrstice pa prikazujejo rezultat izračuna.

Osnovni logični ukrepi

Najpogostejše operacije v logičnih operacijah so negacija (NOT) in logična AND in OR. Torej lahko opisate skoraj vse ukrepe v algebro sodb. Podrobno bomo podrobno preučili vsako od treh operacij.

Zavrnitev (ne) velja samo za en element (operand). Zato je operacija negacije imenovana unary. Za pisanje koncepta, ki ne vsebujejo A, uporabite naslednje simbole: ne-A, Amacr-macr-macr- ali! A. V tabeli obliki je videti tako:

Za funkcijo negacije je tipična naslednja trditev: če je A resnična, potem je A napačna. Luna se na primer vrti okoli Zemlje - resnica - Zemlja se vrti okoli Lune - laž.

Logično množenje in dodajanje

Logično AND se imenuje operacija konjunkcije. Kaj to pomeni? Prvič, da ga lahko uporabimo za dva operanda, to je, jaz sem binarni postopek. Drugič, samo to, da je resnica obeh operandov (in A in B), je izraz sam. Pregovor "Patience in delo bo peretrut" predpostavlja, da bo le dva dejavnika pomagala pri soočanju s težavami.

Za pisanje se uporabljajo simboli Aand-B, Asdot-B ali AB.

Konjunkcija je analogna množenju v aritmetiki. Včasih pravijo tako logično množenje. Če pomnožimo elemente tabele po vrsticah, dobimo rezultat, podoben logičnemu razmišljanju.

Disjunkcija se imenuje logično operacijo OR. Ko je vsaj eden izmed teh, potrebuje resnico izjave so resnične (ali A ali B). Tako je napisano: Aor-B, A + B ali A || B. Tabele resničnosti za te operacije so:

Disjunkcija je kot aritmetični dodatek. Delovanje logičnega dodajanja ima samo eno omejitev: 1 + 1 = 1. Vendar se spomnimo, da je v digitalni obliki matematična logika omejena na 0 in 1 (kjer je 1 res, 0 je napačno). Na primer, izjava »v muzeju si lahko ogledate mojstrovino ali srečate zanimivega sogovornika« pomeni, da si lahko ogledate umetniška dela in se lahko seznanite z zanimivo osebo. Hkrati ni izključena možnost hkratnega izpolnjevanja obeh dogodkov.

Funkcije in zakoni

Torej, že vemo, katere logične operacije uporablja Boolova algebra. Funkcije opisujejo vse lastnosti elementov matematične logike in vam omogočajo, da poenostavite kompleksne sestavljene pogoje nalog. Najbolj razumljivo in enostavno je lastnost opuščanja izvedenih operacij. Izvedeni finančni instrumenti so izključni OR, impliciranje in enakovrednost. Ker smo se seznanili samo z osnovnimi operacijami, bomo upoštevali le njihove lastnosti.

Združljivost pomeni, da v izjavah, kot so "in A, B in B", štetje operandov ni pomembno. Formula je naslednja:

(Aand-B) in -B = Aand- (Band-B) = A-Band-B,

(Aor-B) ali -B = Aor- (Bor-B) = Aor-Bor-B.

Kot vidimo, je to nenavadno le za sonde, temveč tudi za disjunkcije.

Komutativnost trdi, da rezultat konjunkcije ali disjunkcije ni odvisen od tega, kateri element je bil upoštevan na začetku:

A-B = pas-A-Aor-B = BOR-A.

Distributivnost vam omogoča odpiranje oklepajev v zapletenih logičnih izrazih. Pravila so podobna razkritju oklepajev pri pomnoževanju in dodajanju v algebra:

Aand- (Bor-B) = Aand-Bor-Aand-B-Aor-Band-B = (Aor-B) in- (Aor-B).

Lastnosti enote in nič, ki so lahko eden od operandov, so tudi analogne algebraičnemu množenju z ničlo ali eno in dodatek k enemu:

Aand-0 = 0, Aand-1 = A-Aor-0 = A, Aor-1 = 1.

Idempotentnost nam pove, da če se izid operacije izkaže za podoben glede na dva enakopravna operanda, potem lahko "izvržete" dodatne opere, ki otežujejo potek razmišljanja. Konjunkcija in disjunkcija sta idempotentni postopki.

BAND-B = B-BOR-B = B.

Absorpcija omogoča tudi poenostavitev enačb. Absorpcija pravi, da če se operacija z istim operandom uporabi za izraz z enim operandom, je rezultat operand iz absorpcijske operacije.

Aand-Bor-B = B- (Aor-B) in B = B.

Zaporedje operacij

Zaporedje operacij ni nič pomembnega. Pravzaprav, kot velja za algebra, obstaja prednostna naloga funkcij, ki uporabljajo Boolove algebre. Formule je mogoče poenostaviti le, če opazimo pomembnost operacij. Razvrstitev od najpomembnejših do manjših, dobimo naslednje zaporedje:

1. Zavrnitev.

2. Konjunkcija.

3. Disjunkcija izključuje OR.

4. Vpliv, enakovrednost.

Kot vidimo, samo zanikanje in konjunkcija nimata enakih prednostnih nalog. Prednost disjunkcije in ekskluzivni OR sta enaka, pa tudi prednostne naloge implicitne in enakovredne narave.

Implikacije in enakovredne funkcije

Kot smo že povedali, poleg osnovnih logičnih operacij matematična logika in teorija algoritmov uporabljajo derivate. Najpogosteje uporabljene posledice in enakovrednost.

Implikacija ali logično sledenje je izjava, v kateri je eno dejanje pogoj, drugo pa je posledica njegove izpolnitve. Z drugimi besedami, ta stavek z izgovori "če ... potem." "Všeč ste, da se vozite, ljubite in sankate, da jih nosite." To pomeni, da je za drsanje potrebno pritrditi sani na hrib. Če ni želje zapustiti gore, potem vam ni treba nositi sani. Pisano je tako: A → B ali ArArr-B.

Enakovrednost predpostavlja, da nastalo dejanje nastane le, če sta oba operanda resnična. Na primer, noč se nadomesti z današnjim danom (in šele takrat), ko sonce vzhaja iz obzorja. V jeziku matematične logike je ta izjava napisana kot: Aequiv-B, AhArr-B, A == B.

Drugi zakoni Boolove algebre

Razvija se sodna algebra in mnogi zainteresirani znanstveniki so oblikovali nove zakone. Najbolj znani so postulati škotskega matematika O. de Morgana. Opazil in opredelil je take lastnosti kot tesno negiranje, dodajanje in dvojno negiranje.

Zapri Negation predlaga, da pred nosilcem ni ene negacije: ne (A ali B) = ne A ali ne B.

Ko je operand zanikan, ne glede na njen pomen, Poleg tega:

Band-ne-B = 0- Bor-ne-B = 1.

In končno, dvojna negacija se kompenzira. Torej. Pred operandom izguba izgine ali ostane samo ena.

Kako rešiti teste

Logic pomeni poenostavitev, vnaprej enačb. Tako kot v Lie algebra, je treba čim bolj olajšati prvi pogoj (da se znebite zapletenih vhodnih operacij in z njimi), nato pa začeli iskati za pravilen odgovor.

Kaj lahko storimo za poenostavitev stvari? Pretvorite vse izpeljane operacije v preproste. Nato odprite vse oklepaje (ali obratno, naredite oklepaje, da skrajšate ta element). Naslednji korak je, da v praksi uporabimo lastnosti Boolove algebre (absorpcija, lastnosti nič in enote itd.).

Konec koncev mora biti enačba sestavljena iz najmanjšega števila neznanih, združenih s preprostimi operacijami. Najlažje je iskati rešitev, če dosežemo veliko število tesnih negacij. Potem se bo odgovor pojavil kot sam po sebi.