Hvordan løse logiske formler. Systemer av logiske ligninger i oppgavene til eksamen i informatikk

Bruken av ligninger er utbredt i våre liv. De brukes i mange beregninger, konstruksjon av strukturer og til og med sport. Ligninger har blitt brukt av mennesker siden antikken og siden har bruken bare økt. I matematikk er det visse oppgaver som er viet til logikken til proposisjoner. For å løse denne typen ligninger, må du ha en viss mengde kunnskap: kunnskap om lover for proposisjonell logikk, kunnskap om sannhetstabellene for logiske funksjoner av 1 eller 2 variabler, metoder for å transformere logiske uttrykk. I tillegg må du kjenne til følgende egenskaper ved logiske operasjoner: konjunksjoner, disjunksjoner, inversjoner, implikasjoner og ekvivalenser.

Enhver logisk funksjon fra \ variabler - \ kan spesifiseres av en sannhetstabell.

La oss løse noen logiske ligninger:

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

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

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

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

La oss starte løsningen med \[X1\] og bestemme hvilke verdier\u200b\u200bdenne variabelen kan ta: 0 og 1. Deretter vurderer du hver av verdiene ovenfor \u200b\u200 og se hva \[X2.\] kan være i dette tilfellet

Som det fremgår av tabellen, har vår logiske ligning 11 løsninger.

Hvor kan jeg løse en logisk ligning på nettet?

Du kan løse ligningen på vår nettside https: // site. Gratis online løser lar deg løse en online ligning av enhver kompleksitet på sekunder. Alt du trenger å gjøre er å legge inn dataene dine i løseren. Du kan også se videoinstruksjonen og lære hvordan du løser ligningen på nettsiden vår. Og hvis du har spørsmål, kan du stille dem i vår Vkontakte-gruppe http://vk.com/pocketteacher. Bli med i gruppen vår, vi er alltid glade for å hjelpe deg.

Løse systemer av logiske ligninger ved å endre variabler

Metoden for endring av variabler brukes hvis noen variabler er inkludert i ligningene kun i form av et spesifikt uttrykk, og ingenting annet. Da kan dette uttrykket betegnes med en ny variabel.

Eksempel 1

Hvor mange forskjellige sett med verdier av logiske variabler x1, x2, x3, x4, x5, x6, x7, x8 er det som tilfredsstiller alle følgende betingelser?

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

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

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

Svaret trenger ikke å liste opp alle de forskjellige settene med verdier av variablene x1, x2, x3, x4, x5, x6, x7, x8, der det gitte likhetssystemet er oppfylt. Som svar må du angi antall slike sett.

Løsning:

(xl -> x2) = yl; (x3 -> x4) = y2; (x5 -> x6) = y3; (x7 → x8) = y4.

Da kan systemet skrives som en enkelt ligning:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunksjonen er 1 (sann) når hver operand evalueres til 1. Det vil si, hver av implikasjonene må være sanne, og dette gjelder for alle verdier unntatt (1 → 0). De. i tabellen med verdier for variablene y1, y2, y3, y4, må enheten ikke være til venstre for null:

De. betingelsene er oppfylt for 5 sett y1-y4.

Fordi y1 = x1 → x2, så oppnås verdien y1 = 0 på et enkelt sett x1, x2: (1, 0), og verdien y1 = 1 oppnås på tre sett x1, x2: (0,0) , ( 0,1), (1,1). Tilsvarende for y2, y3, y4.

Siden hvert sett (x1,x2) for variabel y1 er kombinert med hvert sett (x3,x4) for variabel y2, og så videre, multipliseres antall sett med variabler x:

La oss legge til antall sett: 1 + 3 + 9 + 27 + 81 = 121.

Svar: 121

Eksempel 2

Hvor mange forskjellige sett med verdier av boolske variabler x1, x2, ... x9, y1, y2, ... y9 er det som tilfredsstiller alle følgende betingelser?

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

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

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

Som svar ikke nødvendig liste opp alle forskjellige sett med verdier av variablene x1, x2, ... x9, y1, y2, ... y9, der det gitte likhetssystemet er oppfylt. Som svar må du angi antall slike sett.

Løsning:

La oss gjøre en endring av variabler:

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

Systemet kan skrives som en enkelt ligning:

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

Ekvivalens er sann bare hvis begge operandene er like. Løsningene til denne ligningen vil være to sett:

Fordi zi = (xi ≡ yi), så tilsvarer verdien zi = 0 to sett (xi,yi): (0,1) og (1,0), og verdien zi = 1 tilsvarer to sett (xi,yi) ): (0,0) og (1,1).

Da tilsvarer det første settet z1, z2,..., z9 2 9 sett (x1,y1), (x2,y2),..., (x9,y9).

Det samme tallet tilsvarer det andre settet z1, z2,..., z9. Da er det 2 9 +2 9 = 1024 sett totalt.

Svar: 1024

Løse systemer av logiske ligninger ved visuell definisjon av rekursjon.

Denne metoden brukes hvis ligningssystemet er enkelt nok og rekkefølgen for å øke antall sett ved å legge til variabler er åpenbar.

Eksempel 3

Hvor mange ulike løsninger har ligningssystemet

¬x9 ∨ x10 = 1,

hvor x1, x2, ... x10 er boolske variabler?

Svaret trenger ikke å telle opp alle de forskjellige settene med verdier x1, x2, ... x10 som det gitte likhetssystemet gjelder for. Som svar må du angi antall slike sett.

Løsning:

La oss løse den første ligningen. En disjunksjon er lik 1 hvis minst en av operandene er lik 1. Det vil si, løsningene er settene:

For x1=0 er det to x2-verdier (0 og 1), og for x1=1 er det bare én x2-verdi (1), slik at mengden (x1,x2) er løsningen på ligningen. Kun 3 sett.

La oss legge til variabelen x3 og vurdere den andre ligningen. Den ligner på den første, noe som betyr at for x2=0 er det to verdier av x3 (0 og 1), og for x2=1 er det bare én verdi av x3 (1), slik at settet ( x2,x3) er en løsning på ligningen. Det er 4 sett totalt.

Det er lett å se at når du legger til en annen variabel, blir ett sett lagt til. De. rekursiv formel for antall sett på (i+1) variabler:

N i +1 = N i + 1. Så for ti variabler får vi 11 sett.

Svar: 11

Løse systemer av logiske ligninger av ulike typer

Eksempel 4

Hvor mange forskjellige sett med verdier av boolske variabler x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 er det som tilfredsstiller alle de følgende betingelsene?

(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

Som svar ikke nødvendig liste opp alle forskjellige sett med verdier av variablene x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , der det gitte likhetssystemet er tilfredsstilt .

Som svar må du angi antall slike sett.

Løsning:

Merk at de tre likningene i systemet er de samme på forskjellige uavhengige sett med variabler.

Tenk på den første ligningen. En konjunksjon er sann (lik 1) bare hvis alle operandene er sanne (lik 1). Implikasjonen er 1 på alle sett unntatt (1,0). Dette betyr at løsningen på den første ligningen vil være slike sett x1, x2, x3, x4, der 1 ikke er til venstre for 0 (5 sett):

På samme måte vil løsningene av den andre og tredje ligningen være nøyaktig de samme settene av y1,…,y4 og z1,…,z4.

La oss nå analysere systemets fjerde likning: x 4 ∧ y 4 ∧ z 4 = 0. Løsningen vil være alle sett x4, y4, z4 der minst én av variablene er lik 0.

De. for x4 = 0 er alle mulige sett (y4, z4) egnet, og for x4 = 1 er sett (y4, z4) som inneholder minst én null egnet: (0, 0), (0,1) , ( 1, 0).

Det totale antallet sett er 25 + 4*9 = 25 + 36 = 61.

Svar: 61

Løse systemer med logiske ligninger ved å konstruere tilbakevendende formler

Metoden for å konstruere tilbakevendende formler brukes til å løse komplekse systemer der rekkefølgen for å øke antall sett ikke er åpenbar, og det er umulig å bygge et tre på grunn av volumer.

Eksempel 5

Hvor mange forskjellige sett med verdier av boolske variabler x1, x2, ... x7, y1, y2, ... y7 er det som tilfredsstiller alle følgende betingelser?

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

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

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

Svaret trenger ikke å liste opp alle de forskjellige settene med verdier av variablene x1, x2, ..., x7, y1, y2, ..., y7, som det gitte likhetssystemet gjelder. Som svar må du angi antall slike sett.

Løsning:

Legg merke til at de første seks ligningene i systemet er de samme og skiller seg bare i settet med variabler. Tenk på den første ligningen. Løsningen vil være følgende sett med variabler:

Betegn:

antall sett (0,0) på variabler (x1,y1) til A 1 ,

antall sett (0,1) på variabler (x1,y1) til og med B 1 ,

antall sett (1,0) på variabler (x1,y1) via C 1 ,

antall sett (1,1) på variabler (x1,y1) via D 1 .

antall sett (0,0) på variabler (x2,y2) til og med A 2 ,

antall sett (0,1) på variabler (x2,y2) via B 2 ,

antall sett (1,0) på variabler (x2,y2) via C 2 ,

antall sett (1,1) på variabler (x2,y2) via D 2 .

Fra beslutningstreet ser vi det

A1=0, B1=1, C1=1, D1=1.

Merk at tuppelen (0,0) på variablene (x2,y2) er hentet fra tuppelene (0,1), (1,0) og (1,1) på variablene (x1,y1). De. A 2 \u003d B 1 + C 1 + D 1.

Settet (0,1) på variablene (x2,y2) er hentet fra settene (0,1), (1,0) og (1,1) på variablene (x1,y1). De. B 2 \u003d B 1 + C 1 + D 1.

Ved å argumentere på samme måte merker vi at C 2 = B 1 + C 1 + D 1. D2 = D1.

Dermed får vi rekursive formler:

A i+1 = Bi + Ci + D i

Bi+1 = Bi + Ci + Di

Ci+1 = Bi + Ci + Di

Di+1 = A i + Bi + Ci + D i

La oss lage et bord

Den siste ligningen (x7 ∨ y7) = 1 er tilfredsstilt av alle sett unntatt de der x7=0 og y7=0. I vår tabell er antallet slike sett A 7 .

Da er det totale antallet sett B 7 + C 7 + D 7 = 127+127+1 = 255

Svar: 255

Kommunal budsjettutdanningsinstitusjon

"Ungdomsskole nr. 18"

bydistrikt i byen Salavat i republikken Bashkortostan

Systemer av logiske ligninger

i oppgavene til eksamen i informatikk

Avsnittet "Fundamentals of Algebra of Logic" i oppgavene til eksamen regnes som en av de vanskeligste og dårligst løste. Gjennomsnittlig prosentandel av å fullføre oppgaver om dette emnet er den laveste og er 43,2.

Basert på spesifikasjonen til KIM 2018, inkluderer denne blokken fire oppgaver med ulike nivåer av kompleksitet.

Oppgave 23 er en høy vanskelighetsgrad, derfor har den den laveste fullføringsprosenten. Blant de trente kandidatene (81-100 poeng) fullførte 49,8% oppgaven, de gjennomsnittlig forberedte (61-80 poeng) takler 13,7%, den gjenværende elevgruppen fullfører ikke denne oppgaven.

Suksessen til å løse et system med logiske ligninger avhenger av kunnskapen om logikkens lover og av den nøyaktige anvendelsen av metoder for å løse systemet.

Vurder løsningen av et system med logiske ligninger ved hjelp av kartleggingsmetoden.

(23.154 Polyakov K.Yu.) Hvor mange forskjellige løsninger har ligningssystemet?

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

Hvor x1 , x2 ,…, x8, på1 ,y2 ,…,y8 - Boolske variabler? Svaret trenger ikke å liste opp alle de forskjellige settene med variabelverdier som denne likheten gjelder. Som svar må du angi antall slike sett.

Løsning. Alle likninger som inngår i systemet er av samme type, og fire variabler er inkludert i hver likning. Når vi kjenner x1 og y1, kan vi finne alle mulige verdier av x2 og y2 som tilfredsstiller den første ligningen. Ved å argumentere på en lignende måte, fra de kjente x2 og y2 kan vi finne x3, y3 som tilfredsstiller den andre ligningen. Det vil si at når vi kjenner paret (x1 , y1) og bestemmer verdien av paret (x2 , y2), vil vi finne paret (x3 , y3 ), som igjen vil føre til paret (x4 , y4 ) og så på.

La oss finne alle løsningene til den første ligningen. Dette kan gjøres på to måter: å bygge en sannhetstabell, gjennom resonnement og anvendelse av logikkens lover.

Sannhetstabell:

Å bygge en sannhetstabell er arbeidskrevende og tidsineffektivt, så vi bruker den andre metoden - logisk resonnement. Produktet er 1 hvis og bare hvis hver faktor er 1.

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

(x1  x2 ) =1

(y1  y2 ) =1

Tenk på den første ligningen. Følgende er lik 1, når 0 0, 0 1, 1 1, så (x1 y1)=0 ved (01), (10), så paret (x2  y2 ) kan være hvilken som helst (00), (01), (10), (11), og for (x1 y1)=1, dvs. (00) og (11) tar paret (x2 y2)=1 de samme verdiene (00) og (11). Vi ekskluderer fra denne løsningen de parene der den andre og tredje ligningen er usanne, det vil si x1=1, x2=0, y1=1, y2=0.

Totalt antall par 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Hvor mange forskjellige løsninger har et system med logiske ligninger

(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

Løsning. 1) Ligningene er av samme type, så ved resonnementmetoden vil vi finne alle mulige par (x1,y1), (x2,y2) av den første ligningen.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Løsningen til den andre ligningen er par (00), (01), (11).

La oss finne løsninger på den første ligningen. Hvis x1=0, så tar x2, y2 - hvilken som helst, hvis x1=1, så tar x2, y2 verdien (11).

La oss lage koblinger mellom par (x1 , y1) og (x2 , y2).

La oss lage en tabell for å beregne antall par på hvert trinn.

Ta hensyn til løsningene til den siste ligningen x 7  y 7 = 1, vi eliminerer paret (10). Finn det totale antallet løsninger 1+7+0+34=42

3)(23.180) Hvor mange ulike løsninger har systemet med logiske ligninger

(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

Løsning. 1) Ligningene er av samme type, så ved resonneringsmetoden vil vi finne alle mulige par (x1,x2), (x3,x4) av den første ligningen.

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

Vi ekskluderer fra løsningen parene som gir 0 (1 0) i det følgende, dette er parene (01, 00, 11) og (10).

Lag lenker mellom par (x1,x2), (x3,x4)

Instruksjon. Når du går inn fra tastaturet, bruk følgende konvensjoner:

Logiske funksjonsinndataregler

1. Bruk +-tegnet i stedet for v (disjunksjon, ELLER).
2. Før den logiske funksjonen trenger du ikke spesifisere funksjonsbetegnelsen. For eksempel, i stedet for F(x,y)=(x|y)=(x^y) skriver du ganske enkelt (x|y)=(x^y) .
3. Maksimalt antall variabler er 10 .

Design og analyse av datalogiske kretser utføres ved hjelp av en spesiell seksjon av matematikk - logikkens algebra. I logikkens algebra kan tre logiske hovedfunksjoner skilles: "IKKE" (negasjon), "AND" (konjunksjon), "ELLER" (disjunksjon).
For å lage en hvilken som helst logisk enhet, er det nødvendig å bestemme avhengigheten til hver av utgangsvariablene på gjeldende inngangsvariabler, en slik avhengighet kalles en svitsjfunksjon eller en funksjon av den logiske algebraen.
En logisk algebrafunksjon kalles fullt definert hvis alle 2 n av verdiene er gitt, hvor n er antall utdatavariabler.
Hvis ikke alle verdier er definert, kalles funksjonen delvis definert.
En enhet kalles logisk hvis tilstanden er beskrevet ved hjelp av en funksjon av logikkens algebra.
Følgende metoder brukes til å representere den logiske algebrafunksjonen:
I algebraisk form er det mulig å konstruere et diagram av en logisk enhet ved hjelp av logiske elementer.


Figur 1 - Diagram av en logisk enhet

Alle operasjoner av logikkens algebra er definert sannhetstabeller verdier. Sannhetstabellen bestemmer resultatet av å utføre en operasjon for alt mulig x logiske verdier av de originale utsagnene. Antallet alternativer som gjenspeiler resultatet av å bruke operasjonene vil avhenge av antall utsagn i det logiske uttrykket. Hvis antallet utsagn i det logiske uttrykket er N, vil sannhetstabellen inneholde 2 N rader, siden det er 2 N forskjellige kombinasjoner av mulige argumentverdier.

