Capitolul 5 - Bazele logice ale computerelor

5.13. Cum de a rezolva problemele logice?

• mijloace de algebră a logicii;
• de masă;
• cu ajutorul raționamentului.

Să ne cunoaștem la rândul lor.

I. Soluția problemelor logice prin algebra logică

1. starea problemei este studiată;
2. se introduce un sistem de notații pentru pronunțări logice;
3. o formulă logică este construită care descrie conexiunile logice dintre toate afirmațiile despre starea problemei;
4. se determină valorile adevărului acestei formulări logice;
5. din valorile obținute ale adevărului formulei, valorile adevărului celor intrate Declarații logice pe baza cărora se face o concluzie cu privire la decizie.

Exemplul 1. Trei prieteni, fanii cursei de Formula 1, au susținut rezultatele etapei viitoare de curse.

# 151; Vei vedea, Schumacher nu va veni primul, # 151; a spus John. Primul va fi Hill.

# 151; Nu, câștigătorul va fi, ca întotdeauna, Schumacher, # 151; exclamă Nick. # 151; Și nu este nimic de spus despre Alesi, el nu ar trebui să fie primul.

Peter, căruia ia adresat Nick, era indignat:

# 151; Hill nu vede primul loc, dar Alesi pilotează cea mai puternică mașină.

La sfârșitul cursei sa dovedit că fiecare dintre cele două ipoteze ale celor doi prieteni a fost confirmată și ambele ipoteze ale celui de-al treilea dintre prieteni au fost greșite. Cine a câștigat stadiul cursei?

Soluția. Introducem notația pentru propozițiile logice:

W # 151; Schumacher va câștiga; X # 151; Hill va câștiga; A # 151; Alesi câștigă.

Replica lui Nick "Alesi piloți cea mai puternică mașină" nu conține nici o declarație despre locul pe care îl va lua acest cursant, deci în raționamentul ulterior nu este luată în considerare.

Fixați declarațiile fiecăruia dintre prieteni:

Având în vedere că ipotezele celor doi prieteni au fost confirmate și ipotezele celui de-al treilea sunt incorecte, vom scrie și vom simplifica declarația adevărată

Instrucțiunea este valabilă numai pentru W = 1, A = 0, X = 0.

Răspuns. Câștigătorul cursei a fost Schumacher.

Exemplul 2. Un anumit aventurier a călătorit într-o excursie în întreaga lume pe un iaht echipat cu un computer de bord. El a fost avertizat că cel mai adesea eșuează trei noduri de computer # 151; a. b. c. și a dat părțile necesare pentru înlocuire. Este posibil să se determine care nod ar trebui să fie înlocuit, poate prin lumina de semnalizare pe panoul de control. Becuri, de asemenea, exact trei: x. y și z.

1. dacă cel puțin unul dintre nodurile calculatorului este defect, atunci cel puțin una dintre luminile x este aprinsă. y. z;
2. dacă nodul a este defect. dar nodul este OK. atunci se aprinde becul y;
3. dacă nodul este defect. dar nodul b este OK. lumina y se aprinde. dar lumina x nu se aprinde;
4. dacă nodul b este defect. dar nodul c este OK. luminile x și y se aprind sau lumina x nu se aprinde;
5. dacă becul x este pornit și nodul a este fie defect. sau toate cele trei noduri a. b. c funcționează, atunci becul y este pornit.

În felul acesta, calculatorul sa stricat. Lampa x a fost aprinsă în panoul de control. După ce a studiat cu atenție instrucțiunile, călătorul a repara calculatorul. Dar, din acel moment până la sfârșitul călătoriei, el nu a fost lăsat neclintit. El și-a dat seama că instrucțiunea este imperfectă și că există cazuri în care nu-l va ajuta.

Ce noduri a înlocuit călătorul? Ce defecte a găsit în instrucțiuni?

Soluția. Introducem notația pentru propozițiile logice:

Regulile 1-5 sunt exprimate prin următoarele formule:

Formulele 1-5 sunt adevărate prin ipoteze, prin urmare, conjuncția lor este de asemenea adevărată:

Exprimând implicația prin disjuncție și negație (amintim că), obținem:

Substituind în această identitate valorile concrete ale adevărului x = 1, y = 0, z = 0, obținem:

Rezultă că a = 0, b = 1, c = 1.

Răspunsul la prima întrebare a problemei: trebuie să înlocuiți blocurile b și c; blocul a nu necesită înlocuire. Răspunsul la a doua întrebare a problemei se obține independent.

II. Rezolvarea problemelor logice în mod tabular

Folosind această metodă, condițiile care conțin sarcina și rezultatele raționamentului sunt fixate cu ajutorul tabelelor special compilate.

Exemplul 3. În orchestra simfonică au fost angajați trei muzicieni: Braun, Smith și Wesson, care pot interpreta vioara, fluiera, viola, clarinet, oboe și trompetă.

1. Smith este cel mai înalt;
2. jucând vioara mai puțin decât jucătorul care joacă flautul;
3. Redarea vioară și flaut și Brown ca pizza;
4. atunci când apare o ceartă între violonist și trumpetru, Smith le recompensează;
5. Brown nu știe să joace nici pe trompetă, nici pe oboi.

