În secțiunea logicii propoziționale sunt considerate funcții booleene, adică funcții care iau doar două valori: adevărate sau false. Funcțiile booleene pot fi împărțite în clase de funcții (grupuri de funcții), relativ la o anumită caracteristică. Se spune că o clasă de funcții booleene este închisă dacă în ea este cuprinsă o combinație de funcții dintr-o anumită clasă. Printr-o combinație de funcții booleene înțelegem o funcție constând din alte funcții booleene legate de semnele operațiilor logice.
Există mai multe clase de funcții închise:
1) Clasa funcțiilor care păstrează zero :.
2) Clasa funcțiilor care păstrează identitatea :.
3) Clasa S a funcțiilor auto-duale este o funcție pe seturi opuse care iau valori opuse.
4) Clasa funcțiilor liniare L este compusă din funcții care sunt reprezentate de polinomul Zhegalkin de gradul I.
5) Clasa M a funcțiilor monotone: pentru vectorii binare și. în cazul în care. . se introduce următoarea relație parțială. Se crede că. dacă pentru. Clasa M este definită după cum urmează:
Verificarea că funcția Booleană aparține claselor închise se face conform tabelului de adevăr. Verificarea faptului că funcția booleană aparține clasei L se realizează prin construirea polinomului Zhegalkin.
Funcția de algebră a logicii se numește monotonă. dacă pentru orice seturi b dimensionale n, de la asta. rezultă că
O teoremă asupra funcțiilor monotonice: fiecare funcție booleană în semnătura unei algebre logice care nu conține negări este o funcție monotonă. pentru orice funcție monotonă a algebrei logice, alta decât 0 și 1, există o funcție booleană echivalentă fără negări.
Exemplu 1. Determinați dacă funcția este monotonă.
- nu conține negări, este monotonă.
Funcția se numește funcția duală a funcției. Funcția se numește auto-dublă. în cazul în care.
Auto-dualele sunt funcții
Verificați pe funcțiile de auto-duale pot fi efectuate pe tabela de adevăr, care în ultima coloană: primul 0 sau 1 se înlocuiește cu 1 sau 0, legat de ultimul loc, în cazul în care pe ultimul loc este 1 sau 0, controalele sunt pe - în comparație cu cea de a doua linie și penultima, și așa mai departe până la mijloc. Dacă două valori identice sunt obținute pe cel puțin două linii din ultima coloană a tabelului de adevăr simetric față de mijloc, atunci funcția nu este auto-dublă.
Exemplu 2. Determinați dacă funcția este dublă.
Construim funcția duală la funcția inițială:
Dacă funcția duală față de funcția originală este egală cu funcția originală, atunci funcția originală este auto-duală.
Un sistem de funcții booleene se numește funcțional complet. dacă o funcție booleană este reprezentată ca o suprapunere (o funcție complexă) a funcțiilor unui sistem dat.
Postulatul privind completitudinea funcțională. pentru ca sistemul de funcții să fie complet, este necesar și suficient ca acesta să nu fie inclus în niciuna dintre următoarele clase închise T0. T1. L, M și S.
Pentru a verifica completitudinea funcțională a unui sistem de funcții Boolean, se construiește un așa-numit tabel Post, în care sunt notate funcțiile aparținând clasei închise. Dacă există cel puțin un minus în fiecare coloană a tabelului Post, sistemul este complet, altfel nu este.
Exemplu 1. Verificați completitudinea funcțională a sistemului funcțional Boolean.
Verificăm dacă apar clasele închise ale funcției. Să construim tabelul de adevăr al acestei funcții:
Sistem de funcții Á formează un sistem complet, deoarece pentru fiecare dintre clasele Post din sistem există funcții care nu aparțin acestei clase. Sistem de funcții Á este o bază, deoarece este completă și, atunci când una dintre funcții este ștearsă, sistemul devine incomplet.
Exemplul 4. Determinați dacă sistemul complet de funcții F = și dacă acesta formează o bază.
x Ù oy
x Ù oy
Pentru x Ù oy:
4) Deoarece f (0,0) = f (1,1), prin urmare, funcția f (x Ù Yy) este monotonică;
5) Polinomul lui Zhegalkin: x + xy.
4) Deoarece f (0,0) 5) Polinomul lui Zhegalkin: x + y + xy. Sistemul de funcții este incomplet. Exemplul 5. Determinați dacă întregul sistem de funcții este: Se compilează o tabelă de adevăr pentru fiecare dintre aceste cinci funcții (pentru f2 și f4, tabelul poate fi alcătuit separat). Predictive și cuantificatori Fie A setul de obiecte de natură arbitrară (domeniul subiect al predicatului), predicatul n-loc este o mapare arbitrară Exemplul 1. Predicatul A (x) = "x ≤ 2" pe setul X = R este un singur. Predicatul B (x. Y) = "xy> 0" pe setul X = este două locuri. Dacă X =, atunci predicatul n-loc este o funcție booleană n-loc. Un predicat de ordin zero este o declarație. Deoarece valorile prescrise ale oricărui predicat se află în setul, predicatele pot produce toate operațiunile booleene și sunt cuprinse toate cunoscute proprietățile operațiilor logice pentru predicate. Luați în considerare aceste proprietăți (pentru confort, predicatele dintr-un loc sunt scrise în proprietăți): 6. Legea excluderii celui de-al treilea: P (x) P (x) = 1. 8. Legile lui de Morgan: 9. Proprietățile operațiilor cu constante logice: Pentru predicate se definesc operații de tip special, numite cuantificatoare. Fie n un predicat n-loc pe X. Indicăm că A este o proprietate a lui A. și să fim una dintre variabile. Apoi, înregistrarea înseamnă că pentru toate valorile variabilei, proprietatea A este satisfăcută. Simbolul este numit cuantificatorul universalității (comunității). Predicatul este valabil (n-1). Depinde de variabile. Dacă este dat un predicat unic P (x), atunci instruciunea xP (x) este un predicat de ordin zero, adică o declarație adevărată sau falsă. Pentru un predicat n-local pe un set X și o variabilă, scrierea înseamnă că există o valoare a variabilei. pentru care proprietatea A este satisfăcută. Simbolul este numit cuantificatorul existenței. Predicatul este (n-1) - loc, depinde de variabile. pentru predicatul unic P (x), afirmația xP (x) este un predicat de ordin zero, adică o declarație adevărată sau falsă. Exemplul 2. Predicatul A (x) = "x ≤2" este dat pe setul X = R. Instrucțiunea x (x ≤ 2) este falsă, x (x ≤ 2) este adevărată. Notația xA (xA) nu implică faptul că formula A are o variabilă x. Variabila x este numită variabila în cuantificator. și A este intervalul cuantificatorului. Există echivalențe: Predicatul este identic adevărat (identic fals). dacă pentru toate valorile posibile ale variabilelor ia valoarea 1 (0). Teza este un predicat unic definit pe setul N. - "există un x. pentru care este adevărat "- o afirmație adevărată; - "pentru toate x este adevărat" este o declarație falsă. Propoziția este un predicat cu două locuri definit pe setul A. Un predicat se numește executabil. dacă pentru unele valori ale variabilelor este valabilă valoarea. Exemplu 4. Găsiți sensul afirmației. Un predicat cu trei locuri este definit pe setul N. Soluție: Fie = 1. Echivalența este valabilă dacă și numai dacă pentru unii. și predicatul este identic în ceea ce privește y. că este, declarația originală este adevărată. Fie A o formulă, o variabilă care intră în formula A (una sau mai multe ori). Se spune că o intrare în A este conectată. dacă fie este o variabilă în cuantificator, fie este în intervalul cuantificatorului. Dacă apariția în A nu este conectată, atunci se numește liberă. În formula, aparițiile ambelor variabile sunt libere, în formula, apariția variabilei x este conectată, iar apariția variabilei y este liberă. Pentru fiecare predicat A, domeniul adevărului este setul Y = x X. A (x) = 1> pe care predicatul preia valoarea 1. Setul de adevăr al predicatului, Pentru predicatul A (x) = "x ≤ 2" pe setul X = domeniul adevărului este setul Y = x R, x ≤ 2>. Pentru domeniul adevărului de intersecție și unire a predicatelor, următoarele relații sunt adevărate: Următoarea teză înseamnă: - „este adevărat pentru toți m: m este împărțit de n» sau «orice număr pozitiv non-zero, împărțit la n» - un singur predicat depinde de n. un predicat executabil, domeniul adevărului său este n = 1>, deoarece toate numerele sunt divizibile cu 1; - „există m, următoarele afirmații: m este împărțit de n“ sau „există un număr pozitiv de zero, care este divizibil cu cealaltă naturală nenulă număr“ - un singur predicat depinde de n. adevăratul predicat este identic, domeniul adevărului său este A; - "pentru toate n este adevărat: m este divizibil prin n" sau "un număr natural non-zero este divizibil de orice număr natural nenulul" - un predicat unic, depinde de m. un predicat identic, domeniul adevărului său este un set gol; - "există un n. pentru care este adevărat: m este divizibil cu n "sau" un număr natural nenulul este divizibil de un număr natural diferit de zero "- un predicat unic depinde de m. adevăratul predicat este identic, domeniul adevărului său este A. 1. Identificați predicatele, pentru fiecare predicat, setați localitatea și domeniul adevărului dacă X = R. Pentru predicatele de două poziții, reprezentați domeniul adevărului grafic. 2) Pentru x = 0, egalitatea x - 2 = 0; 5) numărul unic x este simplu.
Articole similare
Trimiteți-le prietenilor: