Loogisten yhtälöiden ratkaisu. Loogisten operaatioiden etusija

Olkoon n muuttujan looginen funktio. Looginen yhtälö on:

Vakiolla C on arvo 1 tai 0.

Loogisella yhtälöllä voi olla 0:sta eri ratkaisuihin. Jos C on 1, niin ratkaisut ovat kaikki ne totuustaulukon muuttujajoukot, joissa funktio F saa arvon tosi (1). Loput joukot ovat yhtälön ratkaisuja C:lle, joka on yhtä suuri kuin nolla. Voimme aina tarkastella vain yhtälöitä, joiden muoto on:

Todellakin, annetaan yhtälö:

Tässä tapauksessa voit siirtyä vastaavaan yhtälöön:

Tarkastellaan k loogisen yhtälön järjestelmää:

Järjestelmän ratkaisu on joukko muuttujia, joihin kaikki järjestelmän yhtälöt täyttyvät. Loogisten funktioiden osalta ratkaisun saamiseksi loogisten yhtälöiden järjestelmään tulisi löytää joukko, jossa looginen funktio Ф on tosi, edustaen alkuperäisten funktioiden konjunktiota:

Jos muuttujien määrä on pieni, esimerkiksi alle 5, niin funktiolle ei ole vaikeaa rakentaa totuustaulukkoa, jonka avulla voidaan sanoa kuinka monta ratkaisua järjestelmässä on ja mitkä ovat ratkaisuja antavat joukot.

Joissakin Unified State Examinationin tehtävissä ratkaisujen löytämiseksi loogiseen yhtälöjärjestelmään muuttujien määrä saavuttaa arvon 10. Silloin totuustaulukon rakentamisesta tulee lähes ratkaisematon tehtävä. Ongelman ratkaiseminen vaatii erilaista lähestymistapaa. Mielivaltaiselle yhtälöjärjestelmälle ei ole olemassa muuta yleistä tapaa kuin luettelointi, joka mahdollistaisi tällaisten ongelmien ratkaisemisen.

Tentissä ehdotetuissa tehtävissä ratkaisu perustuu yleensä yhtälöjärjestelmän erityispiirteiden huomioon ottamiseen. Toistan, että lukuun ottamatta muuttujien joukon kaikkien muunnelmien luetteloa, ongelman ratkaisemiseksi ei ole yleistä tapaa. Ratkaisu tulee rakentaa järjestelmän erityispiirteiden mukaan. Usein on hyödyllistä suorittaa yhtälöjärjestelmän alustava yksinkertaistaminen tunnettujen logiikan lakien avulla. Toinen hyödyllinen tekniikka tämän ongelman ratkaisemiseksi on seuraava. Emme ole kiinnostuneita kaikista joukoista, vaan vain niistä, joissa funktiolla on arvo 1. Sen sijaan, että rakentaisimme täydellisen totuustaulukon, rakennamme sen analogin - binaarisen päätöspuun. Jokainen tämän puun haara vastaa yhtä ratkaisua ja määrittää joukon, jossa funktiolla on arvo 1. Haarojen lukumäärä päätöspuussa on yhtä suuri kuin yhtälöjärjestelmän ratkaisujen lukumäärä.

Mikä on binäärinen päätöspuu ja miten se rakennetaan, selitän esimerkkien avulla useista tehtävistä.

Ongelma 18

Kuinka monta erilaista Boolen muuttujien x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 arvojoukkoa on olemassa, jotka täyttävät kahden yhtälön järjestelmän?

Vastaus: Järjestelmässä on 36 erilaista ratkaisua.

Ratkaisu: Yhtälöjärjestelmä sisältää kaksi yhtälöä. Etsitään ratkaisujen lukumäärä ensimmäiselle yhtälölle riippuen 5 muuttujasta - . Ensimmäistä yhtälöä voidaan puolestaan ​​pitää 5 yhtälöjärjestelmänä. Kuten on osoitettu, yhtälöjärjestelmä edustaa itse asiassa loogisten funktioiden konjunktiota. Myös käänteinen väite on totta - ehtojen konjunktiota voidaan pitää yhtälöjärjestelmänä.

Rakennetaan päätöspuu implikaatiolle () - konjunktion ensimmäiselle termille, jota voidaan pitää ensimmäisenä yhtälönä. Tältä tämän puun graafinen kuva näyttää

Puu koostuu kahdesta tasosta yhtälön muuttujien lukumäärän mukaan. Ensimmäinen taso kuvaa ensimmäistä muuttujaa. Tämän tason kaksi haaraa heijastavat tämän muuttujan mahdollisia arvoja - 1 ja 0. Toisella tasolla puun haarat heijastavat vain niitä muuttujan mahdollisia arvoja, joille yhtälö ottaa arvon tosi. Koska yhtälö määrittelee implikaation, haara, jossa sen arvo on 1, edellyttää, että sillä on arvo 1. Haara, jolla sen arvo on 0, luo kaksi haaraa, joiden arvot ovat yhtä suuret kuin 0 ja 1. Konstruoitu puu määrittelee kolme ratkaisua, missä implikaatio saa arvon 1. Jokaiselle haaralle kirjoitetaan vastaava muuttujien arvojoukko, joka antaa ratkaisun yhtälöön.

Nämä joukot ovat: ((1, 1), (0, 1), (0, 0))

Jatketaan päätöspuun rakentamista lisäämällä seuraava yhtälö, seuraava implikaatio. Yhtälöjärjestelmämme erityispiirre on, että jokainen uusi järjestelmän yhtälö käyttää yhtä muuttujaa edellisestä yhtälöstä ja lisää yhden uuden muuttujan. Koska muuttujalla on jo arvoja puussa, niin kaikilla oksilla, joissa muuttujan arvo on 1, muuttujan arvo on myös 1. Tällaisille oksille puun rakentaminen jatkuu seuraavalle tasolle, mutta uusia oksia ei näy. Ainoa haara, jossa muuttujan arvo on 0, antaa haaran kahteen haaraan, joissa muuttuja saa arvot 0 ja 1. Siten jokainen uuden yhtälön lisäys, sen spesifisyydestä huolimatta, lisää yhden ratkaisun. Alkuperäinen ensimmäinen yhtälö:

on 6 ratkaisua. Tämän yhtälön täydellinen päätöspuu näyttää tältä:

Järjestelmämme toinen yhtälö on samanlainen kuin ensimmäinen:

Ainoa ero on, että yhtälö käyttää muuttujia Y. Tässä yhtälössä on myös 6 ratkaisua. Koska jokainen muuttujaratkaisu voidaan yhdistää kuhunkin muuttujaratkaisuun, ratkaisujen kokonaismäärä on 36.

Huomaa, että rakennettu päätöspuu ei anna vain ratkaisujen lukumäärää (haarojen lukumäärän mukaan), vaan myös itse ratkaisut, jotka on kirjoitettu puun jokaiseen haaraan.

Ongelma 19

Kuinka monta erilaista loogisten muuttujien x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 arvojoukkoa on olemassa, jotka täyttävät kaikki seuraavat ehdot?

Tämä tehtävä on muunnos edellisestä tehtävästä. Erona on, että lisätään toinen yhtälö, joka yhdistää X- ja Y-muuttujat.

Yhtälöstä seuraa, että kun sen arvo on 1 (yksi tällainen ratkaisu on olemassa), sen arvo on 1. Siten on olemassa yksi joukko, jolla ja joilla on arvot 1. Kun se on yhtä suuri kuin 0, sillä voi olla mikä tahansa arvo, sekä 0 että 1. Siksi jokainen joukko, joka on yhtä suuri kuin 0, ja tällaisia ​​joukkoja on 5, vastaa kaikkia 6 joukkoa, joissa on muuttuja Y. Siksi ratkaisujen kokonaismäärä on 31.

Ongelma 20

Ratkaisu: Muistaen perusekvivalenssin, kirjoitamme yhtälömme seuraavasti:

Implikaatioiden syklinen ketju tarkoittaa, että muuttujat ovat identtisiä, joten yhtälömme on ekvivalentti:

Tällä yhtälöllä on kaksi ratkaisua, kun kaikki ovat joko 1 tai 0.

Ongelma 21

Kuinka monta ratkaisua yhtälöllä on:

Ratkaisu: Kuten tehtävässä 20, siirrymme syklisistä implikaatioista identiteettiin kirjoittamalla yhtälön uudelleen muotoon:

Rakennetaan päätöspuu tälle yhtälölle:

