Løsning af logiske ligninger. Prioritet af logiske operationer

Lad være en logisk funktion af n variable. Den logiske ligning ser således ud:

Konstanten C har værdien 1 eller 0.

En logisk ligning kan have fra 0 til forskellige løsninger. Hvis C er lig med 1, så er løsningerne alle de sæt af variabler fra sandhedstabellen, for hvilke funktionen F tager værdien sand (1). De resterende mængder er løsninger af ligningen med C lig med nul. Du kan altid kun overveje formens ligninger:

Faktisk, lad ligningen gives:

I dette tilfælde kan vi gå til den ækvivalente ligning:

Overvej et system af k logiske ligninger:

Løsningen til et system er et sæt variabler, hvorpå alle systemets ligninger er opfyldt. Med hensyn til logiske funktioner, for at opnå en løsning til et system af logiske ligninger, bør man finde et sæt, hvor den logiske funktion Ф er sand, der repræsenterer konjunktionen af ​​de oprindelige funktioner:

Hvis antallet af variable er lille, for eksempel mindre end 5, så er det ikke svært at konstruere en sandhedstabel for funktionen, som giver os mulighed for at sige, hvor mange løsninger systemet har, og hvilke mængder der giver løsninger.

I nogle USE-problemer med at finde løsninger på et system af logiske ligninger, når antallet af variabler 10. Så bliver det en næsten umulig opgave at konstruere en sandhedstabel. At løse problemet kræver en anden tilgang. For et vilkårligt ligningssystem er der ingen generel metode udover opregning, der tillader løsning af sådanne problemer.

I de problemer, der foreslås til eksamen, er løsningen normalt baseret på at tage højde for de særlige forhold ved ligningssystemet. Jeg gentager, bortset fra at prøve alle mulighederne for et sæt variabler, er der ingen generel måde at løse problemet på. Løsningen skal bygges ud fra systemets specifikationer. Det er ofte nyttigt at udføre en foreløbig forenkling af et ligningssystem ved hjælp af kendte logiske love. En anden nyttig teknik til at løse dette problem er som følger. Vi er ikke interesserede i alle mængder, men kun dem, hvorpå funktionen har værdien 1. I stedet for at bygge en komplet sandhedstabel, vil vi bygge dens analog - et binært beslutningstræ. Hver gren af ​​dette træ svarer til én løsning og angiver et sæt, hvorpå funktionen har værdien 1. Antallet af grene i beslutningstræet falder sammen med antallet af løsninger til ligningssystemet.

Jeg vil forklare, hvad et binært beslutningstræ er, og hvordan det er bygget ved hjælp af eksempler på flere problemer.

Opgave 18

Hvor mange forskellige værdisæt af de logiske variable x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 er der, der opfylder systemet med to ligninger?

Svar: Systemet har 36 forskellige løsninger.

Løsning: Ligningssystemet omfatter to ligninger. Lad os finde antallet af løsninger til den første ligning, afhængig af 5 variable - . Den første ligning kan igen betragtes som et system af 5 ligninger. Som det er blevet vist, repræsenterer ligningssystemet faktisk sammensætningen af ​​logiske funktioner. Det omvendte udsagn er også sandt - en konjunktion af betingelser kan betragtes som et ligningssystem.

Lad os bygge et beslutningstræ for implikation () - det første led i konjunktionen, som kan betragtes som den første ligning. Sådan ser en grafisk gengivelse af dette træ ud

Træet består af to niveauer i henhold til antallet af variable i ligningen. Det første niveau beskriver den første variabel. To grene af dette niveau afspejler de mulige værdier af denne variabel - 1 og 0. På det andet niveau afspejler grenene af træet kun de mulige værdier af den variabel, for hvilken ligningen vurderes til at være sand. Da ligningen angiver en implikation, kræver en gren, hvorpå har værdien 1, at der på denne gren er en værdi på 1. En gren, hvorpå har værdien 0, genererer to grene med værdier lig med 0 og 1. Den konstruerede træ specificerer tre løsninger, hvoraf implikationen tager værdien 1. På hver gren er et tilsvarende sæt af variable værdier skrevet ud, hvilket giver en løsning til ligningen.

Disse sæt er: ((1, 1), (0, 1), (0, 0))

Lad os fortsætte med at bygge beslutningstræet ved at tilføje følgende ligning med følgende implikation. Det specifikke ved vores ligningssystem er, at hver ny ligning i systemet bruger en variabel fra den forrige ligning, og tilføjer en ny variabel. Da variablen allerede har værdier i træet, så vil variablen på alle grene, hvor variablen har en værdi på 1, også have en værdi på 1. For sådanne grene fortsætter konstruktionen af ​​træet til næste niveau, men nye grene dukker ikke op. En enkelt gren, hvor en variabel har en værdi på 0, vil forgrene sig i to grene, hvor variablen vil modtage værdier på 0 og 1. Således tilføjer hver tilføjelse af en ny ligning, givet dens specificitet, én løsning. Original første ligning:

har 6 løsninger. Sådan ser det komplette beslutningstræ for denne ligning ud:

Den anden ligning i vores system ligner den første:

Den eneste forskel er, at ligningen bruger Y-variable. Denne ligning har også 6 løsninger. Da hver variabel løsning kan kombineres med hver variabel løsning, er det samlede antal løsninger 36.

Bemærk venligst, at det konstruerede beslutningstræ ikke kun angiver antallet af løsninger (i henhold til antallet af grene), men også selve løsningerne skrevet på hver gren af ​​træet.

Opgave 19

Hvor mange forskellige værdisæt af de logiske variable x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 er der, der opfylder alle betingelserne anført nedenfor?

Denne opgave er en ændring af den tidligere opgave. Forskellen er, at der tilføjes en anden ligning, der relaterer variablerne X og Y.

Det følger af ligningen, at når den har en værdi på 1 (der findes en sådan løsning), så har den en værdi på 1. Der er således et sæt, som og har værdier på 1. Når det er lig med 0, kan det har en hvilken som helst værdi, både 0 og og 1. Derfor svarer hvert sæt med , lig med 0, og der er 5 sådanne sæt, til alle 6 sæt med variable Y. Derfor er det samlede antal løsninger 31.

Opgave 20

Løsning: Når vi husker de grundlæggende ækvivalenser, skriver vi vores ligning som:

Den cykliske kæde af implikationer betyder, at variablerne er identiske, så vores ligning svarer til ligningen:

Denne ligning har to løsninger, når alle er enten 1 eller 0.

Opgave 21

Hvor mange løsninger har ligningen:

Løsning: Ligesom i opgave 20 bevæger vi os fra cykliske implikationer til identiteter og omskriver ligningen i formen:

Lad os bygge et beslutningstræ for denne ligning:

Opgave 22

Hvor mange løsninger har følgende ligningssystem?

I slutningen af ​​året viste det sig, at kun én af de tre antagelser var sand. Hvilke divisioner gav overskud ved årets udgang?

Løsning. Lad os nedskrive antagelserne fra problemforholdene i form af logiske udsagn: ”At modtage et overskud ved division B er ikke en nødvendig betingelse for at opnå

overskud ved division A ":F 1 (A, B, C) = A → B

"At få et overskud fra mindst én division B og C er ikke tilstrækkeligt til at division A giver et overskud": F 2 (A, B, C) = (B + C) → A

"Afdeling A og B giver ikke overskud på samme tid": F 3 (A, B, C) = A B

Fra betingelsen vides det, at kun én af de tre antagelser er sand. Det betyder, at vi skal finde ud af, hvilket af de følgende tre logiske udtryk, der ikke er identisk falsk:

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

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

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

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

I slutningen af ​​året viste den anden antagelse sig derfor at være sand, og den første og tredje var falsk.

Derfor vil division C få et overskud, men division A og B vil ikke få et overskud.

Løsning af logiske ligninger

I teksterne om statscentraliseret test er der en opgave (A8), som beder om at finde roden til en logisk ligning. Lad os se på måder at løse sådanne opgaver ved hjælp af et eksempel.

Find roden til den logiske ligning: (A + B)(X AB) = B + X → A.

Den første løsning er at konstruere en sandhedstabel. Lad os bygge sandhedstabeller for højre og venstre side af ligningen og se, ved hvilket X værdierne i de sidste kolonner i disse tabeller falder sammen.

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

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

Lad os sammenligne de resulterende sandhedstabeller og vælge de rækker, hvor værdierne af F 1 (A, B, X) og F 2 (A, B, X) falder sammen.

Lad os kun omskrive de valgte rækker, så kun argumentkolonnerne efterlades. Lad os se på variablen X som en funktion af A og B.

Det er klart, X = B → A.

Den anden løsning er at erstatte lighedstegnet i ligningen med et ækvivalenttegn og derefter forenkle den resulterende logiske ligning.

For at lette yderligere arbejde, lad os først forenkle højre og venstre side af den logiske ligning og finde deres negationer:

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

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

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

Lad os erstatte lighedstegnet i vores logiske ligning med et ækvivalenstegn:

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

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

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

Lad os omarrangere de logiske udtryk i dette udtryk og tage faktorerne X og X ud af parentes.

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

Lad os så betegne T = A B

X T+ X T= X↔ T.

Derfor, for at en logisk ligning skal have en løsning: X = A B = B + A = B → A.

Computerlogiske elementer. Konstruktion af funktionsdiagrammer

Med udviklingen af ​​computerteknologi viste matematisk logik sig at være tæt forbundet med spørgsmål om design og programmering af computerteknologi. Algebra af logik fandt bred anvendelse oprindeligt i udviklingen relækontakt ordninger Den første grundlæggende forskning, der henledte ingeniører involveret i computerdesign opmærksomhed på muligheden for at analysere elektriske kredsløb ved hjælp af boolsk algebra blev offentliggjort i december 1938 af amerikaneren Claude Shannon, "Symbolic Analysis of Ladder Circuits." Efter denne artikel kunne computerdesign ikke udføres uden brug af boolsk algebra.

Logisk element er et kredsløb, der implementerer de logiske operationer af disjunktion, konjunktion og inversion. Lad os overveje implementeringen af ​​logiske elementer gennem elektriske relæ-kontaktkredsløb, du kender fra et skolefysikkursus.

Seriel forbindelse af kontakter

Parallelforbindelse af kontakter

Lad os kompilere en tabel over afhængigheder af kredsløbstilstanden på alle mulige tilstande af kontakterne. Lad os introducere følgende notationer: 1 - kontakten er lukket, der er strøm i kredsløbet; 0 – kontakten er åben, der er ingen strøm i kredsløbet.

Som du kan se, svarer et kredsløb med en seriel forbindelse til den logiske drift af forbindelsen, da strøm i kredsløbet kun vises, når kontakterne A og B er lukket samtidigt. Et kredsløb med en parallelforbindelse svarer til den logiske drift af disjunktion, da der kun er nogen strøm i kredsløbet i det øjeblik, hvor begge kontakter er åbne.

Den logiske operation af inversion implementeres gennem kontaktkredsløbet af et elektromagnetisk relæ, hvis princip studeres i et skolefysikkursus. Kontakt x er åben, når x er lukket og omvendt.

Brugen af ​​relækontaktelementer til at konstruere logiske kredsløb af computere har ikke retfærdiggjort sig selv på grund af lav pålidelighed, store dimensioner, højt strømforbrug og lav ydeevne. Fremkomsten af ​​elektroniske enheder (vakuum og halvleder) har skabt muligheden for at konstruere logiske elementer med hastigheder på 1 million koblinger pr. sekund og højere. Halvlederlogiske elementer fungerer i switch-tilstand svarende til et elektromagnetisk relæ. Hele teorien præsenteret for kontaktkredsløb overføres til halvlederelementer. Logiske elementer på halvledere er ikke kendetegnet ved kontakternes tilstand, men af ​​tilstedeværelsen af ​​signaler ved input og output.

Lad os overveje logiske elementer, der implementerer grundlæggende logiske operationer:

diagram svarende til funktionen:

&F(X, Y, Z)

Løsning af problemer ved hjælp af konjunktiv normal

Og disjunktiv-normal formularer

I Logiske problembøger indeholder ofte standardproblemer, hvor du skal skrive en funktion, der implementerer ladderdiagram, forenkle det og konstruer en sandhedstabel for denne funktion. Hvordan løses det omvendte problem? Givet en vilkårlig sandhedstabel, skal du bygge et funktionelt diagram eller et relædiagram. Vi vil behandle dette spørgsmål i dag.

Enhver logisk algebrafunktion kan repræsenteres af en kombination af tre operationer: konjunktion, disjunktion og inversion. Lad os finde ud af, hvordan dette gøres. For at gøre dette, lad os nedskrive et par definitioner.

