Institusyong pang-edukasyon sa badyet ng munisipyo

"Secondary school No. 18"

urban na distrito ng lungsod ng Salavat ng Republika ng Bashkortostan

Mga sistema ng lohikal na equation

sa mga gawain ng pagsusulit sa informatics

Ang seksyong "Mga Batayan ng Algebra ng Logic" sa mga gawain ng pagsusulit ay itinuturing na isa sa pinakamahirap at hindi maayos na nalutas. Ang average na porsyento ng pagkumpleto ng mga gawain sa paksang ito ay ang pinakamababa at 43.2.

Seksyon ng kurso	Average na porsyento ng pagkumpleto ng mga pangkat ng mga gawain
Pag-coding ng impormasyon at pagsukat ng dami nito
pagmomodelo ng impormasyon
Mga sistema ng numero
Mga Batayan ng Algebra ng Logic
Algorithmization at programming
Mga pangunahing kaalaman sa teknolohiya ng impormasyon at komunikasyon

Batay sa detalye ng KIM 2018, ang block na ito ay may kasamang apat na gawain ng iba't ibang antas ng pagiging kumplikado.

№ mga gawain	Sinuri mga elemento ng nilalaman	Antas ng kahirapan sa gawain
	Kakayahang bumuo ng mga talahanayan ng katotohanan at logic circuit
	Kakayahang maghanap ng impormasyon sa Internet
	Kaalaman sa mga pangunahing konsepto at batas lohika ng matematika
	Kakayahang bumuo at magbago ng mga lohikal na expression

Ang Gawain 23 ay isang mataas na antas ng kahirapan, samakatuwid ito ay may pinakamababang porsyento ng pagkumpleto. Sa mga sinanay na nagtapos (81-100 puntos) 49.8% nakumpleto ang gawain, ang karaniwang inihanda (61-80 puntos) ay nakayanan ng 13.7%, ang natitirang pangkat ng mga mag-aaral ay hindi nakumpleto ang gawaing ito.

Ang tagumpay ng paglutas ng isang sistema ng mga lohikal na equation ay nakasalalay sa kaalaman sa mga batas ng lohika at sa tumpak na aplikasyon ng mga pamamaraan para sa paglutas ng sistema.

Isaalang-alang ang solusyon ng isang sistema ng mga lohikal na equation sa pamamagitan ng paraan ng pagmamapa.

(23.154 Polyakov K.Yu.) Ilang magkakaibang solusyon mayroon ang sistema ng mga equation?

