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ă nici măcar nu teoretic, ci general, ne așteaptă sarcini practice și, prin urmare, 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 î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ă remarc 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 un lucru important: identitățile sunt valabile nu numai pentru propozițiile elementare, ci și pentru formulele 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 .

Lecția de informatică este destinată elevilor din clasa a X-a a unei școli de învățământ general, a cărei curriculum include secțiunea „Algebra logicii”. Această temă este foarte dificilă pentru elevi, așa că eu, ca profesor, am vrut să-i interesez să studieze legile logicii, să simplifice expresiile logice și să abordez cu interes rezolvarea problemelor logice. În forma obișnuită, a da lecții pe această temă este plictisitoare și supărătoare, iar unele definiții nu sunt întotdeauna clare pentru copii. În legătură cu asigurarea spațiului de informare, am avut ocazia să-mi postez lecțiile în shell-ul „învățare”. Studenții, înscriși la acesta, pot urma acest curs în timpul liber și pot reciti ceea ce nu a fost clar în lecție. Unii elevi, care au ratat lecțiile din cauza unei boli, compensează subiectul ratat acasă sau la școală și sunt întotdeauna pregătiți pentru următoarea lecție. Această formă de predare se potrivea foarte mult multor copii, iar acele legi care erau de neînțeles pentru ei sunt acum învățate pe calculator mult mai ușor și mai rapid. Ofer una dintre aceste lecții de informatică, care se desfășoară în mod integrativ cu TIC.

Planul lecției

1. Explicarea materialului nou, cu implicarea unui calculator - 25 de minute.
2. Concepte și definiții de bază prezentate în „învățare” - 10 minute.
3. Material pentru curioși - 5 minute.
4. Tema pentru acasă - 5 minute.

1. Explicarea materialului nou

Legile logicii formale

Cele mai simple și mai necesare conexiuni adevărate între gânduri sunt exprimate în legile de bază ale logicii formale. Acestea sunt legile identităţii, necontradicţiei, mijloc exclus, motiv suficient.

Aceste legi sunt fundamentale pentru că în logică joacă un rol deosebit de important, sunt cele mai generale. Ele vă permit să simplificați expresiile logice și să construiți inferențe și dovezi. Primele trei dintre legile de mai sus au fost identificate și formulate de Aristotel, iar legea rațiunii suficiente - de G. Leibniz.

Legea identității: în procesul unui anumit raționament, fiecare concept și judecată trebuie să fie identice cu sine.

Legea necontradicției: este imposibil ca unul și același ochi în același timp să fie și să nu fie inerent aceluiași lucru în același sens. Adică este imposibil să afirmi și să negi ceva în același timp.

Legea mijlocului exclus: dintre două propoziții contradictorii, una este adevărată, cealaltă este falsă și a treia nu este dată.

Legea Rațiunii Suficiente: Fiecare gând adevărat trebuie să fie suficient de justificat.

Ultima lege spune că dovada a ceva presupune justificarea unor gânduri precise și numai adevărate. Gândurile false nu pot fi dovedite. Există un proverb latin bun: „A greși este comun oricărei persoane, dar numai un prost trebuie să insiste asupra unei greșeli”. Nu există o formulă pentru această lege, întrucât are doar un caracter material. Judecățile adevărate, materialul faptic, datele statistice, legile științei, axiomele, teoremele dovedite pot fi folosite ca argumente pentru a confirma un gând adevărat.

Legile algebrei propoziționale

Algebra propozițiilor (algebra logicii) este o secțiune a logicii matematice care studiază operațiile logice asupra propozițiilor și regulile de transformare a propozițiilor complexe.

La rezolvarea multor probleme logice, este adesea necesară simplificarea formulelor obținute prin formalizarea condițiilor acestora. Simplificarea formulelor în algebra propozițiilor se realizează pe baza transformărilor echivalente bazate pe legile logice de bază.

Legile algebrei propozițiilor (algebra logicii) sunt tautologii.

Uneori aceste legi sunt numite teoreme.

În algebra propozițională, legile logice sunt exprimate ca egalitate de formule echivalente. Dintre legi se disting în special cele care conțin o variabilă.

Primele patru dintre următoarele legi sunt legile de bază ale algebrei propoziționale.

Legea identității:

Fiecare concept și judecată este identică cu sine.

Legea identității înseamnă că în procesul de raționament nu se poate înlocui un gând cu altul, un concept cu altul. Dacă această lege este încălcată, sunt posibile erori logice.

De exemplu, discuție Ei spun corect că limba te va aduce la Kiev, dar am cumpărat limbă afumată ieri, ceea ce înseamnă că acum pot merge în siguranță la Kiev incorect, deoarece primul și al doilea cuvânt „limbă” denotă concepte diferite.

In discutie: Mișcarea este eternă. A merge la școală este mișcare. Prin urmare, mersul la școală este pentru totdeauna cuvântul „mișcare” este folosit în două sensuri diferite (primul - în sens filozofic - ca atribut al materiei, al doilea - în sens obișnuit - ca acțiune de deplasare în spațiu), ceea ce duce la o concluzie falsă.

Legea necontradicției:

O propoziție și negația ei nu pot fi adevărate în același timp. Adică dacă declarația DAR este adevărat, apoi negația sa nu A trebuie să fie fals (și invers). Atunci produsul lor va fi întotdeauna fals.

Această egalitate este adesea folosită la simplificarea expresiilor logice complexe.

Uneori această lege este formulată astfel: două afirmații care se contrazic nu pot fi adevărate în același timp. Exemple de nerespectare a legii necontradicției:

1. Există viață pe Marte și nu există viață pe Marte.

2. Olya a absolvit liceul și este în clasa a X-a.

Legea mijlocului exclus:

În același moment, afirmația poate fi fie adevărată, fie falsă, nu există o a treia. Adevărat fie DAR, sau nu A. Exemple de implementare a legii mijlocului exclus:

1. Numărul 12345 este fie par, fie impar, nu există o treime.

2. Compania operează cu pierderi sau prag de rentabilitate.

3. Acest lichid poate fi sau nu un acid.

Legea mijlocului exclus nu este o lege recunoscută de toți logicienii ca o lege universală a logicii. Această lege se aplică acolo unde cunoștințele se ocupă de o situație rigidă: „ori – sau”, „adevărat-fals”. Acolo unde există incertitudine (de exemplu, în raționamentul despre viitor), legea mijlocului exclus adesea nu poate fi aplicată.

Luați în considerare următoarea afirmație: Această sugestie este falsă. Nu poate fi adevărat pentru că se pretinde a fi fals. Dar nici nu poate fi fals, pentru că atunci ar fi adevărat. Această afirmație nu este nici adevărată, nici falsă și, prin urmare, legea mijlocului exclus este încălcată.

Paradox(Paradoxos grecesc - neașteptat, ciudat) în acest exemplu rezultă din faptul că propoziția se referă la ea însăși. Un alt paradox celebru este problema coaforului: Într-un oraș, un coafor tunde părul tuturor locuitorilor, cu excepția celor care își tund singuri părul. Cine tunde parul frizerului?În logică, din cauza formalității sale, nu este posibil să se obțină forma unei astfel de enunțuri autoreferențiale. Acest lucru confirmă încă o dată ideea că, cu ajutorul algebrei logicii, este imposibil să se exprime toate gândurile și argumentele posibile. Să arătăm cum, pe baza definiției echivalenței propoziționale, pot fi obținute restul legilor algebrei propoziționale.

De exemplu, să definim ceea ce este echivalent cu (echivalent cu) DAR(de două ori nr DAR, adică negația negației DAR). Pentru a face acest lucru, vom construi un tabel de adevăr:

Prin definiția echivalenței, trebuie să găsim coloana ale cărei valori se potrivesc cu valorile coloanei DAR. Aceasta va fi coloana DAR.

Astfel, putem formula dubla legenegatii:

Dacă negăm o afirmație de două ori, atunci rezultatul este afirmația originală. De exemplu, afirmația DAR= Matroskin- pisică este echivalent cu a spune A = Nu este adevărat că Matroskin nu este o pisică.

În mod similar, următoarele legi pot fi derivate și verificate:

Proprietăți constante:

Legile impotentei:

Indiferent de câte ori repetăm: TV pe sau televizor pe sau televizor pe... sensul propoziției nu se va schimba. La fel de la repetare E cald afara, e cald afara... nici un grad mai cald.

Legile comutativității:

A v B = B v A

A & B = B & A

operanzi DARși LAîn operaţiile de disjuncţie şi conjuncţie pot fi interschimbate.

Legile asociativității:

A v(B v C) = (A v B) v C;

A și (B și C) = (A și B) și C.

Dacă expresia folosește doar operația de disjuncție sau numai operația de conjuncție, atunci puteți neglija parantezele sau le puteți aranja în mod arbitrar.

Legile distributivității:

A v (B & C) = (A v B) & (A v C)

(disjuncție distributivă
referitor la conjuncție)

A și (B v C) = (A și B) v (A și C)

(distributivitatea conjuncției
referitor la disjuncție)

Legea distributivă a conjuncției cu privire la disjuncție este similară cu legea distributivă din algebră, dar legea distributivă a conjuncției față de conjuncție nu are analog, este valabilă doar în logică. Prin urmare, trebuie dovedit. Dovada se face cel mai bine folosind un tabel de adevăr:

Legile de absorbție:

A v (A și B) = A

A și (A v B) = A

Efectuați singur dovada legilor de absorbție.

Legile lui De Morgan:

Formulări verbale ale legilor lui de Morgan:

Regula mnemonică:în partea stângă a identității, operația de negație stă deasupra întregului enunț. În partea dreaptă, pare a fi rupt și negația stă deasupra fiecăreia dintre afirmațiile simple, dar în același timp operația se schimbă: disjuncție în conjuncție și invers.

Exemple de implementare a legii lui de Morgan:

1) Declarație Nu este adevărat că știu arabă sau chineză este identică cu afirmația Nu știu arabă și nu știu chineză.

2) Declarație Nu este adevărat că mi-am învățat lecția și am primit un D la ea este identică cu afirmația Ori nu am învățat lecția, ori nu am primit A la ea.

Înlocuirea operațiunilor de implicare și echivalență

Operațiile de implicare și echivalență nu se numără uneori printre operațiunile logice ale unui anumit computer sau compilator dintr-un limbaj de programare. Cu toate acestea, aceste operații sunt necesare pentru rezolvarea multor probleme. Există reguli pentru înlocuirea acestor operații cu secvențe de operații de negație, disjuncție și conjuncție.

Deci, înlocuiți operațiunea implicatii posibil conform următoarei reguli:

Pentru a înlocui operația echivalenţă sunt doua reguli:

Este ușor de verificat validitatea acestor formule prin construirea tabelelor de adevăr pentru părțile din dreapta și din stânga ambelor identități.

Cunoașterea regulilor de înlocuire a operațiilor de implicare și echivalență ajută, de exemplu, la construirea corectă a negației unei implicații.

Luați în considerare următorul exemplu.

Să fie dat enunțul:

E = Nu este adevărat că dacă voi câștiga concursul, voi primi un premiu.

Lăsa DAR= Voi câștiga concursul

B = Voi primi un premiu.

Prin urmare, E = voi câștiga competiția, dar nu voi primi un premiu.

Următoarele reguli sunt de asemenea de interes:

De asemenea, le puteți demonstra validitatea folosind tabele de adevăr.

Exprimarea lor în limbaj natural este interesantă.

De exemplu, fraza

Dacă Winnie the Pooh a mâncat miere, atunci este sătul

este identic cu fraza

Dacă Winnie the Pooh nu este sătul, atunci nu a mâncat miere.

Exercițiu: gândiți-vă la expresii-exemple pe aceste reguli.

2. Concepte de bază și definițiiîn Anexa 1

3. Material pentru curioșiîn Anexa 2

4. Tema pentru acasă

1) Învață legile logicii folosind cursul Algebra logicii situat în spațiul informațional (www.learning.9151394.ru).

2) Verificați dovada legilor lui De Morgan pe un computer prin construirea unui tabel de adevăr.

Aplicații

1. Concepte și definiții de bază (Anexa 1).
2. Material pentru curioși (Anexa 2).

1. Completați tabelul scriind în sistemul numeric pozițional zecimal numerele corespunzătoare numerelor scrise în sistemul numeric roman:

2. Convertiți numerele din sistemul numeric roman în sistemul numeric zecimal:

3. Scrieți în sistemul numeric roman:

4. Notați alfabetele următoarelor sisteme de numere poziționale:

5. Alfabete ale căror sisteme de numere poziționale sunt prezentate mai jos? Notează-le numele:

6. Notează cea mai mică bază a sistemului numeric în care pot fi scrise următoarele numere:

7. Notați numerele în formă extinsă:

8. Calculați echivalentele zecimale ale următoarelor numere:

9. Calculați echivalentele zecimale ale următoarelor numere binare:

10. Notați numerele maxime și minime de patru cifre:

11. Calculatorul, care lucrează în sistemul numeric ternar, are cinci familiarități pentru afișarea numărului pe ecran. Care este cel mai mare număr zecimal cu care poate lucra acest calculator?

12. Specificați numerele de numere în ordine crescătoare:

13. Comparați numerele:

14. Calculați x pentru care egalitățile sunt adevărate:

15. Un om înțelept a scris: „Am 33 de ani. Mama mea are 124 de ani, iar tatăl meu 131. Împreună avem 343 de ani.” Ce sistem de numere a folosit înțeleptul și câți ani are?

16. O persoană avea 102 monede. Le-a împărțit în mod egal între cei doi copii ai săi. Fiecare a primit 12 monede și una a rămas de prisos. Ce sistem numeric a fost folosit și câte monede erau?

17. Construiți un desen pe planul de coordonate prin marcarea și conectarea punctelor în secvența specificată.

18. Construiți un desen pe planul de coordonate, marcând și conectând punctele în succesiune:

19. Construiți un desen pe planul de coordonate, marcând și conectând punctele în succesiune:

20. Convertiți numere întregi din zecimal în binar:

21. Convertiți numere întregi din zecimal în binar folosind metoda diferențelor:

22. Descifrați imaginea grafică prezentând următoarele numere zecimale în cod binar (introduceți fiecare cifră binară într-o celulă separată; umbriți celulele cu zerouri):

23. Câți 1 există în notație binară pentru un număr zecimal?

24. Câte 0 sunt în notație binară pentru un număr zecimal?

25. Notează numerele întregi naturale aparținând următoarelor intervale numerice:

26. Convertiți numere întregi din zecimal în octal:

27. Convertiți numere întregi din zecimal în hexazecimal:

28. Completați tabelul, în fiecare rând în care trebuie scris același număr în sisteme numerice cu baza 2, 8, 10 și 16.

29. Efectuați operația de adunare pe numere binare. Verificați prin conversia termenilor și a sumei în sistemul numeric zecimal.

30. Efectuați o operație de înmulțire pe numere binare. Verificați prin conversia factorilor și a produsului în sistemul numeric zecimal.

31. Elaborați tabele de adunare și înmulțire pentru sistemul de numere octale.

32. Rezolvați ecuația

33. La olimpiada de informatică au participat 30 de fete și 50 de băieți, iar în total - 100 de persoane. În ce sistem de numere este înregistrată această informație?

34. Aflați valoarea expresiei K+L+M+N în octal dacă:

35. Construiți un grafic care să reflecte relația dintre conceptele de bază pe tema „Sisteme numerice”.

36. Convertiți numărul 1010 din zecimal în binar. Câte unități conține numărul rezultat? În răspunsul tău, scrie un număr - numărul de unități.
Raspuns: 7.

37. Reprezentați numere zecimale în format de 8 biți fără semn.

38. Scrie codul direct al numerelor zecimale în format de 8 cifre semnate.

39. Găsiți echivalentele zecimale ale numerelor după codurile lor directe scrise în format semnat pe 8 biți:

40. Notează următoarele numere în formă naturală:

41. Scrieți numărul 2014.4102(10) în cinci moduri diferite în formă normală:

42. Scrieți următoarele numere în formă normală cu o mantisă normalizată - o fracție proprie care are o cifră diferită de zero după virgulă:

43. Luați în considerare un fragment din tabelul de codificare ASCII:

45. Un rezumat scris pe computer conține 16 pagini, 32 de rânduri pe fiecare pagină, 64 de caractere pe fiecare rând. Determinați volumul de informații al articolului în codificare Unicode, unde fiecare caracter este codificat pe 16 biți.

46. ​​​​Fiecărei cifre hexazecimale i se atribuie un lanț de patru 0 și 1 (tetradă binară):
Decodificați imaginile grafice prin înlocuirea fiecărei cifre hexazecimale cu o tetradă binară. Completați celulele cu zerouri.

47. Calculați cantitatea necesară de memorie video pentru modul grafic, dacă rezoluția ecranului monitorului este 1024x768, adâncimea culorii este de 32 de biți.

48. Calculați cantitatea necesară de memorie video pentru modul grafic, dacă rezoluția ecranului monitorului este 1024x768 și numărul de culori din paletă este 256.

49. Pentru a stoca un bitmap de 128x64 pixeli, au fost alocați 8 KB de memorie. Care este numărul maxim posibil de culori din paleta unei imagini?

50. Un articol tastat pe computer conține 4 pagini, fiecare pagină are 40 de rânduri, fiecare rând are 64 de caractere. Într-o reprezentare a Unicode, fiecare caracter este codificat cu 16 biți. Determinați conținutul informațional al articolului în această variantă a reprezentării Unicode.
Răspuns: 1) 20 KB.

51. Notează o afirmație adevărată și una falsă din biologie, geografie, informatică, istorie, matematică, literatură:

