Løsning af ligningen 1. Gå til præfiksformen for at skrive ligningen, og udskift negationernes symboler med ¬ 2. Konstruer titlen på en sandhedstabel af en speciel type 3. Udfyld rækkerne i sandhedstabellen for alle kombinationer af ligningen A og B, der erstatter 0 eller 1 i stedet for X. 4. Generer en sandhedstabel for X = F (A,B) 5. Brug sandhedstabellen til at bestemme typen af funktion X, om nødvendigt, ved hjælp af metoderne til at konstruere SCNF og SDNF, som vil blive diskuteret nedenfor.
Konstruktion af en sandhedstabel med en speciel form ¬((A+B)·(X A·B))=¬(B+¬(X A))
Sandhedstabel X=F(A, B) ABX Svarer til negationen af implikation B i ET SVAR:
Kombinationskredsløb af logiske enheder Grundlæggende elementer (GOST): 1 A B Disjunktion A B Ækvivalens & A B Konjunktion M2 A B XOR
Kombinationskredsløb af logiske enheder Grundlæggende elementer (GOST): 1 A B Implikation & A B Schaeffer element & A B Coimplication 1 A B Webb element
Eksempel kredsløb F 1 & 1 & & 1M2 B A
Løsning af kredsløb 1 Mulighed - at konvertere et kredsløb til et komplekst logisk udtryk og derefter forenkle det i henhold til logikkens love. Mulighed 2 – opbygning af en sandhedstabel og derefter, om nødvendigt, opbygning gennem SKNF eller SDNF (se nedenfor). Lad os overveje den anden mulighed, da den er enklere og mere forståelig.
Konstruktion af sandhedstabellen AB A + B + · B B · A + A B A + · ·
Sandhedstabel F(A, B) ABX Svarer til negationen af implikationen B i ET SVAR:
SDNF og SKNF (definitioner) En elementær konjunktion er en konjunktion af flere variable, taget med eller uden negation, og blandt variablerne kan der være identiske. En elementær disjunktion kaldes en disjunktion af flere variable, taget med eller uden negation, og blandt variablene kan der være identiske Enhver disjunktion af elementære konjunktioner Lad os kalde det en disjunktiv normalform (DNF) Lad os kalde enhver konjunktion af elementære disjunktioner en konjunktiv normalform (DNF)
SDNF og SCNF (definitioner) En perfekt disjunktiv normalform (PDNF) kaldes en DNF, hvor der ikke er identiske elementære konjunktioner, og alle konjunktioner består af det samme sæt af variable, hvor hver variabel kun optræder én gang (evt. med negation). En perfekt konjunktiv normalform (PCNF) er en CNF, hvor der ikke er identiske elementære disjunktioner, og alle disjunktioner består af det samme sæt af variable, hvor hver variabel kun optræder én gang (evt. med negation).
Algoritme til opnåelse af SDNF fra sandhedstabellen 1. Marker rækkerne i sandhedstabellen i den sidste kolonne, hvoraf der er 1. 2. Skriv for hver markeret række konjunktionen af alle variable som følger: hvis værdien af en variabel i en given række er 1, så inkluder denne variabel selv i konjunktionen, hvis den er lig med 0, så dens negation. 3. Forbind alle de resulterende konjunktioner til en disjunktion. Algoritme til at opnå SCNF fra sandhedstabellen 1. Marker rækkerne i sandhedstabellen i den sidste kolonne, hvoraf der er 0. 2. Skriv for hver markeret række disjunktionen af alle variable som følger: hvis værdien af en variabel i en given række er 0, så inkluder denne variabel selv i konjunktionen, hvis den er lig med 1, så dens negation. 3. Forbind alle de resulterende disjunktioner til en konjunktion.
Eksempel på konstruktion af SKNF XY F(X,Y) Marker nuller 2. Disjunktioner: X + Y 3. Konjunktion: (X + Y) · (X + Y)
Løsning af logiske ligningssystemer ved at ændre variable
Metoden til substitution af variabler bruges, hvis nogle variabler kun indgår i ligningerne i form af et specifikt udtryk, og intet andet. Så kan dette udtryk betegnes med en ny variabel.
Eksempel 1.
Hvor mange forskellige værdisæt af de logiske variable x1, x2, x3, x4, x5, x6, x7, x8 er der, der opfylder alle betingelserne anført nedenfor?
(x1 → x2) → (x3→ x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Svaret behøver ikke at liste alle de forskellige værdisæt af variablerne x1, x2, x3, x4, x5, x6, x7, x8, for hvilke dette lighedssystem er opfyldt. Som svar skal du angive antallet af sådanne sæt.
Løsning:
(xl -> x2) = yl; (x3 -> x4) = y2; (x5 -> x6) = y3; (x7 → x8) = y4.
Så kan vi skrive systemet i form af en enkelt ligning:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunktionen er 1 (sand), når hver operand har værdien 1. Dvs. hver af implikationerne skal være sande, og dette gælder for alle værdier undtagen (1 → 0). De der. i tabellen over værdier af variablerne y1, y2, y3, y4, skal man ikke være til venstre for nul:
De der. betingelserne er opfyldt for 5 sæt y1-y4.
Fordi y1 = x1 → x2, så opnås værdien y1 = 0 på et enkelt sæt x1, x2: (1, 0), og værdien y1 = 1 – på tre sæt x1, x2: (0,0) , (0) ,1), (1.1). Ligeledes for y2, y3, y4.
Da hvert sæt (x1,x2) for variablen y1 kombineres med hvert sæt (x3,x4) for variablen y2 osv., ganges antallet af sæt af variablerne x:
|
Antal sæt pr. x1…x8 |
||||
Lad os lægge antallet af sæt sammen: 1 + 3 + 9 + 27 + 81 = 121.
Svar: 121
Eksempel 2.
Hvor mange forskellige værdisæt af de logiske variable x1, x2, ... x9, y1, y2, ... y9 er der, der opfylder alle betingelserne anført nedenfor?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
Som svar intet behov liste alle de forskellige værdisæt af variablerne x1, x2, ... x9, y1, y2, ... y9, for hvilke det givne system af ligheder er opfyldt. Som svar skal du angive antallet af sådanne sæt.
Løsning:
Lad os lave en ændring af variabler:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Systemet kan skrives som en enkelt ligning:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Ækvivalens er kun sand, hvis begge operander er ens. Der er to sæt løsninger til denne ligning:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Fordi zi = (xi ≡ yi), så svarer værdien zi = 0 til to sæt (xi,yi): (0,1) og (1,0), og værdien zi = 1 svarer til to sæt (xi,yi) ): (0,0) og (1,1).
Så svarer det første sæt z1, z2,..., z9 til 2 9 sæt (x1,y1), (x2,y2),..., (x9,y9).
Det samme tal svarer til det andet sæt z1, z2,..., z9. Så er der i alt 2 9 +2 9 = 1024 sæt.
Svar: 1024
Løsning af systemer af logiske ligninger ved hjælp af metoden til visuel bestemmelse af rekursion.
Denne metode bruges, hvis ligningssystemet er ret simpelt, og rækkefølgen af at øge antallet af sæt ved tilføjelse af variable er indlysende.
Eksempel 3.
Hvor mange forskellige løsninger har ligningssystemet?
¬x9 ∨ x10 = 1,
hvor x1, x2, … x10 er logiske variable?
Svaret behøver ikke at angive alle de forskellige sæt værdier x1, x2, ... x10, som dette system af ligheder er opfyldt for. Som svar skal du angive antallet af sådanne sæt.
Løsning:
Lad os løse den første ligning. En disjunktion er lig med 1, hvis mindst en af dens operander er lig med 1. Det vil sige løsningerne er sættene:
For x1=0 er der to værdier af x2 (0 og 1), og for x1=1 er der kun én værdi af x2 (1), således at mængden (x1,x2) er en løsning på ligningen . Der er 3 sæt i alt.
Lad os tilføje variablen x3 og overveje den anden ligning. Det ligner den første, hvilket betyder, at der for x2=0 er to værdier af x3 (0 og 1), og for x2=1 er der kun én værdi x3 (1), således at mængden (x2) ,x3) er en løsning på ligningen. Der er 4 sæt i alt.
Det er let at se, at når der tilføjes en anden variabel, tilføjes et sæt. De der. rekursiv formel for antallet af sæt af (i+1) variable:
N i +1 = N i + 1. Så for ti variable får vi 11 sæt.
Svar: 11
Løsning af systemer af logiske ligninger af forskellige typer
Eksempel 4.
Hvor mange forskellige værdisæt af de logiske variable x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 er der, der opfylder alle betingelserne nedenfor ?
(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 intet behov liste alle de forskellige værdisæt af variablerne x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, for hvilke dette lighedssystem er opfyldt.
Som svar skal du angive antallet af sådanne sæt.
Løsning:
Bemærk, at de tre ligninger i systemet er ens på forskellige uafhængige sæt af variable.
Lad os se på den første ligning. En konjunktion er kun sand (lig med 1), hvis alle dens operander er sande (lig med 1). Implikationen er 1 på alle tupler undtagen (1,0). Det betyder, at løsningen til den første ligning vil være følgende sæt x1, x2, x3, x4, hvor 1 ikke er placeret til venstre for 0 (5 sæt):
Tilsvarende vil løsningerne til den anden og tredje ligning være absolut de samme mængder y1,…,y4 og z1,…, z4.
Lad os nu analysere systemets fjerde ligning: x 4 ∧ y 4 ∧ z 4 = 0. Løsningen vil være alle sæt x4, y4, z4, hvori mindst én af variablerne er lig med 0.
De der. for x4 = 0 er alle mulige mængder (y4, z4) egnede, og for x4 = 1 er sæt (y4, z4) egnede, hvori der er mindst ét nul: (0, 0), (0,1 ), (1, 0).
|
Antal sæt |
||||
Det samlede antal sæt er 25 + 4*9 = 25 + 36 = 61.
Svar: 61
Løsning af systemer af logiske ligninger ved at konstruere tilbagevendende formler
Metoden til at konstruere tilbagevendende formler bruges til at løse komplekse systemer, hvor rækkefølgen af at øge antallet af sæt ikke er indlysende, og at konstruere et træ er umuligt på grund af volumener.
Eksempel 5.
Hvor mange forskellige værdisæt af de logiske variable x1, x2, ... x7, y1, y2, ... y7 er der, der opfylder alle betingelserne anført nedenfor?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Svaret behøver ikke at liste alle de forskellige værdisæt af variablerne x1, x2, ..., x7, y1, y2, ..., y7, for hvilke dette lighedssystem er opfyldt. Som svar skal du angive antallet af sådanne sæt.
Løsning:
Bemærk, at de første seks ligninger i systemet er identiske og kun adskiller sig i mængden af variable. Lad os se på den første ligning. Dens løsning vil være følgende sæt af variabler:
Lad os betegne:
antal tupler (0,0) på variable (x1,y1) til A 1,
antal tupler (0,1) på variable (x1,y1) til og med B 1,
antal tupler (1,0) på variable (x1,y1) til C 1,
antallet af tupler (1,1) på variablerne (x1,y1) til og med D 1 .
antal tupler (0,0) på variable (x2,y2) til A 2 ,
antal tupler (0,1) på variable (x2,y2) til B 2,
antal tupler (1,0) på variable (x2,y2) til og med C 2,
antallet af tupler (1,1) på variablerne (x2,y2) til og med D 2 .
Det ser vi af beslutningstræet
A1=0, B1=1, C1=1, D1=1.
Bemærk, at mængden (0,0) på variablerne (x2,y2) er hentet fra sættene (0,1), (1,0) og (1,1) på variablerne (x1,y1). De der. A2=B1+C1+D1.
Mængden (0,1) på variablerne (x2,y2) fås fra sættene (0,1), (1,0) og (1,1) på variablerne (x1,y1). De der. B2=B1+C1+D1.
På samme måde bemærker vi, at C 2 =B 1 + C 1 + D 1. D2 = D1.
Således får vi tilbagevendende formler:
Ai+1 = Bi + Ci + Di
Bi+1 = Bi + Ci + Di
Ci+1 = Bi + Ci + Di
Di+1 = Ai+Bi + Ci+Di
Lad os lave et bord
| Sæt | Betegnelse. | Formel |
Antal sæt |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | Ai+1 =Bi+Ci+Di | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | Bi+1 =Bi+Ci+Di | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | Ci+1 =Bi+Ci+Di | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | Di+1 =Di | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Den sidste ligning (x7 ∨ y7) = 1 er opfyldt af alle mængder undtagen dem, hvor x7=0 og y7=0. I vores tabel er antallet af sådanne sæt A 7.
Så er det samlede antal sæt B 7 + C 7 + D 7 = 127+127+1 = 255
Svar: 255
Løsning af systemer af logiske ligninger ved hjælp af tabelformede metoder ved at transformere logiske udtryk.Denne teknik er baseret på brugen af sandhedstabeller og er designet til elever, der ved, hvordan man konverterer logiske udtryk. Hvis eleverne ikke er flydende i disse metoder, kan de bruges uden transformationer. (Vi vil bruge transformationer). For at mestre denne løsningsmetode er det bydende nødvendigt at kende egenskaberne ved grundlæggende logiske operationer: konjunktion, disjunktion, inversion, implikation og ækvivalens.
Algoritme til løsning af ligningssystemer ved hjælp af denne metode:
Transformer den logiske ligning og forenkle den.
Bestem rækkefølgen af løsning af ligninger i systemet, da der i de fleste tilfælde er en sekventiel løsning af ligninger fra top til bund (som de er placeret i systemet), men der er muligheder, når det er mere bekvemt og lettere at begynde at løse fra bund til top.
Byg en tabel med variabler, hvor du kan indstille startværdierne for den første variabel (eller den sidste).
Skriv konsekvent de mulige muligheder ned for følgende variabel hvornår alle sammen betydningen af den første.
Efter at have løst den forrige ligning, gå videre til den næste, skal du sørge for at være opmærksom på, hvilke variabler der bruges i de foregående og efterfølgende ligninger, da værdierne af variablerne opnået ved løsning af de foregående ligninger videregives som muligheder for følgende ligninger.
Vær opmærksom på de resulterende mængder af løsningen, når du flytter til den næste variabel, fordi et mønster i stigningen i beslutninger kan identificeres.
Eksempel 1.
¬ x1 ˅ x2=1
¬ x2 ˅ x3=1
¬ x3 ˅ x4=1
¬ x9 ˅ x10=1
Lad os starte med X1 og se, hvilke værdier denne variabel kan tage: 0 og 1.
Derefter vil vi overveje hver af disse værdier og se, hvad X2 kan være.
Svar: 11 løsninger
Eksempel 2.
( x1x2)˅(¬x1˄¬x2) ˅( x1↔ x3)=1
( x2˄x3)˅(¬x2˄¬x3) ˅( x2↔ x4)=1
(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0
Lad os transformere ved hjælp af formlen (EN˄ B)˅ (¬ EN ˄ ¬ B)= EN↔ B
Vi får:
( x1↔ x2) ˅ (x1↔ x3) =1
( x2↔ x3) ˅ (x2↔ x4) =1
( x8↔ x9 (x8↔ x10) =0
For X1 =0 - 8 løsninger
Lad os tage X1=1 og se, hvilken værdi X2 kan tage. Nu vil vi for hver X2 overveje, hvilke værdier X3 kan tage osv.
For X1=1 – 8 løsninger
I alt 8+8=16 løsninger
Svar. 16 løsninger
Eksempel 3 .
¬ ( x1↔ x2) ˄ ( x1x3) ˄ (¬x1˅¬x3 )=0
¬ ( x2↔ x3) ˄ (x2 ˅x4) ˄ (¬x2˅¬x4)=0
….
¬ ( x8↔ x9 (x8x10) ˄ (¬x8˅¬x10)=0
Efter transformationer (EN˅ B) ˄(¬ EN ˅¬ B)= ¬( EN ↔ B)
vi får:
¬ ( x1↔ x2) ˄ ¬ (x1↔ x3)=0
¬ ( x2↔ x3) ˄ ¬ (x2↔ x4)=0
…..
¬ ( x8↔ x9) ˄ ¬ (x8↔ x10)=0
Lad os tage X1=0 og se, hvilken værdi X2 kan tage. Nu vil vi for hver X2 overveje, hvilke værdier X3 kan tage osv.
Vi har 10 løsninger til X1=0
Lad os gøre det samme for X1=1. Vi får også 10 løsninger
I alt:10+10=20
Svar: 20 løsninger.
Eksempel 4.
(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1
(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1
….
(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0
Lad os konvertere ved hjælp af formler. (EN˄ B)˅ (¬ EN ˄ ¬ B)= EN↔ B. Vi får:
(X1↔ X2) ˅ (X2↔ X3)=1
(X2↔ X3) ˅ (X3↔ X4)=1
(X3↔ X4) ˅ (X4↔ X5)=1
(X4↔ X5) ˅ (X5↔ X6)=1
(X5↔ X6) ˅ (X6↔ X7)=1
(X6↔ X7) ˅ (X7↔ X8)=1
(X7↔ X8) ˅ (X8↔ X9)=1
(X8↔ X9) ˅ (X9↔ X10)=0
Lad os starte fra slutningen, for i den sidste ligning er variablerne bestemt entydigt.
Lad X10=0, så X9=1, X8=0, X7=0, X6=0, og de følgende variable kan have forskellige værdier. Vi vil overveje hver.
I alt 21 løsninger for X10=0
Overvej nu for X10=1. Vi får også 21 løsninger
I alt:21+21=42
Svar: 42 løsninger
Eksempel 5.
( x1x2) ˅ (¬x1 ˄ ¬x2) ˅ (¬x3 ˄x4 (x3 ˄ ¬x4)=1
( x3 ˄x4) ˅ (¬x3 ˄ ¬x4) ˅ (¬x5x6) ˅ (x5˄¬x6)=1
( x5x6) ˅ (¬x5˄¬x6) ˅ (¬x7˄x8 (x7˄¬x8)=1
( x7˄x8) ˅ (¬x7˄¬x8) ˅ (¬ x9x10 (x9˄¬x10) =1
Lad os transformere efter formlerne:(¬ EN ˄ B) ˅ ( EN ˄ ¬ B)= EN↔ ¬ B
( EN˄ B)˅ (¬ EN ˄ ¬ B)= EN↔ B
( x1↔ x2) ˅ (x3 ↔ ¬x4)=1
( x3↔ x4 (x5 ↔ ¬x6)=1
( x5↔ x6) ˅ (x7 ↔ ¬x8)=1
( x7↔ x8 (x9 ↔ ¬x10)=1
Lad os overveje, hvilke værdier X1 og X2 kan tage: (0,0), (0,1), (1,0), (1,1).
Lad os overveje hver mulighed og se, hvilke værdier X3, X4 kan tage.
Fra X7, X8 vil vi straks skrive antallet af løsninger ned, da det umiddelbart er klart, at når værdierne er de samme (1,1) og (0,0), så har følgende variabler 4 løsninger, og når de er forskellige (0,1) og (1 ,0) – 2 løsninger.
I alt: 80+80+32=192
Svar: 192 løsninger
Eksempel 6.
(X1↔X2) ˅ (X2 ↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4 ↔X5)=1
….
(X8↔X9) ˅ (X9 ↔X10)=1
Lad os tage X1=0 og se, hvilken værdi X2 kan tage. Nu vil vi for hver X2 overveje, hvilke værdier X3 kan tage osv.
Vi ser et vist mønster: Antallet af efterfølgende løsninger er lig med summen af de to foregående.
Det samme for X1=1 får vi 89 løsninger
I alt: 89+89=178 løsninger
Svar: 178 løsninger
Lad os løse det på en måde mere
(X1↔X2) ˅ (X2 ↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4 ↔X5)=1
….
(X8↔X9) ˅ (X9 ↔X10)=1
Lad os introducere erstatningen:
T 1 =(X1↔X2)
T 2 =(X2↔X3)
T 3 =(X3↔X4)
T 4 =(X4↔X5)
T 5 =(X5↔X6)
T 6 =(X6↔X7)
T 7 =(X7↔X8)
T 8 =(X8↔X9)
T 9 =(X9↔X10)
Vi får:
T1T2=1
T2 ˅T3=1
T3˅T4=1
T4T5=1
T5T6=1
T6˅T7=1
T7˅T8=1
T8T9=1
T9T10=1
Lad os tageT1=1 og brug egenskaberne for disjunktion:
MEN lad os huske det
T 1 =(X1↔X2)
T 2 =(X2↔X3) osv.
Lad os bruge ækvivalensegenskaben og sørge for, når vi ser på tabellen, at
Når T = 1, opnås to løsninger. Og når =0 er der én løsning.
Derfor kan vi tælle antallet af enere og gange dem med 2+ antallet af nuller. Tælling, også ved hjælp af et mønster.
Det viser sig, at antallet af enere = det foregående samlede antal løsninger T, og antallet af nuller er lig med det foregående antal enere
Så. Vi får det. Da man giver to løsninger, så er 34 * 2 = 68 løsninger fra én + 21 løsninger fra 0.
I alt 89 løsninger for T=1. På lignende måde får vi 89 løsninger for T=0
I alt 89+89=178
Svar: 178 løsninger
Eksempel 7.
(x1 ↔ x2) ˅ (x3↔ x4) ˄ ¬(x1 ↔ x2) ˅ ¬(x3↔ x4)=1
(x3 ↔ x4 (x5↔ x6) ˄ ¬(x3 ↔ x4) ˅ ¬(x5↔ x6)=1
(x5 ↔ x6) ˅ (x7↔ x8) ˄ ¬(x5 ↔ x6) ˅ ¬(x7↔ x8)=1
(x7 ↔ x8 (x9↔ x10) ˄ ¬(x7 ↔ x8) ˅ ¬(x9↔ x10)=1
Lad os introducere erstatningen:
T1=(x1 ↔ x2)
T2=(x3↔ x4)
T3=(x5↔ x6)
T4=(x7 ↔ x8)
T5=(x9↔ x10)
Vi får:
(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1
(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1
(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1
(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1
Lad os overveje, hvad T'er kan være:
T1
T2
T3
T4
T5
Total
0
1
0
1
0
32
1
0
1
0
1
32
T K ≠T K+1 DET K =T K+2
Vi får: 2 5 =32 for T
I alt: 32+32=64
Svar: 64 løsninger.
Kommunal budgetuddannelsesinstitution
"Grundskole nr. 18"
bydistrikt i byen Salavat i Republikken Bashkortostan
Systemer af logiske ligninger
i Unified State Examination problemer i datalogi
Afsnittet "Fundamentals of Algebra of Logic" i Unified State Examination-opgaverne betragtes som en af de sværeste og sværeste at løse. Den gennemsnitlige procentdel af udførte opgaver om dette emne er den laveste og er 43,2.
| Kursusafsnit | Gennemsnitlig fuldførelsesprocent efter opgavegrupper |
| Kodning af information og måling af dens mængde | |
| Informationsmodellering | |
| Talsystemer | |
| Grundlæggende om logisk algebra | |
| Algoritmisering og programmering | |
| Det grundlæggende i informations- og kommunikationsteknologier |
Baseret på 2018 KIM-specifikationen indeholder denne blok fire opgaver med forskellige sværhedsgrader.
| № opgaver | Verificerbar indholdselementer | Opgavens sværhedsgrad |
| Evne til at konstruere sandhedstabeller og logiske kredsløb | ||
| Evne til at søge information på internettet | ||
| Kendskab til grundlæggende begreber og love matematisk logik | ||
| Evne til at konstruere og transformere logiske udtryk |
Opgave 23 er høj i sværhedsgrad, derfor har den den laveste fuldførelsesprocent. Blandt forberedte kandidater (81-100 point) fuldførte 49,8% opgaven; moderat forberedte kandidater (61-80 point) fuldførte 13,7%; den resterende gruppe af studerende fuldførte ikke denne opgave.
Succesen med at løse et system af logiske ligninger afhænger af viden om logikkens love og af den præcise anvendelse af metoder til løsning af systemet.
Lad os overveje at løse et system af logiske ligninger ved hjælp af kortlægningsmetoden.
(23.154 Polyakov K.Yu.) Hvor mange forskellige 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 - logiske variable? Svaret behøver ikke at angive alle de forskellige sæt af variabelværdier, som denne lighed gælder for. Som svar skal du angive antallet af sådanne sæt.
Løsning. Alle ligninger, der indgår i systemet, er af samme type, og hver ligning indeholder fire variable. Ved at kende x1 og y1, kan vi finde alle mulige værdier af x2 og y2, der opfylder den første ligning. På samme måde kan vi ud fra de kendte x2 og y2 finde x3, y3, der opfylder den anden ligning. Det vil sige, ved at kende parret (x1, y1) og bestemme værdien af parret (x2, y2), vil vi finde parret (x3, y3), som igen vil føre til parret (x4, y4) og så videre.
Lad os finde alle løsninger til den første ligning. Dette kan gøres på to måder: konstruer en sandhedstabel gennem ræsonnement og anvendelse af logikkens love.
Sandhedstabel:
| x 1 y 1 | x 2 y 2 | (x 1 y 1) (x2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
At konstruere en sandhedstabel er arbejdskrævende og tidsineffektivt, så vi bruger den anden metode - logisk ræsonnement. Produktet er lig med 1, hvis og kun hvis hver faktor er lig med 1.
(x1 y1 ) (x2 y2 ))=1
(x1 x2 ) =1
(y1 y2 ) =1
Lad os se på den første ligning. Konsekvensen er lig med 1 når 0 0, 0 1, 1 1, hvilket betyder (x1 y1)=0 for (01), (10), så parret (x2 y2 ) kan være en hvilken som helst (00), (01), (10), (11), og når (x1 y1) = 1, det vil sige (00) og (11), tager parret (x2 y2) = 1 samme værdier (00) og (11). Lad os udelukke fra denne løsning de par, for hvilke den anden og tredje ligning er falsk, det vil sige x1=1, x2=0, y1=1, y2=0.
| (x1 , y1 ) | (x2 , y2 ) |
Samlet antal par 1+1+1+22= 25
2) (23.160 Polyakov K.Yu.) Hvor mange forskellige løsninger har systemet 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) Ligningerne er af samme type, så ved hjælp af ræsonnement finder vi alle mulige par (x1,y1), (x2,y2) af den første ligning.
(x1 (x2 y2 ))=1
(y1 y2 ) = 1
Løsningen til den anden ligning er parrene (00), (01), (11).
Lad os finde løsninger på den første ligning. Hvis x1=0, så x2, y2 - enhver, hvis x1=1, så tager x2, y2 værdien (11).
Lad os skabe forbindelser mellem par (x1, y1) og (x2, y2).
| (x1 , y1 ) | (x2 , y2 ) |
Lad os lave en tabel for at beregne antallet af par på hvert trin.
| 0 |
|||||||
Under hensyntagen til løsningerne af den sidste ligning x 7 y 7 = 1, lad os udelukke par (10). Find det samlede antal løsninger 1+7+0+34=42
3)(23.180) Hvor mange forskellige løsninger har et system af 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) Ligningerne er af samme type, så ved hjælp af ræsonnement finder vi alle mulige par (x1,x2), (x3,x4) af den første ligning.
(x1 x2 ) (x3 x4 ) = 1
Lad os udelukke fra løsningen de par, der i rækkefølgen giver 0 (1 0), det er parrene (01, 00, 11) og (10).
Lad os skabe forbindelser mellem par (x1,x2), (x3,x4)
Lektionens emne: Løsning af logiske ligninger
Pædagogisk – studere metoder til at løse logiske ligninger, udvikle færdigheder i at løse logiske ligninger og konstruere et logisk udtryk ved hjælp af en sandhedstabel;Udviklings- skabe betingelser for udvikling af elevernes kognitive interesse, fremme udviklingen af hukommelse, opmærksomhed og logisk tænkning;
Pædagogisk : fremmer evnen til at lytte til andres meninger, pleje viljen og udholdenheden til at opnå endelige resultater.
Lektionstype: kombineret lektion
Udstyr: computer, multimedieprojektor, præsentation 6.
Under timerne
Gentagelse og opdatering af grundlæggende viden. Kontrol af lektier (10 minutter)
I tidligere lektioner stiftede vi bekendtskab med de grundlæggende love i logisk algebra og lærte at bruge disse love til at forenkle logiske udtryk.
Lad os tjekke vores hjemmearbejde om at forenkle logiske udtryk:
1. Hvilket af følgende ord opfylder den logiske betingelse:
(første bogstavs konsonant → andet bogstavs konsonant)٨ (sidste bogstavvokal → næstsidste bogstavvokal)? Hvis der er flere sådanne ord, skal du angive det mindste af dem.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Lad os introducere følgende notation:
A – første bogstavs konsonant
B – andet bogstavs konsonant
S – sidste bogstavs vokal
D – næstsidste vokalbogstav
Lad os komme med et udtryk:
Lad os lave en tabel:
2. Angiv hvilket logisk udtryk der svarer til udtrykket
Lad os forenkle registreringen af det originale udtryk og de foreslåede muligheder:
3. Givet et fragment af sandhedstabellen for udtryk F:
Hvilket udtryk matcher F?
Lad os bestemme værdierne af disse udtryk for de angivne værdier af argumenterne:
Introduktion til lektionens emne, præsentation af nyt stof (30 minutter)
Vi fortsætter med at studere det grundlæggende i logik, og emnet for vores dagens lektion er "Løsning af logiske ligninger." Efter at have studeret dette emne, vil du lære de grundlæggende måder at løse logiske ligninger på, få færdighederne til at løse disse ligninger ved at bruge sproget i logisk algebra og evnen til at komponere et logisk udtryk ved hjælp af en sandhedstabel.
1. Løs en logisk ligning
(¬K M) → (¬L M N) = 0
Skriv dit svar som en streng på fire tegn: værdierne af variablerne K, L, M og N (i nævnte rækkefølge). Så f.eks. svarer linje 1101 til, at K=1, L=1, M=0, N=1.
Løsning:
Lad os omdanne udtrykket(¬K M) → (¬L M N)
Et udtryk er falsk, når begge udtryk er falske. Det andet led er lig med 0, hvis M =0, N =0, L =1. I det første led K = 0, da M = 0, og 
.
Svar: 0100
2. Hvor mange løsninger har ligningen (angiv kun tallet i dit svar)?
Løsning: transformer udtrykket
(A+B)*(C+D)=1
A+B=1 og C+D=1
Metode 2: udarbejdelse af en sandhedstabel
3 vejs: konstruktion af en SDNF - en perfekt disjunktiv normalform for en funktion - en disjunktion af komplette regulære elementære konjunktioner.Lad os omdanne det oprindelige udtryk, åbne parenteserne for at opnå disjunktionen af konjunktioner:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Lad os supplere konjunktionerne til komplette konjunktioner (produktet af alle argumenter), åbn parenteserne:
Lad os tage de samme konjunktioner i betragtning:
Som et resultat opnår vi en SDNF indeholdende 9 konjunktioner. Derfor har sandhedstabellen for denne funktion værdien 1 i 9 rækker med 2 4 = 16 sæt af variable værdier.
3. Hvor mange løsninger har ligningen (angiv kun tallet i dit svar)?
Lad os forenkle udtrykket:
,
3 vejs: konstruktion af SDNF
Lad os tage de samme konjunktioner i betragtning:
Som et resultat opnår vi en SDNF indeholdende 5 konjunktioner. Derfor har sandhedstabellen for denne funktion værdien 1 på 5 rækker med 2 4 = 16 sæt af variable værdier.
Konstruktion af et logisk udtryk ved hjælp af en sandhedstabel:
for hver række i sandhedstabellen, der indeholder 1, sammensætter vi et produkt af argumenter, og variabler lig med 0 er inkluderet i produktet med negation, og variable lig med 1 er inkluderet uden negation. Det ønskede udtryk F vil være sammensat af summen af de resulterende produkter. Så, hvis det er muligt, bør dette udtryk forenkles.
Eksempel: der gives en sandhedstabel for et udtryk. Konstruer et logisk udtryk.
Løsning:3. Hjemmearbejde (5 minutter)
Løs ligningen:
Hvor mange løsninger har ligningen (angiv kun tallet i dit svar)?
Konstruer ved hjælp af en given sandhedstabel et logisk udtryk og
forenkle det.