Metodat për zgjidhjen e sistemeve të ekuacioneve logjike. Metodat për zgjidhjen e sistemeve të ekuacioneve logjike

Noskin Andrey Nikolaevich,
IT-mësues
kategoria më e lartë e kualifikimit,
Kandidat i Shkencave Ushtarake, Profesor i Asociuar
Liceu GBOU Nr. 1575, Moskë

Metoda e optimizuar e hartës për zgjidhjen e problemit 23 nga Provimi i Unifikuar Shtetëror KIM në shkenca kompjuterike dhe TIK

Një nga detyrat më të vështira në Provimin e Bashkuar të Shtetit KIM është problemi 23, në të cilin duhet të gjeni numrin e grupeve të ndryshme të vlerave të variablave logjikë që plotësojnë kushtin e specifikuar.
Kjo detyrë është ndoshta detyra më e vështirë e Provimit të Unifikuar të Shtetit KIM në shkencat kompjuterike dhe TIK. Si rregull, jo më shumë se 5% e të ekzaminuarve e përballojnë atë (1).
Një përqindje kaq e vogël e studentëve që përfunduan këtë detyrë shpjegohet me sa vijon:
- nxënësit mund të ngatërrojnë (harrojnë) shenjat e veprimeve logjike;
- gabime matematikore në procesin e kryerjes së llogaritjeve;
- gabime në arsyetim gjatë kërkimit të zgjidhjes;
- gabime në procesin e thjeshtimit të shprehjeve logjike;
- mësuesit rekomandojnë zgjidhjen e këtij problemi pas përfundimit të të gjithë punës, pasi ka gjasa të
gabimet janë shumë të mëdha, dhe "pesha" e detyrës është vetëm një pikë kryesore.
Për më tepër, disa mësues kanë vështirësi në zgjidhjen e këtij lloj problemi dhe për këtë arsye përpiqen të zgjidhin probleme më të thjeshta me fëmijët.
Ajo që e ndërlikon gjithashtu situatën është se në këtë bllok ka një numër të madh detyrash të ndryshme dhe është e pamundur të zgjedhësh ndonjë zgjidhje shabllon.
Për të korrigjuar këtë situatë, komuniteti pedagogjik po finalizon dy metodat kryesore për zgjidhjen e problemeve të këtij lloji: zgjidhja me zinxhirë bit (2) dhe metoda e hartës (3).
Nevoja për të përmirësuar (optimizuar) këto metoda është për faktin se detyrat po ndryshojnë vazhdimisht si në strukturë ashtu edhe në numrin e variablave (vetëm një lloj i variablave X, dy lloje të variablave X dhe Y, tre lloje: X, Y , Z).
Vështirësia e zotërimit të këtyre metodave për zgjidhjen e problemeve konfirmohet nga fakti se në faqen e internetit të K.Yu. Polyakov, ka 38 analiza të këtij lloj problemi (4). Disa analiza ofrojnë më shumë se një lloj zgjidhjeje për një problem.
Kohët e fundit, në Provimin e Unifikuar të Shtetit KIM në shkenca kompjuterike, ka pasur probleme me dy lloje të variablave X dhe Y.
Unë kam optimizuar metodën e shfaqjes dhe inkurajoj studentët e mi të përdorin metodën e përmirësuar.
Kjo jep rezultate. Përqindja e nxënësve të mi që përballen me këtë detyrë varion deri në 43% të atyre që kalojnë. Si rregull, çdo vit nga 25 deri në 33 persona nga të gjitha klasat e 11-ta i nënshtrohen Provimit të Unifikuar të Shtetit në shkenca kompjuterike.
Para shfaqjes së problemave me dy lloje variablash, nxënësit përdornin me shumë sukses metodën e hartës, por pas shfaqjes së Y në shprehjen logjike, fillova të vërej se përgjigjet e fëmijëve nuk përkonin më me testet. Doli se ata nuk ishin mjaft të qartë se si të krijonin një tabelë të pasqyrave me një lloj të ri variabli. Më pas më lindi mendimi se për lehtësi, e gjithë shprehja duhet të reduktohet në një lloj ndryshoreje, siç është e përshtatshme për fëmijët.
Unë do ta jap këtë teknikë në më shumë detaje. Për lehtësi, do ta konsideroj duke përdorur shembullin e sistemit të shprehjeve logjike të dhënë në (4).
Sa zgjidhje të ndryshme ka një sistem ekuacionesh logjike?

(x 1 ^ y 1)=(¬x 2 V ¬ y 2 )
(x 2 ^ y 2)= (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5) = (¬ x 6 V ¬ y 6 )

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

5. Plotësoni tabelën duke llogaritur numrin e çifteve të variablave për të cilat sistemi ka zgjidhje.

6. Mblidhni të gjitha rezultatet: 9 + 9 + 9 + 27 = 54
7. Përgjigje: 54.
Metodologjia e optimizuar e mësipërme për zgjidhjen e problemit 23 nga Provimi i Unifikuar i Shtetit KIM i lejoi studentët të rifitonin besimin dhe të zgjidhnin me sukses këtë lloj problemi.

Literatura:

1. FIPI. Rekomandime metodologjike për mësuesit, të përgatitura mbi bazën e një analize të gabimeve tipike të pjesëmarrësve në Provimin e Unifikuar të Shtetit 2015 në SHKENCA E INFORMACIONIT dhe TIK. Mënyra e hyrjes: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

Ka mënyra të ndryshme për të zgjidhur sistemet e ekuacioneve logjike. Ky është reduktimi në një ekuacion, ndërtimi i një tabele të së vërtetës dhe zbërthimi.

Detyra: Zgjidh një sistem ekuacionesh logjike:

Le të shqyrtojmë metoda e reduktimit në një ekuacion . Kjo metodë përfshin transformimin e ekuacioneve logjike në mënyrë që anët e tyre të djathta të jenë të barabarta me vlerën e së vërtetës (d.m.th., 1). Për ta bërë këtë, përdorni operacionin e mohimit logjik. Pastaj, nëse ekuacionet përmbajnë operacione komplekse logjike, ne i zëvendësojmë ato me ato themelore: "DHE", "OSE", "JO". Hapi tjetër është kombinimi i ekuacioneve në një, ekuivalent me sistemin, duke përdorur operacionin logjik "AND". Pas kësaj, ju duhet të transformoni ekuacionin që rezulton bazuar në ligjet e algjebrës logjike dhe të merrni një zgjidhje specifike për sistemin.

Zgjidhja 1: Aplikoni përmbysjen në të dy anët e ekuacionit të parë:

Le të imagjinojmë implikimin përmes operacioneve bazë "OR" dhe "JO":

Meqenëse anët e majta të ekuacioneve janë të barabarta me 1, ne mund t'i kombinojmë ato duke përdorur operacionin "AND" në një ekuacion që është ekuivalent me sistemin origjinal:

Hapim kllapin e parë sipas ligjit të De Morgan dhe transformojmë rezultatin e marrë:

Ekuacioni që rezulton ka një zgjidhje: A =0, B=0 dhe C=1.

Metoda tjetër është ndërtimi i tabelave të së vërtetës . Meqenëse sasitë logjike kanë vetëm dy vlera, thjesht mund të kaloni nëpër të gjitha opsionet dhe të gjeni midis tyre ato për të cilat një sistem i caktuar ekuacionesh është i kënaqur. Kjo do të thotë, ne ndërtojmë një tabelë të përbashkët të së vërtetës për të gjitha ekuacionet e sistemit dhe gjejmë një vijë me vlerat e kërkuara.

Zgjidhja 2: Le të krijojmë një tabelë të së vërtetës për sistemin:

Vija për të cilën plotësohen kushtet e detyrës theksohet me shkronja të zeza. Pra A=0, B=0 dhe C=1.

Mënyra dekompozimi . Ideja është të rregulloni vlerën e njërës prej variablave (të vendosni atë të barabartë me 0 ose 1) dhe në këtë mënyrë të thjeshtoni ekuacionet. Pastaj mund të rregulloni vlerën e ndryshores së dytë, e kështu me radhë.

Zgjidhja 3: Le të jetë A = 0, atëherë:

Nga ekuacioni i parë marrim B = 0, dhe nga e dyta - C = 1. Zgjidhja e sistemit: A = 0, B = 0 dhe C = 1.

Në Provimin e Unifikuar të Shtetit në shkenca kompjuterike, është shumë shpesh e nevojshme të përcaktohet numri i zgjidhjeve të një sistemi ekuacionesh logjike, pa gjetur vetë zgjidhjet, ekzistojnë edhe metoda të caktuara për këtë. Mënyra kryesore për të gjetur numrin e zgjidhjeve të një sistemi ekuacionesh logjike ështëduke zëvendësuar variablat. Së pari, ju duhet të thjeshtoni secilën prej ekuacioneve sa më shumë që të jetë e mundur bazuar në ligjet e algjebrës logjike, dhe më pas të zëvendësoni pjesët komplekse të ekuacioneve me ndryshore të reja dhe të përcaktoni numrin e zgjidhjeve për sistemin e ri. Tjetra, kthehuni te zëvendësimi dhe përcaktoni numrin e zgjidhjeve për të.

Detyra: Sa zgjidhje ka ekuacioni (A →B) + (C →D) = 1? Ku A, B, C, D janë variabla logjike.

Zgjidhja: Le të prezantojmë variabla të reja: X = A →B dhe Y = C →D. Duke marrë parasysh variablat e rinj, ekuacioni do të shkruhet si: X + Y = 1.

Dijunksioni është i vërtetë në tre raste: (0;1), (1;0) dhe (1;1), ndërsa X dhe Y janë nënkuptime, domethënë është i vërtetë në tre raste dhe i gabuar në një. Prandaj, rasti (0;1) do të korrespondojë me tre kombinime të mundshme të parametrave. Rasti (1;1) - do të korrespondojë me nëntë kombinime të mundshme të parametrave të ekuacionit origjinal. Kjo do të thotë se zgjidhjet totale të mundshme të këtij ekuacioni janë 3+9=15.

Mënyra tjetër për të përcaktuar numrin e zgjidhjeve të një sistemi ekuacionesh logjike është pemë binare. Le ta shohim këtë metodë duke përdorur një shembull.

Detyra: Sa zgjidhje të ndryshme ka sistemi i ekuacioneve logjike:

Sistemi i dhënë i ekuacioneve është i barabartë me ekuacionin:

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

Le të pretendojmë se x 1 – është e vërtetë, atëherë nga ekuacioni i parë e marrim atë x 2 gjithashtu e vërtetë, nga e dyta - x 3 =1, dhe kështu me radhë derisa x m= 1. Kjo do të thotë se bashkësia (1; 1; …; 1) e m njësive është një zgjidhje për sistemin. Lëreni tani x 1 =0, atëherë nga ekuacioni i parë kemi x 2 =0 ose x 2 =1.

Kur x 2 e vërtetë, marrim se variablat e mbetur janë gjithashtu të vërteta, domethënë grupi (0; 1; ...; 1) është një zgjidhje për sistemin. Në x 2 =0 e marrim atë x 3 =0 ose x 3 =, dhe kështu me radhë. Duke vazhduar te ndryshorja e fundit, gjejmë se zgjidhjet e ekuacionit janë grupet e mëposhtme të variablave (zgjidhje m +1, secila zgjidhje përmban m vlerat e variablave):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Kjo qasje ilustrohet mirë duke ndërtuar një pemë binare. Numri i zgjidhjeve të mundshme është numri i degëve të ndryshme të pemës së ndërtuar. Është e lehtë të shihet se është e barabartë me m +1.

Në rast të vështirësive në arsyetim kërkimi dhe ndërtimie zgjidhjeve me të cilat mund të kërkoni një zgjidhje duke përdorur tabelat e së vërtetës, për një ose dy ekuacione.

Le të rishkruajmë sistemin e ekuacioneve në formën:

Dhe le të krijojmë një tabelë të së vërtetës veçmas për një ekuacion:

Le të krijojmë një tabelë të së vërtetës për dy ekuacione:

Si të zgjidhni disa probleme në seksionet A dhe B të provimit të shkencave kompjuterike

Mësimi #3. Logjikat. Funksionet logjike. Zgjidhja e ekuacioneve

Një numër i madh i problemeve të Provimit të Unifikuar të Shtetit i kushtohen logjikës propozicionale. Për të zgjidhur shumicën e tyre, mjafton të njihen ligjet bazë të logjikës propozicionale, njohja e tabelave të së vërtetës së funksioneve logjike të një dhe dy ndryshoreve. Do të jap ligjet bazë të logjikës propozicionale.

1. Komutativiteti i disjunksionit dhe lidhëzës:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Ligji shpërndarës në lidhje me ndarjen dhe lidhjen:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Mohimi i mohimit:
   ¬(¬a) ≡ a
4. Konsistenca:
   a ^ ¬а ≡ e rreme
5. E treta ekskluzive:
   a ˅ ¬а ≡ e vërtetë
6. Ligjet e De Morganit:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Thjeshtimi:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ e vërtetë ≡ a
   a ˄ e rreme ≡ e rreme
8. Absorbimi:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Zëvendësimi i nënkuptimit
   a → b ≡ ¬a ˅ b
10. Zëvendësimi i identitetit
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Paraqitja e funksioneve logjike

Çdo funksion logjik i n variablave - F(x 1, x 2, ... x n) mund të specifikohet nga një tabelë e së vërtetës. Një tabelë e tillë përmban 2n grupe variablash, për secilën prej të cilave specifikohet vlera e një funksioni në këtë grup. Kjo metodë është e mirë kur numri i variablave është relativisht i vogël. Tashmë për n > 5 përfaqësimi bëhet dobët i dukshëm.

Një mënyrë tjetër është përcaktimi i funksionit me një formulë duke përdorur funksione të njohura mjaft të thjeshta. Një sistem funksionesh (f 1, f 2, ... f k) quhet i plotë nëse ndonjë funksion logjik mund të shprehet me një formulë që përmban vetëm funksione f i.

Sistemi i funksioneve (¬, ˄, ˅) është i plotë. Ligjet 9 dhe 10 janë shembuj që tregojnë se si implikimi dhe identiteti shprehen përmes mohimit, lidhjes dhe ndarjes.

Në fakt, një sistem i dy funksioneve - mohimi dhe lidhja ose mohimi dhe disjunksioni - është gjithashtu i plotë. Nga ligjet e De Morganit vijojnë idetë që lejojnë njeriun të shprehë një lidhje përmes mohimit dhe ndarjes dhe, në përputhje me rrethanat, të shprehë një ndarje përmes mohimit dhe lidhjes:

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

Në mënyrë paradoksale, një sistem i përbërë nga vetëm një funksion është i plotë. Ekzistojnë dy funksione binare - antikonjuksioni dhe antidisjunksioni, të quajtur shigjeta e Peirce dhe goditja e Schaeffer, që përfaqësojnë një sistem të zbrazët.

Funksionet themelore të gjuhëve të programimit zakonisht përfshijnë identitetin, mohimin, lidhjen dhe ndarjen. Në problemet e Provimit të Unifikuar të Shtetit, së bashku me këto funksione, shpesh gjenden implikime.

Le të shohim disa probleme të thjeshta që përfshijnë funksione logjike.

Problemi 15:

Jepet një fragment i tabelës së së vërtetës. Cili nga tre funksionet e dhëna i korrespondon këtij fragmenti?

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

Funksioni numër 3.

Për të zgjidhur problemin, duhet të dini tabelat e së vërtetës së funksioneve bazë dhe të mbani mend përparësitë e operacioneve. Më lejoni t'ju kujtoj se lidhja (shumëzimi logjik) ka përparësi më të madhe dhe ekzekutohet më herët se disjunksioni (mbledhja logjike). Gjatë llogaritjeve, vërehet lehtë se funksionet me numrat 1 dhe 2 në grupin e tretë kanë vlerën 1 dhe për këtë arsye nuk korrespondojnë me fragmentin.

Problemi 16:

Cili nga numrat e dhënë plotëson kushtin:

(shifrat, duke filluar nga shifra më domethënëse, janë në rend zbritës) → (numër - çift) ˄ (shifër e ulët - çift) ˄ (shifër e lartë - tek)

Nëse ka disa numra të tillë, tregoni më të madhin.

1. 13579
2. 97531
3. 24678
4. 15386

Kushti plotësohet nga numri 4.

Dy numrat e parë nuk e plotësojnë kushtin për arsye se shifra më e ulët është tek. Lidhja e kushteve është e rreme nëse një nga termat e lidhjes është i rremë. Për numrin e tretë, kushti për shifrën më të lartë nuk plotësohet. Për numrin e katërt plotësohen kushtet e vendosura për shifrat e ulëta dhe të larta të numrit. Termi i parë i lidhëzës është gjithashtu i vërtetë, pasi nënkuptimi është i vërtetë nëse premisa e saj është e rreme, gjë që është edhe këtu.

Problemi 17: Dy dëshmitarë dhanë dëshminë e mëposhtme:

Dëshmitari i parë: Nëse A është fajtor, atëherë B është edhe më fajtor, dhe C është i pafajshëm.

Dëshmitari i dytë: Dy janë fajtorë. Dhe një nga të tjerët është padyshim fajtor dhe fajtor, por nuk mund të them se kush saktësisht.

Çfarë përfundimesh për fajësinë e A, B dhe C mund të nxirren nga dëshmia?

Përgjigje: Nga dëshmia del se A dhe B janë fajtorë, dhe C është i pafajshëm.

Zgjidhja: Natyrisht, përgjigja mund të jepet bazuar në sensin e përbashkët. Por le të shohim se si mund të bëhet kjo në mënyrë rigoroze dhe formale.

Gjëja e parë që duhet të bëni është të zyrtarizoni deklaratat. Le të prezantojmë tre variabla logjikë - A, B dhe C, secila prej të cilave ka vlerën e vërtetë (1) nëse i dyshuari përkatës është fajtor. Pastaj dëshmia e dëshmitarit të parë jepet me formulën:

A → (B ˄ ¬C)

Dëshmia e dëshmitarit të dytë jepet me formulën:

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

Dëshmia e të dy dëshmitarëve supozohet të jetë e vërtetë dhe përfaqëson lidhjen e formulave përkatëse.

Le të ndërtojmë një tabelë të së vërtetës për këto lexime:

Provat përmbledhëse janë të vërteta vetëm në një rast, duke çuar në një përgjigje të qartë - A dhe B janë fajtorë, dhe C është i pafajshëm.

Nga analiza e kësaj tabele del gjithashtu se dëshmia e dëshmitarit të dytë është më informuese. Nga e vërteta e dëshmisë së tij, pasojnë vetëm dy opsione të mundshme - A dhe B janë fajtorë, dhe C është i pafajshëm, ose A dhe C janë fajtorë, dhe B është i pafajshëm. Dëshmia e dëshmitarit të parë është më pak informative - ka 5 opsione të ndryshme që korrespondojnë me dëshminë e tij. Dëshmia e të dy dëshmitarëve së bashku jep një përgjigje të qartë për fajësinë e të dyshuarve.

Ekuacionet logjike dhe sistemet e ekuacioneve

Le të jetë F(x 1, x 2, …x n) një funksion logjik i n variablave. Ekuacioni logjik duket si ky:

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

Konstanta C ka vlerën 1 ose 0.

Një ekuacion logjik mund të ketë nga 0 deri në 2 n zgjidhje të ndryshme. Nëse C është e barabartë me 1, atëherë zgjidhjet janë të gjitha ato grupe variablash nga tabela e së vërtetës për të cilat funksioni F merr vlerën true (1). Grupet e mbetura janë zgjidhje të ekuacionit me C të barabartë me zero. Ju gjithmonë mund të merrni parasysh vetëm ekuacionet e formës:

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

Në të vërtetë, le të jepet ekuacioni:

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

Në këtë rast, mund të shkojmë në ekuacionin ekuivalent:

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

Konsideroni një sistem k ekuacionesh logjike:

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

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

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

Zgjidhja e një sistemi është një grup variablash në të cilat plotësohen të gjitha ekuacionet e sistemit. Për sa i përket funksioneve logjike, për të marrë një zgjidhje për një sistem ekuacionesh logjike, duhet gjetur një grup në të cilin funksioni logjik Ф është i vërtetë, duke përfaqësuar lidhjen e funksioneve origjinale F:

Ф = F 1 ˄ F 2 ˄ … F k

Nëse numri i variablave është i vogël, për shembull, më pak se 5, atëherë nuk është e vështirë të ndërtohet një tabelë e vërtetësisë për funksionin Ф, e cila na lejon të themi sa zgjidhje ka sistemi dhe cilat janë grupet që japin zgjidhje.

Në disa probleme të USE për gjetjen e zgjidhjeve për një sistem ekuacionesh logjike, numri i variablave arrin në 10. Më pas, ndërtimi i një tabele të vërtetësisë bëhet një detyrë pothuajse e pamundur. Zgjidhja e problemit kërkon një qasje të ndryshme. Për një sistem arbitrar ekuacionesh, nuk ka asnjë metodë të përgjithshme përveç numërimit që lejon zgjidhjen e problemeve të tilla.

Në problemet e propozuara në provim, zgjidhja zakonisht bazohet në marrjen parasysh të specifikave të sistemit të ekuacioneve. E përsëris, përveç testimit të të gjitha opsioneve për një grup variablash, nuk ka asnjë mënyrë të përgjithshme për të zgjidhur problemin. Zgjidhja duhet të ndërtohet në bazë të specifikave të sistemit. Shpesh është e dobishme të kryhet një thjeshtësim paraprak i një sistemi ekuacionesh duke përdorur ligjet e njohura të logjikës. Një teknikë tjetër e dobishme për zgjidhjen e këtij problemi është si më poshtë. Ne nuk jemi të interesuar për të gjitha grupet, por vetëm ato në të cilat funksioni Ф ka vlerën 1. Në vend që të ndërtojmë një tabelë të plotë të së vërtetës, ne do të ndërtojmë analogun e saj - një pemë binar vendimi. Çdo degë e kësaj peme i përgjigjet një zgjidhjeje dhe specifikon një bashkësi në të cilën funksioni Ф ka vlerën 1. Numri i degëve në pemën e vendimit përkon me numrin e zgjidhjeve të sistemit të ekuacioneve.

Unë do të shpjegoj se çfarë është një pemë e vendimeve binare dhe si është ndërtuar duke përdorur shembuj të disa problemeve.

Problemi 18

Sa grupe të ndryshme vlerash të ndryshoreve logjike x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë sistemin e dy ekuacioneve?

Përgjigje: Sistemi ka 36 zgjidhje të ndryshme.

Zgjidhje: Sistemi i ekuacioneve përfshin dy ekuacione. Le të gjejmë numrin e zgjidhjeve për ekuacionin e parë, në varësi të 5 ndryshoreve - x 1, x 2, ...x 5. Ekuacioni i parë mund të konsiderohet si një sistem prej 5 ekuacionesh. Siç u tregua, sistemi i ekuacioneve në fakt përfaqëson lidhjen e funksioneve logjike. E kundërta është gjithashtu e vërtetë: një lidhje kushtesh mund të konsiderohet si një sistem ekuacionesh.

Le të ndërtojmë një pemë vendimi për nënkuptimin (x1→ x2) - termi i parë i lidhëzës, i cili mund të konsiderohet si ekuacioni i parë. Kështu duket një paraqitje grafike e kësaj peme:

Pema përbëhet nga dy nivele sipas numrit të variablave në ekuacion. Niveli i parë përshkruan variablin e parë X 1 . Dy degë të këtij niveli pasqyrojnë vlerat e mundshme të kësaj variabli - 1 dhe 0. Në nivelin e dytë, degët e pemës pasqyrojnë vetëm ato vlera të mundshme të ndryshores X 2 për të cilat ekuacioni është i vërtetë. Meqenëse ekuacioni specifikon një implikim, një degë në të cilën X 1 ka vlerën 1 kërkon që në atë degë X 2 të ketë vlerën 1. Një degë në të cilën X 1 ka vlerën 0 prodhon dy degë me vlerat e X 2 e barabartë me 0 dhe 1 Pema e ndërtuar përcakton tre zgjidhje, mbi të cilat implikimi X 1 → X 2 merr vlerën 1. Në secilën degë, një grup përkatës vlerash të ndryshueshme shkruhet, duke i dhënë një zgjidhje ekuacionit.

Këto grupe janë: ((1, 1), (0, 1), (0, 0))

Le të vazhdojmë ndërtimin e pemës së vendimit duke shtuar ekuacionin e mëposhtëm, nënkuptimin e mëposhtëm X 2 → X 3 . Specifikimi i sistemit tonë të ekuacioneve është se çdo ekuacion i ri i sistemit përdor një ndryshore nga ekuacioni i mëparshëm, duke shtuar një ndryshore të re. Meqenëse ndryshorja X 2 tashmë ka vlera në pemë, atëherë në të gjitha degët ku ndryshorja X 2 ka vlerën 1, ndryshorja X 3 gjithashtu do të ketë vlerën 1. Për degë të tilla, ndërtimi i pemës vazhdon në nivelin tjetër, por degët e reja nuk shfaqen. Dega e vetme ku ndryshorja X 2 ka vlerën 0 do të degëzohet në dy degë ku ndryshorja X 3 do të marrë vlerat 0 dhe 1. Kështu, çdo shtim i një ekuacioni të ri, duke pasur parasysh specifikat e tij, shton një zgjidhje. Ekuacioni i parë origjinal:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
ka 6 zgjidhje. Ja se si duket pema e plotë e vendimit për këtë ekuacion:

Ekuacioni i dytë i sistemit tonë është i ngjashëm me të parën:

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

Dallimi i vetëm është se ekuacioni përdor variabla Y Ky ekuacion ka gjithashtu 6 zgjidhje. Meqenëse çdo zgjidhje për ndryshoret X i mund të kombinohet me secilën zgjidhje për variablat Y j , numri i përgjithshëm i zgjidhjeve është 36.

Ju lutemi vini re se pema e ndërtuar e vendimeve jep jo vetëm numrin e zgjidhjeve (sipas numrit të degëve), por edhe vetë zgjidhjet e shkruara në secilën degë të pemës.

Problemi 19

