Kuinka ratkaista loogisia kaavoja. Loogiset yhtälöt tietojenkäsittelytieteen Unified State Exam -tehtävissä

Yhtälöiden käyttö on yleistä elämässämme. Niitä käytetään monissa laskelmissa, rakenteiden rakentamisessa ja jopa urheilussa. Ihminen käytti yhtälöitä muinaisina aikoina, ja siitä lähtien niiden käyttö on vain lisääntynyt. Matematiikassa on tiettyjä propositionaalisen logiikan ongelmia. Tämän kaltaisen yhtälön ratkaisemiseksi sinulla on oltava tietty määrä tietoa: tietämystä lauselogiikan laeista, tietoa 1 tai 2 muuttujan loogisten funktioiden totuustaulukoista, menetelmiä loogisten lausekkeiden muuntamiseen. Lisäksi sinun tulee tietää seuraavat loogisten operaatioiden ominaisuudet: konjunktio, disjunktio, inversio, implikaatio ja ekvivalenssi.

Mikä tahansa \variables - \ -funktion looginen funktio voidaan määrittää totuustaulukolla.

Ratkaistaan ​​useita loogisia yhtälöitä:

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

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

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

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

Aloitetaan ratkaisu \[X1\]:lla ja määritetään, mitä arvoja tämä muuttuja voi ottaa: 0 ja 1. Seuraavaksi tarkastelemme jokaista yllä olevaa arvoa ja katsomme, mikä \[X2.\] voi olla.

Kuten taulukosta voidaan nähdä, loogisessa yhtälössämme on 11 ratkaisua.

Mistä voin ratkaista logiikkayhtälön verkossa?

Voit ratkaista yhtälön verkkosivustollamme https://site. Ilmaisen online-ratkaisijan avulla voit ratkaista minkä tahansa monimutkaisia ​​online-yhtälöitä muutamassa sekunnissa. Sinun tarvitsee vain syöttää tietosi ratkaisijaan. Voit myös katsoa video-ohjeet ja oppia ratkaisemaan yhtälön verkkosivustoltamme. Ja jos sinulla on vielä kysyttävää, voit kysyä niitä VKontakte-ryhmässämme http://vk.com/pocketteacher. Liity joukkoomme, autamme sinua aina mielellämme.

Loogisten yhtälöjärjestelmien ratkaiseminen muuttujia muuttamalla

Muuttujien korvausmenetelmää käytetään, jos jotkin muuttujat sisällytetään yhtälöihin vain tietyn lausekkeen muodossa, ei mitään muuta. Sitten tämä lauseke voidaan merkitä uudella muuttujalla.

Esimerkki 1.

Kuinka monta erilaista arvojoukkoa loogisilla muuttujilla x1, x2, x3, x4, x5, x6, x7, x8 on olemassa, jotka täyttävät kaikki alla luetellut ehdot?

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

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

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

Vastauksen ei tarvitse luetella kaikkia muuttujien x1, x2, x3, x4, x5, x6, x7, x8 erilaisia ​​arvojoukkoja, joille tämä yhtäläisyysjärjestelmä täyttyy. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Sitten voimme kirjoittaa järjestelmän yhden yhtälön muodossa:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunktio on 1 (tosi), kun jokainen operandi saa arvon 1. jokaisen implikaatiosta on oltava tosi, ja tämä pätee kaikille arvoille paitsi (1 → 0). Nuo. muuttujien y1, y2, y3, y4 arvotaulukossa yksi ei saa olla nollan vasemmalla puolella:

Nuo. ehdot täyttyvät 5 sarjalle y1-y4.

Koska y1 = x1 → x2, niin arvo y1 = 0 saavutetaan yhdellä joukolla x1, x2: (1, 0) ja arvo y1 = 1 – kolmella joukolla x1, x2: (0,0) , (0 ,1), (1.1). Samoin y2, y3, y4.

Koska jokainen joukko (x1,x2) muuttujalle y1 yhdistetään jokaiseen joukkoon (x3,x4) muuttujalle y2 jne., muuttujien x joukkojen määrät kerrotaan:

Lasketaan yhteen joukkojen määrä: 1 + 3 + 9 + 27 + 81 = 121.

Vastaus: 121

Esimerkki 2.

Kuinka monta erilaista arvojoukkoa loogisilla muuttujilla x1, x2, ... x9, y1, y2, ... y9 on olemassa, jotka täyttävät kaikki alla luetellut ehdot?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

Vastauksena ei tarvetta luettele kaikki muuttujien x1, x2, ... x9, y1, y2, ... y9 erilaiset arvojoukot, joille annettu yhtäläisyysjärjestelmä täyttyy. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu:

Tehdään muuttujien muutos:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Järjestelmä voidaan kirjoittaa yhtenä yhtälönä:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Ekvivalenssi on totta vain, jos molemmat operandit ovat yhtä suuret. Tälle yhtälölle on kaksi ratkaisusarjaa:

Koska zi = (xi ≡ yi), silloin arvo zi = 0 vastaa kahta joukkoa (xi,yi): (0,1) ja (1,0) ja arvo zi = 1 vastaa kahta joukkoa (xi,yi) ): (0 ,0) ja (1,1).

Sitten ensimmäinen joukko z1, z2,…, z9 vastaa 2 9 joukkoa (x1,y1), (x2,y2),…, (x9,y9).

Sama numero vastaa toista joukkoa z1, z2,…, z9. Sitten on yhteensä 2 9 +2 9 = 1024 sarjaa.

Vastaus: 1024

Loogisten yhtälöjärjestelmien ratkaiseminen rekursion visuaalisen määrityksen menetelmällä.

Tätä menetelmää käytetään, jos yhtälöjärjestelmä on melko yksinkertainen ja joukkojen määrän lisäämisjärjestys muuttujia lisättäessä on ilmeinen.

Esimerkki 3.

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

¬x9 ∨ x10 = 1,

missä x1, x2, … x10 ovat loogisia muuttujia?

Vastauksen ei tarvitse luetella kaikkia erilaisia ​​arvojoukkoja x1, x2, ... x10, joille tämä yhtäläisyysjärjestelmä täyttyy. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu:

Ratkaistaan ​​ensimmäinen yhtälö. Disjunktio on yhtä suuri kuin 1, jos ainakin yksi sen operandeista on yhtä suuri kuin 1. Eli ratkaisut ovat sarjat:

Kun x1=0 on kaksi x2:n arvoa (0 ja 1), ja x1=1:llä on vain yksi arvo x2 (1), joten joukko (x1,x2) on yhtälön ratkaisu . Yhteensä on 3 settiä.

Lisätään muuttuja x3 ja tarkastellaan toista yhtälöä. Se on samanlainen kuin ensimmäinen, mikä tarkoittaa, että arvolla x2=0 on kaksi x3:n arvoa (0 ja 1) ja arvolla x2=1 on vain yksi arvo x3 (1), joten joukko (x2 ,x3) on yhtälön ratkaisu. Yhteensä on 4 settiä.

On helppo nähdä, että kun lisäät toisen muuttujan, yksi joukko lisätään. Nuo. rekursiivinen kaava (i+1)-muuttujien joukkojen lukumäärälle:

N i +1 = N i + 1. Sitten kymmenelle muuttujalle saadaan 11 joukkoa.

Vastaus: 11

Erilaisten loogisten yhtälöjärjestelmien ratkaiseminen

Esimerkki 4.

Kuinka monta erilaista arvojoukkoa loogisilla muuttujilla x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 on olemassa, jotka täyttävät kaikki alla luetellut ehdot ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

Vastauksena ei tarvetta luettele kaikki muuttujien x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 eri arvojoukot, joille tämä yhtäläisyysjärjestelmä täyttyy.

Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu:

Huomaa, että järjestelmän kolme yhtälöä ovat samat eri riippumattomilla muuttujajoukoilla.

Katsotaanpa ensimmäistä yhtälöä. Konjunktio on tosi (yhtä kuin 1) vain, jos kaikki sen operandit ovat tosi (yhtä kuin 1). Implikaatio on 1 kaikissa monissa paitsi (1,0). Tämä tarkoittaa, että ensimmäisen yhtälön ratkaisu on seuraavat joukot x1, x2, x3, x4, joissa 1 ei ole 0:n (5 joukkoa) vasemmalla puolella:

Vastaavasti toisen ja kolmannen yhtälön ratkaisut ovat täysin samat joukot y1,…,y4 ja z1,…, z4.

