Løsning af logiske ligninger. Løs logisk ligning

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 ^ ¬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 2 n 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 er kendt for en given logisk ligning eller ligningssystem, så er antallet af sæt også kendt - 2 n som skal sorteres fra. Ved at bruge C#-sprogets grundlæggende funktioner - 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)

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.

Baseret på 2018 KIM-specifikationen indeholder denne blok fire opgaver med forskellige sværhedsgrader.

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:

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.

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).

Lad os lave en tabel for at beregne antallet af par på hvert trin.

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)

Instruktioner. Når du indtaster fra tastaturet, skal du bruge følgende konventioner:

Regler for indtastning af en logisk funktion

1. I stedet for v (disjunktion, OR)-symbolet skal du bruge +-tegnet.
2. Det er ikke nødvendigt at angive en funktionsbetegnelse før en logisk funktion. For eksempel, i stedet for F(x,y)=(x|y)=(x^y) skal du blot indtaste (x|y)=(x^y) .
3. Det maksimale antal variabler er 10.

Design og analyse af computerlogiske kredsløb udføres ved hjælp af en særlig gren af ​​matematik - logisk algebra. I logikkens algebra kan der skelnes mellem tre logiske hovedfunktioner: "NOT" (negation), "AND" (konjunktion), "OR" (disjunktion).
For at skabe en logisk enhed er det nødvendigt at bestemme afhængigheden af ​​hver af outputvariablerne af de eksisterende inputvariabler; denne afhængighed kaldes en omskiftningsfunktion eller en logisk algebrafunktion.
En logisk algebrafunktion kaldes fuldstændig defineret, hvis alle 2n af dens værdier er givet, hvor n er antallet af outputvariable.
Hvis ikke alle værdier er defineret, kaldes funktionen delvist defineret.
En enhed kaldes logisk, hvis dens tilstand er beskrevet ved hjælp af en logisk algebrafunktion.
Følgende metoder bruges til at repræsentere en logisk algebrafunktion:
I algebraisk form kan du bygge et kredsløb af en logisk enhed ved hjælp af logiske elementer.


Figur 1 - Logisk enhedsdiagram

Alle operationer i logikkens algebra er defineret sandhedstabeller værdier. Sandhedstabellen bestemmer resultatet af en operation for alle er mulige x logiske værdier af de originale udsagn. Antallet af muligheder, der afspejler resultatet af anvendelsen af ​​operationer, vil afhænge af antallet af udsagn i det logiske udtryk. Hvis antallet af udsagn i et logisk udtryk er N, vil sandhedstabellen indeholde 2 N rækker, da der er 2 N forskellige kombinationer af mulige argumentværdier.

Operation NOT - logisk negation (inversion)

• hvis det oprindelige udtryk er sandt, så vil resultatet af dets negation være falsk;
• hvis det oprindelige udtryk er falsk, så vil resultatet af dets negation være sandt.

ELLER-operation - logisk addition (disjunktion, forening)

Operation OG - logisk multiplikation (konjunktion)

Operation "HVIS-SÅ" - logisk konsekvens (implikation)

Operation "A hvis og kun hvis B" (ækvivalens, ækvivalens)

Operation "Addition modulo 2" (XOR, eksklusiv eller, streng disjunktion)

Prioritet af logiske operationer

• Handlinger i parentes
• Inversion
• Konjunktion (&)
• Disjunktion (V), Eksklusiv ELLER (XOR), sum modulo 2
• Implikation (→)
• Ækvivalens (↔)

Perfekt disjunktiv normalform

1. Hvert logisk led i formlen indeholder alle de variable, der indgår i funktionen F(x 1,x 2,...x n).
2. Alle logiske udtryk i formlen er forskellige.
3. Ikke et enkelt logisk udtryk indeholder en variabel og dens negation.
4. Intet logisk led i en formel indeholder den samme variabel to gange.

Perfekt konjunktiv normalform

1. Alle elementære disjunktioner indeholder alle de variable, der indgår i funktionen F(x 1 ,x 2 ,...x n).
2. Alle elementære disjunktioner er forskellige.
3. Hver elementær disjunktion indeholder en variabel én gang.
4. Ikke en enkelt elementær disjunktion indeholder en variabel og dens negation.

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, hvor J, K, L, M, N er logiske variable?

Løsning.

Udtrykket (N ∨ ¬N) er derfor sandt for enhver N

J ∧ ¬K ∧ L ∧ ¬M = 0.

Lad os anvende negation på begge sider af den logiske ligning og bruge De Morgans lov ¬ (A ∧ B) = ¬ A ∨ ¬ B. Vi får ¬J ∨ K ∨ ¬L ∨ M = 1.