Et minterm er en funktion dannet af sammensætningen af ​​et bestemt antal variable eller deres negationer. Minterm tager værdien 1 for det eneste af alle mulige sæt

argumenter, og værdien er 0 for alle andre. Eksempel: x 1 x 2 x 3 x 4 .

En maxterm er en funktion dannet af disjunktionen af ​​et bestemt antal variable eller deres negationer. Maxterm tager værdien 0 i et af de mulige sæt og 1 i alle andre.

Eksempel: x 1 + x 2 + x 3.

Funktion i disjunktiv normalform(DNF) er den logiske sum af minterms.

Eksempel: x 1x 2+ x 1x 2+ x 1x 2x 3.

Konjunktiv normalform(CNF) er et logisk produkt af elementære disjunktioner (maxterms).

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

Perfekt disjunktiv normalform kaldes en DNF, hvor alle variabler eller deres negationer er til stede i hvert minterm.

Eksempel: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Perfekt konjunktiv normalform kaldes CNF, i hvert maxterm, hvoraf alle variabler eller deres negationer er til stede.

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

At skrive en logisk funktion fra en tabel

Enhver logisk funktion kan udtrykkes som SDNF eller SCNF. Som et eksempel kan du overveje funktionen f præsenteret i tabellen.

Funktionerne G0, G1, G4, G5, G7 er minterms (se definition). Hver af disse funktioner er produktet af tre variable eller deres inverse og tager kun værdien 1 i én situation. Det kan ses, at for at få 1 i værdien af ​​funktionen f, skal der et minterm. Følgelig er antallet af minterms, der udgør SDNF for denne funktion, lig med antallet af enheder i funktionsværdien: f= G0+G1+G4+G5+G7. SDNF har således formen:

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

På samme måde kan du bygge SKNF. Antallet af faktorer er lig med antallet af nuller i funktionsværdierne:

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

Enhver logisk funktion givet i form af en tabel kan således skrives som en formel.

Algoritme til at konstruere SDNF ved hjælp af en sandhedstabel

En sandhedstabel af en eller anden funktion er givet. For at opbygge en SDNF skal du udføre følgende sekvens af trin:

1. Vælg alle tabelrækker, hvor funktionen har værdien 1.

2. Tildel for hver sådan linje en konjunktion af alle argumenter eller deres inversioner (minterm). I dette tilfælde er argumentet med værdien 0 inkluderet i mintermen med negation, og værdien 1 er inkluderet uden negation.

3. Til sidst danner vi disjunktionen af ​​alle de opnåede minterms. Antallet af minterms skal svare til antallet af enheder i den logiske funktion.

Algoritme til at konstruere SCNF ved hjælp af en sandhedstabel

En sandhedstabel af en eller anden funktion er givet. For at bygge SKNF skal du udføre følgende sekvens af trin:

1. Vælg alle rækker i tabellen, hvor funktionen har værdien 0.

2. Tildel for hver sådan linje en disjunktion af alle argumenter eller deres inversioner (maxterm). I dette tilfælde er et argument med værdien 1 inkluderet i maxtermen med negation, og værdien 1 er inkluderet uden negation.

3. Til sidst danner vi konjunktionen af ​​alle de opnåede maxterms. Antallet af maxterms skal svare til antallet af nuller i den logiske funktion.

Hvis vi fra to former (SDNF eller SKNF) er enige om at give fortrinsret til den, der indeholder færre bogstaver, så er SDNF at foretrække, hvis der er færre blandt værdierne af sandhedstabelfunktionen, SKNF - hvis der er færre nuller.

Eksempel. Sandhedstabellen for en logisk funktion af tre variable er givet. Konstruer en logisk formel, der implementerer denne funktion.

Lad os vælge de rækker i denne sandhedstabel, hvor funktionsværdien er 0.

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

Lad os tjekke den afledte funktion ved at oprette en sandhedstabel.

Ved at sammenligne de indledende og afsluttende sandhedstabeller kan vi konkludere, at den logiske funktion er konstrueret korrekt.

Problemløsning

1. Tre lærere udvælger problemer til olympiaden. Der er flere opgaver at vælge imellem. For hver opgave udtrykker hver lærer sin mening: en let (0) eller svær (1) opgave. En opgave indgår i olympiadeopgaven, hvis mindst to lærere markerer den som svær, men hvis alle tre lærere anser den for svær, så indgår sådan en opgave ikke i olympiadeopgaven som for svær. Lav et logisk diagram over en enhed, der udsender 1, hvis opgaven er inkluderet i Olympiade-opgaven, og 0, hvis den ikke er inkluderet.

Lad os bygge en sandhedstabel til den ønskede funktion. Vi har tre inputvariable (tre lærere). Derfor vil den nødvendige funktion være en funktion af tre variable.

Ved at analysere problemtilstanden får vi følgende sandhedstabel:

Vi bygger SDNF. F(A, B, C) = ABC+ ABC+ ABC

Nu bygger vi et logisk diagram over denne funktion.

B&1F(A,B,C)

2. Byolympiade i datalogi grundforløb, 2007.Byg et elektrisk kredsløbsdiagram for indgangen til et tre-etagers hus, således at en kontakt på enhver etage kan tænde eller slukke lyset i hele huset.

Så vi har tre kontakter, som vi skal bruge til at tænde og slukke lyset. Hver kontakt har to tilstande: op (0) og ned (1). Lad os antage, at hvis alle tre kontakter er i position 0, er lysene i indgangen slukket. Når du derefter flytter en af ​​de tre kontakter til position 1, bør lyset i indgangen lyse op. Når du flytter en hvilken som helst anden kontakt til position 1, vil lyset i indgangen naturligvis slukke. Hvis den tredje kontakt skiftes til position 1, tændes lyset i indgangen. Vi bygger en sandhedstabel.

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

Bemærk. For at løse dette problem skal du huske følgende logiske formler:

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

x ↔ y= x y+ x y

Vi får en logisk funktion af tre variable F 1 (A, B, C) = C → A + B = C + A B.

Lad os ændre variablerne B og C samtidigt: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Lad os bygge sandhedstabeller for disse to funktioner:

Lad os analysere den resulterende tabel. Af de otte rækker i tabellen er det kun i to (2. og 3.) funktionen, der ikke ændrer sin værdi. Bemærk, at på disse linjer vender variabel A ikke sin værdi, men det gør variable B og C.

