Teorema de absorbție scrisă sub două forme – disjunctive şi

conjunctiv, respectiv:

A + AB \u003d A (16)

A(A + B)=A (17)

Să demonstrăm prima teoremă. Să scoatem litera A din paranteze:

DAR + AB \u003d A (1 + B)

Conform teoremei (3) 1 + B = 1, prin urmare

A(1 + B) = A 1 = A

Pentru a demonstra a doua teoremă, extindem parantezele:

A(A + B) = A A + AB = A + AB

Rezultatul este o expresie care tocmai a fost dovedită.

Să luăm în considerare câteva exemple de aplicare a teoremei de absorbție pentru

simplificarea formulelor booleene.

Teorema de lipire are de asemenea două forme – disjunctive şi

conjunctivala:

Să demonstrăm prima teoremă:

deoarece conform teoremelor (5) și (4)

Pentru a demonstra a doua teoremă, deschidem parantezele:

Conform teoremei (6), deci:

Conform teoremei de absorbție (16) A + AB \u003d A

Teorema de absorbție, ca și teorema de lipire, se aplică la simplificare

formule booleene, de exemplu:

teorema lui De Morgan leagă toate cele trei operații de bază ale algebrei booleene

Disjuncția, conjuncția și inversiunea:

Prima teoremă se arată în felul următor: inversarea unei conjuncții este o disjuncție

inversiuni. În al doilea rând, inversarea unei disjuncții este conjuncția inversiilor. Puteți demonstra teoremele lui Morgan folosind tabele de adevăr pentru părțile din stânga și din dreapta.

Teorema lui De Morgan se aplică și la Mai mult variabile:

Cursul 5

Inversa expresii complexe

Teorema lui De Morgan se aplică nu numai conjuncțiilor simple

sau disjuncții, dar și la expresii mai complexe.

Să găsim inversul expresiei AB + CD , reprezentată ca o disjuncţie a conjuncţiilor. Inversarea va fi considerată completă dacă semnele negative sunt doar deasupra variabilelor. Să introducem notația: AB = X;

CD=Y apoi

Găsiți și înlocuiți în expresia (22):

În acest fel:

Luați în considerare o expresie prezentată sub formă conjunctivă:

(A + B) (C + D)

Să găsim inversarea ei în formă

Să introducem notația: A + B = X; C + D \u003d Y, apoi

Găsiți și înlocuiți-le în expresie

În acest fel:

Când inversați expresii complexe, puteți folosi următoarea regulă. Pentru a găsi inversiunea, este necesar să înlocuiți semnele de conjuncție cu semne de disjuncție și semnele de disjuncție cu semne de conjuncție și să puneți inversiuni peste fiecare variabilă:

Conceptul unei funcții booleene

LAîn cazul general, o funcție (lat. functio - performanță, conformitate,

maparea) este o anumită regulă (lege), conform căreia fiecare element al mulțimii X, care este domeniul de variabilă independentă X, i se atribuie un anumit element al multimii F,

care este înțeles ca interval de valori ale variabilei dependente f . În cazul funcţiilor booleene X=F = (0,1). Regula prin care este specificată funcția poate fi orice formulă booleană, de exemplu:

Simbol f aici este o funcție care este, ca și argumentele lui A, B, C, variabilă binară.

Argumentele sunt variabile independente, pot lua orice valoare - fie 0, fie 1. Funcția f - variabilă dependentă. Semnificația sa este complet determinată de valorile variabilelor și de conexiunile logice dintre ele.

caracteristica principală funcția: pentru a-i determina valoarea, în general, este necesar să se cunoască valorile tuturor argumentelor de care depinde. De exemplu, funcția de mai sus depinde de trei argumente A, V, S. Dacă luăm A = 1, atunci obținem

adică, se obține o nouă expresie, care nu este egală nici cu zero, nici cu

unitate. Lasă acum LA= 1. Apoi

adică, în acest caz, nu se știe dacă funcția este egală cu zero sau cu unu.

În sfârșit, să luăm DIN= 0. Atunci obținem: f = 0. Astfel, dacă luăm A = 1 în expresia originală, LA= 1, DIN = 0, atunci funcția va lua o valoare zero: f= 0.

Considera noţiunea de set de valori variabile .

Dacă tuturor argumentelor de care depinde funcția li se atribuie anumite valori, atunci se vorbește despre un set de valori ale argumentului care poate fi

numiți-i doar un set. Setul de valori ale argumentului este o secvență de zerouri și unu, de exemplu, 110, unde prima cifră corespunde primului argument, a doua celui de-al doilea și a treia celui de-al treilea. Evident, este necesar să fim de acord în prealabil care este primul, al doilea sau, să zicem, al cincilea argument. Pentru a face acest lucru, este convenabil să utilizați aranjarea alfabetică a literelor.

De exemplu, dacă

apoi conform alfabetului latin primul argument este R, al doilea -

Q, al treilea - X, al patrulea - U. Apoi, după setul de valori ale argumentelor, este ușor

găsiți valoarea funcției. Să fie dat, de exemplu, setul 1001. Conform lui

înregistrează, adică pe setul 1001, funcția dată este egală cu unu.

Rețineți din nou că setul de valori ale argumentului este setul

zerouri și unu. Numerele binare sunt, de asemenea, seturi de zerouri și unu.

Acest lucru ridică întrebarea - se pot considera seturile ca fiind binare

numere? Este posibil și, în multe cazuri, este foarte convenabil, mai ales dacă este binar

convertiți numărul în zecimală. De exemplu, dacă

A = 0, B = 1, C = 1, D = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

adică, mulțimea dată are numărul 6 în zecimală.

Dacă doriți să găsiți valorile argumentelor după număr zecimal, atunci

acționăm în ordine inversă: mai întâi, traducem numărul zecimal în binar, apoi adăugăm atâtea zerouri în stânga, astfel încât numărul total biți a fost egal cu numărul de argumente, după care găsim valorile argumentelor.

Să fie, de exemplu, să se găsească valorile argumentelor A, B, C, D, E, F prin multimea cu numarul 23. Convertim numarul 23 in sistem binar folosind metoda

împărțirea la doi:

Ca rezultat, obținem 23 10 = 10111 2 . Acesta este un număr de cinci cifre și în total

Există șase argumente, prin urmare, în stânga trebuie scris un zero:

23 10 = 010111 2 . De aici găsim:

A = 0, B = 1, C = 0, D = 1, E = 1, F = 1.

Câte seturi există dacă numărul este cunoscut P argumente? Evident, câte numere binare de n biți sunt, adică 2 n

Cursul 6

Setarea unei funcții booleene

Știm deja un fel. Este analitică, adică sub forma unei expresii matematice folosind variabile binare și operații logice. În plus, există și alte modalități, dintre care cel mai important este tabelul. Tabelul listează toate seturile posibile de valori ale argumentelor și pentru fiecare set este indicată valoarea funcției. Un astfel de tabel se numește tabel de corespondență (adevăr).

Pe exemplul funcției

Să ne dăm seama cum să construim un tabel de căutare pentru acesta.

Funcția depinde de trei argumente A, B, C. Prin urmare, în tabel

furniza trei coloane pentru argumentele A,B,Cși o coloană pentru valorile funcției f. În stânga coloanei A, este util să plasați o altă coloană. Vom scrie în el numere zecimale, care corespund mulțimilor, dacă le considerăm numere binare de trei cifre. Această zecimală

coloana este introdusă pentru confortul lucrului cu tabelul, prin urmare, în principiu,

poate fi neglijat.

Completam tabelul. Rândul cu numărul LLC arată:

A = B = C = 0.

Să definim valoarea funcției pe acest set:

În coloana f scriem zero pe linia cu mulțimea 000.

Următorul set: 001, adică e. A = B = 0, C = 1. Aflați valoarea funcției

pe acest set:

Pe setul 001, funcția este egală cu 1, prin urmare, în coloana f în linia cu

numărul 001 notăm unitatea.

În mod similar, calculăm valorile funcțiilor pe toate celelalte seturi și

completează întregul tabel.

Asociativitatea

x 1 (x 2 x 3) \u003d (x 1 x 2) x 3;

x 1 Ú (x 2 Ú x 3) \u003d (x 1 Ú x 2) Ú x 3.

comutativitatea

x 1 x 2 = x 2 x 1

x 1 Ú x 2 = x 2 Ú x 1

Distributivitatea conjuncției în raport cu disjuncția

x 1 (x 2 Ú x 3) \u003d x 1 x 2 Ú x 1 x 3.

Distributivitatea disjuncției în raport cu conjuncția

x 1 Ú(x 2 × x 3) = (x 1 Úx 2) × (x 1 Úx 3). *

Idempotenta (tautologie)

De două ori nu

Proprietăți constante

x & 1 = x; (legile setului universal)

x & 0 = 0; (legi zero set)

Regulile (legile) lui Morgan

Legea contradicției (adiționalității)

Legea excluderii mijlocului (suplimentar)

Dovezile tuturor acestor formule sunt banale. Una dintre opțiuni este să construiți tabele de adevăr ale părților din stânga și din dreapta și să le comparați.

Reguli de lipire

Regula de lipire pentru conjuncțiile elementare rezultă din legea distributivă, legea complementarității și legea mulțimii universale: disjuncția a două conjuncții adiacente poate fi înlocuită cu o conjuncție elementară, care este o parte comună a conjuncțiilor originale .

Regula de lipire pentru sumele elementare rezultă din legea distributivă de al doilea fel, legea complementarității și legea setării zero: conjuncția a două disjuncții adiacente poate fi înlocuită cu o disjuncție elementară, care este o parte comună a disjuncțiilor originale .

Regula de absorbție

Regula de absorbție pentru suma a două produse elementare rezultă din legea distributivă a primului fel și legile mulțimii universale: disjuncția a două conjuncții elementare, dintre care una este parte integrantă altul, poate fi înlocuit cu o conjuncție cu mai puțini operanzi .

Regula de absorbție pentru produsul sumelor elementare rezultă din legea distributivă de al doilea fel și legile zeroului: conjuncția a două disjuncții elementare, dintre care una este un constituent al celeilalte, poate fi înlocuită cu o disjuncție elementară având mai puțini operanzi.

Regula de implementare

Această regulă definește acțiunea inversă a lipirii.

Regula pentru extinderea unui produs elementar într-o sumă logică de produse elementare de rang superior (în limita până la r = n, adică până la constituenții unității, așa cum se va discuta mai jos) rezultă din legile mulțimii universale. , legea distributivă de primul fel și se realizează în trei etape:

Produsul elementar al rangului r de dezvoltat este introdus ca factori unități n-r, unde n este rangul constituenților unității;

Fiecare unitate este înlocuită cu suma logică a unei variabile care nu este prezentă în produsul elementar original și negația acestuia: x i v `x i = 1;

Toate parantezele sunt extinse pe baza unei legi distributive de primul fel, care duce la extinderea produsului elementar original al rangului r într-o sumă logică de 2 constituenți unitari n-r.

Regula elementară de extindere a produsului este utilizată pentru a minimiza funcțiile de algebră logică (FAL).

Regula pentru extinderea unei sume elementare de rang r la un produs al sumelor elementare de rang n (constituent zero) urmează legile lor ale mulțimii zero (6) și legea distributivă de al doilea fel (14) și se realizează în trei etape:

În suma extensibilă a rangului r introducem ca sumanzi n-r zerouri;

Fiecare zero este reprezentat ca un produs logic al unei variabile care nu este prezentă în suma inițială și negația acesteia: x i·` x i = 0;

Expresia rezultată este transformată pe baza legii distributive de al doilea fel (14) în așa fel încât suma inițială a rangului r să se desfășoare într-un produs logic de 2 n-r constituenți zero.

16. Conceptul de sistem complet. Exemple de sisteme complete (cu dovezi)

Definiție. Se numește mulțimea de funcții ale algebrei logice A sistem complet(în P2) dacă orice funcție a algebrei logicii poate fi exprimată printr-o formulă peste A.

Sistemul de funcții A=( f 1 , f 1 ,…, f m) care este complet este numit bază.

O bază minimă este o astfel de bază pentru care este eliminată cel puțin o funcție f1, care formează această bază, transformă sistemul de funcții (f 1 , f 1 ,…, f m)în incomplet.

Teorema. Sistemul A = (∨, &, ) este complet.

Dovada. Dacă funcția algebrică logică f nu este identic zero, atunci f este exprimată ca o formă normală disjunctivă perfectă, care include doar disjuncția, conjuncția și negația. Dacă f ≡ 0, atunci f = x & x . Teorema a fost demonstrată.

Lema. Dacă sistemul A este complet și orice funcție a sistemului A poate fi exprimată printr-o formulă peste un alt sistem B, atunci B este, de asemenea, un sistem complet.

Dovada. Considerăm o funcție arbitrară a algebrei logice f (x 1 , …, x n) și două sisteme de funcții: A = (g 1 , g 2 , …) și B = (h 1 , h 2 , …). Datorită faptului că sistemul A este complet, funcția f poate fi exprimată sub formă de formulă peste el:

f (x 1 , …, x n) = ℑ

unde g i = ℜ i

adică funcţia f este reprezentată ca

f (x 1 , …, x n)=ℑ[ℜ1,ℜ2,...]

cu alte cuvinte, poate fi reprezentat printr-o formulă peste B. Enumerând în acest fel toate funcțiile algebrei logicii, obținem că și sistemul B este complet. Lema este dovedită.

Teorema. Următoarele sisteme sunt complete în P 2:

4) (&, ⊕ , 1) baza Zhegalkin.

Dovada.

1) Se știe (Teorema 3) că sistemul A = (&, V, ) este complet. Să arătăm că sistemul B = ( V, . Într-adevăr, din legea de Morgan (x& y) = (x ∨ y) obținem că x & y = (x ∨ y) , adică conjuncția se exprimă prin disjuncția și negația, iar toate funcțiile sistemului A sunt exprimate prin formule peste sistemul B. Conform lemei, sistemul B este complet.

2) Similar cu itemul 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) iar lema 2 implică adevărul itemului 2.

3) x | y=(x&y), x | x = x; x & y = (x | y) = (x | y) | (x | y) iar după Lema 2 sistemul este complet.

4) x = x ⊕1 și conform Lemei 2 sistemul este complet.

Teorema a fost demonstrată.

17. Algebra lui Zhegalkin. Proprietățile operaționale și caracterul complet

Setul de funcții booleene definite în baza Zhegalkin S4=(⊕,&,1) se numește algebra Zhegalkin.

Proprietăți de bază.

1. comutativitatea

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. asociativitatea

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. distributivitatea

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. proprietăți constante

5. h⊕h=0 h&h=h
Afirmație. Prin operațiile algebrei Zhegalkin, toate celelalte funcții booleene pot fi exprimate:

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

18. Polinomul Zhegalkin. Metode de construcție. Exemplu.

Polinomul Zhegalkin (polinomul modulo 2) din n variabilele x 1 ,x 2 ... x n se numește expresie de forma:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n ,

unde constantele C k pot lua valorile 0 sau 1.

Dacă polinomul Zhegalkin nu conține produse ale variabilelor individuale, atunci se numește liniar (funcție liniară).

De exemplu, f=x⊕yz⊕xyz și f 1 =1⊕x⊕y⊕z sunt polinoame, acestea din urmă fiind o funcție liniară.

Teorema. Fiecare funcție booleană este reprezentată ca un polinom Zhegalkin într-un mod unic.

Să prezentăm principalele metode de construire a polinoamelor Zhegalkin ale unei funcții date.

1. Metoda coeficienților nedeterminați. Fie P(x 1 ,x 2 ... x n) polinomul Zhegalkin necesar realizând pentru această funcție f(x 1 ,x 2 ... x n). O scriem sub formă

P=c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Să găsim coeficienții C k . Pentru a face acest lucru, dăm secvenţial variabilelor x 1 ,x 2 ... x n valori din fiecare rând al tabelului de adevăr. Ca rezultat, obținem un sistem de 2 n ecuații cu 2 n necunoscute, care are singura decizie. Rezolvând-o, găsim coeficienții polinomului P(X 1 ,X 2 ... X n).

2. O metodă bazată pe transformarea formulelor peste un set de conjunctive (,&). Construiește o formulă F peste mulţimea legăturilor (,&) realizând funcţia dată f(X 1 ,X 2 ... X n). Apoi înlocuim peste tot subformulele de forma A cu A⊕1, deschidem parantezele folosind legea distributivă (vezi proprietatea 3), apoi aplicăm proprietățile 4 și 5.

Exemplu. Construiți polinomul Zhegalkin al funcției f(X,Y)=X→Y

Soluţie.
1. (metoda coeficienților incerti). Scriem polinomul dorit sub forma:

P=c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Folosind tabelul de adevăr al implicației, obținem asta

f(0,0)=P(0,0)=C0 =1

f(0,1)=P(0,1)=C 0 ⊕C 2 =1

f(1,0)=P(1,0)=C 0 ⊕C 1 =0

f(1,1)=P(1,1)=C 0 ⊕C 1 ⊕C 2 ⊕C 12 =1

De unde găsim succesiv, C 0 =1, C 1 =1, C 2 =0, C 12 =1

Prin urmare: x→y=1⊕X⊕XY.

2. (Metoda de conversie a formulelor.). Avem: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Rețineți că avantajul algebrei Zhegalkin (comparativ cu alte algebre) este aritmetizarea logicii, ceea ce face posibilă efectuarea transformărilor funcțiilor booleene destul de simplu. Dezavantajul său în comparație cu algebra booleană este greutatea formulelor.

Informații similare.

Legile lui De Morgan sunt reguli logice stabilite de matematicianul scoțian Augustus de Morgan care conectează perechi de operații logice folosind negația logică.

Augustus de Morgan a observat că următoarele relații sunt adevărate în logica clasică:

nu (A și B) = (nu A) sau (nu B)

nu (A sau B) = (nu A) și (nu B)

Într-o formă mai familiară pentru noi, aceste rapoarte pot fi scrise în următoarea formă:

Legile lui De Morgan pot fi formulate după cum urmează:

Legea lui I de Morgan: Negația disjuncției a două enunțuri simple este echivalentă cu conjuncția negațiilor acestor enunțuri.

Legea lui II de Morgan: Negația conjuncției a două enunțuri simple este echivalentă cu disjuncția negațiilor acestor enunțuri.

Luați în considerare aplicarea legilor lui de Morgan pe exemple specifice.

Exemplul 1 Transformați formula astfel încât să nu existe negații ale enunțurilor complexe.

Să folosim prima lege a lui de Morgan, obținem:

aplicăm a doua lege a lui de Morgan la negația conjuncției afirmațiilor simple B și C, obținem:

,

prin urmare:

.

Ca urmare, am obținut o declarație echivalentă în care nu există negații de enunțuri compuse, iar toate negațiile se referă doar la afirmații simple.

Puteți verifica validitatea soluției folosind tabele de adevăr. Pentru a face acest lucru, compilam tabele de adevăr pentru afirmația originală:

iar pentru afirmația obținută ca urmare a transformărilor efectuate folosind legile lui de Morgan:

.

Tabelul 1.

După cum vedem din tabele, afirmația logică originală și afirmația logică obținută cu ajutorul legilor lui de Morgan sunt echivalente. Acest lucru este dovedit de faptul că în tabelele de adevăr avem aceleași seturi de valori.

Formule și legile logicii

Într-o lecție introductivă despre Fundamentele logicii matematice, ne-am familiarizat cu conceptele de bază ale acestei secțiuni de matematică, iar acum subiectul primește o continuare firească. Pe lângă noul material educațional teoretic, sau mai degrabă nu teoretic - ci general, așteptăm sarcini practice, și de aceea dacă ați ajuns la această pagină dintr-un motor de căutare și/sau sunteți prost orientat în material, atunci vă rugăm să urmați linkul de mai sus și să începeți de la articolul anterior. În plus, pentru practică avem nevoie de 5 tabele de adevăr operatii logice pe care eu recomand cu caldura rescrie manual.

NU ține minte, NU tipări, și anume, înțelegi și rescrie din nou pe hârtie cu propria ta mână - astfel încât să fie în fața ochilor tăi:

– masa NU;
- tabelul I;
– masa SAU;
– tabel de implicare;
- Tabel de echivalență.

Este foarte important. In principiu, ar fi convenabil sa le numerotati „Tabelul 1”, „Tabelul 2”, etc., dar am subliniat în mod repetat defectul acestei abordări - după cum se spune, într-o sursă tabelul va fi primul, iar în cealaltă - o sută primul. Prin urmare, vom folosi nume „naturale”. Noi continuăm:

De fapt, ești deja familiarizat cu conceptul de formulă logică. Voi da un standard, dar mai degrabă spiritual definiție: formule algebrele propoziționale se numesc:

1) orice afirmații elementare (simple);

2) dacă și sunt formule, atunci formulele sunt și expresii ale formei
.

Nu există alte formule.

În special, o formulă este orice operație logică, cum ar fi înmulțirea logică. Acordați atenție celui de-al doilea punct - permite recursiv mod de a „crea” o formulă arbitrar lungă. Pentru că sunt formule, atunci este și o formulă; întrucât și sunt formule, atunci - de asemenea o formulă etc. Orice afirmație elementară (din nou prin definitie) poate introduce formula de mai multe ori.

Formulă nu este, de exemplu, o înregistrare - și aici există o analogie evidentă cu „gunoaiele algebrice”, din care nu este clar dacă numerele trebuie adăugate sau înmulțite.

Formula logică poate fi gândită ca functie logica. Să scriem aceeași conjuncție în formă funcțională:

Enunțurile elementare în acest caz joacă și rolul de argumente (variabile independente), care în logica clasică pot lua 2 valori: Adevărat sau Fals. În cele ce urmează, pentru comoditate, voi numi uneori afirmații simple variabile.

Tabelul care descrie formula logică (funcția) se numește, așa cum sa menționat deja, tabelul de adevăr. Vă rog - o imagine familiară:

Principiul formării tabelului de adevăr este următorul: „la intrare” trebuie să enumerați toate combinațiile posibile adevăruri și minciuni pe care propozițiile (argumentele) elementare le pot accepta. În acest caz, formula include două afirmații și este ușor de aflat că există patru astfel de combinații. „La ieșire”, obținem valorile logice corespunzătoare ale întregii formule (funcție).

Trebuie să spun că „ieșirea” aici s-a dovedit a fi „într-un singur pas”, dar în cazul general formula logică este mai complexă. Și în astfel de „cazuri dificile” este necesar să se observe ordinea executării operaţiilor logice:

- se execută mai întâi negația;
- în al doilea rând - conjuncție;
- apoi - disjuncție;
- apoi implicatia ;
- și, în sfârșit, cea mai mică prioritate are echivalentul.

Deci, de exemplu, intrarea implică că mai întâi trebuie să efectuați înmulțirea logică, apoi - adunarea logică:. La fel ca în algebra „obișnuită” - „întâi înmulțim, apoi adunăm”.

Ordinea acțiunilor poate fi schimbată în mod obișnuit - paranteze:
- aici, în primul rând, se realizează disjuncția și abia apoi o operație mai „puternică”.

Probabil că toată lumea înțelege, dar pentru orice caz un pompier: și asta două diferite formule! (atât din punct de vedere formal, cât și din punct de vedere material)

Să facem un tabel de adevăr pentru formulă. Această formulă include două declarații elementare și „la intrare” trebuie să enumerăm toate combinațiile posibile de unu și zero. Pentru a evita confuziile și inconsecvențele, suntem de acord să enumeram combinații strict în această ordine (pe care de fapt îl folosesc de facto de la bun început):

Formula include două operații logice, iar în funcție de prioritatea lor, în primul rând, trebuie să efectuați negare declarații. Ei bine, anulăm coloana „pe” - transformăm unitățile în zerouri și zerourile în unități:

În al doilea pas, ne uităm la coloane și le aplicăm SAU operare. Privind puțin înainte, voi spune că disjuncția este permutabilă (si sunt acelasi lucru), și, prin urmare, coloanele pot fi analizate în ordinea obișnuită - de la stânga la dreapta. Când efectuați adunări logice, este convenabil să utilizați următorul raționament aplicat: „Dacă sunt două zerouri, punem zero, dacă măcar o unitate, punem una”:

Tabelul adevărului este construit. Și acum să ne amintim de vechea implicație bună:

…atent-atent… uită-te la ultimele coloane…. În algebra propozițională, astfel de formule sunt numite echivalent sau identic:

(trei linii orizontale sunt pictograma de identitate)

În prima parte a lecției, am promis că voi exprima implicația prin operații logice de bază, iar împlinirea promisiunii nu a întârziat să apară! Cei care doresc pot pune un sens semnificativ implicației (de exemplu, „Dacă plouă, afară este umed”)și analizează independent afirmația echivalentă.

Să formulăm definiție generală: cele două formule se numesc echivalent (identic), dacă iau aceleași valori pentru orice set de valori incluse în aceste formule variabile (enunțuri elementare). Ei spun si asta „formulele sunt echivalente dacă tabelele lor de adevăr sunt aceleași”, dar nu prea îmi place această frază.

Exercitiul 1

Faceți un tabel de adevăr pentru formula și asigurați-vă că identitatea pe care o cunoașteți este adevărată.

Să repetăm ​​procedura de rezolvare a problemei:

1) Deoarece formula include două variabile, vor exista 4 seturi posibile de zerouri și unu în total. Le notăm în ordinea specificată mai sus.

2) Implicațiile sunt „mai slabe” decât conjuncțiile, dar sunt situate între paranteze. Completam coloana, deși este convenabil să folosim următorul raționament aplicat: „dacă zero urmează de la unu, atunci punem zero, în toate celelalte cazuri - unu”. Apoi, completați coloana pentru implicația și, în același timp, Atenţie!– coloane și ar trebui analizate „de la dreapta la stânga”!

3) Și în etapa finală, completați coloana finală. Și aici este convenabil să argumentezi astfel: „dacă sunt două în coloane, atunci punem una, în toate celelalte cazuri - zero”.

Și, în sfârșit, verificăm tabelul de adevăr echivalențe .

Echivalențe de bază ale algebrei propoziționale

Tocmai ne-am întâlnit pe doi dintre ei, dar problema, desigur, nu se limitează la ei. Există destul de multe identități și le voi enumera pe cele mai importante și mai faimoase dintre ele:

Comutativitatea conjuncției și comutativitatea disjuncției

comutativitatea este o permutare:

Familiar din regulile clasei I: „Dintr-o rearanjare a factorilor (termenilor), produsul (suma) nu se modifică”. Dar, cu toată elementaritatea aparentă a acestei proprietăți, este departe de a fi întotdeauna adevărată, în special, este necomutativă. înmulțirea matriceală (în general, nu pot fi rearanjate), A produs încrucișat al vectorilor– anticomutativ (permutarea vectorilor implică o schimbare de semn).

Și în plus, aici vreau să subliniez din nou formalismul logicii matematice. Deci, de exemplu, fraze „Elevul a promovat examenul și a băut”și „Elevul a băut și a promovat examenul” diferit din punct de vedere al conținutului, dar imposibil de distins din punctul de vedere al adevărului formal. ... Fiecare dintre noi cunoaște astfel de studenți, iar din motive etice nu vom numi nume specifice =)

Asociativitatea înmulțirii și adunării logice

Sau, dacă „stil de școală” este o proprietate asociativă:

