Hoe logische formules op te lossen. Systemen van logische vergelijkingen in de taken van het examen in de informatica

Het gebruik van vergelijkingen is wijdverbreid in ons leven. Ze worden gebruikt in veel berekeningen, constructie van constructies en zelfs sport. Vergelijkingen worden al sinds de oudheid door de mens gebruikt en sindsdien is het gebruik ervan alleen maar toegenomen. In de wiskunde zijn er bepaalde taken die zijn gewijd aan de logica van proposities. Om dit soort vergelijkingen op te lossen, moet je een bepaalde hoeveelheid kennis hebben: kennis van de wetten van de propositielogica, kennis van de waarheidstabellen van logische functies van 1 of 2 variabelen, methoden voor het transformeren van logische uitdrukkingen. Daarnaast moet je de volgende eigenschappen van logische bewerkingen kennen: voegwoorden, disjuncties, inversies, implicaties en equivalenties.

Elke logische functie van \ variabelen - \ kan worden gespecificeerd door een waarheidstabel.

Laten we enkele logische vergelijkingen oplossen:

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

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

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

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

Laten we de oplossing beginnen met \[X1\] en bepalen welke waarden deze variabele kan aannemen: 0 en 1. Bekijk vervolgens elk van de bovenstaande waarden en kijk wat \[X2.\] kan in dit geval zijn

Zoals uit de tabel blijkt, heeft onze logische vergelijking 11 oplossingen.

Waar kan ik een logische vergelijking online oplossen?

U kunt de vergelijking oplossen op onze website https: // site. Met de gratis online oplosser kunt u binnen enkele seconden een online vergelijking van elke complexiteit oplossen. Het enige dat u hoeft te doen, is uw gegevens in de oplosser in te voeren. U kunt ook de video-instructie bekijken en leren hoe u de vergelijking kunt oplossen op onze website. En als je vragen hebt, kun je ze stellen in onze Vkontakte-groep http://vk.com/pocketteacher. Word lid van onze groep, we zijn altijd blij om je te helpen.

Systemen van logische vergelijkingen oplossen door variabelen te veranderen

De methode voor het wijzigen van variabelen wordt gebruikt als sommige variabelen alleen in de vorm van een specifieke uitdrukking in de vergelijkingen worden opgenomen en niets anders. Dan kan deze uitdrukking worden aangeduid met een nieuwe variabele.

voorbeeld 1

Hoeveel verschillende reeksen waarden van logische variabelen x1, x2, x3, x4, x5, x6, x7, x8 zijn er die aan alle volgende voorwaarden voldoen?

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

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

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

Het antwoord hoeft niet alle verschillende reeksen waarden van de variabelen x1, x2, x3, x4, x5, x6, x7, x8 op te sommen waaronder aan dit systeem van gelijkheden wordt voldaan. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing:

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

Dan kan het systeem worden geschreven als een enkele vergelijking:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. De conjunctie is 1 (waar) wanneer elke operand evalueert tot 1. Dat wil zeggen, elk van de implicaties moet waar zijn, en dit geldt voor alle waarden behalve (1 → 0). Die. in de tabel met waarden van variabelen y1, y2, y3, y4 mag de eenheid niet links van nul staan:

Die. voorwaarden is voldaan voor 5 sets y1-y4.

Omdat y1 = x1 → x2, dan wordt de waarde y1 = 0 bereikt op een enkele set x1, x2: (1, 0), en de waarde y1 = 1 wordt bereikt op drie sets x1, x2: (0,0) , ( 0,1), (1.1). Hetzelfde geldt voor y2, y3, y4.

Aangezien elke verzameling (x1,x2) voor variabele y1 wordt gecombineerd met elke verzameling (x3,x4) voor variabele y2, enzovoort, wordt het aantal verzamelingen variabelen x vermenigvuldigd:

Laten we het aantal sets optellen: 1 + 3 + 9 + 27 + 81 = 121.

Antwoorden: 121

Voorbeeld 2

Hoeveel verschillende reeksen waarden van booleaanse variabelen x1, x2, ... x9, y1, y2, ... y9 zijn er die aan alle volgende voorwaarden voldoen?

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

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

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

In antwoord niet nodig maak een lijst van alle verschillende reeksen waarden van de variabelen x1, x2, ... x9, y1, y2, ... y9, waaronder aan het gegeven stelsel van gelijkheden wordt voldaan. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing:

Laten we een verandering van variabelen maken:

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

Het systeem kan worden geschreven als een enkele vergelijking:

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

Equivalentie is alleen waar als beide operanden gelijk zijn. De oplossingen van deze vergelijking zijn twee sets:

Omdat zi = (xi ≡ yi), dan komt de waarde zi = 0 overeen met twee sets (xi,yi): (0,1) en (1,0), en de waarde zi = 1 komt overeen met twee sets (xi,yi ): (0,0) en (1,1).

Dan komt de eerste verzameling z1, z2,..., z9 overeen met 2 9 verzamelingen (x1,y1), (x2,y2),..., (x9,y9).

Hetzelfde nummer komt overeen met de tweede set z1, z2,..., z9. Dan zijn er in totaal 2 9 +2 9 = 1024 sets.

Antwoorden: 1024

Systemen van logische vergelijkingen oplossen door visuele definitie van recursie.

Deze methode wordt gebruikt als het systeem van vergelijkingen eenvoudig genoeg is en de volgorde van het verhogen van het aantal sets bij het toevoegen van variabelen duidelijk is.

Voorbeeld 3

Hoeveel verschillende oplossingen heeft het stelsel vergelijkingen?

¬x9 ∨ x10 = 1,

waarbij x1, x2, ... x10 booleaanse variabelen zijn?

Het antwoord hoeft niet alle verschillende reeksen waarden x1, x2, ... x10 op te sommen waarvoor het gegeven stelsel van gelijkheden geldt. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing:

Laten we de eerste vergelijking oplossen. Een disjunctie is gelijk aan 1 als ten minste één van zijn operanden gelijk is aan 1. Dat wil zeggen, de oplossingen zijn de sets:

Voor x1=0 zijn er twee x2-waarden (0 en 1), en voor x1=1 is er slechts één x2-waarde (1), zodat de verzameling (x1,x2) de oplossing van de vergelijking is. Slechts 3 setjes.

Laten we de variabele x3 toevoegen en de tweede vergelijking bekijken. Het is vergelijkbaar met de eerste, wat betekent dat er voor x2=0 twee waarden zijn van x3 (0 en 1), en voor x2=1 is er slechts één waarde van x3 (1), zodat de verzameling ( x2,x3) is een oplossing van de vergelijking. Er zijn in totaal 4 setjes.

Het is gemakkelijk te zien dat bij het toevoegen van een andere variabele, één set wordt toegevoegd. Die. recursieve formule voor het aantal sets op (i+1) variabelen:

N i +1 = N i + 1. Dan krijgen we voor tien variabelen 11 verzamelingen.

Antwoorden: 11

Systemen van logische vergelijkingen van verschillende typen oplossen

Voorbeeld 4

Hoeveel verschillende reeksen waarden van booleaanse variabelen x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 zijn er die aan alle volgende voorwaarden voldoen?

(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

In antwoord niet nodig noem alle verschillende reeksen waarden van de variabelen x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , waaronder aan het gegeven stelsel van gelijkheden wordt voldaan .

Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing:

Merk op dat de drie vergelijkingen van het systeem hetzelfde zijn op verschillende onafhankelijke reeksen variabelen.

Beschouw de eerste vergelijking. Een conjunctie is alleen waar (gelijk aan 1) als alle operanden waar zijn (gelijk aan 1). De implicatie is 1 op alle sets behalve (1,0). Dit betekent dat de oplossing van de eerste vergelijking zulke sets x1, x2, x3, x4 zal zijn, waarin 1 niet links van 0 is (5 sets):

Evenzo zullen de oplossingen van de tweede en derde vergelijking exact dezelfde verzamelingen zijn van y1,...,y4 en z1,...,z4.

Laten we nu de vierde vergelijking van het systeem analyseren: x 4 ∧ y 4 ∧ z 4 = 0. De oplossing is alle verzamelingen x4, y4, z4 waarin ten minste één van de variabelen gelijk is aan 0.

Die. voor x4 = 0 zijn alle mogelijke verzamelingen (y4, z4) geschikt, en voor x4 = 1 zijn verzamelingen (y4, z4) die ten minste één nul bevatten geschikt: (0, 0), (0,1) , ( 1, 0).

Het totaal aantal sets is 25 + 4*9 = 25 + 36 = 61.

Antwoorden: 61

Systemen van logische vergelijkingen oplossen door terugkerende formules te construeren

De methode van het construeren van terugkerende formules wordt gebruikt om complexe systemen op te lossen waarin de volgorde van het verhogen van het aantal sets niet duidelijk is en het bouwen van een boom onmogelijk is vanwege volumes.

Voorbeeld 5

Hoeveel verschillende reeksen waarden van booleaanse variabelen x1, x2, ... x7, y1, y2, ... y7 zijn er die aan alle volgende voorwaarden voldoen?

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

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

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

Het antwoord hoeft niet alle verschillende reeksen waarden van de variabelen x1, x2, ..., x7, y1, y2, ..., y7 op te sommen waaronder het gegeven stelsel van gelijkheden geldt. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing:

Merk op dat de eerste zes vergelijkingen van het systeem hetzelfde zijn en alleen verschillen in de reeks variabelen. Beschouw de eerste vergelijking. De oplossing zal de volgende sets variabelen zijn:

Geef aan:

aantal sets (0,0) op variabelen (x1,y1) t/m A 1 ,

aantal sets (0,1) op variabelen (x1,y1) t/m B 1 ,

aantal sets (1,0) op variabelen (x1,y1) via C 1 ,

aantal sets (1,1) op variabelen (x1,y1) via D 1 .

aantal sets (0,0) op variabelen (x2,y2) t/m A 2 ,

aantal sets (0,1) op variabelen (x2,y2) via B 2 ,

aantal sets (1,0) op variabelen (x2,y2) via C 2 ,

aantal sets (1,1) op variabelen (x2,y2) via D 2 .

Uit de beslisboom zien we dat

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

Merk op dat de tupel (0,0) op de variabelen (x2,y2) wordt verkregen uit de tupels (0,1), (1,0) en (1,1) op de variabelen (x1,y1). Die. A 2 \u003d B 1 + C 1 + D 1.

De verzameling (0,1) op de variabelen (x2,y2) wordt verkregen uit de verzamelingen (0,1), (1,0) en (1,1) op de variabelen (x1,y1). Die. B 2 \u003d B 1 + C 1 + D 1.

Op dezelfde manier argumenteren we dat C 2 \u003d B 1 + C 1 + D 1. D2 = D1.

Zo krijgen we recursieve formules:

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

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

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

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

Laten we een tafel maken

Aan de laatste vergelijking (x7 ∨ y7) = 1 wordt voldaan door alle verzamelingen behalve die waarin x7=0 en y7=0. In onze tabel is het aantal van dergelijke sets A 7 .

Dan is het totaal aantal sets B 7 + C 7 + D 7 = 127+127+1 = 255

Antwoorden: 255

Gemeentelijke budgettaire onderwijsinstelling

"Secundaire school nr. 18"

stadsdeel van de stad Salavat van de Republiek Bashkortostan

Stelsels van logische vergelijkingen

in de taken van het examen in de informatica

De sectie "Fundamentals of Algebra of Logic" in de taken van het examen wordt als een van de moeilijkste en slecht opgeloste beschouwd. Het gemiddelde percentage voltooide taken over dit onderwerp is het laagst en is 43,2.

Op basis van de specificatie van KIM 2018 omvat dit blok vier taken van verschillende niveaus van complexiteit.

Taak 23 heeft een hoge moeilijkheidsgraad en heeft daarom het laagste voltooiingspercentage. Van de getrainde afgestudeerden (81-100 punten) heeft 49,8% deze taak voltooid, de gemiddeld voorbereide (61-80 punten) 13,7% heeft deze taak volbracht, de overige groep studenten heeft deze taak niet voltooid.

Het succes van het oplossen van een stelsel van logische vergelijkingen hangt af van de kennis van de wetten van de logica en van de precieze toepassing van methoden om het stelsel op te lossen.

Beschouw de oplossing van een systeem van logische vergelijkingen door de mapping-methode.

(23.154 Polyakov K.Yu.) Hoeveel verschillende oplossingen heeft het stelsel vergelijkingen?

((x1  ja1 )  (x2  ja2 ))  (x1  x2 )  (y1  ja2 ) =1

((x2  ja2 )  (x3  ja3 ))  (x2  x3 )  (y2  ja3 ) =1

((x7  ja7 )  (x8  ja8 ))  (x7  x8 )  (ja7  ja8 ) =1

waar x1 , x2 ,…, x8, Bij1 ,y2 ,…,y8 - Booleaanse variabelen? Het antwoord hoeft niet alle verschillende sets variabele waarden op te sommen waarvoor deze gelijkheid geldt. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing. Alle vergelijkingen in het systeem zijn van hetzelfde type en in elke vergelijking zijn vier variabelen opgenomen. Als we x1 en y1 kennen, kunnen we alle mogelijke waarden van x2 en y2 vinden die voldoen aan de eerste vergelijking. Als we op een vergelijkbare manier redeneren, kunnen we uit de bekende x2 en y2 x3, y3 vinden die voldoet aan de tweede vergelijking. Dat wil zeggen, als we het paar (x1 , y1) kennen en de waarde van het paar (x2 , y2) bepalen, zullen we het paar (x3 , y3 ) vinden, wat op zijn beurt zal leiden tot het paar (x4 , y4 ) en zo Aan.

Laten we alle oplossingen van de eerste vergelijking zoeken. Dit kan op twee manieren: een waarheidstabel bouwen, door te redeneren en de wetten van de logica toe te passen.

Waarheidstabel:

Het bouwen van een waarheidstabel is arbeidsintensief en tijdinefficiënt, dus gebruiken we de tweede methode - logisch redeneren. Het product is 1 als en slechts dan als elke factor 1 is.

(x1  ja1 )  (x2  ja2 ))=1