Ongelma 22

Kuinka monta ratkaisua seuraavalla yhtälöjärjestelmällä on?

Vuoden lopussa kävi ilmi, että vain yksi kolmesta oletuksesta piti paikkansa. Mitkä osastot tekivät voittoa vuoden lopussa?

Ratkaisu. Kirjoitetaan oletukset ongelman ehdosta loogisten lauseiden muodossa: ”Tuottojen saaminen osastolta B ei ole välttämätön edellytys

voitot yksiköllä A ":F 1 (A , B , C ) = A → B

”Vähintään yhdeltä B- ja C-osastolta ei riitä voiton saaminen osastolle A”: F 2 (A , B , C ) = (B + C ) → A

"Divisioonat A ja B eivät tuota voittoa samaan aikaan": F 3 (A , B , C ) = A B

Ehdosta tiedetään, että vain yksi kolmesta oletuksesta on totta. Tämä tarkoittaa, että meidän on löydettävä, mikä seuraavista kolmesta loogisesta lausekkeesta ei ole identtisesti epätosi:

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Näin ollen vuoden lopussa toinen oletus osoittautui oikeaksi ja ensimmäinen ja kolmas olivat vääriä.

Siksi divisioona C saa voittoa, mutta divisioonat A ja B eivät saa voittoa.

Loogisten yhtälöiden ratkaiseminen

Valtion keskitetyn testauksen teksteissä on tehtävä (A8), jossa ehdotetaan loogisen yhtälön juuren löytämistä. Katsotaanpa, kuinka tällaiset tehtävät ratkaistaan ​​esimerkin avulla.

Etsi loogisen yhtälön juuri: (A + B )(X AB ) = B + X → A .

Ensimmäinen ratkaisu on rakentaa totuustaulukko. Rakennataan yhtälön oikean ja vasemman puolen totuustaulukot ja katsotaan, mihin X , näiden taulukoiden viimeisten sarakkeiden arvot täsmäävät.

F1 (A, B, X) = (A+ B)(X AB)

F2 (A, B, X) = B + X → A

Verrataan saatuja totuustaulukoita ja valitaan ne rivit, joissa arvot F 1 (A , B , X ) ja F 2 (A , B , X ) täsmäävät.

Kirjoitamme vain valitut rivit uudelleen, jättäen vain argumenttisarakkeet. Tarkastellaan muuttujaa X A:n ja B:n funktiona.

On selvää, että X = B → A .

Toinen ratkaisu on korvata yhtälön yhtälömerkki vastaavalla merkillä ja yksinkertaistaa sitten saatua loogista yhtälöä.

Jatkotyöskentelyn helpottamiseksi yksinkertaistamme ensin loogisen yhtälön oikeaa ja vasenta puolta ja etsimme niiden negatiivit:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Korvataan yhtäläisyysmerkki loogisessa yhtälössämme ekvivalenssimerkillä:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

Ryhmitetään tämän lausekkeen loogiset termit uudelleen ottamalla tekijät X ja X pois suluista.

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

Merkitään sitten T = A B

X T+ X T= X↔ T.

Siksi, jotta loogisella yhtälöllä olisi ratkaisu: X = A B = B + A = B → A .

Tietokoneen loogiset elementit. Toiminnallisten kaavioiden rakentaminen

Matemaattinen logiikka tietotekniikan kehityksen kanssa oli läheisessä yhteydessä tietotekniikan suunnitteluun ja ohjelmointiin. Logiikkaalgebra löysi laajan sovelluksen alun perin kehityksessä rele-kosketin järjestelmiä. Ensimmäinen perustutkimus, joka kiinnitti tietokoneiden suunnitteluun osallistuneiden insinöörien huomion mahdollisuuteen analysoida sähköpiirejä Boolen algebralla, julkaistiin joulukuussa 1938 amerikkalaisen Claude Shannonin artikkelissa "Symbolic Analysis of Relay-Contact Circuits". Tämän artikkelin jälkeen tietokoneiden suunnittelu ei ollut täydellinen ilman Boolen algebran käyttöä.

Looginen elementti on piiri, joka toteuttaa disjunktion, konjunktion ja inversion loogiset toiminnot. Harkitse loogisten elementtien toteuttamista sähköisten rele-koskettimien kautta, jotka ovat sinulle tuttuja koulun fysiikan kurssilta.

Koskettimien sarjaliitäntä

Koskettimien rinnakkaiskytkentä

Tehdään taulukko piirien tilan riippuvuuksista koskettimien kaikista mahdollisista tiloista. Otetaan käyttöön merkintä: 1 - kosketin on kiinni, virtapiirissä on virta; 0 - kosketin on auki, piirissä ei ole virtaa.

Kuten näet, sarjakytkennällä varustettu piiri vastaa konjunktion loogista toimintaa, koska virtapiirissä näkyy vain, kun koskettimet A ja B suljetaan samanaikaisesti. Rinnakkaiskytkentäinen piiri vastaa loogisen toiminnan disjunktiota, koska virtapiirissä ei ole virtaa vain sillä hetkellä, kun molemmat koskettimet ovat auki.

Inversion looginen toiminta toteutetaan sähkömagneettisen releen kosketuspiirin kautta, jonka periaatetta tutkitaan koulun fysiikan kurssilla. Kosketin x on auki, kun x on kiinni ja päinvastoin.

Relekontaktielementtien käyttö tietokoneiden logiikkapiirien rakentamiseen ei ole perustellut itseään alhaisen luotettavuuden, suurien mittojen, suuren virrankulutuksen ja alhaisen nopeuden vuoksi. Elektronisten laitteiden (tyhjiö ja puolijohde) tulo mahdollisti logiikkaelementtien rakentamisen nopeudella 1 miljoona kytkentää sekunnissa ja enemmän. Puolijohteiden logiikkaelementit toimivat avaintilassa, kuten sähkömagneettinen rele. Koko kosketinpiireille esitetty teoria siirtyy puolijohdeelementteihin. Puolijohteiden loogisia elementtejä ei luonnehdi koskettimien tila, vaan signaalien läsnäolo tulossa ja lähdössä.

Harkitse loogisia elementtejä, jotka toteuttavat loogiset perustoiminnot:

toimintoa vastaava kaavio:

& F(X, Y, Z)

Ongelmien ratkaiseminen konjunktiivi-normaalilla

ja disjunktiivinen-normaali lomakkeita

AT Loogisissa tehtäväkirjoissa on usein vakiotehtäviä, joissa täytyy kirjoittaa muistiin toteuttava funktio tikapuukaavio, yksinkertaistaa sitä ja rakentaa totuustaulukko tälle funktiolle. Kuinka ratkaista käänteinen ongelma? Kun otetaan huomioon mielivaltainen totuustaulukko, sinun on rakennettava toimiva tai relekontaktipiiri. Käsittelemme tätä asiaa tänään.

Mikä tahansa logiikan algebran funktio voidaan esittää kolmen operaation yhdistelmällä: konjunktio, disjunktio ja inversio. Katsotaan kuinka se tehdään. Tätä varten kirjoitamme useita määritelmiä.

Mintermi on funktio, joka muodostuu tietyn määrän muuttujia tai niiden negaatioita yhdistämällä. Minterm ottaa arvon 1 ainoalle mahdolliselle joukolle

argumentit ja arvo 0 kaikille muille. Esimerkki: x 1 x 2 x 3 x 4 .

Maksterm on funktio, joka muodostuu tietyn määrän muuttujia tai niiden negaatioita disjunktiosta. Maxterm ottaa arvon 0 yhdessä mahdollisista joukoista ja 1 kaikista muista.

Esimerkki: x 1 + x 2 + x 3 .

Toiminto sisään disjunktiivinen normaalimuoto(DNF) on mintermien looginen summa.

Esimerkki: x 1x 2+ x 1x 2+ x 1x 2x 3.

Konjunktiivinen normaalimuoto(CNF) on alkeisdisjunktioiden (maxterms) looginen tulos.

Esimerkki: (x 1+ x 2+ x 3) (x 1+ x 2) .

Täydellinen disjunktiivinen normaalimuoto kutsutaan DNF:ksi, jonka jokainen mintermi sisältää kaikki muuttujat tai niiden negaatiot.

Esimerkki: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Täydellinen konjunktiivinen normaalimuoto kutsutaan CNF:ksi, jonka jokaisessa maxtermissä on kaikki muuttujat tai niiden negaatiot.