Ce instrumente se joacă fiecare dintre muzicieni, dacă fiecare are două instrumente?

Soluția. Noi compunem tabelul și reflectă condițiile din problemă în el, umplând celulele corespunzătoare cu cifrele 0 și 1, în funcție de dacă instrucțiunea corespunzătoare este falsă sau adevărată.

Deoarece muzicienii sunt trei, șase instrumente și fiecare are doar două instrumente, se pare că fiecare muzician joacă pe instrumente pe care alții nu le dețin.

Condiția 4 implică faptul că Smith nu joacă viola sau trompeta, dar din condițiile 3 și 5 Brown nu știe să cânte la vioară, flaut, trompetă și oboe. În consecință, instrumentele lui Brown # 151; viola și clarinet. Îl vom pune în masă și vom umple restul celulelor coloanelor "alt" și "clarinet" cu zerouri:

Răspuns: Brown joacă violul și clarinetul, Smith # 151; pe flaut și oboe, Wesson # 151; pe vioară și trâmbiță.

Exemplul 4. Trei colegi de clasă # 151; Vlad, Timur și Yura, s-au întâlnit la 10 ani după absolvire. Sa dovedit că unul dintre ei a devenit doctor, un alt fizician și un al treilea avocat. Unul a iubit turismul, o altă fugă, pasiunea celui de-al treilea # 151; rugby.

Yura a spus că nu are suficient timp pentru turism, deși sora lui # 151; singurul medic din familie, un turist inveter. Doctorul a spus că împărtășește entuziasmul unui coleg.

Este amuzant, dar doi dintre prietenii lor nu au o singură scrisoare cu numele lor în numele profesiilor și hobby-urilor lor.

Determina cine iubește în timpul liber și cine are ce profesie.