52. În următoarele afirmații, evidențiați-le pe cele simple, notându-le pe fiecare cu o literă; notează fiecare enunț compus folosind litere și semne ale operațiilor logice.

53. Tabelul arată interogările și numărul de pagini găsite pe acestea pentru un anumit segment de internet.

54. Tabelul prezintă interogări și numărul de pagini găsite pe acestea pentru un anumit segment de internet.

55. Tabelul arată interogările și numărul de pagini găsite pe acestea pentru un anumit segment de internet.

56. Unele segmente ale rețelei de internet sunt formate din 1000 de site-uri. Tabelul arată interogările și numărul de pagini găsite de aceștia în acest segment de rețea:

60. Găsiți valoarea expresiei logice pentru valorile X date:

61. Completați tabelul cu valori booleene:

62. Trei prieteni jucau fotbal în curte și au spart geamul cu o minge. Vanya a spus: „Eu am spart geamul, Kolya nu a spart geamul”. Kolya a spus: „Nu eu și nu Sasha am făcut-o”. Sasha a spus: „Nu eu și nici Vanya am făcut-o”. Bunica s-a așezat pe bancă și a văzut totul. Ea a spus că doar un băiat a spus adevărul de ambele ori, dar nu l-a numit pe cel care a spart geamul. Cine este aceasta?

63. Se cercetează dosarul de delapidare. Bragin, Kurgin și Likhodeev sunt suspectați de această crimă. Fiecare dintre ei a dat următoarea mărturie.
Bragin: „Nu am făcut-o. Acest lucru a fost făcut de Likhodeev.
Likhodeev: „Nu este vina mea, dar nici Kurgin nu are nimic de-a face cu asta”.
Kurgin: „Likhodeev nu este vinovat. Crima a fost comisă de Bragin.
Ancheta a stabilit cu certitudine că furtul a fost săvârșit de doi, în plus, suspecții au fost confuzi în mărturie și fiecare dintre ei nu a depus mărturie pe deplin veridică. Cine a comis crima?
Rezolvați problema completând și analizând tabelul de adevăr:

64. Într-o călătorie, cinci prieteni - Anton, Boris, Vadim, Dima și Grisha - s-au întâlnit cu un coleg de călătorie. I-au rugat să le ghicească numele și fiecare dintre ei a făcut o afirmație adevărată și una falsă:
Dima a spus: „Numele meu de familie este Mishin, iar numele de familie al lui Boris este Khohlov”.
Anton a spus: „Mishin este numele meu de familie, iar numele de familie al lui Vadim este Belkin”. Boris a spus: „Numele de familie al lui Vadim este Tikhonov, iar numele meu de familie este Mishin”.
Vadim a spus: „Numele meu de familie este Belkin, iar numele de familie al lui Grisha este Cehov”.
Grisha a spus: „Da, numele meu este Cehov, iar numele de familie al lui Anton este Tihonov”.
Care este numele de familie al fiecărui prieten?

(Dm(¬Bx)+(¬Dm)Bx)*(Am(¬Wb)+(¬Am)Wb)*(Bm(¬W)+(¬Bm)W)*(Wb(¬Gch)+( ¬Wb)Gch)*(Gch(¬At)+(¬Gch)At)=1
Expresia este adevărată atunci când toate sumele sunt adevărate. Să presupunem că Dm=1, apoi Am=0, Bm=0; Dar atunci Wb=1 și W=1, ceea ce este imposibil. Deci, Bh-adevăr. Atunci Bm este fals, W este adevărat, At este fals, Gh este adevărat, Wb este fals, Am este adevărat.
Răspuns: Boris Hokhlov, Vadim Tihonov, Grisha Cehov, Anton Mișin, Dima Belkin.

65. Trei prieteni, fani ai fotbalului, se certau despre rezultatele turneului viitor.
Opinia lui Yuri: „O să vezi, Barcelona nu va fi prima. Zenit va fi primul.
Opinia lui Victor: „Barcelona va fi câștigătoare. Și nu e nimic de spus despre Zenit, nu va fi primul.
Opinia lui Leonid: „Realul nu va vedea primul loc, dar Barcelona are toate șansele să câștige”.
La finalul competiției, s-a dovedit că fiecare dintre cele două presupuneri ale celor doi prieteni a fost confirmată, iar ambele presupuneri ale celui de-al treilea dintre prieteni s-au dovedit a fi greșite. Cine a câștigat turneul?
Rezolvați problema compunând și transformând o expresie logică:

66. Aflați ce semnal ar trebui să fie la ieșirea circuitului pentru fiecare set posibil de semnale la intrări. Completați foaia de lucru a schemei. Ce expresie logică descrie circuitul?

67. Pentru care dintre nume date este adevărată afirmația:

Cuvinte cheie:

• algebra logicii
• afirmație
• operatie logica
• conjuncţie
• disjuncție
• negare
• expresie booleană
• tabelul de adevăr
• legile logicii

1.3.1. afirmație

Algebra în sensul cel mai larg al cuvântului este știința operațiilor generale, similare cu adunarea și înmulțirea, care pot fi efectuate pe o varietate de obiecte matematice. Studiezi multe obiecte matematice (numere întregi și raționale, polinoame, vectori, mulțimi) la cursul de algebră școlară, unde te familiarizezi cu astfel de secțiuni ale matematicii precum algebra numerelor, algebra polinomială, algebra mulțimilor etc.

Pentru informatică, ramura matematicii numită algebra logicii este importantă; obiectele algebrei logicii sunt propoziţii.

De exemplu, în ceea ce privește propozițiile „Marele om de știință rus M.V. Lomonosov s-a născut în 1711” și „Doi plus șase este opt”, se poate spune fără echivoc că sunt adevărate. Propoziția „Vrăbiile hibernează iarna” este falsă. Prin urmare, aceste propoziții sunt afirmații.

De exemplu, propoziția „Această propoziție este falsă” nu este o propoziție, deoarece nu se poate spune despre ea dacă este adevărată sau falsă fără a obține o contradicție. Într-adevăr, dacă acceptăm că propoziția este adevărată, atunci aceasta contrazice ceea ce s-a spus. Dacă acceptăm că propoziția este falsă, atunci rezultă că este adevărată.