Operasjon NOT - logisk negasjon (inversjon)

• hvis det opprinnelige uttrykket er sant, vil resultatet av dets negasjon være usant;
• hvis det opprinnelige uttrykket er usant, vil resultatet av dets negasjon være sant.

Operasjon ELLER - logisk tillegg (disjunksjon, forening)

Operasjon OG - logisk multiplikasjon (konjunksjon)

Operasjon "HVIS-SÅ" - logisk konsekvens (implikasjon)

Operasjon "A hvis og bare hvis B" (ekvivalens, ekvivalens)

Modulo 2 addisjonsoperasjon (XOR, eksklusiv eller, streng disjunksjon)

Forrang for logiske operasjoner

• Handlinger i parentes
• Inversjon
• Konjunksjon (&)
• Disjunksjon (V), Eksklusiv ELLER (XOR), modulo 2 sum
• Implikasjon (→)
• Ekvivalens (↔)

Perfekt disjunktiv normalform

1. Hvert logiske ledd i formelen inneholder alle variablene som er inkludert i funksjonen F(x 1 ,x 2 ,...x n).
2. Alle logiske termer i formelen er forskjellige.
3. Ingen logisk term inneholder en variabel og dens negasjon.
4. Ingen logisk term i en formel inneholder den samme variabelen to ganger.

Perfekt konjunktiv normalform

1. Alle elementære disjunksjoner inneholder alle variabler som inngår i funksjonen F(x 1 ,x 2 ,...x n).
2. Alle elementære disjunksjoner er forskjellige.
3. Hver elementær disjunksjon inneholder en variabel én gang.
4. Ingen elementær disjunksjon inneholder en variabel og dens negasjon.

Metoder for å løse systemer av logiske ligninger

Du kan løse et system med logiske ligninger, for eksempel ved å bruke en sannhetstabell (hvis antallet variabler ikke er for stort) eller ved å bruke et beslutningstre, etter å ha forenklet hver ligning.

1. Metode for endring av variabler.

Innføringen av nye variabler gjør det mulig å forenkle ligningssystemet ved å redusere antall ukjente.Nye variabler må være uavhengige av hverandre. Etter å ha løst det forenklede systemet, er det nødvendig å gå tilbake til de opprinnelige variablene igjen.

Vurder bruken av denne metoden på et spesifikt eksempel.

Eksempel.

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

Løsning:

La oss introdusere nye variabler: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Obs! Hver av deres variabler x1, x2, ..., x10 må inkluderes i bare én av de nye variablene A, B, C, D, E, dvs. de nye variablene er uavhengige av hverandre).

Da vil ligningssystemet se slik ut:

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

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

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

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

La oss bygge et beslutningstre for det resulterende systemet:

Tenk på ligningen A=0, dvs. (X1≡ X2)=0. Den har 2 røtter:

Fra samme tabell kan man se at ligningen A \u003d 1 også har 2 røtter. La oss ordne antall røtter på beslutningstreet:

For å finne antall løsninger for en gren, må du multiplisere antall løsninger på hvert nivå. Venstre gren har 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 løsninger; høyre gren har også 32 løsninger. De. hele systemet har 32+32=64 løsninger.

Svar: 64.

2. Metode for resonnement.

Kompleksiteten ved å løse systemer med logiske ligninger ligger i omfanget av det komplette beslutningstreet. Resonneringsmetoden lar deg ikke bygge hele treet helt, men samtidig forstå hvor mange grener det vil ha. La oss vurdere denne metoden på spesifikke eksempler.

Eksempel 1 Hvor mange forskjellige sett med verdier av boolske variabler x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 er det som tilfredsstiller alle følgende betingelser?

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

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

x1\/y1 =1

Svaret trenger ikke å liste opp alle de forskjellige settene med verdier av variablene x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 der det gitte likhetssystemet er oppfylt. Som svar må du angi antall slike sett.

Løsning :

Den første og andre ligningen inneholder uavhengige variabler som er relatert til en tredje betingelse. La oss konstruere et beslutningstre for den første og andre ligningen.