((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

saan x1 , x2 ,…, x8, sa1 ,y2 ,…,y8 - Mga variable ng Boolean? Hindi kailangang ilista ng sagot ang lahat ng iba't ibang hanay ng mga variable na halaga kung saan pinanghahawakan ang pagkakapantay-pantay na ito. Bilang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Desisyon. Ang lahat ng mga equation na kasama sa system ay may parehong uri, at apat na variable ang kasama sa bawat equation. Sa pag-alam sa x1 at y1, mahahanap natin ang lahat ng posibleng halaga ng x2 at y2 na nakakatugon sa unang equation. Ang pagtatalo sa katulad na paraan, mula sa kilalang x2 at y2 ay mahahanap natin ang x3, y3 na nakakatugon sa pangalawang equation. Iyon ay, ang pag-alam sa pares (x1 , y1) at pagtukoy sa halaga ng pares (x2 , y2) , makikita natin ang pares (x3 , y3 ), na hahantong sa pares (x4 , y4 ) at iba pa. sa.

Hanapin natin ang lahat ng solusyon ng unang equation. Magagawa ito sa dalawang paraan: upang bumuo ng talahanayan ng katotohanan, sa pamamagitan ng pangangatwiran at paglalapat ng mga batas ng lohika.

Talahanayan ng katotohanan:

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

Ang pagbuo ng talahanayan ng katotohanan ay matrabaho at hindi epektibo sa oras, kaya ginagamit namin ang pangalawang paraan - lohikal na pangangatwiran. Ang produkto ay 1 kung at kung ang bawat salik ay 1.

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

(x1  x2 ) =1

(y1  y2 ) =1

Isaalang-alang ang unang equation. Ang sumusunod ay katumbas ng 1, kapag 0 0, 0 1, 1 1, pagkatapos (x1 y1)=0 sa (01), (10), pagkatapos ay ang pares (x2  y2 ) maaaring alinman sa (00), (01), (10), (11), at para sa (x1 y1)=1, ibig sabihin, (00) at (11) ang pares (x2 y2)=1 ay tumatagal ng parehong mga halaga (00) at (11). Ibinubukod namin mula sa solusyon na ito ang mga pares kung saan mali ang pangalawa at pangatlong equation, iyon ay, x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

Kabuuang bilang ng mga pares 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Ilang iba't ibang solusyon mayroon ang isang sistema ng mga lohikal na equation

(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

Desisyon. 1) Ang mga equation ay may parehong uri, kaya sa pamamagitan ng paraan ng pangangatwiran ay mahahanap natin ang lahat ng posibleng mga pares (x1,y1), (x2,y2) ng unang equation.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Ang solusyon ng pangalawang equation ay mga pares (00), (01), (11).

Maghanap tayo ng mga solusyon sa unang equation. Kung x1=0, kung gayon x2 , y2 - anuman, kung x1=1, kung gayon ang x2 , y2 ay kumukuha ng halaga (11).

Gumawa tayo ng mga koneksyon sa pagitan ng mga pares (x1 , y1) at (x2 , y2).

(x1 , y1 )	(x2 , y2 )

Gumawa tayo ng talahanayan upang kalkulahin ang bilang ng mga pares sa bawat yugto.

							0

Isinasaalang-alang ang mga solusyon ng huling equation x 7  y 7 = 1, inaalis namin ang pares (10). Hanapin ang kabuuang bilang ng mga solusyon 1+7+0+34=42

3)(23.180) Ilang magkakaibang solusyon mayroon ang sistema ng mga lohikal na equation

(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

Desisyon. 1) Ang mga equation ay may parehong uri, kaya sa pamamagitan ng paraan ng pangangatwiran ay mahahanap natin ang lahat ng posibleng mga pares (x1,x2), (x3,x4) ng unang equation.

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

Ibinubukod namin mula sa solusyon ang mga pares na nagbibigay ng 0 (1 0) sa mga sumusunod, ito ang mga pares (01, 00, 11) at (10).

Bumuo ng mga link sa pagitan ng mga pares (x1,x2), (x3,x4)

Mayroong iba't ibang mga paraan upang malutas ang mga sistema ng mga lohikal na equation. Ito ay isang pagbawas sa isang equation, ang pagbuo ng isang talahanayan ng katotohanan at pagkabulok.

Gawain: Lutasin ang isang sistema ng mga lohikal na equation:

Isipin mo paraan ng pagbabawas sa isang equation . Ang pamamaraang ito ay nagsasangkot ng pagbabago ng mga lohikal na equation, upang ang kanilang kanang bahagi ay katumbas ng halaga ng katotohanan (iyon ay, 1). Upang gawin ito, gamitin ang pagpapatakbo ng lohikal na negation. Pagkatapos, kung may mga kumplikadong lohikal na operasyon sa mga equation, pinapalitan namin ang mga ito ng mga pangunahing: "AT", "O", "HINDI". Ang susunod na hakbang ay upang pagsamahin ang mga equation sa isa, katumbas ng sistema, gamit ang lohikal na operasyon na "AT". Pagkatapos nito, dapat kang gumawa ng mga pagbabago sa resultang equation batay sa mga batas ng algebra ng lohika at kumuha ng isang tiyak na solusyon sa system.

Solusyon 1: Ilapat ang inversion sa magkabilang panig ng unang equation:

Katawanin natin ang implikasyon sa pamamagitan ng mga pangunahing operasyong "OR", "NOT":

Dahil ang kaliwang bahagi ng mga equation ay katumbas ng 1, maaari mong pagsamahin ang mga ito gamit ang "AT" na operasyon sa isang equation na katumbas ng orihinal na sistema:

Binuksan namin ang unang bracket ayon sa batas ni de Morgan at binago namin ang resulta:

Ang resultang equation ay may isang solusyon: A=0, B=0 at C=1.

Ang susunod na paraan ay pagbuo ng mga talahanayan ng katotohanan . Dahil ang mga lohikal na dami ay may dalawang halaga lamang, maaari mo lamang na dumaan sa lahat ng mga pagpipilian at hanapin kasama ng mga ito ang mga kung saan ang ibinigay na sistema ng mga equation ay nasiyahan. Iyon ay, bumuo kami ng isang karaniwang talahanayan ng katotohanan para sa lahat ng mga equation ng system at makahanap ng isang linya na may mga nais na halaga.

Solusyon 2: Gumawa tayo ng talahanayan ng katotohanan para sa system:

0	0	1	1	0	1

Bold ang linya kung saan natutugunan ang mga kondisyon ng problema. Kaya A=0, B=0 at C=1.

Paraan pagkabulok . Ang ideya ay upang ayusin ang halaga ng isa sa mga variable (ilagay ito katumbas ng 0 o 1) at sa gayon ay gawing simple ang mga equation. Pagkatapos ay maaari mong ayusin ang halaga ng pangalawang variable, at iba pa.

Solusyon 3: Hayaan ang A = 0, pagkatapos ay:

Mula sa unang equation nakukuha natin ang B = 0, at mula sa pangalawa - С=1. Solusyon ng system: A = 0, B = 0 at C = 1.

Sa USE sa computer science, madalas na kinakailangan upang matukoy ang bilang ng mga solusyon sa isang sistema ng mga lohikal na equation, nang hindi nahahanap ang mga solusyon sa kanilang sarili, mayroon ding ilang mga pamamaraan para dito. Ang pangunahing paraan upang mahanap ang bilang ng mga solusyon sa isang sistema ng mga lohikal na equation aypagbabago ng mga variable. Una, kinakailangan na gawing simple ang bawat isa sa mga equation hangga't maaari batay sa mga batas ng algebra ng lohika, at pagkatapos ay palitan ang mga kumplikadong bahagi ng mga equation ng mga bagong variable at matukoy ang bilang ng mga solusyon sa bagong sistema. Pagkatapos ay bumalik sa kapalit at tukuyin ang bilang ng mga solusyon para dito.

Gawain: Ilang solusyon mayroon ang equation (A → B ) + (C → D ) = 1? Kung saan ang A, B, C, D ay mga boolean variable.

Desisyon: Ipakilala natin ang mga bagong variable: X = A → B at Y = C → D . Isinasaalang-alang ang mga bagong variable, ang equation ay isusulat sa anyo: X + Y = 1.

Ang disjunction ay totoo sa tatlong kaso: (0;1), (1;0) at (1;1), habang ang X at Y ay isang implikasyon, iyon ay, ito ay totoo sa tatlong kaso at mali sa isa. Samakatuwid, ang kaso (0;1) ay tumutugma sa tatlong posibleng kumbinasyon ng mga parameter. Case (1;1) - ay tumutugma sa siyam na posibleng kumbinasyon ng mga parameter ng orihinal na equation. Samakatuwid, mayroong 3+9=15 posibleng solusyon ng equation na ito.

Ang sumusunod na paraan upang matukoy ang bilang ng mga solusyon sa isang sistema ng mga lohikal na equation ay − binary tree. Isaalang-alang natin ang pamamaraang ito sa isang halimbawa.

Gawain: Ilang magkakaibang solusyon mayroon ang sistema ng mga lohikal na equation:

Ang ibinigay na sistema ng mga equation ay katumbas ng equation:

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

Magpanggap na tayo x 1 ay totoo, pagkatapos ay mula sa unang equation makuha namin iyon x 2 totoo rin, mula sa pangalawa - x 3 =1, at iba pa hanggang x m= 1. Nangangahulugan ito na ang set (1; 1; …; 1) ng m unit ay ang solusyon ng system. Hayaan mo na x 1 =0, pagkatapos ay mula sa unang equation na mayroon kami x 2 =0 o x 2 =1.

Kailan x 2 totoo, nakuha namin na ang iba pang mga variable ay totoo rin, iyon ay, ang set (0; 1; ...; 1) ay ang solusyon ng system. Sa x 2 =0 makuha natin iyan x 3 =0 o x 3 =, at iba pa. Ang pagpapatuloy sa huling variable, nakuha namin na ang mga solusyon ng equation ay ang mga sumusunod na hanay ng mga variable (m + 1 solusyon, ang bawat solusyon ay may m mga halaga ng mga variable):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ang diskarte na ito ay mahusay na inilarawan sa pamamagitan ng pagbuo ng isang binary tree. Ang bilang ng mga posibleng solusyon ay ang bilang ng iba't ibang sanga ng itinayong puno. Madaling makita na ito ay katumbas ng m + 1.

	Kahoy	Bilang ng mga desisyon
x 1
x2
x 3
		…

Sa kaso ng mga kahirapan sa pangangatwiran niyah at construction dedagundong ng mga solusyon, maaari kang maghanap ng solusyon sa gamit mga talahanayan ng katotohanan, para sa isa o dalawang equation.

Muli naming isinusulat ang sistema ng mga equation sa anyo:

At gumawa tayo ng talahanayan ng katotohanan nang hiwalay para sa isang equation:

x 1	x2	(x 1 → x 2)

Gumawa tayo ng talahanayan ng katotohanan para sa dalawang equation:

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

Paksa ng aralin: Paglutas ng mga lohikal na equation

Pang-edukasyon - pag-aaral kung paano lutasin ang mga lohikal na equation, ang pagbuo ng mga kasanayan at kakayahan para sa paglutas ng mga lohikal na equation at pagbuo ng isang lohikal na pagpapahayag ayon sa talahanayan ng katotohanan;

Pang-edukasyon - lumikha ng mga kondisyon para sa pagbuo ng nagbibigay-malay na interes ng mga mag-aaral, itaguyod ang pag-unlad ng memorya, atensyon, lohikal na pag-iisip;

Pang-edukasyon : mag-ambag sa edukasyon ng kakayahang makinig sa mga opinyon ng iba, edukasyon ng kalooban at tiyaga upang makamit ang mga huling resulta.

Uri ng aralin: pinagsamang aralin

Kagamitan: kompyuter, multimedia projector, presentasyon 6.

Sa panahon ng mga klase

Pag-uulit at pag-update ng mga pangunahing kaalaman. Pagsusuri ng takdang-aralin (10 minuto)

Sa mga nakaraang aralin, nakilala namin ang mga pangunahing batas ng algebra ng lohika, natutunan kung paano gamitin ang mga batas na ito upang gawing simple ang mga lohikal na expression.

Suriin natin ang araling-bahay sa pagpapasimple ng mga lohikal na expression:

1. Alin sa mga sumusunod na salita ang nakakatugon sa lohikal na kondisyon:

(unang katinig → pangalawang katinig)٨ (huling titik patinig → penultimate titik patinig)? Kung mayroong ilang mga ganoong salita, ipahiwatig ang pinakamaliit sa kanila.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Ipakilala natin ang notasyon:

Ang A ay ang unang titik ng isang katinig

Ang B ay ang pangalawang titik ng isang katinig

S ang huling patinig

D - penultimate na patinig

Gumawa tayo ng isang expression:

Gumawa tayo ng talahanayan:

2. Ipahiwatig kung aling lohikal na expression ang katumbas ng expression

Pasimplehin natin ang pagsulat ng orihinal na expression at ang mga iminungkahing opsyon:

3. Ang isang fragment ng talahanayan ng katotohanan ng expression F ay ibinigay:

Anong expression ang tumutugma sa F?

Tukuyin natin ang mga halaga ng mga expression na ito para sa tinukoy na mga halaga ng mga argumento:

Pagkilala sa paksa ng aralin, paglalahad ng bagong materyal (30 minuto)

Patuloy nating pinag-aaralan ang mga pangunahing kaalaman sa lohika at ang paksa ng ating aralin ngayon na "Paglutas ng mga lohikal na equation." Pagkatapos pag-aralan ang paksang ito, matututunan mo ang mga pangunahing paraan upang malutas ang mga lohikal na equation, makakuha ng mga kasanayan upang malutas ang mga equation na ito sa pamamagitan ng paggamit ng wika ng logic algebra at ang kakayahang bumuo ng lohikal na pagpapahayag sa talahanayan ng katotohanan.

1. Lutasin ang lohikal na equation

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

Isulat ang iyong sagot bilang isang string ng apat na character: ang mga halaga ng mga variable na K, L, M, at N (sa ganoong pagkakasunud-sunod). Kaya, halimbawa, ang linya 1101 ay tumutugma sa K=1, L=1, M=0, N=1.

Desisyon:

Ibahin natin ang ekspresyon(¬K  M) → (¬L  M  N)

Mali ang expression kapag mali ang parehong termino. Ang pangalawang termino ay katumbas ng 0 kung M=0, N=0, L=1. Sa unang termino, K = 0, dahil M = 0, at
.

Sagot: 0100

2. Ilang solusyon mayroon ang equation (isaad lamang ang numero sa iyong sagot)?

Solusyon: baguhin ang expression

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

A+B=1 at C+D=1

Paraan 2: pag-compile ng talahanayan ng katotohanan

3 paraan: pagtatayo ng SDNF - isang perpektong disjunctive na normal na anyo para sa isang function - isang disjunction ng kumpletong regular na elementary conjunctions.

Ibahin natin ang orihinal na expression, buksan ang mga bracket upang makuha ang disjunction ng mga conjunction:

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

Dagdagan natin ang mga pang-ugnay upang makumpleto ang mga pang-ugnay (ang produkto ng lahat ng mga argumento), buksan ang mga bracket:

Isaalang-alang ang parehong mga pang-ugnay:

Bilang resulta, nakakakuha kami ng SDNF na naglalaman ng 9 na mga conjunction. Samakatuwid, ang talahanayan ng katotohanan para sa function na ito ay may halaga na 1 sa 9 na hanay sa 2 4 =16 na hanay ng mga variable na halaga.

3. Ilang solusyon mayroon ang equation (isaad lamang ang numero sa iyong sagot)?

Pasimplehin natin ang expression:

,

3 paraan: pagtatayo ng SDNF

Isaalang-alang ang parehong mga pang-ugnay:

Bilang resulta, nakakakuha kami ng SDNF na naglalaman ng 5 mga conjunction. Samakatuwid, ang talahanayan ng katotohanan para sa function na ito ay may value na 1 sa 5 row ng 2 4 =16 set ng variable value.

Pagbuo ng lohikal na pagpapahayag ayon sa talahanayan ng katotohanan:

para sa bawat hilera ng talahanayan ng katotohanan na naglalaman ng 1, binubuo namin ang produkto ng mga argumento, at ang mga variable na katumbas ng 0 ay kasama sa produktong may negation, at ang mga variable na katumbas ng 1 ay hindi tinatanggihan. Ang gustong ekspresyong F ay bubuuin ng kabuuan ng mga produktong nakuha. Pagkatapos, kung maaari, ang expression na ito ay dapat na pasimplehin.

Halimbawa: ang talahanayan ng katotohanan ng isang expression ay ibinigay. Bumuo ng lohikal na pagpapahayag.

Desisyon:

3. Takdang-Aralin (5 minuto)

Lutasin ang equation:

Gaano karaming mga solusyon ang mayroon ang equation (sagutin lamang ang numero)?

Ayon sa ibinigay na talahanayan ng katotohanan, gumawa ng lohikal na pagpapahayag at

pasimplehin ito.

Mga paraan upang malutas ang mga sistema ng mga lohikal na equation

Kirgizova E.V., Nemkova A.E.

Lesosibirsk Pedagogical Institute -

sangay ng Siberian Federal University, Russia

Ang kakayahang mag-isip nang tuluy-tuloy, makipagtalo nang konklusibo, bumuo ng mga hypotheses, pabulaanan ang mga negatibong konklusyon, ay hindi nagmumula mismo, ang kasanayang ito ay binuo ng agham ng lohika. Ang lohika ay isang agham na nag-aaral ng mga pamamaraan ng pagtatatag ng katotohanan o kamalian ng ilang mga pahayag batay sa katotohanan o kamalian ng ibang mga pahayag.

Ang pag-master ng mga pangunahing kaalaman ng agham na ito ay imposible nang walang paglutas ng mga lohikal na problema. Ang pagsuri sa pagbuo ng mga kasanayan upang mailapat ang kanilang kaalaman sa isang bagong sitwasyon ay isinasagawa sa pamamagitan ng pagpasa. Sa partikular, ito ay ang kakayahang malutas ang mga lohikal na problema. Ang mga Gawain B15 sa pagsusulit ay mga gawain na mas kumplikado, dahil naglalaman ang mga ito ng mga sistema ng mga lohikal na equation. Mayroong iba't ibang mga paraan upang malutas ang mga sistema ng mga lohikal na equation. Ito ay pagbabawas sa isang equation, pagbuo ng isang talahanayan ng katotohanan, agnas, sequential solution ng mga equation, atbp.

Gawain:Lutasin ang isang sistema ng mga lohikal na equation:

Isipin mo paraan ng pagbabawas sa isang equation . Ang pamamaraang ito ay nagsasangkot ng pagbabago ng mga lohikal na equation, upang ang kanilang kanang bahagi ay katumbas ng halaga ng katotohanan (iyon ay, 1). Upang gawin ito, gamitin ang pagpapatakbo ng lohikal na negation. Pagkatapos, kung may mga kumplikadong lohikal na operasyon sa mga equation, pinapalitan namin ang mga ito ng mga pangunahing: "AT", "O", "HINDI". Ang susunod na hakbang ay upang pagsamahin ang mga equation sa isa, katumbas ng sistema, gamit ang lohikal na operasyon na "AT". Pagkatapos nito, dapat kang gumawa ng mga pagbabago sa resultang equation batay sa mga batas ng algebra ng lohika at kumuha ng isang tiyak na solusyon sa system.

Solusyon 1:Ilapat ang inversion sa magkabilang panig ng unang equation:

Katawanin natin ang implikasyon sa pamamagitan ng mga pangunahing operasyong "OR", "NOT":

Dahil ang mga kaliwang bahagi ng mga equation ay katumbas ng 1, maaari mong pagsamahin ang mga ito gamit ang "AT" na operasyon sa isang equation na katumbas ng orihinal na sistema:

Binuksan namin ang unang bracket ayon sa batas ni de Morgan at binago namin ang resulta:

Ang resultang equation ay may isang solusyon: A= 0 , B=0 at C=1 .

Ang susunod na paraan ay pagbuo ng mga talahanayan ng katotohanan . Dahil ang mga lohikal na halaga ay may dalawang halaga lamang, maaari mo lamang na dumaan sa lahat ng mga pagpipilian at hanapin sa kanila ang mga kung saan ang ibinigay na sistema ng mga equation ay nasiyahan. Iyon ay, bumuo kami ng isang karaniwang talahanayan ng katotohanan para sa lahat ng mga equation ng system at makahanap ng isang linya na may mga nais na halaga.

Solusyon 2:Gumawa tayo ng talahanayan ng katotohanan para sa system:

0	0	1	1	0	1

Bold ang linya kung saan natutugunan ang mga kondisyon ng problema. Kaya A =0 , B =0 at C =1 .

Paraan pagkabulok . Ang ideya ay upang ayusin ang halaga ng isa sa mga variable (ilagay ito katumbas ng 0 o 1) at sa gayon ay gawing simple ang mga equation. Pagkatapos ay maaari mong ayusin ang halaga ng pangalawang variable, at iba pa.

Solusyon 3: Hayaan A = 0, pagkatapos ay:

Mula sa unang equation na nakuha namin B =0, at mula sa pangalawa - С=1. Solusyon ng system: A = 0 , B = 0 at C = 1 .

Maaari mo ring gamitin ang pamamaraan sunud-sunod na solusyon ng mga equation , pagdaragdag ng isang variable sa set na isinasaalang-alang sa bawat hakbang. Upang gawin ito, kinakailangan na ibahin ang anyo ng mga equation sa paraan na ang mga variable ay ipinasok sa alpabetikong pagkakasunud-sunod. Susunod, bumuo kami ng isang puno ng desisyon, sunud-sunod na pagdaragdag ng mga variable dito.

Ang unang equation ng system ay nakasalalay lamang sa A at B, at ang pangalawang equation sa A at C. Ang variable A ay maaaring tumagal ng 2 halaga 0 at 1:

Ito ay sumusunod mula sa unang equation na , kaya kapag A = 0 nakukuha natin ang B = 0 , at para sa A = 1 mayroon tayong B = 1 . Kaya, ang unang equation ay may dalawang solusyon na may paggalang sa mga variable A at B.

Gumuhit kami ng pangalawang equation, kung saan tinutukoy namin ang mga halaga ng C para sa bawat pagpipilian. Para sa A =1, ang implikasyon ay hindi maaaring mali, iyon ay, ang pangalawang sangay ng puno ay walang solusyon. Sa A= 0 makukuha natin ang tanging solusyon C= 1 :

Kaya, nakuha namin ang solusyon ng system: A = 0 , B = 0 at C = 1 .

Sa USE sa computer science, madalas na kinakailangan upang matukoy ang bilang ng mga solusyon sa isang sistema ng mga lohikal na equation, nang hindi nahahanap ang mga solusyon sa kanilang sarili, mayroon ding ilang mga pamamaraan para dito. Ang pangunahing paraan upang mahanap ang bilang ng mga solusyon sa isang sistema ng mga lohikal na equation ay pagbabago ng mga variable. Una, kinakailangan na gawing simple ang bawat isa sa mga equation hangga't maaari batay sa mga batas ng algebra ng lohika, at pagkatapos ay palitan ang mga kumplikadong bahagi ng mga equation ng mga bagong variable at matukoy ang bilang ng mga solusyon sa bagong sistema. Pagkatapos ay bumalik sa kapalit at tukuyin ang bilang ng mga solusyon para dito.

Gawain:Gaano karaming mga solusyon ang ginagawa ng equation ( A → B ) + (C → D ) = 1? Kung saan ang A, B, C, D ay mga boolean variable.

Desisyon:Ipakilala natin ang mga bagong variable: X = A → B at Y = C → D . Isinasaalang-alang ang mga bagong variable, ang equation ay maaaring isulat bilang: X + Y = 1.

Ang disjunction ay totoo sa tatlong kaso: (0;1), (1;0) at (1;1), habang X at Y ay isang implikasyon, ibig sabihin, ito ay totoo sa tatlong kaso at mali sa isa. Samakatuwid, ang kaso (0;1) ay tumutugma sa tatlong posibleng kumbinasyon ng mga parameter. Case (1;1) - ay tumutugma sa siyam na posibleng kumbinasyon ng mga parameter ng orihinal na equation. Samakatuwid, mayroong 3+9=15 posibleng solusyon ng equation na ito.

Ang sumusunod na paraan upang matukoy ang bilang ng mga solusyon sa isang sistema ng mga lohikal na equation ay − binary tree. Isaalang-alang natin ang pamamaraang ito sa isang halimbawa.

Gawain:Ilang magkakaibang solusyon mayroon ang sistema ng mga lohikal na equation:

Ang ibinigay na sistema ng mga equation ay katumbas ng equation:

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

Magpanggap na tayox 1 ay totoo, pagkatapos ay mula sa unang equation makuha namin iyonx 2 totoo rin, mula sa pangalawa -x 3 =1, at iba pa hanggang x m= 1. Kaya ang set (1; 1; …; 1) mula sa m Ang mga yunit ay ang solusyon ng system. Hayaan mo nax 1 =0, pagkatapos ay mula sa unang equation na mayroon kamix 2 =0 o x 2 =1.

Kailan x 2 totoo, nakuha namin na ang iba pang mga variable ay totoo rin, iyon ay, ang set (0; 1; ...; 1) ay ang solusyon ng system. Sax 2 =0 makuha natin iyan x 3 =0 o x 3 =, at iba pa. Sa pagpapatuloy sa huling variable, nakita namin na ang mga solusyon sa equation ay ang mga sumusunod na hanay ng mga variable ( m +1 na solusyon, sa bawat solusyon m variable na halaga):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ang diskarte na ito ay mahusay na inilarawan sa pamamagitan ng pagbuo ng isang binary tree. Ang bilang ng mga posibleng solusyon ay ang bilang ng iba't ibang sanga ng itinayong puno. Ito ay madaling makita na ito ay m+1.

Mga variable	Kahoy	Bilang ng mga desisyon
x 1
x2
x 3

Sa kaso ng mga kahirapan sa pangangatwiran at pagbuo ng isang puno ng desisyon, maaari kang maghanap ng solusyon gamit mga talahanayan ng katotohanan, para sa isa o dalawang equation.

Muli naming isinusulat ang sistema ng mga equation sa anyo:

At gumawa tayo ng talahanayan ng katotohanan nang hiwalay para sa isang equation:

x 1	x2	(x 1 → x 2)

Gumawa tayo ng talahanayan ng katotohanan para sa dalawang equation:

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

Susunod, makikita mo na ang isang equation ay totoo sa sumusunod na tatlong kaso: (0; 0), (0; 1), (1; 1). Ang sistema ng dalawang equation ay totoo sa apat na kaso (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Sa kasong ito, agad na malinaw na mayroong isang solusyon na binubuo lamang ng mga zero at higit pa m mga solusyon kung saan idinagdag ang isang yunit, simula sa huling posisyon hanggang sa mapunan ang lahat ng posibleng lugar. Maaaring ipagpalagay na ang pangkalahatang solusyon ay magkakaroon ng parehong anyo, ngunit para sa gayong paraan upang maging solusyon, kinakailangan ang patunay na totoo ang palagay.

Sa kabuuan ng lahat ng nasa itaas, nais kong bigyang pansin ang katotohanan na hindi lahat ng isinasaalang-alang na mga pamamaraan ay pangkalahatan. Kapag nilulutas ang bawat sistema ng mga lohikal na equation, ang mga tampok nito ay dapat isaalang-alang, batay sa kung saan dapat piliin ang paraan ng solusyon.

Panitikan:

1. Mga lohikal na gawain / O.B. Bogomolov - 2nd ed. – M.: BINOM. Knowledge Laboratory, 2006. - 271 p.: ill.

2. Polyakov K.Yu. Mga sistema ng lohikal na equation / Pang-edukasyon at pamamaraang pahayagan para sa mga guro ng computer science: Informatics No. 14, 2011

Mga pamamaraan para sa paglutas ng mga sistema ng mga lohikal na equation

Maaari mong lutasin ang isang sistema ng mga lohikal na equation, halimbawa, gamit ang isang talahanayan ng katotohanan (kung ang bilang ng mga variable ay hindi masyadong malaki) o paggamit ng isang puno ng desisyon, pagkatapos na gawing simple ang bawat equation.

1. Paraan ng pagbabago ng mga variable.

Ang pagpapakilala ng mga bagong variable ay ginagawang posible na gawing simple ang sistema ng mga equation sa pamamagitan ng pagbabawas ng bilang ng mga hindi alam.Ang mga bagong variable ay dapat na independyente sa bawat isa. Matapos malutas ang pinasimple na sistema, kinakailangang bumalik muli sa orihinal na mga variable.

Isaalang-alang ang aplikasyon ng paraang ito sa isang partikular na halimbawa.

Halimbawa.

((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

Desisyon:

Ipakilala natin ang mga bagong variable: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Atensyon! Ang bawat isa sa kanilang mga variable na x1, x2, ..., x10 ay dapat isama lamang sa isa sa mga bagong variable na A, B, C, D, E, ibig sabihin, ang mga bagong variable ay independyente sa bawat isa).

Pagkatapos ang sistema ng mga equation ay magiging ganito:

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

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

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

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

Bumuo tayo ng isang puno ng desisyon ng nagresultang sistema:

Isaalang-alang ang equation A=0, i.e. (X1≡ X2)=0. Ito ay may 2 ugat:

		X1 ≡ X2

Mula sa parehong talahanayan makikita na ang equation A \u003d 1 ay mayroon ding 2 mga ugat. Ayusin natin ang bilang ng mga ugat sa decision tree:

Upang mahanap ang bilang ng mga solusyon para sa isang sangay, kailangan mong i-multiply ang bilang ng mga solusyon sa bawat antas. Ang kaliwang sangay ay may 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 solusyon; ang tamang sangay ay mayroon ding 32 solusyon. Yung. ang buong sistema ay may 32+32=64 na solusyon.

Sagot: 64.

2. Paraan ng pangangatwiran.

Ang pagiging kumplikado ng paglutas ng mga sistema ng mga lohikal na equation ay nakasalalay sa bulkiness ng kumpletong puno ng desisyon. Ang paraan ng pangangatwiran ay nagpapahintulot sa iyo na huwag itayo ang buong puno, ngunit sa parehong oras ay maunawaan kung gaano karaming mga sanga ang magkakaroon nito. Isaalang-alang natin ang pamamaraang ito sa mga partikular na halimbawa.

Halimbawa 1 Ilang iba't ibang hanay ng mga halaga ng boolean variable x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ang mayroon na nakakatugon sa lahat ng sumusunod na kundisyon?

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

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

x1\/y1 =1

Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga halaga ng mga variable na x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 kung saan nasiyahan ang ibinigay na sistema ng pagkakapantay-pantay. Bilang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Desisyon :

Ang una at pangalawang equation ay naglalaman ng mga independiyenteng variable na nauugnay sa ikatlong kondisyon. Bumuo tayo ng decision tree para sa una at pangalawang equation.

Upang kumatawan sa puno ng desisyon ng system mula sa una at pangalawang equation, kinakailangang ipagpatuloy ang bawat sangay ng unang puno na may puno para sa mga variable. sa . Ang punong itinayo sa ganitong paraan ay maglalaman ng 36 na sanga. Ang ilan sa mga sangay na ito ay hindi nakakatugon sa ikatlong equation ng system. Tandaan sa unang puno ang bilang ng mga sanga ng puno"sa" , na nakakatugon sa ikatlong equation:

Linawin natin: para sa katuparan ng ikatlong kondisyon sa x1=0 dapat mayroong y1=1, ibig sabihin, lahat ng sanga ng puno"X" , kung saan ang x1=0 ay maaaring ipagpatuloy na may isang sangay lamang mula sa puno"sa" . At para lamang sa isang sanga ng puno"X" (kanan) magkasya sa lahat ng sanga ng puno"sa". Kaya, ang kumpletong puno ng buong sistema ay naglalaman ng 11 sanga. Ang bawat sangay ay kumakatawan sa isang solusyon sa orihinal na sistema ng mga equation. Kaya ang buong sistema ay may 11 solusyon.

Sagot: 11.

Halimbawa 2 Ilang iba't ibang solusyon mayroon ang sistema ng mga equation

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

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

………………

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

(X1 ≡ X10) = 0

kung saan ang x1, x2, …, x10 ay boolean variable? Hindi kailangang ilista ng sagot ang lahat ng iba't ibang hanay ng mga variable na halaga kung saan pinanghahawakan ang pagkakapantay-pantay na ito. Bilang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Desisyon : Pasimplehin natin ang sistema. Bumuo tayo ng talahanayan ng katotohanan ng bahagi ng unang equation:

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

Bigyang-pansin ang huling column, tumutugma ito sa resulta ng aksyon X1 ≡ X10.

X1 ≡ X10

Pagkatapos ng pagpapasimple, nakukuha namin:

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

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

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

……

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

(X1 ≡ X10) = 0

Isaalang-alang ang huling equation:(X1 ≡ X10) = 0 , ibig sabihin. Ang x1 ay hindi dapat kapareho ng x10. Upang ang unang equation ay maging katumbas ng 1, ang pagkakapantay-pantay ay dapat manatili(X1 ≡ X2)=1, ibig sabihin. Dapat tumugma ang x1 sa x2.

Bumuo tayo ng decision tree para sa unang equation:

Isaalang-alang ang pangalawang equation: para sa x10=1 at para sa x2=0 ang bracketdapat katumbas ng 1 (ibig sabihin, ang x2 ay kapareho ng x3); sa x10=0 at sa x2=1 bracket(X2 ≡ X10)=0 , kaya bracket (X2 ≡ X3) dapat katumbas ng 1 (ibig sabihin, ang x2 ay kapareho ng x3):

Sa pagtatalo sa ganitong paraan, bumuo kami ng decision tree para sa lahat ng equation:

Kaya, ang sistema ng mga equation ay may 2 solusyon lamang.

Sagot: 2.

Halimbawa 3

Ilang iba't ibang hanay ng mga halaga ng boolean variable x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 ang mayroon na nakakatugon sa lahat ng sumusunod na kundisyon?

(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

Desisyon:

Bumuo tayo ng decision tree ng 1st equation:

Isaalang-alang ang pangalawang equation:

• Kapag x1=0 : ang pangalawa at pangatlong bracket ay magiging 0; para ang unang bracket ay katumbas ng 1, dapat y1=1 , z1=1 (ibig sabihin, sa kasong ito - 1 solusyon)
• Sa x1=1 : ang unang panaklong ay magiging 0; pangalawa o ang ikatlong panaklong ay dapat na katumbas ng 1; ang pangalawang bracket ay magiging katumbas ng 1 kapag y1=0 at z1=1; ang ikatlong bracket ay magiging katumbas ng 1 para sa y1=1 at z1=0 (i.e. sa kasong ito - 2 solusyon).

Katulad din para sa natitirang mga equation. Tandaan ang bilang ng mga solusyon na nakuha para sa bawat node ng puno:

Upang malaman ang bilang ng mga solusyon para sa bawat sangay, i-multiply namin ang mga nakuhang numero nang hiwalay para sa bawat sangay (mula kaliwa hanggang kanan).

1 sangay: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solusyon

2 sangay: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 solusyon

3rd branch: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 na solusyon

4 na sangay: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 solusyon

5 sangay: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 na solusyon

Idagdag natin ang mga numerong nakuha: kabuuang 31 solusyon.

Sagot: 31.

3. Regular na pagtaas ng bilang ng mga ugat

Sa ilang mga sistema, ang bilang ng mga ugat ng susunod na equation ay nakasalalay sa bilang ng mga ugat ng nakaraang equation.

Halimbawa 1 Ilang iba't ibang hanay ng mga halaga ng boolean variable x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 ang naroroon na nakakatugon sa lahat ng sumusunod na kundisyon?

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

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

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

Pasimplehin unang equation:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Pagkatapos ang system ay kukuha ng form:

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

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

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

atbp.

Ang bawat sumusunod na equation ay may 2 higit pang mga ugat kaysa sa nauna.

4 na equation ay may 12 ugat;

Ang equation 5 ay may 14 na ugat

Ang 8 equation ay may 20 ugat.

Sagot: 20 ugat.

Minsan ang bilang ng mga ugat ay lumalaki ayon sa batas ng mga numero ng Fibonacci.

Ang paglutas ng isang sistema ng mga lohikal na equation ay nangangailangan ng isang malikhaing diskarte.