Vi bygger SKNF-funktioner ved hjælp af disse linjer:

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

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

Derfor er det ønskede svar 4.

4. Betingelse for at ændre værdien af ​​en logisk funktion F (A, B, C) = C + AB, mens argumenterne A og B samtidigt ændres, er lig med:

Lad os analysere den resulterende tabel. Af de otte rækker i tabellen er det kun i to (1. og 7.) funktionen, der ændrer sin værdi. Bemærk venligst, at i disse linjer ændrer variabel C ikke sin værdi, men det gør variable A og B.

Vi bygger SDNF-funktioner ved hjælp af disse linjer:

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

Derfor er det nødvendige svar 2.

Referencer

1. Shapiro S.I. Løsning af logiske problemer og spilproblemer(logiske og psykologiske undersøgelser). – M.: Radio og kommunikation, 1984. – 152 s.

2. Sholomov L.A. Grundlæggende om teorien om diskrete logiske og computerenheder. – M.: Videnskab. Ch. udg. fysisk - mat. lit., 1980. - 400 s.

3. Pukhalsky G.I., Novoseltseva T.Ya. Design af diskrete enheder på integrerede kredsløb: Håndbog. – M.: Radio og kommunikation, 1990.

Metoder til løsning af logiske ligningssystemer

Kirgizova E.V., Nemkova A.E.

Lesosibirsk Pædagogiske Institut –

afdeling af Siberian Federal University, Rusland

Evnen til at tænke konsekvent, ræsonnere overbevisende, bygge hypoteser og tilbagevise negative konklusioner kommer ikke af sig selv; denne færdighed er udviklet af videnskaben om logik. Logik er en videnskab, der studerer metoder til at fastslå sandheden eller falskheden af ​​nogle udsagn på grundlag af sandheden eller falskheden af ​​andre udsagn.

At mestre det grundlæggende i denne videnskab er umuligt uden at løse logiske problemer. Afprøvning af udviklingen af ​​færdigheder til at anvende sin viden i en ny situation udføres gennem beståelse. Dette er især evnen til at løse logiske problemer. Opgaver B15 i Unified State Examination er opgaver med øget kompleksitet, da de indeholder systemer af logiske ligninger. Der er forskellige måder at løse logiske ligningssystemer på. Dette er reduktion til én ligning, konstruktion af en sandhedstabel, dekomponering, sekventiel løsning af ligninger osv.

Opgave:Løs et system af logiske ligninger:

Lad os overveje reduktionsmetode til én ligning . Denne metode involverer transformation af logiske ligninger, så deres højre side er lig med sandhedsværdien (det vil sige 1). For at gøre dette skal du bruge den logiske negationsoperation. Så, hvis ligningerne indeholder komplekse logiske operationer, erstatter vi dem med grundlæggende: "AND", "OR", "NOT". Det næste trin er at kombinere ligningerne til én, svarende til systemet, ved hjælp af den logiske operation "AND". Efter dette skal du transformere den resulterende ligning baseret på lovene i logisk algebra og opnå en specifik løsning til systemet.

Løsning 1:Anvend inversion på begge sider af den første ligning:

Lad os forestille os implikationen gennem de grundlæggende operationer "ELLER" og "NOT":

Da de venstre sider af ligningerne er lig med 1, kan vi kombinere dem ved at bruge "AND"-operationen til en ligning, der svarer til det oprindelige system:

Vi åbner den første parentes i henhold til De Morgans lov og transformerer det opnåede resultat:

Den resulterende ligning har én løsning: A= 0, B=0 og C=1.

Den næste metode er at konstruere sandhedstabeller . Da logiske størrelser kun har to værdier, kan du blot gennemgå alle mulighederne og blandt dem finde dem, for hvilke et givet ligningssystem er opfyldt. Det vil sige, at vi bygger én fælles sandhedstabel for alle systemets ligninger og finder en linje med de nødvendige værdier.

Løsning 2:Lad os oprette en sandhedstabel for systemet:

Linjen, for hvilken opgavebetingelserne er opfyldt, er fremhævet med fed skrift. Så A =0, B =0 og C =1.

Vej nedbrydning . Ideen er at fiksere værdien af ​​en af ​​variablerne (sæt den lig med 0 eller 1) og derved forenkle ligningerne. Derefter kan du rette værdien af ​​den anden variabel, og så videre.

Løsning 3: Lade A = 0, så:

Fra den første ligning får vi B =0, og fra anden – C=1. Løsning af systemet: A = 0, B = 0 og C = 1.

Du kan også bruge metoden sekventiel løsning af ligninger , ved hvert trin at tilføje en variabel til det pågældende sæt. For at gøre dette er det nødvendigt at transformere ligningerne, så variablerne indtastes i alfabetisk rækkefølge. Dernæst bygger vi et beslutningstræ og tilføjer sekventielt variabler til det.

Systemets første ligning afhænger kun af A og B, og den anden ligning af A og C. Variabel A kan have 2 værdier 0 og 1:

Af den første ligning følger det , derfor hvornår A = 0 og vi får B = 0, og for A = 1 har vi B = 1. Så den første ligning har to løsninger med hensyn til variablerne A og B.

Lad os afbilde den anden ligning, hvorfra vi bestemmer værdierne af C for hver mulighed. Når A =1, kan implikationen ikke være falsk, det vil sige, at den anden gren af ​​træet ikke har nogen løsning. På A= 0 vi får den eneste løsning C= 1 :

Således fik vi løsningen til systemet: A = 0, B = 0 og C = 1.

I Unified State Exam i datalogi er det meget ofte nødvendigt at bestemme antallet af løsninger til et system af logiske ligninger uden at finde selve løsningerne; der er også visse metoder til dette. Den vigtigste måde at finde antallet af løsninger til et system af logiske ligninger på er erstatte variabler. Først skal du forenkle hver af ligningerne så meget som muligt baseret på lovene i logisk algebra, og derefter erstatte de komplekse dele af ligningerne med nye variable og bestemme antallet af løsninger til det nye system. Vend derefter tilbage til erstatningen og bestem antallet af løsninger til den.

Opgave:Hvor mange løsninger har ligningen ( A → B ) + (C → D ) = 1? Hvor A, B, C, D er logiske variable.

Løsning:Lad os introducere nye variabler: X = A → B og Y = C → D . Under hensyntagen til de nye variabler vil ligningen blive skrevet som: X + Y = 1.