En logisk sum er lig med 1, hvis mindst et af dets konstituerende udsagn er lig med 1. Derfor er den resulterende ligning opfyldt af enhver kombination af logiske variable undtagen tilfældet, hvor alle mængder inkluderet i ligningen er lig med 0. Hver af de 4 variable kan være lig med enten 1 eller 0, derfor er alle mulige kombinationer 2·2·2·2 = 16. Derfor har ligningen 16 −1 = 15 løsninger.

Det er tilbage at bemærke, at de 15 fundne løsninger svarer til enhver af de to mulige værdier af den logiske variabel N, så den oprindelige ligning har 30 løsninger.

Svar: 30

Hvor mange forskellige løsninger har ligningen?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

hvor J, K, L, M, N er logiske variable?

Svaret behøver ikke at angive alle de forskellige værdisæt af J, K, L, M og N, som denne lighed gælder for. Som svar skal du angive antallet af sådanne sæt.

Løsning.

Vi bruger formlerne A → B = ¬A ∨ B og ¬(A ∨ B) = ¬A ∧ ¬B

Lad os overveje den første underformel:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Lad os overveje den anden underformel

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬

Lad os overveje den tredje underformel

1) M → J = 1 derfor,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Lad os kombinere:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 deraf 4 løsninger.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Lad os kombinere:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L derfor 4 løsninger.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Svar: 4 + 4 = 8.

Svar: 8

Hvor mange forskellige løsninger har ligningen?

((K ∨ L) → (L ∧ M ∧ N)) = 0

hvor K, L, M, N er logiske variable? Svaret behøver ikke at angive alle de forskellige værdisæt af K, L, M og N, som denne lighed gælder for. Som svar skal du angive antallet af sådanne sæt.

Løsning.

Lad os omskrive ligningen ved hjælp af enklere notation for operationer:

((K + L) → (L M N)) = 0

1) fra sandhedstabellen for "implikationsoperationen" (se det første problem) følger det, at denne lighed er sand, hvis og kun hvis på samme tid

K + L = 1 og L M N = 0

2) af den første ligning følger det, at mindst én af variablerne, K eller L, er lig med 1 (eller begge sammen); så lad os overveje tre tilfælde

3) hvis K = 1 og L = 0, så er den anden lighed opfyldt for enhver M og N; da der er 4 kombinationer af to boolske variable (00, 01, 10 og 11), har vi 4 forskellige løsninger

4) hvis K = 1 og L = 1, så gælder den anden lighed for M · N = 0; der er 3 sådanne kombinationer (00, 01 og 10), vi har 3 flere løsninger

5) hvis K = 0, så er L = 1 (fra den første ligning); i dette tilfælde er den anden lighed opfyldt, når M · N = 0; der er 3 sådanne kombinationer (00, 01 og 10), vi har 3 flere løsninger

6) i alt får vi 4 + 3 + 3 = 10 løsninger.

Svar: 10

Hvor mange forskellige løsninger har ligningen?

(K ∧ L) ∨ (M ∧ N) = 1

Løsning.

Udtrykket er sandt i tre tilfælde, når (K ∧ L) og (M ∧ N) er lig med henholdsvis 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N er lig med 1, og K og L er alt undtagen samtidig 1. Derfor er der 3 løsninger.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 opløsning.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 løsninger.

Svar: 7.

Svar: 7

Hvor mange forskellige løsninger har ligningen?

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0

hvor X, Y, Z, P er logiske variable? Svaret behøver ikke at angive alle de forskellige værdisæt, som denne lighed gælder. Som svar skal du kun angive antallet af sådanne sæt.

Løsning.

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z)∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Logisk ELLER er kun falsk i ét tilfælde: når begge udtryk er falske.

Derfor,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Derfor er der kun én løsning på ligningen.

Svar: 1

Hvor mange forskellige løsninger har ligningen?

(K ∨ L) ∧ (M ∨ N) = 1

hvor K, L, M, N er logiske variable? Svaret behøver ikke at angive alle de forskellige sæt værdier af K, L, M og N, som denne lighed gælder for. Som svar skal du kun angive antallet af sådanne sæt.

Løsning.

Logisk Og er kun sandt i ét tilfælde: når alle udtryk er sande.

K ∨ L = 1, M ∨ N = 1.

Hver ligning giver 3 løsninger.

Overvej ligningen A ∧ B = 1, hvis både A og B tager sande værdier i tre tilfælde hver, så har ligningen i alt 9 løsninger.

Derfor er svaret 9.

Svar: 9

Hvor mange forskellige løsninger har ligningen?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

hvor A, B, C, D er logiske variable?

