Kā atrisināt loģisko vienādojumu sistēmas. Loģisko vienādojumu risināšana matemātikā. Uzdevuma grūtības pakāpe

Pašvaldības budžets izglītības iestāde

"Vidēji vispārizglītojošā skola Nr. 18"

Baškortostānas Republikas Salavatas pilsētas pilsētas rajons

Loģisko vienādojumu sistēmas

eksāmena uzdevumos informātikā

Sadaļa "Loģikas algebras pamati" in LIETOŠANAS uzdevumi tiek uzskatīts par vienu no visgrūtākajiem un vāji atrisinātajiem. Vidējais uzdevumu izpildes procents par šo tēmu ir viszemākais un ir 43,2.

Kursu sadaļa	Vidējais izpildes procents pa uzdevumu grupām
Informācijas kodēšana un daudzuma mērīšana
informācijas modelēšana
Skaitļu sistēmas
Loģikas algebras pamati
Algoritmizācija un programmēšana
Informācijas un komunikācijas tehnoloģiju pamati

Pamatojoties uz 2018. gada KIM specifikāciju, šajā blokā ir iekļauti četri uzdevumi dažādi līmeņi grūtības.

№ uzdevumus	Pārbaudīts satura elementi	Uzdevuma grūtības pakāpe
	Spēja veidot patiesības tabulas loģika
	Spēja meklēt informāciju internetā
	Pamatjēdzienu un likumu pārzināšana matemātiskā loģika
	Spēja veidot un pārveidot loģiskās izteiksmes

23. uzdevums ir ar augstu grūtības pakāpi, tāpēc tam ir viszemākais izpildes procents. No apmācītajiem absolventiem (81-100 punkti) uzdevumu izpildīja 49,8%, vidēji sagatavotie (61-80 punkti) tiek galā ar 13,7%, pārējā studentu grupa šo uzdevumu neizpilda.

Loģisko vienādojumu sistēmas risināšanas panākumi ir atkarīgi no loģikas likumu zināšanām un no precīzas sistēmas risināšanas metožu pielietošanas.

Apsveriet loģisko vienādojumu sistēmas risinājumu ar kartēšanas metodi.

(23.154 Poļakovs K.Ju.) Cik dažādu atrisinājumu ir vienādojumu sistēmai?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

kur x1 , x2 ,…, x8, plkst1 ,y2 ,…,y8 - Būla 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 skaits.

Risinājums. Visi sistēmā iekļautie vienādojumi ir viena veida, un katrā vienādojumā ir iekļauti četri mainīgie. Zinot x1 un y1, mēs varam atrast visas iespējamās x2 un y2 vērtības, kas apmierina pirmo vienādojumu. Argumentējot līdzīgi, no zināmajiem x2 un y2 varam atrast x3, y3, kas apmierina otro vienādojumu. Tas ir, zinot pāri (x1 , y1) un nosakot pāra vērtību (x2 , y2) , mēs atradīsim pāri (x3 , y3 ), kas savukārt novedīs pie pāra (x4 , y4 ) un tā ieslēgts.

Atradīsim visus pirmā vienādojuma atrisinājumus. To var izdarīt divos veidos: izveidot patiesības tabulu, argumentējot un piemērojot loģikas likumus.

Patiesības tabula:

				x 1  g 1	x2  y2	(x 1  y1)  (x 2  y2)	(x 1  x2)	(y 1  y2)	(x 1  x2)  (y 1  y2)

Patiesības tabulas veidošana ir darbietilpīga un laika ziņā neefektīva, tāpēc izmantojam otro metodi – loģisko spriešanu. Produkts ir 1 tad un tikai tad, ja katrs faktors ir 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Apsveriet pirmo vienādojumu. Tālāk ir vienāds ar 1, kad 0 0, 0 1, 1 1, tad (x1 y1)=0 pie (01), (10), tad pāris (x2  y2 ) var būt jebkurš (00), (01), (10), (11) un (x1 y1)=1, t.i., (00) un (11) pārim (x2 y2)=1 ir vienādas vērtības (00) un (11). No šī risinājuma izslēdzam tos pārus, kuriem otrais un trešais vienādojums ir nepatiess, tas ir, x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

Kopējais pāru skaits 1+1+1+22= 25

2) (23.160 Poļakovs K.Ju.) Cik dažādu risinājumu ir loģisko vienādojumu sistēmai

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Risinājums. 1) Vienādojumi ir viena veida, tāpēc ar spriešanas metodi mēs atradīsim visus iespējamos pirmā vienādojuma pārus (x1,y1), (x2,y2).

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Otrā vienādojuma atrisinājums ir pāri (00), (01), (11).

Atradīsim pirmā vienādojuma risinājumus. Ja x1=0, tad x2 , y2 - jebkurš, ja x1=1, tad x2 , y2 pieņem vērtību (11).

Izveidosim savienojumus starp pāriem (x1 , y1) un (x2 , y2).

(x1 , y1 )	(x2 , y2 )

Izveidosim tabulu, lai aprēķinātu pāru skaitu katrā posmā.

							0

Ņemot vērā pēdējā vienādojuma atrisinājumus x 7  y 7 = 1, mēs likvidējam pāri (10). Atrodi kopējo risinājumu skaitu 1+7+0+34=42

3)(23.180) Cik dažādu risinājumu ir loģisko vienādojumu sistēmai

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Risinājums. 1) Vienādojumi ir viena veida, tāpēc ar spriešanas metodi atradīsim visus iespējamos pirmā vienādojuma pārus (x1,x2), (x3,x4).

(x1  x2 )  (x3  x4 ) = 1

No risinājuma izslēdzam pārus, kas turpmāk dod 0 (1 0), tie ir pāri (01, 00, 11) un (10).

Izveidojiet saites starp pāriem (x1,x2), (x3,x4)

Var atšķirt dažādi veidi 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:

Apsveriet reducēš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ā, ekvivalentā sistēmai, izmantojot loģisko darbību "UN". Pēc tam jums ir jāveic iegūtā vienādojuma transformācijas, pamatojoties uz loģikas algebras likumiem, un jāiegūst konkrēts sistēmas risinājums.

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

Apzīmēsim nozīmi, izmantojot pamatoperācijas "OR", "NOT":

Tā kā vienādojumu kreisās puses ir vienādas ar 1, varat 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 rezultātu:

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

Nākamais veids ir patiesības tabulu konstruēšana . Tā kā loģiskajām vērtībām ir tikai divas vērtības, varat vienkārši apskatīt visas iespējas un atrast starp tām tās, kurām šī sistēma vienādojumi. Tas ir, mēs izveidojam vienu kopīgu patiesības tabulu visiem sistēmas vienādojumiem un atrodam līniju ar vēlamajām vērtībām.

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

0	0	1	1	0	1

Treknraksts ir līnija, kurai ir izpildīti problēmas nosacījumi. Tātad A=0, B=0 un C=1.

veids sadalīšanās . Ideja ir fiksēt viena mainīgā vērtību (piešķirt to 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ā - С=1. Sistēmas risinājums: A = 0, B = 0 un C = 1.

Lietojot datorzinātnēs, ļoti bieži ir nepieciešams noteikt loģisko vienādojumu sistēmas risinājumu skaitu, neatrodot pašus risinājumus, tam ir arī noteiktas metodes. Galvenais veids, kā atrast risinājumu skaitu loģisko vienādojumu sistēmai, irmainīgo lielumu maiņa. Pirmkārt, ir nepieciešams pēc iespējas vienkāršot katru vienādojumu, pamatojoties uz loģikas algebras likumiem, un pēc tam vienādojumu kompleksās daļas aizstāt ar jauniem mainīgajiem un noteikt risinājumu skaitu. 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 Būla 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 šādā formā: X + Y = 1.

Disjunkcija ir patiesa trīs gadījumos: (0;1), (1;0) un (1;1), savukārt X un Y ir implikācija, 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 kopumā iespējamie risinājumi dots vienādojums 3+9=15.

Sekojošais veids, kā noteikt loģisko vienādojumu sistēmas risinājumu skaitu, ir − binārais koks. Apskatīsim šo metodi ar 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.

Izliksimies tā 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 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 atrisinā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ā, iegūstam, ka vienādojuma risinājumi ir šādas mainīgo kopas (m + 1 risinājums, katram risinājumam ir 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 dažādu konstruētā koka zaru skaits. Ir viegli redzēt, ka tas ir vienāds ar m + 1.

	Koks	Lēmumu skaits
x 1
x2
x 3
		…

Spriešanas grūtību gadījumā niyah un būvniecības derisinājumu rūkoņa, jūs varat meklēt risinājumu ar izmantojot patiesības tabulas, vienam vai diviem vienādojumiem.

Mēs pārrakstām vienādojumu sistēmu šādā formā:

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

x 1	x2	(x 1 → x 2)

Izveidosim patiesības tabulu diviem vienādojumiem:

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

Loģisko vienādojumu sistēmu risināšanas veidi

Kirgizova E.V., Ņemkova A.E.

Lesosibirskas pedagoģiskais institūts -

Sibīrijas atzars federālā universitāte, Krievija

Spēja konsekventi domāt, pārliecinoši argumentēt, izvirzīt hipotēzes, atspēkot negatīvus secinājumus nerodas pati par sevi, šo prasmi attīsta loģikas zinātne. Loģika ir zinātne, kas pēta metodes, kā noteikt dažu apgalvojumu patiesumu vai nepatiesību, pamatojoties uz citu apgalvojumu patiesumu vai nepatiesību.

Šīs zinātnes pamatu apgūšana nav iespējama bez loģisku problēmu risināšanas. Prasmju veidošanās pārbaude, lai pielietotu savas zināšanas jaunā situācijā, tiek veikta, nokārtojot. Jo īpaši tā ir spēja atrisināt loģiskie uzdevumi. Eksāmenā B15 uzdevumi ir paaugstinātas sarežģītības uzdevumi, jo tie satur loģisko vienādojumu sistēmas. Ir dažādi veidi, kā atrisināt loģisko vienādojumu sistēmas. Tas ir reducēšana uz vienu vienādojumu, patiesības tabulas konstruēšana, sadalīšana, vienādojumu secīgs risinājums utt.

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

Apsveriet reducēš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ā, ekvivalentā sistēmai, izmantojot loģisko darbību "UN". Pēc tam jums jāveic iegūtā vienādojuma transformācijas, pamatojoties uz loģikas algebras likumiem, un jāiegūst konkrēts sistēmas risinājums.

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

Apzīmēsim nozīmi, izmantojot pamatoperācijas "OR", "NOT":

Tā kā vienādojumu kreisās puses ir vienādas ar 1, varat 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 rezultātu:

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

Nākamais veids ir patiesības tabulu konstruēšana . Tā kā loģiskajām vērtībām ir tikai divas vērtības, varat vienkārši iziet cauri visām iespējām un starp tām atrast tos, kuriem dotā vienādojumu sistēma ir apmierināta. Tas ir, mēs izveidojam vienu kopīgu patiesības tabulu visiem sistēmas vienādojumiem un atrodam līniju ar vēlamajām vērtībām.

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

0	0	1	1	0	1

Treknraksts ir līnija, kurai ir izpildīti problēmas nosacījumi. Tātad A =0, B =0 un C =1.

veids sadalīšanās . Ideja ir fiksēt viena mainīgā vērtību (piešķirt to 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 mēs iegūstam B =0, un no otrā - С=1. Sistēmas risinājums: A = 0 , B = 0 un C = 1 .

Varat arī izmantot metodi vienādojumu secīgs risinājums , katrā darbībā pievienojot apskatāmajai kopai vienu mainīgo. Lai to izdarītu, vienādojumus nepieciešams pārveidot tā, lai mainīgie tiktu ievadīti alfabētiskā secībā. Tālāk mēs izveidojam lēmumu koku, secīgi pievienojot tam mainīgos.

Sistēmas pirmais vienādojums ir atkarīgs tikai no A un B, bet otrais vienādojums no A un C. Mainīgajam A var būt 2 vērtības 0 un 1:

No pirmā vienādojuma izriet, ka , tad, kad A = 0 mēs iegūstam B = 0, un A = 1 mums ir B = 1. Tātad pirmajam vienādojumam ir divi risinājumi attiecībā uz mainīgajiem lielumiem A un B .

Mēs izveidojam otro vienādojumu, no kura mēs katrai opcijai nosakām C vērtības. Ja A =1, implikācija nevar būt nepatiesa, tas ir, koka otrajam zaram nav atrisinājuma. Plkst A= 0 mēs iegūstam vienīgo risinājumu C= 1 :

Tādējādi mēs ieguvām sistēmas atrisinājumu: A = 0 , B = 0 un C = 1 .

Lietojot datorzinātnēs, ļoti bieži ir nepieciešams noteikt loģisko vienādojumu sistēmas risinājumu skaitu, neatrodot pašus risinājumus, tam ir arī noteiktas metodes. Galvenais veids, kā atrast risinājumu skaitu loģisko vienādojumu sistēmai, ir mainīgo lielumu maiņa. Pirmkārt, ir nepieciešams, cik vien iespējams, vienkāršot katru vienādojumu, pamatojoties uz loģikas algebras likumiem, un pēc tam aizstāt vienādojumu sarežģītās daļas ar jauniem mainīgajiem un noteikt jaunās sistēmas risinājumu skaitu. Pēc tam atgriezieties pie nomaiņas un nosakiet tam risinājumu skaitu.

Uzdevums:Cik atrisinājumu veido vienādojums ( A → B ) + (C → D ) = 1? Kur A, B, C, D ir Būla mainīgie.

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

Disjunkcija ir patiesa trīs gadījumos: (0;1), (1;0) un (1;1), savukārt X un Y ir norāde, 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. Līdz ar to šī vienādojuma iespējamie risinājumi ir 3+9=15.

Sekojošais veids, kā noteikt loģisko vienādojumu sistēmas risinājumu skaitu, ir − binārais koks. Apskatīsim šo metodi ar 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.

Izliksimies tāx 1 ir taisnība, tad no pirmā vienādojuma mēs to iegūstamx 2 arī taisnība, no otrā -x 3 =1 un tā tālāk līdz x m= 1. Līdz ar to kopa (1; 1; …; 1) no m vienības ir sistēmas risinājums. Ļaujiet tagadx 1 =0, tad no pirmā vienādojuma mums irx 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 atrisinājums. Plkstx 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, katrā risinājumā m mainīgās 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 dažādu konstruētā koka zaru skaits. Ir viegli redzēt, ka tā ir m+1.

Mainīgie lielumi	Koks	Lēmumu skaits
x 1
x2
x 3

Ja rodas grūtības argumentācijā un lēmumu koka veidošanā, varat meklēt risinājumu, izmantojot patiesības tabulas, vienam vai diviem vienādojumiem.

Mēs pārrakstām vienādojumu sistēmu šādā formā:

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

x 1	x2	(x 1 → x 2)

Izveidosim patiesības tabulu diviem vienādojumiem:

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

Tālāk var redzēt, ka viens vienādojums ir patiess šādos trīs gadījumos: (0; 0), (0; 1), (1; 1). Divu vienādojumu sistēma ir patiesa četros gadījumos (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Šajā gadījumā uzreiz ir skaidrs, ka ir risinājums, kas sastāv tikai no nullēm un vairāk m risinājumus, kuros tiek pievienota viena vienība, sākot no pēdējās pozīcijas līdz tiek aizpildītas visas iespējamās vietas. Var pieņemt, ka kopīgs lēmums būs tāda pati forma, taču, lai šāda pieeja būtu risinājums, ir jāpierāda, ka pieņēmums ir patiess.

Apkopojot visu iepriekš minēto, es vēlos vērst uzmanību uz to, ka ne visas aplūkotās metodes ir universālas. Risinot katru loģisko vienādojumu sistēmu, jāņem vērā tās pazīmes, uz kuru pamata jāizvēlas risināšanas metode.

Literatūra:

1. Loģiskie uzdevumi / O.B. Bogomolovs — 2. izd. – M.: BINOM. Zināšanu laboratorija, 2006. - 271 lpp.: ill.

2. Poļakovs K.Ju. Loģisko vienādojumu sistēmas / Mācību un metodiskā avīze informātikas skolotājiem: Informātika Nr.14, 2011

Loģisko vienādojumu sistēmu risināšanas metodes

Jūs varat atrisināt loģisko vienādojumu sistēmu, piemēram, izmantojot patiesības tabulu (ja mainīgo lielumu skaits nav pārāk liels) vai izmantojot lēmumu koku, pēc katra vienādojuma vienkāršošanas.

1. Mainīgo lielumu maiņas metode.

Jaunu mainīgo ieviešana ļauj vienkāršot vienādojumu sistēmu, samazinot nezināmo skaitu.Jaunajiem mainīgajiem ir jābūt neatkarīgiem vienam no otra. Pēc vienkāršotās sistēmas atrisināšanas atkal jāatgriežas pie sākotnējiem mainīgajiem.

Apsveriet šīs metodes piemērošanu konkrētā piemērā.

Piemērs.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Risinājums:

Ieviesīsim jaunus mainīgos: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Uzmanību! Katrs no to mainīgajiem x1, x2, …, x10 ir jāiekļauj tikai vienā no jaunajiem mainīgie A, B, C, D, E, t.i. jauni mainīgie ir neatkarīgi viens no otra).

Tad vienādojumu sistēma izskatīsies šādi:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Izveidosim iegūtās sistēmas lēmumu koku:

Aplūkosim vienādojumu A=0, t.i. (X1≡ X2)=0. Tam ir 2 saknes:

		X1 ≡ X2

No tās pašas tabulas var redzēt, ka vienādojumam A \u003d 1 ir arī 2 saknes. Sakārtosim sakņu skaitu lēmumu kokā:

Lai atrastu risinājumu skaitu vienai filiālei, ir jāreizina risinājumu skaits katrā līmenī. Kreisajā zarā ir 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 risinājumi; labajā zarā ir arī 32 risinājumi. Tie. visā sistēmā ir 32+32=64 risinājumi.

Atbilde: 64.

2. Spriešanas metode.

Loģisko vienādojumu sistēmu risināšanas sarežģītība slēpjas pilnīga lēmumu koka apjomā. Spriešanas metode ļauj nebūvēt visu koku pilnībā, bet tajā pašā laikā saprast, cik zaru tam būs. Apskatīsim šo metodi konkrētos piemēros.

1. piemērs Cik dažādu Būla mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas atbilst visiem tālāk norādītajiem nosacījumiem?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

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

x1\/y1 =1

Atbildē nav jāuzskaita visas dažādās mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopas, saskaņā ar kurām tiek izpildīta dotā vienādību sistēma. Kā atbilde jums jānorāda šādu komplektu skaits.

Risinājums:

Pirmajā un otrajā vienādojumā ir neatkarīgi mainīgie, kas ir saistīti ar trešo nosacījumu. Izveidosim lēmumu koku pirmajam un otrajam vienādojumam.

Lai attēlotu sistēmas lēmumu koku no pirmā un otrā vienādojuma, ir jāturpina katrs pirmā koka zars ar mainīgo koku plkst . Šādā veidā uzbūvētajam kokam būs 36 zari. Dažas no šīm atzarēm neatbilst sistēmas trešajam vienādojumam. Uz pirmā koka atzīmējiet koka zaru skaitu"pie" , kas apmierina trešo vienādojumu:

Precizēsim: trešā nosacījuma izpildei pie x1=0 jābūt y1=1, t.i., visiem koka zariem"X" , kur x1=0 var turpināt tikai ar vienu zaru no koka"pie" . Un tikai vienam koka zaram"X" (pa labi) atbilst visiem koka zariem"pie". Tādējādi visas sistēmas pilnajā kokā ir 11 zari. Katrs zars ir viens sākotnējās vienādojumu sistēmas risinājums. Tātad visai sistēmai ir 11 risinājumi.

Atbilde: 11.

2. piemērs Cik dažādu risinājumu ir vienādojumu sistēmai

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10) = 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10) = 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10) = 1

(X1 ≡ X10) = 0

kur x1, x2, …, x10 ir Būla 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 skaits.

Risinājums: Vienkāršosim sistēmu. Izveidosim pirmā vienādojuma daļas patiesības tabulu:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)

Pievērsiet uzmanību pēdējai kolonnai, tā atbilst darbības rezultātam X1 ≡ X10.

X1 ≡ X10

Pēc vienkāršošanas mēs iegūstam:

(X1 ≡ X2) ∨ (X1 ≡ X10) = 1

(X2 ≡ X3) ∨ (X2 ≡ X10) = 1

(X3 ≡ X4) ∨ (X3 ≡ X10) = 1

……

(X9 ≡ X10) ∨ (X9 ≡ X10) = 1

(X1 ≡ X10) = 0

Apsveriet pēdējo vienādojumu:(X1 ≡ X10) = 0, t.i. x1 nedrīkst būt tāds pats kā x10. Lai pirmais vienādojums būtu vienāds ar 1, vienādībai ir jābūt spēkā(X1 ≡ X2)=1, t.i. x1 ir jāatbilst x2.

Izveidosim lēmumu koku pirmajam vienādojumam:

Apsveriet otro vienādojumu: x10 = 1 un x2 = 0 iekavajābūt vienādam ar 1 (t.i., x2 ir tāds pats kā x3); pie x10=0 un pie x2=1 iekava(X2 ≡ X10) = 0, tātad iekava (X2 ≡ X3) jābūt vienādam ar 1 (t.i., x2 ir tāds pats kā x3):

