Secțiunea 2. Echivalența logică a formulelor. Forme normale pentru formule de algebră propozițională

Relația de echivalență

Cu ajutorul tabelelor de adevăr, se poate determina sub ce seturi de valori de adevăr ale variabilelor de intrare formula va lua o valoare adevărată sau falsă (precum și o declarație care are structura logică corespunzătoare), care formule vor fi tautologii sau contradicții și, de asemenea, stabiliți dacă două formule date echivalent.

În logică, se spune că două propoziții sunt echivalente dacă ambele sunt adevărate sau ambele false. Cuvântul „simultan” din această frază este ambiguu. Deci, pentru propozițiile „Mâine va fi marți” și „Ieri a fost duminică” acest cuvânt are un sens literal: luni sunt amândouă adevărate, iar în restul săptămânii ambele sunt false. Pentru ecuațiile " x = 2" și " 2x = 4» „simultan” înseamnă „cu aceleași valori ale variabilei”. Pronosticurile „Mâine va ploua” și „Nu este adevărat că mâine nu va ploua” vor fi simultan confirmate (se dovedesc a fi adevărate) sau neconfirmate (se dovedesc a fi false). În esență, aceasta este aceeași prognoză, exprimată în două diferite forme, care poate fi reprezentat prin formule Xși . Aceste formule iau simultan valoarea „adevărat” sau valoarea „falsă”. Pentru a verifica, este suficient să faci un tabel de adevăr:

Vedem că valorile de adevăr în prima și ultima coloană sunt aceleași. Astfel de formule, precum și propozițiile corespunzătoare acestora, sunt considerate în mod natural echivalente.

Formulele F 1 și F 2 se numesc echivalente dacă echivalentul lor este o tautologie.

Echivalența a două formule se scrie astfel: (a se citi: formula F1 este echivalent cu formula F2).

Există trei moduri de a verifica dacă formulele sunt echivalente: 1) faceți echivalentul lor și utilizați tabelul de adevăr pentru a verifica dacă este o tautologie; 2) pentru fiecare formulă, faceți un tabel de adevăr și comparați rezultatele finale; dacă în total coloanele pentru aceleași seturi de valori variabile valorile de adevăr ale ambelor formule vor fi egale, atunci formulele sunt echivalente; 3) cu ajutorul transformărilor echivalente.

Exemplul 2.1: Aflați dacă formulele sunt echivalente: 1) , ; 2), .

1) Să folosim prima metodă pentru a determina echivalența, adică să aflăm dacă echivalența formulelor este o tautologie.

Să facem o echivalență de formule: . Formula rezultată conține două variabile diferite ( DARși LA) si 6 operatii: 1) ; 2) ; 3) ; patru); 5) ; 6). Aceasta înseamnă că tabelul de adevăr corespunzător va avea 5 rânduri și 8 coloane:

Din coloana finală a tabelului de adevăr, se poate observa că echivalența compilată este o tautologie și, prin urmare, .

2) Pentru a afla dacă formulele și sunt echivalente, folosim a doua metodă, adică alcătuim un tabel de adevăr pentru fiecare dintre formule și comparăm coloanele finale. ( cometariu. Pentru a utiliza eficient a doua metodă, este necesar ca toate tabelele de adevăr compilate să înceapă în același mod, adică seturile de valori variabile au fost aceleași în rândurile respective .)

Formula are două variabile diferite și 2 operații, ceea ce înseamnă că tabelul de adevăr corespunzător are 5 rânduri și 4 coloane:

Formula are două variabile diferite și 3 operații, ceea ce înseamnă că tabelul de adevăr corespunzător are 5 rânduri și 5 coloane:

Comparând coloanele finale ale tabelelor de adevăr compilate (întrucât tabelele încep la fel, putem ignora seturile de valori variabile), vedem că acestea nu se potrivesc și, prin urmare, formulele nu sunt echivalente ().

Expresia nu este o formulă (deoarece simbolul „ ” nu se referă la nicio operație logică). Ea exprimă atitudineîntre formule (precum egalitatea între numere, paralelismul între linii etc.).

Teorema proprietăților relației de echivalență este valabilă:

Teorema 2.1. Relația de echivalență între formulele de algebră propozițională:

1) în mod reflex: ;

2) simetric: daca , atunci ;

3) tranzitiv: dacă și , atunci .

Legile logicii

Echivalențele formulelor logice propoziționale sunt adesea numite legile logicii. Le enumerăm pe cele mai importante dintre ele:

1. - legea identităţii.

2. - legea mijlocului exclus

3. - legea contradictiei

4. - disjuncția cu zero

5. - conjuncție cu zero

6. - disjuncție cu unitate

7. - conjuncție cu unitatea

8. - legea dublei negaţii

9. - comutativitatea conjuncţiei

10. – comutativitatea disjuncției

11. - asociativitatea conjuncţiei

12. - asociativitatea disjuncției

13. – distributivitatea conjuncţiei

14. – disjuncție distributivă

15. - legile impotentei

16. ; - legile de absorbtie

17. ; - Legile lui De Morgan

18. este legea care exprimă implicația prin disjuncție

19. - legea contrapoziției

20. - legi care exprimă echivalenţa prin alte operaţii logice

Legile logicii sunt folosite pentru a simplifica formulele complexe și pentru a demonstra că formulele sunt identic adevărate sau false.

Transformări echivalente. Formule simplificate

Dacă în formulele echivalente de peste tot înlocuim aceeași formulă în loc de o variabilă, atunci și formulele nou obținute se vor dovedi a fi echivalente în conformitate cu regula de substituție. În acest fel, din fiecare echivalență se poate obține orice număr de noi echivalențe.

Exemplul 1: Dacă în legea lui De Morgan în loc de Xînlocuitor, în loc de Yînlocuitor, atunci obținem o nouă echivalență. Valabilitatea echivalenței obținute este ușor de verificat folosind tabelul de adevăr.

Dacă vreo formulă care face parte din formula F, să fie înlocuit cu o formulă echivalentă cu formula , apoi formula rezultată va fi echivalentă cu formula F.

Apoi, pentru formula din Exemplul 2, putem face următoarele substituții:

- legea dublei negaţii;

- legea lui De Morgan;

- legea dublei negaţii;

– legea asociativității;

este legea idempotei.

Prin proprietatea tranzitivității relației de echivalență putem afirma că .

Se numește înlocuirea unei formule cu alta, echivalentă cu aceasta transformare echivalentă formule.

Sub simplificare formulele care nu conțin semne de implicație și echivalență înțeleg o transformare echivalentă care duce la o formulă care nu conține negații de formule neelementare (în special, negații duble) sau conține în total un număr mai mic de semne de conjuncție și disjuncție decât originalul unu.

Exemplul 2.2: Să simplificăm formula .

La primul pas, am aplicat legea care transformă implicația într-o disjuncție. La a doua etapă a fost aplicată legea comutativă. La a treia etapă s-a aplicat legea idempotității. Pe al patrulea - legea lui De Morgan. Și pe a cincea - legea dublei negații.

Observație 1. Dacă o anumită formulă este o tautologie, atunci orice formulă echivalentă cu aceasta este, de asemenea, o tautologie.

Astfel, transformările echivalente pot fi folosite și pentru a demonstra adevărul identic al anumitor formule. Pentru a face acest lucru, această formulă trebuie redusă prin transformări echivalente la una dintre formulele care sunt tautologii.

Observația 2. Unele tautologii și echivalențe sunt combinate în perechi (legea contradicției și legea legilor alternative, comutative, asociative etc.). În aceste corespondențe, așa-numitul principiul dualității .

Se numesc două formule care nu conțin semne de implicație și echivalență dual , dacă fiecare dintre ele poate fi obținut de la celălalt prin înlocuirea semnelor cu , respectiv.

Principiul dualității prevede următoarele:

Teorema 2.2: Dacă două formule care nu conțin semne de implicație și de echivalență sunt echivalente, atunci formulele lor duale sunt de asemenea echivalente.

forme normale

forma normala este un mod neambiguu din punct de vedere sintactic de a scrie o formulă care implementează o funcție dată.

Folosind legile logicii cunoscute, orice formulă poate fi transformată într-o formulă echivalentă a formei , unde și fiecare este fie o variabilă, fie negația unei variabile, fie o conjuncție de variabile sau negațiile acestora. Cu alte cuvinte, orice formulă poate fi redusă la o formulă echivalentă a unei forme standard simple, care va fi o disjuncție de elemente, fiecare dintre acestea fiind o conjuncție de variabile logice diferite, fie cu sau fără semn de negație.

Exemplul 2.3:În formulele mari sau cu transformări multiple se obișnuiește să se omite semnul conjuncției (prin analogie cu semnul înmulțirii): . Vedem că după transformările efectuate, formula este o disjuncție a trei conjuncții.

Această formă se numește forma normală disjunctivă (DNF). Un singur element al unui DNF este numit conjuncție elementară sau unitate constitutivă.

În mod similar, orice formulă poate fi redusă la o formulă echivalentă, care va fi o conjuncție de elemente, fiecare dintre ele va fi o disjuncție de variabile logice cu sau fără semn de negație. Adică, fiecare formulă poate fi redusă la o formulă echivalentă a formei , unde și fiecare este fie o variabilă, fie negația unei variabile, fie o disjuncție de variabile sau negațiile lor. Această formă se numește forma normală conjunctivă (KNF).

Exemplul 2.4:

Un singur element al CNF este numit disjuncție elementară sau constituentul lui zero.

Evident, fiecare formulă are infinit de DNF-uri și CNF-uri.

Exemplul 2.5: Să găsim mai multe DNF-uri pentru formulă .

Forme normale perfecte

SDNF (DNF perfect) este un astfel de DNF în care fiecare conjuncție elementară conține toate enunțurile elementare, sau negațiile lor o dată, conjuncțiile elementare nu se repetă.

SKNF (perfect CNF) este un astfel de CNF în care fiecare disjuncție elementară conține toate propozițiile elementare sau negațiile lor odată, disjuncțiile elementare nu se repetă.

Exemplul 2.6: 1) - SDNF

2) 1 - SKNF

Să formulăm trăsăturile caracteristice ale SDNF (SKNF).

1) Toți membrii disjuncției (conjuncției) sunt diferiți;

2) Toți membrii fiecărei conjuncții (disjuncție) sunt diferiți;

3) Nicio conjuncție (disjuncție) nu conține atât o variabilă, cât și negația acesteia;

4) Fiecare conjuncție (disjuncție) conține toate variabilele incluse în formula originală.

După cum vedem, caracteristicile (dar nu și formele!) satisfac definiția dualității, așa că este suficient să înțelegem o formă pentru a învăța cum să le obții pe amândouă.

Este ușor să obțineți SDNF (SKNF) din DNF (CNF) cu ajutorul transformărilor echivalente. Întrucât regulile pentru obținerea formelor normale perfecte sunt și ele duale, vom analiza în detaliu regula pentru obținerea SMNF și vom formula independent regula pentru obținerea SKNF folosind definiția dualității.

Regula generala aducerea formulei la SDNF folosind transformări echivalente:

Pentru a da formula F, care nu este identic fals, cu SDNF, este suficient:

1) aduceți-l la niște DNF;

2) eliminați membrii disjuncției care conține variabila împreună cu negația acesteia (dacă există);

3) din aceiași membri ai disjuncției (dacă există), eliminați toți în afară de unul;

4) eliminați toți, cu excepția unuia dintre membrii identici ai fiecărei conjuncții (dacă există);

5) dacă vreo conjuncție nu conține o variabilă dintre variabilele incluse în formula originală, adăugați un termen la această conjuncție și aplicați legea distributivă corespunzătoare;

6) dacă disjuncția rezultată conține aceiași termeni, folosiți prescripția 3.

Formula rezultată este SDNF-ul acestei formule.

Exemplul 2.7: Să găsim SDNF și SKNF pentru formulă .

Deoarece DNF pentru această formulă a fost deja găsit (vezi Exemplul 2.5), vom începe prin a obține SDNF:

2) în disjuncția rezultată nu există variabile împreună cu negațiile lor;

3) nu există membri identici în disjuncție;

4) nu există variabile identice în nicio conjuncție;

5) prima conjuncție elementară conține toate variabilele incluse în formula originală, iar celei de-a doua conjuncție elementară îi lipsește o variabilă z, deci să adăugăm un termen la el și să aplicăm legea distributivă: ;

6) se vede ușor că în disjuncție au apărut aceiași termeni, așa că înlăturăm unul (rețeta 3);

3) eliminați una dintre disjuncțiile identice: ;

4) nu există termeni identici în disjuncțiile rămase;

5) niciuna dintre disjuncţiile elementare nu conţine toate variabilele incluse în formula originală, deci completăm fiecare dintre ele cu conjuncţia : ;

6) nu există disjuncții identice în conjuncția rezultată, deci forma conjunctivă găsită este perfectă.

Deoarece în agregatul SKNF și SDNF formulele F 8 membri, atunci cel mai probabil sunt găsiți corect.

Fiecare formulă satisfăcătoare (refutabilă) are un singur SDNF și un singur SKNF. O tautologie nu are SKNF, iar o contradicție nu are SDNF.

Lecție deschisă de matematică „Schema Bernoulli. Rezolvarea problemelor folosind schema Bernoulli și Laplace”

Didactic: dobândirea de abilități și abilități de a lucra cu schema Bernoulli pentru a calcula probabilități.

Dezvoltarea: dezvoltarea abilităților de aplicare a cunoștințelor în practică, formarea și dezvoltarea gândirii funcționale a elevilor, dezvoltarea abilităților de comparare, analiză și sinteză, abilități de lucru în perechi, extinderea vocabularului profesional.

Cum să joci acest joc:

Educativ: stimularea interesului pentru materie prin aplicarea practică a teoriei, realizarea unei asimilari conștiente a materialului educațional al elevilor, formarea capacității de a lucra în echipă, utilizarea corectă a termenilor informatici, interesul pentru știință, respectul pentru viitoare profesie.

Cunoștințe științifice: B

Tip de lecție: lecție combinată:

• consolidarea materialului acoperit în clasele anterioare;
• tematică, tehnologia informației-problemă;
• generalizarea şi consolidarea materialului studiat în această lecţie.

Metoda de predare: explicativă - ilustrativă, problematică.

Controlul cunoștințelor: sondaj frontal, rezolvare de probleme, prezentare.

Materialul și echipamentul tehnic al lecției. calculator, proiector multimedia.

Suport metodologic: materiale de referință, prezentare pe tema lecției, cuvinte încrucișate.

În timpul orelor

1. Moment organizatoric: 5 min.

(salut, pregătirea grupului pentru lecție).

2. Verificarea cunoștințelor:

Verificați întrebările frontal pe diapozitive: 10 min.

• definițiile secțiunii „Teoria probabilității”
• conceptul principal al secțiunii „Teoria probabilității”
• ce evenimente sunt studiate de „Teoria probabilității”
• caracteristică unui eveniment aleatoriu
• definiția clasică a probabilităților

Rezumând. 5 minute.

3. Rezolvarea problemelor pe rânduri: 5 min.

Sarcina 1. Se aruncă un zar. Care este probabilitatea de a obține un număr par mai mic de 5?

Sarcina 2. Există nouă tuburi radio identice într-o cutie, dintre care trei erau în uz. În timpul zilei de lucru, comandantul trebuia să ia două tuburi radio pentru a repara echipamentul. Care este probabilitatea ca ambele lămpi să fi fost folosite?

Sarcina 3. Există trei filme diferite în trei săli de cinema. Probabilitatea ca pentru o anumită oră să existe bilete la casa de bilete a sălii 1 este de 0,3, la casa de bilete a sălii a 2-a - 0,2, iar la casa de bilete a sălii a 3-a - 0,4. Care este probabilitatea ca la o oră dată să se poată cumpăra un bilet pentru cel puțin un film?

4. Verificarea la tablă a modului de rezolvare a problemelor. Aplicare 1. 5 min.

Concluzia a 5-a privind rezolvarea problemelor:

Probabilitatea de apariție a unui eveniment este aceeași pentru fiecare sarcină: m și n - const

6. Stabilirea obiectivelor prin sarcină: 5 min.

O sarcină. Doi jucători egali de șah joacă șah. Care este probabilitatea de a câștiga două jocuri din patru?

