Kā atrisināt loģisko vienādojumu sistēmas USE. Loģika. Loģiskās funkcijas. Vienādojumu risināšana

Kā atrisināt dažus uzdevumus datorzinātņu eksāmena A un B sadaļā

Nodarbība #3. Loģika. Loģiskās funkcijas. Vienādojumu risināšana

Liela daļa vienotā valsts eksāmena uzdevumu ir veltīti priekšlikuma loģikai. Lai atrisinātu lielāko daļu no tiem, pietiek zināt propozicionālās loģikas pamatlikumus, zināšanas par viena un divu mainīgo loģisko funkciju patiesuma tabulām. Es došu propozicionālās loģikas pamatlikumus.

Disjunkcijas un konjunkcijas komutativitāte:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Sadales likums par disjunkciju un konjunkciju:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Nolieguma noliegums:
¬(¬a) ≡ a
Konsekvence:
a ^ ¬а ≡ nepatiess
Ekskluzīva trešā:
a ˅ ¬а ≡ taisnība
De Morgana likumi:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Vienkāršošana:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ patiess ≡ a
a ˄ nepatiess ≡ nepatiess
Absorbcija:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
Implikācijas aizstāšana
a → b ≡ ¬a ˅ b
Identitātes aizstāšana
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Loģisko funkciju attēlojums

Jebkuru n mainīgo loģisko funkciju - F(x 1, x 2, ... x n) var norādīt ar patiesības tabulu. Šādā tabulā ir 2n mainīgo kopas, katrai no kurām ir norādīta šīs kopas funkcijas vērtība. Šī metode ir laba, ja mainīgo lielumu skaits ir salīdzinoši mazs. Jau n > 5 attēlojums kļūst slikti redzams.

Vēl viens veids ir definēt funkciju pēc kādas formulas, izmantojot zināmas diezgan vienkāršas funkcijas. Funkciju sistēmu (f 1, f 2, ... f k) sauc par pilnīgu, ja jebkuru loģisku funkciju var izteikt ar formulu, kas satur tikai funkcijas f i.

Funkciju sistēma (¬, ˄, ˅) ir pabeigta. 9. un 10. likumi ir piemēri, kas parāda, kā implikācija un identitāte tiek izteikta ar noliegumu, konjunkciju un disjunkciju.

Faktiski divu funkciju sistēma – noliegums un konjunkcija vai noliegums un disjunkcija – arī ir pilnīga. No De Morgana likumiem izriet idejas, kas ļauj izteikt konjunkciju ar noliegumu un disjunkciju un attiecīgi izteikt disjunkciju ar noliegumu un konjunkciju:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradoksāli, bet sistēma, kas sastāv tikai no vienas funkcijas, ir pabeigta. Ir divas bināras funkcijas - antikonjunkcija un antidisjunkcija, ko sauc par Pīrsa bultiņu un Šēfera gājienu, kas attēlo dobu sistēmu.

Programmēšanas valodu pamatfunkcijas parasti ietver identitāti, noliegšanu, konjunkciju un disjunkciju. Vienotā valsts eksāmena problēmās līdztekus šīm funkcijām bieži tiek atrasta nozīme.

Apskatīsim dažas vienkāršas problēmas, kas saistītas ar loģiskām funkcijām.

15. problēma:

Ir dots patiesības tabulas fragments. Kura no trim dotajām funkcijām atbilst šim fragmentam?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