(x1  x2 ) =1

(ja1  ja2 ) =1

Beschouw de eerste vergelijking. Volgende is gelijk aan 1, wanneer 0 0, 0 1, 1 1, dan (x1 y1)=0 bij (01), (10), dan is het paar (x2  ja2 ) kan elke (00), (01), (10), (11) zijn en voor (x1 y1)=1, d.w.z. (00) en (11) heeft het paar (x2 y2)=1 dezelfde waarden (00) en (11). We sluiten van deze oplossing die paren uit waarvoor de tweede en derde vergelijking onwaar zijn, dat wil zeggen x1=1, x2=0, y1=1, y2=0.

Totaal aantal paren 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Hoeveel verschillende oplossingen heeft een stelsel van logische vergelijkingen?

(x 1  (x 2  ja 2 ))  (y 1  ja 2 ) = 1

(x 2  (x 3  ja 3 ))  (y 2  ja 3 ) = 1

...

( x 6  ( x 7  ja 7 ))  ( ja 6  ja 7 ) = 1

x 7  ja 7 = 1

Oplossing. 1) De vergelijkingen zijn van hetzelfde type, dus door de redeneermethode zullen we alle mogelijke paren (x1,y1), (x2,y2) van de eerste vergelijking vinden.

(x1  (x2  ja2 ))=1

(ja1  ja2 ) = 1

De oplossing van de tweede vergelijking zijn paren (00), (01), (11).

Laten we oplossingen zoeken voor de eerste vergelijking. Als x1=0, dan krijgt x2 , y2 - willekeurig, als x1=1, dan krijgt x2 , y2 de waarde (11).

Laten we verbindingen maken tussen paren (x1 , y1) en (x2 , y2).

Laten we een tabel maken om het aantal paren in elke fase te berekenen.

Rekening houdend met de oplossingen van de laatste vergelijking x 7  ja 7 = 1, we elimineren het paar (10). Vind het totale aantal oplossingen 1+7+0+34=42