Svaret behøver ikke at angive alle de forskellige sæt værdier A, B, C, D, som denne lighed gælder for. Som svar skal du angive antallet af sådanne sæt.

Løsning.

Logisk "ELLER" er sandt, når mindst et af udsagn er sandt.

(D ∧ ¬D)= 0 for enhver D.

Derfor,

(A → B) ∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, hvilket giver os 3 mulige løsninger for hver D.

(D ∧ ¬ D)= 0 for enhver D, hvilket giver os to løsninger (for D = 1, D = 0).

Derfor: samlede løsninger 2*3 = 6.

I alt 6 løsninger.

Svar: 6

Hvor mange forskellige løsninger har ligningen?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

hvor K, L, M, N er logiske variable? Svaret behøver ikke at angive alle de forskellige sæt værdier af K, L, M og N, som denne lighed gælder for. Som svar skal du kun angive antallet af sådanne sæt.

Løsning.

Lad os anvende negation på begge sider af ligningen:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Logisk ELLER er sandt i tre tilfælde.

Mulighed 1.

K ∧ L ∧ M = 1, derefter K, L, M = 1, og ¬L ∧ M ∧ N = 0. N er vilkårlig, det vil sige 2 løsninger.

Mulighed 2.

¬L ∧ M ∧ N = 1, derefter N, M = 1; L = 0, K enhver, det vil sige 2 løsninger.

Derfor er svaret 4.

Svar: 4

A, B og C er heltal, for hvilke udsagnet er sandt

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

Hvad er B lig med, hvis A = 45 og C = 43?

Løsning.

Bemærk venligst, at dette komplekse udsagn består af tre simple

1) ¬(A = B); (A > B) →(B > C); (B > A) → (C > B);

2) disse simple udsagn er forbundet med operationen ∧ (AND, konjunktion), det vil sige, at de skal udføres samtidigt;

3) fra ¬(A = B)=1 følger umiddelbart, at A B;

4) antag at A > B, så får vi fra den anden betingelse 1→(B > C)=1; dette udtryk kan være sandt, hvis og kun hvis B > C = 1;

5) derfor har vi A > B > C, kun tallet 44 svarer til denne betingelse;

6) for en sikkerheds skyld, lad os også tjekke mulighed A 0 →(B > C)=1;

dette udtryk er sandt for enhver B; Nu ser vi på den tredje betingelse, og vi får

dette udtryk kan være sandt, hvis og kun hvis C > B, og her har vi en modsigelse, fordi der ikke er et sådant tal B, for hvilket C > B > A.

Svar: 44.

Svar: 44

Konstruer en sandhedstabel for en logisk funktion

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

hvor kolonnen med værdier af argument A er den binære repræsentation af tallet 27, kolonnen med værdier af argument B er tallet 77, kolonnen med værdier af argument C er tallet 120. Tallet i kolonnen skrives fra top til bund fra den mest signifikante til den mindst signifikante (inklusive nulsættet). Konverter den resulterende binære repræsentation af værdierne af funktion X til decimaltalsystemet.

Løsning.

Lad os skrive ligningen ved hjælp af enklere notation for operationer:

1) dette er et udtryk med tre variable, så der vil være linjer i sandhedstabellen; derfor skal den binære repræsentation af de tal, der bruges til at konstruere tabelkolonner A, B og C bestå af 8 cifre

2) konverter tallene 27, 77 og 120 til det binære system, og læg straks op til 8 cifre af nuller i begyndelsen af ​​tallene

3) det er usandsynligt, at du straks vil være i stand til at skrive værdierne af X-funktionen for hver kombination, så det er praktisk at tilføje yderligere kolonner til tabellen for at beregne mellemresultater (se tabellen nedenfor)

4) udfyld tabelkolonnerne:

værdien er kun 1 i de linjer, hvor A = B

værdien er 1 i de linjer, hvor enten B eller C = 1

værdien er kun 0 i de linjer, hvor A = 1 og B + C = 0

værdien er det omvendte af den forrige kolonne (0 er erstattet af 1, og 1 er erstattet af 0)

resultatet af X (sidste kolonne) er den logiske sum af de to kolonner og

5) For at få svaret, skriv bits fra kolonne X fra top til bund:

6) konverter dette tal til decimalsystemet:

Svar: 171

Hvad er det største heltal X, som udsagnet (10 (X+1)·(X+2)) er sandt for?

Løsning.

En ligning er en implikationsoperation mellem to relationer:

1) Selvfølgelig kan du her anvende den samme metode som i eksempel 2208, men du bliver nødt til at løse andengradsligninger (det vil jeg ikke...);

2) Bemærk, at vi ved betingelse kun er interesserede i heltal, så vi kan forsøge på en eller anden måde at transformere det oprindelige udtryk og opnå en tilsvarende erklæring (vi er slet ikke interesseret i de nøjagtige værdier af rødderne!);

3) Overvej uligheden: selvfølgelig kan det være enten et positivt eller et negativt tal;

4) Det er nemt at kontrollere, at i domænet er udsagnet sandt for alle heltal , og i domænet - for alle heltal (for ikke at blive forvirret er det mere praktisk at bruge ikke-strenge uligheder, og i stedet for og );

5) Derfor kan det for heltal erstattes af et ækvivalent udtryk

6) et udtryks sandhedsdomæne er foreningen af ​​to uendelige intervaller;

7) Overvej nu den anden ulighed: det er indlysende, at det også kan være enten et positivt eller et negativt tal;

8) I regionen er sætningen sand for alle heltal, og i regionen - for alle heltal, derfor kan den for heltal erstattes af et ækvivalent udtryk

9) udtrykkets sandhedsdomæne er et lukket interval;

10) Det givne udtryk er sandt overalt, undtagen områder hvor og ;

11) Bemærk venligst, at værdien ikke længere er passende, fordi der og , dvs. implikationen giver 0;

12) Når du erstatter 2, (10 (2+1) · (2+2)), eller 0 → 0, som opfylder betingelsen.

Så svaret er 2.

Svar: 2

Hvad er det største heltal X, som udsagnet er sandt for

(50 (X+1)·(X+1))?

Løsning.

Lad os anvende implikationstransformationen og transformere udtrykket:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Logisk ELLER er sand, når mindst én logisk sætning er sand. Efter at have løst begge uligheder og taget i betragtning, ser vi, at det største heltal, som mindst én af dem er opfyldt for, er 7 (i figuren er den positive løsning af den anden ulighed vist i gult og den første med blå).

Svar: 7

Angiv værdierne af variablerne K, L, M, N, hvor det logiske udtryk

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

falsk. Skriv svaret som en streng på 4 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.

Dubletter opgave 3584.

Svar: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Løsning.

Lad os anvende implikationstransformationen:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Lad os anvende negation på begge sider af ligningen:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Lad os konvertere:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Derfor, M = 0, N = 0, overvej nu (¬K ∧ L ∨ M ∧ L):

af det faktum, at M = 0, N = 0, følger det, at M ∧ L = 0, så ¬K ∧ L = 1, det vil sige K = 0, L = 1.

Svar: 0100

Angiv værdierne af variablerne K, L, M, N, hvor det logiske udtryk

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

falsk. 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 skrive ligningen ved at bruge enklere notation af operationer (betingelsen "udtrykket er falsk" betyder, at det er lig med logisk nul):

1) af formuleringen af ​​betingelsen følger det, at udtrykket kun skal være falsk for ét sæt variable

2) af sandhedstabellen for "implikationsoperationen" følger det, at dette udtryk er falsk, hvis og kun hvis det samtidig

3) den første lighed (det logiske produkt er lig med 1) er opfyldt hvis og kun hvis og ; heraf følger (den logiske sum er lig nul), hvilket kun kan ske, når ; Vi har således allerede defineret tre variable

4) fra den anden betingelse, , for og vi opnår .

Dublerer opgaven

Svar: 1000

Angiv værdierne af de logiske variable P, Q, S, T, hvor det logiske udtryk

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) er falsk.

Skriv svaret som en streng på fire tegn: værdierne af variablerne P, Q, S, T (i nævnte rækkefølge).

Løsning.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Lad os anvende implikationstransformationen:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Svar: 0100

Angiv værdierne af variablerne K, L, M, N, hvor det logiske udtryk

(K → M) ∨ (L ∧ K) ∨ ¬N

falsk. 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.

Logisk ELLER er falsk, hvis og kun hvis begge udsagn er falske.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Lad os anvende implikationstransformationen for det første udtryk:

¬K ∨ M = 0 => K = 1, M = 0.

Overvej det andet udtryk:

(L ∧ K) ∨ ¬N = 0 (se resultatet af det første udtryk) => L ∨ ¬N = 0 => L = 0, N = 1.

Svar: 1001.

Svar: 1001

Angiv værdierne af variablerne K, L, M, N, hvor det logiske udtryk

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

rigtigt. 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.

Logisk "AND" er sandt, hvis og kun hvis begge udsagn er sande.

1) (K → M) = 1 Anvend implikationstransformationen: ¬K ∨ M = 1

2) (K → ¬M) = 1 Anvend implikationstransformationen: ¬K ∨ ¬M = 1

Det følger, at K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Lad os anvende implikationstransformationen: K ∨ (M ∧ ¬L ∧ N) = 1 fra det faktum, at K = 0 får vi.