În ceea ce privește propoziția „ Grafica pe computer este subiectul cel mai interesant în cursul de informatică școlară”, de asemenea, este imposibil de spus fără echivoc dacă este adevărată sau falsă. Gândește-te singur de ce.

De exemplu, propoziții precum: „Notă-ți temele”, „Cum să ajungi la bibliotecă?”, „Cine a venit la noi? ".

Exemple de afirmații pot fi:

1. „Na este metal” (afirmație adevărată);
2. „A doua lege a lui Newton este exprimată prin formula F=m a” (enunț adevărat);
3. „Perimetrul unui dreptunghi cu lungimea laturii a u b este egal cu a b” (afirmație falsă).

Expresiile numerice nu sunt enunțuri, dar o declarație poate fi făcută din două expresii numerice conectându-le cu semne de egalitate sau de inegalitate. De exemplu:

1. „34-5 = 2 4” (afirmație adevărată);
2. „II4-VI > VIII” (afirmație falsă).

Egalitățile sau inegalitățile care conțin variabile nu sunt nici afirmații. De exemplu, propoziția „X< 12» становится высказыванием только при замене переменной каким-либо конкретным значением: «5 < 12» - истинное высказывание; «12 < 12» - ложное высказывание.

Fundamentarea adevărului sau falsității afirmațiilor este decisă de științele cărora le aparțin. Algebra logicii este extrasă din conținutul semantic al enunțurilor. Ea este interesată doar dacă afirmația dată este adevărată sau falsă. În algebra logicii, enunțurile sunt notate cu litere și sunt numite variabile logice. Mai mult, dacă afirmația este adevărată, atunci valoarea variabilei logice corespunzătoare este notată cu unu (A \u003d 1), iar dacă este falsă, cu zero (B \u003d 0). 0 și 1 care denotă valorile variabilelor booleene se numesc valori booleene.

Operând cu variabile logice care pot fi doar egale cu 0 sau 1, algebra logicii vă permite să reduceți procesarea informațiilor la operații cu date binare. Este aparatul algebrei logicii care formează baza dispozitivelor computerizate pentru stocarea și procesarea informațiilor. Cu ajutorul elementelor algebrei logicii, vă veți întâlni în multe alte secțiuni ale informaticii.

1.3.2. Operații booleene

Afirmațiile sunt simple și complexe. O afirmație se numește simplă dacă nicio parte din ea nu este ea însăși o declarație. Instructiunile complexe (compuse) sunt construite din cele simple cu ajutorul operatiilor logice.

Luați în considerare operațiile logice de bază definite pe instrucțiuni. Toate corespund conectivelor folosite în limbajul natural.

Conjuncție

Luați în considerare două afirmații: A = „Fondatorul algebrei logicii este George Boole”, B = „Cercetarea lui Claude Shannon a făcut posibilă aplicarea algebrei logicii în tehnologia computerelor”. Evident, noua afirmație „Fondatorul algebrei logicii este George Boole, iar cercetările lui Claude Shannon au făcut posibilă aplicarea algebrei logicii în tehnologia computerelor” este adevărată numai dacă ambele afirmații inițiale sunt adevărate în același timp.

Următoarele semne sunt folosite pentru a scrie conjuncția: , , Și, &. De exemplu: A B, A B, A AND C, A&B.

O conjuncție poate fi descrisă ca un tabel, care se numește tabel de adevăr:

Tabelul de adevăr enumeră toate valorile posibile ale afirmațiilor originale (coloanele A și B), iar numerele binare corespunzătoare acestora, de regulă, sunt aranjate în ordine crescătoare: 00, 01, 10, 11. Ultima coloană conține rezultatul efectuării unei operații logice pentru operanzii corespunzători.

În caz contrar, conjuncția se numește înmulțire logică. Gândește-te de ce.

Disjuncție

Luați în considerare două afirmații: A = „Ideea de a folosi simbolismul matematic în logică îi aparține lui Gottfried Wilhelm Leibniz”, B = „Leibniz este fondatorul aritmeticii binare”. Evident, noua afirmație „Ideea de a folosi simbolismul matematic în logică îi aparține lui Gottfried Wilhelm Leibniz sau Leibniz este fondatorul aritmeticii binare” este falsă numai dacă ambele afirmații inițiale sunt false în același timp.

Stabiliți în mod independent adevărul sau falsitatea celor trei afirmații luate în considerare.

Următoarele semne sunt folosite pentru a înregistra disjuncția: v, |, SAU, +. De exemplu: AvB, A|B, A SAU B, A+B.

Disjuncția este definită de următorul tabel de adevăr:

În caz contrar, disjuncția se numește adunare logică. Gândește-te de ce.

Inversiunea

Următoarele semne sunt folosite pentru a scrie inversiunea: NU, ¬, ‾. De exemplu: NU, ¬, ‾.

Inversiunea este definită de următorul tabel de adevăr:

Inversiunea este cunoscută și sub denumirea de negație logică.

Negarea afirmației „Am un computer acasă” va fi afirmația „Nu este adevărat că am un computer acasă” sau, ceea ce este același în rusă, „Nu am un computer acasă”. Negarea afirmației „Nu știu chineză” va fi afirmația „Nu este adevărat că nu știu chineză” sau, care este același în rusă, „Știu chineză”. Negarea afirmației „Toți băieții de clasa a IX-a sunt elevi excelenți” este afirmația „Nu este adevărat că toți băieții de clasa a IX-a sunt elevi excelenți”, cu alte cuvinte, „Nu toți băieții de clasa a IX-a sunt excelenți elevi".

Astfel, atunci când construiți o negație la o afirmație simplă, fie se folosește expresia „nu este adevărat că...”, fie negația este construită la predicat, apoi particula „nu” este adăugată verbului corespunzător.