Sa grupe të ndryshme vlerash të ndryshoreve logjike x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë të gjitha kushtet e renditura më poshtë?

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

Kjo detyrë është një modifikim i detyrës së mëparshme. Dallimi është se shtohet një ekuacion tjetër që lidh variablat X dhe Y.

Nga ekuacioni X 1 → Y 1 del se kur X 1 ka vlerën 1 (ekziston një zgjidhje e tillë), atëherë Y 1 ka gjithashtu vlerën 1. Pra, ekziston një grup në të cilin X 1 dhe Y 1 kanë vlerat 1 Kur X 1 është e barabartë me 0, Y 1 mund të ketë çdo vlerë, si 0 ashtu edhe 1. Prandaj, çdo grup me X 1 të barabartë me 0, dhe ka 5 grupe të tilla, korrespondon me të 6 grupet me ndryshore Y. Prandaj, numri i përgjithshëm i zgjidhjeve është 31 .

Problemi 20

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

Zgjidhje: Duke kujtuar ekuivalencat bazë, e shkruajmë ekuacionin tonë si:

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

Zinxhiri ciklik i implikimeve do të thotë që variablat janë identikë, kështu që ekuacioni ynë është i barabartë me ekuacionin:

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

Ky ekuacion ka dy zgjidhje kur të gjitha X i janë ose 1 ose 0.

Problemi 21

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

Zgjidhja: Ashtu si në problemin 20, ne kalojmë nga implikimet ciklike në identitete, duke e rishkruar ekuacionin në formën:

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

Le të ndërtojmë një pemë vendimi për këtë ekuacion:

Problemi 22

Sa zgjidhje ka sistemi i mëposhtëm i ekuacioneve?

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

Përgjigje: 64

Zgjidhja: Le të kalojmë nga 10 ndryshore në 5 variabla duke prezantuar ndryshimin e mëposhtëm të variablave:

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);

Atëherë ekuacioni i parë do të marrë formën:

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

Ekuacioni mund të thjeshtohet duke e shkruar atë si:

(Y 1 ≡ Y 2) = 0

Duke kaluar në formën tradicionale, ne e shkruajmë sistemin pas thjeshtimeve në formën:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Pema e vendimit për këtë sistem është e thjeshtë dhe përbëhet nga dy degë me vlera të ndryshueshme të alternuara:

Duke u kthyer te variablat origjinale X, vini re se për secilën vlerë në ndryshoren Y ka 2 vlera në variablat X, kështu që çdo zgjidhje në variablat Y gjeneron 2 5 zgjidhje në ndryshoret X 5 zgjidhje, pra numri i përgjithshëm i zgjidhjeve është 64.

Siç mund ta shihni, çdo problem i zgjidhjes së një sistemi ekuacionesh kërkon qasjen e vet. Një teknikë e zakonshme është kryerja e transformimeve ekuivalente për të thjeshtuar ekuacionet. Një teknikë e zakonshme është ndërtimi i pemëve të vendimit. Qasja e përdorur të kujton pjesërisht ndërtimin e një tabele të së vërtetës me veçantinë se nuk janë ndërtuar të gjitha grupet e vlerave të mundshme të variablave, por vetëm ato mbi të cilat funksioni merr vlerën 1 (e vërtetë). Shpesh në problemet e propozuara nuk ka nevojë të ndërtohet një pemë e plotë vendimi, pasi tashmë në fazën fillestare është e mundur të përcaktohet modeli i shfaqjes së degëve të reja në çdo nivel pasues, siç u bë, për shembull, në problemin 18. .

Në përgjithësi, problemet që përfshijnë gjetjen e zgjidhjeve për një sistem ekuacionesh logjike janë ushtrime të mira matematikore.

Nëse problemi është i vështirë për t'u zgjidhur me dorë, atëherë mund t'ia besoni zgjidhjen kompjuterit duke shkruar një program të përshtatshëm për zgjidhjen e ekuacioneve dhe sistemeve të ekuacioneve.

Nuk është e vështirë të shkruash një program të tillë. Një program i tillë do të përballojë lehtësisht të gjitha detyrat e ofruara në Provimin e Unifikuar të Shtetit.

Mjaft e çuditshme, detyra për të gjetur zgjidhje për sistemet e ekuacioneve logjike është e vështirë për një kompjuter, dhe rezulton se një kompjuter ka kufijtë e tij. Kompjuteri mund të përballojë mjaft lehtë problemet ku numri i variablave është 20-30, por do të fillojë të mendojë për një kohë të gjatë për probleme me përmasa më të mëdha. Fakti është se funksioni 2 n, i cili specifikon numrin e grupeve, është një eksponencial që rritet me shpejtësi ndërsa n rritet. Aq i shpejtë sa një kompjuter personal i zakonshëm nuk mund të përballojë një detyrë që ka 40 variabla në ditë.

Program në gjuhën C# për zgjidhjen e ekuacioneve logjike

Shkrimi i një programi për zgjidhjen e ekuacioneve logjike është i dobishëm për shumë arsye, qoftë edhe vetëm sepse mund ta përdorni për të kontrolluar korrektësinë e zgjidhjes suaj për problemet e testit të Provimit të Unifikuar të Shtetit. Një arsye tjetër është se një program i tillë është një shembull i shkëlqyer i një detyre programimi që plotëson kërkesat për detyrat e kategorisë C në Provimin e Unifikuar të Shtetit.

Ideja e ndërtimit të një programi është e thjeshtë - bazohet në një kërkim të plotë të të gjitha grupeve të mundshme të vlerave të ndryshueshme. Meqenëse për një ekuacion të caktuar logjik ose sistem ekuacionesh dihet numri i variablave n, atëherë dihet edhe numri i grupeve - 2 n të cilat duhet të zgjidhen. Duke përdorur funksionet bazë të gjuhës C# - mohimi, disjunksioni, lidhja dhe identiteti, nuk është e vështirë të shkruhet një program që, për një grup të caktuar variablash, llogarit vlerën e funksionit logjik që korrespondon me një ekuacion logjik ose një sistem ekuacionesh. .

Në një program të tillë, ju duhet të ndërtoni një lak bazuar në numrin e grupeve, në trupin e ciklit, duke përdorur numrin e grupit, të formoni vetë grupin, të llogarisni vlerën e funksionit në këtë grup, dhe nëse kjo vlera është 1, atëherë grupi i jep zgjidhje ekuacionit.

Vështirësia e vetme që lind gjatë zbatimit të programit lidhet me detyrën e gjenerimit të vetë grupit të vlerave të variablave bazuar në numrin e caktuar. E bukura e këtij problemi është se kjo detyrë në dukje e vështirë në fakt zbret në një problem të thjeshtë që tashmë është shfaqur shumë herë. Në të vërtetë, mjafton të kuptojmë se grupi i vlerave të ndryshueshme që korrespondojnë me numrin i, i përbërë nga zero dhe njëshe, përfaqëson paraqitjen binar të numrit i. Pra, detyra komplekse për të marrë një grup vlerash të ndryshueshme sipas numrit të caktuar reduktohet në detyrën e njohur të konvertimit të një numri në binar.

Kështu duket një funksion në C# që zgjidh problemin tonë:

///

///

/// funksioni logjik - metoda,

/// nënshkrimi i të cilit është specifikuar nga delegati i DF

///

/// numri i variablave

/// numri i zgjidhjeve

Static int SolveEquations (DF fun, int n)

bool set = bool i ri[n];

int m = (int)Math.Pow(2, n); //numri i grupeve

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

//Kërkimi i plotë sipas numrit të grupeve

për (int i = 0; i< m; i++)

//Formimi i grupit - grupit të ardhshëm,

//specifikuar nga paraqitja binar e numrit i

për (int j = 0; j< n; j++)

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

//Llogaritni vlerën e funksionit në grup

Për të kuptuar programin, shpresoj se shpjegimet e idesë së programit dhe komentet në tekstin e tij janë të mjaftueshme. Do të fokusohem vetëm në shpjegimin e titullit të funksionit të dhënë. Funksioni SolveEquations ka dy parametra hyrës. Parametri fun specifikon një funksion logjik që korrespondon me ekuacionin ose sistemin e ekuacioneve që zgjidhen. Parametri n specifikon numrin e variablave argëtues. Si rezultat, funksioni SolveEquations kthen numrin e zgjidhjeve të funksionit logjik, domethënë numrin e atyre grupeve në të cilat funksioni vlerësohet në të vërtetë.

Është e zakonshme për nxënësit e shkollës kur një funksion F(x) ka një parametër hyrës x që është një variabël i tipit aritmetik, varg ose logjik. Në rastin tonë, përdoret një dizajn më i fuqishëm. Funksioni SolveEquations i referohet funksioneve të rendit më të lartë - funksione të tipit F(f), parametrat e të cilëve mund të jenë jo vetëm variabla të thjeshtë, por edhe funksione.

Klasa e funksioneve që mund të kalohet si parametër në funksionin SolveEquations është specifikuar si më poshtë:

delegoj bool DF(bool vars);

Kjo klasë zotëron të gjitha funksionet që kalojnë si parametër një grup vlerash të ndryshoreve logjike të specifikuara nga grupi vars. Rezultati është një vlerë Boolean që përfaqëson vlerën e funksionit në këtë grup.

Së fundi, këtu është një program që përdor funksionin SolveEquations për të zgjidhur disa sisteme ekuacionesh logjike. Funksioni SolveEquations është pjesë e klasës ProgramCommon më poshtë:

klasë Programi i përbashkët

delegoj bool DF(bool vars);

zbrazëti statike kryesore (argët e vargut)

Console.WriteLine("Dhe Funksionet - " +

ZgjidheEkuacione (FunDhe, 2));

Console.WriteLine("Funksioni ka 51 zgjidhje - " +

ZgjidheEkuacione (Fun51, 5));

Console.WriteLine("Funksioni ka 53 zgjidhje - " +

ZgjidheEquations (Fun53, 10));

bool statike FunAnd (bool vars)

kthim vars && vars;

static bool Fun51 (bool vars)

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

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

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

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

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

static bool Fun53 ​​(bool vars)

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

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

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

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

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

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

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

Ja se si duken rezultatet e zgjidhjes për këtë program:

10 detyra për punë të pavarur

1. Cili nga tre funksionet është ekuivalent:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Jepet një fragment i tabelës së së vërtetës:

Me cilin nga tre funksionet korrespondon ky fragment:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Juria përbëhet nga tre persona. Vendimi merret nëse për të voton kryetari i jurisë, i mbështetur nga të paktën një prej anëtarëve të jurisë. Në të kundërt nuk merret asnjë vendim. Ndërtoni një funksion logjik që zyrtarizon procesin e vendimmarrjes.
5. X fiton mbi Y nëse katër hedhje monedhash rezultojnë në koka tri herë. Përcaktoni një funksion logjik që përshkruan fitimin e X.
6. Fjalët në një fjali numërohen duke filluar nga një. Një fjali konsiderohet e ndërtuar saktë nëse plotësohen rregullat e mëposhtme:
   1. Nëse një fjalë me numër çift përfundon me një zanore, atëherë fjala tjetër, nëse ekziston, duhet të fillojë me një zanore.
   2. Nëse një fjalë me numër tek përfundon me një bashkëtingëllore, atëherë fjala tjetër, nëse ekziston, duhet të fillojë me një bashkëtingëllore dhe të përfundojë me një zanore.
      Cilat nga fjalitë e mëposhtme janë ndërtuar saktë:
   3. Mami e lau Mashën me sapun.
   4. Një lider është gjithmonë një model.
   5. E vërteta është e mirë, por lumturia është më e mirë.
7. Sa zgjidhje ka ekuacioni:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Listoni të gjitha zgjidhjet e ekuacionit:
   (a → b) → c = 0
9. Sa zgjidhje ka sistemi i mëposhtëm i ekuacioneve:
   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
10. Sa zgjidhje ka ekuacioni:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Përgjigjet për problemet:

1. Funksionet b dhe c janë ekuivalente.
2. Fragmenti i përgjigjet funksionit b.
3. Lëreni variablin logjik P të marrë vlerën 1 kur kryetari i jurisë voton “pro” vendimin. Variablat M 1 dhe M 2 përfaqësojnë opinionet e anëtarëve të jurisë. Funksioni logjik që specifikon marrjen e një vendimi pozitiv mund të shkruhet si më poshtë:
   P ˄ (M 1 ˅ M 2)
4. Lëreni variablin logjik P i të marrë vlerën 1 kur monedha i-të hidhet mbi koka. Funksioni logjik që specifikon fitimin X mund të shkruhet si më poshtë:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Fjalia b.
6. Ekuacioni ka 3 zgjidhje: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Institucion arsimor buxhetor komunal

"Shkolla e mesme nr. 18"

rrethi urban i qytetit të Salavat të Republikës së Bashkortostanit

Sistemet e ekuacioneve logjike

në Problemet e Provimit të Unifikuar të Shtetit në shkencat kompjuterike

Seksioni "Bazat e Algjebrës së Logjikës" në detyrat e Provimit të Unifikuar të Shtetit konsiderohet si një nga më të vështirat dhe më të vështirat për t'u zgjidhur. Përqindja mesatare e detyrave të kryera në këtë temë është më e ulëta dhe është 43.2.