Esimerkki: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Loogisen funktion tallentaminen taulukkoon

Mikä tahansa looginen funktio voidaan ilmaista muodossa SDNF tai SKNF. Tarkastellaan esimerkkinä taulukossa esitettyä funktiota f.

Funktiot G0, G1, G4, G5, G7 ovat mintermejä (katso määritelmä). Jokainen näistä funktioista on kolmen muuttujan tai niiden käänteisarvon tulos ja saa arvon 1 vain yhdessä tilanteessa. Voidaan nähdä, että jotta funktion f arvoksi saadaan 1, tarvitaan yksi mintermi. Siksi tämän funktion SDNF:n muodostavien mintermien lukumäärä on yhtä suuri kuin ykkösten lukumäärä funktion arvossa: f= G0+G1+G4+G5+G7. Siten SDNF:llä on muoto:

f (x 1, x 2, x 3) = x 1 x 2 x 3+ x 1 x 2 x 3+ x 1 x 2 x 3+ x 1 x 2 x 3+ x 1 x 2 x 3.

Samalla tavalla voidaan rakentaa SKNF. Tekijöiden lukumäärä on yhtä suuri kuin nollien lukumäärä funktioarvoissa:

f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

Siten mikä tahansa taulukon muodossa annettu looginen funktio voidaan kirjoittaa kaavaksi.

Algoritmi SDNF:n rakentamiseksi totuustaulukon mukaan

Jonkin funktion totuustaulukko on annettu. SDNF:n rakentamiseksi sinun on suoritettava seuraavat vaiheet:

1. Valitse kaikki taulukon rivit, joissa funktio saa arvon 1.

2. Jokaiselle tällaiselle riville on määritetty konjunktio kaikista argumenteista tai niiden inversioista (minterm). Tässä tapauksessa argumentti, joka saa arvon 0, syöttää mintermin negaatiolla ja arvo 1 tulee mintermiin ilman negatiivista.

3. Lopuksi muodostamme disjunktion kaikista saaduista mintermeistä. Mintermien lukumäärän on vastattava loogisen funktion yksiköiden määrää.

Algoritmi SKNF:n rakentamiseksi totuustaulukon mukaan

Jonkin funktion totuustaulukko on annettu. SKNF:n rakentamiseksi sinun on suoritettava seuraavat vaiheet:

1. Valitse kaikki taulukon rivit, joissa funktio saa arvon 0.

2. Jokaiselle tällaiselle riville on määritetty disjunktio kaikista argumenteista tai niiden inversioista (maxterm). Tässä tapauksessa argumentti, joka saa arvon 1, sisältyy maxtermiin negatiivisesti ja arvo 1 ilman negatiivista.

3. Lopuksi muodostamme konjunktion kaikista saaduista maksimitermeistä. Maksimitermien määrän on vastattava loogisen funktion nollien määrää.

Jos sovimme kahdesta muodosta (SDNF tai SKNF) suosimaan sitä, joka sisältää vähemmän kirjaimia, niin SDNF on parempi, jos totuustaulukkofunktion, SKNF -funktion arvojen joukossa on vähemmän ykkösiä - jos nollia on vähemmän.

Esimerkki. Kolmen muuttujan loogisen funktion totuustaulukko on annettu. Muodosta looginen kaava, joka toteuttaa tämän funktion.

Valitsemme annetusta totuustaulukosta ne rivit, joissa funktion arvo on 0.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Tarkistetaan johdettu funktio laatimalla totuustaulukko.

Vertaamalla alkuperäistä ja lopullista totuustaulukkoa voimme päätellä, että looginen funktio on rakennettu oikein.

Ongelmanratkaisu

1. Kolme opettajaa valitsee tehtävät olympialaisia ​​varten. Valittavana on useita tehtäviä. Jokaisesta tehtävästä jokainen opettaja ilmaisee mielipiteensä: helppo (0) tai vaikea (1) tehtävä. Tehtävä sisällytetään olympiatehtävään, jos vähintään kaksi opettajaa on merkinnyt sen vaikeaksi, mutta jos kaikki kolme opettajaa pitävät sitä vaikeana, niin tehtävä ei sisälly olympiatehtävään liian vaikeaksi. Tee looginen kaavio laitteesta, joka tulostaa 1, jos ongelma sisältyy olympiatehtävään, ja 0, jos sitä ei ole mukana.

Tehdään totuustaulukko halutusta funktiosta. Meillä on kolme syöttömuuttujaa (kolme opettajaa). Siksi haluttu funktio on kolmen muuttujan funktio.

Analysoimalla ongelman tilaa saadaan seuraava totuustaulukko:

Rakennamme SDNF:n. F(A, B, C) = ABC + ABC + ABC

Nyt rakennamme tämän funktion logiikkapiirin.

B & 1F(A,B,C)

2. Kaupungin olympialaiset informatiikan peruskurssilla 2007.Rakenna kolmikerroksisen talon sisäänkäynnille sähkökytkentäkaavio, jotta minkä tahansa kerroksen kytkimellä voidaan sytyttää tai sammuttaa koko talon valo.

Joten meillä on kolme kytkintä, joilla meidän on kytkettävä valo päälle ja pois. Jokaisella kytkimellä on kaksi tilaa: korkea (0) ja matala (1). Oletetaan, että jos kaikki kolme kytkintä ovat asennossa 0, sisäänkäynnin valo ei pala. Sitten kun siirrät jonkin kolmesta kytkimestä asentoon 1, sisäänkäynnin valon pitäisi syttyä. Ilmeisesti, kun siirrät minkä tahansa muun kytkimen asentoon 1, sisäänkäynnin valo sammuu. Jos kolmas kytkin siirretään asentoon 1, sisäänkäynnin valo syttyy. Rakennamme totuustaulukon.

Sitten F(A, B, C) = ABC+ ABC+ ABC+ ABC.

Merkintä. Jotta voit ratkaista tämän ongelman onnistuneesti, muista seuraavat loogiset kaavat:

x → y= x+ y x y= x y+ x y

x ↔ y= x y + x y

Meille annetaan kolmen muuttujan looginen funktio F 1 (A , B , C ) = C → A + B = C + A B .

Muutetaan muuttujat B ja C samaan aikaan: F 2 (A , B , C ) = F 1 (A , B , C ) = C + A B . Rakennetaan näiden kahden funktion totuustaulukot:

Analysoidaan tuloksena oleva taulukko. Taulukon kahdeksasta rivistä vain kahdella (2. ja 3.) funktio ei muuta arvoaan. Huomaa, että näillä riveillä muuttuja A ei käännä arvoaan, kun taas muuttujat B ja C tekevät.

Rakennamme SKNF-funktioita näiden linjojen mukaan:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (B C) → A

Siksi vaadittu vastaus on 4.

4. Loogisen funktion arvon muuttamisen ehto F (A , B , C ) = C + AB argumentteja A ja B muuttaessa on yhtä suuri kuin:

Analysoidaan tuloksena oleva taulukko. Taulukon kahdeksasta rivistä vain kahdella (1. ja 7.) funktio muuttaa arvoaan. Huomaa, että näillä riveillä muuttuja C ei muuta arvoaan, kun taas muuttujat A ja B muuttavat.

Rakennamme SDNF-funktioita seuraavien linjojen mukaan:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Siksi vaadittu vastaus on 2.

Viitteet

1. Shapiro S.I. Logiikka- ja peliongelmien ratkaiseminen(loogiset ja psykologiset tutkimukset). - M.: Radio ja viestintä, 1984. - 152 s.

2. Sholomov L.A. Diskreetin logiikan ja laskentalaitteiden teorian perusteet. – M.: Tiede. Ch. toim. fyysistä - matto. lit., 1980. - 400 s.

3. Pukhalsky G.I., Novoseltseva T.Ya. Integroitujen piirien erillisten laitteiden suunnittelu.: Käsikirja. - M .: Radio ja viestintä, 1990.

Tapoja ratkaista loogisia yhtälöjärjestelmiä

Kirgizova E.V., Nemkova A.E.

Lesosibirskin pedagoginen instituutti -

Siperian liittovaltion yliopiston haara, Venäjä

Kyky ajatella johdonmukaisesti, väittää lopullisesti, rakentaa hypoteeseja, kumota negatiiviset johtopäätökset, ei tule itsestään, tämä taito on logiikan tieteen kehittämä. Logiikka on tiede, joka tutkii menetelmiä joidenkin väittämien totuuden tai valheellisuuden toteamiseksi muiden väitteiden totuuden tai virheellisyyden perusteella.