Proprietăți de distribuție

Vă rugăm să rețineți că în al 2-lea caz va fi incorect să vorbiți despre „deschiderea parantezelor”, într-un sens, aici este o „ficțiune” - la urma urmei, acestea pot fi eliminate cu totul: înmulțirea este o operație mai puternică.

Și din nou, aceste proprietăți aparent „banale” sunt departe de a fi satisfăcute în toate sistemele algebrice și, în plus, necesită dovezi. (despre care vom vorbi foarte curând). Apropo, a doua lege distributivă nu este valabilă nici măcar în algebra noastră „obișnuită”. Și într-adevăr:

Legea idempotentei

Ce să faci, latină....

Doar un principiu al unui psihic sănătos: „Eu și eu sunt eu”, „Eu sau eu sunt și eu” =)

Și iată câteva identități similare:

... ei bine, ceva chiar am închis... așa că mâine te poți trezi cu un doctorat =)

Legea dublei negații

Ei bine, aici exemplul cu limba rusă deja sugerează de la sine - toată lumea știe foarte bine că două particule „nu” înseamnă „da”. Și pentru a îmbunătăți culoarea emoțională a negării, trei „nu” sunt adesea folosite:
- chiar și cu o mică dovadă că a funcționat!

Legile de absorbție

- A fost un băiat? =)

În identitatea corectă, parantezele pot fi omise.

legile lui De Morgan

Să presupunem că un profesor strict (al cărui nume îl știi și tu :)) pune un examen dacă - Elevul a răspuns la prima întrebare și – Elevul a răspuns la a 2-a întrebare. Apoi declarația care spune că Student nu a trecut examenul, va fi echivalent cu afirmația - Student nu a raspuns la prima intrebare sau la a 2-a întrebare.

După cum sa menționat mai sus, echivalențele sunt supuse dovezilor, care sunt efectuate în mod standard folosind tabele de adevăr. De fapt, am demonstrat deja echivalențele care exprimă implicația și echivalența, iar acum este timpul să reparăm tehnica de rezolvare a acestei probleme.

Să dovedim identitatea. Deoarece include o singură instrucțiune, atunci sunt posibile doar două opțiuni „la intrare”: una sau zero. Apoi, atribuim o singură coloană și le aplicăm regulă ȘI:

Ca urmare, „la ieșire” se obține o formulă, al cărei adevăr coincide cu adevărul enunțului. Echivalența a fost dovedită.

Da, această dovadă este primitivă (și cineva va spune că este „prost”), dar un profesor tipic de logică de matematică îi va zgudui sufletul pentru el. Prin urmare, chiar și astfel de lucruri simple nu trebuie tratate cu dispreț.

Acum să ne asigurăm, de exemplu, de validitatea legii lui de Morgan.

Mai întâi, să creăm un tabel de adevăr pentru partea stângă. Deoarece disjuncția este între paranteze, în primul rând o executăm, după care negăm coloana:

Apoi, alcătuim un tabel de adevăr pentru partea dreaptă. Și aici totul este transparent - în primul rând, efectuăm mai multe negative „puternice”, apoi aplicăm coloanelor regulă ȘI:

Rezultatele s-au potrivit, astfel încât identitatea este dovedită.

Orice echivalență poate fi reprezentată ca formulă identică adevărată. Înseamnă că PENTRU ORICE set inițial de zerouri și unu„la ieșire” se obține strict unitate. Și există o explicație foarte simplă pentru aceasta: deoarece tabelele de adevăr și coincid, atunci, desigur, ele sunt echivalente. Să combinăm, de exemplu, părțile din stânga și din dreapta ale identității de Morgan tocmai dovedite prin echivalență:

Sau, mai compact:

Sarcina 2

Demonstrați următoarele echivalențe:

b)

Scurtă soluție la sfârșitul lecției. Să nu fim leneși! Încercați nu numai să faceți tabele de adevăr, ci și clar formula concluzii. După cum am observat recent, neglijarea lucrurilor simple poate fi foarte, foarte costisitoare!

Continuăm să ne familiarizăm cu legile logicii!

Da, absolut corect - lucrăm deja cu ei cu putere și principal:

Adevărat la , se numește formulă identică adevărată sau legea logicii.

În virtutea tranziției justificate anterior de la echivalență la formula identic adevărată, toate identitățile enumerate mai sus sunt legile logicii.

Formula care ia o valoare Minciună la orice set de valori ale variabilelor incluse în acesta, se numește formulă identică falsă sau contradicţie.

Un exemplu de contradicție de la grecii antici:
Nicio afirmație nu poate fi adevărată și falsă în același timp.

Dovada este banala:

„Ieșire” a primit exclusiv zerouri, prin urmare, formula este într-adevăr identic fals.

Cu toate acestea, orice contradicție este și o lege a logicii, în special:

Este imposibil să acoperim un subiect atât de vast într-un singur articol și, prin urmare, mă voi limita la doar câteva legi:

Legea mijlocului exclus

- în logica clasică, orice afirmație este adevărată sau falsă și nu există a treia cale. "A fi sau a nu fi aceasta este intrebarea.

Fă-ți propriul tabel de adevăr și asigură-te că este identic adevărat formulă.

Legea contrapoziției

Această lege a fost exagerată în mod activ când am discutat despre esență conditie necesara, tine minte: „Dacă afară este umed în timpul ploii, atunci rezultă că dacă afară este uscat, atunci cu siguranță nu a plouat”.

Din această lege mai rezultă că dacă echitabil este Drept teorema, apoi afirmația, care se numește uneori opus teorema.

Daca e adevarat verso teoremă, atunci, în virtutea legii contrapoziției, este valabilă și teorema, invers invers:

Și să revenim la exemplele noastre semnificative: pentru enunțuri - un număr este divizibil cu 4, - un număr este divizibil cu 2 corect Dreptși opus teoreme, dar false versoși invers invers teoreme. Pentru formularea „adultă” a teoremei lui Pitagora, toate cele 4 „direcții” sunt adevărate.

Legea silogismului

De asemenea, un clasic al genului: „Toți stejarii sunt copaci, toți copacii sunt plante, de aceea toți stejarii sunt plante”.

Ei bine, din nou aș dori să notez formalismul logicii matematice: dacă Profesorul nostru strict crede că un anumit Student este un stejar, atunci din punct de vedere formal, acest Student este cu siguranță o plantă =) ... deși, dacă te gandesti bine, poate fi si de la unul informal = )

Să facem un tabel de adevăr pentru formulă. În conformitate cu prioritatea operațiilor logice, respectăm următorul algoritm:

1) efectuați implicațiile și . În general, puteți executa imediat a treia implicație, dar este mai convenabil cu ea (și permis!) dă-ți seama puțin mai târziu

2) se aplică coloanelor regulă ȘI;

3) acum executăm;

4) iar la etapa finală aplicați implicația la coloane și .

Simțiți-vă liber să controlați procesul cu degetele arătător și mijlociu :))


Din ultima coloană, cred că totul este clar fără comentarii:
, ceea ce urma să fie dovedit.

Sarcina 3

Aflați dacă următoarea formulă este o lege a logicii:

Scurtă soluție la sfârșitul lecției. Da, și aproape că am uitat - să fim de acord să enumeram seturile inițiale de zerouri și unu în exact aceeași ordine ca și în dovedirea legii silogismului. Bineînțeles, liniile pot fi rearanjate, dar acest lucru va face foarte dificil să se împace cu soluția mea.

Conversia formulelor booleene

Pe lângă scopul lor „logic”, echivalențele sunt utilizate pe scară largă pentru a transforma și simplifica formulele. În linii mari, o parte a identității poate fi schimbată cu alta. Deci, de exemplu, dacă întâlniți un fragment într-o formulă logică, atunci, conform legii idempotității, puteți (și ar trebui) să scrieți simplu în locul lui. Dacă vedeți , atunci, conform legii absorbției, simplificați notația la . Si asa mai departe.

În plus, mai este unul lucru important: identitățile sunt valabile nu numai pentru propoziții elementare, ci și pentru formule arbitrare. De exemplu:

, unde sunt (oricât de complex doriți) formule.

Să transformăm, de exemplu, implicația complexă (prima identitate):

În continuare, aplicăm legea „complexă” de Morgan la paranteză, în timp ce, din cauza priorității operațiunilor, este legea , unde :

Parantezele pot fi eliminate, deoarece în interior există o conjuncție mai „puternică”:

Ei bine, cu comutativitatea, în general, totul este simplu - nici măcar nu trebuie să desemnați nimic ... ceva a pătruns în sufletul meu legea silogismului :))

Astfel, legea poate fi rescrisă într-o formă mai complicată:

Vorbește cu voce tare lanțul logic „cu un stejar, un copac, o plantă”, și vei înțelege că sensul de fond al legii nu s-a schimbat deloc din rearanjarea implicațiilor. Este că formularea a devenit mai originală.

Ca antrenament, simplificăm formula.

Unde sa încep? În primul rând, pentru a înțelege ordinea acțiunilor: aici negația se aplică unui întreg parantez, care este „fixat” cu enunțul printr-o conjuncție „puțin mai slabă”. În esență, avem în fața noastră produsul logic a doi factori: . Dintre cele două operațiuni rămase, implicarea are cea mai mică prioritate și, prin urmare, întreaga formulă are următoarea structură: .

De regulă, la primul pas (pașii) scăpați de echivalență și implicație (daca sunt)și reduceți formula la trei operații logice de bază. Ce pot sa spun…. Logic.

(1) Folosim identitatea . Și în cazul nostru.

Aceasta este de obicei urmată de „dezasamblarea” cu paranteze. Mai întâi toată soluția, apoi comentariile. Pentru a nu obține „ulei de unt”, voi folosi pictogramele de egalitate „obișnuite”:

(2) Aplicăm legea lui de Morgan la parantezele exterioare, unde .

Operațiile avute în vedere asupra mulțimilor sunt supuse unor legi, care amintesc de binecunoscutele legi elementare ale algebrei numerelor. Aceasta definește numele algebră setată, care este adesea numită algebră de mulțimi booleene, care este asociată cu numele matematicianului englez John Boole, care și-a bazat cercetările logice pe ideea unei analogii între algebră și logică.

Pentru mulțimile arbitrare A, B și C, următoarele identități sunt adevărate (Tabelul 3.1):

Tabelul 3.1

Legile algebrei mulțimilor în raport cu operațiile de intersecție () și unire () sunt supuse principiului dualității: dacă în orice lege toate semnele de intersecție sunt înlocuite cu semne de unire, iar toate semnele de unire sunt semne de intersecție , semnul universului (U) este înlocuit cu semnul unei mulțimi goale (Ø), iar semnul golului - semnul universului, apoi obținem din nou identitatea corectă. De exemplu (în virtutea acestui principiu), rezultă din etc.

3.1. Verificarea adevărului identităților folosind diagramele Euler-Venn

Toate legile algebrei mulțimilor pot fi reprezentate și demonstrate vizual folosind diagramele Euler-Venn. Pentru asta ai nevoie de:

Desenați diagrama corespunzătoare și umbriți toate seturile din partea stângă a ecuației.

Desenați o altă diagramă și faceți același lucru pentru partea dreaptă a ecuației.

Această identitate este adevărată dacă și numai dacă aceeași zonă este umbrită pe ambele diagrame.

Observație 3.1. Două cercuri care se intersectează împart întregul set universal în patru regiuni (vezi Fig. 3.1)

Observație 3.2. Trei cercuri care se intersectează împart întregul set universal în opt regiuni (vezi Fig. 3.2):

Observație 3.2. Când scrieți condițiile diferitelor exemple, se folosește adesea notația:

 - din ... rezultă ...;

 - dacă și numai dacă...

Sarcina 3.1 . Simplificați expresiile de algebră setată:

Soluţie.

O sarcină 3 .2 . Demonstrați identitățile:

(AB)\B = A\B;

A(BC) = A\(A\B)(A\C).

Soluţie.

Sarcina 3.3 . Demonstrați următoarele relații în două moduri: folosind diagrame și folosind definiția egalității mulțimilor.

Soluţie.

2. Dovada prin definiţia egalităţii mulţimilor.

Prin definiție, mulțimile X și Y sunt egale dacă sunt îndeplinite simultan următoarele relații: XY și YX.

Să arătăm mai întâi asta
. Lăsa X este un element arbitrar al multimii
, acesta este X
. Înseamnă că XU și X
. De aici rezultă că XA sau XB. În cazul în care un XAh, atunci XĀ, ceea ce înseamnă
. Dacă XB, atunci
, care înseamnă
. Astfel, fiecare element al setului.
. este, de asemenea, un element al setului
Acesta este

Demonstrăm acum invers, adică că
. Lăsa
. În cazul în care un XĀ, atunci XU și XA, ceea ce înseamnă XAB. De aici rezultă că
. Dacă
, apoi XU și XB. Mijloace, XAB, adică
. Rezultă că fiecare element al setului
este, de asemenea, un element al setului
, acesta este
.

Mijloace,
, ceea ce urma să fie dovedit.

A(BC) = (AB)(AC);

1. Demonstrați cu o diagramă:

Lăsa XA(BC). Apoi XA și XBC. În cazul în care un XB, atunci XAB, care nu contrazice cele spuse, ceea ce înseamnă că X(AB)(AC). Dacă XC, atunci XAC. Prin urmare, X(AB)(AC). Deci, am demonstrat că A(BC)  (AB)(AC.

Lasă acum X (AB)(AC). În cazul în care un XAB, atunci XA și XB. De aici rezultă că XA și XВС, adică XA(BC). Dacă XAC, atunci XA și XC. De aici rezultă că XA și XВС, adică XA(BC). Astfel, (AB)(AC) A(BC). Prin urmare, A(BC) = (AB)(AC). Q.E.D.

La demonstrarea suficienței, am obținut că АВ=. Este evident că С, deci relația este demonstrată. În dovadă a fost luat în considerare cazul cel mai general. Cu toate acestea, există încă câteva opțiuni atunci când construiți diagrame. De exemplu, cazul egalității AB \u003d C sau
, cazul seturilor goale și așa mai departe. Este evident că este dificil să ții cont de toate opțiunile posibile. Prin urmare, se crede că demonstrarea relațiilor folosind diagrame nu este întotdeauna corectă.

2. Dovada prin definiţia egalităţii mulţimilor.

Nevoie. Fie ABC și elementul XA. Să arătăm că în acest caz un element al mulțimii A va fi și un element al mulțimii
.

Luați în considerare două cazuri: XÎn sau
.

În cazul în care un XB, atunci XABC, adică XC și, ca urmare,
.

Dacă
, apoi și
. Necesitatea a fost dovedită.

Lasă acum
și XAB. Să arătăm că elementul X va fi, de asemenea, un element al mulțimii C.

În cazul în care un XAB, atunci XA și XB. Pentru că
, mijloace XC. Suficiența a fost dovedită.

1. Demonstrați cu o diagramă:

2. Dovada prin definiţia egalităţii mulţimilor.

Fie AB. Luați în considerare elementul XB (sau
). În mod similar: XA (sau XĀ). Adică fiecare element al setului este, de asemenea, un element al mulțimii Â. Și acesta poate fi cazul dacă
. Q.E.D.

Sarcina 3.4. Exprimați simbolic zonele indicate și simplificați expresiile rezultate.

Soluţie.

Zona căutată este formată din două părți izolate. Să le numim de sus și de jos. Setul pe care îl descriu poate fi descris după cum urmează:

M = ( X XA și XÎn şi XC sau XC și XA și XB).

Din definiția operațiilor pe mulțimi, obținem:

M = ((AB)\C)(C\A\B).

Să scriem această expresie folosind operațiile de bază - adunare, unire și intersecție:

Este imposibil să simplificăm această expresie, deoarece avem câte o apariție a fiecărui caracter. Aceasta este cea mai simplă formă a acestei formule.

Această zonă poate fi considerată ca uniunea mulțimilor A\B\C și ABC. Prin definiție, M = ( X XA și XÎn și XC sau XA și XÎn şi XC). Să simplificăm:

Sarcini pentru soluție independentă.

1. Simplifica:

2. Demonstrați folosind diagrame, legile algebrei mulțimilor și definiția egalității mulțimilor:

(AB)\B = A\B;

A(BC) = A\(A\B)(A\C);

AB \u003d AB  A \u003d B;

A \ B \u003d   AB \u003d A.

3. Aflați dacă există o mulțime X care satisface pentru orice A egalitatea:

AX \u003d A; (răspuns );