Funksioni logjikështë një funksion në të cilin variablat marrin vetëm dy vlera: logjike një ose zero logjike. E vërteta ose falsiteti i gjykimeve komplekse është funksion i së vërtetës ose falsitetit të gjykimeve të thjeshta. Ky funksion quhet funksioni i gjykimit Boolean f (a, b).

Çdo funksion logjik mund të specifikohet duke përdorur një tabelë të së vërtetës, në anën e majtë të së cilës është shkruar një grup argumentesh, dhe në anën e djathtë - vlerat përkatëse të funksionit logjik.

Kur ndërtohet një tabelë e së vërtetës, është e nevojshme të merret parasysh rendi në të cilin kryhen veprimet logjike. Veprimet në një shprehje Boolean kryhen nga e majta në të djathtë, duke iu nënshtruar kllapave, në rendin e mëposhtëm:

• 1. përmbysja;
• 2. lidhëz;
• 3. shkëputje;
• 4. implikimi dhe ekuivalenca.

Kllapat përdoren për të ndryshuar rendin në të cilin kryhen veprimet logjike.

Propozohet si më poshtë Algoritmi i ndërtimit të tabelës së së vërtetës.

• 1. Përcaktoni numri i grupeve të variablave hyrëse- të gjitha kombinimet e mundshme të vlerave të variablave të përfshira në shprehje, sipas formulës: Q = 2 n, ku n është numri i variablave hyrëse. Ai përcakton numrin e rreshtave në tabelë.
• 2. Futni të gjitha grupet e variablave hyrëse në tabelë.
• 3. Përcaktoni numrin e veprimeve logjike dhe sekuencën e ekzekutimit të tyre.
• 4. Plotësoni kolonat me rezultatet e kryerjes së veprimeve logjike në sekuencën e treguar.

Për të mos përsëritur ose humbur asnjë kombinim të mundshëm të vlerave të variablave hyrëse, duhet të përdorni një nga metodat e mëposhtme për plotësimin e tabelës.

Metoda 1. Çdo grup vlerash të ndryshoreve fillestare është një kod i një numri në sistemin e numrave binar, dhe numri i shifrave të numrit është i barabartë me numrin e ndryshoreve hyrëse. Seti i parë është numri 0. Duke shtuar 1 në numrin aktual çdo herë, marrim grupin tjetër. Grupi i fundit është vlera maksimale binare për gjatësinë e kodit të dhënë.

Për shembull, për një funksion të tre variablave, sekuenca e grupeve përbëhet nga numra:

Metoda 2. Për një funksion prej tre variablash, sekuenca e të dhënave mund të merret në mënyrën e mëposhtme:

• a) ndani kolonën e vlerave të ndryshores së parë në gjysmë dhe mbushni gjysmën e sipërme me zero, gjysmën e poshtme me një;
• b) në kolonën tjetër për variablin e dytë, ndajeni sërish gjysmën në gjysmë dhe plotësoni grupet me zero dhe njëshe; mbushni gjysmën e dytë në të njëjtën mënyrë;
• c) bëjeni këtë derisa grupet e zeros dhe njëshit të përbëhen nga një karakter.

Metoda 3. Përdorni një tabelë të njohur të së vërtetës për dy argumente. Duke shtuar argumentin e tretë, fillimisht shkruani 4 rreshtat e parë të tabelës, duke i kombinuar me vlerën e argumentit të tretë të barabartë me 0, dhe më pas shkruani të njëjtat 4 rreshta, por tani me vlerën e argumentit të tretë të barabartë me 1. Si rezultat, tabela për tre argumente do të jetë 8 rreshta:

Për shembull, le të ndërtojmë një tabelë të së vërtetës për një funksion logjik:

Numri i variablave hyrëse në shprehjen e dhënë është tre (A, B, C)... Prandaj, numri i grupeve të hyrjes Q = 2 3 =8 .

Kolonat e tabelës së së vërtetës korrespondojnë me vlerat e shprehjeve origjinale A, B, C, rezultatet e ndërmjetme dhe ( B V C), si dhe vlerën përfundimtare të dëshiruar të një shprehje komplekse aritmetike:

• 0 0 0 1 0 0
• 0 0 1 1 1 1
• 0 1 0 1 1 1
• 0 1 1 1 1 1
• 1 0 0 0 0 0
• 1 0 1 0 1 0
• 1 1 0 0 1 0
• 1 1 1 0 1 0
• 7.4. Funksionet logjike dhe shndërrimet e tyre. Ligjet e logjikës

Për operacionet e lidhjes, shkëputjes dhe përmbysjes, përcaktohen ligjet e algjebrës së Bulit, të cilat bëjnë të mundur prodhimin shndërrime identike (ekuivalente) të shprehjeve logjike.

Ligjet e logjikës

• 1. ¬¬ A
• 2. A&B
• 3. AVB
• 4. A & (B&C)
• 5. AV (BVC)
• 6.A & (BVC)
• 7. AV (B&C)
• 8. A&A
• 9. AVA
• 10. AV¬A
• 11.A & ¬A
• 12. A&I
• 13. AVI
• 14.A&L
• 15. AVL
• 16. ¬ (A&B)
• 17. ¬ (AVB)
• 18.A => B

Bazuar në ligje, ju mund të thjeshtoni shprehjet komplekse Boolean. Ky proces i zëvendësimit të një funksioni logjik kompleks me një funksion më të thjeshtë, por të barabartë me të, quhet minimizim i funksionit.