Bazuar në specifikimin KIM 2018, ky bllok përfshin katër detyra të niveleve të ndryshme të vështirësisë.

Detyra 23 është e nivelit të lartë të vështirësisë, prandaj ka përqindjen më të ulët të përmbushjes. Ndër të diplomuarit e përgatitur (81-100 pikë) 49,8% e kanë kryer detyrën, të përgatitur mesatarisht (61-80 pikë) kanë përfunduar 13,7%, pjesa e mbetur e grupit të studentëve nuk e kanë kryer këtë detyrë.

Suksesi i zgjidhjes së një sistemi ekuacionesh logjike varet nga njohja e ligjeve të logjikës dhe nga zbatimi i saktë i metodave për zgjidhjen e sistemit.

Le të shqyrtojmë zgjidhjen e një sistemi ekuacionesh logjike duke përdorur metodën e hartës.

(23.154 Polyakov K.Yu.) Sa zgjidhje të ndryshme ka sistemi i ekuacioneve?

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

Ku x1 , x2 ,…, x8, në1 , y2 ,…,y8 - variabla logjike? Përgjigja nuk ka nevojë të listojë të gjitha grupet e ndryshme të vlerave të ndryshueshme për të cilat vlen kjo barazi. Si përgjigje, duhet të tregoni numrin e grupeve të tilla.

Zgjidhje. Të gjitha ekuacionet e përfshira në sistem janë të të njëjtit lloj, dhe secili ekuacion përfshin katër variabla. Duke ditur x1 dhe y1, ne mund të gjejmë të gjitha vlerat e mundshme të x2 dhe y2 që plotësojnë ekuacionin e parë. Duke arsyetuar në mënyrë të ngjashme, nga të njohurat x2 dhe y2 mund të gjejmë x3, y3 që plotëson ekuacionin e dytë. Kjo do të thotë, duke ditur çiftin (x1, y1) dhe duke përcaktuar vlerën e çiftit (x2, y2), do të gjejmë çiftin (x3, y3), i cili, nga ana tjetër, do të çojë në çiftin (x4, y4) e kështu me radhë.

Le të gjejmë të gjitha zgjidhjet e ekuacionit të parë. Kjo mund të bëhet në dy mënyra: të ndërtoni një tabelë të së vërtetës, përmes arsyetimit dhe zbatimit të ligjeve të logjikës.

Tabela e së vërtetës:

Ndërtimi i një tabele të së vërtetës është punë intensive dhe joefikase në kohë, kështu që ne përdorim metodën e dytë - arsyetimin logjik. Produkti është i barabartë me 1 nëse dhe vetëm nëse secili faktor është i barabartë me 1.

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

(x1  x2 ) =1

(y1  y2 ) =1

Le të shohim ekuacionin e parë. Pasoja është e barabartë me 1 kur 0 0, 0 1, 1 1, që do të thotë (x1 y1)=0 për (01), (10), pastaj çifti (x2  y2 ) mund të jetë çdo (00), (01), (10), (11), dhe kur (x1 y1) = 1, pra (00) dhe (11) çifti (x2 y2) = 1 merr të njëjtat vlera (00) dhe (11). Le të përjashtojmë nga kjo zgjidhje ato çifte për të cilat ekuacioni i dytë dhe i tretë janë false, pra x1=1, x2=0, y1=1, y2=0.

Numri total i çifteve 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Sa zgjidhje të ndryshme ka sistemi i ekuacioneve logjike?

(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

Zgjidhje. 1) Ekuacionet janë të të njëjtit lloj, kështu që duke përdorur arsyetimin do të gjejmë të gjitha çiftet e mundshme (x1,y1), (x2,y2) të ekuacionit të parë.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Zgjidhja e ekuacionit të dytë janë çiftet (00), (01), (11).

Le të gjejmë zgjidhje për ekuacionin e parë. Nëse x1=0, atëherë x2, y2 - çdo, nëse x1=1, atëherë x2, y2 merr vlerën (11).

Le të bëjmë lidhjet midis çifteve (x1, y1) dhe (x2, y2).

Le të krijojmë një tabelë për të llogaritur numrin e çifteve në çdo fazë.

Duke marrë parasysh zgjidhjet e ekuacionit të fundit x 7  y 7 = 1, le të përjashtojmë çiftin (10). Gjeni numrin e përgjithshëm të zgjidhjeve 1+7+0+34=42

3)(23.180) Sa zgjidhje të ndryshme ka një sistem ekuacionesh logjike?

(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

Zgjidhje. 1) Ekuacionet janë të të njëjtit lloj, kështu që duke përdorur arsyetimin do të gjejmë të gjitha çiftet e mundshme (x1,x2), (x3,x4) të ekuacionit të parë.

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

Le të përjashtojmë nga zgjidhja çiftet që në sekuencë japin 0 (1 0), këto janë çiftet (01, 00, 11) dhe (10).

Le të bëjmë lidhjet midis çifteve (x1,x2), (x3,x4)

Le të jetë një funksion logjik i n variablave. Ekuacioni logjik duket si ky:

Konstanta C ka vlerën 1 ose 0.

Një ekuacion logjik mund të ketë nga 0 në zgjidhje të ndryshme. Nëse C është e barabartë me 1, atëherë zgjidhjet janë të gjitha ato grupe variablash nga tabela e së vërtetës për të cilat funksioni F merr vlerën true (1). Grupet e mbetura janë zgjidhje të ekuacionit me C të barabartë me zero. Ju gjithmonë mund të merrni parasysh vetëm ekuacionet e formës:

Në të vërtetë, le të jepet ekuacioni:

Në këtë rast, mund të shkojmë në ekuacionin ekuivalent:

Konsideroni një sistem k ekuacionesh logjike:

Zgjidhja e një sistemi është një grup variablash në të cilat plotësohen të gjitha ekuacionet e sistemit. Për sa i përket funksioneve logjike, për të marrë një zgjidhje për një sistem ekuacionesh logjike, duhet gjetur një grup në të cilin funksioni logjik Ф është i vërtetë, duke përfaqësuar lidhjen e funksioneve origjinale:

Nëse numri i variablave është i vogël, për shembull, më pak se 5, atëherë nuk është e vështirë të ndërtohet një tabelë e vërtetësisë për funksionin, e cila na lejon të themi sa zgjidhje ka sistemi dhe cilat janë grupet që japin zgjidhje.

Në disa probleme të USE për gjetjen e zgjidhjeve për një sistem ekuacionesh logjike, numri i variablave arrin në 10. Më pas, ndërtimi i një tabele të vërtetësisë bëhet një detyrë pothuajse e pamundur. Zgjidhja e problemit kërkon një qasje të ndryshme. Për një sistem arbitrar ekuacionesh, nuk ka asnjë metodë të përgjithshme përveç numërimit që lejon zgjidhjen e problemeve të tilla.

Në problemet e propozuara në provim, zgjidhja zakonisht bazohet në marrjen parasysh të specifikave të sistemit të ekuacioneve. E përsëris, përveç testimit të të gjitha opsioneve për një grup variablash, nuk ka asnjë mënyrë të përgjithshme për të zgjidhur problemin. Zgjidhja duhet të ndërtohet në bazë të specifikave të sistemit. Shpesh është e dobishme të kryhet një thjeshtësim paraprak i një sistemi ekuacionesh duke përdorur ligjet e njohura të logjikës. Një teknikë tjetër e dobishme për zgjidhjen e këtij problemi është si më poshtë. Ne nuk jemi të interesuar për të gjitha grupet, por vetëm ato në të cilat funksioni ka vlerën 1. Në vend që të ndërtojmë një tabelë të plotë të së vërtetës, ne do të ndërtojmë analogun e saj - një pemë binar vendimi. Çdo degë e kësaj peme i përgjigjet një zgjidhjeje dhe specifikon një grup në të cilin funksioni ka vlerën 1. Numri i degëve në pemën e vendimit përkon me numrin e zgjidhjeve të sistemit të ekuacioneve.

Unë do të shpjegoj se çfarë është një pemë e vendimeve binare dhe si është ndërtuar duke përdorur shembuj të disa problemeve.

Problemi 18

Sa grupe të ndryshme vlerash të ndryshoreve logjike x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë sistemin e dy ekuacioneve?

Përgjigje: Sistemi ka 36 zgjidhje të ndryshme.

Zgjidhje: Sistemi i ekuacioneve përfshin dy ekuacione. Le të gjejmë numrin e zgjidhjeve për ekuacionin e parë, në varësi të 5 variablave - . Ekuacioni i parë mund të konsiderohet si një sistem prej 5 ekuacionesh. Siç u tregua, sistemi i ekuacioneve në fakt përfaqëson lidhjen e funksioneve logjike. Deklarata e kundërt është gjithashtu e vërtetë - një lidhje e kushteve mund të konsiderohet si një sistem ekuacionesh.

Le të ndërtojmë një pemë vendimi për nënkuptim () - termi i parë i lidhëzës, i cili mund të konsiderohet si ekuacioni i parë. Kështu duket një paraqitje grafike e kësaj peme

Pema përbëhet nga dy nivele sipas numrit të variablave në ekuacion. Niveli i parë përshkruan variablin e parë. Dy degë të këtij niveli pasqyrojnë vlerat e mundshme të kësaj variabli - 1 dhe 0. Në nivelin e dytë, degët e pemës pasqyrojnë vetëm ato vlera të mundshme të ndryshores për të cilat ekuacioni vlerëson të vërtetë. Meqenëse ekuacioni specifikon një implikim, një degë në të cilën ka vlerën 1 kërkon që në këtë degë të ketë vlerën 1. Një degë në të cilën ka vlerën 0 gjeneron dy degë me vlera të barabarta me 0 dhe 1. pema specifikon tre zgjidhje, nga të cilat implikimi merr vlerën 1. Në secilën degë, shkruhet një grup përkatës vlerash të ndryshueshme, duke i dhënë një zgjidhje ekuacionit.

Këto grupe janë: ((1, 1), (0, 1), (0, 0))

Le të vazhdojmë ndërtimin e pemës së vendimit duke shtuar ekuacionin e mëposhtëm, nënkuptimin e mëposhtëm. Specifikimi i sistemit tonë të ekuacioneve është se çdo ekuacion i ri i sistemit përdor një ndryshore nga ekuacioni i mëparshëm, duke shtuar një ndryshore të re. Meqenëse ndryshorja ka tashmë vlera në pemë, atëherë në të gjitha degët ku ndryshorja ka vlerën 1, ndryshorja do të ketë gjithashtu vlerën 1. Për degë të tilla, ndërtimi i pemës vazhdon në nivelin tjetër, por nuk shfaqen degë të reja. Një degë e vetme ku ndryshorja ka vlerën 0 do të degëzohet në dy degë ku ndryshorja do të marrë vlerat 0 dhe 1. Kështu, çdo shtim i një ekuacioni të ri, duke pasur parasysh specifikën e tij, shton një zgjidhje. Ekuacioni i parë origjinal:

ka 6 zgjidhje. Ja se si duket pema e plotë e vendimit për këtë ekuacion:

Ekuacioni i dytë i sistemit tonë është i ngjashëm me të parën:

Dallimi i vetëm është se ekuacioni përdor variabla Y Ky ekuacion ka gjithashtu 6 zgjidhje. Meqenëse çdo zgjidhje variabël mund të kombinohet me secilën zgjidhje të ndryshueshme, numri i përgjithshëm i zgjidhjeve është 36.

Ju lutemi vini re se pema e ndërtuar e vendimeve jep jo vetëm numrin e zgjidhjeve (sipas numrit të degëve), por edhe vetë zgjidhjet e shkruara në secilën degë të pemës.

Problemi 19

Sa grupe të ndryshme vlerash të ndryshoreve logjike x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë të gjitha kushtet e renditura më poshtë?

Kjo detyrë është një modifikim i detyrës së mëparshme. Dallimi është se shtohet një ekuacion tjetër që lidh variablat X dhe Y.

Nga ekuacioni del se kur ka vlerën 1 (ekziston një zgjidhje e tillë), atëherë ajo ka vlerën 1. Kështu, ekziston një grup në të cilin dhe ka vlera 1. Kur është e barabartë me 0, mund të të ketë ndonjë vlerë, si 0 ashtu edhe 1. Prandaj, çdo grup me , i barabartë me 0, dhe ka 5 grupe të tilla, i korrespondon të 6 grupeve me ndryshore Y. Prandaj, numri i përgjithshëm i zgjidhjeve është 31.

Problemi 20

Zgjidhje: Duke kujtuar ekuivalencat bazë, e shkruajmë ekuacionin tonë si:

Zinxhiri ciklik i implikimeve do të thotë që variablat janë identikë, kështu që ekuacioni ynë është i barabartë me ekuacionin:

Ky ekuacion ka dy zgjidhje kur të gjitha janë ose 1 ose 0.

Problemi 21

Sa zgjidhje ka ekuacioni:

Zgjidhja: Ashtu si në problemin 20, ne kalojmë nga implikimet ciklike në identitete, duke e rishkruar ekuacionin në formën:

Le të ndërtojmë një pemë vendimi për këtë ekuacion:

Problemi 22

Sa zgjidhje ka sistemi i mëposhtëm i ekuacioneve?