(X 1 → X 2) ˄ ¬ X 3 ˅ X 4
(¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funkcijas numurs 3.

Lai atrisinātu problēmu, ir jāzina pamatfunkciju patiesības tabulas un jāatceras darbību prioritātes. Atgādināšu, ka konjunkcijai (loģiskajai reizināšanai) ir augstāka prioritāte un tā tiek izpildīta agrāk nekā disjunkcijai (loģiskā saskaitīšana). Veicot aprēķinus, var viegli pamanīt, ka funkcijām ar skaitļiem 1 un 2 trešajā kopā ir vērtība 1 un šī iemesla dēļ tās neatbilst fragmentam.

16. problēma:

Kurš no dotajiem skaitļiem atbilst nosacījumam:

(cipari, sākot no nozīmīgākā cipara, ir dilstošā secībā) → (skaitlis - pāra) ˄ (zems cipars - pāra) ˄ (augstais cipars - nepāra)

Ja ir vairāki šādi skaitļi, norādiet lielāko.

13579
97531
24678
15386

Nosacījumu apmierina cipars 4.

Pirmie divi skaitļi neatbilst nosacījumam, jo zemākais cipars ir nepāra. Nosacījumu konjunkcija ir nepatiesa, ja viens no savienojuma nosacījumiem ir nepatiess. Trešajam skaitlim nav izpildīts nosacījums par augstāko ciparu. Ceturtajam numuram ir izpildīti nosacījumi, kas izvirzīti skaitļa mazajam un augstajam ciparam. Arī savienojuma pirmais termins ir patiess, jo implikācija ir patiesa, ja tās premisa ir nepatiesa, kā tas ir šajā gadījumā.

17. problēma: divi liecinieki sniedza šādas liecības:

Pirmais liecinieks: ja A ir vainīgs, tad B ir vēl vairāk vainīgs, un C ir nevainīgs.

Otrais liecinieks: Divi ir vainīgi. Un viens no atlikušajiem noteikti ir vainīgs un vainīgs, bet es nevaru pateikt, kurš tieši.

Kādus secinājumus par A, B un C vainu var izdarīt no liecībām?

Atbilde: No liecības izriet, ka A un B ir vainīgi, bet C ir nevainīgs.

Risinājums: Protams, atbildi var sniegt, balstoties uz veselo saprātu. Bet paskatīsimies, kā to var izdarīt stingri un formāli.

Pirmā lieta, kas jādara, ir formalizēt paziņojumus. Ieviesīsim trīs loģiskos mainīgos - A, B un C, katram no kuriem ir vērtība true (1), ja vainīgs ir attiecīgais aizdomās turamais. Tad pirmā liecinieka liecība tiek sniegta pēc formulas:

A → (B ˄ ¬C)

Otrā liecinieka liecība tiek sniegta pēc formulas:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Tiek pieņemts, ka abu liecinieku liecības ir patiesas un atspoguļo atbilstošo formulu savienojumu.

Izveidosim patiesības tabulu šiem lasījumiem:

A	B	C	F 1	F 2	F 1˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Kopsavilkuma pierādījumi ir patiesi tikai vienā gadījumā, kas noved pie skaidras atbildes - A un B ir vainīgi, un C ir nevainīgs.

No šīs tabulas analīzes arī izriet, ka otrā liecinieka liecībai ir informatīvāka nozīme. No viņa liecības patiesības izriet tikai divas lietas: iespējamie varianti- A un B ir vainīgi, un C ir nevainīgi, vai A un C ir vainīgi, un B ir nevainīgi. Pirmā liecinieka liecība ir mazāk informatīva - ir 5 dažādi varianti, kas atbilst viņa liecībām. Kopā abu liecinieku liecības sniedz skaidru atbildi par aizdomās turamo vainu.

Loģiskie vienādojumi un vienādojumu sistēmas

Pieņemsim, ka F(x 1, x 2, …x n) ir n mainīgo loģiskā funkcija. Loģiskais vienādojums izskatās šādi:

F(x 1, x 2, … x n) = C,

Konstantei C ir vērtība 1 vai 0.

Loģiskam vienādojumam var būt no 0 līdz 2 n dažādu risinājumu. Ja C ir vienāds ar 1, tad risinājumi ir visas tās mainīgo kopas no patiesības tabulas, kurām funkcija F iegūst vērtību true (1). Atlikušās kopas ir C vienādojuma atrisinājumi, vienāds ar nulli. Jūs vienmēr varat ņemt vērā tikai formas vienādojumus:

F(x 1 , x 2 , …x n) = 1

Patiešām, dosim vienādojumu:

F(x 1, x 2, … x n) = 0

Šajā gadījumā mēs varam pāriet uz līdzvērtīgu vienādojumu:

¬F(x 1 , x 2 , …x n) = 1

Apsveriet sistēmu k loģiskie vienādojumi:

F1 (x 1, x 2, …x n) = 1

F2 (x 1, x 2, …x n) = 1

F k (x 1 , x 2 , …x n) = 1

Sistēmas risinājums ir mainīgo lielumu kopa, uz kuras ir izpildīti visi sistēmas vienādojumi. Runājot par loģiskajām funkcijām, lai iegūtu loģisko vienādojumu sistēmas risinājumu, jāatrod kopa, kurā ir patiesa loģiskā funkcija Ф, kas attēlo sākotnējo funkciju F konjunkciju:

Ф = F 1 ˄ F 2 ˄ … F k

Ja mainīgo skaits ir mazs, piemēram, mazāks par 5, tad nav grūti izveidot patiesības tabulu funkcijai Ф, kas ļauj pateikt, cik sistēmai ir risinājumu un kādas ir kopas, kas nodrošina risinājumus.

Dažās USE problēmās, meklējot risinājumus loģisko vienādojumu sistēmai, mainīgo skaits sasniedz 10. Tad patiesības tabulas izveidošana kļūst par gandrīz neiespējamu uzdevumu. Problēmas risināšanai nepieciešama cita pieeja. Patvaļīgai vienādojumu sistēmai nav citas vispārīgas metodes, izņemot uzskaitīšanu, kas ļautu atrisināt šādas problēmas.

Eksāmenā piedāvātajās problēmās risinājums parasti balstās uz vienādojumu sistēmas specifikas ņemšanu vērā. Es atkārtoju, ka, izņemot visu mainīgo lielumu kopas opciju izmēģināšanu, nav vispārēja veida, kā problēmu atrisināt. Risinājums jābūvē, balstoties uz sistēmas specifiku. Bieži vien ir lietderīgi veikt vienādojumu sistēmas iepriekšēju vienkāršošanu, izmantojot zināmus loģikas likumus. Vēl viens noderīgs paņēmiens šīs problēmas risināšanai ir šāds. Mūs neinteresē visas kopas, bet tikai tās, kurās funkcijai Ф ir vērtība 1. Tā vietā, lai izveidotu pilnīgu patiesības tabulu, mēs izveidosim tās analogu - bināro lēmumu koku. Katrs šī koka zars atbilst vienam atrisinājumam un norāda kopu, uz kuras funkcijai Ф ir vērtība 1. Zaru skaits lēmumu kokā sakrīt ar vienādojumu sistēmas atrisinājumu skaitu.

Es paskaidrošu, kas ir binārais lēmumu koks un kā tas tiek veidots, izmantojot vairāku problēmu piemērus.

18. problēma

Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas apmierina divu vienādojumu sistēmu?

Atbilde: Sistēmai ir 36 dažādi risinājumi.

Risinājums: vienādojumu sistēma ietver divus vienādojumus. Atradīsim atrisinājumu skaitu pirmajam vienādojumam atkarībā no 5 mainīgajiem - x 1, x 2, ...x 5. Pirmo vienādojumu savukārt var uzskatīt par 5 vienādojumu sistēmu. Kā parādīts, vienādojumu sistēma faktiski attēlo loģisko funkciju savienojumu. Ir arī otrādi: nosacījumu konjunkciju var uzskatīt par vienādojumu sistēmu.

Izveidosim lēmumu koku implikācijai (x1→ x2) - savienojuma pirmajam loceklim, ko var uzskatīt par pirmo vienādojumu. Lūk, kā izskatās šī koka grafiskais attēlojums:

Koks sastāv no diviem līmeņiem atbilstoši mainīgo skaitam vienādojumā. Pirmais līmenis apraksta pirmo mainīgo X 1 . Divi šī līmeņa atzari atspoguļo šī mainīgā iespējamās vērtības - 1 un 0. Otrajā līmenī koka zari atspoguļo tikai tās iespējamās mainīgā X 2 vērtības, kurām vienādojums ir patiess. Tā kā vienādojums norāda implikāciju, atzaram, kurā X 1 ir vērtība 1, šajā atzarā X 2 ir jābūt vērtībai 1. Atzars, kurā X 1 ir vērtība 0, veido divus zarus ar vērtībām X 2 vienāds ar 0 un 1 Konstruētais koks definē trīs risinājumus, uz kuriem implikācija X 1 → X 2 iegūst vērtību 1. Uz katra zara tiek izrakstīta atbilstoša mainīgo vērtību kopa, kas dod vienādojuma atrisinājumu.

Šīs kopas ir: ((1, 1), (0, 1), (0, 0))

Turpināsim lēmumu koka veidošanu, pievienojot šādu vienādojumu ar sekojošu implikāciju X 2 → X 3 . Mūsu vienādojumu sistēmas specifika ir tāda, ka katrā jaunajā sistēmas vienādojumā tiek izmantots viens mainīgais no iepriekšējā vienādojuma, pievienojot vienu jaunu mainīgo. Tā kā mainīgajam X 2 jau ir vērtības kokā, tad visos zaros, kur mainīgā X 2 vērtība ir 1, arī mainīgajam X 3 būs vērtība 1. Šādiem zariem koka konstrukcija turpina uz nākamo līmeni, bet jauni zari neparādās. Viena atzara, kurā mainīgajam X 2 ir vērtība 0, sazarosies divās atzaros, kur mainīgais X 3 saņems vērtības 0 un 1. Tādējādi katra jauna vienādojuma pievienošana, ņemot vērā tā specifiku, pievieno vienu risinājumu. Sākotnējais pirmais vienādojums:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
ir 6 risinājumi. Lūk, kā izskatās šī vienādojuma pilns lēmumu koks:

Mūsu sistēmas otrais vienādojums ir līdzīgs pirmajam:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Vienīgā atšķirība ir tā, ka vienādojumā ir izmantoti Y mainīgie. Šim vienādojumam ir arī 6 risinājumi. Tā kā katru mainīgo X i risinājumu var apvienot ar katru mainīgo Y j risinājumu, kopējais risinājumu skaits ir 36.

Ņemiet vērā, ka konstruētais lēmumu koks dod ne tikai risinājumu skaitu (atbilstoši zaru skaitam), bet arī pašus risinājumus, kas uzrakstīti uz katra koka zara.

19. problēma

Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

Šis uzdevums ir iepriekšējā uzdevuma modifikācija. Atšķirība ir tāda, ka tiek pievienots vēl viens vienādojums, kas attiecas uz mainīgajiem X un Y.

No vienādojuma X 1 → Y 1 izriet, ka, ja X 1 ir vērtība 1 (viens šāds risinājums pastāv), tad arī Y 1 ir vērtība 1. Tādējādi ir viena kopa, kurā X 1 un Y 1 ir vērtības 1. Kad X 1 ir vienāds ar 0, Y 1 var būt jebkura vērtība, gan 0, gan 1. Tāpēc katra kopa ar X 1, kas ir vienāda ar 0, un šādas kopas ir 5, atbilst visām 6 kopām ar Y mainīgajiem. Tāpēc kopējais risinājumu skaits ir 31 .

20. problēma

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Risinājums: atceroties pamata ekvivalences, mēs rakstām vienādojumu šādi:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Ietekmju cikliskā ķēde nozīmē, ka mainīgie ir identiski, tāpēc mūsu vienādojums ir līdzvērtīgs vienādojumam:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Šim vienādojumam ir divi risinājumi, ja visi X i ir 1 vai 0.

21. problēma

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Risinājums: Tāpat kā 20. uzdevumā, mēs pārejam no cikliskām sekām uz identitātēm, pārrakstot vienādojumu šādā formā:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Izveidosim lēmumu koku šim vienādojumam:

22. problēma

Cik atrisinājumu ir šādai vienādojumu sistēmai?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Atbilde: 64

Risinājums: pāriesim no 10 mainīgajiem uz 5 mainīgajiem, ieviešot šādas mainīgo izmaiņas:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Tad pirmais vienādojums būs šāds:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Vienādojumu var vienkāršot, ierakstot to šādi:

(Y 1 ≡ Y 2) = 0

Pārejot uz tradicionālo formu, mēs rakstām sistēmu pēc formas vienkāršošanas:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Šīs sistēmas lēmumu koks ir vienkāršs un sastāv no diviem zariem ar mainīgām mainīgajām vērtībām:

Atgriežoties pie sākotnējiem X mainīgajiem, ņemiet vērā, ka katrai Y mainīgā vērtībai ir 2 vērtības X mainīgajos, tāpēc katrs Y mainīgā risinājums ģenerē 2 5 risinājumus X mainīgajos 5 risinājumi, tātad kopējais risinājumu skaits ir 64.

Kā redzat, katrai vienādojumu sistēmas risināšanas problēmai ir nepieciešama sava pieeja. Izplatīts paņēmiens ir veikt līdzvērtīgas transformācijas, lai vienkāršotu vienādojumus. Izplatīta metode ir lēmumu koku konstruēšana. Izmantotā pieeja daļēji atgādina patiesības tabulas izveidošanu ar īpatnību, ka tiek konstruētas ne visas iespējamo mainīgo vērtību kopas, bet tikai tās, kurām funkcijai ir vērtība 1 (true). Bieži vien piedāvātajās problēmās nav nepieciešams izveidot pilnīgu lēmumu koku, jo jau tagad sākuma stadija ir iespējams izveidot jaunu zaru parādīšanās modeli katrā nākamajā līmenī, kā tas tika darīts, piemēram, 18. uzdevumā.

Kopumā problēmas, kas saistītas ar risinājumu meklēšanu loģisko vienādojumu sistēmai, ir labi matemātiski vingrinājumi.

Ja problēmu ir grūti atrisināt manuāli, tad risinājumu var uzticēt datoram, uzrakstot atbilstošu programmu vienādojumu un vienādojumu sistēmu risināšanai.

Uzrakstīt šādu programmu nav grūti. Šāda programma viegli tiks galā ar visiem Vienotajā valsts eksāmenā piedāvātajiem uzdevumiem.

Savādi, bet uzdevums atrast risinājumus loģisko vienādojumu sistēmām datoram ir sarežģīts, un izrādās, ka datoram ir savas robežas. Dators var diezgan viegli tikt galā ar uzdevumiem, kuros mainīgo lielumu skaits ir 20-30, taču tas sāks ilgi domāt par problēmām lielāks izmērs. Fakts ir tāds, ka funkcija 2 n, kas nosaka kopu skaitu, ir eksponenciāls, kas strauji pieaug, palielinoties n. Tik ātri, ka parasts personālais dators nevar tikt galā ar uzdevumu, kuram dienā ir 40 mainīgie.

Programma C# valodā loģisko vienādojumu risināšanai

Loģisko vienādojumu risināšanas programmas rakstīšana ir noderīga daudzu iemeslu dēļ, kaut vai tāpēc, ka varat to izmantot, lai pārbaudītu sava vienotā valsts eksāmena pārbaudes uzdevumu risinājuma pareizību. Vēl viens iemesls ir tas, ka šāda programma ir lielisks programmēšanas uzdevuma piemērs, kas atbilst C kategorijas uzdevumu prasībām vienotajā valsts eksāmenā.

Programmas izveides ideja ir vienkārša - tās pamatā ir pilnīga visu iespējamo mainīgo vērtību kopu meklēšana. Tā kā konkrētam loģiskam vienādojumam vai vienādojumu sistēmai ir zināms mainīgo lielumu skaits n, tad zināms arī kopu skaits - 2 n, kuras ir jāsakārto. Izmantojot C# valodas pamatfunkcijas – noliegumu, disjunkciju, konjunkciju un identitāti, nav grūti uzrakstīt programmu, kas noteiktai mainīgo kopai aprēķina loģiskam vienādojumam vai vienādojumu sistēmai atbilstošās loģiskās funkcijas vērtību. .

Šādā programmā jums ir jāizveido cilpa, pamatojoties uz kopu skaitu, pati kopa jāveido cilpas pamattekstā, pamatojoties uz kopas numuru, jāaprēķina šīs kopas funkcijas vērtība un, ja šī vērtība ir 1, tad kopa dod vienādojuma atrisinājumu.

Vienīgās grūtības, kas rodas, ieviešot programmu, ir saistītas ar uzdevumu pašam ģenerēt mainīgo vērtību kopu, pamatojoties uz iestatīto numuru. Šīs problēmas skaistums ir tāds, ka šis šķietami sarežģītais uzdevums faktiski ir saistīts ar vienkāršu problēmu, kas jau ir radusies daudzas reizes. Patiešām, pietiek saprast, ka mainīgo vērtību kopa, kas atbilst skaitlim i, kas sastāv no nullēm un vieniniekiem, ir skaitļa i binārais attēlojums. Tātad sarežģītais uzdevums iegūt mainīgo vērtību kopu pēc iestatītā skaitļa tiek samazināts līdz pazīstamajam uzdevumam pārvērst skaitli binārā.

Šādi izskatās funkcija C#, kas atrisina mūsu problēmu:

///

/// programma risinājumu skaita skaitīšanai

/// loģiskais vienādojums (vienādojumu sistēma)

///

/// loģiskā funkcija — metode,

/// kuras parakstu norāda DF delegāts

///

/// mainīgo lielumu skaits

/// risinājumu skaits

statisks int. Atrisiniet vienādojumus (DF jautri, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); //komplektu skaits

int p = 0, q = 0, k = 0;

//Pabeigt meklēšanu pēc kopu skaita

for (int i = 0; i< m; i++)

//Nākamās kopas veidošana - komplekts,

//norāda skaitļa i binārais attēlojums

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Aprēķināt funkcijas vērtību komplektā

Lai saprastu programmu, ceru, ka programmas idejas skaidrojumi un komentāri tās tekstā ir pietiekami. Es pievērsīšos tikai dotās funkcijas nosaukuma izskaidrošanai. Funkcijai SolveEquations ir divi ievades parametri. Funkcijas parametrs norāda loģisku funkciju, kas atbilst atrisināmajam vienādojumam vai vienādojumu sistēmai. Parametrs n norāda jautro mainīgo skaitu. Rezultātā funkcija SolveEquations atgriež loģiskās funkcijas risinājumu skaitu, tas ir, to kopu skaitu, kurās funkcija novērtē kā patiesu.

Skolēniem ir raksturīgi, ja kāda funkcija F(x) ievades parametrs x ir aritmētiskā, virknes vai Būla tipa mainīgais. Mūsu gadījumā tiek izmantots jaudīgāks dizains. Funkcija SolveEquations attiecas uz augstākas kārtas funkcijām - F(f) tipa funkcijām, kuru parametri var būt ne tikai vienkārši mainīgie, bet arī funkcijas.

Funkciju klase, ko var nodot kā parametru funkcijai SolveEquations, ir norādīta šādi:

delegate bool DF(bool vars);

Šai klasei pieder visas funkcijas, kuras kā parametrs tiek nodotas loģisko mainīgo vērtību kopai, ko nosaka vars masīvs. Rezultāts ir Būla vērtība, kas attēlo šīs kopas funkcijas vērtību.

Visbeidzot, šeit ir programma, kas izmanto SolveEquations funkciju, lai atrisinātu vairākas loģisko vienādojumu sistēmas. Funkcija SolveEquations ir daļa no tālāk norādītās ProgrammCommon klases:

klases ProgrammCommon

delegate bool DF(bool vars);

statiskā tukšums Galvenā (stīgu args)

Console.WriteLine("Un funkcijas - " +

Atrisiniet vienādojumus (Jautri, 2));

Console.WriteLine("Funkcijai ir 51 risinājums - " +

Atrisiniet vienādojumus (Fun51, 5));

Console.WriteLine("Funkcijai ir 53 risinājumi - " +

Atrisiniet vienādojumus (Fun53, 10));

statisks bool FunAnd(bool vars)

atgriezties vars && vars;

statiskā bool Fun51 (bool vars)

f = f && (!vars || vars);

statiskā bool Fun53 (bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Lūk, kā izskatās šīs programmas risinājuma rezultāti:

10 uzdevumi patstāvīgam darbam

Kuras no trim funkcijām ir līdzvērtīgas:
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
Dots fragments no patiesības tabulas:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Kurai no trim funkcijām šis fragments atbilst:

(X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
Žūrijas sastāvā ir trīs cilvēki. Lēmums ir pieņemts, ja par to nobalso žūrijas priekšsēdētājs, un to atbalsta vismaz viens no žūrijas locekļiem. Pretējā gadījumā lēmums netiek pieņemts. Izveidojiet loģisku funkciju, kas formalizē lēmumu pieņemšanas procesu.
X uzvar pār Y, ja četru monētu mešanas rezultātā trīs reizes tiek iegūtas galviņas. Definējiet loģisku funkciju, kas apraksta X izmaksu.
Vārdi teikumā ir numurēti, sākot no viena. Uzskata, ka teikums ir pareizi uzbūvēts, ja tiek ievēroti šādi noteikumi:
1. Ja pāra skaitļa vārds beidzas ar patskaņu, tad nākamajam vārdam, ja tāds pastāv, jāsākas ar patskaņu.
2. Ja nepāra skaitļa vārds beidzas ar līdzskaņu, tad nākamajam vārdam, ja tāds pastāv, jāsākas ar līdzskaņu un jābeidzas ar patskaņi.
  Kuri no šiem teikumiem ir pareizi izveidoti:
3. Mamma mazgāja Mašu ar ziepēm.
4. Līderis vienmēr ir modelis.
5. Patiesība ir laba, bet laime ir labāka.
Cik atrisinājumu ir vienādojumam:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Uzskaitiet visus vienādojuma risinājumus:
(a → b) → c = 0
Cik atrisinājumu ir šādai vienādojumu sistēmai:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1
Cik atrisinājumu ir vienādojumam:
(((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Atbildes uz problēmām:

Funkcijas b un c ir līdzvērtīgas.
Fragments atbilst funkcijai b.
Lai loģiskais mainīgais P iegūst vērtību 1, kad žūrijas priekšsēdētājs balso “par” lēmumu. Mainīgie lielumi M 1 un M 2 atspoguļo žūrijas locekļu viedokli. Loģisko funkciju, kas nosaka pozitīva lēmuma pieņemšanu, var uzrakstīt šādi:
P ˄ (M 1 ˅ M 2)
Ļaujiet loģiskajam mainīgajam P i pieņemt vērtību 1, kad i-tā monētas mešana piezemējas uz galvām. Loģisko funkciju, kas nosaka izmaksu X, var uzrakstīt šādi:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
Teikums b.
Vienādojumam ir 3 risinājumi: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Ļaut būt n mainīgo loģiskā funkcija. Loģiskais vienādojums izskatās šādi:

Konstantei C ir vērtība 1 vai 0.

Loģiskajam vienādojumam var būt no 0 līdz dažādiem risinājumiem. Ja C ir vienāds ar 1, tad risinājumi ir visas tās mainīgo kopas no patiesības tabulas, kurām funkcija F iegūst vērtību true (1). Atlikušās kopas ir vienādojuma atrisinājumi ar C vienādu ar nulli. Jūs vienmēr varat ņemt vērā tikai formas vienādojumus:

Patiešām, dosim vienādojumu:

Šajā gadījumā mēs varam pāriet uz līdzvērtīgu vienādojumu:

Apsveriet k loģisko vienādojumu sistēmu:

Ja mainīgo skaits ir mazs, piemēram, mazāks par 5, tad nav grūti konstruēt funkcijas patiesības tabulu, kas ļauj pateikt, cik sistēmai ir risinājumu un kādas ir kopas, kas nodrošina risinājumus.

Eksāmenā piedāvātajās problēmās risinājums parasti balstās uz vienādojumu sistēmas specifikas ņemšanu vērā. Es atkārtoju, ka, izņemot visu mainīgo lielumu kopas opciju izmēģināšanu, nav vispārēja veida, kā problēmu atrisināt. Risinājums jābūvē, balstoties uz sistēmas specifiku. Bieži vien ir lietderīgi veikt vienādojumu sistēmas iepriekšēju vienkāršošanu, izmantojot zināmus loģikas likumus. Vēl viens noderīgs paņēmiens šīs problēmas risināšanai ir šāds. Mūs neinteresē visas kopas, bet tikai tās, kurās funkcijai ir vērtība 1. Tā vietā, lai izveidotu pilnīgu patiesības tabulu, mēs izveidosim tās analogu - bināro lēmumu koku. Katrs šī koka zars atbilst vienam atrisinājumam un norāda kopu, kurā funkcijai ir vērtība 1. Zaru skaits lēmumu kokā sakrīt ar vienādojumu sistēmas atrisinājumu skaitu.

Es paskaidrošu, kas ir binārais lēmumu koks un kā tas tiek veidots, izmantojot vairāku problēmu piemērus.

18. problēma

Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas apmierina divu vienādojumu sistēmu?

Atbilde: Sistēmai ir 36 dažādi risinājumi.

Risinājums: vienādojumu sistēma ietver divus vienādojumus. Atradīsim atrisinājumu skaitu pirmajam vienādojumam atkarībā no 5 mainīgajiem - . Pirmo vienādojumu savukārt var uzskatīt par 5 vienādojumu sistēmu. Kā parādīts, vienādojumu sistēma faktiski attēlo loģisko funkciju savienojumu. Patiess ir arī apgrieztais apgalvojums - nosacījumu konjunkciju var uzskatīt par vienādojumu sistēmu.

Izveidosim lēmumu koku implikācijai () - savienojuma pirmajam loceklim, ko var uzskatīt par pirmo vienādojumu. Šādi izskatās šī koka grafiskais attēlojums

Koks sastāv no diviem līmeņiem atbilstoši mainīgo skaitam vienādojumā. Pirmais līmenis apraksta pirmo mainīgo. Divi šī līmeņa zari atspoguļo šī mainīgā iespējamās vērtības - 1 un 0. Otrajā līmenī koka zari atspoguļo tikai tās iespējamās mainīgā vērtības, kurām vienādojums ir novērtēts kā patiess. Tā kā vienādojums nosaka implikāciju, atzaram, kura vērtība ir 1, ir jābūt vērtībai 1. Atzars, kura vērtība ir 0, ģenerē divus zarus ar vērtībām, kas vienādas ar 0 un 1. koks norāda trīs risinājumus, no kuriem imlikācija iegūst vērtību 1. Uz katra zara tiek izrakstīta atbilstoša mainīgo vērtību kopa, dodot vienādojuma atrisinājumu.

Šīs kopas ir: ((1, 1), (0, 1), (0, 0))

Turpināsim lēmumu koka veidošanu, pievienojot šādu vienādojumu, sekojošu implikāciju. Mūsu vienādojumu sistēmas specifika ir tāda, ka katrā jaunajā sistēmas vienādojumā tiek izmantots viens mainīgais no iepriekšējā vienādojuma, pievienojot vienu jaunu mainīgo. Tā kā mainīgajam kokā jau ir vērtības, tad visos zaros, kur mainīgā vērtība ir 1, mainīgajam būs arī vērtība 1. Šādiem zariem koka konstrukcija turpinās uz nākamo līmeni, bet jauni zari neparādās. Viena atzara, kurā mainīgā vērtība ir 0, sazarosies divās atzaros, kur mainīgais saņems vērtības 0 un 1. Tādējādi katra jauna vienādojuma pievienošana, ņemot vērā tā specifiku, pievieno vienu risinājumu. Sākotnējais pirmais vienādojums:

ir 6 risinājumi. Lūk, kā izskatās šī vienādojuma pilns lēmumu koks:

Mūsu sistēmas otrais vienādojums ir līdzīgs pirmajam:

Vienīgā atšķirība ir tā, ka vienādojumā ir izmantoti Y mainīgie. Šim vienādojumam ir arī 6 risinājumi. Tā kā katru mainīgo risinājumu var apvienot ar katru mainīgo risinājumu, kopējais risinājumu skaits ir 36.

Ņemiet vērā, ka konstruētais lēmumu koks dod ne tikai risinājumu skaitu (atbilstoši zaru skaitam), bet arī pašus risinājumus, kas uzrakstīti uz katra koka zara.

19. problēma

Cik dažādu loģisko mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem?

Šis uzdevums ir iepriekšējā uzdevuma modifikācija. Atšķirība ir tāda, ka tiek pievienots vēl viens vienādojums, kas attiecas uz mainīgajiem X un Y.

No vienādojuma izriet, ka, ja ir vērtība 1 (viens šāds risinājums pastāv), tad tā vērtība ir 1. Tādējādi ir viena kopa, uz kuras un kuru vērtības ir 1. Ja ir vienāda ar 0, tā var ir jebkura vērtība, gan 0, gan un 1. Tāpēc katra kopa ar , vienāda ar 0 un ir 5 šādas kopas, atbilst visām 6 kopām ar mainīgajiem Y. Tāpēc kopējais risinājumu skaits ir 31.

20. problēma

Risinājums: atceroties pamata ekvivalences, mēs rakstām vienādojumu šādi:

Ietekmju cikliskā ķēde nozīmē, ka mainīgie ir identiski, tāpēc mūsu vienādojums ir līdzvērtīgs vienādojumam:

Šim vienādojumam ir divi risinājumi, ja visi ir 1 vai 0.

21. problēma

Cik atrisinājumu ir vienādojumam:

Risinājums: Tāpat kā 20. uzdevumā, mēs pārejam no cikliskām sekām uz identitātēm, pārrakstot vienādojumu šādā formā:

Izveidosim lēmumu koku šim vienādojumam:

22. problēma

Cik atrisinājumu ir šādai vienādojumu sistēmai?

Pakalpojuma mērķis. Tiešsaistes kalkulators ir paredzēts loģiskās izteiksmes patiesības tabulas konstruēšana.
Patiesības tabula – tabula, kurā ir visas iespējamās ievades mainīgo kombinācijas un tām atbilstošās izvades vērtības.
Patiesības tabulā ir 2n rindas, kur n ir ievades mainīgo skaits, un n+m ir kolonnas, kur m ir izvades mainīgie.

Norādījumi. Ievadot no tastatūras, izmantojiet šādus noteikumus:

Piemēram, loģiskā izteiksme abc+ab~c+a~bc jāievada šādi: a*b*c+a*b=c+a=b*c
Lai ievadītu datus loģiskās diagrammas veidā, izmantojiet šo pakalpojumu.

Noteikumi loģiskās funkcijas ievadīšanai

Simbola v (disjunkcija, VAI) vietā izmantojiet zīmi +.
Pirms loģiskās funkcijas nav nepieciešams norādīt funkcijas apzīmējumu. Piemēram, F(x,y)=(x|y)=(x^y) vietā vienkārši jāievada (x|y)=(x^y) .
Maksimālais mainīgo skaits ir 10.

Datoru loģisko shēmu projektēšana un analīze tiek veikta, izmantojot īpašu matemātikas nozari - loģisko algebru. Loģikas algebrā var izdalīt trīs galvenās loģiskās funkcijas: “NOT” (negācija), “UN” (konjunkcija), “OR” (disjunkcija).
Lai izveidotu jebkuru loģisko ierīci, ir jānosaka katra izejas mainīgā atkarība no esošajiem ievades mainīgajiem šo atkarību sauc par komutācijas funkciju vai loģiskās algebras funkciju.
Loģiskās algebras funkciju sauc par pilnībā definētu, ja ir norādītas visas 2n tās vērtības, kur n ir izvades mainīgo skaits.
Ja visas vērtības nav definētas, funkcija tiek saukta par daļēji definētu.
Ierīci sauc par loģisku, ja tās stāvoklis ir aprakstīts, izmantojot loģiskās algebras funkciju.
Loģiskās algebras funkcijas attēlošanai tiek izmantotas šādas metodes:
Algebriskā formā jūs varat izveidot loģiskās ierīces ķēdi, izmantojot loģiskos elementus.

1. attēls - loģiskās ierīces diagramma

Visas loģikas algebras darbības ir definētas patiesības tabulas vērtības. Patiesības tabula nosaka operācijas rezultātu par katrs ir iespējams x sākotnējo paziņojumu loģiskās vērtības. Opciju skaits, kas atspoguļo operāciju piemērošanas rezultātu, būs atkarīgs no loģiskās izteiksmes priekšrakstu skaita. Ja apgalvojumu skaits loģiskajā izteiksmē ir N, tad patiesības tabulā būs 2 N rindas, jo ir 2 N dažādas iespējamo argumentu vērtību kombinācijas.

Operācija NOT — loģiskā noliegšana (inversija)

Loģiska darbība NETIEK lietota vienam argumentam, kas var būt vienkārša vai sarežģīta loģiska izteiksme. Operācijas rezultāts NAV šāds:

ja sākotnējā izteiksme ir patiesa, tad tās nolieguma rezultāts būs nepatiess;
ja sākotnējā izteiksme ir nepatiesa, tad tās nolieguma rezultāts būs patiess.

Noliegšanas darbībai NAV pieņemtas šādas vienošanās:
nevis A, Ā, nevis A, ¬A, !A
Noliegšanas darbības rezultāts NAV noteikts pēc šādas patiesības tabulas:

A	nevis A
0	1
1	0

Noliegšanas darbības rezultāts ir patiess, ja sākotnējais apgalvojums ir nepatiess, un otrādi.

VAI operācija — loģiska pievienošana (disjunkcija, savienošana)

Loģiskā VAI operācija veic divu priekšrakstu apvienošanas funkciju, kas var būt gan vienkārša, gan sarežģīta loģiska izteiksme. Paziņojumus, kas ir loģiskās darbības sākumpunkts, sauc par argumentiem. Operācijas VAI rezultāts ir izteiksme, kas būs patiesa tad un tikai tad, ja vismaz viena no sākotnējām izteiksmēm ir patiesa.
Izmantotie apzīmējumi: A vai B, A V B, A vai B, A||B.
Operācijas VAI rezultātu nosaka šāda patiesības tabula:
Operācijas VAI rezultāts ir patiess, ja A ir patiess vai B ir patiess, vai gan A, gan B ir patiess, un nepatiess, ja argumenti A un B ir nepatiesi.

Operācija UN — loģiskā reizināšana (savienojums)

Loģiskā darbība UN veic divu apgalvojumu (argumentu) krustošanās funkciju, kas var būt gan vienkārša, gan sarežģīta loģiska izteiksme. Operācijas UN rezultāts ir izteiksme, kas būs patiesa tad un tikai tad, ja abas sākotnējās izteiksmes ir patiesas.
Izmantotie apzīmējumi: A un B, A Λ B, A un B, A un B.
Operācijas UN rezultātu nosaka šāda patiesības tabula:

A	B	A un B
0	0	0
0	1	0
1	0	0
1	1	1

Operācijas UN rezultāts ir patiess tad un tikai tad, ja apgalvojumi A un B ir patiesi un visos citos gadījumos ir nepatiesi.

Operācija “IF-THEN” - loģiskas sekas (implikācija)

Šī darbība savieno divas vienkāršas loģiskās izteiksmes, no kurām pirmā ir nosacījums, bet otrā ir šī nosacījuma sekas.
Izmantotie apzīmējumi:
ja A, tad B; A nozīmē B; ja A, tad B; A→B.
Patiesības tabula:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Implikācijas darbības rezultāts ir nepatiess tikai tad, ja premisa A ir patiesa un secinājums B (seka) ir nepatiess.

Operācija “A tad un tikai tad, ja B” (ekvivalence, ekvivalence)

Izmantotais apzīmējums: A ↔ B, A ~ B.
Patiesības tabula:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operācija “Addition modulo 2” (XOR, ekskluzīva vai stingra disjunkcija)

Izmantotais apzīmējums: A XOR B, A ⊕ B.
Patiesības tabula:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Ekvivalences darbības rezultāts ir patiess tikai tad, ja A un B vienlaikus ir patiesi vai nepatiesi.

Loģisko operāciju prioritāte

Darbības iekavās
Inversija
Saikne (&)
Disjunkcija (V), ekskluzīva VAI (XOR), summa modulo 2
Ietekme (→)
Ekvivalence (↔)

Perfekta disjunktīva normālā forma

Perfekta disjunktīva formulas normālā forma(SDNF) ir līdzvērtīga formula, kas ir elementāru savienojumu disjunkcija un kurai ir šādas īpašības:

Katrs formulas loģiskais termins satur visus funkcijā F(x 1,x 2,...x n) iekļautos mainīgos.
Visi formulas loģiskie termini ir atšķirīgi.
Neviens loģiskais termins nesatur mainīgo un tā noliegumu.
Neviens loģiskais termins formulā nesatur vienu un to pašu mainīgo divreiz.

SDNF var iegūt, izmantojot patiesības tabulas vai līdzvērtīgas transformācijas.
Katrai funkcijai SDNF un SCNF ir unikāli definēti līdz permutācijai.

Perfekta konjunktīva parastā forma

Perfekta konjunktīva parastā formulas forma (SCNF)Šī ir tai līdzvērtīga formula, kas ir elementāru disjunkciju konjunkcija un apmierina īpašības:

Visas elementārās disjunkcijas satur visus funkcijā F(x 1 ,x 2 ,...x n) iekļautos mainīgos.
Visas elementārās disjunkcijas ir atšķirīgas.
Katra elementārā disjunkcija vienreiz satur mainīgo.
Neviena elementāra disjunkcija nesatur mainīgo un tā noliegumu.

Jūs varat izvēlēties dažādos veidos loģisko vienādojumu sistēmu risināšana. Tas ir reducēšana uz vienu vienādojumu, patiesības tabulas konstruēšana un sadalīšana.

Uzdevums: Atrisiniet loģisko vienādojumu sistēmu:

Apsvērsim samazināšanas metode līdz vienam vienādojumam . Šī metode ietver loģisko vienādojumu pārveidošanu tā, lai to labās puses būtu vienādas ar patiesības vērtību (tas ir, 1). Lai to izdarītu, izmantojiet loģiskās noliegšanas darbību. Tad, ja vienādojumos ir sarežģītas loģiskās darbības, mēs tās aizstājam ar pamata operācijām: “UN”, “OR”, “NOT”. Nākamais solis ir apvienot vienādojumus vienā, kas ir ekvivalents sistēmai, izmantojot loģisko darbību “UN”. Pēc tam jums jāpārveido iegūtais vienādojums, pamatojoties uz loģiskās algebras likumiem, un jāiegūst konkrēts sistēmas risinājums.

1. risinājums: Lietojiet inversiju abām pirmā vienādojuma pusēm:

Iedomāsimies nozīmi, izmantojot pamata darbības “OR” un “NOT”:

Tā kā vienādojumu kreisās puses ir vienādas ar 1, mēs varam tos apvienot, izmantojot operāciju “UN”, vienā vienādojumā, kas ir līdzvērtīgs sākotnējai sistēmai:

Mēs atveram pirmo iekavu saskaņā ar De Morgana likumu un pārveidojam iegūto rezultātu:

Iegūtajam vienādojumam ir viens risinājums: A =0, B=0 un C=1.

Nākamā metode ir veidojot patiesības tabulas . Tā kā loģiskajiem lielumiem ir tikai divas vērtības, varat vienkārši izskatīt visas iespējas un atrast starp tām tos, kuriem ir izpildīta noteiktā vienādojumu sistēma. Tas ir, mēs izveidojam vienu kopīgu patiesības tabulu visiem sistēmas vienādojumiem un atrodam līniju ar nepieciešamajām vērtībām.

2. risinājums: Izveidosim patiesības tabulu sistēmai:








0	0	1	1	0	1

Rinda, kurai ir izpildīti uzdevuma nosacījumi, ir izcelta treknrakstā. Tātad A=0, B=0 un C=1.

veids sadalīšanās . Ideja ir fiksēt viena mainīgā vērtību (iestatīt to vienādu ar 0 vai 1) un tādējādi vienkāršot vienādojumus. Pēc tam varat labot otrā mainīgā vērtību utt.

3. risinājums:Ļaujiet A = 0, tad:

No pirmā vienādojuma iegūstam B = 0, bet no otrā - C = 1. Sistēmas risinājums: A = 0, B = 0 un C = 1.

Vienotajā valsts eksāmenā datorzinātnēs ļoti bieži ir nepieciešams noteikt atrisinājumu skaitu loģisko vienādojumu sistēmai, neatrodot pašus risinājumus, arī tam ir noteiktas metodes. Galvenais veids, kā atrast risinājumu skaitu loģisko vienādojumu sistēmai, irmainīgo lielumu aizstāšana. Pirmkārt, jums pēc iespējas jāvienkāršo katrs vienādojums, pamatojoties uz loģiskās algebras likumiem, un pēc tam vienādojumu sarežģītās daļas jāaizstāj ar jauniem mainīgajiem un jānosaka risinājumu skaits. jauna sistēma. Pēc tam atgriezieties pie nomaiņas un nosakiet tam risinājumu skaitu.

Uzdevums: Cik atrisinājumu ir vienādojumam (A → B) + (C → D) = 1? Kur A, B, C, D ir loģiskie mainīgie.

Risinājums: Ieviesīsim jaunus mainīgos: X = A →B un Y = C →D. Ņemot vērā jaunos mainīgos, vienādojums tiks uzrakstīts šādi: X + Y = 1.

Disjunkcija ir patiesa trīs gadījumos: (0;1), (1;0) un (1;1), savukārt X un Y ir implikācijas, tas ir, tā ir patiesa trīs gadījumos un nepatiesa vienā. Tāpēc gadījums (0;1) atbildīs trīs iespējamām parametru kombinācijām. Gadījums (1;1) – atbildīs deviņām iespējamām sākotnējā vienādojuma parametru kombinācijām. Tātad, kopā iespējamie risinājumi no šī vienādojuma 3+9=15.

Nākamais veids, kā noteikt risinājumu skaitu loģisko vienādojumu sistēmai, ir binārais koks. Apskatīsim šo metodi, izmantojot piemēru.

Uzdevums: Cik dažādu risinājumu ir loģisko vienādojumu sistēmai:

Dotā vienādojumu sistēma ir līdzvērtīga vienādojumam:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Pieņemsim, ka x 1 – ir taisnība, tad no pirmā vienādojuma mēs to iegūstam x 2 arī taisnība, no otrā - x 3 =1 un tā tālāk līdz x m= 1. Tas nozīmē, ka m vienību kopa (1; 1; …; 1) ir sistēmas risinājums. Ļaujiet tai tagad x 1 =0, tad no pirmā vienādojuma mums ir x 2 =0 vai x 2 =1.

Kad x 2 taisnība, mēs iegūstam, ka arī pārējie mainīgie ir patiesi, tas ir, kopa (0; 1; ...; 1) ir sistēmas risinājums. Plkst x 2 =0 mēs to sapratām x 3 =0 vai x 3 =, un tā tālāk. Turpinot pie pēdējā mainīgā, mēs atklājam, ka vienādojuma risinājumi ir šādas mainīgo kopas (m +1 risinājums, katrs risinājums satur m mainīgo lielumu vērtības):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Šo pieeju labi ilustrē bināra koka izveide. Iespējamo risinājumu skaits ir konstruētā koka dažādu zaru skaits. Ir viegli redzēt, ka tas ir vienāds ar m +1.

	Koks	Risinājumu skaits
x 1
x 2
x 3
		…

Spriešanas grūtību gadījumā pētniecība un būvniecībarisinājumus, ar kuriem varat meklēt risinājumu izmantojot patiesības tabulas, vienam vai diviem vienādojumiem.

Pārrakstīsim vienādojumu sistēmu šādā formā:

Un izveidosim patiesības tabulu atsevišķi vienam vienādojumam:

x 1	x 2	(x 1 → x 2)

Izveidosim patiesības tabulu diviem vienādojumiem:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Nodarbības tēma: Loģisko vienādojumu risināšana

Izglītojoši – pētīt loģisko vienādojumu risināšanas metodes, attīstot prasmes loģisko vienādojumu risināšanā un loģiskās izteiksmes konstruēšanā, izmantojot patiesības tabulu;

Attīstība - radīt apstākļus attīstībai kognitīvā interese skolēnus, veicināt atmiņas, uzmanības, loģiskās domāšanas attīstību;

Izglītojoši : veicināt spēju uzklausīt citu viedokļus, audzinot gribu un neatlaidību, lai sasniegtu gala rezultātus.

Nodarbības veids: apvienotā nodarbība

Aprīkojums: dators, multimediju projektors, prezentācija 6.

Nodarbības progress

Pamatzināšanu atkārtošana un atjaunošana. Mājas darbu pārbaude (10 minūtes)

Iepriekšējās nodarbībās iepazināmies ar loģiskās algebras pamatlikumiem un mācījāmies izmantot šos likumus loģisko izteiksmju vienkāršošanai.

Pārbaudīsim mūsu mājasdarbu par loģisko izteiksmju vienkāršošanu:

1. Kurš no šiem vārdiem atbilst loģiskajam nosacījumam:

(pirmā burta līdzskaņa → otrā burta līdzskaņa)٨ (pēdējā burta patskaņa → priekšpēdējā burta patskaņa)? Ja ir vairāki šādi vārdi, norādiet mazāko no tiem.

1) ANNA 2) MARIJA 3) OLEG 4) STEPĀNS

Ieviesīsim šādu apzīmējumu:

A – pirmā burta līdzskaņa

B – otrā burta līdzskaņa

S – pēdējā burta patskanis

D – priekšpēdējais patskaņa burts

Izteiksim izteiksmi:

Izveidosim tabulu:

2. Norādiet, kura loģiskā izteiksme ir ekvivalenta izteiksmei

Vienkāršosim sākotnējās izteiksmes ierakstīšanu un piedāvātās iespējas:

3. Dots izteiksmes F patiesuma tabulas fragments:

Kura izteiksme atbilst F?

Noteiksim šo izteiksmju vērtības norādītajām argumentu vērtībām:

Ievads nodarbības tēmā, jauna materiāla prezentācija (30 minūtes)

Mēs turpinām pētīt loģikas pamatus, un mūsu šodienas nodarbības tēma ir “Loģisko vienādojumu risināšana”. Apgūstot šo tēmu, jūs apgūsiet loģisko vienādojumu risināšanas pamatveidus, iegūsiet iemaņas šo vienādojumu risināšanā, izmantojot loģiskās algebras valodu un prasmi sastādīt loģisko izteiksmi, izmantojot patiesības tabulu.

1. Atrisiniet loģisko vienādojumu

(¬K M) → (¬L M N) =0

Uzrakstiet savu atbildi kā četru zīmju virkni: mainīgo K, L, M un N vērtības (šajā secībā). Tātad, piemēram, 1101. rinda atbilst tam, ka K=1, L=1, M=0, N=1.

Risinājums:

Pārveidosim izteiksmi(¬K  M) → (¬L  M  N)

Izteiksme ir nepatiesa, ja abi termini ir nepatiesi. Otrais loceklis ir vienāds ar 0, ja M =0, N =0, L =1. Pirmajā terminā K = 0, jo M = 0, un
.

Atbilde: 0100

2. Cik atrisinājumu ir vienādojumam (atbildē norādiet tikai skaitli)?

Risinājums: pārveidojiet izteiksmi

(A +B )*(C +D )=1

A +B =1 un C +D =1

2. metode: patiesības tabulas sastādīšana

3 ceļi: SDNF uzbūve - perfekta disjunktīva normālā forma funkcijai - pilnīgu regulāru elementāru savienojumu disjunkcija.

Pārveidosim sākotnējo izteiksmi, atveram iekavas, lai iegūtu savienojumu disjunkciju:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Papildināsim saikļus līdz pabeigtiem saikļiem (visu argumentu reizinājums), atveram iekavas:

Ņemsim vērā tos pašus savienojumus:

Rezultātā mēs iegūstam SDNF, kas satur 9 savienojumus. Tāpēc šīs funkcijas patiesības tabulā ir vērtība 1 9 rindās no 2 4 =16 mainīgo vērtību kopām.

3. Cik atrisinājumu ir vienādojumam (atbildē norādiet tikai skaitli)?

Vienkāršosim izteicienu:

3 ceļi: SDNF būvniecība

Ņemsim vērā tos pašus savienojumus:

Rezultātā mēs iegūstam SDNF, kas satur 5 savienojumus. Tāpēc šīs funkcijas patiesības tabulai ir vērtība 1 uz 5 rindām no 2 4 =16 mainīgo vērtību kopām.

Loģiskās izteiksmes konstruēšana, izmantojot patiesības tabulu:

katrai patiesības tabulas rindai, kurā ir 1, mēs veidojam argumentu reizinājumu, un mainīgie, kas vienādi ar 0, tiek iekļauti reizinājumā ar noliegumu, un mainīgie, kas vienādi ar 1, tiek iekļauti bez noliegšanas. Vēlamā izteiksme F tiks veidota no iegūto reizinājumu summas. Pēc tam, ja iespējams, šī izteiksme ir jāvienkāršo.

Piemērs: ir dota izteiksmes patiesības tabula. Izveidojiet loģisku izteiksmi.

Risinājums:

3. Mājas darbs (5 minūtes)

Atrisiniet vienādojumu:

Cik atrisinājumu ir vienādojumam (atbildē norādiet tikai skaitli)?

Izmantojot doto patiesības tabulu, konstruējiet loģisku izteiksmi un

vienkāršot to.