For å representere beslutningstreet til systemet fra den første og andre ligningen, er det nødvendig å fortsette hver gren av det første treet med et tre for variabler på . Treet konstruert på denne måten vil inneholde 36 greiner. Noen av disse grenene tilfredsstiller ikke den tredje ligningen i systemet. Merk på det første treet antall grener på treet"på" , som tilfredsstiller den tredje ligningen:

La oss presisere: for oppfyllelsen av den tredje betingelsen ved x1=0 må det være y1=1, dvs. alle grener av treet"X" , hvor x1=0 kan fortsettes med bare én gren fra treet"på" . Og bare for en gren av treet"X" (til høyre) passer alle grener på treet"på". Dermed inneholder hele treet i hele systemet 11 grener. Hver gren representerer én løsning til det opprinnelige ligningssystemet. Så hele systemet har 11 løsninger.

Svar: 11.

Eksempel 2 Hvor mange ulike løsninger har ligningssystemet

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

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

………………

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

(X1 ≡ X10) = 0

hvor x1, x2, …, x10 er boolske variabler? Svaret trenger ikke å liste opp alle de forskjellige settene med variabelverdier som denne likheten gjelder. Som svar må du angi antall slike sett.

Løsning : La oss forenkle systemet. La oss bygge en sannhetstabell for delen av den første ligningen:

Vær oppmerksom på den siste kolonnen, den samsvarer med resultatet av handlingen X1 ≡ X10.

Etter forenkling får vi:

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

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

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

……

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

(X1 ≡ X10) = 0

Tenk på den siste ligningen:(X1 ≡ X10) = 0, dvs. x1 skal ikke være det samme som x10. For at den første ligningen skal være lik 1, må likheten holde(X1 ≡ X2)=1, dvs. x1 må samsvare med x2.

La oss bygge et beslutningstre for den første ligningen:

Tenk på den andre ligningen: for x10=1 og for x2=0 parentesenmå være lik 1 (dvs. x2 er det samme som x3); ved x10=0 og ved x2=1 parentes(X2 ≡ X10)=0 , så brakett (X2 ≡ X3) må være lik 1 (dvs. x2 er det samme som x3):

Ved å argumentere på denne måten konstruerer vi et beslutningstre for alle ligninger:

Dermed har ligningssystemet bare 2 løsninger.

Svar: 2.

Eksempel 3

Hvor mange forskjellige sett med verdier av boolske variabler x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 er det som tilfredsstiller alle de følgende betingelsene?

(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

Løsning:

La oss bygge et beslutningstre av den første ligningen:

Tenk på den andre ligningen:

• Når x1=0 : andre og tredje parentes vil være 0; for at den første parentesen skal være lik 1, må y1=1 , z1=1 (dvs. i dette tilfellet - 1 løsning)
• Med x1=1 : første parentes vil være 0; sekund eller den tredje parentesen må være lik 1; den andre parentesen vil være lik 1 når y1=0 og z1=1; den tredje parentesen vil være lik 1 for y1=1 og z1=0 (dvs. i dette tilfellet - 2 løsninger).

Tilsvarende for resten av ligningene. Legg merke til antall løsninger oppnådd for hver node i treet:

For å finne ut antall løsninger for hver gren, multipliserer vi de oppnådde tallene separat for hver gren (fra venstre til høyre).

1 gren: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 løsning

2 gren: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 løsninger

3. gren: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 løsninger

4 gren: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 løsninger

5 gren: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 løsninger

La oss legge til tallene som er oppnådd: totalt 31 løsninger.

Svar: 31.

3. Regelmessig økning i antall røtter

I noen systemer avhenger antall røtter til neste ligning av antall røtter til forrige ligning.

Eksempel 1 Hvor mange forskjellige sett med verdier av boolske variabler x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 er det som tilfredsstiller alle følgende betingelser?

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

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

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

Forenkle første ligning:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Da vil systemet ta formen:

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

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

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

Etc.

Hver påfølgende ligning har 2 flere røtter enn den forrige.

4 ligning har 12 røtter;

Ligning 5 har 14 røtter

8 ligning har 20 røtter.

Svar: 20 røtter.

Noen ganger vokser antallet røtter i henhold til loven om Fibonacci-tall.

Å løse et system med logiske ligninger krever en kreativ tilnærming.