3)(23.180) Hoeveel verschillende oplossingen heeft het stelsel van logische vergelijkingen?

(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

Oplossing. 1) De vergelijkingen zijn van hetzelfde type, dus door de redeneermethode zullen we alle mogelijke paren (x1,x2), (x3,x4) van de eerste vergelijking vinden.

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

We sluiten van de oplossing de paren uit die 0 (1 0) geven in het volgende, dit zijn de paren (01, 00, 11) en (10).

Stel koppelingen samen tussen paren (x1,x2), (x3,x4)

Instructie. Gebruik bij het invoeren vanaf het toetsenbord de volgende conventies:

Invoerregels voor logische functie

1. Gebruik het + teken in plaats van v (disjunctie, OR).
2. Voor de logische functie hoeft u de functieaanduiding niet op te geven. In plaats van F(x,y)=(x|y)=(x^y) typt u bijvoorbeeld gewoon (x|y)=(x^y) .
3. Het maximale aantal variabelen is 10 .

Het ontwerp en de analyse van computerlogicaschakelingen wordt uitgevoerd met behulp van een speciaal onderdeel van de wiskunde - de algebra van logica. In de algebra van de logica kunnen drie belangrijke logische functies worden onderscheiden: "NIET" (negatie), "AND" (conjunctie), "OF" (disjunctie).
Om een ​​logisch apparaat te maken, is het noodzakelijk om de afhankelijkheid van elk van de uitvoervariabelen van de huidige invoervariabelen te bepalen, een dergelijke afhankelijkheid wordt een schakelfunctie of een functie van de logische algebra genoemd.
Een logische algebrafunctie wordt volledig gedefinieerd genoemd als alle 2 n van zijn waarden worden gegeven, waarbij n het aantal uitvoervariabelen is.
Als niet alle waarden zijn gedefinieerd, wordt de functie gedeeltelijk gedefinieerd genoemd.
Een apparaat wordt logisch genoemd als de toestand ervan wordt beschreven met behulp van een functie van de algebra van de logica.
De volgende methoden worden gebruikt om de logische algebrafunctie weer te geven:
In algebraïsche vorm is het mogelijk om een ​​diagram van een logisch apparaat te construeren met behulp van logische elementen.


Figuur 1 - Schema van een logisch apparaat

Alle bewerkingen van de algebra van de logica zijn gedefinieerd waarheidstabellen waarden. De waarheidstabel bepaalt het resultaat van het uitvoeren van een bewerking voor: alles mogelijk x logische waarden van de originele statements. Het aantal opties dat het resultaat van het toepassen van de bewerkingen weerspiegelt, hangt af van het aantal instructies in de logische expressie. Als het aantal uitspraken in de logische uitdrukking N is, dan bevat de waarheidstabel 2 N rijen, aangezien er 2 N verschillende combinaties van mogelijke argumentwaarden zijn.

Operatie NOT - logische ontkenning (inversie)

• als de oorspronkelijke uitdrukking waar is, zal het resultaat van zijn ontkenning onwaar zijn;
• als de oorspronkelijke uitdrukking onwaar is, dan is het resultaat van zijn ontkenning waar.

Operatie OR - logische toevoeging (disjunctie, vereniging)

Operatie AND - logische vermenigvuldiging (conjunctie)

Operatie "IF-THEN" - logisch gevolg (implicatie)

Operatie "A als en slechts als B" (equivalentie, equivalentie)

Modulo 2 optelbewerking (XOR, exclusief of, strikte disjunctie)

Voorrang van logische bewerkingen

• Acties tussen haakjes
• inversie
• Voegwoord (&)
• Disjunctie (V), Exclusief OF (XOR), modulo 2 som
• Implicatie (→)
• Gelijkwaardigheid (↔)

Perfecte disjunctieve normaalvorm

1. Elke logische term van de formule bevat alle variabelen van de functie F(x 1 ,x 2 ,...x n).
2. Alle logische termen van de formule zijn verschillend.
3. Geen enkele logische term bevat een variabele en zijn ontkenning.
4. Geen enkele logische term in een formule bevat twee keer dezelfde variabele.

