Logiske ligninger. Systemer af logiske ligninger i Unified State eksamensproblemer i datalogi

Formålet med tjenesten. Online-beregneren er designet til at konstruere en sandhedstabel til et logisk udtryk.
Sandhedstabel – en tabel, der indeholder alle mulige kombinationer af inputvariabler og deres tilsvarende outputværdier.
Sandhedstabellen indeholder 2n rækker, hvor n er antallet af inputvariable, og n+m er kolonner, hvor m er outputvariable.

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

For eksempel skal det logiske udtryk abc+ab~c+a~bc indtastes således: a*b*c+a*b=c+a=b*c
Brug denne service for at indtaste data i form af et logisk diagram.

Regler for indtastning af en logisk funktion

I stedet for v (disjunktion, OR)-symbolet skal du bruge +-tegnet.
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) .
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)

En logisk operation anvendes IKKE på et enkelt argument, som kan være et simpelt eller komplekst logisk udtryk. Resultatet af operationen er IKKE følgende:

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.

Følgende konventioner accepteres IKKE for negationsoperationen:
ikke A, Ā, ikke A, ¬A, !A
Resultatet af negationsoperationen bestemmes IKKE af følgende sandhedstabel:

EN	ikke A
0	1
1	0

Resultatet af negationsoperationen er sandt, når den oprindelige sætning er falsk, og omvendt.

ELLER-operation - logisk addition (disjunktion, forening)

Den logiske ELLER-operation udfører funktionen med at kombinere to udsagn, som enten kan være et simpelt eller et komplekst logisk udtryk. Udsagn, der er udgangspunktet for en logisk operation, kaldes argumenter. Resultatet af OR-operationen er et udtryk, der vil være sandt, hvis og kun hvis mindst et af de oprindelige udtryk er sandt.
Anvendte betegnelser: A eller B, A V B, A eller B, A||B.
Resultatet af ELLER-operationen bestemmes af følgende sandhedstabel:
Resultatet af ELLER-operationen er sandt, når A er sandt, eller B er sandt, eller både A og B er sandt, og falsk, når argumenterne A og B er falske.

Operation OG - logisk multiplikation (konjunktion)

Den logiske operation AND udfører funktionen som skæringspunkt mellem to udsagn (argumenter), som enten kan være et simpelt eller et komplekst logisk udtryk. Resultatet af AND-operationen er et udtryk, der vil være sandt, hvis og kun hvis begge originale udtryk er sande.
Anvendte betegnelser: A og B, A Λ B, A & B, A og B.
Resultatet af AND-operationen bestemmes af følgende sandhedstabel:

EN	B	A og B
0	0	0
0	1	0
1	0	0
1	1	1

Resultatet af AND-operationen er sandt, hvis og kun hvis udsagn A og B er både sande og falske i alle andre tilfælde.

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

Denne operation forbinder to simple logiske udtryk, hvoraf det første er en betingelse, og det andet er en konsekvens af denne betingelse.
Anvendte betegnelser:
hvis A, så B; A medfører B; hvis A så B; A→B.
Sandhedstabel:

EN	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Resultatet af implikationsoperationen er kun falsk, hvis præmis A er sand, og konklusion B (konsekvens) er falsk.

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

Anvendt betegnelse: A ↔ B, A ~ B.
Sandhedstabel:

EN	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

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

Brugt notation: A XOR B, A ⊕ B.
Sandhedstabel:

EN	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Resultatet af ækvivalensoperationen er kun sandt, hvis A og B begge er sande eller falske på samme tid.

Prioritet af logiske operationer

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

Perfekt disjunktiv normalform

Perfekt disjunktiv normal form af en formel(SDNF) er en ækvivalent formel, som er en disjunktion af elementære konjunktioner og har følgende egenskaber:

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

SDNF kan opnås enten ved hjælp af sandhedstabeller eller ved hjælp af tilsvarende transformationer.
For hver funktion er SDNF og SCNF unikt defineret op til permutation.

Perfekt konjunktiv normalform

Perfekt konjunktiv normal form af en formel (SCNF) Dette er en formel svarende til den, som er en sammensætning af elementære disjunktioner og opfylder egenskaberne:

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

Brugen af ligninger er udbredt i vores liv. De bruges i mange beregninger, konstruktion af strukturer og endda sport. Mennesket brugte ligninger i oldtiden, og siden er deres brug kun steget. I matematik er der visse problemer, der omhandler propositionel logik. For at løse denne form for ligning skal du have en vis mængde viden: kendskab til lovene for propositionel logik, kendskab til sandhedstabeller af logiske funktioner af 1 eller 2 variable, metoder til konvertering af logiske udtryk. Derudover skal du kende følgende egenskaber ved logiske operationer: konjunktion, disjunktion, inversion, implikation og ækvivalens.

Enhver logisk funktion af \variabler - \kan specificeres af en sandhedstabel.

Lad os løse flere logiske ligninger:

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

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

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

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

Lad os starte løsningen med \[X1\] og bestemme, hvilke værdier denne variabel kan tage: 0 og 1. Dernæst vil vi overveje hver af ovenstående værdier og se, hvad \[X2.\] kan være.

Som det fremgår af tabellen, har vores logiske ligning 11 løsninger.

Hvor kan jeg løse en logisk ligning online?

Du kan løse ligningen på vores hjemmeside https://site. Den gratis online løser giver dig mulighed for at løse online ligninger af enhver kompleksitet i løbet af få sekunder. Alt du skal gøre er blot at indtaste dine data i solveren. Du kan også se videoinstruktioner og lære, hvordan du løser ligningen på vores hjemmeside. Og hvis du stadig har spørgsmål, kan du stille dem i vores VKontakte-gruppe http://vk.com/pocketteacher. Tilmeld dig vores gruppe, vi er altid glade for at hjælpe dig.

Der er forskellige måder at løse logiske ligningssystemer på. Dette er reduktion til én ligning, konstruktion af en sandhedstabel og dekomponering.

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:








0	0	1	1	0	1

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: Lad A = 0, så:

Fra den første ligning får vi B = 0, og fra den anden - C = 1. Løsning af 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å ererstatte 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 variable: X = A →B og Y = C →D. Under hensyntagen til de nye variable 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 implikationer, det vil sige, at den er sand i tre tilfælde og falsk i ét. 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 om x 1 – er sandt, så får vi det ud fra den første ligning x 2 også sandt, fra den anden - x 3 =1, og så videre indtil x m= 1. Det betyder, at sættet (1; 1; …; 1) af m enheder er en løsning på systemet. Lad det nu x 1 =0, så fra den første ligning vi har x 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 variabler (m +1 løsning, hver løsning indeholder m værdier af variablerne):

