Funcția logică este o funcție în care variabilele iau doar două valori: una logică sau zero logic. Adevărul sau falsitatea judecăților complexe este o funcție a adevărului sau falsitatea celor simple. Această funcție se numește funcție de judecată booleană f (a, b).

Orice funcție logică poate fi specificată folosind un tabel de adevăr, pe partea stângă a căruia este scris un set de argumente, iar în partea dreaptă - valorile corespunzătoare ale funcției logice.

La construirea unui tabel de adevăr, este necesar să se țină cont de ordinea în care sunt efectuate operațiile logice. Operațiile într-o expresie booleană sunt efectuate de la stânga la dreapta, sub rezerva parantezelor, în următoarea ordine:

• 1. inversiune;
• 2. conjuncție;
• 3. disjuncție;
• 4. implicare și echivalență.

Parantezele sunt folosite pentru a schimba ordinea în care sunt efectuate operațiile logice.

Se propune urmatorul algoritm de construcție a tabelului de adevăr.

• 1. Determină numărul de seturi de variabile de intrare- toate combinațiile posibile de valori ale variabilelor incluse în expresii, conform formulei: Q = 2 n, unde n este numărul de variabile de intrare. Acesta determină numărul de rânduri din tabel.
• 2. Introduceți toate seturile de variabile de intrare în tabel.
• 3. Determinați numărul de operații logice și succesiunea executării acestora.
• 4. Completați coloanele cu rezultatele efectuării operațiilor logice în secvența indicată.

Pentru a nu repeta sau pierde nicio combinație posibilă a valorilor variabilelor de intrare, ar trebui să utilizați una dintre următoarele metode pentru completarea tabelului.

Metoda 1. Fiecare set de valori ale variabilelor inițiale este un cod al unui număr în sistemul de numere binar, iar numărul de cifre ale numărului este egal cu numărul de variabile de intrare. Primul set este numărul 0. Adăugând 1 la numărul curent de fiecare dată, obținem următorul set. Ultimul set este valoarea binară maximă pentru lungimea codului dată.

De exemplu, pentru o funcție de trei variabile, succesiunea de mulțimi constă din numere:

Metoda 2. Pentru o funcție de trei variabile, secvența de date poate fi obținută în felul următor:

• a) împărțiți coloana de valori a primei variabile în jumătate și completați jumătatea superioară cu zerouri, jumătatea inferioară cu unu;
• b) în coloana următoare pentru a doua variabilă, împărțiți din nou jumătatea în jumătate și completați grupuri de zerouri și unu; completați a doua jumătate în același mod;
• c) faceți acest lucru până când grupurile de zerouri și unu sunt formate dintr-un singur caracter.

Metoda 3. Utilizați un tabel de adevăr cunoscut pentru două argumente. Adăugând al treilea argument, mai întâi scrieți primele 4 rânduri ale tabelului, combinându-le cu valoarea celui de-al treilea argument egală cu 0, apoi scrieți din nou aceleași 4 rânduri, dar acum cu valoarea celui de-al treilea argument egală cu 1. Ca rezultat, tabelul pentru trei argumente va fi de 8 linii:

De exemplu, să construim un tabel de adevăr pentru o funcție logică:

Numărul de variabile de intrare în expresia dată este trei (A, B, C)... Prin urmare, numărul de seturi de intrare Q = 2 3 =8 .

Coloanele din tabelul de adevăr corespund valorilor expresiilor originale A, B, C, rezultate intermediare și ( B V C), precum și valoarea finală dorită a unei expresii aritmetice complexe:

• 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. Funcțiile logice și transformările lor. Legile logicii

Pentru operațiile de conjuncție, disjuncție și inversare sunt definite legile algebrei booleene care fac posibilă producerea transformări identice (echivalente) ale expresiilor logice.

Legile logicii