Argumentējot šādā veidā, mēs izveidojam lēmumu koku visiem vienādojumiem:

Tādējādi vienādojumu sistēmai ir tikai 2 risinājumi.

Atbilde: 2.

3. piemērs

Cik dažādu Būla mainīgo x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 vērtību kopu ir, kas atbilst visiem tālāk norādītajiem nosacījumiem?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Risinājums:

Izveidosim 1. vienādojuma lēmumu koku:

Apsveriet otro vienādojumu:

• Kad x1=0 : otrā un trešā iekava būs 0; lai pirmā iekava būtu vienāda ar 1, ir jābūt y1=1 , z1=1 (t.i., šajā gadījumā - 1 risinājums)
• Ar x1=1 : pirmā iekava būs 0; otrais vai trešajai iekavai jābūt vienādai ar 1; otrā iekava būs vienāda ar 1, ja y1=0 un z1=1; trešā iekava būs vienāda ar 1, ja y1=1 un z1=0 (t.i., šajā gadījumā - 2 risinājumi).

Līdzīgi arī pārējiem vienādojumiem. Ievērojiet katram koka mezglam iegūto risinājumu skaitu:

Lai noskaidrotu atrisinājumu skaitu katram zaram, iegūtos skaitļus reizinām katram zaram atsevišķi (no kreisās uz labo).