Disjunktionen er sand i tre tilfælde: (0;1), (1;0) og (1;1), mens X og Y er en implikation, det vil sige, at det er sandt i tre tilfælde og falsk i ét tilfælde. Derfor vil tilfældet (0;1) svare til tre mulige kombinationer af parametre. Tilfælde (1;1) – vil svare til ni mulige kombinationer af parametre i den oprindelige ligning. Det betyder, at de samlede mulige løsninger til denne ligning er 3+9=15.

Den næste måde at bestemme antallet af løsninger til et system af logiske ligninger er binært træ. Lad os se på denne metode ved hjælp af et eksempel.

Opgave:Hvor mange forskellige løsninger har systemet af logiske ligninger:

Det givne ligningssystem svarer til ligningen:

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

Lad os lade som omx 1 – er sandt, så får vi det ud fra den første ligningx 2 også sandt, fra den anden -x 3 =1, og så videre indtil x m= 1. Så mængden (1; 1; …; 1) af m enheder er systemets løsning. Lad det nux 1 =0, så fra den første ligning vi harx 2 =0 eller x 2 =1.

Hvornår x 2 sandt, opnår vi, at de resterende variable også er sande, det vil sige, at mængden (0; 1; ...; 1) er en løsning på systemet. Påx 2 =0 det får vi x 3 =0 eller x 3 =, og så videre. Fortsætter vi til den sidste variabel finder vi, at løsningerne til ligningen er følgende sæt af variable ( m +1 opløsning, i hver opløsning m variabelværdier):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Denne tilgang er godt illustreret ved at konstruere et binært træ. Antallet af mulige løsninger er antallet af forskellige grene af det konstruerede træ. Det er let at se, at det er lige m+1.

I tilfælde af vanskeligheder med at ræsonnere og bygge et beslutningstræ, kan du søge efter en løsning vha sandhedstabeller, for en eller to ligninger.

Lad os omskrive ligningssystemet på formen:

Og lad os oprette en sandhedstabel separat for én ligning:

Lad os lave en sandhedstabel for to ligninger:

Dernæst kan du se, at én ligning er sand i følgende tre tilfælde: (0; 0), (0; 1), (1; 1). Et system med to ligninger er sandt i fire tilfælde (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). I dette tilfælde er det umiddelbart klart, at der er en løsning, der kun består af nuller og mere m løsninger, hvor der tilføjes en enhed ad gangen, startende fra sidste position, indtil alle mulige pladser er besat. Det kan antages, at den generelle løsning vil have samme form, men for at en sådan tilgang kan blive en løsning, kræves bevis for, at antagelsen er korrekt.

For at opsummere alt ovenstående vil jeg gerne henlede din opmærksomhed på det faktum, at ikke alle de diskuterede metoder er universelle. Når man løser hvert system af logiske ligninger, skal man tage hensyn til dets funktioner, på grundlag af hvilke løsningsmetoden skal vælges.

Litteratur:

1. Logiske problemer / O.B. Bogomolov – 2. udg. – M.: BINOM. Videnslaboratorium, 2006. – 271 s.: ill.

2. Polyakov K.Yu. Systemer af logiske ligninger / Uddannelses- og metodeavis for datalogilærere: Informatik nr. 14, 2011.

Lektionens emne: Løsning af logiske ligninger

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:

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

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.

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.

Sådan løses nogle problemer i afsnit A og B i datalogi eksamen

Lektion #3. Logikker. Logiske funktioner. Løsning af ligninger

Et stort antal Unified State Exam-problemer er afsat til propositionel logik. For at løse de fleste af dem er det nok at kende de grundlæggende love for propositionel logik, viden om sandhedstabellerne for logiske funktioner af en og to variable. Jeg vil give de grundlæggende love for propositionel logik.

1. Kommutativitet af disjunktion og konjunktion:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distributiv lov vedrørende disjunktion og konjunktion:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negation af negation:
   ¬(¬a) ≡ a
4. Konsistens:
   a ^ ¬а ≡ falsk
5. Eksklusiv tredje:
   a ˅ ¬а ≡ sand
6. De Morgans love:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Forenkling:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ sand ≡ a
   a ˄ falsk ≡ falsk
8. Absorption:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Udskiftning af implikation
   a → b ≡ ¬a ˅ b
10. Udskiftning af identitet
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Repræsentation af logiske funktioner

Enhver logisk funktion af n variable - F(x 1, x 2, ... x n) kan specificeres af en sandhedstabel. En sådan tabel indeholder 2n sæt af variable, for hver af hvilke værdien af ​​en funktion i dette sæt er angivet. Denne metode er god, når antallet af variable er relativt lille. Allerede for n > 5 bliver repræsentationen dårligt synlig.

En anden måde er at definere funktionen ved hjælp af en formel ved hjælp af kendte ret simple funktioner. Et system af funktioner (f 1, f 2, ... f k) kaldes komplet, hvis en logisk funktion kan udtrykkes med en formel, der kun indeholder funktioner fi.

Funktionssystemet (¬, ˄, ˅) er komplet. Love 9 og 10 er eksempler, der viser, hvordan implikation og identitet udtrykkes gennem negation, konjunktion og disjunktion.

Faktisk er et system med to funktioner – negation og konjunktion eller negation og disjunktion – også komplet. Fra De Morgans love følger ideer, der tillader en at udtrykke en konjunktion gennem negation og disjunktion og følgelig at udtrykke en disjunktion gennem negation og konjunktion:

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

Paradoksalt nok er et system bestående af kun én funktion komplet. Der er to binære funktioner - antikonjunktion og antidisjunktion, kaldet Peirce-pilen og Schaeffer-slaget, der repræsenterer et hult system.

De grundlæggende funktioner i programmeringssprog inkluderer normalt identitet, negation, konjunktion og disjunktion. I Unified State Examination problemer, sammen med disse funktioner, findes ofte implikationer.

Lad os se på nogle få simple problemer, der involverer logiske funktioner.

Opgave 15:

Et fragment af sandhedstabellen er givet. Hvilken af ​​de tre angivne funktioner svarer til dette fragment?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funktion nummer 3.

For at løse problemet skal du kende sandhedstabellerne over grundlæggende funktioner og huske prioriteterne for operationer. Lad mig minde dig om, at konjunktion (logisk multiplikation) har højere prioritet og udføres tidligere end disjunktion (logisk addition). Under beregninger er det let at bemærke, at funktioner med tallene 1 og 2 i det tredje sæt har værdien 1 og af denne grund ikke svarer til fragmentet.

Opgave 16:

Hvilket af de givne tal opfylder betingelsen:

(cifre, startende fra det mest signifikante ciffer, er i faldende rækkefølge) → (tal - lige) ˄ (lavt ciffer - lige) ˄ (højt ciffer - ulige)

Hvis der er flere sådanne tal, angives det største.

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

Betingelsen er opfyldt med tallet 4.

De to første tal opfylder ikke betingelsen af ​​den grund, at det laveste ciffer er ulige. En konjunktion af betingelser er falsk, hvis en af ​​vilkårene i konjunktionen er falsk. For det tredje tal er betingelsen for det højeste ciffer ikke opfyldt. For det fjerde nummer er betingelserne for de lave og høje cifre i nummeret opfyldt. Det første led i konjunktionen er også sandt, eftersom implikationen er sand, hvis dens forudsætning er falsk, hvilket er tilfældet her.

Opgave 17: To vidner afgav følgende vidnesbyrd:

Første vidne: Hvis A er skyldig, så er B endnu mere skyldig, og C er uskyldig.

Andet vidne: To er skyldige. Og en af ​​de tilbageværende er bestemt skyldig og skyldig, men jeg kan ikke sige hvem præcist.

Hvilke konklusioner om skylden hos A, B og C kan drages ud fra vidneforklaringen?

Svar: Af vidneforklaringen følger, at A og B er skyldige, og C er uskyldig.

Løsning: Selvfølgelig kan svaret gives ud fra sund fornuft. Men lad os se på, hvordan dette kan gøres strengt og formelt.

Den første ting at gøre er at formalisere udtalelserne. Lad os introducere tre logiske variable - A, B og C, som hver har værdien sand (1), hvis den tilsvarende mistænkte er skyldig. Derefter afgives det første vidnes vidnesbyrd med formlen:

A → (B ˄ ¬C)

Det andet vidnes vidnesbyrd er givet ved formlen:

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

Begge vidners vidnesbyrd antages at være sande og repræsenterer sammensætningen af ​​de tilsvarende formler.

Lad os bygge en sandhedstabel for disse læsninger:

Det summariske bevis er kun sandt i én sag, hvilket fører til et klart svar - A og B er skyldige, og C er uskyldig.

Af analysen af ​​denne tabel følger det også, at det andet vidnes vidnesbyrd er mere informativt. Ud fra sandheden af ​​hans vidnesbyrd følger kun to mulige muligheder - A og B er skyldige, og C er uskyldige, eller A og C er skyldige, og B er uskyldige. Det første vidnes forklaring er mindre informativt - der er 5 forskellige muligheder svarende til hans forklaring. Tilsammen giver begge vidners forklaring et klart svar om de mistænktes skyld.

Logiske ligninger og ligningssystemer

Lad F(x 1, x 2, …x n) være en logisk funktion af n variable. Den logiske ligning ser således ud:

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

Konstanten C har værdien 1 eller 0.

En logisk ligning kan have fra 0 til 2 n forskellige løsninger. Hvis C er lig med 1, så er løsningerne alle de sæt af variabler fra sandhedstabellen, for hvilke funktionen F tager værdien sand (1). De resterende mængder er løsninger af ligningen med C lig med nul. Du kan altid kun overveje formens ligninger:

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

Faktisk, lad ligningen gives:

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

I dette tilfælde kan vi gå til den ækvivalente ligning:

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

Overvej et system af k logiske ligninger:

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

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

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

Løsningen til et system er et sæt variabler, hvorpå alle systemets ligninger er opfyldt. Med hensyn til logiske funktioner, for at opnå en løsning på et system af logiske ligninger, bør man finde et sæt, hvor den logiske funktion Ф er sand, der repræsenterer konjunktionen af ​​de oprindelige funktioner F:

Ф = F 1 ˄ F 2 ˄ … F k

Hvis antallet af variable er lille, for eksempel mindre end 5, så er det ikke svært at konstruere en sandhedstabel for funktionen Ф, som giver os mulighed for at sige, hvor mange løsninger systemet har, og hvilke mængder der giver løsninger.

I nogle USE-problemer med at finde løsninger på et system af logiske ligninger, når antallet af variabler 10. Så bliver det en næsten umulig opgave at konstruere en sandhedstabel. At løse problemet kræver en anden tilgang. For et vilkårligt ligningssystem er der ingen generel metode udover opregning, der tillader løsning af sådanne problemer.

I de problemer, der foreslås til eksamen, er løsningen normalt baseret på at tage højde for de særlige forhold ved ligningssystemet. Jeg gentager, bortset fra at prøve alle mulighederne for et sæt variabler, er der ingen generel måde at løse problemet på. Løsningen skal bygges ud fra systemets specifikationer. Det er ofte nyttigt at udføre en foreløbig forenkling af et ligningssystem ved hjælp af kendte logiske love. En anden nyttig teknik til at løse dette problem er som følger. Vi er ikke interesserede i alle mængder, men kun dem, hvor funktionen Ф har værdien 1. I stedet for at bygge en komplet sandhedstabel, vil vi bygge dens analog - et binært beslutningstræ. Hver gren af ​​dette træ svarer til én løsning og angiver et sæt, hvor funktionen Ф har værdien 1. Antallet af grene i beslutningstræet falder sammen med antallet af løsninger til ligningssystemet.

Jeg vil forklare, hvad et binært beslutningstræ er, og hvordan det er bygget ved hjælp af eksempler på flere problemer.

Opgave 18

Hvor mange forskellige værdisæt af de logiske variable x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 er der, der opfylder systemet med to ligninger?

Svar: Systemet har 36 forskellige løsninger.

Løsning: Ligningssystemet omfatter to ligninger. Lad os finde antallet af løsninger til den første ligning, afhængigt af 5 variable - x 1, x 2, ...x 5. Den første ligning kan igen betragtes som et system af 5 ligninger. Som det er blevet vist, repræsenterer ligningssystemet faktisk sammensætningen af ​​logiske funktioner. Det omvendte er også sandt: en konjunktion af betingelser kan betragtes som et ligningssystem.

Lad os bygge et beslutningstræ for implikationen (x1→ x2) - det første led i konjunktionen, som kan betragtes som den første ligning. Sådan ser en grafisk gengivelse af dette træ ud:

