Schema electrica, conceput pentru a efectua o operațiune logică cu date de intrare, se numește element logic. Datele de intrare sunt reprezentate aici sub formă de tensiuni de diferite niveluri, iar rezultatul operației logice la ieșire se obține și sub forma unei tensiuni de un anumit nivel.
În acest caz, operanzii sunt furnizați - semnalele sub forma unei tensiuni de nivel înalt sau scăzut sunt recepționate la intrarea elementului logic, care servesc în esență ca date de intrare. Astfel, o tensiune de nivel înalt - un 1 logic - indică o valoare adevărată a operandului, iar o tensiune de nivel scăzut 0 - o valoare falsă. 1 - ADEVĂRAT, 0 - FALS.
Element logic- un element care implementează anumite relații logice între semnalele de intrare și de ieșire. Porțile logice sunt utilizate în mod obișnuit pentru a construi circuite logice calculatoare, circuite automate discrete de monitorizare și control. Toate tipurile de elemente logice, indiferent de natura lor fizică, se caracterizează prin valori discrete ale semnalelor de intrare și de ieșire.
Elementele logice au una sau mai multe intrări și una sau două ieșiri (de obicei inverse una față de cealaltă). Valorile „zerourilor” și „unui” ale semnalelor de ieșire ale elementelor logice sunt determinate de funcția logică pe care o îndeplinește elementul și de valorile „zerourilor” și „unui” ale semnalelor de intrare, care sunt redate. rolul variabilelor independente. Există funcții logice elementare din care poate fi compusă orice funcție logică complexă.
În funcție de proiectarea circuitului elementului, de parametrii săi electrici, nivelurile logice (niveluri de tensiune înaltă și joasă) ale intrării și ieșirii au aceleași valori pentru stările înalte și scăzute (adevărat și fals).
În mod tradițional, elementele logice sunt produse sub formă de componente radio speciale - circuite integrate. Operații logice, precum conjuncția, disjuncția, negația și adăugarea modulo (ȘI, SAU, NU, SAU exclusiv) sunt operațiile de bază efectuate pe porțile logice ale principalelor tipuri. În continuare, să ne uităm mai atent la fiecare dintre aceste tipuri de elemente logice.
Element logic „ȘI” - conjuncție, înmulțire logică, ȘI
„ȘI” este un element logic care efectuează o operație de conjuncție sau de multiplicare logică asupra datelor de intrare. Acest obiect poate avea de la 2 la 8 (cele mai comune în producție sunt elementele „ȘI” cu 2, 3, 4 și 8 intrări) intrări și o ieșire.
Simbolurile elementelor logice „ȘI” cu numere diferite de intrări sunt prezentate în figură. În text, un element logic „ȘI” cu un anumit număr de intrări este desemnat ca „2I”, „4I”, etc. - un element „ȘI” cu două intrări, cu patru intrări etc.
Tabelul de adevăr pentru elementul 2I arată că ieșirea elementului va fi una logică numai dacă cele logice sunt simultan la prima intrare ȘI la a doua intrare. În celelalte trei cazuri posibile, rezultatul va fi zero.
În diagramele occidentale, pictograma elementului I are o linie dreaptă la intrare și o linie rotunjită la ieșire. Pe diagramele interne - un dreptunghi cu simbolul „&”.
Element logic „SAU” - disjuncție, adunare logică, SAU
„SAU” este un element logic care efectuează o operație de disjuncție sau de adăugare logică asupra datelor de intrare. El, ca și elementul „I”, este disponibil cu două, trei, patru, etc. intrări și o ieșire. Simbolurile elementelor logice „SAU” cu numere diferite de intrări sunt prezentate în figură. Aceste elemente sunt desemnate după cum urmează: 2OR, 3OR, 4OR etc.
Tabelul de adevăr pentru elementul „2OR” arată că pentru ca unul logic să apară la ieșire, este suficient ca cel logic să fie la prima intrare SAU la a doua intrare. Dacă există cele logice la două intrări simultan, ieșirea va fi, de asemenea, una.
În diagramele occidentale, pictograma elementului „SAU” are o intrare rotunjită și o ieșire rotunjită, ascuțită. Pe diagramele interne există un dreptunghi cu simbolul „1”.
Element logic „NU” - negație, invertor, NU
„NU” este un element logic care efectuează o operație de negație logică asupra datelor de intrare. Acest element, care are o singură ieșire și o singură intrare, se mai numește și invertor, deoarece de fapt inversează (inversează) semnalul de intrare. Figura prezintă simbolul pentru elementul logic „NU”.
Tabelul de adevăr pentru un invertor arată că un potențial de intrare ridicat produce un potențial de ieșire scăzut și invers.
În diagramele occidentale, pictograma elementului „NU” are forma unui triunghi cu un cerc la ieșire. Pe diagramele interne există un dreptunghi cu simbolul „1”, cu un cerc la ieșire.
Element logic „NAND” - conjuncție (înmulțire logică) cu negație, NAND
„ȘI-NU” este un element logic care efectuează o operație de adăugare logică asupra datelor de intrare, iar apoi o operație de negație logică, rezultatul este trimis la ieșire. Cu alte cuvinte, este practic un element „ȘI”, completat de un element „NU”. Figura prezintă simbolul pentru elementul logic „2ȘI-NU”.
Tabelul de adevăr pentru poarta NAND este opusul tabelului de adevăr pentru poarta AND. În loc de trei zerouri și unul, sunt trei unu și un zero. Elementul NAND este numit și „elementul Schaeffer” în onoarea matematicianului Henry Maurice Schaeffer, care a remarcat pentru prima dată semnificația lui în 1913. Notat ca „I”, doar cu un cerc la ieșire.
Element logic „OR-NOT” - disjuncție (adunare logică) cu negație, NOR
„SAU-NU” este un element logic care efectuează o operație de adăugare logică asupra datelor de intrare, iar apoi o operație de negație logică, rezultatul este trimis la ieșire. Cu alte cuvinte, acesta este un element „SAU” completat de un element „NU” - un invertor. Figura prezintă simbolul pentru elementul logic „2SAU-NU”.
Tabelul de adevăr pentru o poartă SAU este opusul tabelului de adevăr pentru o poartă SAU. Un potențial de ieșire ridicat este obținut doar într-un caz - potențialele scăzute sunt aplicate simultan ambelor intrări. Este desemnat ca „SAU”, doar cu un cerc la ieșire care indică inversarea.
Poarta logică "SAU exclusivă" - adăugare modulo 2, XOR
„SAU exclusiv” este un element logic care efectuează o operație de adăugare logică modulo 2 asupra datelor de intrare, are două intrări și o ieșire. Adesea aceste elemente sunt utilizate în circuitele de control. Figura prezintă simbolul pentru acest element.
Imaginea în circuitele vestice este ca „SAU” cu o bandă curbată suplimentară pe partea de intrare, în cele domestice este ca „SAU”, doar că în loc de „1” se va scrie „=1”.
Acest element logic este numit și „neechivalență”. Un nivel de tensiune ridicat va fi la ieșire numai atunci când semnalele de la intrare nu sunt egale (unul este unul, celălalt este zero sau unul este zero, iar celălalt este unul), chiar dacă sunt două la intrare în același timp, ieșirea va fi zero - aceasta este diferența față de „SAU”. Aceste elemente logice sunt utilizate pe scară largă în sumatori.
Secțiuni: Informatică
În prezent, la examenele de admitere în informatică există multe sarcini pe tema „algebra logicii”. Scopul acestei lecții este de a consolida abilitățile de rezolvare a sarcinilor Unified State Examination în informatică folosind elemente de algebră logică.
Obiectivele lecției:
- Formarea capacității de a aplica în practică cunoștințele dobândite;
- Dezvoltarea capacității de a construi tabele de adevăr folosind formule date;
- Dezvoltarea abilității de a rezolva probleme de cuvinte folosind legile logicii.
Obiectivele lecției:
- Educational – dezvoltarea interesului cognitiv, gândirea logică.
- Educational– repetarea bazelor logicii matematice, îndeplinirea sarcinilor practice.
- De dezvoltare – dezvoltarea gândirii logice, a atenției.
În timpul orelor
- Repetarea operațiilor și legilor logice.
- Aplicarea operațiilor logice și a legilor în practică.
- Explicația temei.
Astăzi terminăm subiectul „Fundamentals of Logic” și vom aplica operații logice de bază și legile de transformare pentru a rezolva sarcinile Unified State Examination în informatică.
Lecția se desfășoară în paralel cu prezentarea.<Приложение1>
1. Repetarea operațiilor și legilor logice.
Algebra logicii este o ramură a logicii matematice care studiază structura enunțurilor logice complexe și metodele de stabilire a adevărului lor folosind metode algebrice.
1. Fondatorul logicii formale?
Aristotel.
2. Fondatorul algebrei logicii?
George Boole.
3. Enumerați operațiunile logice:
¬ negație (inversare)
&, /\conjuncție („Și”)
V disjuncție („SAU”)
consecință logică (implicație)
echivalență (echivalență)
4. Care este sensul legii dublei negații?
Un dublu negativ elimină negativul.
5. Legile lui De Morgan (legile inversiunii generale).
Negația unei disjuncții este o conjuncție de negații:
¬(A V B) = ¬A /\ ¬B
Negația unei conjuncții este o disjuncție a negațiilor:
¬(A /\B) = ¬A V ¬B
6. Legea idempotentei (asimilitatii).
7. Care este sensul legii excluderii celui de-al treilea?
Dintre două afirmații contradictorii despre același lucru, una este întotdeauna adevărată, a doua este falsă și a treia nu este dată:
8. Despre ce este legea contradicției?
O afirmație și negația ei nu pot fi adevărate în același timp:
9. Legea excluderii constantelor.
Pentru adăugarea logică:
A V 1 = 1 A V 0 = A
Pentru înmulțirea logică:
A /\ 1 = A A /\ 0 = 0
10. Cum se exprimă o implicație printr-o disjuncție?
A B = ¬A V B
2. Aplicarea operaţiilor logice şi a legilor în practică.
Exemplul 1. ( Task A11 versiunea demonstrativă 2004)
Pentru care nume este adevărată afirmația:
¬ (Prima literă a numelui este o vocală -> A patra literă a numelui este o consoană)?
Soluţie. O declarație complexă constă din două afirmații simple:
A este prima literă a numelui, vocala,
B este a patra literă a numelui, o consoană.
¬ (A B) = ¬ (¬A V B) = (¬ (¬A) /\ ¬B) = A /\ ¬B
Formule folosite:
1. Implicație prin disjuncția A? B = ¬A V B
2. Legea lui De Morgan ¬(A V B) = ¬A /\ ¬B
3. Legea dublei negaţii.
(Prima literă a numelui este o vocală /\ A patra literă a numelui este o vocală)
Exemplul 2. ( Task A12 versiunea demonstrativă 2004)
Ce expresie logică este echivalentă cu expresia ¬ (A \/ ¬B)?
Soluţie. ¬ (A \/ ¬B)= ¬ A \/ ¬ (¬B)= ¬ A \/ B
Creați un tabel de adevăr pentru formulă
¬ (B /\ C) V (A/\C B)
Ordinea operațiilor logice:
¬ (B /\ C) V (A/\C B)
Creați un tabel de adevăr.
Câte rânduri vor fi în tabelul tău? 3 variabile: A, B, C; 2 3 =8
Câte coloane? 5 operații + 3 variabile = 8
| A | B | C | (B/\C) | ¬(B/\C) | A/\C | (A/\C ? B) | ¬ (B /\ C) V (A/\CB) |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
Ce răspunsuri ați primit în ultima coloană?
identic adevărat, dacă ia valori 1 pe toate seturile de instrucțiuni simple incluse în acesta. Se numesc formule identic adevărate tautologii.
Să rezolvăm acest exemplu folosind metoda analitică:
simplificați expresia
¬ (B /\ C) V (A/\C B)= (aplicați formula pentru implicare)
¬ (B /\ C) V ¬ (A /\ C) V B = (aplicați 1 și 2 legile lui de Morgan)
(¬B V ¬C) V (¬A V ¬C) V B = (înlăturați parantezele)
¬B V ¬C V ¬A V ¬C V B= (aplicați legea comutativă)
¬B V B V ¬C V ¬C V ¬A = (legea excluderii mijlocului, legea idempotei)
1 V ¬С V ¬A = 1 V ¬A = 1 (legea excluderii constantelor)
Răspuns: 1 , înseamnă că formula este identic adevărată sau o tautologie.
Se numește expresia logică identic fals, dacă ia valori 0 pe toate seturile de instrucțiuni simple incluse în acesta.
(tema pentru acasă 3)
Tabelul prezintă interogări către serverul de căutare. Aranjați desemnările interogărilor în ordinea crescătoare a numărului de pagini pe care motorul de căutare le va găsi pentru fiecare interogare.
Simbolul I este folosit pentru a indica operația logică „SAU” în interogare, iar simbolul & este folosit pentru a indica operația logică „ȘI”.
Prima metodă se bazează pe raționament. Raționând logic, vedem că cele mai multe pagini vor fi găsite pentru interogarea G, deoarece atunci când este executată, paginile cu cuvântul „legi”, și paginile cu cuvântul „fizică”, și paginile cu cuvântul „biologie” găsite. Cel mai mic număr de pagini va fi găsit pentru interogarea B, deoarece conține prezența tuturor celor patru cuvinte pe pagina căutată. Rămâne de comparat interogările A și B. Interogarea B va găsi toate paginile corespunzătoare interogării A (deoarece aceasta din urmă conține în mod necesar cuvântul „legi”), precum și paginile care conțin atât cuvintele „fizică”, cât și „biologie”. Prin urmare, vor fi găsite mai multe pagini pentru interogarea B decât pentru interogarea A. Deci, ordonând interogările în ordine crescătoare a paginilor, obținem VABG.
Răspuns: VABG.
A doua metodă presupune utilizarea unei reprezentări grafice a operațiilor pe mulțimi. (Vezi prezentarea)
Exemplul 5. ( Task A16 versiunea demonstrativă 2006)
Mai jos, în formă tabelară, este un fragment al bazei de date cu rezultatele testării elevilor (este folosită o scară de o sută de puncte)
| Nume de familie | Podea | Matematică | Limba rusă | Chimie | Informatică | Biologie |
| Aganyan | și | 82 | 56 | 46 | 32 | 70 |
| Voronin | m | 43 | 62 | 45 | 74 | 23 |
| Grigorchuk | m | 54 | 74 | 68 | 75 | 83 |
| Rodnina | și | 71 | 63 | 56 | 82 | 79 |
| Sergeenko | și | 33 | 25 | 74 | 38 | 46 |
| Cherepanova | și | 18 | 92 | 83 | 28 | 61 |
Câte înregistrări din acest fragment satisfac condiția
„Gen=’m’ SAU Chimie>Biologie”?
Selectăm intrările: Băieți (doi) și Chimie>Biologie (trei, dar un băiat, luat deja 1 dată). Ca urmare, 4 înregistrări îndeplinesc condiția.
Sarcina 6. ( Task B4 versiunea demonstrativă 2007)
În campionatul școlar de tenis de masă, primele patru au inclus fete: Natasha, Masha, Lyuda și Rita. Cei mai înfocați fani și-au exprimat presupunerile cu privire la distribuția locurilor în competițiile ulterioare.
Se crede că Natasha va fi prima, iar Masha va fi a doua.
Un alt fan o prezice pe Luda pe locul doi, iar Rita, în opinia sa, va ocupa locul patru.
Un al treilea fan de tenis nu a fost de acord cu ei. El crede că Rita va ocupa locul trei, iar Natasha va fi a doua.
Ce loc au ocupat Natasha, Masha, Lyuda, Rita la campionat?
(În răspunsul dumneavoastră, enumerați pe rând, fără spații, numerele corespunzătoare locurilor fetelor în ordinea specificată a numelor.)
Să notăm afirmațiile:
H1 = „Natasha va fi prima”;
M2 = „Masha va fi a doua”;
L2 = „Luda va fi a doua”;
P4 = „Rita va fi a patra”;
P3 = „Rita va fi a treia”;
H2 = „Natasha va fi a doua.”
Dupa conditie:
din afirmatiile unui ventilator rezulta ca H1VM2 este adevarat;
din afirmațiile fanului2 rezultă că A2VP4 este adevărat;
din afirmatiile ventilatorului 3 rezulta ca P3VH2 este adevarat.
Prin urmare, și conjuncția este adevărată
(H1VM2) /\ (L2VP4) /\ (Р3VН2) = 1.
Deschizând parantezele obținem:
(Н1VM2) /\ (Л2VP4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=
Н1/\Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/ \Л2/\Н2 V М2/\Р4/\Н2 =Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3
Natasha-1, Lyuda-2, Rita-3 și Masha-4.
Răspuns: 1423
3. Explicarea temelor.
Exercitiul 1. ( Task B8 versiunea demonstrativă 2007)
Tabelul prezintă interogări către serverul de căutare. Aranjați simbolurile de interogare în ordinea crescătoare a numărului de pagini pe care motorul de căutare le va găsi pentru fiecare interogare.
Pentru a indica operația logică „SAU” în interogare, utilizați simbolul | și pentru a indica operația logică „ȘI” – &.
Sarcina 2 ( Task B4 versiunea demo 2008)
Înainte de începerea Turneului celor Patru, fanii au făcut următoarele presupuneri despre idolii lor:
A) Max va câștiga, Bill va fi al doilea;
B) Bill este al treilea. Nick este primul;
C) Max este ultimul, iar primul este John.
Când competiția s-a încheiat, s-a dovedit că fiecare dintre fani a avut dreptate doar în una dintre predicțiile lor.
Ce loc au ocupat John, Nick, Bill, Max în turneu?
(În răspunsul dvs., enumerați locurile participanților într-un rând fără spații, în ordinea specificată a numelor.)
Conjuncție sau înmulțire logică (în teoria mulțimilor, aceasta este intersecția)
O conjuncție este o expresie logică complexă care este adevărată dacă și numai dacă ambele expresii simple sunt adevărate. Această situație este posibilă doar într-un singur caz; în toate celelalte cazuri conjuncția este falsă.
Notație: &, $\wedge$, $\cdot$.
Tabelul de adevăr pentru conjuncție
Poza 1.
Proprietățile conjuncției:
- Dacă cel puțin una dintre subexpresiile unei conjuncții este falsă pentru un set de valori variabile, atunci întreaga conjuncție va fi falsă pentru acest set de valori.
- Dacă toate expresiile unei conjuncții sunt adevărate pe un set de valori variabile, atunci întreaga conjuncție va fi și ea adevărată.
- Sensul întregii conjuncții a unei expresii complexe nu depinde de ordinea în care sunt scrise subexpresiile cărora se aplică (ca înmulțirea la matematică).
Disjuncție sau adunare logică (în teoria mulțimilor aceasta este uniunea)
O disjuncție este o expresie logică complexă care este aproape întotdeauna adevărată, cu excepția cazului în care toate expresiile sunt false.
Notație: +, $\vee$.
Tabelul de adevăr pentru disjuncție
Figura 2.
Proprietățile disjuncției:
- Dacă cel puțin una dintre subexpresiile disjuncției este adevărată pentru un set de valori variabile, atunci întreaga disjuncție capătă o valoare adevărată pentru acest set subexpresii.
- Dacă toate expresiile dintr-o listă de disjuncții sunt false pe un set de valori variabile, atunci întreaga disjuncție a acestor expresii este de asemenea falsă.
- Sensul întregii disjuncții nu depinde de ordinea în care sunt scrise subexpresiile (ca la matematică - adunare).
Negație, negație logică sau inversare (în teoria mulțimilor aceasta este negație)
Negația înseamnă că particula NU sau cuvântul FALSE se adaugă la expresia logică inițială, CE și ca rezultat obținem că dacă expresia originală este adevărată, atunci negația originalului va fi falsă și invers, dacă expresia originală. este falsă, atunci negația sa va fi adevărată.
Notație: nu $A$, $\bar(A)$, $¬A$.
Tabelul de adevăr pentru inversare
Figura 3.
Proprietățile negației:
„Negația dublă” a lui $¬¬A$ este o consecință a propoziției $A$, adică este o tautologie în logica formală și este egală cu valoarea însăși în logica booleană.
Implicație sau consecință logică
O implicație este o expresie logică complexă care este adevărată în toate cazurile, cu excepția cazului în care adevărul urmează falsului. Adică, această operație logică conectează două expresii logice simple, dintre care prima este o condiție ($A$), iar a doua ($A$) este o consecință a condiției ($A$).
Notație: $\to$, $\Rightarrow$.
Tabel de adevăr pentru implicare
Figura 4.
Proprietăți ale implicației:
- $A \to B = ¬A \vee B$.
- Implicația $A \to B$ este falsă dacă $A=1$ și $B=0$.
- Dacă $A=0$, atunci implicația $A \la B$ este adevărată pentru orice valoare a lui $B$, (adevărat poate decurge din fals).
Echivalența sau echivalența logică
Echivalența este o expresie logică complexă care este adevărată pentru valori egale ale variabilelor $A$ și $B$.
Notație: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.
Tabelul de adevăr pentru echivalență
Figura 5.
Proprietăți de echivalență:
- Echivalența este adevărată pe seturi egale de valori ale variabilelor $A$ și $B$.
- CNF $A \equiv B = (\bar(A) \vee B) \cdot (A \cdot \bar(B))$
- DNF $A \equiv B = \bar(A) \cdot \bar(B) \vee A \cdot B$
Disjuncție strictă sau adunare modulo 2 (în teoria mulțimilor, aceasta este unirea a două mulțimi fără intersecția lor)
O disjuncție strictă este adevărată dacă valorile argumentelor nu sunt egale.
Pentru electronică, aceasta înseamnă că implementarea circuitelor este posibilă folosind un element standard (deși acesta este un element scump).
Ordinea operațiilor logice într-o expresie logică complexă
- Inversiunea(negarea);
- Conjuncție (înmulțire logică);
- Disjuncția și disjuncția strictă (adăugarea logică);
- Implicație (consecință);
- Echivalența (identitatea).
Pentru a modifica ordinea specificată a operațiilor logice, trebuie să utilizați paranteze.
Proprietăți generale
Pentru un set de $n$ variabile booleene, există exact $2^n$ valori distincte. Tabelul de adevăr pentru o expresie logică a $n$ variabile conține $n+1$ coloane și $2^n$ rânduri.
PROPRIETĂȚI ALE OPERAȚIUNILOR LOGICE
1. Denumiri
1.1. Notație pentru conexiunile logice (operații):
A) negare(inversiunea, NOT logic) este notat cu ¬ (de exemplu, ¬A);
b) conjuncţie(înmulțirea logică, AND logic) se notează cu /\
(de exemplu, A /\ B) sau & (de exemplu, A & B);
c) disjuncție(adăugarea logică, SAU logic) se notează cu \/
(de exemplu, A \/ B);
d) ca urmare a(implicație) se notează cu → (de exemplu, A → B);
e) identitate notat cu ≡ (de exemplu, A ≡ B). Expresia A ≡ B este adevărată dacă și numai dacă valorile lui A și B sunt aceleași (fie ambele sunt adevărate, fie ambele sunt false);
f) simbolul 1 este folosit pentru a desemna adevărul (afirmația adevărată); simbolul 0 – pentru a indica o minciună (afirmație falsă).
1.2. Sunt numite două expresii booleene care conțin variabile echivalent (echivalent) dacă valorile acestor expresii coincid pentru orice valori ale variabilelor. Astfel, expresiile A → B și (¬A) \/ B sunt echivalente, dar A /\ B și A \/ B nu sunt (sensurile expresiilor sunt diferite, de exemplu, când A = 1, B = 0 ).
1.3. Prioritățile operațiilor logice: inversare (negație), conjuncție (înmulțire logică), disjuncție (adunare logică), implicație (urmărire), identitate. Astfel, ¬A \/ B \/ C \/ D înseamnă la fel ca
((¬A) \/ B) \/ (C \/ D).
Este posibil să scrieți A \/ B \/ C în loc de (A \/ B) \/ C. Același lucru este valabil și pentru conjuncție: este posibil să scrieți A /\ B /\ C în loc de (A /\ B ) /\ C.
2. Proprietăți
Lista de mai jos NU se dorește a fi completă, dar este, sperăm, suficient de reprezentativă.
2.1. Proprietăți generale
- Pentru un set de n sunt exact variabile logice 2 n sensuri diferite. Tabelul de adevăr pentru expresia logică din n variabilele contine n+1 coloana si 2 n linii.
2.2.Disjuncţie
- Dacă cel puțin una dintre subexpresiile cărora li se aplică disjuncția este adevărată pe un set de valori ale variabilelor, atunci întreaga disjuncție este adevărată pentru acest set de valori.
- Dacă toate expresiile dintr-o anumită listă sunt adevărate pe un anumit set de valori variabile, atunci este adevărată și disjuncția acestor expresii.
- Dacă toate expresiile dintr-o anumită listă sunt false pe un anumit set de valori variabile, atunci disjuncția acestor expresii este și ea falsă.
- Sensul unei disjuncții nu depinde de ordinea de scriere a subexpresiilor la care se aplică.
2.3. Conjuncție
- Dacă cel puțin una dintre subexpresiile cărora le este aplicată conjuncția este falsă pentru un set de valori variabile, atunci întreaga conjuncție este falsă pentru acest set de valori.
- Dacă toate expresiile dintr-o anumită listă sunt adevărate pe un anumit set de valori variabile, atunci conjuncția acestor expresii este de asemenea adevărată.
- Dacă toate expresiile dintr-o anumită listă sunt false pe un anumit set de valori variabile, atunci conjuncția acestor expresii este și ea falsă.
- Sensul unei conjuncții nu depinde de ordinea de scriere a subexpresiilor la care se aplică.
2.4. Disjuncții și conjuncții simple
Să numim (pentru comoditate) conjuncția simplu, dacă subexpresiile la care se aplică conjuncția sunt variabile distincte sau negații ale acestora. În mod similar, se numește disjuncția simplu, dacă subexpresiile cărora li se aplică disjuncția sunt variabile distincte sau negații ale acestora.
- O conjuncție simplă evaluează la 1 (adevărat) pe exact un set de valori variabile.
- O disjuncție simplă evaluează la 0 (fals) pe exact un set de valori variabile.
2.5. Implicare
- Implicare A →B este echivalent cu disjuncția (¬ A) \/ B. Această disjuncție mai poate fi scrisă astfel: ¬ A\/B.
- Implicare A →B ia valoarea 0 (fals) numai dacă A=1Și B=0. Dacă A=0, apoi implicația A →B adevărat pentru orice valoare B.
Pentru cautare rapida informațiile de pe Internet sunt utilizate de interogări de căutare. O interogare de căutare este un set Cuvinte cheie, legate prin semnele operațiilor logice ȘI, SAU, NU.
Prioritatea operațiilor, dacă nu există paranteze special plasate, este următoarea: mai întâi NU, apoi ȘI, apoi SAU.
Trebuie să înțelegeți că operația AND (îndeplinirea simultană a condițiilor) reduce volumul rezultatului obținut, iar operația SAU (îndeplinirea a cel puțin una dintre condiții) dimpotrivă crește volumul.
Dacă cererea conține o expresie între ghilimele, sistemul va căuta exact acea expresie în întregime.
1. Aranjarea interogărilor în ordine crescătoare (descrescătoare).
Operația „ȘI” (&) indică prezența simultană a cuvintelor cheie în documentele căutate și, prin urmare, reduce cantitatea de informații găsite. Cu cât sunt conectate mai multe cuvinte cheie folosind operația „ȘI”, cu atât se găsesc mai puține informații. În schimb, operația „SAU” (|) indică prezența a cel puțin unui cuvânt cheie în documentele căutate și, prin urmare, crește cantitatea de informații găsite.
Exemplul 1.
Tabelul prezintă interogări către serverul de căutare. Aranjați simbolurile de interogare în ordinea crescătoare a numărului de pagini pe care motorul de căutare le va găsi pentru fiecare interogare.
A) abstract | matematică | Gauss
B) rezumat | matematică | Gauss | metodă
B) rezumat | matematică
D) abstract & matematică & Gauss
Soluţie:
Cel mai mic număr de pagini va fi selectat pentru interogarea cu cel mai mare număr de operații „ȘI” (interogarea D), cel mai mare număr de pagini va fi selectat pentru interogarea cu cel mai mare număr de operații „SAU” (interogarea B). Vor fi selectate mai multe pagini pentru interogarea A decât pentru interogarea B, deoarece Interogarea A conține mai multe cuvinte cheie SAU.
Răspuns: GWAB
2. Numărarea paginilor găsite la cerere
Acest tip de problemă este de obicei rezolvată printr-un sistem de ecuații. Voi sugera o modalitate mai vizuală și mai simplă.
Principiul selectării informaţiei conform interogări de căutare Diagrama Euler-Venn (cercurile euleriene) ilustrează bine acest lucru. În diagramă, mulțimile sunt reprezentate prin cercuri care se intersectează. Operația AND (&) este intersecția cercurilor, iar operația SAU (|) este uniunea cercurilor.
De exemplu, să notăm seturile Mere, Pere, Banane cu cercuri. Interogarea Mere, Pere și Banane va selecta intersecția (partea comună) a tuturor celor trei cercuri:
La cerere Mere | Perele vor fi selectate prin combinarea a două cercuri:
Exemplul 2.
Tabelul arată interogările și numărul de pagini pe care motorul de căutare le-a găsit pentru aceste interogări într-un anumit segment de internet:
Câte pagini (în mii) vor fi găsite pentru interogarea șah?
Soluţie:
Să desenăm o diagramă Euler-Venn. Metoda de rezolvare a problemei este de a număra numărul de pagini corespunzător fiecărei zone delimitate de linii:
Interogarea șah & tenis corespunde zonei din mijloc (1000 mii pagini), iar interogarea tenis corespunde întregului cerc din dreapta (5500 mii pagini).
Atunci „cercul tăiat” din dreapta este 5500-1000=4500:
Cere șah | tenis ambele cercuri corespund (7770), apoi „cercul tăiat” din stânga este 7770-5500=2270