Orice declarație complexă poate fi scrisă ca o expresie logică - o expresie care conține variabile logice, semne de operații logice și paranteze. Operațiile logice într-o expresie logică sunt efectuate în următoarea ordine: inversare, conjuncție, disjuncție. Puteți modifica ordinea operațiilor prin plasarea parantezelor.

Exemplul 1. Fie A = „Cuvântul „cruiser” apare pe pagina web”, B = „Cuvântul „cuirasat” apare pe pagina web”. Se consideră un anumit segment al Internetului, care conține 5.000.000 de pagini Web. Aici afirmația A este adevărată pentru 4800 de pagini, afirmația B este adevărată pentru 4500 de pagini și afirmația A v B este adevărată pentru 7000 de pagini. Pentru câte pagini Web ar fi adevărate următoarele expresii și afirmații în acest caz?

a) NU (A SAU B);

c) Pagina Web conține cuvântul „cruiser” și nu conține cuvântul „cuirasat”.

Soluţie. Să descriem setul tuturor paginilor Web ale sectorului considerat al Internetului ca un cerc, în interiorul căruia vom plasa două cercuri: unul dintre ele corespunde setului de pagini Web, unde afirmația A este adevărată, al doilea - unde afirmația B este adevărată (fig. 1.3).

Orez. 1.3.
Reprezentarea grafică a seturilor de pagini Web

Să descriem grafic seturile de pagini Web pentru care expresiile și afirmația a) - c) sunt adevărate (Fig. 1.4)

Orez. 1.4.
Reprezentare grafică a unor seturi de pagini Web pentru care expresiile și afirmațiile a) - c) sunt adevărate

Schemele construite ne vor ajuta să răspundem la întrebările cuprinse în sarcină.

Expresia A SAU B este adevărată pentru 7.000 de pagini Web, pentru un total de 5.000.000 de pagini. Prin urmare, A SAU B este falsă pentru 4.993.000 de pagini Web. Cu alte cuvinte, pentru 4.993.000 de pagini Web, expresia NOT (A SAU B) este adevărată.

Expresia A v B este adevărată pentru acele pagini Web în care A este adevărat (4800), precum și pentru acele pagini Web în care B este adevărat (4500). Dacă toate paginile Web ar fi diferite, atunci A v B ar fi adevărat pentru 9300 (4800 + 4500) pagini Web. Dar, conform condiției, există doar 7000 de astfel de pagini Web. Aceasta înseamnă că pe 2300 (9300 - 7000) pagini Web ambele cuvinte apar în același timp. Prin urmare, expresia A & B este adevărată pentru 2300 de pagini Web.

Pentru a afla pentru câte pagini Web afirmația A este adevărată și afirmația B este falsă în același timp, scădeți 2300 din 4800. pagini.

Notați singur expresia logică corespunzătoare afirmației luate în considerare.

Site-ul web al Centrului Federal pentru Informații și Resurse Educaționale (http://fcoir.edu.ru/) conține modulul de informații „Declarație. Propoziții simple și complexe. Operații logice de bază. Familiarizarea cu această resursă vă va permite să vă extindeți înțelegerea subiectului studiat.

1.3.3. Construirea tabelelor de adevăr pentru expresii logice

Pentru o expresie logică, puteți construi un tabel de adevăr care arată ce valori ia expresia pentru toate seturile de valori ale variabilelor incluse în ea. Pentru a construi un tabel de adevăr, ar trebui să:

1. count n - numărul de variabile din expresie;
2. numărați numărul total de operații logice din expresie;
3. stabilește succesiunea de execuție a operațiilor logice, ținând cont de paranteze și priorități;
4. determinați numărul de coloane din tabel: numărul de variabile + numărul de operații;
5. completați antetul tabelului, incluzând variabilele și operațiunile din acesta, în conformitate cu succesiunea stabilită la paragraful 3;
6. determinați numărul de rânduri din tabel (excluzând antetul tabelului) m = 2n;
7. scrieți seturi de variabile de intrare, ținând cont de faptul că acestea sunt o serie întreagă de numere binare de n biți de la 0 la 2 n - 1;
8. completați tabelul pe coloane, efectuând operații logice în conformitate cu succesiunea stabilită.

Să construim un tabel de adevăr pentru expresia logică A v A & B. Are două variabile, două operații și mai întâi se realizează conjuncția și apoi disjuncția. În tabel vor fi patru coloane:

Seturile de variabile de intrare sunt numere întregi de la 0 la 3, reprezentate în cod binar de două cifre: 00, 01, 10, 11. Tabelul de adevăr completat arată astfel:

Rețineți că ultima coloană (rezultat) este aceeași cu coloana A. În acest caz, se spune că expresia logică A v A & B este echivalentă cu expresia logică A.

1.3.4. Proprietățile operațiilor booleene

Luați în considerare proprietățile de bază (legile) algebrei logicii.

Legile algebrei logicii pot fi demonstrate folosind tabele de adevăr.

Să demonstrăm legea distributivă pentru adunarea logică:

A v (B & C) = (A V B) & (A v C).

Coincidența coloanelor corespunzătoare expresiilor logice din stânga și dreapta egalității dovedește validitatea legii distributive pentru adunare logică.

Exemplul 2. Găsiți valoarea unei expresii logice pentru numărul X = 0.

Soluţie. Cu X = 0, obținem următoarea expresie logică: . Deoarece expresiile logice 0< 3, 0 < 2 истинны, то, подставив их значения в логическое выражение, получаем: 1&Т = 1&0 = 0.

1.3.5. Rezolvarea problemelor logice

Luați în considerare mai multe moduri de a rezolva probleme logice.

Sarcina 1. Kolya, Vasya și Seryozha și-au vizitat bunica vara. Într-o zi, unul dintre băieți a spart din greșeală vaza preferată a bunicii sale. La întrebarea cine a spart vaza, ei au răspuns următoarele:

Seryozha: 1) Nu m-am prăbușit. 2) Vasya nu s-a rupt.

Vasya: 3) Seryozha nu s-a rupt. 4) Kolya a spart vaza.

Kolya: 5) Nu m-am prăbușit. 6) Seryozha a spart vaza.