Tämän tieteen perusteiden hallitseminen on mahdotonta ilman loogisten ongelmien ratkaisemista. Taitojen muodostumisen tarkistaminen soveltaa tietojaan uudessa tilanteessa suoritetaan läpäisemällä. Erityisesti tämä on kyky ratkaista loogisia ongelmia. Tentin tehtävät B15 ovat monimutkaisempia tehtäviä, koska ne sisältävät loogisia yhtälöjärjestelmiä. On olemassa useita tapoja ratkaista loogisia yhtälöjärjestelmiä. Tämä on pelkistämistä yhteen yhtälöön, totuustaulukon rakentamista, hajottamista, yhtälöiden peräkkäistä ratkaisua jne.

Tehtävä:Ratkaise looginen yhtälöjärjestelmä:

Harkitse pelkistysmenetelmä yhteen yhtälöön . Tämä menetelmä sisältää loogisten yhtälöiden muuntamisen siten, että niiden oikeat puolet ovat yhtä suuret kuin totuusarvo (eli 1). Käytä tätä varten loogista negaatiota. Sitten, jos yhtälöissä on monimutkaisia ​​loogisia operaatioita, korvaamme ne perusoperaatioilla: "AND", "OR", "NOT". Seuraava askel on yhdistää yhtälöt yhdeksi, joka vastaa järjestelmää käyttämällä loogista operaatiota "AND". Sen jälkeen sinun tulee tehdä muunnoksia tuloksena olevasta yhtälöstä logiikan algebran lakien perusteella ja saada systeemille erityinen ratkaisu.

Ratkaisu 1:Käytä inversiota ensimmäisen yhtälön molemmille puolille:

Esitetään implikaatio perusoperaatioilla "OR", "NOT":

Koska yhtälöiden vasen puoli on yhtä suuri kuin 1, voit yhdistää ne AND-operaatiolla yhdeksi yhtälöksi, joka vastaa alkuperäistä järjestelmää:

Avaamme ensimmäisen hakasulkeen de Morganin lain mukaan ja muunnamme tuloksen:

Tuloksena olevalla yhtälöllä on yksi ratkaisu: A= 0, B = 0 ja C = 1.

Seuraava tapa on totuustaulukoiden rakentaminen . Koska loogisilla arvoilla on vain kaksi arvoa, voit yksinkertaisesti käydä läpi kaikki vaihtoehdot ja löytää niistä ne, joille annettu yhtälöjärjestelmä täyttyy. Toisin sanoen rakennamme yhden yhteisen totuustaulukon kaikille järjestelmän yhtälöille ja löydämme rivin halutuilla arvoilla.

Ratkaisu 2:Tehdään totuustaulukko järjestelmälle:

Lihavoitu on viiva, jolla ongelman ehdot täyttyvät. Joten A =0, B =0 ja C =1.

Tapa hajoaminen . Ajatuksena on kiinnittää yhden muuttujan arvo (asettaa se 0:ksi tai 1:ksi) ja siten yksinkertaistaa yhtälöitä. Sitten voit korjata toisen muuttujan arvon ja niin edelleen.

Ratkaisu 3: Päästää A = 0, sitten:

Ensimmäisestä yhtälöstä saamme B =0, ja toisesta - С=1. Järjestelmäratkaisu: A = 0, B = 0 ja C = 1.

Voit myös käyttää menetelmää yhtälöiden peräkkäinen ratkaisu , lisäämällä yhden muuttujan tarkasteltavaan joukkoon kussakin vaiheessa. Tätä varten yhtälöt on muutettava siten, että muuttujat syötetään aakkosjärjestyksessä. Seuraavaksi rakennamme päätöspuun ja lisäämme siihen muuttujia peräkkäin.

Järjestelmän ensimmäinen yhtälö riippuu vain A:sta ja B:stä ja toinen yhtälö A:sta ja C:stä. Muuttujalla A voi olla 2 arvoa 0 ja 1:

Ensimmäisestä yhtälöstä seuraa, että , joten kun A = 0 saamme B = 0, ja kun A = 1, meillä on B = 1. Ensimmäisellä yhtälöllä on siis kaksi ratkaisua muuttujien A ja B suhteen.

Piirrämme toisen yhtälön, josta määritämme C:n arvot kullekin vaihtoehdolle. Jos A =1, implikaatio ei voi olla epätosi, eli puun toisella haaralla ei ole ratkaisua. klo A= 0 saamme ainoan ratkaisun C= 1 :

Siten saimme järjestelmän ratkaisun: A = 0 , B = 0 ja C = 1 .

Tietojenkäsittelytieteen KÄYTÖSSÄ on hyvin usein tarpeen määrittää ratkaisujen lukumäärä loogisten yhtälöjen järjestelmään, etsimättä itse ratkaisuja, tähän on myös tiettyjä menetelmiä. Pääasiallinen tapa löytää ratkaisujen lukumäärä loogiselle yhtälöjärjestelmälle on muuttujien muutos. Ensin on tarpeen yksinkertaistaa kutakin yhtälöä mahdollisimman paljon logiikan algebran lakien perusteella ja sitten korvata yhtälöiden monimutkaiset osat uusilla muuttujilla ja määrittää ratkaisujen lukumäärä uuteen järjestelmään. Palaa sitten korvaavaan tilaan ja määritä sille ratkaisujen määrä.

Tehtävä:Kuinka monta ratkaisua yhtälö ( A → B ) + (C → D ) = 1? Missä A, B, C, D ovat loogisia muuttujia.

Ratkaisu:Otetaan käyttöön uusia muuttujia: X = A → B ja Y = C → D . Uudet muuttujat huomioon ottaen yhtälö voidaan kirjoittaa seuraavasti: X + Y = 1.

Disjunktio on totta kolmessa tapauksessa: (0;1), (1;0) ja (1;1), kun taas X ja Y on implikaatio, eli se on totta kolmessa tapauksessa ja epätosi yhdessä. Siksi tapaus (0;1) vastaa kolmea mahdollista parametrien yhdistelmää. Tapaus (1;1) - vastaa yhdeksää mahdollista alkuperäisen yhtälön parametrien yhdistelmää. Näin ollen tälle yhtälölle on 3+9=15 mahdollista ratkaisua.

Seuraava tapa määrittää loogisen yhtälöjärjestelmän ratkaisujen lukumäärä on − binäärinen puu. Tarkastellaan tätä menetelmää esimerkin avulla.

Tehtävä:Kuinka monta eri ratkaisua loogisella yhtälöjärjestelmällä on:

Annettu yhtälöjärjestelmä vastaa yhtälöä:

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

Teeskennetäänpä sitäx 1 on totta, niin ensimmäisestä yhtälöstä saamme senx 2 myös totta, toisesta -x 3 =1 ja niin edelleen kunnes x m= 1. Tästä syystä joukko (1; 1; …; 1) alkaen m yksiköt on järjestelmän ratkaisu. Anna nytx 1 =0, niin ensimmäisestä yhtälöstä meillä onx 2 =0 tai x 2 =1.

Kun x 2 tosi, saadaan, että muutkin muuttujat ovat tosi, eli joukko (0; 1; ...; 1) on järjestelmän ratkaisu. klox 2 =0 ymmärrämme sen x 3 =0 tai x 3 =, ja niin edelleen. Jatkamalla viimeiseen muuttujaan, huomaamme, että yhtälön ratkaisut ovat seuraavat muuttujajoukot ( m +1 ratkaisu, jokaisessa ratkaisussa m muuttuvat arvot):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Tätä lähestymistapaa havainnollistaa hyvin binääripuun rakentaminen. Mahdollisten ratkaisujen lukumäärä on rakennetun puun eri oksien lukumäärä. On helppo nähdä, että se on m+1.

Jos päättelyssä ja päätöspuun rakentamisessa on vaikeuksia, voit etsiä ratkaisua käyttämällä totuustaulukot, yhdelle tai kahdelle yhtälölle.

Kirjoitamme yhtälöjärjestelmän uudelleen muotoon:

Ja tehdään totuustaulukko erikseen yhdelle yhtälölle:

Tehdään totuustaulukko kahdelle yhtälölle:

Seuraavaksi voit nähdä, että yksi yhtälö on tosi seuraavissa kolmessa tapauksessa: (0; 0), (0; 1), (1; 1). Kahden yhtälön järjestelmä on totta neljässä tapauksessa (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Tässä tapauksessa on heti selvää, että on olemassa ratkaisu, joka koostuu vain nollia ja enemmän m ratkaisuja, joissa lisätään yksi yksikkö viimeisestä paikasta alkaen, kunnes kaikki mahdolliset paikat on täytetty. Voidaan olettaa, että yleisellä ratkaisulla on sama muoto, mutta jotta tällaisesta lähestymistavasta tulisi ratkaisu, vaaditaan todiste siitä, että olettamus on totta.

Yhteenvetona kaikesta yllä olevasta haluaisin kiinnittää huomion siihen, että kaikki tarkasteltavat menetelmät eivät ole universaaleja. Jokaista loogista yhtälöjärjestelmää ratkaistaessa tulee ottaa huomioon sen ominaisuudet, joiden perusteella ratkaisutapa tulee valita.

Kirjallisuus:

1. Loogiset tehtävät / O.B. Bogomolov - 2. painos. – M.: BINOM. Knowledge Laboratory, 2006. - 271 s.: ill.

2. Poljakov K. Yu. Loogiset yhtälöt / Opetus- ja menetelmälehti tietojenkäsittelytieteen opettajille: Informatiikka nro 14, 2011

Oppitunnin aihe: Loogisten yhtälöiden ratkaiseminen

Koulutuksellinen - luoda olosuhteet opiskelijoiden kognitiivisen kiinnostuksen kehittymiselle, edistää muistin, huomion, loogisen ajattelun kehitystä;

Koulutuksellinen : edistää kykyä kuunnella muiden mielipiteitä, tahtoa ja sinnikkyyttä lopputulosten saavuttamiseksi.

Oppitunnin tyyppi: yhdistetty oppitunti

Laitteet: tietokone, multimediaprojektori, esitys 6.

Tuntien aikana

Perustietojen toisto ja päivittäminen. Kotitehtävien tarkistaminen (10 minuuttia)

Edellisillä tunneilla tutustuimme logiikan algebran peruslakeihin, opimme käyttämään näitä lakeja loogisten lausekkeiden yksinkertaistamiseen.

Katsotaanpa kotitehtävä loogisten lausekkeiden yksinkertaistamisesta:

1. Mikä seuraavista sanoista täyttää loogisen ehdon:

(ensimmäinen konsonantti → toinen konsonantti)٨ (viimeisen kirjaimen vokaali → toiseksi viimeinen kirjainvokaali)? Jos tällaisia ​​sanoja on useita, merkitse pienin niistä.

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

Otetaan käyttöön merkintä:

A on konsonantin ensimmäinen kirjain

B on konsonantin toinen kirjain

S on viimeinen vokaali

D - toiseksi viimeinen vokaali

Tehdään ilmaus:

Tehdään taulukko:

2. Ilmoita, mikä looginen lauseke vastaa lauseketta

Yksinkertaistetaan alkuperäisen lausekkeen ja ehdotettujen vaihtoehtojen kirjoittamista:

3. Lausekkeen F totuustaulukon fragmentti annetaan:

Määritetään näiden lausekkeiden arvot määritetyille argumenttien arvoille:

Oppitunnin aiheeseen tutustuminen, uuden materiaalin esittely (30 minuuttia)

Jatkamme logiikan perusteiden ja tämän päivän oppitunnin aiheen "Loogisten yhtälöiden ratkaiseminen" opiskelua. Tämän aiheen opiskelun jälkeen opit perustavat loogisten yhtälöiden ratkaisemiseen, saat taidot ratkaista näitä yhtälöitä käyttämällä logiikkaalgebran kieltä ja kykyä laatia looginen lauseke totuustaulukossa.

1. Ratkaise looginen yhtälö

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

Kirjoita vastauksesi neljän merkin merkkijonona: muuttujien K, L, M ja N arvot (tässä järjestyksessä). Joten esimerkiksi rivi 1101 vastaa K=1, L=1, M=0, N=1.

Ratkaisu:

Muunnetaan lauseke(¬K  M) → (¬L  M  N)

Lauseke on epätosi, kun molemmat termit ovat vääriä. Toinen termi on yhtä suuri kuin 0, jos M=0, N=0, L=1. Ensimmäisessä termissä K = 0, koska M = 0 ja
.

Vastaus: 0100

2. Kuinka monta ratkaisua yhtälöllä on (ilmoita vastauksessasi vain numero)?

Ratkaisu: muunna lauseke

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

A+B=1 ja C+D=1

Tapa 2: Totuustaulukon laatiminen

Muunnetaan alkuperäinen lauseke, avataan sulut saadaksesi konjunktioiden disjunktion:

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

Täydennetään konjunktiot täydellisiksi konjunktioiksi (kaikkien argumenttien tulo), avataan sulut:

Harkitse samoja yhteyksiä:

Tuloksena saadaan SDNF, joka sisältää 9 konjunktia. Siksi tämän funktion totuustaulukon arvo on 1 9 rivillä 2 4 =16 muuttujaarvojoukosta.

3. Kuinka monta ratkaisua yhtälöllä on (ilmoita vastauksessasi vain numero)?

Yksinkertaistetaan lausetta:

,

3 tapaa: SDNF:n rakentaminen

Harkitse samoja yhteyksiä:

Tuloksena saamme SDNF:n, joka sisältää 5 konjunktia. Siksi tämän funktion totuustaulukon arvo on 1 5 rivillä 2 4 =16 muuttujaarvojen joukkoa.

Loogisen lausekkeen rakentaminen totuustaulukon mukaan:

kullekin totuustaulukon riville, joka sisältää luvun 1, muodostamme argumenttien tulon, ja muuttujat, jotka ovat yhtä suuria kuin 0, sisällytetään tuloon negatiivisella ja muuttujat, jotka ovat yhtä suuria kuin 1 - ilman negatiivista. Haluttu lauseke F muodostuu saatujen tuotteiden summasta. Sitten, jos mahdollista, tätä ilmaisua tulisi yksinkertaistaa.

Esimerkki: lausekkeen totuustaulukko on annettu. Rakenna looginen lauseke.

3. Kotitehtävät (5 minuuttia)

Ratkaise yhtälö:

Kuinka monta ratkaisua yhtälöllä on (vastaa vain numero)?

Tee annetun totuustaulukon mukaan looginen lauseke ja

yksinkertaistaa sitä.

Kuinka ratkaista joitakin ongelmia tietojenkäsittelytieteen kokeen osioissa A ja B

Oppitunti numero 3. Logiikka. Logiikkafunktiot. Yhtälöiden ratkaiseminen

Suuri määrä USE-tehtäviä on omistettu ehdotusten logiikalle. Useimpien niistä ratkaisemiseksi riittää, että tunnet lauselogiikan peruslait, yhden ja kahden muuttujan loogisten funktioiden totuustaulukot. Annan propositionaalisen logiikan peruslait.

1. Disjunktion ja konjunktion kommutatiivisuus:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Disjunktiota ja konjunktiota koskeva jakolaki:
   a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negatiivinen negaatio:
   ¬(¬a) ≡ a
4. Johdonmukaisuus:
   a ^ ¬a ≡ väärä
5. Eksklusiivinen kolmas:
   a ˅ ¬a ≡ totta
6. De Morganin lait:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Yksinkertaistaminen:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ tosi ≡ a
   a ˄ epätosi ≡ epätosi
8. Imeytyminen:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Korvaa implikaatiota
   a → b ≡ ¬a ˅ b
10. Identiteettimuutos
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Loogisten funktioiden esitys

Mikä tahansa n muuttujan looginen funktio - F(x 1 , x 2 , ... x n) voidaan määritellä totuustaulukolla. Tällainen taulukko sisältää 2 n muuttujajoukkoa, joille jokaiselle on määritetty tämän joukon funktion arvo. Tämä menetelmä on hyvä, kun muuttujien määrä on suhteellisen pieni. Jopa n > 5, esitys tulee huonosti näkyväksi.

Toinen tapa on määritellä funktio jollain kaavalla käyttämällä tunnettuja melko yksinkertaisia ​​funktioita. Funktiojärjestelmää (f 1 , f 2 , … f k ) kutsutaan täydelliseksi, jos mikä tahansa looginen funktio voidaan ilmaista kaavalla, joka sisältää vain funktioita f i .

Toimintojärjestelmä (¬, ˄, ˅) on valmis. Lait 9 ja 10 ovat esimerkkejä siitä, kuinka implikaatio ja identtisyys ilmaistaan ​​negaatiolla, konjunktiolla ja disjunktiolla.

Itse asiassa kahden funktion järjestelmä on myös täydellinen - negaatio ja konjunktio tai negaatio ja disjunktio. Esitykset perustuvat De Morganin lakeihin, jotka sallivat konjunktion ilmaisemisen negationin ja disjunktion kautta ja vastaavasti disjunktion ilmaisemisen negationin ja konjunktion kautta:

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

Paradoksaalisesti vain yhdestä toiminnosta koostuva järjestelmä on valmis. On kaksi binaarifunktiota - antikonjunktio ja antidisjunktio, joita kutsutaan Piercen nuoleksi ja Schaefferin iskuksi, jotka edustavat onttoa järjestelmää.

Ohjelmointikielten perustoimintoja ovat yleensä identiteetti, negaatio, konjunktio ja disjunktio. Tentin tehtävissä näiden toimintojen ohella on usein implikaatiota.

Katsotaanpa muutamia yksinkertaisia ​​loogisiin toimintoihin liittyviä tehtäviä.

Tehtävä 15:

Esitetään fragmentti totuustaulukosta. Mikä kolmesta annetusta funktiosta vastaa tätä fragmenttia?

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)