Træet består af to niveauer i henhold til antallet af variable i ligningen. Det første niveau beskriver den første variabel X 1 . To grene af dette niveau afspejler de mulige værdier af denne variabel - 1 og 0. På det andet niveau afspejler træets grene kun de mulige værdier af variablen X 2, for hvilke ligningen er sand. Da ligningen angiver en implikation, kræver en gren, hvor X 1 har værdien 1, at X 2 på den gren har værdien 1. En gren, hvor X 1 har værdien 0, producerer to grene med værdierne X 2 lig med 0 og 1 Det konstruerede træ definerer tre løsninger, hvor implikationen X 1 → X 2 tager værdien 1. På hver gren er et tilsvarende sæt af variable værdier skrevet ud, hvilket giver en løsning til ligningen.

Disse sæt er: ((1, 1), (0, 1), (0, 0))

Lad os fortsætte med at bygge beslutningstræet ved at tilføje følgende ligning, følgende implikation X 2 → X 3 . Det specifikke ved vores ligningssystem er, at hver ny ligning i systemet bruger en variabel fra den forrige ligning, og tilføjer en ny variabel. Da variablen X 2 allerede har værdier i træet, vil variablen X 3 på alle grene, hvor variablen X 2 har en værdi på 1, også have en værdi på 1. For sådanne grene gælder træets konstruktion. fortsætter til næste niveau, men nye grene dukker ikke op. Den enkelte gren, hvor variablen X 2 har værdien 0, vil forgrene sig i to grene, hvor variablen X 3 vil modtage værdierne 0 og 1. Således tilføjer hver tilføjelse af en ny ligning, givet dens detaljer, én løsning. Original første ligning:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
har 6 løsninger. Sådan ser det komplette beslutningstræ for denne ligning ud:

Den anden ligning i vores system ligner den første:

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

Den eneste forskel er, at ligningen bruger Y-variable. Denne ligning har også 6 løsninger. Da hver løsning for variablerne X i kan kombineres med hver løsning for variablerne Y j , er det samlede antal løsninger 36.

Bemærk venligst, at det konstruerede beslutningstræ ikke kun angiver antallet af løsninger (i henhold til antallet af grene), men også selve løsningerne skrevet på hver gren af ​​træet.

Opgave 19

Hvor mange forskellige værdisæt af de logiske variable x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 er der, der opfylder alle betingelserne anført nedenfor?

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

Denne opgave er en ændring af den tidligere opgave. Forskellen er, at der tilføjes en anden ligning, der relaterer variablerne X og Y.

Af ligningen X 1 → Y 1 følger det, at når X 1 har værdien 1 (der findes en sådan løsning), så har Y 1 også værdien 1. Der er således et sæt, hvor X 1 og Y 1 har værdierne 1. Når X 1 er lig med 0, kan Y 1 have en hvilken som helst værdi, både 0 og 1. Derfor svarer hvert sæt med X 1 lig med 0, og der er 5 sådanne sæt, til alle 6 sæt med Y-variable. Derfor er det samlede antal løsninger 31 .

Opgave 20

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

Løsning: Når vi husker de grundlæggende ækvivalenser, skriver vi vores ligning som:

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

Den cykliske kæde af implikationer betyder, at variablerne er identiske, så vores ligning svarer til ligningen:

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

Denne ligning har to løsninger, når alle X i er enten 1 eller 0.

Opgave 21

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

Løsning: Ligesom i opgave 20 bevæger vi os fra cykliske implikationer til identiteter og omskriver ligningen i formen:

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

Lad os bygge et beslutningstræ for denne ligning:

Opgave 22

Hvor mange løsninger har følgende ligningssystem?

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

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

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

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

Svar: 64

Løsning: Lad os gå fra 10 variable til 5 variable ved at introducere følgende ændring af variable:

Y1 = (X1 ≡ X 2); Y2 = (X3 ≡ X 4); Y3 = (X5 ≡ X 6); Y4 = (X7 = X 8); Y5 = (X9 ≡ X 10);

Så vil den første ligning have formen:

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

Ligningen kan forenkles ved at skrive den som:

(Y 1 ≡ Y 2) = 0

Går vi videre til den traditionelle form, skriver vi systemet efter forenklinger i formularen:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Beslutningstræet for dette system er enkelt og består af to grene med skiftende variabelværdier:

For at vende tilbage til de oprindelige X-variabler, bemærk, at for hver værdi i Y-variablen er der 2 værdier i X-variablerne, så hver løsning i Y-variablerne genererer 2 5 løsninger i X-variablerne. De to grene genererer 2 * 2 5 løsninger, så det samlede antal løsninger er 64.

Som du kan se, kræver hvert problem med at løse et ligningssystem sin egen tilgang. En almindelig teknik er at udføre ækvivalente transformationer for at forenkle ligninger. En almindelig teknik er at konstruere beslutningstræer. Den anvendte tilgang minder delvist om at konstruere en sandhedstabel med den ejendommelighed, at ikke alle sæt af mulige værdier af variable er konstrueret, men kun dem, hvorpå funktionen tager værdien 1 (sand). Ofte i de foreslåede problemer er der ikke behov for at bygge et komplet beslutningstræ, da det allerede i den indledende fase er muligt at etablere mønsteret for udseendet af nye grene på hvert efterfølgende niveau, som det for eksempel blev gjort i opgave 18 .

Generelt er problemer med at finde løsninger på et system af logiske ligninger gode matematiske øvelser.

Hvis problemet er svært at løse manuelt, så kan du overlade løsningen til computeren ved at skrive et passende program til løsning af ligninger og ligningssystemer.

Det er ikke svært at skrive sådan et program. Et sådant program vil nemt klare alle de opgaver, der tilbydes i Unified State Exam.

Mærkeligt nok er opgaven med at finde løsninger på systemer med logiske ligninger vanskelig for en computer, og det viser sig, at en computer har sine grænser. Computeren kan ret nemt klare problemer, hvor antallet af variable er 20-30, men den vil begynde at tænke i lang tid på problemer af større størrelse. Faktum er, at funktionen 2 n, som angiver antallet af mængder, er en eksponentiel, der vokser hurtigt, når n stiger. Så hurtigt, at en almindelig personlig computer ikke kan klare en opgave, der har 40 variabler på en dag.

Program i C#-sprog til løsning af logiske ligninger