Bunica știa că unul dintre nepoții ei, să-i spunem sincer, a spus adevărul de ambele ori; al doilea, să-i spunem glumeț, de ambele ori spus o minciună; al treilea, să-l numim viclean, odată spus adevărul, iar altă dată - minciună. Care sunt numele celor adevărați, glumeților și vicleanului. Care dintre nepoți a spart vaza?

Soluţie. Fie K = „Kolya a spart vaza”, B = „Vasya a spart vaza”, C = „Seryozha a spart vaza”. Să facem un tabel de adevăr cu care vom prezenta afirmațiile fiecărui băiat 1 .

1 Ținând cont de faptul că vaza a fost spartă de un nepot, a fost posibil să se compileze nu întregul tabel, ci doar fragmentul acestuia care conține următoarele seturi de variabile de intrare: 001, 010, 100.

Pe baza a ceea ce știe bunica despre nepoți, ar trebui să căutați rânduri în tabel care conțin trei combinații de valori în orice ordine: 00, 11, 01 (sau 10). Există două astfel de rânduri în tabel (sunt marcate cu bifă). Potrivit celui de-al doilea dintre ei, vaza a fost spartă de Kolya și Vasya, ceea ce contrazice condiția. Potrivit primei rânduri găsite, Seryozha a spart vaza, s-a dovedit și viclean. Vasya s-a dovedit a fi un glumeț. Numele adevăratului nepot este Kolya.

Sarcina 2. Alla, Valya, Sima și Dasha participă la competiții de gimnastică. Fanii au speculat despre posibilii câștigători:

1. Sima va fi primul, Valya - al doilea;
2. Sima va fi al doilea, Dasha - al treilea;
3. Alla va fi al doilea, Dasha - al patrulea.

La finalul competiției, s-a dovedit că în fiecare dintre ipoteze, doar una dintre afirmații este adevărată, cealaltă este falsă. Ce loc a ocupat fiecare dintre fete în competiție dacă toate au ajuns în locuri diferite?

Soluţie. Luați în considerare afirmațiile simple:

C 1 = „Sim a câștigat primul loc”;

B 2 = „Valya a ocupat locul doi”;

C 2 = „Sima a ocupat locul doi”;

D 3 = „Dasha a ocupat locul trei”;

A 2 \u003d „Alla a ocupat locul doi”;

D 4 \u003d „Dasha a ocupat locul al patrulea”.

Deoarece în fiecare dintre cele trei ipoteze una dintre afirmații este adevărată, iar cealaltă este falsă, putem concluziona următoarele:

1. C 1 + B 2 \u003d 1, C 1 B 2 \u003d 0;
2. C 2 + D 3 \u003d 1, C 2 D 3 \u003d 0;
3. A 2 + D 4 \u003d 1, A 2 D 4 \u003d 0.

Produsul logic al afirmațiilor adevărate va fi adevărat:

(C 1 + B 2) (C 2 + D 3) (A 2 + D 4) = 1.

Pe baza legii distribuției, transformăm partea stângă a acestei expresii:

(C 1 C 2 + C 1 D 3 + B 2 C 2 + B 2 D 3) (A 2 + D 4) = 1.

Afirmația C 1 C 2 înseamnă că Sima a ocupat atât primul cât și al doilea loc. În funcție de starea problemei, această afirmație este falsă. Afirmația B 2 C 2 este de asemenea falsă. Ținând cont de legea operațiilor cu constanta 0, scriem:

(C 1 D 3 + B 2 D 3) (A 2 + D 4) = 1.

Transformarea în continuare a părții stângi a acestei egalități și excluderea afirmațiilor în mod deliberat false dau:

C 1 D 3 A 2 + C 1 D 3 D 4 + B 2 D 3 A 2 + B 2 D 3 D 4 \u003d 1.

C 1 D 3 A 2 \u003d 1.

Din ultima egalitate rezultă că C 1 \u003d 1, D 3 \u003d 1, A 2 \u003d 1. Aceasta înseamnă că Sima a ocupat primul loc, Alla - al doilea, Dasha - al treilea. În consecință, Valya a ocupat locul patru.