• 1. ¬¬ A
• 2. A&B
• 3. AVB
• 4. A & (B&C)
• 5. AV (BVC)
• 6.A și (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

Pe baza legilor, puteți simplifica expresii booleene complexe. Acest proces de înlocuire a unei funcții logice complexe cu o funcție mai simplă, dar echivalentă cu aceasta, se numește minimizarea funcției.

Exemplul 1. Simplificați expresiile astfel încât formulele rezultate să nu conțină negația expresiilor complexe.

Soluţie

Exemplul 2. Minimizați funcția

Pentru simplificarea expresiei s-au folosit formulele de absorbtie si aderenta.

Exemplul 3. Găsiți negația următoarei afirmații: „Dacă lecția este interesantă, atunci niciunul dintre elevi (Misha, Vika, Sveta) nu se va uita pe fereastră”.

Soluţie

Să desemnăm declarații:

Y- „Lecția este interesantă”;

M- „Misha se uită pe fereastră”;

B- „Vika se uită pe fereastră”;

C- „Sveta se uită pe fereastră”.

La simplificarea expresiei s-au folosit formula de substituire a operațiilor și legea lui de Morgan.

Exemplul 4. Determinați participantul la infracțiune pe baza a două premise: tabelul logic al computerului

• 1) „Dacă Ivanov nu a participat sau Petrov a participat, atunci a participat Sidorov”;
• 2) „Dacă Ivanov nu a participat, atunci Sidorov nu a participat”.

Soluţie

Să compunem expresii:

eu- „Ivanov a participat la crimă”;

P- „Petrov a participat la crimă”;

S- „Sidorov a luat parte la crimă”.

Să scriem parcelele sub formă de formule:

Să verificăm rezultatul folosind tabelul de adevăr:

Răspuns: Ivanov a luat parte la crimă.

Construirea unei funcții logice din tabelul său de adevăr

Am învățat cum să facem o tabelă de adevăr pentru o funcție logică. Să încercăm să rezolvăm problema inversă.

Luați în considerare rândurile în care valoarea de adevăr a funcției Z este adevărată (Z = 1). Funcția pentru acest tabel de adevăr poate fi compusă după cum urmează: Z (X, Y) = (¬ X & ¬Y) V (X & ¬Y).

Fiecare linie în care funcția este adevărată (egal cu 1) corespunde unei paranteze, care este o conjuncție de argumente, iar dacă valoarea argumentului este O, atunci o luăm cu negație. Toate suporturile sunt conectate printr-o operație de disjuncție. Formula rezultată poate fi simplificată prin aplicarea legilor logicii:

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

Verificați formula rezultată: faceți un tabel de adevăr pentru funcția Z (X, Y).

Scrieți regulile pentru construirea unei funcții logice conform tabelului de adevăr:

• 1. Selectați în tabelul de adevăr acele rânduri în care valoarea funcției este egală cu 1.
• 2. Scrieți formula necesară sub forma unei disjuncții a mai multor elemente logice. Numărul acestor elemente este egal cu numărul de linii selectate.
• 3. Fiecare element logic din această disjuncție este scris ca o conjuncție a argumentelor funcției.
• 4. Dacă valoarea oricărui argument al funcției din rândul corespunzător al tabelului este 0, atunci luăm acest argument cu negație.

1. Stabiliți ordinea acțiunilor.

2. Determinați dimensiunea tabelului de adevăr.

Numărul de coloane este determinat de numărul de variabile logice (sunt două A, B) și numărul de acțiuni (sunt și două).

4. Formulează un răspuns.
Ultima coloană are un „0” corespunzător lui A egal cu „1” și B egal cu „0”. Rezultă că această funcție este falsă dacă și numai dacă variabila logică A este adevărată, iar variabila logică B este falsă, ceea ce corespunde funcției logice CONSECUȚIA.
Prin urmare, această funcție este egală cu consecința logică a variabilelor A și B: dacă A, atunci B.

Creați un tabel de adevăr pentru o funcție logică:

1. Stabiliți ordinea acțiunilor.

2. Determinați dimensiunea tabelului de adevăr.

„Antetul” tabelului conține două linii - numărul de acțiuni și operațiile logice ale acțiunilor.
Numărul de coloane este determinat de numărul de variabile logice (sunt două A, B) și de numărul de acțiuni (sunt cinci).
Numărul de rânduri din tabel este egal cu două la puterea egală cu numărul de variabile logice - în cazul a două variabile se obțin 4 rânduri.
3. Completați rând pe rând coloanele tabelului în conformitate cu funcția logică a acestei coloane.


4. Formulează un răspuns.
În ultima coloană „1” corespunde lui A egal cu B, iar „0” - A inegal B. Rezultă că această funcție este adevărată când A este egal cu B și falsă când A nu este egal cu B, ceea ce corespunde la funcția logică IDENTITATE.
Prin urmare, această funcție este egală cu IDENTITATEA logică a variabilelor A și B: A este identică cu B.

Informatică: hardware de calculator personal Yashin Vladimir Nikolaevich

4.3. Funcții logice și tabele de adevăr

Relațiile dintre variabilele logice și funcțiile logice din algebra logică pot fi afișate și folosind tabelele corespunzătoare, care sunt numite tabele de adevăr. Tabelele de adevăr sunt utilizate pe scară largă deoarece arată clar ce valori ia o funcție logică pentru toate combinațiile de valori ale variabilelor sale logice. Tabelul de adevăr este format din două părți. Prima parte (stânga) se referă la variabile booleene și conține o listă completă de combinații posibile de variabile booleene. A, B, C... etc. A doua parte (dreapta) a acestui tabel definește stările de ieșire ca o funcție logică a combinațiilor de mărimi de intrare.

De exemplu, pentru o funcție logică F = A v B contra C(disjuncția) a trei variabile booleene A, B,și CU tabelul de adevăr va avea forma prezentată în fig. 4.1. Pentru a înregistra valorile variabilelor logice și o funcție logică, acest tabel de adevăr conține 8 rânduri și 4 coloane, adică numărul de rânduri pentru înregistrarea valorilor argumentelor și funcțiilor oricărui tabel de adevăr va fi egal cu 2 n, Unde NS - numărul de argumente pentru funcția booleană și numărul de coloane este n + 1.

Orez. 4.1. Tabel de adevăr pentru o funcție logică F = A v V v C

Un tabel de adevăr poate fi compilat pentru orice funcție logică, de exemplu, în Fig. 4.2 este un tabel al adevărului funcției logice F = A? B? C(echivalente).

Funcțiile logice sunt denumite corespunzător. Există șaisprezece funcții logice pentru două variabile binare, ale căror nume sunt date mai jos. În fig. 4.3 este un tabel care prezintă funcțiile logice F 1, F 2, F 3, … , F 16 două variabile booleene Ași V.

Funcţie F 1 = 0și se numește funcție zero constantă sau generator zero.

Orez. 4.2. Tabel de adevăr pentru o funcție logică F = A? B? C

Orez. 4.3. Funcții logice F 1, F 2, F 3, ... F 16 din două argumente Ași V

Funcţie F 2 = A și B se numește funcția de conjuncție.

A.

Funcţie F4 = A A.

se numește funcția de inhibare a unei variabile logice V.

Funcţie F6 = B numită funcție de repetiție pe o variabilă booleană V.

numită funcție exclusivă „SAU”.

Funcţie F 8 = A v B numită funcţie de disjuncţie.

numită funcția Pierce.

se numește funcție de echivalență.

V.

Funcţie F 12 = B? A B? A.

se numește funcția de negație (inversie) a unei variabile logice A.

Funcţie F 14 = A? B numită funcţie de implicare A? B.

numită funcția Scheffer.

Funcţie F 16 = 1 se numește funcția generatorului 1.

Printre funcțiile logice ale variabilelor enumerate mai sus, există mai multe funcții logice care pot fi folosite pentru a exprima alte funcții logice. Operația de înlocuire a unei funcții logice cu alta în algebra logicii se numește operația de suprapunere sau metoda de suprapunere. De exemplu, funcția Schaeffer poate fi exprimată folosind funcțiile de disjuncție logică și de negație folosind legea lui de Morgan:

Funcțiile logice care pot fi folosite pentru a exprima alte funcții logice folosind metoda suprapunerii sunt numite funcții logice de bază. Un astfel de set de funcții logice de bază se numește un set complet funcțional de funcții logice. În practică, trei funcții logice sunt cele mai utilizate ca atare mulțime: conjuncție, disjuncție și negație. Dacă o funcție logică este reprezentată folosind funcții de bază, atunci această formă de prezentare se numește normală. În exemplul anterior, funcția logică Schaeffer, exprimată în termeni de funcții de bază, este reprezentată în formă normală.

Folosind un set de funcții de bază și dispozitivele tehnice corespunzătoare care implementează aceste funcții logice, puteți proiecta și crea orice dispozitiv sau sistem logic.

Orez. 4.4. Feature Wizard - Pasul 1 din 2 Caseta de dialog

După cum se vede din fig. 4.4, ca parte a funcțiilor logice ale programului MS Excel include un set complet funcțional de funcții logice, constând din următoarele funcții logice: AND (conjuncție), SAU (disjuncție), NOT (negație). Astfel, folosind un set complet funcțional de funcții logice ale programului MS Excel alte funcții pot fi implementate. Funcția logică IF (implicație), inclusă și în funcțiile logice MS Excel, efectuează o verificare logică și, în funcție de rezultatul verificării, efectuează una dintre cele două acțiuni posibile. În acest program, are următorul format: = IF (arg1; arg2; arg3), unde arg1 este o condiție logică; arg2 este valoarea returnată cu condiția ca valoarea argumentului arg1 să fie adevărată (TRUE); arg3 este valoarea returnată cu condiția ca arg1 să nu fie evaluat (FALSE). De exemplu, dacă într-o celulă arbitrară a foii de program MS Excel introduceți expresia "= IF (A1 = 5;" cinci ";" nu cinci ")", apoi când introduceți numărul 5 în celula A1 și apăsați tasta "Enter" în celula A1, cuvântul "cinci" va fi automat fie scris, când introduceți orice alte numere în celula A1, cuvântul „nu cinci” va fi scris în ea. După cum sa menționat deja, folosind funcțiile logice ale programului MS Excel poate reprezintă alte funcții logice și tabelele de adevăr corespunzătoare.

Implementăm folosind funcțiile logice IF și AND tabelul de adevăr modificat al funcției logice F = A și B(conjuncție), format din două rânduri și trei coloane, care permite modificarea valorilor (0 sau 1) ale variabilelor logice A și B setați automat, de exemplu, în celula E6 valoarea funcției F = A și B, corespunzătoare valorilor acestor variabile booleene. Pentru a face acest lucru, introduceți următoarea expresie în celula E6: „= IF (ȘI (C6; D6); 1; 0)”, apoi atunci când introduceți în celulele C6 și D6 valori 0 sau 1 în celula E6, funcția logică va fi executat F = A și B. Rezultatul acestor acțiuni este prezentat în Fig. 4.5.

Orez. 4.5. Implementarea unui tabel de adevăr al funcției logice modificate F = A și B

Acest text este un fragment introductiv. Din cartea Computer Science and Information Technology: Lecture Notes autorul Tsvetkova AV

1. Comenzi logice Alături de mijloacele de calcul aritmetic, sistemul de comenzi al microprocesorului dispune și de mijloace de conversie logică a datelor. Logic înseamnă astfel de transformări de date, care se bazează pe regulile formale

Din cartea Computer 100. Noțiuni introductive cu Windows Vista autor Zozulya Yuri

Funcții logice în Excel Când calculați, de multe ori trebuie să alegeți o formulă în funcție de condiții specifice. De exemplu, la calcularea salariilor, pot fi aplicate diferite indemnizații în funcție de vechimea în muncă, calificări sau condiții specifice de muncă, care sunt calculate

Dintr-un registru de lucru Excel. Curs multimedia autorul Medinov Oleg

Funcții logice Funcțiile logice pot fi utilizate în calcule matematice, de inginerie sau în analiza comparativă a datelor. Ne vom uita la o funcție booleană folosind funcția IF ca exemplu. Cu funcția IF puteți crea o expresie booleană și

Din cartea Computer Science: Personal Computer Hardware autorul Iașin Vladimir Nikolaevici

4.1. Variabile logice și operații logice Informațiile (date, instrucțiuni ale mașinii etc.) dintr-un computer sunt reprezentate într-un sistem de numere binar, care utilizează două cifre - 0 și 1. Un semnal electric care trece prin circuite electronice și conectează

Din cartea PHP Author's Reference

Funcții booleene pentru determinarea tipului unei variabile is_scalar Verifică dacă o variabilă este simplă Sintaxă: bool is_scalar (var mixt) Returnează adevărat dacă var este de tip scalar (numere, șiruri, booleani), dar nu complex (matrice sau obiecte). Is_null Verifică dacă este

Din cartea HTML 5, CSS 3 și Web 2.0. Dezvoltarea de site-uri web moderne autorul Dronov Vladimir

Operatori logici Operatorii logici efectuează operații pe valori booleene. Toate sunt date în tabel. 14.5. Și în tabel. 14.6 și 14.7 arată rezultatele acestor operatori Principala zonă de aplicare a operatorilor booleeni este expresiile de comparație (despre ei vezi.

Din cartea XSLT autorul Holzner Stephen

Funcții booleene XPath XPath acceptă, de asemenea, următorul set de funcții booleene: boolean (). Convertește argumentul într-o valoare booleană; fals (). Returnează false (fals); lang (). Verifică dacă limba setată în atributul xml: lang este aceeași cu limba transmisă funcției; nu ().

Din cartea XSLT Technology autorul Valikov Alexey Nikolaevici

Operații booleene XSLT are două operații booleene, sau și și. Aceste operații sunt binare, adică fiecare dintre ele este definită pentru doi operanzi. Dacă operanzii nu sunt booleeni, ei sunt implicit booleeni.Semantica lui sau și și este evidentă - sunt

Din cartea Limbajul de programare C pentru computerul personal autorul Bochkov S.O.

Operații logice Operațiile logice efectuează funcții logice ȘI (&&) și SAU (||) pe operanzii lor. Operanzii operațiilor logice pot fi de tip întreg, flotant sau pointeri. Tipurile primului și celui de-al doilea operanzi pot fi diferite. Întotdeauna primul

Din cartea O scurtă introducere în programare în Bash autorul Rodriguez Harold

ȘI și SAU logic Ați văzut deja ce sunt structurile de control și cum să le utilizați. Mai există două moduri de a îndeplini aceleași sarcini. Acestea sunt ȘI logice - „&&” și „SAU” logice - „|| ". Boolean AND este folosit după cum urmează: expresie_1 && expresie_2

Din cartea Firebird DATABASE DESIGNER'S GHIDE de Borri Helen

Operatori booleeni Firebird oferă trei operatori booleeni care pot lucra cu alte predicate în moduri diferite.* NOT specifică negarea termenului de căutare căruia i se aplică. Are cea mai mare prioritate.* ȘI creează un predicat complex, concatenează cele două

Din cartea C Language - A Beginner's Guide de Prata Stefan

Înțelegerea adevăratului și a falsului Din punct de vedere semantic, dacă un predicat returnează „incertitudine”, nu este nici adevărat, nici fals. În SQL, aceasta rezolvă numai afirmațiile ca adevărate sau false - o declarație care nu este evaluată la adevărat este tratată ca

Din cartea Data Recovery 100% autorul Tașkov Petr Andreevici

IV. Operații logice Operațiile logice sunt în general considerate operanzi. Operațiune! are un operand la dreapta. Restul operațiilor au doi operanzi: unul în stânga și unul în dreapta. && Boolean AND: rezultatul operației este adevărat,

Din cartea C++ pentru începători autorul Lippman Stanley

Încălcări logice Dacă o unitate este solidă din punct de vedere fizic, dar pare a fi goală sau neformatată, iar datele de pe ea nu sunt vizibile pentru sistemul de operare, atunci în acest caz tabelele de servicii ale sistemului de fișiere sunt deteriorate. Datele rămân aproape întotdeauna pe

Din cartea Descrierea limbajului PascalABC.NET autorul Echipa RuBoard

12.3.4. Obiecte cu funcții logice Obiectele cu funcție logică acceptă operații „ȘI logice” (returnează adevărat dacă ambii operanzi sunt adevărati, - utilizează operatorul && asociat tipului Tip), „SAU logic” (returnează adevărat dacă cel puțin unul dintre operanzi este adevărat, -

Din cartea autorului

Operații booleene Operațiile booleene includ operațiile binare și, sau și xor, precum și operația unară not, care au operanzi booleeni și returnează o valoare booleană. Aceste operații se supun regulilor standard ale logicii: a și b sunt adevărate numai atunci când a și b sunt adevărate, a sau b sunt adevărate

Selectați liniile în care
și scriem conjuncțiile tuturor variabilelor, în plus, dacă variabila din această mulțime este egală cu 1, atunci o notăm, iar dacă variabila = 0, atunci negația ei.

Pentru acest exemplu

conjuncția acestor disjuncții va fi formula dorită:

Definiție: Conjuncție numit elementar dacă toate variabilele incluse în acesta sunt diferite. Se numește numărul de litere incluse într-o conjuncție elementară sau într-o disjuncție elementară rang.

Numărul 1 este considerat o conjuncție elementară de rang 0. O variabilă este considerată o conjuncție elementară sau o disjuncție elementară de rang 1. Numărul 0 este considerat o disjuncție elementară de rang 0. Orice conjuncție de variabile care nu este identic falsă poate fi redusă la o formă elementară și orice disjuncție de litere care nu este identic adevărată, poate fi, de asemenea, redusă la o formă elementară. Pentru aceasta este necesar să se aplice proprietățile comutativității, idempotității și asociativității conjuncției și disjuncției.

S-a dovedit riguros că orice formulă a algebrei booleene poate fi exprimată folosind operațiile , &, . Intuitiv, acest fapt este evident, să ne amintim algoritmul de întocmire a unei formule conform tabelului de adevăr. Cu toate acestea, folosim doar aceste operațiuni. Această formă de notație se numește forma normală disjunctivă(DNF). Acesta este un fel de mecanism pentru normalizarea formulelor de algebră logică.

Definiție: DNF Este o disjuncție a diferitelor conjuncții elementare (adică fiecare conjuncție este formată din enunțuri elementare sau negații ale acestora).

CNF este definit în mod similar - formă normală conjunctivă.

Definiție: Dacă într-un DNF toate conjuncțiile elementare au același rang egal cu numărul de variabile de care depinde DNF, atunci se numește perfect (SDNF).

Teorema. Pentru orice funcție care nu este identic falsă, există și un SDNF unic.

Consecinţă ... Orice funcție booleană care nu este falsă identic poate fi reprezentată ca o suprapunere &, , , iar negația se aplică numai variabilelor.

Definiție: Un sistem de operații logice se numește complet funcțional dacă, folosind aceste operații și constantele acestui sistem, poate fi reprezentată orice funcție a algebrei booleene.

Sisteme (&, , ); (, ); (&, ), (/) - sunt complete din punct de vedere funcțional

(&, ) - incomplet din punct de vedere funcțional.

Vom accepta aceste fapte fără dovezi, iar atunci când rezolvăm probleme, vom încerca să reprezentăm orice formulă folosind (&, , ). Mai târziu vom discuta mai detaliat problema completității funcționale și incompletității sistemului de operațiuni.

Subiectul 1.7. Metode de simplificare a expresiilor logice. Metode de rezolvare a problemelor logice.

Să luăm în considerare un exemplu de rezolvare a unei probleme de logică.

Exemplu :

După discutarea componenței participanților la expediție, s-a decis că trebuie îndeplinite două condiții.

Dacă Arbuzov pleacă, atunci ar trebui să meargă Bryukvin sau Vișnevski

Dacă Arbuzov și Vishnevsky pleacă, atunci Bryukvin va merge

Elaborați o formulă logică pentru luarea unei decizii într-o formă simbolică, simplificați formula rezultată și formulați o nouă condiție pentru formarea unei expediții folosind-o.

Să introducem variabilele și afirmațiile lor elementare corespunzătoare.

- Arbuzov va pleca

- Bryukvin va pleca

- Vișnevski va pleca

Atunci condițiile dezvoltate pentru formarea expediției vor arăta astfel:

Să întocmim o formulă generală și să simplificăm expresia

acestea. dacă se duce Arbuzov, va pleca Bryukvin.

Exemplu:

Dacă mâine va fi vreme bună, vom merge la plajă sau mergem în pădure. Să întocmim o formulă pentru comportamentul nostru de mâine.

- vreme buna

- noi vom merge pe plajă

- vom merge în pădure

Acum să construim o negație a acestei fraze.

atunci. primim zicala „Mâine va fi vreme bună și nu vom merge la pădure și la plajă.

Cei interesați pot construi un tabel de adevăr și pot verifica această afirmație.

Exemplu :

Brown, John și Smith sunt arestați sub suspiciunea unei crime. Unul dintre ei este un bătrân respectat în oraș, al doilea este un oficial, iar al treilea este un escroc binecunoscut. În timpul anchetei, bătrânul a spus adevărul, escrocul a mințit, iar al treilea deținut într-un caz a spus adevărul, iar în celălalt a mințit.

Iată ce au spus:

Brown: Am făcut-o. Nu este vina lui John. (B & D)

John: Nu este vina lui Brown. Haiduc Smith. (B&C)

Smith: Nu e vina mea. Blame Brown (C & B)

Să descriem formal aceste afirmații:

- Crima a fost comisă de Brown

- crima a fost comisă de John

- Crima a fost comisă de Smith

Apoi cuvintele lor sunt descrise prin următoarele expresii:

Maro:

Ioan:

Smith:

pentru că prin condițiile problemei, două dintre acestea & sunt false și unul este adevărat

Să alcătuim un tabel de adevăr

Rămâne doar cazul 2, adică criminalul Smith și ambele declarații ale sale sunt false.

prin urmare - fals și - Adevărat

= 1 - Ioan dragă bătrâne

Rămâne că Brown este un oficial și de atunci - fals, atunci - Adevărat.

Folosind legile și identitățile algebrei booleene, puteți simplifica expresiile logice.

Exemplu :

Exercitiul:

Scopul serviciului... Calculatorul online este conceput pentru construirea unui tabel de adevăr pentru o expresie booleană.
Tabel de adevăr - un tabel care conține toate combinațiile posibile de variabile de intrare și valorile lor de ieșire corespunzătoare.
Tabelul de adevăr conține 2 n rânduri, unde n este numărul de variabile de intrare și n + m sunt coloane, unde m sunt variabile de ieșire.

Instruire. Când introduceți de la tastatură, utilizați următoarea notație: De exemplu, expresia logică abc + ab ~ c + a ~ bc trebuie introdusă astfel: a * b * c + a * b = c + a = b * c
Utilizați acest serviciu pentru a introduce date sub forma unei diagrame logice.

Reguli de intrare a funcției logice

1. Folosiți + în loc de v (disjuncție, SAU).
2. Nu trebuie să precedeți o funcție logică cu un desemnator de funcție. De exemplu, în loc de F (x, y) = (x | y) = (x ^ y), trebuie doar să introduceți (x | y) = (x ^ y).
3. Numărul maxim de variabile este 10.

Proiectarea și analiza circuitelor logice computerizate se realizează folosind o secțiune specială de matematică - algebra logicii. În algebra logicii se pot distinge trei funcții logice principale: „NU” (negație), „ȘI” (conjuncție), „SAU” (disjuncție).
Pentru a crea orice dispozitiv logic, este necesar să se determine dependența fiecăreia dintre variabilele de ieșire de variabilele de intrare de funcționare, o astfel de dependență se numește funcție de comutare sau funcție de algebră logică.
O funcție de algebră logică se numește complet definită dacă sunt date toate cele 2 n dintre valorile sale, unde n este numărul de variabile de ieșire.
Dacă nu sunt definite toate valorile, se spune că funcția este parțial definită.
Un dispozitiv este numit logic dacă starea lui este descrisă folosind o funcție de algebră logică.
Următoarele metode sunt utilizate pentru a reprezenta o funcție a algebrei logicii:

• descrierea verbală este o formă care este utilizată în stadiul inițial de proiectare și are o reprezentare condiționată.
• descrierea funcției algebrei logicii sub forma unui tabel de adevăr.
• descrierea funcției algebrei logicii sub forma unei expresii algebrice: se folosesc două forme algebrice ale FAL:
  A) DNF - formă normală disjunctivă Este o sumă logică de produse logice elementare. DNF este obținut din tabelul de adevăr conform următorului algoritm sau regulă:
  1) acele rânduri de variabile pentru care funcția de ieșire = 1 sunt selectate în tabel.
  2) se scrie un produs logic pentru fiecare rând de variabile; unde variabilele = 0 sunt scrise cu inversare.
  3) produsul rezultat este însumat logic.
  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
  Un DNF se numește perfect dacă toate variabilele au același rang sau ordine, adică. fiecare lucrare trebuie să includă toate variabilele în formă directă sau inversă.
  b) CNF - formă normală conjunctivă Este un produs logic al unor sume logice elementare.
  CNF poate fi obținut din tabelul de adevăr folosind următorul algoritm:
  1) selectați seturi de variabile pentru care funcția de ieșire = 0
  2) pentru fiecare set de variabile notăm o sumă logică elementară, iar variabilele = 1 se scriu cu inversare.
  3) sumele primite se înmulțesc logic.
  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 se numește perfect dacă toate variabilele au același rang.

În formă algebrică, puteți construi un circuit de dispozitiv logic folosind porți logice.

Figura 1 - Diagrama dispozitivului logic

Toate operațiile booleene sunt definite tabele de adevăr valorile. Tabelul de adevăr determină rezultatul operației pentru toate sunt posibile x valorile logice ale afirmațiilor originale. Numărul de opțiuni care reflectă rezultatul aplicării operațiilor va depinde de numărul de instrucțiuni dintr-o expresie logică. Dacă numărul de afirmații dintr-o expresie logică este N, atunci tabelul de adevăr va conține 2 N linii, deoarece există 2 N combinații diferite de valori posibile ale argumentelor.

Operațiunea NOT - negație logică (inversie)

O operație logică NU se aplică unui singur argument, care poate fi o expresie logică simplă sau complexă. Rezultatul operației NU este următorul:

• dacă expresia inițială este adevărată, atunci rezultatul negației sale va fi fals;
• dacă expresia inițială este falsă, atunci rezultatul negației sale va fi adevărat.

Următoarele convenții NU sunt acceptate pentru operația de negație:
nu А, Â, nu A, ¬А,! A
Rezultatul unei operații de negație NU este determinat de următorul tabel de adevăr:

A	nu A
0	1
1	0

Rezultatul operației de negație este adevărat atunci când afirmația inițială este falsă și invers.

Operație SAU - adunare logică (disjuncție, unire)

Operația logic OR îndeplinește funcția de a combina două instrucțiuni, care pot fi fie o expresie logică simplă, fie o expresie logică complexă. Declarațiile care sunt sursa unei operații logice se numesc argumente. Rezultatul operației SAU este o expresie care va fi adevărată dacă și numai dacă cel puțin una dintre expresiile originale va fi adevărată.
Denumiri aplicate: A sau B, A V B, A sau B, A || B.
Rezultatul operației OR este determinat de următorul tabel de adevăr:
Rezultatul operației SAU este adevărat atunci când A este adevărat, sau B este adevărat, sau ambele A și B sunt adevărate în același timp și false când argumentele A și B sunt false.

Operație ȘI - înmulțire logică (conjuncție)

Operația logică AND îndeplinește funcția de intersecție a două afirmații (argumente), care pot fi atât o expresie logică simplă, cât și o expresie logică complexă. Rezultatul operației AND este o expresie care va fi adevărată dacă și numai dacă ambele expresii originale sunt adevărate.
Denumiri aplicate: A și B, A Λ B, A și B, A și B.
Rezultatul operației AND este determinat de următorul tabel de adevăr:

A	B	A și B
0	0	0
0	1	0
1	0	0
1	1	1

Rezultatul operației AND este adevărat dacă și numai dacă afirmațiile A și B sunt adevărate în același timp și false în toate celelalte cazuri.

Operațiunea „IF-THEN” - urmărire logică (implicație)

Această operație conectează două expresii logice simple, dintre care prima este o condiție, iar a doua este o consecință a acestei condiții.
Denumiri aplicate:
dacă A, atunci B; A implică B; dacă A atunci B; A → B.
Tabelul de adevăr:

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

Rezultatul următoarei operații (implicația) este fals numai atunci când premisa A este adevărată, iar concluzia B (consecința) este falsă.

Operația „A dacă și numai dacă B” (echivalență, echivalență)

Denumirea aplicată: A ↔ B, A ~ B.
Tabelul de adevăr:

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

Operațiunea „Adăugați mod 2” (XOR, exclusiv sau, disjuncție strictă)

Denumirea aplicată: A XOR B, A ⊕ B.
Tabelul de adevăr:

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

Rezultatul echivalenței operației este adevărat numai dacă A și B sunt ambele adevărate sau false în același timp.

Prioritate booleană

• Acțiunile între paranteze
• Inversiunea
• Conjuncție (&)
• Disjuncție (V), SAU exclusiv (XOR), sumă mod 2
• Implicație (→)
• Echivalență (↔)

Forma normală disjunctivă perfectă

Forma normală disjunctivă perfectă a unei formule(SDNF) este o formulă echivalentă cu aceasta, care este o disjuncție a conjuncțiilor elementare cu următoarele proprietăți:

1. Fiecare termen logic al formulei conține toate variabilele incluse în funcția F (x 1, x 2, ... x n).
2. Toți termenii logici ai formulei sunt diferiți.
3. Niciun termen logic nu conține o variabilă și negația acesteia.
4. Niciun termen logic dintr-o formulă nu conține aceeași variabilă de două ori.

SDNF poate fi obținut fie folosind tabele de adevăr, fie folosind transformări echivalente.
Pentru fiecare funcție, SDNF și SKNF sunt definite în mod unic până la permutare.

Forma normală conjunctivă perfectă

Formula de formă normală conjunctivă perfectă (SKNF) este o formulă echivalentă cu aceasta, care este o conjuncție de disjuncții elementare, care satisface proprietățile:

1. Toate propozițiile elementare conțin toate variabilele incluse în funcția F (x 1, x 2, ... x n).
2. Toate disjuncțiile elementare sunt diferite.
3. Fiecare disjuncție elementară conține o variabilă o dată.
4. Nicio disjuncție elementară nu conține o variabilă și negația acesteia.