Ominaisuus numero 3.

Ongelman ratkaisemiseksi sinun on tunnettava perusfunktioiden totuustaulukot ja pidettävä mielessä toimintojen prioriteetit. Haluan muistuttaa, että konjunktiolla (loogisella kertolaskulla) on korkeampi prioriteetti ja se suoritetaan ennen disjunktiota (loogista yhteenlaskua). Laskettaessa on helppo nähdä, että kolmannen joukon funktioilla numeroilla 1 ja 2 on arvo 1 eivätkä ne tästä syystä vastaa fragmenttia.

Tehtävä 16:

Mikä seuraavista luvuista täyttää ehdon:

(numerot, alkaen merkittävimmästä numerosta, menevät laskevassa järjestyksessä) → (luku - parillinen) ˄ (pienin numero - parillinen) ˄ (suurin numero - pariton)

Jos tällaisia ​​lukuja on useita, merkitse suurin.

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

Ehto täyttyy numerolla 4.

Kaksi ensimmäistä numeroa eivät täytä ehtoa, koska alin numero on pariton. Ehtojen konjunktio on epätosi, jos jokin konjunktion ehdoista on epätosi. Kolmannen numeron osalta korkeimman numeron ehto ei täyty. Neljännen numeron osalta numeron ala- ja isonumeroille asetetut ehdot täyttyvät. Myös konjunktion ensimmäinen termi on tosi, koska implikaatio on tosi, jos sen premissi on epätosi, kuten tässä tapauksessa.

Ongelma 17: Kaksi todistajaa todisti seuraavasti:

Ensimmäinen todistaja: Jos A on syyllinen, niin B on varmasti syyllinen ja C on syytön.

Toinen todistaja: Kaksi on syyllisiä. Ja yksi jäljellä olevista on ehdottomasti syyllinen ja syyllinen, mutta en osaa sanoa tarkalleen kuka.

Mitä johtopäätöksiä A:n, B:n ja C:n syyllisyydestä voidaan tehdä todisteista?

Vastaus: Todistuksesta seuraa, että A ja B ovat syyllisiä, mutta C on syytön.

Ratkaisu: Tietysti vastaus voidaan antaa maalaisjärjen perusteella. Mutta katsotaanpa, kuinka tämä voidaan tehdä tiukasti ja muodollisesti.

Ensimmäinen asia on virallistaa lausunnot. Otetaan käyttöön kolme Boolen muuttujaa, A, B ja C, joista jokainen on tosi (1), jos vastaava epäilty on syyllinen. Sitten ensimmäisen todistajan todistus annetaan kaavalla:

A → (B ˄ ¬C)

Toisen todistajan todistus annetaan kaavalla:

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

Molempien todistajien todistusten oletetaan olevan totta ja ne edustavat vastaavien kaavojen konjunktiota.

Rakennetaan totuustaulukko näille lukemille:

Yhteenvetotodistus on totta vain yhdessä tapauksessa, mikä johtaa selkeään vastaukseen - A ja B ovat syyllisiä ja C on syytön.

Tämän taulukon analyysistä seuraa myös, että toisen todistajan todistus on informatiivisempi. Hänen todistuksensa totuudesta seuraa vain kaksi mahdollista vaihtoehtoa - A ja B ovat syyllisiä ja C on syytön tai A ja C ovat syyllisiä ja B on syytön. Ensimmäisen todistajan todistus on vähemmän informatiivinen - on 5 eri vaihtoehtoa, jotka vastaavat hänen todistustaan. Yhdessä molempien todistajien todistukset antavat yksiselitteisen vastauksen epäiltyjen syyllisyydestä.

Logiikkayhtälöt ja yhtälöjärjestelmät

Olkoon F(x 1 , x 2 , …x n) n muuttujan looginen funktio. Looginen yhtälö on:

F(x 1, x 2, ... x n) \u003d C,

Vakiolla C on arvo 1 tai 0.

Loogisella yhtälöllä voi olla 0-2n erilaista ratkaisua. Jos C on 1, niin ratkaisut ovat kaikki ne totuustaulukon muuttujajoukot, joissa funktio F saa arvon tosi (1). Loput joukot ovat yhtälön ratkaisuja C:lle, joka on yhtä suuri kuin nolla. Voimme aina tarkastella vain yhtälöitä, joiden muoto on:

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

Todellakin, annetaan yhtälö:

F(x1, x2, …xn) = 0

Tässä tapauksessa voit siirtyä vastaavaan yhtälöön:

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

Tarkastellaan k loogisen yhtälön järjestelmää:

F 1 (x 1, x 2, ... x n) \u003d 1

F 2 (x 1, x 2, ... x n) \u003d 1

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

Järjestelmän ratkaisu on joukko muuttujia, joihin kaikki järjestelmän yhtälöt täyttyvät. Loogisten funktioiden osalta ratkaisun saamiseksi loogisten yhtälöiden järjestelmään tulisi löytää joukko, jossa looginen funktio Ф on tosi, edustaen alkuperäisten funktioiden F konjunktiota:

Ф = F 1 ˄ F 2 ˄ … F k

Jos muuttujien määrä on pieni, esimerkiksi alle 5, niin funktiolle Ф ei ole vaikeaa rakentaa totuustaulukkoa, jonka avulla voidaan sanoa kuinka monta ratkaisua järjestelmässä on ja mitkä ovat ratkaisuja antavat joukot.

Joissakin Unified State Examinationin tehtävissä ratkaisujen löytämiseksi loogiseen yhtälöjärjestelmään muuttujien määrä saavuttaa arvon 10. Silloin totuustaulukon rakentamisesta tulee lähes ratkaisematon tehtävä. Ongelman ratkaiseminen vaatii erilaista lähestymistapaa. Mielivaltaiselle yhtälöjärjestelmälle ei ole olemassa muuta yleistä tapaa kuin luettelointi, joka mahdollistaisi tällaisten ongelmien ratkaisemisen.

Tentissä ehdotetuissa tehtävissä ratkaisu perustuu yleensä yhtälöjärjestelmän erityispiirteiden huomioon ottamiseen. Toistan, että lukuun ottamatta muuttujien joukon kaikkien muunnelmien luetteloa, ongelman ratkaisemiseksi ei ole yleistä tapaa. Ratkaisu tulee rakentaa järjestelmän erityispiirteiden mukaan. Usein on hyödyllistä suorittaa yhtälöjärjestelmän alustava yksinkertaistaminen tunnettujen logiikan lakien avulla. Toinen hyödyllinen tekniikka tämän ongelman ratkaisemiseksi on seuraava. Meitä ei kiinnosta kaikki joukot, vaan vain ne, joissa funktiolla Ф on arvo 1. Täydellisen totuustaulukon rakentamisen sijaan rakennamme sen analogin - binaarisen päätöspuun. Jokainen tämän puun haara vastaa yhtä ratkaisua ja määrittää joukon, jossa funktion Ф arvo on 1. Haarojen lukumäärä päätöspuussa on yhtä suuri kuin yhtälöjärjestelmän ratkaisujen lukumäärä.

Mikä on binäärinen päätöspuu ja miten se rakennetaan, selitän esimerkkien avulla useista tehtävistä.

Ongelma 18

Kuinka monta erilaista Boolen muuttujien x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 arvojoukkoa on olemassa, jotka täyttävät kahden yhtälön järjestelmän?