1 zars: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 risinājums

2 atzars: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 risinājumi

3. zars: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 risinājumi

4 filiāle: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 risinājumi

5 filiāle: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 risinājumi

Saskaitīsim iegūtos skaitļus: kopā 31 risinājums.

Atbilde: 31.

3. Regulāra sakņu skaita palielināšana

Dažās sistēmās nākamā vienādojuma sakņu skaits ir atkarīgs no iepriekšējā vienādojuma sakņu skaita.

1. piemērs Cik dažādu Būla mainīgo x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 vērtību kopu ir, kas atbilst visiem tālāk norādītajiem nosacījumiem?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Vienkāršot pirmais vienādojums:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3= ¬(x1 ≡ x3). Pēc tam sistēma iegūs šādu formu:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4) = 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

utt.

Katram nākamajam vienādojumam ir par 2 saknēm vairāk nekā iepriekšējam.

4 vienādojumam ir 12 saknes;

5. vienādojumam ir 14 saknes

8 vienādojumam ir 20 saknes.

Atbilde: 20 saknes.

Dažreiz sakņu skaits aug saskaņā ar Fibonači skaitļu likumu.

Loģisko vienādojumu sistēmas risināšanai nepieciešama radoša pieeja.

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

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ās funkcija F iegūst vērtību true (1). Atlikušās kopas ir vienādojuma C atrisinājumi, kas vienāds ar nulli. Mēs vienmēr varam ņemt vērā tikai formas vienādojumus:

Patiešām, dosim vienādojumu:

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

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

Sistēmas risinājums ir mainīgo lielumu kopa, uz kuras ir izpildīti visi sistēmas vienādojumi. Saistībā ar loģiskās funkcijas Lai iegūtu loģisko vienādojumu sistēmas risinājumu, jāatrod kopa, uz kuras ir patiesa loģiskā funkcija Ф, kas attēlo sākotnējo funkciju konjunkciju:

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 atrisinājumu sistēmai ir un kādas ir kopas, kas dod risinājumus.

Dažos Vienotā valsts pārbaudījuma uzdevumos par risinājumu meklēšanu loģisko vienādojumu sistēmai mainīgo lielumu skaits sasniedz 10. Tad patiesības tabulas izveidošana kļūst par gandrīz neatrisināmu uzdevumu. Problēmas risināšanai nepieciešama cita pieeja. Patvaļīgai vienādojumu sistēmai nav vispārīgs veids, kas atšķiras no uzskaitīšanas, kas ļauj atrisināt šādas problēmas.

Eksāmenā piedāvātajos uzdevumos risinājuma pamatā parasti ir vienādojumu sistēmas specifikas ņemšana vērā. Es atkārtoju, ka, izņemot visu mainīgo kopas variantu uzskaitīšanu, nav vispārēja veida problēmas risināšanai. 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.

Kas ir binārais lēmumu koks un kā tas tiek veidots, es paskaidrošu ar vairāku uzdevumu piemēriem.

18. problēma

Cik dažādu Būla 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ā tika 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. Lūk, kā izskatās šī koka grafiskais attēls

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 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ā vērtības, kurām vienādojumā ir patiesa vērtība. Tā kā vienādojums definē implikāciju, atzaram, kuram tā vērtība ir 1, šajā atzarā ir jābūt vērtībai 1. Atzars, kurā tā vērtība ir 0, ģenerē divus atzarus ar vērtībām, kas vienādas ar 0 un 1. Konstruētais koks definē trīs risinājumus, kur implikācija iegūst vērtību 1. Uz katra zara tiek izrakstīta atbilstošā 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. 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. Vienīgais zars, kurā mainīgajam ir vērtība 0, iedos atzaru divās atzaros, kur mainīgais iegūs 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ā izmantoti mainīgie Y. Arī šim vienādojumam ir 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 Būla mainīgo x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 vērtību kopu ir, kas atbilst visiem tālāk norādī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 X un Y mainīgajiem.

No vienādojuma izriet, ka, ja tam ir vērtība 1 (viens šāds risinājums pastāv), tad tam ir vērtība 1. Tādējādi ir viena kopa, uz kuras un kurām ir vērtības 1. Ja tā ir vienāda ar 0, tai var būt jebkura vērtība, gan 0, gan 1. Tāpēc katra kopa ar 0, un šādas kopas ir 5, 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 ekvivalenci, 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:

Š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?