Perfecte conjunctieve normaalvorm

1. Alle elementaire disjuncties bevatten alle variabelen van de functie F(x 1 ,x 2 ,...x n).
2. Alle elementaire disjuncties zijn verschillend.
3. Elke elementaire disjunctie bevat eenmaal een variabele.
4. Geen enkele elementaire disjunctie bevat een variabele en zijn negatie.

Methoden voor het oplossen van stelsels van logische vergelijkingen

U kunt een stelsel van logische vergelijkingen oplossen, bijvoorbeeld met behulp van een waarheidstabel (als het aantal variabelen niet te groot is) of met behulp van een beslisboom, na elke vergelijking te hebben vereenvoudigd.

1. Methode voor het wijzigen van variabelen.

De introductie van nieuwe variabelen maakt het mogelijk om het stelsel van vergelijkingen te vereenvoudigen door het aantal onbekenden te verminderen.Nieuwe variabelen moeten onafhankelijk van elkaar zijn. Na het oplossen van het vereenvoudigde systeem is het nodig om weer terug te keren naar de oorspronkelijke variabelen.

Overweeg de toepassing van deze methode op een specifiek voorbeeld.

Voorbeeld.

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

Oplossing:

Laten we nieuwe variabelen introduceren: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Let op! Elk van hun variabelen x1, x2, ..., x10 moet worden opgenomen in slechts één van de nieuwe variabelen A, B, C, D, E, d.w.z. de nieuwe variabelen zijn onafhankelijk van elkaar).

Dan ziet het stelsel vergelijkingen er als volgt uit:

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

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

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

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

Laten we een beslissingsboom maken van het resulterende systeem:

Beschouw de vergelijking A=0, d.w.z. (X1≡ X2)=0. Het heeft 2 wortels:

Uit dezelfde tabel blijkt dat de vergelijking A \u003d 1 ook 2 wortels heeft. Laten we het aantal wortels op de beslisboom ordenen:

Om het aantal oplossingen voor één tak te vinden, moet u het aantal oplossingen op elk niveau vermenigvuldigen. De linker tak heeft 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 oplossingen; de rechtertak heeft ook 32 oplossingen. Die. het hele systeem heeft 32+32=64 oplossingen.

Antwoord: 64.

2. Wijze van redeneren.

De complexiteit van het oplossen van stelsels van logische vergelijkingen ligt in de omvang van de volledige beslisboom. Met de redeneermethode kun je niet de hele boom volledig bouwen, maar tegelijkertijd begrijpen hoeveel takken hij zal hebben. Laten we deze methode bekijken aan de hand van concrete voorbeelden.

voorbeeld 1 Hoeveel verschillende reeksen waarden van booleaanse variabelen x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 zijn er die aan alle volgende voorwaarden voldoen?

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

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

x1\/y1 =1

Het antwoord hoeft niet alle verschillende reeksen waarden van de variabelen x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 op te sommen waaronder aan het gegeven stelsel van gelijkheden wordt voldaan. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing :

De eerste en tweede vergelijking bevatten onafhankelijke variabelen die verband houden met een derde voorwaarde. Laten we een beslisboom construeren voor de eerste en tweede vergelijking.

Om de beslissingsboom van het systeem uit de eerste en tweede vergelijking weer te geven, is het noodzakelijk om elke tak van de eerste boom voort te zetten met een boom voor variabelen Bij . De op deze manier geconstrueerde boom zal 36 takken bevatten. Sommige van deze takken voldoen niet aan de derde vergelijking van het systeem. Noteer op de eerste boom het aantal takken van de boom"Bij" , die voldoen aan de derde vergelijking:

Laten we verduidelijken: voor de vervulling van de derde voorwaarde bij x1=0 moet er y1=1 zijn, d.w.z. alle takken van de boom"X" , waarbij x1=0 kan worden voortgezet met slechts één tak van de boom"Bij" . En alleen voor één tak van de boom"X" (rechts) passen op alle takken van de boom"Bij". De volledige boom van het hele systeem bevat dus 11 takken. Elke tak vertegenwoordigt één oplossing voor het oorspronkelijke stelsel vergelijkingen. Het hele systeem heeft dus 11 oplossingen.

Antwoord: 11.

Voorbeeld 2 Hoeveel verschillende oplossingen heeft het stelsel vergelijkingen?

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

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

………………

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

(X1 ≡ X10) = 0

waarbij x1, x2, ..., x10 booleaanse variabelen zijn? Het antwoord hoeft niet alle verschillende sets variabele waarden op te sommen waarvoor deze gelijkheid geldt. Als antwoord moet u het aantal van dergelijke sets aangeven.

Oplossing : Laten we het systeem vereenvoudigen. Laten we een waarheidstabel maken van het deel van de eerste vergelijking:

Let op de laatste kolom, deze komt overeen met het resultaat van de actie X1 ≡ X10.

Na vereenvoudiging krijgen we:

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

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

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

……

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

(X1 ≡ X10) = 0

Beschouw de laatste vergelijking:(X1 X10) = 0, d.w.z. x1 mag niet hetzelfde zijn als x10. Om de eerste vergelijking gelijk te maken aan 1, moet de gelijkheid gelden(X1 ≡ X2)=1, d.w.z. x1 moet overeenkomen met x2.

Laten we een beslissingsboom maken voor de eerste vergelijking:

Beschouw de tweede vergelijking: voor x10=1 en voor x2=0 de haakmoet gelijk zijn aan 1 (d.w.z. x2 is hetzelfde als x3); bij x10=0 en bij x2=1 haakjes(X2 ≡ X10)=0 , dus haakje (X2 ≡ X3) moet gelijk zijn aan 1 (d.w.z. x2 is hetzelfde als x3):

Als we op deze manier redeneren, construeren we een beslisboom voor alle vergelijkingen:

Het stelsel vergelijkingen heeft dus maar 2 oplossingen.

Antwoord: 2.

Voorbeeld 3

Hoeveel verschillende reeksen waarden van booleaanse variabelen x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 zijn er die aan alle volgende voorwaarden voldoen?

(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

Oplossing:

Laten we een beslissingsboom van de 1e vergelijking bouwen:

Beschouw de tweede vergelijking:

• Wanneer x1=0 : tweede en derde haakjes zijn 0; om de eerste haak gelijk te maken aan 1, moet y1=1 , z1=1 (d.w.z. in dit geval - 1 oplossing)
• Met x1=1 : eerste haakje is 0; seconde of het derde haakje moet gelijk zijn aan 1; de tweede haak is gelijk aan 1 wanneer y1=0 en z1=1; de derde haak is gelijk aan 1 voor y1=1 en z1=0 (d.w.z. in dit geval - 2 oplossingen).

Hetzelfde geldt voor de rest van de vergelijkingen. Let op het aantal verkregen oplossingen voor elk knooppunt van de boom:

Om het aantal oplossingen voor elke tak te weten te komen, vermenigvuldigen we de verkregen getallen afzonderlijk voor elke tak (van links naar rechts).

1 tak: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 oplossing

2 vertakkingen: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 oplossingen

3e tak: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 oplossingen

4 tak: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 oplossingen

5 tak: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 oplossingen

Laten we de verkregen getallen bij elkaar optellen: in totaal 31 oplossingen.

Antwoord: 31.

3. Regelmatige toename van het aantal wortels

In sommige systemen hangt het aantal wortels van de volgende vergelijking af van het aantal wortels van de vorige vergelijking.

voorbeeld 1 Hoeveel verschillende reeksen waarden van booleaanse variabelen x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 zijn er die aan alle volgende voorwaarden voldoen?

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

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

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

Makkelijker maken eerste vergelijking:(x1 ¬ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Het systeem zal dan de vorm aannemen:

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

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

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

Enz.

Elke volgende vergelijking heeft 2 wortels meer dan de vorige.

4 vergelijking heeft 12 wortels;

Vergelijking 5 heeft 14 wortels

8 vergelijking heeft 20 wortels.

Antwoord: 20 wortels.

Soms groeit het aantal wortels volgens de wet van de Fibonacci-getallen.

Het oplossen van een stelsel van logische vergelijkingen vereist een creatieve aanpak.