Vastaus: Järjestelmässä on 36 erilaista ratkaisua.

Ratkaisu: Yhtälöjärjestelmä sisältää kaksi yhtälöä. Etsitään ensimmäisen yhtälön ratkaisujen lukumäärä 5 muuttujasta riippuen – x 1 , x 2 , …x 5 . Ensimmäistä yhtälöä voidaan puolestaan ​​pitää 5 yhtälöjärjestelmänä. Kuten on osoitettu, yhtälöjärjestelmä edustaa itse asiassa loogisten funktioiden konjunktiota. Myös käänteinen väite on totta - ehtojen konjunktiota voidaan pitää yhtälöjärjestelmänä.

Tehdään päätöspuu implikaatiolle (x1→ x2), konjunktion ensimmäiselle termille, jota voidaan pitää ensimmäisenä yhtälönä. Tältä tämän puun graafinen esitys näyttää:

Puu koostuu kahdesta tasosta yhtälön muuttujien lukumäärän mukaan. Ensimmäinen taso kuvaa ensimmäistä muuttujaa X 1 . Tämän tason kaksi haaraa heijastavat tämän muuttujan mahdollisia arvoja - 1 ja 0. Toisella tasolla puun haarat heijastavat vain niitä muuttujan X 2 mahdollisia arvoja, joille yhtälö saa arvon tosi. Koska yhtälö määrittelee implikaation, haara, jossa X 1:n arvo on 1, edellyttää, että X 2:lla on arvo 1. Haara, jolla X 1:llä on arvo 0, muodostaa kaksi haaraa, joiden X 2 -arvot ovat yhtä suuret kuin 0 ja 1 Rakennetussa puussa on kolme ratkaisua, joissa implikaatio X 1 → X 2 saa arvon 1. Jokaiselle haaralle kirjoitetaan vastaava muuttujien arvojoukko, joka antaa yhtälön ratkaisun.

Nämä joukot ovat: ((1, 1), (0, 1), (0, 0))

Jatketaan päätöspuun rakentamista lisäämällä seuraava yhtälö, seuraava implikaatio X 2 → X 3 . Yhtälöjärjestelmämme erityispiirre on, että jokainen uusi järjestelmän yhtälö käyttää yhtä muuttujaa edellisestä yhtälöstä ja lisää yhden uuden muuttujan. Koska muuttujalla X 2 on jo arvoja puussa, niin kaikissa oksissa, joissa muuttujan X 2 arvo on 1, muuttujalla X 3 on myös arvo 1. Tällaisille oksille puun rakentaminen jatkuu seuraavalle tasolle, mutta uusia oksia ei näy. Ainoa haara, jossa muuttujan X 2 arvo on 0, muodostaa haaran kahteen haaraan, joissa muuttuja X 3 saa arvot 0 ja 1. Siten jokainen uuden yhtälön lisäys, sen spesifisyyden vuoksi, lisää yhden ratkaisu. Alkuperäinen ensimmäinen yhtälö:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
on 6 ratkaisua. Tämän yhtälön täydellinen päätöspuu näyttää tältä:

Järjestelmämme toinen yhtälö on samanlainen kuin ensimmäinen:

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

Ainoa ero on, että yhtälö käyttää muuttujia Y. Tässä yhtälössä on myös 6 ratkaisua. Koska jokainen muuttujaratkaisu X i voidaan yhdistää jokaiseen muuttujaratkaisuun Y j , ratkaisujen kokonaismäärä on 36.

Huomaa, että rakennettu päätöspuu ei anna vain ratkaisujen lukumäärää (haarojen lukumäärän mukaan), vaan myös itse ratkaisut, jotka on kirjoitettu puun jokaiseen haaraan.

Ongelma 19

Kuinka monta erilaista loogisten muuttujien x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 arvojoukkoa on olemassa, jotka täyttävät kaikki seuraavat ehdot?

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

Tämä tehtävä on muunnos edellisestä tehtävästä. Erona on, että lisätään toinen yhtälö, joka yhdistää X- ja Y-muuttujat.

Yhtälöstä X 1 → Y 1 seuraa, että kun X 1:n arvo on 1 (yksi tällainen ratkaisu on olemassa), niin Y 1:llä on arvo 1. Siten on yksi joukko, jossa X 1:llä ja Y 1:llä on arvot ​1. Kun X 1 on 0, Y 1:llä voi olla mikä tahansa arvo, sekä 0 että 1. Siksi jokainen joukko, jossa X 1 on 0, ja tällaisia ​​joukkoja on 5, vastaa kaikkia kuutta joukkoa, joissa on Y-muuttuja. , ratkaisujen kokonaismäärä on 31 .

Ongelma 20

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

Ratkaisu: Muistaen perusekvivalenssin, kirjoitamme yhtälömme seuraavasti:

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

Implikaatioiden syklinen ketju tarkoittaa, että muuttujat ovat identtisiä, joten yhtälömme on ekvivalentti:

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

Tällä yhtälöllä on kaksi ratkaisua, kun kaikki X i ovat joko 1 tai 0.

Ongelma 21

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

Ratkaisu: Kuten tehtävässä 20, siirrymme syklisistä implikaatioista identiteettiin kirjoittamalla yhtälön uudelleen muotoon:

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

Rakennetaan päätöspuu tälle yhtälölle:

Ongelma 22

Kuinka monta ratkaisua seuraavalla yhtälöjärjestelmällä on?

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

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

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

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

Vastaus: 64

Ratkaisu: Siirrytään 10 muuttujasta 5 muuttujaan ottamalla käyttöön seuraava muuttujien muutos:

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

Sitten ensimmäinen yhtälö saa muodon:

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

Yhtälöä voidaan yksinkertaistaa kirjoittamalla se seuraavasti:

(Y 1 ≡ Y 2) = 0

Siirtyessämme perinteiseen muotoon kirjoitamme järjestelmän yksinkertaistamisen jälkeen muodossa:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Tämän järjestelmän päätöspuu on yksinkertainen ja koostuu kahdesta haarasta, joissa on vuorottelevat muuttujan arvot:

Palatakseni alkuperäisiin X-muuttujiin, huomaa, että jokainen Y-muuttujan arvo vastaa kahta X-muuttujan arvoa, joten jokainen Y-muuttujien ratkaisu tuottaa 25 ratkaisua X-muuttujiin. Kaksi haaraa 2 * 25 ratkaisua , joten ratkaisujen kokonaismäärä on 64.

Kuten näet, jokainen tehtävä yhtälöjärjestelmän ratkaisemiseksi vaatii oman lähestymistavan. Yleinen temppu on suorittaa vastaavat muunnokset yhtälöiden yksinkertaistamiseksi. Yleinen tekniikka on päätöspuiden rakentaminen. Sovellettu lähestymistapa muistuttaa osittain totuustaulukon rakentamista sillä erityispiirteellä, että kaikkia mahdollisia muuttujien arvojoukkoja ei rakenneta, vaan vain niitä, joissa funktio saa arvon 1 (true). Usein ehdotetuissa ongelmissa ei ole tarvetta rakentaa täydellistä päätöspuuta, koska jo alkuvaiheessa on mahdollista määrittää uusien oksien ilmaantumisen säännöllisyys kullakin seuraavalla tasolla, kuten tehtiin esimerkiksi tehtävässä 18. .

Yleensä ongelmat ratkaisujen löytämiseksi loogiseen yhtälöjärjestelmään ovat hyviä matemaattisia harjoituksia.

Jos ongelmaa on vaikea ratkaista manuaalisesti, voit uskoa ongelman ratkaisun tietokoneelle kirjoittamalla sopivan ohjelman yhtälöiden ja yhtälöjärjestelmien ratkaisemiseksi.

Sellaisen ohjelman kirjoittaminen on helppoa. Tällainen ohjelma selviytyy helposti kaikista kokeessa tarjotuista tehtävistä.

Kummallista kyllä, mutta ratkaisujen löytäminen loogisten yhtälöjärjestelmien järjestelmiin on myös tietokoneelle vaikeaa, mutta osoittautuu, että tietokoneella on rajansa. Tietokone selviää helposti tehtävissä, joissa muuttujia on 20-30, mutta isompia tehtäviä se alkaa miettimään pitkään. Asia on siinä, että joukkojen lukumäärää määrittelevä funktio 2n on eksponentti, joka kasvaa nopeasti n:n kanssa. Niin nopeasti, että tavallinen henkilökohtainen tietokone ei pysty käsittelemään tehtävää, jossa on 40 muuttujaa päivässä.

C#-ohjelma loogisten yhtälöiden ratkaisemiseen

Ohjelman kirjoittaminen loogisten yhtälöiden ratkaisemiseen on hyödyllistä monista syistä, jo pelkästään siksi, että sen avulla voidaan tarkistaa oman ratkaisusi oikeellisuus USE-testin ongelmiin. Toinen syy on se, että tällainen ohjelma on erinomainen esimerkki ohjelmointiongelmasta, joka täyttää USE:n luokan C ongelmien vaatimukset.

Ohjelman rakentamisen idea on yksinkertainen - se perustuu kaikkien mahdollisten muuttujaarvojen täydelliseen luetteloon. Koska tietylle loogiselle yhtälölle tai yhtälöjärjestelmälle tiedetään muuttujien lukumäärä n, tiedetään myös joukkojen lukumäärä - 2 n , jotka on selvitettävä. Käyttämällä C#-kielen perusfunktioita - negaatiota, disjunktiota, konjunktiota ja identiteettiä - on helppo kirjoittaa ohjelma, joka tietylle muuttujajoukolle laskee loogista yhtälöä tai yhtälöjärjestelmää vastaavan loogisen funktion arvon.

Tällaisessa ohjelmassa sinun on rakennettava sykli joukkojen lukumäärällä, syklin rungossa joukon numerolla, muodostettava itse joukko, laskettava tämän joukon funktion arvo ja jos tämä arvo on sama 1, niin joukko antaa ratkaisun yhtälöön.

Ainoa vaikeus, joka syntyy ohjelman toteutuksessa, liittyy tehtävään muodostaa itse muuttuja-arvot asetetulla numerolla. Tämän tehtävän kauneus on, että tämä näennäisesti vaikea tehtävä itse asiassa laskeutuu yksinkertaiseen tehtävään, joka on jo toistuvasti noussut esiin. Todellakin, riittää ymmärtää, että lukua i vastaavien muuttujien arvojen joukko, joka koostuu nollista ja ykkösistä, edustaa luvun i binääriesitystä. Joten monimutkainen tehtävä muuttujien arvojen joukon saaminen asetetun numeron mukaan rajoittuu hyvin tunnettuun ongelmaan luvun muuntamisesta binäärijärjestelmäksi.

Ongelmamme ratkaiseva C#-funktio näyttää tältä:

///

///

/// looginen funktio - menetelmä,

/// jonka allekirjoituksen on DF:n edustaja

///

/// muuttujien määrä

/// ratkaisujen määrä

staattinen int SolveEquations(DF hauska, int n)

bool set = uusi bool[n];

int m = (int)Math.Pow(2, n); //sarjojen määrä

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

//Täydellinen luettelo sarjojen lukumäärän mukaan

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

//Seuraavan joukon muodostuminen — joukko,

//joka on annettu luvun i binääriesityksenä

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

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

//Laske funktion arvo asetettuna

Ohjelman ymmärtämiseksi toivon, että ohjelman idean selitykset ja sen tekstissä olevat kommentit riittävät. Pysähdyn vain yllä olevan funktion otsikon selitykseen. SolveEquations-funktiolla on kaksi syöttöparametria. Fun-parametri määrittää loogisen funktion, joka vastaa ratkaistavaa yhtälöä tai yhtälöjärjestelmää. Parametri n määrittää muuttujien lukumäärän fun-funktiossa. Tämän seurauksena SolveEquations-funktio palauttaa loogisen funktion ratkaisujen lukumäärän, eli niiden joukkojen määrän, joiden perusteella funktio arvioi tosi.

Koululaisille on tavallista, kun jonkin funktion F(x) syöteparametri x on aritmeettinen, merkkijono tai boolen tyyppinen muuttuja. Meidän tapauksessamme käytetään tehokkaampaa muotoilua. SolveEquations-funktiolla tarkoitetaan korkeamman asteen funktioita - tyypin F(f) funktioita, joiden parametrit voivat olla yksinkertaisten muuttujien lisäksi myös funktioita.

Funktioiden luokka, jotka voidaan välittää parametreina SolveEquations-funktiolle, määritellään seuraavasti:

delegoida bool DF(bool vars);

Tämä luokka sisältää kaikki funktiot, jotka välitetään parametrina vars-taulukon määrittämien loogisten muuttujien arvojen joukko. Tuloksena on Boolen arvo, joka edustaa tämän joukon funktion arvoa.

Lopuksi annan ohjelman, jossa SolveEquations-funktiota käytetään useiden loogisten yhtälöjärjestelmien ratkaisemiseen. SolveEquations-funktio on osa seuraavaa ProgramCommon-luokkaa:

luokan ProgramCommon

delegoida bool DF(bool vars);

staattinen void Main (jonoargumentit)

Console.WriteLine("Toiminto ja ratkaisut - " +

Ratkaise yhtälöt (Hauska, 2));

Console.WriteLine("Funktiolla on 51 ratkaisua - " +

Ratkaise yhtälöt (Fun51, 5));

Console.WriteLine("Funktiolla on 53 ratkaisua - " +

Ratkaise yhtälöt (Fun53, 10));

staattinen bool FunAnd(bool vars)

return vars && vars;

staattinen bool Fun51(bool vars)

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

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

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

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

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

staattinen bool Fun53(bool vars)

f = f && ((muuttujat == muuttujat) || (muuttujat == muuttujat));

f = f && ((muuttujat == muuttujat) || (muuttujat == muuttujat));

f = f && ((muuttujat == muuttujat) || (muuttujat == muuttujat));

f = f && ((muuttujat == muuttujat) || (muuttujat == muuttujat));

f = f && ((muuttujat == muuttujat) || (muuttujat == muuttujat));

f = f && ((muuttujat == muuttujat) || (muuttujat == muuttujat));

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

Tämän ohjelman ratkaisun tulokset näyttävät tältä:

10 tehtävää itsenäiseen työskentelyyn

1. Mitkä kolmesta funktiosta ovat vastaavia:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Fragmentti totuustaulukosta annetaan:

Mikä kolmesta funktiosta vastaa tätä fragmenttia:

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. Tuomaristo koostuu kolmesta henkilöstä. Päätös on tehty, jos tuomariston puheenjohtaja äänestää sen puolesta ja sitä kannattaa vähintään yksi tuomariston jäsenistä. Muuten päätöstä ei tehdä. Rakenna looginen funktio, joka virallistaa päätöksentekoprosessin.
5. X voittaa Y:n, jos neljä kolikonheittoa osuu kolmesti. Määritä boolen funktio, joka kuvaa voittoa X.
6. Lauseen sanat numeroidaan yhdestä alkaen. Lause katsotaan hyvin muotoilluksi, jos seuraavat säännöt täyttyvät:
   1. Jos parillinen sana päättyy vokaaliin, seuraavan sanan, jos se on olemassa, tulee alkaa vokaalilla.
   2. Jos pariton sana päättyy konsonanttiin, seuraavan sanan, jos se on olemassa, täytyy alkaa konsonantilla ja päättyä vokaaliin.
      Mitkä seuraavista lauseista ovat oikein:
   3. Äiti pesi Mashan saippualla.
   4. Johtaja on aina malli.
   5. Totuus on hyvä, mutta onnellisuus on parempi.
7. Kuinka monta ratkaisua yhtälöllä on:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Listaa kaikki yhtälön ratkaisut:
   (a → b) → c = 0
9. Kuinka monta ratkaisua seuraavalla yhtälöjärjestelmällä on:
   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. Kuinka monta ratkaisua yhtälöllä on:
    (((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Vastaukset tehtäviin:

1. Funktiot b ja c ovat ekvivalentteja.
2. Fragmentti vastaa toimintoa b.
3. Olkoon loogisen muuttujan P arvo 1, kun tuomariston puheenjohtaja äänestää "puoleen". Muuttujat M 1 ja M 2 edustavat tuomariston jäsenten mielipidettä. Looginen funktio, joka määrittelee myönteisen päätöksen tekemisen, voidaan kirjoittaa seuraavasti:
   P ˄ (M 1 ˅ M 2)
4. Olkoon loogisen muuttujan P i arvo 1, kun i:s kolikonheitto nousee ylös. Voiton X määrittelevä looginen funktio voidaan kirjoittaa seuraavasti:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Tarjous b.
6. Yhtälössä on 3 ratkaisua: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)