Puteți face cunoștință cu alte modalități de rezolvare a problemelor logice, precum și să participați la olimpiade de internet și competiții pentru rezolvarea acestora, pe site-ul „Matematică pentru școlari” (http://www.kenqyry.com/).

Pe site-ul http://www.kaser.com/ puteți descărca o versiune demo a unui puzzle logic Sherlock foarte util care dezvoltă abilități de logică și raționament.

1.3.6. Elemente logice

Algebra logicii este o ramură a matematicii care joacă un rol important în proiectarea dispozitivelor automate, dezvoltarea hardware și software pentru tehnologiile informației și comunicațiilor.

Știți deja că orice informație poate fi reprezentată într-o formă discretă - ca un set fix de valori individuale. Dispozitivele care procesează astfel de valori (semnale) sunt numite discrete. Un convertor discret care, după procesarea semnalelor binare, scoate la ieșire valoarea uneia dintre operațiile logice se numește element logic.

Pe fig. 1.5 prezintă simbolurile (circuitele) elementelor logice care implementează înmulțirea logică, adunarea și inversarea logică.

Fig 1.5.
Elemente logice

Elementul logic AND (conjunctor) implementează operația de înmulțire logică (Fig. 1.5, a). Unitatea de la ieșirea acestui element va apărea numai atunci când există unele la toate intrările.

Elementul logic OR (disjunctor) implementează operația de adunare logică (Fig. 1.5, b). Dacă cel puțin o intrare este una, atunci și ieșirea elementului va fi una.

Elementul logic NOT (invertor) implementează operația de negație (Fig. 1.5, c). Dacă elementul de intrare este O, atunci ieșirea este 1 și invers.

Dispozitivele computerizate care efectuează operații asupra numerelor binare și celulele care stochează date sunt circuite electronice formate din elemente logice separate. Aceste probleme vor fi discutate mai detaliat la cursul de informatică pentru clasele 10-11.

Exemplul 3. Să analizăm circuitul electronic, adică să aflăm ce semnal ar trebui să fie la ieșire pentru fiecare set posibil de semnale la intrări.

Soluţie. Toate combinațiile posibile de semnale de la intrările A la B vor fi introduse în tabelul de adevăr. Să urmărim transformarea fiecărei perechi de semnale pe măsură ce acestea trec prin elementele logice și să scriem rezultatul într-un tabel. Tabelul de adevăr completat descrie complet circuitul electronic considerat.

Tabelul de adevăr poate fi construit și după o expresie logică corespunzătoare unui circuit electronic. Ultimul element logic din circuitul luat în considerare este conjunctorul. Acesta primește semnale de la intrarea L și de la invertor. La rândul său, invertorul primește un semnal de la intrarea B. Astfel,

Lucrul cu simulatorul logic (http://kpolyakov.narod.ru/prog/logic.htm) vă va ajuta să obțineți o imagine mai completă a elementelor logice și a circuitelor electronice.

Cel mai important

O propoziție este o propoziție în orice limbă, al cărei conținut poate fi determinat fără ambiguitate ca adevărat sau fals.

Operații logice de bază definite peste enunțuri: inversare, conjuncție, disjuncție.

Tabele de adevăr pentru operațiile logice de bază:

La evaluarea expresiilor logice, acțiunile din paranteze sunt efectuate mai întâi. Prioritatea executării operațiilor logice:

Întrebări și sarcini

1.3.1. AFIRMAȚIE
1.3.2. OPERAȚII LOGICE
1.3.3. CONSTRUIREA TABELELOR DE ADEVĂR PENTRU EXPRESII LOGICE
1.3.4. PROPRIETĂȚI ALE OPERAȚIUNILOR LOGICE
1.3.5. REZOLVAREA PROBLEMELOR LOGICE
1.3.6. ELEMENTE LOGICE

1. Familiarizați-vă cu materialele de prezentare pentru paragraful conținute în suplimentul electronic la manual. Prezentarea completează informațiile conținute în textul paragrafului?

2. Explicați de ce următoarele propoziții nu sunt enunțuri.
1) Ce culoare este casa asta?
2) Numărul X nu depășește unu.
3) 4X+3.
4) Privește pe fereastră.
5) Bea suc de rosii!
6) Acest subiect este plictisitor.
7) Ricky Martin este cel mai popular cântăreț.
8) Ai fost la teatru?

3. Dați un exemplu de afirmații adevărate și false din biologie, geografie, informatică, istorie, matematică, literatură.

4. În următoarele enunţuri, evidenţiaţi enunţurile simple, notând fiecare dintre ele cu o literă; notează fiecare enunț compus folosind litere și semne ale operațiilor logice.
1) Numărul 376 este par și format din trei cifre.
2) Iarna, copiii merg la patinaj sau la schi.
3) Vom sărbători Anul Nou la dacha sau în Piața Roșie.
4) Nu este adevărat că Soarele se mișcă în jurul Pământului.
5) Pământul are forma unei mingi, care arată albastru din spațiu.
6) La lecția de matematică, elevii de liceu au răspuns la întrebările profesorului și au scris și lucrări independente.

5. Construiți negativele următoarelor afirmații.

6. Fie A \u003d „Orice îi plac lecțiile de matematică” și B \u003d „Orice îi plac lecțiile de chimie”. Exprimați următoarele formule într-un limbaj simplu:

7. Unele segmente ale rețelei de internet sunt formate din 1000 de site-uri. Serverul de căutare a compilat automat un tabel de cuvinte cheie pentru site-urile din acest segment. Iată fragmentul ei:

8. Construiți tabele de adevăr pentru următoarele expresii logice:

9. Dați dovada legilor logice luate în considerare în paragraf folosind tabele de adevăr.

10. În sistemul numeric zecimal sunt date trei numere: A=23, B=19, C=26. Convertiți A, B și C în sistemul numeric binar și efectuați operații logice pe biți (A v B) și C. Dați răspunsul în sistem de numere zecimal.

11. Găsiți semnificația expresiilor:

12. Găsiți valoarea expresiei logice (x
1) 1
2) 2
3) 3
4) 4
1) 0. 2) 0. 3) 1. 4) 1.

13. Fie A \u003d „Prima literă a numelui este o vocală”, B \u003d „A patra literă a numelui este o consoană”. Găsiți valoarea expresiei logice A v B pentru următoarele nume:
1) ELENA 2) VADIM 3) ANTON 4) FEDOR
1) 1. 2) 1. 3) 0. 4) 1.

14. Se tratează cazul lui John, Brown și Smith. Se știe că unul dintre ei a găsit și a ascuns comoara. Pe parcursul anchetei, fiecare dintre suspecți a făcut două declarații:
Smith: „Nu am făcut-o. Brown a făcut-o.”
John: „Brown nu este vinovat. Smith a făcut-o.”
Brown: Nu am făcut-o. John nu a făcut-o.”
Instanța a constatat că unul dintre ei a mințit de două ori, celălalt a spus adevărul de două ori, al treilea a mințit o dată, a spus adevărul o dată. Care suspect ar trebui achitat?
Răspuns: Smith și John.

15. Alyosha, Borya și Grisha au găsit un vas străvechi în pământ. Având în vedere descoperirea uimitoare, fiecare a făcut două presupuneri:
1) Alioșa: „Acest vas este grecesc și făcut în secolul al V-lea.”
2) Borya: „Acesta este un vas fenician și a fost făcut în secolul al III-lea”.
3) Grisha: „Acest vas nu este grecesc și a fost făcut în secolul al IV-lea.”
Profesorul de istorie le-a spus copiilor că fiecare dintre ei a avut dreptate doar una din cele două presupuneri. Unde și în ce secol a fost făcut vasul?
Răspuns: Vas fenician, realizat în secolul al V-lea.

16. Aflați ce semnal ar trebui să fie la ieșirea circuitului electronic pentru fiecare set posibil de semnale la intrări. Faceți o fișă de lucru a circuitului. Ce expresie logică descrie circuitul?