At skrive et program til at løse logiske ligninger er nyttigt af mange grunde, om end bare fordi du kan bruge det til at kontrollere rigtigheden af ​​din egen løsning på Unified State Exam-testproblemer. En anden grund er, at sådan et program er et glimrende eksempel på en programmeringsopgave, der opfylder kravene til kategori C opgaver i Unified State Exam.

Ideen om at bygge et program er enkel - det er baseret på en komplet søgning af alle mulige sæt af variable værdier. Da antallet af variable n for en given logisk ligning eller ligningssystem er kendt, så er antallet af sæt også kendt - 2 n som skal sorteres fra. Ved at bruge de grundlæggende funktioner i C#-sproget - negation, disjunktion, konjunktion og identitet, er det ikke svært at skrive et program, der for et givet sæt af variable beregner værdien af ​​den logiske funktion svarende til en logisk ligning eller ligningssystem .

I et sådant program skal du bygge en løkke baseret på antallet af sæt, i løkkens krop, ved hjælp af antallet af sættet, danne selve sættet, beregne værdien af ​​funktionen på dette sæt, og hvis dette værdien er 1, så giver mængden en løsning til ligningen.

Den eneste vanskelighed, der opstår ved implementering af programmet, er relateret til opgaven med at generere selve sættet af variable værdier baseret på det indstillede antal. Det smukke ved dette problem er, at denne tilsyneladende vanskelige opgave faktisk kommer ned til et simpelt problem, der allerede er opstået mange gange. Det er faktisk nok at forstå, at sættet af variable værdier, der svarer til tallet i, bestående af nuller og enere, repræsenterer den binære repræsentation af tallet i. Så den komplekse opgave med at opnå et sæt variable værdier efter sættal reduceres til den velkendte opgave at konvertere et tal til binært.

Sådan ser en funktion i C# ud, der løser vores problem:

///

///

/// logisk funktion - metode,

/// hvis underskrift er angivet af DF-delegerede

///

/// antallet af variable

/// antal løsninger

static int SolveEquations(DF fun, int n)

bool sæt = ny bool[n];

int m = (int)Math.Pow(2, n); //antal sæt

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

//Fuldfør søgning efter antal sæt

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

// Dannelse af det næste sæt - sæt,

//specificeret ved den binære repræsentation af tallet i

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

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

//Beregn værdien af ​​funktionen på sættet

For at forstå programmet håber jeg, at forklaringerne på programmets idé og kommentarerne i dets tekst er tilstrækkelige. Jeg vil kun fokusere på at forklare titlen på den givne funktion. Funktionen SolveEquations har to inputparametre. Fun-parameteren specificerer en logisk funktion, der svarer til den ligning eller ligningssystem, der løses. Parameteren n angiver antallet af sjove variable. Som et resultat returnerer funktionen SolveEquations antallet af løsninger af den logiske funktion, det vil sige antallet af de sæt, som funktionen evaluerer til sand.

Det er almindeligt for skolebørn, når en funktion F(x) har en inputparameter x, der er en variabel af aritmetisk, streng eller logisk type. I vores tilfælde bruges et mere kraftfuldt design. Funktionen SolveEquations refererer til funktioner af højere orden - funktioner af typen F(f), hvis parametre ikke kun kan være simple variabler, men også funktioner.

Klassen af ​​funktioner, der kan overføres som en parameter til funktionen SolveEquations, er specificeret som følger:

delegeret bool DF(bool vars);

Denne klasse ejer alle funktioner, der sendes som en parameter et sæt værdier af logiske variabler specificeret af vars-arrayet. Resultatet er en boolsk værdi, der repræsenterer værdien af ​​funktionen i dette sæt.

Endelig er her et program, der bruger SolveEquations-funktionen til at løse flere systemer af logiske ligninger. SolveEquations-funktionen er en del af ProgramCommon-klassen nedenfor:

klasse ProgramFælles

delegeret bool DF(bool vars);

statisk tomrum Main(streng args)

Console.WriteLine("Og funktioner - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Funktionen har 51 løsninger - " +

SolveEquations(Sjov51, 5));

Console.WriteLine("Funktionen har 53 løsninger - " +

SolveEquations(Fun53, 10));

statisk bool FunAnd(bool vars)

returner vars && vars;

statisk bool Fun51(bool vars)

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

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

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

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

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

statisk bool Fun53(bool vars)

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

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

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

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

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

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

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

Sådan ser løsningsresultaterne for dette program ud:

10 opgaver til selvstændigt arbejde

1. Hvilken af ​​de tre funktioner er ækvivalente:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Givet er et fragment af sandhedstabellen:

Hvilken af ​​de tre funktioner svarer dette fragment til:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Juryen består af tre personer. Beslutningen træffes, hvis nævningets formand stemmer herfor, støttet af mindst et af nævningemedlemmerne. Ellers tages der ingen beslutning. Konstruer en logisk funktion, der formaliserer beslutningsprocessen.
5. X vinder over Y, hvis fire møntkast resulterer i hoveder tre gange. Definer en logisk funktion, der beskriver udbetalingen af ​​X.
6. Ord i en sætning er nummereret fra én. En sætning anses for at være korrekt opbygget, hvis følgende regler er opfyldt:
   1. Hvis et ord med lige tal slutter med en vokal, så skal det næste ord, hvis det findes, begynde med en vokal.
   2. Hvis et ulige ord ender med en konsonant, så skal det næste ord, hvis det findes, begynde med en konsonant og slutte med en vokal.
      Hvilken af ​​følgende sætninger er korrekt konstrueret:
   3. Mor vaskede Masha med sæbe.
   4. En leder er altid en model.
   5. Sandheden er god, men lykke er bedre.
7. Hvor mange løsninger har ligningen:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Nævn alle løsninger til ligningen:
   (a → b) → c = 0
9. Hvor mange løsninger har følgende ligningssystem:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Hvor mange løsninger har ligningen:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Svar på problemer:

1. Funktionerne b og c er ækvivalente.
2. Fragmentet svarer til funktion b.
3. Lad den logiske variabel P tage værdien 1, når juryens formand stemmer "for" afgørelsen. Variablerne M 1 og M 2 repræsenterer jurymedlemmernes meninger. Den logiske funktion, der specificerer at træffe en positiv beslutning, kan skrives som følger:
   P ˄ (M 1 ˅ M 2)
4. Lad den logiske variabel P i tage værdien 1, når det i-te møntkast lander på hoveder. Den logiske funktion, der specificerer udbetalingen X, kan skrives som følger:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Sætning b.
6. Ligningen har 3 løsninger: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)