(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 lig med m +1.

	Træ	Antal løsninger
x 1
x 2
x 3
		…

I tilfælde af vanskeligheder med at ræsonnere forskning og konstruktionaf løsninger, du kan søge efter en løsning med ved brug af sandhedstabeller, for en eller to ligninger.

Lad os omskrive ligningssystemet på formen:

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

x 1	x 2	(x 1 → x 2)

Lad os lave en sandhedstabel for to ligninger:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Lektionens emne: Løsning af logiske ligninger

Pædagogisk – studere metoder til at løse logiske ligninger, udvikle færdigheder i at løse logiske ligninger og konstruere et logisk udtryk ved hjælp af en sandhedstabel;

Udviklings- skabe betingelser for udvikling af elevernes kognitive interesse, fremme udviklingen af hukommelse, opmærksomhed og logisk tænkning;

Pædagogisk : fremmer evnen til at lytte til andres meninger, pleje viljen og udholdenheden til at opnå endelige resultater.

Lektionstype: kombineret lektion

Udstyr: computer, multimedieprojektor, præsentation 6.

Under timerne

Gentagelse og opdatering af grundlæggende viden. Kontrol af lektier (10 minutter)

I tidligere lektioner stiftede vi bekendtskab med de grundlæggende love i logisk algebra og lærte at bruge disse love til at forenkle logiske udtryk.

Lad os tjekke vores hjemmearbejde om at forenkle logiske udtryk:

1. Hvilket af følgende ord opfylder den logiske betingelse:

(første bogstavs konsonant → andet bogstavs konsonant)٨ (sidste bogstavvokal → næstsidste bogstavvokal)? Hvis der er flere sådanne ord, skal du angive det mindste af dem.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Lad os introducere følgende notation:

A – første bogstavs konsonant

B – andet bogstavs konsonant

S – sidste bogstavs vokal

D – næstsidste vokalbogstav

Lad os komme med et udtryk:

Lad os lave en tabel:

2. Angiv hvilket logisk udtryk der svarer til udtrykket

Lad os forenkle registreringen af det originale udtryk og de foreslåede muligheder:

3. Givet et fragment af sandhedstabellen for udtryk F:

Hvilket udtryk matcher F?

Lad os bestemme værdierne af disse udtryk for de angivne værdier af argumenterne:

Introduktion til lektionens emne, præsentation af nyt stof (30 minutter)

Vi fortsætter med at studere det grundlæggende i logik, og emnet for vores dagens lektion er "Løsning af logiske ligninger." Efter at have studeret dette emne, vil du lære de grundlæggende måder at løse logiske ligninger på, få færdighederne til at løse disse ligninger ved at bruge sproget i logisk algebra og evnen til at komponere et logisk udtryk ved hjælp af en sandhedstabel.

1. Løs en logisk ligning

(¬K M) → (¬L M N) = 0

Skriv dit svar som en streng på fire tegn: værdierne af variablerne K, L, M og N (i nævnte rækkefølge). Så f.eks. svarer linje 1101 til, at K=1, L=1, M=0, N=1.

Løsning:

Lad os omdanne udtrykket(¬K  M) → (¬L  M  N)

Et udtryk er falsk, når begge udtryk er falske. Det andet led er lig med 0, hvis M =0, N =0, L =1. I det første led K = 0, da M = 0, og
.

Svar: 0100

2. Hvor mange løsninger har ligningen (angiv kun tallet i dit svar)?

Løsning: transformer udtrykket

(A+B)*(C+D)=1

A+B=1 og C+D=1

Metode 2: udarbejdelse af en sandhedstabel

3 vejs: konstruktion af en SDNF - en perfekt disjunktiv normalform for en funktion - en disjunktion af komplette regulære elementære konjunktioner.

Lad os omdanne det oprindelige udtryk, åbne parenteserne for at opnå disjunktionen af konjunktioner:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Lad os supplere konjunktionerne til komplette konjunktioner (produktet af alle argumenter), åbn parenteserne:

Lad os tage de samme konjunktioner i betragtning:

Som et resultat opnår vi en SDNF indeholdende 9 konjunktioner. Derfor har sandhedstabellen for denne funktion værdien 1 i 9 rækker med 2 4 = 16 sæt af variable værdier.

3. Hvor mange løsninger har ligningen (angiv kun tallet i dit svar)?

Lad os forenkle udtrykket:

3 vejs: konstruktion af SDNF

Lad os tage de samme konjunktioner i betragtning:

Som et resultat opnår vi en SDNF indeholdende 5 konjunktioner. Derfor har sandhedstabellen for denne funktion værdien 1 på 5 rækker med 2 4 = 16 sæt af variable værdier.

Konstruktion af et logisk udtryk ved hjælp af en sandhedstabel:

for hver række i sandhedstabellen, der indeholder 1, sammensætter vi et produkt af argumenter, og variabler lig med 0 er inkluderet i produktet med negation, og variable lig med 1 er inkluderet uden negation. Det ønskede udtryk F vil være sammensat af summen af de resulterende produkter. Så, hvis det er muligt, bør dette udtryk forenkles.

Eksempel: der gives en sandhedstabel for et udtryk. Konstruer et logisk udtryk.

Løsning:

3. Hjemmearbejde (5 minutter)

Løs ligningen:

Hvor mange løsninger har ligningen (angiv kun tallet i dit svar)?

Konstruer ved hjælp af en given sandhedstabel et logisk udtryk og

forenkle det.