Care este probabilitatea de a câștiga trei jocuri din șase (nu se iau în considerare remizele)?

Întrebare. Gândește-te și numește diferența dintre întrebările acestei probleme și întrebările problemelor anterioare?

Prin raționament, prin comparație, obțineți un răspuns: la întrebările m și n sunt diferite.

7. Tema lecției:

Calculul probabilității de apariție a unui eveniment k ori din n experimente cu p-const.

Dacă se fac studii în care probabilitatea de apariție a evenimentului A în fiecare studiu nu depinde de rezultatele altor studii, atunci astfel de încercări sunt numite independente în raport cu evenimentul A. Încercări, în fiecare dintre ele probabilitatea de apariție a evenimentul este același.

formula Bernoulli. Probabilitatea ca în n încercări independente, în fiecare dintre ele probabilitatea de apariție a unui eveniment este egală cu p (0

sau Anexa 2 Formula Bernoulli, unde k,n-numere mici unde q = 1-p

Soluție: Jucători egali de șah joacă, deci probabilitatea de a câștiga este p=1/2; prin urmare, probabilitatea de a pierde q este de asemenea 1/2. Deoarece probabilitatea de câștig este constantă în toate jocurile și nu contează în ce ordine sunt câștigate, formula Bernoulli este aplicabilă. 5 minute

Găsiți probabilitatea ca două jocuri din patru să fie câștigate:

Găsiți probabilitatea ca trei din șase jocuri să fie câștigate:

Deoarece P4 (2) > P6 (3), este mai probabil să câștigi două jocuri din patru decât trei din șase.

8. Sarcină.

Găsiți probabilitatea ca evenimentul A să apară exact de 70 de ori în 243 de încercări dacă probabilitatea ca acest eveniment să apară în fiecare încercare este 0,25.

k=70, n=243 Aceasta implică faptul că k și n sunt numere mari. Aceasta înseamnă că este dificil de calculat conform formulei Bernoulli. Pentru astfel de cazuri, se aplică formula locală Laplace:

Anexa 3 pentru valorile pozitive ale lui x este prezentată în apendicele 4; pentru valori negative ale lui x folosiți același tabel și = .

9. Compuneți un algoritm pentru rezolvarea problemei: 5 min.

• găsiți valoarea lui x și rotunjiți până la sutimi (0,01);
• conform tabelului funcției Laplace vom găsi;
• înlocuim valoarea funcției Laplace în formula Laplace

10. Rezolvarea problemei cu analiza la tabla. Anexa 5. 10 min.

11. Rezumarea informațiilor despre lecție prin prezentări

• scurte informații despre secțiunea „Teoria probabilității”; 5 minute.
• materiale istorice despre oamenii de știință Bernoulli și Laplace. 5 minute.

Permițând cuiva să treacă de la ecuația care se rezolvă la așa-numita ecuații echivalenteși ecuații corolare, prin soluții ale cărora se poate determina soluția ecuației inițiale. În acest articol, vom analiza în detaliu ce ecuații sunt numite echivalente și care sunt numite ecuații corolar, vom oferi definițiile corespunzătoare, vom oferi exemple explicative și vom explica cum să găsim rădăcinile unei ecuații din rădăcinile cunoscute ale unei ecuații echivalente și ale unui ecuație corolară.

Ecuații echivalente, definiție, exemple

Să dăm o definiție a ecuațiilor echivalente.

Definiție

Ecuații echivalente sunt ecuații care au aceleași rădăcini sau nu au rădăcini.

Definiții similare ca înțeles, dar ușor diferite în formulare, sunt date în diferite manuale de matematică, de exemplu,

Definiție

Se numesc cele două ecuații f(x)=g(x) și r(x)=s(x). echivalent, dacă au aceleași rădăcini (sau, în special, dacă ambele ecuații nu au rădăcini).

Definiție

Se numesc ecuații care au aceleași rădăcini ecuații echivalente. Ecuațiile care nu au rădăcini sunt de asemenea considerate echivalente.

Prin aceleași rădăcini se înțelege următoarele: dacă un număr este rădăcina uneia dintre ecuațiile echivalente, atunci este și rădăcina oricărei alte ecuații din aceste ecuații și nici una dintre ecuațiile echivalente nu poate avea o rădăcină care nu este rădăcina oricărei alte ecuații.

Să dăm exemple de ecuații echivalente. De exemplu, trei ecuații 4 x=8, 2 x=4 și x=2 sunt echivalente. Într-adevăr, fiecare dintre ele are o rădăcină unică 2, deci sunt echivalente prin definiție. Un alt exemplu: două ecuații x 0=0 și 2+x=x+2 sunt echivalente, mulțimile soluțiilor lor sunt aceleași: rădăcina primei și celei de-a doua dintre ele este orice număr. Cele două ecuații x=x+5 și x 4 =−1 sunt, de asemenea, un exemplu de ecuații echivalente, ambele nu au soluții reale.

Pentru a completa imaginea, merită să oferiți exemple de ecuații neechivalente. De exemplu, ecuațiile x=2 și x 2 =4 nu sunt echivalente, deoarece a doua ecuație are rădăcina −2, care nu este rădăcina primei ecuații. De asemenea, ecuațiile și nu sunt echivalente, deoarece rădăcinile celei de-a doua ecuații sunt orice numere, iar numărul zero nu este rădăcina primei ecuații.

Definiția corectă a ecuațiilor echivalente se aplică atât ecuațiilor cu o variabilă, cât și ecuațiilor cu un număr mare de variabile. Cu toate acestea, pentru ecuațiile cu doi, trei etc. variabile, cuvântul „rădăcini” din definiție ar trebui înlocuit cu cuvântul „soluții”. Asa de,

Definiție

Ecuații echivalente sunt ecuații care au aceleași soluții sau nu le au.

Să arătăm un exemplu de ecuații echivalente cu mai multe variabile. x 2 +y 2 +z 2 =0 și 5 x 2 +x 2 y 4 z 8 =0 - iată un exemplu de ecuații echivalente cu trei variabile x, y și z, ambele având o soluție unică (0, 0 , 0). Dar ecuațiile cu două variabile x + y=5 și x y=1 nu sunt echivalente, deoarece, de exemplu, perechea de valori x=2, y=3 este soluția primei ecuații (la înlocuirea acestor valori ​​în prima ecuație, obținem egalitatea corectă 2+3=5), dar nu este o soluție pentru a doua (când înlocuim aceste valori în a doua ecuație, obținem egalitatea greșită 2 3=1).

Ecuații corolare

Iată definițiile ecuațiilor corolar din manualele școlare:

Definiție

Dacă fiecare rădăcină a ecuației f(x)=g(x) este în același timp rădăcina ecuației p(x)=h(x) , atunci ecuația p(x)=h(x) se numește consecinţă ecuațiile f(x)=g(x) .

Definiție

Dacă toate rădăcinile primei ecuații sunt rădăcini ale celei de-a doua ecuații, atunci a doua ecuație se numește consecinţă prima ecuație.

Să dăm câteva exemple de ecuații corolare. Ecuația x 2 =3 2 este o consecință a ecuației x−3=0 . Într-adevăr, a doua ecuație are o singură rădăcină x=3, această rădăcină este și rădăcina ecuației x 2 =3 2 , prin urmare, prin definiție, ecuația x 2 =3 2 este o consecință a ecuației x−3= 0 . Un alt exemplu: ecuația (x−2) (x−3) (x−4)=0 este o consecință a ecuației , deoarece toate rădăcinile celei de-a doua ecuații (sunt două dintre ele, acestea sunt 2 și 3 ), evident, sunt rădăcinile primei ecuații.

Din definiția unei ecuații de consecință, rezultă că absolut orice ecuație este o consecință a oricărei ecuații care nu are rădăcini.

Merită menționat câteva consecințe destul de evidente din definirea ecuațiilor echivalente și definiția unei ecuații corolar:

• Dacă două ecuații sunt echivalente, atunci fiecare este o consecință a celeilalte.
• Dacă fiecare dintre cele două ecuații este o consecință a celeilalte, atunci aceste ecuații sunt echivalente.
• Două ecuații sunt echivalente dacă și numai dacă fiecare dintre ele este o consecință a celeilalte.