Analysoidaan nyt järjestelmän neljättä yhtälöä: x 4 ∧ y 4 ∧ z 4 = 0. Ratkaisuksi tulee kaikki joukot x4, y4, z4, joissa vähintään yksi muuttujista on yhtä suuri kuin 0.

Nuo. x4 = 0:lle sopivat kaikki mahdolliset joukot (y4, z4) ja x4 = 1:lle sopivat joukot (y4, z4), joissa on vähintään yksi nolla: (0, 0), (0,1) ), (1, 0).

Sarjojen kokonaismäärä on 25 + 4*9 = 25 + 36 = 61.

Vastaus: 61

Loogisten yhtälöjärjestelmien ratkaiseminen rakentamalla toistuvia kaavoja

Toistuvien kaavojen konstruointimenetelmää käytetään ratkaistaessa monimutkaisia ​​järjestelmiä, joissa joukkojen määrän lisäämisjärjestys ei ole ilmeinen ja puun rakentaminen on mahdotonta volyymien vuoksi.

Esimerkki 5.

Kuinka monta erilaista arvojoukkoa loogisilla muuttujilla x1, x2, ... x7, y1, y2, ... y7 on olemassa, jotka täyttävät kaikki alla luetellut ehdot?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

Vastauksen ei tarvitse luetella kaikkia muuttujien x1, x2, ..., x7, y1, y2, ..., y7 erilaisia ​​arvojoukkoja, joille tämä yhtäläisyysjärjestelmä täyttyy. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu:

Huomaa, että järjestelmän kuusi ensimmäistä yhtälöä ovat identtisiä ja eroavat toisistaan ​​vain muuttujien joukossa. Katsotaanpa ensimmäistä yhtälöä. Sen ratkaisu on seuraavat muuttujajoukot:

Merkitään:

monikoiden määrä (0,0) muuttujilla (x1,y1) - A 1,

monikoiden määrä (0,1) muuttujilla (x1,y1) - B 1,

monikoiden määrä (1,0) muuttujilla (x1,y1) - C 1,

monikoiden lukumäärä (1,1) muuttujilla (x1,y1) - D 1 .

monikoiden määrä (0,0) muuttujilla (x2,y2) - A 2 ,

monikoiden määrä (0,1) muuttujilla (x2,y2) - B 2,

monikkomäärä (1,0) muuttujilla (x2,y2) - C 2,

monikoiden lukumäärä (1,1) muuttujilla (x2,y2) - D 2 .

Päätöspuusta näemme sen

A 1 = 0, B 1 = 1, C 1 = 1, D 1 = 1.

Huomaa, että muuttujien (x2,y2) joukko (0,0) saadaan muuttujien (x1,y1) joukoista (0,1), (1,0) ja (1,1). Nuo. A 2 = B 1 + C 1 + D 1.

Muuttujien (x2,y2) joukko (0,1) saadaan muuttujien (x1,y1) joukoista (0,1), (1,0) ja (1,1). Nuo. B 2 = B 1 + C 1 + D 1.

Väittäen samalla tavalla, huomaamme, että C 2 =B 1 + C 1 + D 1. D2 = D1.

Siten saamme toistuvat kaavat:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i + B i + C i + D i

Tehdään pöytä

Viimeinen yhtälö (x7 ∨ y7) = 1 täyttyy kaikissa joukoissa paitsi niissä, joissa x7=0 ja y7=0. Taulukossamme tällaisten joukkojen lukumäärä on A 7.

Silloin joukkojen kokonaismäärä on B 7 + C 7 + D 7 = 127+127+1 = 255

Vastaus: 255

Kunnan budjettikoulutuslaitos

"Yliopisto nro 18"

Salavatin kaupungin kaupunkialue Bashkortostanin tasavallassa

Loogiset yhtälöt

in Unified State Examination ongelmia tietojenkäsittelytieteen

Yhtenäisen valtiontutkinnon tehtävien osiota "Logiikkaalgebran perusteet" pidetään yhtenä vaikeimmista ja vaikeimmin ratkaistavista. Aiheeseen liittyvien tehtävien keskimääräinen prosenttiosuus on alhaisin ja on 43,2.

Vuoden 2018 KIM-spesifikaatioon perustuen tämä lohko sisältää neljä eri vaikeustasoa olevaa tehtävää.

Tehtävä 23 on vaikeudeltaan korkea, joten sen suorittamisprosentti on alhaisin. Valmistuneista (81-100 pistettä) suoritti tehtävän 49,8 %, kohtalaisen valmistautuneista (61-80 pistettä) 13,7 %, loput opiskelijat eivät suorittaneet tätä tehtävää.

Loogisen yhtälöjärjestelmän ratkaisemisen onnistuminen riippuu logiikan lakien tuntemisesta ja järjestelmän ratkaisumenetelmien tarkasta soveltamisesta.

Harkitsemme loogisen yhtälöjärjestelmän ratkaisemista kartoitusmenetelmällä.

(23.154 Polyakov K.Yu.) Kuinka monta erilaista ratkaisua yhtälöjärjestelmällä on?

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

Missä x1 , x2 ,…, x8, klo1 ,y2 ,…,y8 - loogisia muuttujia? Vastauksen ei tarvitse luetella kaikkia erilaisia ​​muuttujien arvoja, joille tämä yhtäläisyys pätee. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu. Kaikki järjestelmään sisältyvät yhtälöt ovat samantyyppisiä, ja jokainen yhtälö sisältää neljä muuttujaa. Kun tiedämme x1 ja y1, voimme löytää kaikki mahdolliset x2:n ja y2:n arvot, jotka täyttävät ensimmäisen yhtälön. Samalla tavalla päätellen tunnetuista x2:sta ja y2:sta voimme löytää x3, y3, jotka tyydyttävät toisen yhtälön. Eli kun tiedämme parin (x1, y1) ja määritämme parin (x2, y2) arvon, löydämme parin (x3, y3), joka puolestaan ​​johtaa pariin (x4, y4) ja niin edelleen.

Etsitään kaikki ratkaisut ensimmäiseen yhtälöön. Tämä voidaan tehdä kahdella tavalla: rakentaa totuustaulukko perustelemalla ja soveltamalla logiikan lakeja.

Totuustaulukko:

Totuustaulukon rakentaminen on työlästä ja aikaavievää, joten käytämme toista menetelmää - loogista päättelyä. Tulo on yhtä suuri kuin 1, jos ja vain jos jokainen tekijä on yhtä suuri kuin 1.

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

(x1  x2 ) =1

(y1  y2 ) =1

Katsotaanpa ensimmäistä yhtälöä. Seuraus on yhtä suuri kuin 1, kun 0 0, 0 1, 1 1, mikä tarkoittaa (x1 y1)=0 arvoille (01), (10), sitten pari (x2  y2 ) voi olla mikä tahansa (00), (01), (10), (11), ja kun (x1 y1) = 1, eli (00) ja (11) pari (x2 y2) = 1 ottaa samat arvot (00) ja (11). Jätetään tästä ratkaisusta pois ne parit, joiden toinen ja kolmas yhtälö ovat vääriä eli x1=1, x2=0, y1=1, y2=0.

Parien kokonaismäärä 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Kuinka monta erilaista ratkaisua loogisella yhtälöjärjestelmällä on?

(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

Ratkaisu. 1) Yhtälöt ovat samaa tyyppiä, joten päättelyn avulla löydämme ensimmäisen yhtälön kaikki mahdolliset parit (x1,y1), (x2,y2).

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Toisen yhtälön ratkaisu on parit (00), (01), (11).

Etsitään ratkaisuja ensimmäiseen yhtälöön. Jos x1=0, niin x2, y2 - mikä tahansa, jos x1=1, niin x2, y2 saa arvon (11).

Tehdään yhteydet parien (x1, y1) ja (x2, y2) välille.

Luodaan taulukko parien lukumäärän laskemiseksi kussakin vaiheessa.

Ottaen huomioon viimeisen yhtälön ratkaisut x 7  y 7 = 1, jätetään pois pari (10). Etsi ratkaisujen kokonaismäärä 1+7+0+34=42

3)(23.180) Kuinka monta eri ratkaisua loogisella yhtälöjärjestelmällä on?

(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

Ratkaisu. 1) Yhtälöt ovat samantyyppisiä, joten päättelyn avulla löydämme ensimmäisen yhtälön kaikki mahdolliset parit (x1,x2), (x3,x4).

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

Jätetään ratkaisusta pois parit, jotka jonossa antavat 0 (1 0), nämä ovat parit (01, 00, 11) ja (10).

Tehdään yhteydet parien välille (x1,x2), (x3,x4)

Ohjeet. Kun syötät näppäimistöltä, käytä seuraavia käytäntöjä:

Säännöt loogisen funktion syöttämiseksi

1. Käytä v-symbolin (disjunktio, OR) sijasta +-merkkiä.
2. Ennen loogista funktiota ei tarvitse määrittää funktion nimeä. Esimerkiksi F(x,y)=(x|y)=(x^y) sijaan sinun on yksinkertaisesti syötettävä (x|y)=(x^y) .
3. Muuttujien enimmäismäärä on 10.

Tietokonelogiikkapiirien suunnittelu ja analysointi suoritetaan käyttämällä erityistä matematiikan haaraa - logiikkaalgebraa. Logiikkaalgebrassa voidaan erottaa kolme pääasiallista loogista funktiota: "EI" (negaatio), "AND" (konjunktio), "OR" (disjunktio).
Minkä tahansa loogisen laitteen luomiseksi on tarpeen määrittää kunkin lähtömuuttujan riippuvuus olemassa olevista tulomuuttujista; tätä riippuvuutta kutsutaan kytkentäfunktioksi tai loogiseksi algebrafunktioksi.
Loogista algebrafunktiota kutsutaan täysin määritellyksi, jos sen kaikki 2n arvoa on annettu, missä n on lähtömuuttujien lukumäärä.
Jos kaikkia arvoja ei ole määritetty, funktiota kutsutaan osittain määritetyksi.
Laitetta kutsutaan loogiseksi, jos sen tilaa kuvataan logiikkaalgebrafunktiolla.
Seuraavia menetelmiä käytetään esittämään loogista algebrafunktiota:
Algebrallisessa muodossa voit rakentaa loogisen laitteen piirin loogisten elementtien avulla.


Kuva 1 - Logiikkalaitekaavio

Kaikki logiikan algebran toiminnot on määritelty totuustaulukot arvot. Totuustaulukko määrittää toiminnon tuloksen for kaikki ovat mahdollisia x alkuperäisten lauseiden loogiset arvot. Käyttötoimintojen tulosta heijastavien vaihtoehtojen määrä riippuu loogisen lausekkeen lauseiden määrästä. Jos lausekkeiden määrä loogisessa lausekkeessa on N, niin totuustaulukko sisältää 2 N riviä, koska mahdollisia argumenttiarvoja on 2 N erilaista yhdistelmää.

Operaatio NOT - looginen negaatio (inversio)

• jos alkuperäinen lauseke on tosi, sen negatiivisen tuloksen tulos on epätosi;
• jos alkuperäinen lauseke on epätosi, niin sen negatiivisen tuloksen tulos on tosi.

TAI-operaatio - looginen summaus (disjunktio, liitto)

Operaatio AND - looginen kertolasku (konjunktio)

Operaatio "JOS-SIIN" - looginen seuraus (implikaatio)

Operaatio "A jos ja vain jos B" (ekvivalenssi, vastaavuus)

Operaatio "Addition modulo 2" (XOR, yksinoikeus tai tiukka disjunktio)

Loogisten operaatioiden prioriteetti

• Toiminnot suluissa
• Inversio
• Konjunktio (&)
• Disjunktio (V), yksinomainen TAI (XOR), summa modulo 2
• Implisaatio (→)
• Vastaavuus (↔)

Täydellinen disjunktiivinen normaalimuoto

1. Jokainen kaavan looginen termi sisältää kaikki funktioon F(x 1,x 2,...x n) sisältyvät muuttujat.
2. Kaikki kaavan loogiset termit ovat erilaisia.
3. Yksikään looginen termi ei sisällä muuttujaa ja sen negaatiota.
4. Mikään kaavan looginen termi ei sisällä samaa muuttujaa kahdesti.

Täydellinen konjunktiivinen normaalimuoto

1. Kaikki alkeisdisjunktiot sisältävät kaikki funktioon F(x 1 ,x 2 ,...x n) sisältyvät muuttujat.
2. Kaikki alkeisdisjunktiot ovat erilaisia.
3. Jokainen alkeisdisjunktio sisältää muuttujan kerran.
4. Yksikään alkeisdisjunktio ei sisällä muuttujaa ja sen negaatiota.

Menetelmiä loogisten yhtälöjärjestelmien ratkaisemiseksi

Voit ratkaista loogisen yhtälöjärjestelmän esimerkiksi käyttämällä totuustaulukkoa (jos muuttujien määrä ei ole liian suuri) tai käyttämällä päätöspuuta yksinkertaistamalla ensin jokaista yhtälöä.

1. Muuttuva korvausmenetelmä.

Uusien muuttujien käyttöönoton avulla voit yksinkertaistaa yhtälöjärjestelmää ja vähentää tuntemattomien määrää.Uusien muuttujien on oltava toisistaan ​​riippumattomia. Kun yksinkertaistettu järjestelmä on ratkaistu, meidän on palattava alkuperäisiin muuttujiin.

Tarkastellaan tämän menetelmän soveltamista tietyn esimerkin avulla.

Esimerkki.

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

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

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

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

Ratkaisu:

Otetaan käyttöön uudet muuttujat: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Huomio! Jokainen muuttuja x1, x2, ..., x10 tulee sisällyttää vain yhteen uusiin muuttujiin A, B, C, D, E, eli uudet muuttujat ovat toisistaan ​​riippumattomia).

Sitten yhtälöjärjestelmä näyttää tältä:

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

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

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

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

Rakennetaan päätöspuu tuloksena olevalle järjestelmälle:

Tarkastellaan yhtälöä A=0, ts. (X1≡ X2) = 0. Sillä on 2 juurta:

Samasta taulukosta voidaan nähdä, että yhtälöllä A=1 on myös 2 juuria. Järjestetään juurten lukumäärä päätöspuussa:

Yhden haaran ratkaisujen lukumäärän selvittämiseksi sinun on kerrottava kunkin tason ratkaisujen määrä. Vasemmassa haarassa on 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 32 liuosta; oikealla haaralla on myös 32 ratkaisua. Nuo. koko järjestelmässä on 32+32=64 ratkaisua.

Vastaus: 64.

2. Päättelytapa.

Loogisten yhtälöjärjestelmien ratkaisemisen vaikeus piilee täydellisen päätöspuun kömpelyydestä. Päättelymenetelmän avulla voit olla rakentamatta koko puuta, vaan ymmärtää kuinka monta oksaa sillä on. Tarkastellaan tätä menetelmää erityisten esimerkkien avulla.

Esimerkki 1. Kuinka monta erilaista arvojoukkoa loogisilla muuttujilla x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 on olemassa, jotka täyttävät kaikki alla luetellut ehdot?

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

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

x1\/y1 =1

Vastauksen ei tarvitse luetella kaikkia muuttujien x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 erilaisia ​​arvojoukkoja, joille tämä yhtäläisyysjärjestelmä täyttyy. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu :

Ensimmäinen ja toinen yhtälö sisältävät riippumattomia muuttujia, jotka liittyvät kolmannelle ehdolle. Rakennetaan ratkaisupuu ensimmäiselle ja toiselle yhtälölle.

Ensimmäisen ja toisen yhtälön järjestelmän ratkaisupuun esittämiseksi ensimmäisen puun jokaista haaraa on jatkettava muuttujien puulla klo . Tällä tavalla rakennettu puu sisältää 36 oksaa. Jotkut näistä haaroista eivät täytä järjestelmän kolmatta yhtälöä. Merkitään ensimmäiseen puuhun puun oksien lukumäärä"y" , jotka täyttävät kolmannen yhtälön:

Selitetään: kolmannen ehdon täyttymiseksi, kun x1=0, täytyy olla y1=1 eli kaikki puun oksat"X" , jossa x1=0 voidaan jatkaa vain yhdellä oksalla puusta"y" . Ja vain yhdelle puun oksalle"X" (oikealla) kaikki puun oksat sopivat"y". Siten koko järjestelmän täydellinen puu sisältää 11 haaraa. Jokainen haara edustaa yhtä ratkaisua alkuperäiseen yhtälöjärjestelmään. Tämä tarkoittaa, että koko järjestelmässä on 11 ratkaisua.

Vastaus: 11.

Esimerkki 2. Kuinka monta erilaista ratkaisua yhtälöjärjestelmällä on?

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

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

………………

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

(X1 ≡ X10) = 0