Shembulli 1. Thjeshtoni shprehjet në mënyrë që formulat që rezultojnë të mos përmbajnë mohimin e shprehjeve komplekse.

Zgjidhje

Shembulli 2. Minimizo funksionin

Për të thjeshtuar shprehjen, u përdorën formulat e përthithjes dhe ngjitjes.

Shembulli 3. Gjeni mohimin e pohimit të mëposhtëm: "Nëse mësimi është interesant, atëherë asnjë nga studentët (Misha, Vika, Sveta) nuk do të shikojë nga dritarja."

Zgjidhje

Le të përcaktojmë deklaratat:

Y- "Mësimi është interesant";

M- "Misha shikon nga dritarja";

B- "Vika shikon nga dritarja";

C- "Sveta shikon nga dritarja."

Gjatë thjeshtimit të shprehjes, u përdor formula për zëvendësimin e operacioneve dhe ligji i de Morgan.

Shembulli 4. Përcaktoni pjesëmarrësin në krim bazuar në dy premisa: tabela logjike kompjuterike

• 1) "Nëse Ivanov nuk ka marrë pjesë ose Petrov ka marrë pjesë, atëherë Sidorov ka marrë pjesë";
• 2) "Nëse Ivanov nuk ka marrë pjesë, atëherë Sidorov nuk ka marrë pjesë."

Zgjidhje

Le të hartojmë shprehje:

Unë- "Ivanov mori pjesë në krim";

P- "Petrov mori pjesë në krim";

S- "Sidorov mori pjesë në krim".

Le t'i shkruajmë parcelat në formën e formulave:

Le të kontrollojmë rezultatin duke përdorur tabelën e së vërtetës:

Përgjigje: Ivanov mori pjesë në krim.

Ndërtimi i një funksioni logjik nga tabela e tij e së vërtetës

Ne kemi mësuar se si të bëjmë një tabelë të vërtetësisë për një funksion logjik. Le të përpiqemi të zgjidhim problemin e kundërt.

Konsideroni rreshtat ku vlera e së vërtetës së funksionit Z është e vërtetë (Z = 1). Funksioni për këtë tabelë të vërtetësisë mund të përbëhet si më poshtë: Z (X, Y) = (¬ X & ¬Y) V (X & ¬Y).

Çdo rresht ku funksioni është i vërtetë (i barabartë me 1) i korrespondon një kllapa, e cila është një lidhje argumentesh, dhe nëse vlera e argumentit është O, atëherë e marrim atë me mohim. Të gjitha kllapat janë të lidhura me një operacion shkëputjeje. Formula që rezulton mund të thjeshtohet duke zbatuar ligjet e logjikës:

Z (X, Y)<=>((¬X & ¬Y) VX) & ((¬X & Y) V ¬Y)<=>(XV (¬X & ¬Y)) & (¬YV (¬X & ¬Y))<=>((XV¬X) & (XV ¬Y)) & ((Y¬V ¬X) & (¬YV ¬Y))<=>(1 & (XV ¬Y)) & ((¬YV ¬X) & ¬Y)<=>(XV ¬Y) & ((¬YV ¬X) & ¬Y).

Kontrolloni formulën që rezulton: bëni një tabelë të së vërtetës për funksionin Z (X, Y).

Shkruani rregullat për ndërtimin e një funksioni logjik sipas tabelës së tij të së vërtetës:

• 1. Zgjidhni në tabelën e së vërtetës ato rreshta në të cilat vlera e funksionit është e barabartë me 1.
• 2. Shkruani formulën e kërkuar në formën e një ndarje të disa elementeve logjike. Numri i këtyre elementeve është i barabartë me numrin e rreshtave të zgjedhur.
• 3. Çdo element logjik në këtë disjunksion shkruhet si lidhëz i argumenteve të funksionit.
• 4. Nëse vlera e ndonjë argumenti funksioni në rreshtin përkatës të tabelës është 0, atëherë këtë argument e marrim me mohim.

1. Përcaktoni radhën e veprimeve.

2. Përcaktoni dimensionin e tabelës së vërtetës.

Numri i kolonave përcaktohet nga numri i variablave logjikë (ka dy A, B) dhe numri i veprimeve (ka edhe dy prej tyre).

4. Formuloni një përgjigje.
Kolona e fundit ka një "0" që korrespondon me A të barabartë me "1" dhe B të barabartë me "0". Rezulton se ky funksion është i gabuar nëse dhe vetëm nëse ndryshorja logjike A është e vërtetë, dhe ndryshorja logjike B është false, që i përgjigjet funksionit logjik PASOJË.
Prandaj, ky funksion është i barabartë me pasojën logjike të variablave A dhe B: Nëse A, atëherë B.

Krijoni një tabelë të së vërtetës për një funksion logjik:

1. Përcaktoni radhën e veprimeve.

2. Përcaktoni dimensionin e tabelës së vërtetës.

"Titulli" i tabelës përmban dy rreshta - numrat e veprimeve dhe operacionet logjike të veprimeve.
Numri i kolonave përcaktohet nga numri i ndryshoreve logjike (ka dy A, B) dhe numri i veprimeve (janë pesë prej tyre).
Numri i rreshtave në tabelë është i barabartë me dy me fuqinë e barabartë me numrin e ndryshoreve logjike - në rastin e dy variablave, fitohen 4 rreshta.
3. Plotësoni një nga një kolonat e tabelës në përputhje me funksionin logjik të kësaj kolone.


4. Formuloni një përgjigje.
Në kolonën e fundit "1" korrespondon me A të barabartë me B, dhe "0" - A me B të pabarabartë. Rezulton se ky funksion është i vërtetë kur A është i barabartë me B dhe i gabuar kur A nuk është i barabartë me B, që korrespondon te funksioni logjik IDENTITY.
Prandaj, ky funksion është i barabartë me IDENTITET logjik të variablave A dhe B: A është identik me B.

Shkenca kompjuterike: pajisja e kompjuterit personal Yashin Vladimir Nikolaevich

4.3. Funksionet logjike dhe tabelat e së vërtetës

Marrëdhëniet midis variablave logjikë dhe funksioneve logjike në algjebër logjike mund të shfaqen gjithashtu duke përdorur tabelat përkatëse, të cilat quhen tabela të së vërtetës. Tabelat e së vërtetës përdoren gjerësisht, sepse ato tregojnë qartë se çfarë vlerash merr një funksion logjik për të gjitha kombinimet e vlerave të variablave të tij logjikë. Tabela e së vërtetës përbëhet nga dy pjesë. Pjesa e parë (majtas) i referohet variablave boolean dhe përmban një listë të plotë të kombinimeve të mundshme të variablave boolean. A, B, C ... etj. Pjesa e dytë (djathtas) e kësaj tabele përcakton gjendjet e daljes si funksion logjik të kombinimeve të sasive hyrëse.

Për shembull, për një funksion logjik F = A v B v C(ndarje) e tre variablave boolean A, B, dhe ME tabela e së vërtetës do të ketë formën e treguar në fig. 4.1. Për të regjistruar vlerat e variablave logjikë dhe një funksioni logjik, kjo tabelë e së vërtetës përmban 8 rreshta dhe 4 kolona, ​​domethënë, numri i rreshtave për regjistrimin e vlerave të argumenteve dhe funksioneve të çdo tabele të së vërtetës do të jetë i barabartë me 2 n, ku P - numri i argumenteve për funksionin boolean dhe numri i kolonave është n + 1.

Oriz. 4.1. Tabela e së vërtetës për një funksion logjik F = A v V v C

Një tabelë e vërtetësisë mund të përpilohet për çdo funksion logjik, për shembull, në Fig. 4.2 është një tabelë e së vërtetës së funksionit logjik F = A? B? C(ekuivalentët).

Funksionet logjike emërtohen në përputhje me rrethanat. Ekzistojnë gjashtëmbëdhjetë funksione logjike për dy ndryshore binare, emrat e të cilave janë dhënë më poshtë. Në fig. 4.3 është një tabelë që tregon funksionet logjike F 1, F 2, F 3, … , F 16 dy variabla boolean A dhe V.

Funksioni F 1 = 0 dhe quhet një funksion konstant zero, ose një gjenerator zero.

Oriz. 4.2. Tabela e së vërtetës për një funksion logjik F = A? B? C

Oriz. 4.3. Funksionet logjike F 1, F 2, F 3, ... F 16 të dy argumenteve A dhe V

Funksioni F 2 = A & B quhet funksioni lidhor.

A.

Funksioni F 4 = A A.

quhet funksioni i frenimit të një ndryshoreje logjike V.

Funksioni F 6 = B quhet funksioni i përsëritjes në një variabël boolean V.

quhet funksioni ekskluziv "OR".

Funksioni F 8 = A v B quhet funksioni i disjuksionit.

quhet funksioni Pierce.

quhet funksion ekuivalent.

V.

Funksioni F 12 = B? A B? A.

quhet funksioni i mohimit (inversionit) të një ndryshoreje logjike A.

Funksioni F 14 = A? B quhet funksioni i nënkuptimit A? B.

quhet funksioni Scheffer.

Funksioni F 16 = 1 quhet funksioni i gjeneratorit 1.

Ndër funksionet logjike të variablave të listuara më sipër, ka disa funksione logjike që mund të përdoren për të shprehur funksione të tjera logjike. Operacioni i zëvendësimit të një funksioni logjik me një tjetër në algjebrën e logjikës quhet operacioni i mbivendosjes ose metoda e mbivendosjes. Për shembull, funksioni Schaeffer mund të shprehet duke përdorur funksionet e ndarjes logjike dhe të mohimit duke përdorur ligjin e de Morgan:

Funksionet logjike që mund të përdoren për të shprehur funksione të tjera logjike duke përdorur metodën e mbivendosjes quhen funksione logjike bazë. Një grup i tillë funksionesh logjike bazë quhet një grup funksionalisht i plotë i funksioneve logjike. Në praktikë, tre funksione logjike përdoren më gjerësisht si një grup i tillë: lidhja, disjunksioni dhe mohimi. Nëse një funksion logjik përfaqësohet duke përdorur funksionet bazë, atëherë kjo formë e paraqitjes quhet normale. Në shembullin e mëparshëm, funksioni logjik i Schaeffer, i shprehur në funksion të funksioneve bazë, është paraqitur në formë normale.

Duke përdorur një grup funksionesh bazë dhe pajisjet e tyre teknike përkatëse që zbatojnë këto funksione logjike, ju mund të dizajnoni dhe krijoni çdo pajisje ose sistem logjik.

Oriz. 4.4. Magjistari i veçorive - Hapi 1 nga 2 Kutia e Dialogut

Siç shihet nga Fig. 4.4, si pjesë e funksioneve logjike të programit MS Excel përfshin një grup funksionalisht të plotë funksionesh logjike, të përbërë nga funksionet logjike të mëposhtme: AND (lidhëz), OSE (ndarje), NOT (negacion). Kështu, duke përdorur një grup funksionalisht të plotë të funksioneve logjike të programit MS Excel mund të zbatohen funksione të tjera. Funksioni logjik IF (implikimi), i përfshirë gjithashtu në funksionet logjike MS Excel, kryen një kontroll logjik dhe, në varësi të rezultatit të kontrollit, kryen një nga dy veprimet e mundshme. Në këtë program, ai ka formatin e mëposhtëm: = IF (arg1; arg2; arg3), ku arg1 është një kusht logjik; arg2 është vlera e kthyer me kusht që vlera e argumentit arg1 të jetë e vërtetë (TRUE); arg3 është vlera e kthyer me kusht që arg1 të mos vlerësohet (FALSE). Për shembull, nëse në një qelizë arbitrare të fletës së programit MS Excel shkruani shprehjen "= IF (A1 = 5;" pesë ";" jo pesë ")", atëherë kur futni numrin 5 në qelizën A1 dhe shtypni tastin "Enter" në qelizën A1, fjala "pesë" do të automatikisht të shkruhet, kur futni ndonjë numër tjetër në qelizën A1, fjala "jo pesë" do të shkruhet në të. Siç u përmend tashmë, duke përdorur funksionet logjike të programit MS Excel mundet paraqesin funksione të tjera logjike dhe tabelat e tyre përkatëse të së vërtetës.

Ne zbatojmë duke përdorur funksionet logjike IF dhe AND tabelën e modifikuar të së vërtetës së funksionit logjik F = A dhe B(lidhja), e përbërë nga dy rreshta dhe tre kolona, ​​e cila lejon ndryshimin e vlerave (0 ose 1) të ndryshoreve logjike A dhe B vendos automatikisht, për shembull, në qelizën E6 vlerën e funksionit F = A dhe B, që korrespondon me vlerat e këtyre variablave boolean. Për ta bërë këtë, futni shprehjen e mëposhtme në qelizën E6: "= IF (AND (C6; D6); 1; 0)", atëherë kur futni vlerat 0 ose 1 në qelizat C6 dhe D6 në qelizën E6, është logjike funksioni do të ekzekutohet F = A dhe B. Rezultati i këtyre veprimeve është paraqitur në Fig. 4.5.

Oriz. 4.5. Zbatimi i një tabele të vërtetësisë së funksionit logjik të modifikuar F = A dhe B

Ky tekst është një fragment hyrës. Nga libri Shkenca Kompjuterike dhe Teknologjia e Informacionit: Shënime Leksioni autori Tsvetkova AV

1. Komandat logjike Së bashku me mjetet e llogaritjeve aritmetike, sistemi i komandave të mikroprocesorit ka edhe mjete të konvertimit logjik të të dhënave. Logjike nënkupton transformime të tilla të dhënash, të cilat bazohen në rregullat e formalitetit

Nga libri Kompjuteri 100. Fillimi me Windows Vista autor Zozulya Yuri

Funksionet logjike në Excel Kur llogaritni, shpesh duhet të zgjidhni një formulë në varësi të kushteve specifike. Për shembull, gjatë llogaritjes së pagave, mund të aplikohen shtesa të ndryshme në varësi të kohëzgjatjes së shërbimit, kualifikimeve ose kushteve specifike të punës, të cilat llogariten

Nga një libër pune në Excel. Kurs multimedial autori Medinov Oleg

Funksionet logjike Funksionet logjike mund të përdoren në llogaritjet matematikore, inxhinierike ose në analizën krahasuese të të dhënave. Ne do të shikojmë një funksion Boolean duke përdorur funksionin IF si shembull.Me funksionin IF mund të krijoni një shprehje Boolean dhe

Nga libri Computer Science: Personal Computer Hardware autori Yashin Vladimir Nikolaevich

4.1. Variablat logjikë dhe operacionet logjike Informacioni (të dhënat, udhëzimet e makinës, etj.) në një kompjuter përfaqësohet në një sistem numrash binar, i cili përdor dy shifra - 0 dhe 1. Një sinjal elektrik që kalon nëpër qarqet elektronike dhe lidhet

Nga libri PHP Referenca e Autorit

Funksionet Boolean për përcaktimin e llojit të një ndryshoreje is_scalar Kontrollon nëse një variabël është e thjeshtë Sintaksë: bool is_scalar (var i përzier) Rikthen true nëse var është i llojit skalar (numra, vargje, booleans), por jo kompleks (vargje ose objekte). Is_null Kontrollon nëse është

Nga libri HTML 5, CSS 3 dhe Web 2.0. Zhvillimi i faqeve moderne të internetit autori Dronov Vladimir

Operatorët logjikë Operatorët logjikë kryejnë operacione mbi vlerat Boolean. Të gjitha ato janë dhënë në tabelë. 14.5. Dhe në tabelë. 14.6 dhe 14.7 tregojnë rezultatet e këtyre operatorëve. Fusha kryesore e aplikimit të operatorëve boolean janë shprehjet e krahasimit (rreth tyre shih.

Nga libri XSLT autori Holzner Stephen

Funksionet Boolean XPath XPath gjithashtu mbështet grupin e mëposhtëm të funksioneve Boolean: boolean (). Konverton argumentin në një vlerë boolean; i rremë (). Kthen false (false); lang (). Kontrollon nëse gjuha e vendosur në atributin xml: lang është e njëjtë me gjuhën e kaluar në funksion; jo ().

Nga libri Teknologjia XSLT autori Valikov Alexey Nikolaevich

Operacionet Boolean XSLT ka dy operacione boolean, ose dhe dhe. Këto operacione janë binare, domethënë secila prej tyre është e përcaktuar për dy operandë. Nëse operandët nuk janë boolean, ato janë në mënyrë implicite boolean. Semantika e ose dhe dhe është e dukshme - ato janë

Nga libri Gjuha e programimit C për kompjuterin personal autori Bochkov S.O.

Operacionet logjike Operacionet logjike kryejnë funksione logjike AND (&&) dhe OR (||) në operandët e tyre. Operadët e operacioneve logjike mund të jenë të tipit të plotë, lundrues ose tregues. Llojet e operandit të parë dhe të dytë mund të jenë të ndryshëm. Gjithmonë i pari

Nga libri Një hyrje e shkurtër në programimin në Bash autori Rodriguez Harold

Logjike AND dhe OSE Ju keni parë tashmë se çfarë janë strukturat e kontrollit dhe si t'i përdorni ato. Ka dy mënyra të tjera për të kryer të njëjtat detyra. Këto janë logjike DHE - "&&" dhe logjike "OR" - "|| ". Boolean AND përdoret si më poshtë: shprehja_1 && shprehja_2

Nga libri Firebird DATABASE DESIGNER'S GUIDE nga Borri Helen

Operatorët Boolean Firebird ofron tre operatorë boolean që mund të punojnë me kallëzues të tjerë në mënyra të ndryshme * NUK specifikon mohimin e termit të kërkimit për të cilin zbatohet. Ajo ka përparësinë më të lartë * DHE krijon një kallëzues kompleks, i bashkon të dyja

Nga libri C Language - Një udhëzues fillestar nga Prata Stephen

Kuptimi i vërtetë dhe i gabuar Semantikisht, nëse një kallëzues kthen "pasiguri", ai nuk është as i vërtetë as i rremë. Në SQL, kjo zgjidh vetëm deklaratat si të vërteta ose të rreme - një deklaratë që nuk vlerësohet në të vërtetë trajtohet si

Nga libri Rimëkëmbja e të dhënave 100% autori Tashkov Petr Andreevich

IV. Operacionet logjike Operacionet logjike përgjithësisht konsiderohen si operandë. Operacioni! ka një operand në të djathtë. Pjesa tjetër e operacioneve kanë dy operandë: një në të majtë dhe një në të djathtë. && Boolean DHE: rezultati i operacionit është i vërtetë,

Nga libri C ++ për fillestarët autor Lippman Stanley

Shkeljet logjike Nëse disku është fizikisht i shëndoshë, por duket se është bosh ose i paformatuar dhe të dhënat në të nuk janë të dukshme për sistemin operativ, atëherë në këtë rast tabelat e shërbimit të sistemit të skedarëve dëmtohen. Të dhënat mbeten pothuajse gjithmonë aktive.

Nga libri Përshkrimi i gjuhës PascalABC.NET autori Ekipi i RuBoard

12.3.4. Objektet e funksionit logjik Objektet e funksionit logjik mbështesin operacionet "DHE logjike" (kthehet e vërtetë nëse të dy operandët janë të vërtetë, - përdor operatorin && të lidhur me llojin e tipit), "OR logjik" (kthehet e vërtetë nëse të paktën njëri prej operandëve është i vërtetë, -

Nga libri i autorit

Operacionet Boolean Operacionet Boolean përfshijnë operacionet binare dhe, ose, dhe xor, si dhe operacionin unar not, të cilët kanë operandë boolean dhe kthejnë një vlerë boolean. Këto operacione u binden rregullave standarde të logjikës: a dhe b janë të vërteta vetëm kur a dhe b janë të vërteta, a ose b janë të vërteta.

Zgjidhni linjat ku
dhe ne i shkruajmë lidhëzat e të gjitha ndryshoreve, për më tepër, nëse ndryshorja në këtë grup është e barabartë me 1, atëherë e shkruajmë atë, dhe nëse ndryshorja = 0, atëherë mohimi i saj.

Për këtë shembull

lidhja e këtyre ndarjeve do të jetë formula e dëshiruar:

Përkufizimi: Lidhëza thirrur elementare nëse të gjithë variablat e përfshirë në të janë të ndryshëm. Numri i shkronjave të përfshira në një lidhëz elementare ose në ndarje elementare quhet gradë.

Numri 1 konsiderohet një lidhje elementare e rangut 0. Një ndryshore konsiderohet një lidhje elementare ose një ndarje elementare e rangut 1. Numri 0 konsiderohet një ndarje elementare e renditjes 0. Çdo lidhje e ndryshoreve që nuk është identike e gabuar mund të jetë reduktuar në një formë elementare, dhe çdo ndarje e shkronjave që nuk është identike e vërtetë, gjithashtu mund të reduktohet në një formë elementare. Për këtë është e nevojshme të zbatohen vetitë e komutativitetit, idempotencës dhe asociativitetit të lidhjes dhe disjunksionit.

Është vërtetuar rigorozisht se çdo formulë e algjebrës së Bulit mund të shprehet duke përdorur veprimet , &, . Intuitivisht, ky fakt është i qartë, le të kujtojmë algoritmin për hartimin e një formule sipas tabelës së së vërtetës. Megjithatë, ne përdorim vetëm këto operacione. Kjo formë shënimi quhet trajtë normale disjunctive(DNF). Ky është një lloj mekanizmi për normalizimin e formulave të algjebrës logjike.

Përkufizimi: DNFËshtë një ndarje e lidhëzave të ndryshme elementare (d.m.th., çdo lidhëz përbëhet nga pohime elementare ose mohimet e tyre).

CNF përcaktohet në mënyrë të ngjashme - forma normale konjuktive.

Përkufizimi: Nëse në një DNF të gjitha lidhëzat elementare kanë të njëjtën rang të barabartë me numrin e variablave nga të cilët varet DNF, atëherë quhet perfekte (SDNF).

Teorema. Për çdo funksion që nuk është identikisht fals, ekziston gjithashtu një SDNF unike.

Pasoja ... Çdo funksion Boolean që nuk është identikisht i gabuar mund të përfaqësohet si një mbivendosje &, , , dhe mohimi zbatohet vetëm për ndryshoret.

Përkufizimi: Një sistem veprimesh logjike quhet funksionalisht i plotë nëse, duke përdorur këto operacione dhe konstantat e këtij sistemi, mund të përfaqësohet çdo funksion i algjebrës së Bulit.

Sistemet (&, , ); (, ); (&, ), (/) - janë funksionalisht të plota

(&, ) - funksionalisht i paplotë.

Ne do t'i pranojmë këto fakte pa prova dhe gjatë zgjidhjes së problemeve, do të përpiqemi të paraqesim çdo formulë duke përdorur (&, , ). Më vonë do të diskutojmë në mënyrë më të detajuar çështjen e plotësisë funksionale dhe paplotësisë së sistemit të operacioneve.

Tema 1.7. Metodat e thjeshtimit për shprehjet logjike. Metodat për zgjidhjen e problemeve logjike.

Le të shqyrtojmë një shembull të zgjidhjes së një problemi logjik.

Shembull :

Pasi u diskutua për përbërjen e pjesëmarrësve të ekspeditës, u vendos që duhet të plotësohen dy kushte.

Nëse Arbuzov shkon, atëherë Bryukvin ose Vishnevsky duhet të shkojnë

Nëse Arbuzov dhe Vishnevsky shkojnë, atëherë Bryukvin do të shkojë

Hartoni një formulë logjike për marrjen e një vendimi në një formë simbolike, thjeshtoni formulën që rezulton dhe formuloni një kusht të ri për formimin e një ekspedite duke e përdorur atë.

Le të prezantojmë variablat dhe deklaratat e tyre elementare përkatëse.

- Arbuzov do të shkojë

- Bryukvin do të shkojë

- Vishnevsky do të shkojë

Atëherë kushtet e zhvilluara për formimin e ekspeditës do të duken si më poshtë:

Le të hartojmë një formulë të përgjithshme dhe të thjeshtojmë shprehjen

ato. nëse Arbuzov shkon, Bryukvin do të shkojë.

Shembull:

Nëse moti është i mirë nesër, do të shkojmë në plazh ose do të shkojmë në pyll. Le të hartojmë një formulë për sjelljen tonë për nesër.

- Moti i mirë

- do të shkojmë në plazh

- do të shkojmë në pyll

Tani le të ndërtojmë një mohim të kësaj fraze.

pastaj. na del thënia “Nesër moti do të jetë i mirë dhe ne nuk do të shkojmë në pyll dhe plazh.

Të interesuarit mund të ndërtojnë një tabelë të së vërtetës dhe të kontrollojnë këtë deklaratë.

Shembull :

Brown, John dhe Smith janë arrestuar nën dyshimin për një krim. Njëri prej tyre është një plak i respektuar në qytet, i dyti është zyrtar dhe i treti është një mashtrues i njohur. Gjatë hetimeve, i moshuari ka thënë të vërtetën, mashtruesi ka gënjyer dhe i arrestuari i tretë në një rast ka thënë të vërtetën dhe në tjetrin ka gënjyer.

Ja çfarë thanë ata:

Brown: E bëra. Nuk është faji i Gjonit. (B dhe D)

John: Nuk është faji i Brown. Smith i jashtëligjshëm. (B&C)

Smith: Nuk është faji im. Faji Brown (C & B)

Le t'i përshkruajmë këto deklarata zyrtarisht:

- krimi u krye nga Brown

- krimi u krye nga Gjoni

- krimi u krye nga Smith

Pastaj fjalët e tyre përshkruhen me shprehjet e mëposhtme:

Kafe:

Gjoni:

Smith:

Sepse sipas kushteve të problemit, dy nga këto dhe janë të rreme dhe një është e vërtetë, atëherë

Le të hartojmë një tabelë të së vërtetës

Ka mbetur vetëm rasti 2, d.m.th. krimineli Smith, dhe të dyja deklaratat e tij janë të rreme.

prandaj - e rreme dhe - e vertete

= 1 - Gjon plak i dashur

Mbetet që Brown është zyrtar, dhe që nga ajo kohë - e rreme, pra - e vertete.

Duke përdorur ligjet dhe identitetet e algjebrës së Bulit, ju mund të thjeshtoni shprehjet logjike.

Shembull :

Ushtrimi:

Qëllimi i shërbimit... Llogaritësi në internet është krijuar për ndërtimi i një tabele të së vërtetës për një shprehje boolean.
Tabela e së vërtetës - një tabelë që përmban të gjitha kombinimet e mundshme të variablave hyrëse dhe vlerat e tyre përkatëse të daljes.
Tabela e së vërtetës përmban 2 n rreshta, ku n është numri i variablave hyrëse dhe n + m janë kolona, ​​ku m janë variabla dalëse.

Udhëzim. Kur futni nga tastiera, përdorni shënimin e mëposhtëm: Për shembull, shprehja logjike abc + ab ~ c + a ~ bc duhet të futet kështu: a * b * c + a * b = c + a = b * c
Përdoreni këtë shërbim për të futur të dhëna në formën e një diagrami logjik.

Rregullat e hyrjes së funksionit logjik

1. Përdorni + në vend të v (ndarje, OSE).
2. Ju nuk keni nevojë të paraprini një funksion logjik me një përcaktues funksioni. Për shembull, në vend të F (x, y) = (x | y) = (x ^ y), thjesht duhet të futni (x | y) = (x ^ y).
3. Numri maksimal i variablave është 10.

Dizajni dhe analiza e qarqeve logjike kompjuterike kryhet duke përdorur një seksion të veçantë të matematikës - algjebrën e logjikës. Në algjebrën e logjikës, mund të dallohen tre funksione kryesore logjike: "JO" (negacion), "DHE" (lidhëz), "OR" (ndarje).
Për të krijuar ndonjë pajisje logjike, është e nevojshme të përcaktohet varësia e secilës prej variablave të daljes nga variablat e hyrjes operative, një varësi e tillë quhet një funksion komutues ose një funksion i algjebrës logjike.
Një funksion algjebër logjik quhet plotësisht i përcaktuar nëse jepen të gjitha 2 n vlerat e tij, ku n është numri i ndryshoreve dalëse.
Nëse jo të gjitha vlerat janë të përcaktuara, funksioni quhet pjesërisht i përcaktuar.
Një pajisje quhet logjike nëse gjendja e saj përshkruhet duke përdorur një funksion algjebër logjik.
Metodat e mëposhtme përdoren për të paraqitur një funksion të algjebrës së logjikës:

• përshkrimi verbal është një formë që përdoret në fazën fillestare të projektimit dhe ka një paraqitje të kushtëzuar.
• përshkrimi i funksionit të algjebrës së logjikës në formën e një tabele të së vërtetës.
• përshkrimi i funksionit të algjebrës së logjikës në formën e një shprehjeje algjebrike: përdoren dy forma algjebrike të FAL:
  a) DNF - forma normale disjunctiveËshtë një shumë logjike e produkteve elementare logjike. DNF merret nga tabela e së vërtetës sipas algoritmit ose rregullit të mëposhtëm:
  1) ato rreshta të variablave për të cilat funksioni i daljes = 1 janë zgjedhur në tabelë.
  2) një produkt logjik është shkruar për çdo rresht të variablave; ku ndryshoret = 0 shkruhen me inversion.
  3) produkti që rezulton përmblidhet logjikisht.
  Fднф = X 1 * X 2 * X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
  Një DNF quhet i përsosur nëse të gjitha variablat kanë të njëjtën rang ose renditje, d.m.th. çdo punë duhet të përfshijë të gjitha variablat në formë të drejtpërdrejtë ose të kundërt.
  b) CNF - forma normale lidhoreËshtë produkt logjik i shumave elementare logjike.
  CNF mund të merret nga tabela e së vërtetës duke përdorur algoritmin e mëposhtëm:
  1) zgjidhni grupe variablash për të cilat funksioni i daljes = 0
  2) për çdo grup variablash shkruajmë një shumë logjike elementare, dhe ndryshoret = 1 shkruhen me përmbysje.
  3) shumat e marra shumohen logjikisht.
  Fscnf = (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  CNF quhet perfekt nëse të gjitha variablat kanë të njëjtën rang.

Në formë algjebrike, mund të ndërtoni një qark të pajisjes logjike duke përdorur portat logjike.

Figura 1 - Diagrami i pajisjes logjike

Të gjitha operacionet Boolean janë të përcaktuara tabelat e së vërtetës vlerat. Tabela e së vërtetës përcakton rezultatin e operacionit për të gjitha janë të mundshme x vlerat logjike të deklaratave origjinale. Numri i opsioneve që pasqyrojnë rezultatin e zbatimit të operacioneve do të varet nga numri i deklaratave në një shprehje logjike. Nëse numri i pohimeve në një shprehje logjike është N, atëherë tabela e së vërtetës do të përmbajë 2 N rreshta, pasi ka 2 N kombinime të ndryshme të vlerave të mundshme të argumenteve.

Operacioni NOT - mohim logjik (inversion)

Një operacion logjik NUK zbatohet për një argument të vetëm, i cili mund të jetë një shprehje logjike e thjeshtë ose komplekse. Rezultati i operacionit NUK është si më poshtë:

• nëse shprehja origjinale është e vërtetë, atëherë rezultati i mohimit të saj do të jetë i rremë;
• nëse shprehja origjinale është e rreme, atëherë rezultati i mohimit të saj do të jetë i vërtetë.

Konventat e mëposhtme NUK pranohen për operacionin e mohimit:
jo А, Ā, jo A, ¬А,! A
Rezultati i një operacioni mohimi NUK përcaktohet nga tabela e mëposhtme e së vërtetës:

A	jo A
0	1
1	0

Rezultati i operacionit të mohimit është i vërtetë kur deklarata origjinale është e rreme, dhe anasjelltas.

Operacioni OSE - shtim logjik (ndarje, bashkim)

Operacioni logjik OSE kryen funksionin e kombinimit të dy deklaratave, të cilat mund të jenë ose një shprehje logjike e thjeshtë ose komplekse. Deklaratat që janë burimi për një operacion logjik quhen argumente. Rezultati i operacionit OR është një shprehje që do të jetë e vërtetë nëse dhe vetëm nëse të paktën një nga shprehjet origjinale do të jetë e vërtetë.
Emërtimet e aplikuara: A ose B, A V B, A ose B, A || B.
Rezultati i operacionit OR përcaktohet nga tabela e mëposhtme e së vërtetës:
Rezultati i operacionit OR është i vërtetë kur A është e vërtetë, ose B është e vërtetë, ose të dyja A dhe B janë të vërteta në të njëjtën kohë, dhe false kur argumentet A dhe B janë false.

AND operacion - shumëzim logjik (lidhëz)

Operacioni logjik DHE kryen funksionin e kryqëzimit të dy pohimeve (argumenteve), të cilat mund të jenë një shprehje logjike e thjeshtë dhe komplekse. Rezultati i operacionit AND është një shprehje që do të jetë e vërtetë nëse dhe vetëm nëse të dyja shprehjet origjinale janë të vërteta.
Emërtimet e aplikuara: A dhe B, A Λ B, A & B, A dhe B.
Rezultati i operacionit AND përcaktohet nga tabela e mëposhtme e së vërtetës:

A	B	A dhe B
0	0	0
0	1	0
1	0	0
1	1	1

Rezultati i veprimit AND është i vërtetë nëse dhe vetëm nëse pohimet A dhe B janë të vërteta në të njëjtën kohë, dhe false në të gjitha rastet e tjera.

Operacioni "IF-THEN" - vijim logjik (nënkuptim)

Ky veprim lidh dy shprehje të thjeshta logjike, nga të cilat e para është kusht dhe e dyta është pasojë e kësaj gjendjeje.
Emërtimet e aplikuara:
nëse A, atëherë B; A përfshin B; nëse A atëherë B; A → B.
Tabela e së vërtetës:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Rezultati i operacionit të mëposhtëm (nënkuptimi) është i rremë vetëm kur premisa A është e vërtetë, dhe përfundimi B (pasoja) është i gabuar.

Operacioni "A nëse dhe vetëm nëse B" (ekuivalenca, ekuivalenca)

Emërtimi i aplikuar: A ↔ B, A ~ B.
Tabela e së vërtetës:

A	B	А↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operacioni "Shto mod 2" (XOR, ekskluzive ose, ndarje e rreptë)

Emërtimi i aplikuar: A XOR B, A ⊕ B.
Tabela e së vërtetës:

A	B	А⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Rezultati i ekuivalencës së operacionit është i vërtetë vetëm nëse A dhe B janë të dyja të vërteta ose të rreme në të njëjtën kohë.

Prioriteti Boolean

• Veprimet në kllapa
• Përmbysja
• Lidhëza (&)
• Disjunction (V), Ekskluzive OSE (XOR), shuma mod 2
• Implikimi (→)
• Ekuivalenca (↔)

Forma normale e përsosur ndarëse

Forma normale e përsosur ndarëse e një formule(SDNF) është një formulë ekuivalente me të, e cila është një ndarje e lidhjeve elementare me vetitë e mëposhtme:

1. Çdo term logjik i formulës përmban të gjitha variablat e përfshira në funksionin F (x 1, x 2, ... x n).
2. Të gjitha termat logjike të formulës janë të ndryshme.
3. Asnjë term i vetëm logjik nuk përmban një ndryshore dhe mohimin e saj.
4. Asnjë term logjik në një formulë nuk përmban të njëjtën variabël dy herë.

SDNF mund të merret ose duke përdorur tabela të së vërtetës ose duke përdorur transformime ekuivalente.
Për secilin funksion, SDNF dhe SKNF përcaktohen në mënyrë unike deri në ndryshim.

Forma normale e përsosur lidhore

Formula e përsosur e formës normale lidhore (SKNF)është një formulë ekuivalente me të, e cila është një lidhje e ndarjeve elementare, që plotëson vetitë:

1. Të gjitha fjalitë elementare përmbajnë të gjitha ndryshoret e përfshira në funksionin F (x 1, x 2, ... x n).
2. Të gjitha ndarjet elementare janë të ndryshme.
3. Çdo ndarje elementare përmban një ndryshore një herë.
4. Asnjë ndarje elementare nuk përmban një ndryshore dhe mohimin e saj.