Soluția. Aici, datele originale sunt împărțite în triple (nume # 151; profesie # 151; hobby).

Din cuvintele lui Yura este clar că nu este interesat de turism și nu este doctor. Din cuvintele medicului rezultă că este un turist.

Scrisoarea "a", prezentă în cuvântul "doctor", indică faptul că Vlad nu este de asemenea doctor, de aici și medic # 151; Timur. În numele lui există literele "t" și "p", găsite în cuvântul "turism", de aici și al doilea dintre prieteni, în numele profesiei și hobby-urilor, pentru care nu există o scrisoare a numelui său # 151; Jura. Yura nu este nici avocat, nici jucător de rugby, deoarece numele său conține literele "yu" și "p". În consecință, avem în sfârșit:

Răspuns. Vlad # 151; avocat și jucător de rugby, Timur # 151; doctor și turist, Jura # 151; fizician și alergător.

Exemplul 5. Trei scriitoare a fiicelor, Doris Kay # 151; Judy, Iris și Linda sunt, de asemenea, foarte talentați. Au câștigat faima în diferite arte # 151; cântând, balet și cinema. Toți trăiesc în diferite orașe, așa că Doris le numește de multe ori la Paris, Roma și Chicago.

1. Judy nu locuieste in Paris, dar Linda # 151; nu în Roma;
2. Parisianul nu este un star de film;
3. cel care trăiește în Roma, cântăreața;
4. Linda este indiferentă față de balet.

Unde trăiește Iris și care este profesia ei?

Soluția. Vom compila masa și vom reflecta condițiile 1 și 4 în ea, umplând celulele cu cifre 0 și 1, în funcție de faptul dacă instrucțiunea corespunzătoare este falsă sau adevărată:

Apoi argumentăm după cum urmează. Din moment ce Linda nu locuieste in Roma, atunci, conform conditiei 3, ea nu este o cantareata. În celula corespunzătoare liniei "Linda" și în coloana "Cântări", setați 0.

De la masă, este clar că Linda este o actriță de film, iar Judy și Iris nu acționează în filme.

Conform condiției 2, parizianul nu este eliminat în film, prin urmare, Linda nu locuiește în Paris. Dar ea nu locuieste nici la Roma. Prin urmare, Linda trăiește în Chicago. Din moment ce Linda și Judy nu locuiesc în Paris, Iris locuieste acolo. Judy trăiește la Roma și, conform condiției 3, este cântăreață. Și din moment ce Linda este actriță de film, Iris este o balerină.

Ca urmare a umplerii treptate, obținem următorul tabel:

Răspuns. Iris balerina. Locuieste in Paris.

III. Rezolvarea problemelor logice prin raționament

Această metodă este de obicei rezolvată prin sarcini logice simple.

Exemplul 6. Vadim, Serghei și Mihail studiază diferite limbi străine: chineză, japoneză și arabă. Întrebat ce limbă fiecare dintre ei studiază, unul a răspuns: "Vadim studiază chinezii, Serghei nu studiază chinezii, iar Michael nu studiază arabă". Mai târziu, sa dovedit că în acest răspuns, doar o afirmație este adevărată, iar celelalte două sunt false. Ce limbă studiază fiecare dintre tineri?

1. Vadim studiază limba chineză;
2. Serghei nu studiază limba chineză;
3. Michael nu studiază arabă.

Dacă prima afirmație este adevărată, atunci a doua este adevărată, deoarece tinerii studiază limbi diferite. Aceasta contrazice condiția problemei, astfel încât prima afirmație este falsă.

Dacă a doua afirmație este adevărată, atunci prima și a treia trebuie să fie false. Se pare că nimeni nu studiază chinezi. Aceasta contrazice condiția, deci a doua afirmație este de asemenea falsă.

Rămâne să se considere că a treia afirmație este adevărată, iar prima și a doua # 151; fals. În consecință, Vadim nu studiază chinezii, studiile chineze Serghei.

Răspuns: Serghei studiază chinezii, Mihail # 151; Japoneză, Vadim # 151; Arabă.

Exemplul 7. În călătoria a cinci prieteni # 151; Anton, Boris, Vadim, Dima și Grisha, s-au familiarizat cu colegul călător. Ei au sugerat că îi ghicesc numele și că fiecare dintre ei a exprimat o afirmație adevărată și una falsă:

Dima spuse: - Numele meu de familie # 151; Mishin și numele lui Boris # 151; Khokhlov. Anton a spus: "Mishin # 151; acesta este numele meu de familie și numele de familie al lui Vadim # 151; Belkin. Boris spuse: - Numele lui Vadim # 151; Tikhonov, și numele meu de familie # 151; Mishin. "Vadim a spus:" Numele meu de familie # 151; Și Belkin, și numele de Grisha # 151; Cehov. "Grisha a spus:" Da, numele meu este Cehov și numele lui Anton # 151; Tikhonov. "

Care este numele fiecărui prieten?

Soluția. Să desemnează forma expresivă "tânărul cu numele A poartă numele de familie B" ca AB. unde literele A și B corespund literelor inițiale ale numelui și prenumelui.

Să presupunem mai întâi că adevăratul DM. Dar dacă e adevărat DM. atunci Anton și Boris ar trebui să aibă alte nume de familie, deci AM și BM sunt false. Dar dacă AM și BM sunt false, atunci WB și BT trebuie să fie adevărate. Dar WB și VT nu pot fi adevărate în același timp.

Deci, există un alt caz: adevărat BH. Acest caz duce la un lanț de concluzii:

BH adevărat BM fals BT adevărat AT fals MF adevărat WB fals AM adevărat.

Răspuns: Boris # 151; Khokhlov, Vadim # 151; Tikhonov, Grisha # 151; Cehov, Anton # 151; Mishin, Dima # 151; Belkin.

Exemplul 8. Miniștrii de externe ai Rusiei, ai Statelor Unite și ai Chinei au discutat, în spatele ușilor închise, proiectele de acorduri privind dezarmarea completă prezentate de fiecare țară. Răspunzând la întrebarea jurnaliștilor: "Cui proiect a fost adoptat?", Miniștrii au dat următoarele răspunsuri: Rusia # 151; "Proiectul nu este al nostru, proiectul nu este SUA";
statele Unite ale Americii # 151; "Proiectul nu este Rusia, proiectul Chinei";
China # 151; "Proiectul nu este al nostru, proiectul Rusiei".

Unul dintre ei (cel mai deschis) a spus de două ori adevărul; cel de-al doilea (cel mai secret) a spus de nenumărate ori, al treilea (precaut) a spus odată adevărul și altă dată # 151; neadevăr.

Determinați reprezentanții țării care sunt miniștri sinceri, secreți și precauți.

Soluția. Pentru comoditatea înregistrării, numim declarațiile diplomaților: Rusia # 151; "Proiectul nu este al nostru" (1), "Proiectul nu este SUA" (2);
statele Unite ale Americii # 151; "Proiectul nu este Rusia" (3), "Proiectul Chinei" (4);
China # 151; "Proiectul nu este al nostru" (5), "Proiectul Rusiei" (6).

Vom afla care ministru este cel mai deschis.

Dacă acesta este un ministru rus, atunci rezultă din justiție (1) și (2) că proiectul chinez a câștigat. Dar, apoi, ambele declarații ale ministrului american sunt, de asemenea, simple, care nu pot fi condiționate.

În cazul în care cel mai deschis # 151; atunci din nou ajungem că proiectul chinez a câștigat, deci ambele declarații ale ministrului rus sunt, de asemenea, adevărate, care nu pot fi condiționate.

Se pare că cel mai clar a fost ministrul chinez. Într-adevăr, din faptul că (5) și (6) sunt adevărate, rezultă că proiectul rus a câștigat. Și apoi se dovedește că din cele două afirmații ale ministrului rus, primul este fals, iar al doilea este adevărat. Ambele declarații ale secretarului american sunt incorecte.

Răspuns: Ministrul chinez a fost mai deschis, mai precaut # 151; Rusă, mai secretă # 151; secretarul de stat al Statelor Unite.

Articole similare

• Algebra logicii și bazele logice ale calculatorului, planeta informatică

• Revizuirea capitolului 1 al lucrării de bază al economiei instituționale 1

Trimiteți-le prietenilor: