Informatika. Pretvaranje Booleovih izraza

U predloženom radu će se detaljno razmotritiPitanje transformacije logičkim izrazima. Osim toga, predlažemo da se kratki tečaj na logiku, koja će se baviti osnovne zakone i koncepte. Pretvori logički izrazi - to je prilično kompliciran proces, ako nije upoznat sa svim nijansama temu.

informatika tečaj će činiti jednostavna izadovoljstvo, ako pažljivo pročitate ovaj članak i naučite pravila i zakone transformacije, rješavanje problema, te izrade sheme. Nudimo početi odmah.

logika znanosti

Osnovna logika - to je prilično teška tema,Ta pisano je toliko knjiga. Ovaj članak će se raspravljati o osnovama zakona transformacije logičkih izraza, to jest, informacija je najviše sažet i koncentriran. Potrebno je uzeti u obzir više smisla računalne tehnologije i izgradnju sheme.

Za početak, što je logika i zašto je potrebna? Važno je napomenuti da je to cijela znanost koja razmatra oblike i metode rasuđivanja. Sve što vidimo, čujemo ili činimo, poštujemo zakone. Bacili su loptu s visine - ona uvijek leti dolje, jer se pokorava zakonima fizike. U jutarnjim satima radimo aromatičnu kavu, dodamo šećer, a rasuti materijali se odmah otapaju u vodi, poštujući zakone fizike. Razgovaramo s prijateljima, dijelimo naše planove: "Ako dobro štitim posao, dobit ću crvenu diplomu", "neću moći doći automobilom, jer je popravljen". Bez uočavanja, gradimo sve naše razgovore, oslanjajući se na logiku i njezine zakone. Zašto onda znanost treba logiku? Naravno, znajući njezine zakone, moći ćete točno odrediti ishod bilo kojeg događaja, jer nećete morati djelovati nasumce i riskirati.

Iako je razmišljanje prilično kompliciran proces, ipak se može podijeliti na određene komponente, točnije, forme (uz pomoć onoga što se izražava misli):

• koncepti;
• izjave;
• rasuđivanje;
• dokazi.

Nadalje predlažemo da se prebacite na logičke funkcije i transformaciju logičkih izraza. Računalna znanost bit će za vas zabavna i prilično jednostavna tema ako pažljivo pročitate ovaj članak.

Logičke funkcije

Sada nudimo da se upoznate s logičnimfunkcije. Često u ulaznicama jedinstvenog državnog ispita u Dijelu B postoje zadaci za pretvaranje logičkih izraza u numeričke segmente. Ne mogu se riješiti bez poznavanja funkcija logike.

Koji je glavni zadatak ove znanosti? Naravno, proučavanje logičkih izraza (složenih i jednostavnih). Kako napraviti tešku izjavu? Spajanjem jednostavnih, što se događa snopovima, koji se obično nazivaju funkcijama.

Može se razlikovati ukupno pet paketa:

• inverzija (to jest, negacija, uz pomoć ove funkcije možete dobiti izjavu suprotnu ovome: danas idem u kino - danas ne idem u kino);
• disjunkcija (ova funkcija se često naziva logičnoOsim toga, kako bismo to pojasnili, dajmo jednostavan primjer iz života: "ako imam glavobolju ili bol u želucu, neću ići u školu" - taj će izraz biti istinit ako se uzme u obzir barem jedan od uvjeta;
• konjunkcija (često se naziva logično množenje: "ako operem suđe i radim domaću zadaću, onda ću ići u šetnju s prijateljima" - taj će izraz biti istinit, ako se uzmu u obzir dva uvjeta;
• implikacija (u logici ova funkcija se nazivanažalost, to se ne može ilustrirati životnom situacijom; lažna funkcija će biti ako želite nešto učiniti, ali to nije uspjelo, inače će funkcija biti istinita);
• ekvivalent (ili jednakost, ako su dvije izjave istinite ili lažne, onda kao rezultat dobijemo istinu).

Važno je napomenuti da je u računalnoj znanosti sve jednostavnoizraz je označen velikim slovom latinične abecede. Zatim, svakako zapamtite tablicu istine za svaku funkciju. Imajte na umu da nije potrebno učiti, dovoljno je samo razumjeti funkcije.

Tablice istine

veznik

Prvi izraz (A)	Drugi izraz (B)	Rezultat (C)
L	L	L
i	L	L
L	i	L
i	i	i

Disjunkcija

Ah.	U	C
L	L	L
i	L	i
L	i	i
i	i	i

inverzija

Ah.	U
i	L
L	i

Implikacija

Ah.	U	C
L	L	i
i	L	L
L	i	i
i	i	i

Logički jednakosti

Ah.	U	C
L	L	i
i	L	L
L	i	L
i	i	i

Osim toga, to je napomenuti i totfakt koje leže u logici je označen broj 0, a pravi izraz znamenke 1.Radi vaše udobnosti, možete primijeniti i plus i minus znakovi.Obratite pozornost na činjenicu da lažni i istinski izraz predložene tablice su označene s slova "l" i "odnosno.

zgrada

Prije premještanja na transformirati Booleovih izraza, to je potrebno upoznati se sa svojim graditi.Bilo koji spoj ili, kako je rekao prije, složeni izrazod dva dijela:

• varijable koje su označene velikim slovima latinske abecede;
• znakovi koji označavaju funkciju i međusobno povezuju jednostavne izraze.

Kako napraviti izraz u jeziku algebre logike? Da biste to učinili, morate učiniti nekoliko stvari:

• podijeliti sve izjave na jednostavne izraze;
• označite ove elemente;
• istaknuti odnos između jednostavnih izraza;
• napišite dobiveni izraz pomoću posebnih simbola algebre logike.

Predlažemo da razmotrimo jednostavan primjer: (Z * F = 5 ili Z * F = 4) I (Z * F nije jednako 5 ili Z * F nije jednako 4). Za varijable je potrebno zamijeniti 2. Nakon toga dobivamo izraz (4 = 5 ili 4 = 4) i (4 nije jednak 5 ili 4 nije jednak 4). Nakon operacija koje smo obavili, moramo razlikovati izraze i veze između njih, treba ispasti kako slijedi: (Z ili F) i (ne Z ili ne F). Nakon toga trebamo pretvoriti taj zapis, zamjenjujući vrijednosti izraza. U slučaju da je izraz istinit, tada je potrebno zamijeniti 1, inače - 0. Dobivamo: G = 1 i 1. Nakon potrebnih izračuna dobivamo rezultat: G = 1, tj. Složeni izraz je istinit.

zakoni

Sada predlažemo da razmotrite zakone logike ipravila konverzije logičkog izraza. Važno je napomenuti da se svaki logički izraz može pretvoriti u drugi pomoću zakona logike. Sada ćemo detaljno razmotriti svih deset pravila.

Prvi na našem popisu je "zakon dvostruke negacije". To jest, izraz "ne (ne A)" će biti jednak izrazu "A".

Komunikativno pravo je u matematici, vrlo je lako zapamtiti. A + B = B + A, A * B = B * A.

Kombinacijski zakon je (D + E) + F = (D + F) + E, isti zakon se primjenjuje na logičko množenje.

Zakon o distribuciji je elementarno otvaranje zagrada. Primjer: (A + B) * C = (A * C) + (B * C).

De Morganov zakon: nije (A + B) = ne-A * ne-B, ne (A * B) = ne-A + ne-B, Aimplikacija B = ne A + B, ne (Amplifikacija B) = A * nije B

Idempotencija: X + X = X ili C * C = C.

Iznimka od konstanti: X + 1 = 1, X + 0 = X; X * 1 = X, X * 0 = 0.

Zatim ističemo zakon kontradikcije, slijedeći ga, možemo tvrditi sljedeću jednakost: B * nonB = 0.

U logici postoji i zakon apsorpcije, koji je u praksi sljedeći: C + (C * D) = C ili C * (C + D) = C.

Također je važno pretvoriti logičke izraze u zapamćeni zakon eliminacije (C * E) + (HC * E) = E ili (C + E) * (HC + E) = E.

Ako pregledate i zapamtite sve u detaljepredstavljeni u ovom odjeljku zakona, onda se problemi s transformacijom nikada neće pojaviti. Jednako je važan i redoslijed funkcija. Obratite više pozornosti na ovu stavku, ispravna raspodjela redoslijeda funkcija je ključ za ispravno rješenje problema.

Pravila i zakoni transformacije i pojednostavljenja, redoslijed postupaka s primjerima

Logički zakoni i pravila transformacijelogički izrazi su vrlo lako zapamtiti. Ako sumnjate u istinitost barem jednog od njih, provjerite sami. Da biste to učinili, morate provesti 10 minuta svog vremena i stvoriti tablice istine kako biste dobili odgovor.

Sada predlažemo da razmotrimo logičke zakone ipravila za pretvaranje logičkih izraza sa specifičnim primjerima. To je nužno kako bi se pravilno stečeno znanje konsolidiralo. Obratite posebnu pozornost na slijed radnji.

S obzirom na nas: C + (ne C * E). Potrebno je pojednostaviti izraz. Prvi korak je otvaranje zagrada. Tada dobijemo izraz: (C + nonC) * (C + E). Odmah uočavamo da nam logično dodavanje dviju suprotstavljenih izjava daje istinu. Ono što dobivamo na kraju: 1 * (C + E). Ponovo otvorite zagrade: (1 * S) + (1 + E). Sada se još jednom sjećamo zakona i dobijemo odgovor: C + E.

Kao što možete vidjeti, sve je vrlo jednostavno. Za rješavanje takvih problema potrebno je zapamtiti zakone koji su navedeni u posljednjem odjeljku. Predlažemo rješavanje logičkih problema, jer je taj zadatak već malo složeniji od prethodnog.

Rješavanje problema

Upoznali smo se s osnovama znanosti"Logika", transformacija logičkih izraza, ukratko smo pregledali, a zakoni su navedeni. Najteži zadaci s kompilacijom logičkih izraza su zadaci. Važno je napomenuti da se oni mogu riješiti pomoću rasuđivanja, transformacije izraza ili tabularne metode. Predlažemo da jedan od njih razmotrimo detaljno.

Tri dječaka (Kirill, Anton i Kostya) su bili ujednokrevetna soba. Iznenada, majka iz kuhinje čuje zvuk slomljene šalice. Potrčala je do svojih sinova i upitala: "Tko je to učinio?" Odgovor je bio sljedeći: Kirill je rekao da nije Kostya razbio kup, nego Anton; Anton je rekao da je Kostya to učinio, a ne Kirill; Kostya tvrdi da Anton nije krivac. Znamo da je jedan od dječaka pogrešno rekao majci. Moramo saznati tko je razbio šalicu.

Logično, odgovori Cyrila iAnton proturječi jedni drugima, kao i Kirilu s Kostjom. Dakle, ne mogu oboje biti istinite. Donosimo sljedeći zaključak - Anton i Kostya su rekli istinu, a Ćiril je krivac slomljene čaše. To je bio način razmišljanja. Sada ćemo razmotriti rješenje istog problema, samo koristeći metodu pretvaranja izraza. Prvo, uvodimo kratice:

• KR - Ćiril razbija šalicu;
• A - Anton je slomio šalicu;
• K - krivac Kostya.

Odgovori dječaka:

• Ćiril - nekiK, A;
• Anton - NeKR, K;
• Kostya - ne.

Nudimo da izrazimo, ako KostyaLagao je, a Cyril i Anton su govorili istinu: NK * A = 1 i K * NKR = 1 i A = 1. Pretvarajući izraz, dobivamo kontradikciju: 0 = 1. Naša je pretpostavka pogrešna, vrijedno je provjeriti i druge pretpostavke.

Ako pretpostavimo da je Cyril lagao, i Antoni Kostya je majci rekao istinu, dobili smo sljedeći izraz: K * nonA = 1 i K * NeKR = 1 i nonA = 1. Pojednostavljujući izraz, dobivamo CR * nonA * neK = 1. To sugerira da je naša pretpostavka bila istinita, doista, Cyril je razbio šalicu i lagao majci.

Tablično rješenje

Razmatrani zakoni logike i transformacijelogički izrazi su nam sigurno pomogli da se nosimo sa zadatkom koji je prikazan u prethodnom dijelu. Sada nudimo tabularnu metodu rješavanja sljedećeg problema.

Dmitry, Anatoly i Lyudmila su obožavateljipoštanska korespondencija, znamo da svatko živi u različitim dijelovima svijeta i ima drugačiji hobi. Odredite tko živi u kojem gradu i što uživa. Poznate su sljedeće činjenice:

• Dmitry nikada nije bio u Parizu, a Lyudmila - u Rimu;
• onaj koji živi u Parizu ne voli kino;
• čovjek koji živi u Rimu radi vokale;
• Lyudmila je zgrožena baletom.

Da biste riješili problem, trebate napraviti mali stol.

Francuska	Italija	Sjedinjene Države		vokal	balet	film
			Dmitry
			Anatolij
			Ljudmila

Nadalje, potrebna vam je maksimalna pozornost. Sve što pročitate u takvom stanju trebalo bi se odraziti u ovoj tablici. Tijekom popunjavanja postat će jasno sljedeće:

• Dmitry živi u Rimu i bavi se vokalom;
• Anatolij živi u Parizu i često posjećuje balet;
• Lyudmila je veliki ljubitelj kinematografije koja živi u SAD-u.

Još jednom napominjemo da je pravi izraz označen brojem 1, a lažni izraz je 0. Ako popunite tablicu ovim simbolima, brzo ćete pronaći odgovor na pitanje koje vas zanima.

Mikroskhematika

Primjeri pretvorbe logičkih izrazakoje smo pregledali, na prvi su pogled vrlo složeni. U kartama jedinstvenog državnog ispita, uvjet se može dati u obliku mikrokreta.

Važno je znati da se svi digitalni uređaji temelje na logičkim elementima, odnosno na određenim uređajima koji obavljaju jednu logičku funkciju.

Već smo razgovarali o takvoj funkciji kao poveznici(logičko množenje). Obično je označen simbolom &. Ova funkcija je potrebna za spajanje nekoliko vrijednosti. Na slici vidite logičku shemu množenja.

Funkcija disjunkcije je potrebna za implementaciju disjunkcije nekih ulaznih vrijednosti. Kod pisanja izraza, ova funkcija se obično označava simbolom. Slika prikazuje shemu.

Funkcija inverzije služi kao pretvarač jednog izraza u suprotno. Na slici vidite kako izgleda dijagram "ne".

Primjer pojednostavljenja formule # 1

Razmotrena su pravila logičke konverzijeizrazi moraju biti utvrđeni u praksi. Upravo u ostvarenju tog cilja predlažemo da samostalno riješimo dva primjera srednje složenosti i usporedimo ih s rezultatima u ovom dijelu članka.

Ako niste imali vremena zapamtiti formule za pretvaranje logičkih izraza, tada možete napraviti mali podsjetnik. Vidjet ćete da uskoro nećete špijunirati.

Primjer: (X + T) * (Hex + T) * (M + NeT). Nemojte slijepo otpisivati, pokušajte sami riješiti primjer.

Tijekom pojednostavljenja dobivamo sljedeće podatke: T * (M + NT) = (T * M) + (T * NT) = (T * N) + 0 = (T + 0) * (M + 0) = T * M.

Kao što vidite, iz prilično dugog i glomaznogsloženi izraz, imamo kratki T * M. Ako niste uspjeli sami riješiti ovaj primjer, onda se ponovno osvrnite na točku u kojoj smo razmatrali transformaciju logičkih izraza, probleme.

Primjer pojednostavljenja formule # 2

U ovom odjeljku predlažemo da pojednostaviteizraz (E + N) * (E + K). Analiziramo rješenje u fazama. Prije svega, moramo otvoriti zagrade, sjetiti se tijeka osnovne matematike. Kao rezultat toga dobivamo sljedeći izraz: E * E + E * K + N * E + N * K. Nadalje, primjećujemo da u rezultirajućem izrazu postoji dio E * E, prisjećamo se zakona idempotencije i pretvorimo zapis: E + E * K + N * E + N * K. Sljedeći korak je transformacija dijela E + E * K, iskorištavanjem uklanjanja varijable E i svojstva: A + 1 = 1. Dobivamo izraz: E + N * E + N * K. Isto tako slijedimo posljednju točku i stavljamo je izvan zagrada E. Kao rezultat, dobivamo odgovor: E + N * K.

Obratite pozornost na činjenicu da se zadaci na prvi pogled čine teškim. Da bi ih "kliknuli kao sjemenke", trebate samo naučiti osnovne zakone logike.

</ p>>