Vienādojums datorzinātnē. Loģisko vienādojumu sistēmas datorzinātņu vienotā valsts eksāmena uzdevumos

Sistēmu risinājums loģiskie vienādojumi loģisko izteiksmju pārveidošanas tabulas metodes.

Šis paņēmiens ir balstīts uz patiesības tabulu izmantošanu un ir paredzēts studentiem, kuri zina, kā pārvērst loģiskās izteiksmes. Ja skolēni nepārvalda šīs metodes, tās var izmantot bez pārveidojumiem. (Mēs izmantosim transformācijas). Lai apgūtu šo risināšanas metodi, obligāti jāzina loģisko pamatoperāciju īpašības: konjunkcija, disjunkcija, inversija, implikācija un ekvivalence.

Algoritms vienādojumu sistēmu atrisināšanai, izmantojot šo metodi:

Pārveidojiet loģisko vienādojumu un vienkāršojiet to.

Nosakiet vienādojumu atrisināšanas secību sistēmā, jo vairumā gadījumu ir secīgs vienādojumu risinājums no augšas uz leju (kā tie atrodas sistēmā), bet ir iespējas, kad ērtāk un vieglāk sākt risināt no no apakšas uz augšu.

Izveidojiet mainīgo tabulu, kurā varat iestatīt pirmā (vai pēdējā) mainīgā sākotnējās vērtības.

Konsekventi pierakstiet iespējamās opcijas tālāk norādītajam mainīgajam, kad visi pirmā nozīme.

Pēc iepriekšējā vienādojuma atrisināšanas, pārejot uz nākamo, noteikti pievērsiet uzmanību tam, kādi mainīgie tiek izmantoti iepriekšējā un turpmākajos vienādojumos, jo mainīgo vērtības, kas iegūtas, risinot iepriekšējos vienādojumus, tiek nodotas kā opcijas šādus vienādojumus.

Pārejot uz nākamo mainīgo, pievērsiet uzmanību iegūtajiem risinājuma daudzumiem, jo var identificēt lēmumu pieauguma modeli.

1. piemērs.

¬ X1 ˅ X2=1

¬ X2 ˅ X3=1

¬ X3 ˅ X4=1

¬ X9 ˅ X10=1

Sāksim ar X1 un redzēsim, kādas vērtības var iegūt šis mainīgais: 0 un 1.

Tad mēs apsvērsim katru no šīm vērtībām un redzēsim, kas var būt X2.

Atbilde: 11 risinājumi

2. piemērs.

( X1X2)˅(¬X1˄¬X2) ˅( X1↔ X3)=1

( X2˄X3)˅(¬X2˄¬X3) ˅( X2↔ X4)=1

(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0

Pārveidosim pēc formulas (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B

Mēs iegūstam:

( X1↔ X2) ˅ (X1↔ X3) =1

( X2↔ X3) ˅ (X2↔ X4) =1

( X8↔ X9 (X8↔ X10) =0

X1 =0 - 8 risinājumiem

Ņemsim X1=1 un paskatīsimies, kādu vērtību var iegūt X2. Tagad katram X2 mēs apsvērsim, kādas vērtības var iegūt X3 utt.

X1=1 – 8 risinājumi

Kopā 8+8=16 risinājumi

Atbilde. 16 risinājumi

3. piemērs .

¬ ( X1↔ X2) ˄ ( X1X3) ˄ (¬X1˅¬X3 )=0

¬ ( X2↔ X3) ˄ (X2˅X4) ˄ (¬X2˅¬X4)=0

….

¬ ( X8↔ X9 (X8X10) ˄ (¬X8˅¬X10)=0

Pēc pārvērtībām (A˅ B) ˄(¬ A ˅¬ B)= ¬( A ↔ B)

mēs iegūstam:

¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0

¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0

…..

¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0

Ņemsim X1=0 un paskatīsimies, kādu vērtību var iegūt X2. Tagad katram X2 mēs apsvērsim, kādas vērtības var iegūt X3 utt.

Mēs saņēmām 10 risinājumus X1=0

Darīsim to pašu ar X1=1. Mēs arī saņemam 10 risinājumus

Kopā:10+10=20

Atbilde: 20 risinājumi.

4. piemērs.

(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1

(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1

….

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Konvertēsim, izmantojot formulas. (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B. Mēs iegūstam:

(X1↔ X2) ˅ (X2↔ X3)=1

(X2↔ X3) ˅ (X3↔ X4)=1

(X3↔ X4) ˅ (X4↔ X5)=1

(X4↔ X5) ˅ (X5↔ X6)=1

(X5↔ X6) ˅ (X6↔ X7)=1

(X6↔ X7) ˅ (X7↔ X8)=1

(X7↔ X8) ˅ (X8↔ X9)=1

(X8↔ X9) ˅ (X9↔ X10)=0

Sāksim no beigām, jo pēdējā vienādojumā mainīgie tiek noteikti unikāli.

Ļaujiet X10=0, tad X9=1, X8=0, X7=0, X6=0, un var ņemt šādus mainīgos dažādas nozīmes. Mēs apsvērsim katru.

Kopā 21 risinājums X10=0

Tagad apsveriet X10=1. Mēs iegūstam arī 21 risinājumu

Kopā:21+21=42

Atbilde: 42 risinājumi

5. piemērs.

( X1X2) ˅ (¬X1 ˄ ¬X2) ˅ (¬X3˄X4 (X3 ˄ ¬X4)=1

( X3˄X4) ˅ (¬X3 ˄ ¬X4) ˅ (¬X5X6) ˅ (X5˄¬X6)=1

( X5X6) ˅ (¬X5˄¬X6) ˅ (¬X7˄X8 (X7 ˄ ¬X8)=1

( X7˄X8) ˅ (¬X7 ˄ ¬X8) ˅ (¬ X9X10 (X9˄ ¬X10) =1

Pārveidosim pēc formulām:(¬ A ˄ B) ˅ ( A ˄ ¬ B)= A↔ ¬ B

( A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B

( X1↔ X2) ˅ (X3 ↔ ¬X4)=1

( X3↔ X4 (X5 ↔ ¬X6)=1

( X5↔ X6) ˅ (X7 ↔ ¬X8)=1

( X7↔ X8 (X9 ↔ ¬X10)=1

Apsvērsim, kādas vērtības X1 un X2 var ņemt: (0,0), (0,1), (1,0), (1,1).

Apsvērsim katru iespēju un redzēsim, kādas vērtības X3, X4 var pieņemt.

Sākot no X7, X8, mēs nekavējoties pierakstīsim risinājumu skaitu, jo uzreiz ir skaidrs, ka, ja vērtības ir vienādas (1,1) un (0,0), tad šādiem mainīgajiem ir 4 risinājumi, un kad tie atšķiras (0,1) un (1 ,0) – 2 risinājumi.

Kopā: 80+80+32=192

Atbilde: 192 risinājumi

6. piemērs.

(X1↔X2) ˅ (X2↔X3)=1

(X2↔X3) ˅ (X3↔X4)=1

(X3↔X4) ˅ (X4↔X5)=1

….

(X8↔X9) ˅ (X9↔X10)=1

Ņemsim X1=0 un paskatīsimies, kādu vērtību var iegūt X2. Tagad katram X2 mēs apsvērsim, kādas vērtības var iegūt X3 utt.

Mēs redzam noteiktu modeli: nākamo risinājumu skaits ir vienāds ar iepriekšējo divu summu.

Tas pats X1=1 iegūstam 89 risinājumus

Kopā: 89+89=178 risinājumi

Atbilde: 178 risinājumi

Atrisināsim to vēl vienā veidā

(X1↔X2) ˅ (X2↔X3)=1

(X2↔X3) ˅ (X3↔X4)=1

(X3↔X4) ˅ (X4↔X5)=1

….

(X8↔X9) ˅ (X9↔X10)=1

Iepazīstinām ar nomaiņu:

T 1 =(X1↔X2)

T 2 =(X2↔X3)

T 3 =(X3↔X4)

T 4 =(X4↔X5)

T 5 =(X5↔X6)

T 6 =(X6↔X7)

T 7 =(X7↔X8)

T 8 =(X8↔X9)

T 9 =(X9↔X10)

Mēs iegūstam:

T1T2=1

T2˅T3=1

T3˅T4=1

T4T5=1

T5T6=1

T6˅T7=1

T7˅T8=1

T8T9=1

T9T10=1

ŅemsimT1=1 un izmantojiet disjunkcijas īpašības:

BET atcerēsimies to

T 1 =(X1↔X2)

T 2 =(X2↔X3) utt.

Izmantosim ekvivalences īpašību un, apskatot tabulu, pārliecināsimies, ka tas

Ja T = 1, tad iegūst divus risinājumus. Un, kad =0, ir viens risinājums.

Tāpēc mēs varam saskaitīt vieniniekus un reizināt tos ar 2+ nulles skaitu. Skaitīšana, arī izmantojot paraugu.

Izrādās, ka vieninieku skaits = iepriekšējais kopējais atrisinājumu skaits T, un nulles ir vienāds ar iepriekšējo vienību skaitu

Tātad. Mēs to saņemsim. Tā kā viens dod divus risinājumus, tad 34 * 2 = 68 risinājumi no viena + 21 risinājums no 0.

Kopā 89 risinājumi T=1. Līdzīgā veidā iegūstam 89 risinājumus T=0

Kopā 89+89=178

Atbilde: 178 risinājumi

7. piemērs.

(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔ X2) ˅ ¬(X3↔ X4)=1

(X3 ↔ X4 (X5↔ X6) ˄ ¬(X3 ↔ X4) ˅ ¬(X5↔ X6)=1

(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔ X6) ˅ ¬(X7↔ X8)=1

(X7 ↔ X8 (X9↔ X10) ˄ ¬(X7 ↔ X8) ˅ ¬(X9↔ X10)=1

Iepazīstinām ar nomaiņu:

T1=(X1 ↔ X2)

T2=(X3↔ X4)

T3=(X5↔ X6)

T4=(X7 ↔ X8)

T5=(X9↔ X10)

Mēs iegūstam:

(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1

(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1

(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1

(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1

Apskatīsim, kas var būt T:

Kopā

T K ≠T K+1 Es T K =T K+2

Mēs iegūstam: 2 5 =32 T

Kopā: 32+32=64

Atbilde: 64 risinājumi.

Vienādojuma atrisinājums 1. Pārejiet uz vienādojuma rakstīšanas prefiksa formu, noliegumu simbolus aizstājot ar ¬ 2. Konstruējiet īpaša veida patiesības tabulas nosaukumu 3. Aizpildiet patiesības tabulas rindas visām kombinācijām A un B, X vietā aizstājot ar 0 vai 1. 4. Izveidojiet patiesības tabulu X = F (A,B) 5. Izmantojot patiesības tabulu, nosakiet funkcijas X veidu, ja nepieciešams, izmantojot SCNF konstruēšanas metodes. un SDNF, kas tiks apspriesti turpmāk.

Īpašas formas patiesības tabulas konstruēšana ¬((A+B)·(X A·B))=¬(B+¬(X A))

Patiesības tabula X=F(A, B) ABX atbilst implikācijas B noliegumam A ATBILDE:

Loģisko ierīču kombinētās shēmas Pamatelementi (GOST): 1 A B Disjunkcija A B Ekvivalence & A B Savienojums M2 A B XOR

Loģisko ierīču kombinētās shēmas Pamatelementi (GOST): 1 A B Implikācijas & A B Šēfera elements un A B Koimlikācija 1 A B Webb elements

Shēmas piemērs F 1 & 1 & & 1M2 B A

Shēmu risināšana 1 Variants - ķēdes pārvēršana sarežģītā loģiskā izteiksmē un pēc tam to vienkāršošana saskaņā ar loģikas likumiem. 2. variants – patiesības tabulas konstruēšana un pēc tam, ja nepieciešams, konstruēšana caur SKNF vai SDNF (skatīt zemāk). Apsvērsim otro iespēju, jo tā ir vienkāršāka un saprotamāka.

Patiesības tabulas uzbūve AB A + B + · B B · A + A B A + · ·

Patiesības tabula F(A, B) ABX atbilst implikācijas B noliegumam A ATBILDE:

SDNF un SKNF (definīcijas) Elementārais konjunkcija ir vairāku mainīgo konjunkcija, kas ņemta ar noliegumu vai bez tā, un starp mainīgajiem var būt identiski par elementāru disjunkciju sauc vairāku mainīgo lielumu konjunkcija, kas ņemta ar noliegumu vai bez tā starp mainīgajiem var būt identiski Jebkurš elementāro savienojumu disjunkts Sauksim to par disjunktīvo normālo formu (DNF) Sauksim jebkuru elementāro savienojumu konjunkciju par konjunktīvo normālo formu (DNF).

SDNF un SCNF (definīcijas) Par perfektu disjunktīvu normālu formu (PDNF) sauc par DNF, kurā nav identisku elementāru savienojumu un visi savienojumi sastāv no vienas un tās pašas mainīgo kopas, kurā katrs mainīgais parādās tikai vienu reizi (iespējams, ar noliegumu). Perfekta konjunktīva normālā forma (PCNF) ir CNF, kurā nav identisku elementāru disjunkciju un visas disjunkcijas sastāv no vienas un tās pašas mainīgo kopas, kurā katrs mainīgais parādās tikai vienu reizi (iespējams, ar noliegumu).

Algoritms SDNF iegūšanai no patiesības tabulas 1. Atzīmējiet patiesības tabulas rindas, kuru pēdējā kolonnā ir 1. 2. Katrai atzīmētajai rindai pierakstiet visu mainīgo konjunkciju šādi: ja mainīgā vērtība dotā rinda ir 1, tad savienojumā iekļaujiet šo mainīgo, ja tas ir vienāds ar 0, tad tā noliegumu. 3. Saistiet visus iegūtos savienojumus disjunkcijā. Algoritms SCNF iegūšanai no patiesības tabulas 1. Atzīmējiet patiesības tabulas rindas, kuru pēdējā kolonnā ir 0. 2. Katrai atzīmētajai rindai izrakstiet visu mainīgo disjunkciju šādi: ja mainīgā vērtība dotā rinda ir 0, tad šo mainīgo iekļaujiet savienojumā, ja ir vienāds ar 1, tad tā noliegumu. 3. Saistiet visus iegūtos disjunkcijas konjunkcijā.

SKNF konstruēšanas piemērs XY F(X,Y) Atzīmējiet nulles 2. Disjunkcijas: X + Y 3. Savienojums: (X + Y) · (X + Y)

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 pietiekami zināmu 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, kurā ir 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žus vienkāršus uzdevumus kas saistīti ar loģiskajā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ī saikļa 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 rādī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 - tādas ir 5 dažādas iespējas, kas atbilst viņa liecībai. 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ģiskajam vienādojumam var būt no 0 līdz 2n dažādi risinājumi. 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:

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 k loģisko vienādojumu sistēmu:

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 vispārīga metode, kas atšķiras no brutālā spēka, kas ļauj risinā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 pēc skaita vienādojuma mainīgie. 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, tad kopējais skaits Ir 36 risinājumi.

Ņ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. Vispārējā uzņemšana 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 sākotnējā posmā ir iespējams noteikt jaunu zaru parādīšanās modeli katrā nākamajā līmenī, kā tas tika darīts, piemēram, 18. problēmā. .

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 problēmām, kurās mainīgo lielumu skaits ir 20-30, bet tas sāks ilgi domāt par lielāka izmēra problēmām. 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 skaitli funkciju mainīgie jautri. 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 ierasts, ka kādai funkcijai F(x) ir ievades parametrs x, kas ir aritmētiskā, virknes vai loģiskā 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 galvas. Definējiet loģisku funkciju, kas apraksta X izmaksu.
Vārdi teikumā tiek 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ņi.
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)

Vienādojumu izmantošana mūsu dzīvē ir plaši izplatīta. Tos izmanto daudzos aprēķinos, konstrukciju būvniecībā un pat sportā. Cilvēks izmantoja vienādojumus senos laikos, un kopš tā laika to lietojums ir tikai palielinājies. Matemātikā ir noteiktas problēmas, kas saistītas ar propozicionālo loģiku. Lai atrisinātu šāda veida vienādojumu, jums ir jābūt noteiktam zināšanu apjomam: zināšanām par propozicionālās loģikas likumiem, 1 vai 2 mainīgo loģisko funkciju patiesības tabulām, loģisko izteiksmju konvertēšanas metodēm. Turklāt jums jāzina šādas loģisko darbību īpašības: konjunkcija, disjunkcija, inversija, implikācija un ekvivalence.

Jebkuru loģisko funkciju \variables - \ var norādīt ar patiesības tabulu.

Atrisināsim vairākus loģiskus vienādojumus:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Sāksim risinājumu ar \[X1\] un noteiksim, kādas vērtības šis mainīgais var iegūt: 0 un 1. Tālāk mēs apsvērsim katru no iepriekšminētajām vērtībām un redzēsim, kas var būt \[X2.\].

Kā redzams tabulā, mūsu loģiskajam vienādojumam ir 11 risinājumi.

Kur es varu atrisināt loģisko vienādojumu tiešsaistē?

Jūs varat atrisināt vienādojumu mūsu vietnē https://site. Bezmaksas tiešsaistes risinātājs ļaus jums dažu sekunžu laikā atrisināt jebkuras sarežģītības tiešsaistes vienādojumus. Viss, kas jums jādara, ir vienkārši ievadīt savus datus risinātājā. Mūsu vietnē varat arī noskatīties video instrukcijas un uzzināt, kā atrisināt vienādojumu. Un, ja jums joprojām ir jautājumi, varat tos uzdot mūsu VKontakte grupā http://vk.com/pocketteacher. Pievienojieties mūsu grupai, mēs vienmēr esam priecīgi jums palīdzēt.

Šajā materiālā ir iekļauta prezentācija, kurā ir izklāstītas loģisko vienādojumu risināšanas metodes un loģisko vienādojumu sistēmas Vienotā valsts eksāmena datorzinātnēs uzdevumā B15 (Nr. 23, 2015). Zināms, ka šis uzdevums ir viens no grūtākajiem Vienotā valsts pārbaudījuma uzdevumiem. Prezentācija var būt noderīga, pasniedzot nodarbības par tēmu “Loģika” specializētajās nodarbībās, kā arī gatavojoties vienotajam valsts eksāmenam.

Lejupielādēt:

Priekšskatījums:

Lai izmantotu prezentācijas priekšskatījumus, izveidojiet sev kontu ( konts) Google un piesakieties: https://accounts.google.com

Slaidu paraksti:

B15 uzdevuma atrisinājums (loģisko vienādojumu sistēmas) Višņevska M.P., MAOU “Ģimnāzija Nr.3” 2013.gada 18.novembris, Saratova

B15 uzdevums ir viens no grūtākajiem Vienotajā valsts eksāmenā datorzinībās!!! Tiek pārbaudītas šādas prasmes: konvertēt izteiksmes, kas satur loģiskos mainīgos; aprakstiet dabiskajā valodā loģisko mainīgo vērtību kopu, kurai ir patiesa dotā loģisko mainīgo kopa; saskaitīt bināro kopu skaitu, kas atbilst dotajiem nosacījumiem. Grūtākais ir tāpēc, ka... nav formālu noteikumu, kā to izdarīt, tas prasa minējumus.

Bez kā nevar iztikt!

Simbolu konjunkcija: A /\ B , A  B , AB , A & B, A un B disjunkcija: A \ / B , A + B , A | B , A vai B noliegums:  A , A, nevis A ekvivalence: A  B, A  B, A  B ekskluzīvs “vai”: A  B , A xor B

Mainīgo aizstāšanas metode Cik dažādu loģisko mainīgo x1, x2, ..., x9, x10 vērtību kopu pastāv, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5) ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Atbildē nav jānorāda visas dažādās kopas x1, x2, …, x9, x10, kurām šī vienlīdzības sistēma ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits (2012. gada demonstrācijas versija)

Risinājums 1. solis. Vienkāršojiet, mainot mainīgos t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Pēc vienkāršošanas: (t1 \/ t2) /\/¬t1 t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Apsveriet vienu no vienādojumiem: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Acīmredzot tas =1 tikai tad, ja viens no mainīgajiem ir 0 un otrs ir 1 Izmantosim formulu, lai izteiktu XOR darbību, izmantojot konjunkciju un disjunkciju: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

2. darbība. Sistēmas analīze ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 01 0 Т1 .Uz. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), tad katra tk vērtība atbilst diviem vērtību pāriem x2k-1 un x2k, piemēram: tk =0 atbilst diviem pāriem - (0 ,1) un (1, 0) , un tk =1 – pāri (0,0) un (1,1).

3. darbība. Risinājumu skaita skaitīšana. Katram t ir 2 atrisinājumi, ts skaits ir 5. Tātad. mainīgajiem t ir 2 5 = 32 atrisinājumi. Bet katram t atbilst atrisinājumu pāris x, t.i. sākotnējā sistēmā ir 2*32 = 64 risinājumi. Atbilde: 64

Daļas risinājumu likvidēšanas metode Cik dažādas loģisko mainīgo vērtību kopas ir x1, x2, ..., x5, y1,y2,..., y5, kas atbilst visiem zemāk uzskaitītajiem nosacījumiem: (x1→ x2 )∧(x2→x3)∧(x3→x4 )∧(x4→x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 =1. Atbildē nav jāuzskaita visas dažādās kopas x1, x2, ..., x5, y 1 , y2, ... , y5, kurām šī vienādību sistēma ir spēkā. Atbildē jānorāda šādu komplektu skaits.

Risinājums. 1. darbība. Secīgs risinājums vienādojumi x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Pirmais vienādojums ir vairāku implikācijas operāciju konjunkcija, kas vienāda ar 1, t.i. katra no sekām ir patiesa. Implikācija ir nepatiesa tikai vienā gadījumā, kad 1  0, visos pārējos gadījumos (0  0, 0  1, 1  1) darbība atgriež 1. Rakstīsim to tabulas formā:

1. darbība. Vienādojumu secīgs risinājums T.o. Tika iegūti 6 risinājumu komplekti x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Spriežot līdzīgi, mēs nonākam pie secinājuma, ka y1, y2, y3, y4, y5 ir tāda pati risinājumu kopa. Jo šie vienādojumi ir neatkarīgi, t.i. tiem nav kopīgu mainīgo, tad šīs vienādojumu sistēmas risinājums (neņemot vērā trešo vienādojumu) būs 6 * 6 = 36 pāri “X” un “Y”. Aplūkosim trešo vienādojumu: y5→ x5 =1 Atrisinājums ir pāri: 0 0 0 1 1 1 Pāris nav risinājums: 1 0

Salīdzināsim iegūtos risinājumus, kur y5 =1, x5=0 neder. ir 5 šādi pāri Sistēmas risinājumu skaits: 36-5= 31. Atbilde: Vajadzēja 31 kombinatoriku!!!

Dinamiskās programmēšanas metode Cik dažādu risinājumu ir loģiskajam vienādojumam x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kur x 1, x 2, …, x 6 ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās mainīgo vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu daudzums.

Risinājuma solis 1. Nosacījuma analīze Pa kreisi vienādojumā implikācijas operācijas ir rakstītas secīgi, prioritāte ir vienāda. Pārrakstīsim: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Katrs nākamais mainīgais ir atkarīgs nevis no iepriekšējā, bet gan no iepriekšējās implikācijas rezultāta!

2. darbība. Modeļa atklāšana Apskatīsim pirmo implikāciju X 1 → X 2. Patiesības tabula: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 No viena 0 mēs saņēmām 2 vienības, bet no 1 mēs saņēmām vienu 0 un vienu 1. Ir tikai viens 0 un trīs 1, tas ir pirmās darbības rezultāts.

2. darbība. Parauga atklāšana Savienojot x 3 ar pirmās darbības rezultātu, iegūstam: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 No diviem 0 – divi 1, no katra 1 (ir 3) viens 0 un viens 1 (3+3)

Solis 3. Formulas atvasināšana T.o. jūs varat izveidot formulas nullju skaita N i un vieninieku skaita E i aprēķināšanai vienādojumam ar i mainīgajiem: ,

4. solis. Tabulas aizpildīšana Aizpildīsim tabulu no kreisās puses uz labo, ja i = 6, aprēķinot nulles un vieniniekus, izmantojot iepriekš minētās formulas; tabulā parādīts, kā tiek veidota nākamā kolonna no iepriekšējās: mainīgo skaits 1 2 3 4 5 6 Nuļļu skaits N i 1 1 3 5 11 21 Vieninieku skaits E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Atbilde: 43

Metode, izmantojot loģisko izteiksmju vienkāršojumus Cik dažādu risinājumu ir vienādojumam ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1, kur J, K, L, M, N ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās J, K, L, M un N vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits.

Risinājums Ņemiet vērā, ka J → K = ¬ J  K Ieviesīsim mainīgo izmaiņu: J → K=A, M  N  L =B Pārrakstīsim vienādojumu, ņemot vērā izmaiņas: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Acīmredzot A  B vienādām A un B vērtībām 6. Apsveriet pēdējo implikāciju M → J = 1 Tas ir iespējams, ja: M = J = 0 M = 0, J = 1 M = J = 1

Risinājums Jo A  B, tad Kad M=J=0 iegūstam 1 + K=0. Nav risinājumu. Ja M=0, J=1 iegūstam 0 + K=0, K=0, un N un L ir jebkuri, 4 risinājumi: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Risinājums 10. Kad M=J=1 iegūstam 0+K=1 *N * L, jeb K=N*L, 4 risinājumi: 11. Kopā ir 4+4=8 risinājumi Atbilde: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Informācijas avoti: O.B. Bogomolova, D.Ju. Usenkovs. B15: jauni uzdevumi un jauni risinājumi // Informātika, Nr. 6, 2012, lpp. 35 – 39. K.Yu. Poļakovs. Loģiskie vienādojumi // Informātika, 14.nr., 2011, lpp. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektroniskais resurss]. http://kpolyakov.narod.ru/school/ege.htm, [Elektroniskais resurss].