missä x1, x2, …, x10 ovat loogisia muuttujia? Vastauksen ei tarvitse luetella kaikkia erilaisia ​​muuttujien arvoja, joille tämä yhtäläisyys pätee. Vastauksena sinun on ilmoitettava tällaisten sarjojen lukumäärä.

Ratkaisu : Yksinkertaistetaan järjestelmää. Rakennetaan totuustaulukko osalle ensimmäistä yhtälöä:

Kiinnitä huomiota viimeiseen sarakkeeseen, se vastaa toiminnon tulosta X1 ≡ X10.

Yksinkertaistamisen jälkeen saamme:

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

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

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

……

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

(X1 ≡ X10) = 0

Harkitse viimeistä yhtälöä:(X1 ≡ X10) = 0, so. x1 ei saa olla sama kuin x10. Jotta ensimmäinen yhtälö olisi yhtä suuri kuin 1, yhtälön on oltava tosi(X1 ≡ X2) = 1, so. x1 on vastattava x2:ta.

Rakennetaan ratkaisupuu ensimmäiselle yhtälölle:

Tarkastellaan toista yhtälöä: x10=1 ja x2=0 sulkumerkkion oltava yhtä suuri kuin 1 (eli x2 on sama kuin x3); x10=0 ja x2=1 hakasulke(X2 ≡ X10) = 0, mikä tarkoittaa hakasulkua (X2 ≡ X3) pitäisi olla yhtä suuri kuin 1 (eli x2 on sama kuin x3):

Tällä tavalla päätellen rakennamme päätöspuun kaikille yhtälöille:

Siten yhtälöjärjestelmällä on vain 2 ratkaisua.

Vastaus: 2.

Esimerkki 3.

Kuinka monta erilaista loogisten muuttujien x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 arvojoukkoa on olemassa, jotka täyttävät kaikki alla luetellut ehdot?

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

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

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

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

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

Ratkaisu:

Rakennetaan ratkaisupuu 1. yhtälöön:

Harkitse toista yhtälöä:

• Kun x1 = 0 : toinen ja kolmas hakasulku ovat yhtä kuin 0; jotta ensimmäinen hakasulke olisi yhtä suuri kuin 1, y1=1, z1=1 (eli tässä tapauksessa - 1 ratkaisu)
• Kun x1=1 : ensimmäinen hakasulke on 0; toinen tai kolmannen sulkumerkin on oltava yhtä suuri kuin 1; toinen hakasulke on yhtä suuri kuin 1, kun y1 = 0 ja z1 = 1; kolmas hakasulke on 1, kun y1=1 ja z1=0 (eli tässä tapauksessa - 2 ratkaisua).

Sama koskee muita yhtälöitä. Merkitään jokaiselle puusolmulle saatu ratkaisumäärä:

Saat selville kunkin haaran ratkaisujen lukumäärän kertomalla saadut luvut jokaiselle haaralle erikseen (vasemmalta oikealle).

1 haara: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 ratkaisu

Haara 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 ratkaisua

3. haara: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 ratkaisua

4. haara: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 ratkaisua

5. haara: 2 ⋅ 2 ⋅ 2 ⋅ 2 = 16 ratkaisua

Lasketaan yhteen saadut luvut: ratkaisuja on yhteensä 31.

Vastaus: 31.

3. Juurien määrän luonnollinen kasvu

Joissakin järjestelmissä seuraavan yhtälön juurien lukumäärä riippuu edellisen yhtälön juurien lukumäärästä.

Esimerkki 1. Kuinka monta erilaista arvojoukkoa loogisilla muuttujilla x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 on olemassa, jotka täyttävät kaikki alla luetellut ehdot?

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

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

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

Yksinkertaistetaan ensimmäinen yhtälö:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Sitten järjestelmä saa muodon:

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

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

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

Jne.

Jokaisella seuraavalla yhtälöllä on 2 juurta enemmän kuin edellisellä.

4 yhtälöllä on 12 juuria;

Yhtälöllä 5 on 14 juuria

Yhtälöllä 8 on 20 juurta.

Vastaus: 20 juurta.

Joskus juurten määrä kasvaa Fibonaccin lain mukaan.

Loogisen yhtälöjärjestelmän ratkaiseminen vaatii luovaa lähestymistapaa.