Extinderea prin variabile vă permite să înlocuiți variabilele cu constantele unei funcții prin luarea variabilelor corespunzătoare în stânga funcțiilor. În exemplul de mai sus al expansiunii, a fost posibilă extinderea funcției a patru variabile într-o expresie în care funcția depinde numai de două variabile.
1.2.3. Proprietățile expansiunii în raport cu variabilele. Pentru m = 1 obținem extinderea unei funcții în raport cu o variabilă:
Un alt caz important: m = n. În acest caz, toate variabilele din partea dreaptă a (1.1) obțin valori fixe. Funcțiile din partea dreaptă devin constante 0 sau 1 și intră într-o conjuncție cu toate variabilele. De exemplu, pentru m = 2, avem:
Calculând valoarea adevărului unei funcții în toate cele patru interpretări diferite, este necesar să înlocuiți aceste valori în formula. Să presupunem, de exemplu, f (0, 1) = 0, f (0, 0) = 1, f (1, 0) = 1, f (1, 1) = 0, atunci f (x1, x2) = x1 0 × x2 0 + x1 1 × x2 0. Sau este compact :. Este ușor de observat că expresia obținută pentru această funcție se află în regiunea algebricii booleene, deoarece conține numai operații booleene.
În forma generală, proprietatea expansiunii în toate variabilele are forma:
adică, fiecare disjuncție corespunde unui set de variabile care inversează funcția inițială în 1.
Partea dreaptă a lui (1.3) este denumită forma normală disjunctivă normală (SDNF). Orice FAL este aliniat la un singur SDNF. Acest lucru ne permite să vorbim despre SDNF ca o formă standard de înregistrare FAL sub forma unei funcții de tip special de AD.
În viitor, vom arăta cum să traducem orice funcție în SDNF.
Pentru a obține CDNF, în conformitate cu (1.3), sunt necesare informații despre seturile în care funcția devine 1. Aceste informații sunt în tabelul de adevăr. Dar este de asemenea cunoscut faptul că FAL are două moduri de a reprezenta: sub forma unei tabele de adevăr și sub forma unei formulări, un polinom algebric binar al logicii. Dacă nu există o tabelă de adevăr, ci un polinom, atunci puteți obține CDNF folosind doar ea. Pentru aceasta, formula este modificată pas cu pas, fără a-și schimba sensul și este adusă treptat sub forma SDNF.
1.2.4. Completitudinea algebrei booleene. (1.3) conduce la o concluzie importantă.
TEOREM 1.2. BA, care utilizează 3 operații: o conjuncție, o disjuncție și o negare - este completă.
Astfel, 3 operațiuni sunt suficiente pentru a exprima prin ele orice FAL și formalizarea oricărei declarații verbale.
Pentru dovada este suficient să se uite la punctul 1.3, aici este clar că orice funcție (în stânga) poate fi reprezentată de o combinație de 3 operații (pe dreapta). (1.3) nu descrie doar o funcție: în această funcție nu există un set care să o transforme la 1. Această funcție este o constantă de 0. Dar nu este greu de arătat. Teorema este dovedită.
1.2.5. Tranziția la algebra booleană. Pentru a obține CDNF din PPF, mai întâi trebuie să faceți o tranziție la BA. La urma urmei, în CDNF există doar trei operațiuni. Declarațiile complexe de vorbire reală nu se limitează la sindicatele "AND", "OR" și la particula "NU". S-au format instrucțiuni compuse folosind toate operațiile din tabel. 2.
Constatând complet al astmului, putem fi siguri că orice funcție logică, inclusiv orice operațiune logică binară, exprimată în termeni de „AND“, „SAU“ și „NU“. Următoarele două relații interpretează operațiile de echivalență și implicare. Utilizând tabelul. 2, cititorul le va dovedi cu ușurință prin verificarea tuturor interpretărilor posibile ale atomilor.
Se recomandă cititorului să creeze o tabelă de ecuații care efectuează traducerea oricărei operații din tabel. 2 în funcționarea astmului.
1.2.6. Proprietățile operațiilor booleene. operații booleene au anumite proprietăți, care pot verifica construirea de tabele de adevăr pentru expresiile din ecuație pe raționamentul stânga și dreapta, sau logică, bazată pe identitatea expresiilor semnificație stânga și dreapta:
A doua aplicare a legii lui de Morgan dă:
care coincide cu rezultatul obținut din tabelul de adevăr.
1.2.13. Dovada echivalenței formulelor. Deci, SDNF și SKNF sunt formele standard de înregistrare FAL. În plus, funcția one-to-one cu SDNF-ul său este folosită pentru a demonstra echivalența a două funcții (formule). Introducerea consecventă a două formule la CDNF, concluzionează că ele sunt echivalente dacă SDNF-urile sunt aceleași.
1.2.14. Crearea de formule echivalente prin reducere la SDNF.
THEOREM 1.3. Pentru oricare două formule echivalente F 1 și F 2, există o transformare echivalentă a F1 la F2 prin intermediul relațiilor (1.4) - (1.17).
Dovada. Deoarece F1 și F2 sunt echivalente, CDNF-urile lor coincid. Reading (1.4) - (1.17) în direcția opusă, este posibil de PDNF F 2 go la majoritatea 2. F F 1 Se procedează apoi la PDNF și de la PDNF proceda la 2. F rezultată arată astfel lanțul de transformări echivalență formulele F 1 și F 2. Teorema este dovedită.
1.2.15. Dualitatea. După cum a arătat practica, echivalențele sunt importante în lucrul cu FAL, astfel încât nu este inutil să se descrie încă un alt mod de obținere a echivalențelor. Acesta este aparatul cu funcții duale.
1.2.16. Principiul dualității. Folosind definiția dualității, nu este dificil să demonstrăm principiul dualității printr-un calcul direct. dacă în formula reprezentând funcția toate semnele de funcții sunt înlocuite de funcții duale, atunci formula rezultantă va descrie o funcție dublă funcției inițiale.
În BA, conjuncția este dublă față de disjuncție, unitatea este zero, negarea este auto-dublă. Folosind acest lucru, noi echivalente sunt obținute în BA. Înlocuirea în partea stângă + pe . pe +, 1 pe 0 și 0 pe 1, obțineți o formulă dublă în partea stângă, apoi faceți același lucru cu partea dreaptă și formulele obținute sunt asimilate. Au fost obținute două relații de absorbție în acest fel.
1.3 Metodele rezolvării problemelor tipice
1.3.1. Formalizarea declarațiilor. Sarcina de a formaliza o exprimare este de a pune formula care reflectă structura sa internă în conformitate cu declarația.
Pentru a rezolva problema formalizării unei declarații, este necesar să se facă distincția în termenii "atomi" - părți indivizibile, declarații elementare. Aceste afirmații sunt cele mai simple pentru a compara semnificația logică: "adevăr" sau "minciună". Într-o formulă scrisă echivalentă cu o afirmație lingvistică, declarațiile elementare corespund atomilor (numele variabilelor).
Luați în considerare exemplul: "Dacă focul arde și lemnul este uscat, acum este întuneric sau rece. Dacă lemnul nu este uscat, nu este adevărat că este acum întuneric sau rece, cu excepția faptului că în cazul în care focul nu arde, atunci este rece. Din toate cele de mai sus rezultă că fie este rece, iar lemnul este uscat, sau este acum întuneric și focul arde ". Selectați atomii: x - "foc este ars", y - "lemn uscat", z - "acum întuneric", h - "acum este rece".
După determinarea atomilor, este necesar să restabiliți structura instrucțiunii originale folosind conectori logici. Construcțiile principale ale limbii care definesc structura cuvântului sunt prezentate în Tabelul. 3. Dacă în instrucțiune structura este setată de vorbirea transformă nu este prezentată în tab. 3, este necesar să încercați să le reduceți la tabel. Pentru a face acest lucru, cifra de afaceri discutabilă este înlocuită cu cea cunoscută (din tabelul 3) și, dacă se păstrează structura și semnificația declarației, atunci cifra de afaceri a bursierului este tabelară.
Rezumatul operațiunilor logice
Declarația din exemplu constă din 3 propoziții. Formalizăm fiecare dintre ele separat ținând cont de atomii fixi:
1. "Dacă focul arde și lemnul este uscat, este acum întuneric sau rece": Deoarece implicația se referă la ambii atomi, z și h. ele trebuie separate de delimitatori.
2. „În cazul în care lemnul nu este uscat, nu este adevărat că acum întuneric sau rece, în plus, în cazul în care focul nu este aprins, rece“: Sarcina a devenit aspect mai complex de „plus“ de înlocuire ligamentului a acestui ligament conjuncția „și“ nu schimbă sensul vorbit . Banda "și" este una dintre cele mai "puternice", deci sunt necesare delimitatori, astfel încât părțile dorite ale propoziției să intre în conjuncție. În plus, expresia "nu este bine că este acum întuneric sau rece" poate fi scrisă în două moduri echivalente:
Datorită volumului mare, acest material este plasat pe mai multe pagini:
1 2 3 4 5 6 7
Aboneaza-te la newsletter-ul nostru:
Știri interesante
Subiecte importante
Recenzii de servicii Pandia.ru
Federația Rusă
o putere puternică!
calcul
aceasta este dobândirea de cunoștințe noi din datele de intrare
Proiecte pe tema:
matematică
logică
Vatră acasă
Informații de referință
Educație și știință
Afaceri și Finanțe
tehnologiei
infrastructură
Trimiteți-le prietenilor: