Logiska formler för sanningstabellen. II

Demonstrationsversion av tentamen 2019 - uppgift nummer 2

Misha fyllde i sanningstabellen för funktionen (¬x / \\ ¬y) \\ / (y≡z) \\ / ¬w, men lyckades bara fylla i ett fragment av tre olika rader i den, utan att ens ange vilken kolumn i tabellen var och en av variablerna w, x motsvarar ,
y, z.

Bestäm vilken kolumn i tabellen som var och en av variablerna w, x, y, z motsvarar.
I ditt svar skriver du bokstäverna w, x, y, z i den ordning i vilken motsvarande kolumner visas (först bokstaven som motsvarar den första kolumnen, sedan bokstaven som motsvarar den andra kolumnen, etc.). Brev
i svaret, skriv i rad, du behöver inte placera några separatorer mellan bokstäverna.
Exempel. Om funktionen gavs av uttrycket ¬x \\ / y, beroende på två variabler, och fragmentet i tabellen skulle ha formen

då skulle den första kolumnen vara y och den andra kolumnen skulle vara x. Svaret borde ha varit yx.

(¬x ¬y) + (y≡z) + ¬w \u003d 0

w \u003d 1 w måste vara sant; w - sist

y och z måste vara olika, så innan det sista är det x. de två första är y och z eller z och y.

y och x kan inte vara falska samtidigt. den första är z.

Svar: zyxw

Demonstrationsversion av USE 2018 - uppgift nummer 2

Den logiska funktionen F ges av uttrycket ¬x \\ / y \\ / (¬z / \\ w). Figuren visar ett fragment av sanningstabellen för funktionen F, som innehåller alla uppsättningar av argument för vilka funktionen F är falsk. Bestäm vilken kolumn i sanningstabellen för funktionen F som motsvarar var och en av variablerna w, x, y, z

I svaret skriver du bokstäverna w, x, y, z i den ordning som motsvarande kolumner går i (först - bokstaven som motsvarar den första kolumnen; sedan - bokstaven som motsvarar den andra kolumnen, etc.) Skriv bokstäverna i svaret i rad, inga separatorer krävs mellan bokstäverna. Exempel. Om funktionen gavs av uttrycket ¬x \\ / y, beroende på två variabler: x och y, och ett fragment av dess sanningstabell gavs, innehållande alla uppsättningar av argument för vilka funktionen är sant.

Då motsvarar den första kolumnen variabeln y och den andra kolumnen motsvarar variabeln x. Svaret borde ha varit: yx.

Svar: xzwy

Logisk funktion Fges av uttrycket x/\ ¬y/\ (¬z\/ w).

Figuren visar ett fragment av funktionens sanningstabell Fsom innehåller alltuppsättningar av argument för vilka funktionen Fsann.

Bestäm vilken kolumn i funktionens sanningstabell Fvar och en av variablerna motsvarar w, x, y, z.

Skriv bokstäver i svaret w, x, y, zi den ordning de går

deras motsvarande kolumner (först - bokstaven som motsvarar den första

kolumn; sedan - bokstaven som motsvarar den andra kolumnen, etc.) Bokstäver

i svaret skriv i rad, sätt inga separatorer mellan bokstäverna

inte nödvändigt.

Demonstrationsversion av USE 2017 - uppgift nummer 2

Beslut:

Konjunktion (logisk multiplikation) är sant om och endast om alla uttalanden är sanna. Därav variabeln x 1 .

Variabel ¬y måste matcha kolumnen där alla värden är lika 0 .

En disjunktion (logiskt tillägg) av två påståenden är sant om och endast om minst ett påstående är sant.
Åtskiljande ¬z \\ / y z \u003d 0, w \u003d 1.

Så variabeln ¬z w matchar kolumn med variabel 4 (4 kolumner).

Svar: zyxw

Demonstrationsversion av USE 2016 - uppgift nummer 2

Logisk funktion F ges av uttrycket (¬z) / \\ x \\ / x / \\ y. Bestäm vilken kolumn i sanningstabellen för funktionen F som motsvarar var och en av variablerna x, y, z.

I svaret skriver du bokstäverna x, y, z i den ordning i vilken motsvarande kolumner går (först - bokstaven som motsvarar den första kolumnen; sedan - bokstaven som motsvarar den andra kolumnen; sedan - bokstaven som motsvarar den tredje kolumnen) ... Skriv bokstäverna i rad i rad; inga separatorer krävs mellan bokstäverna.

Exempel... Låt ett uttryck x → y, beroende på två variabler x och y, och en sanningstabell ges:

Sedan motsvarar den första kolumnen variabeln y och den andra kolumnen
variabeln x motsvarar. I svaret måste du skriva: yx.

Beslut:

1. Låt oss skriva det givna uttrycket i enklare notation:

¬z * x + x * y \u003d x * (¬z + y)

2. En sammankoppling (logisk multiplikation) är sant om och endast om alla uttalanden är sanna. Därför, för funktionen ( F) var lika med en ( 1 ) är det nödvändigt att varje faktor är lika med en ( 1 ). Således för F \u003d 1, variabel x måste matcha kolumnen där alla värden är lika 1 .

3. Överväg (¬z + y), vid F \u003d 1 detta uttryck är också lika med 1 (se punkt 2).

4. Disjunktion (logiskt tillägg) av två påståenden är sant om och endast om minst ett påstående är sant.
Åtskiljande ¬z \\ / y på en viss rad är sant endast om

1. z \u003d 0; y \u003d 0eller y \u003d 1;
2. z \u003d 1; y \u003d 1

5. Således är variabeln ¬z matchar kolumn med variabel 1 (1 kolumn), variabel y

Svar: zyx

KIM-ANVÄNDNING 2016 (tidig period)- uppgift nummer 2

Den logiska funktionen F ges av uttrycket

(x / \\ y / \\ ¬z) \\ / (x / \\ y / \\ z) \\ / (x / \\ ¬y / \\ ¬z).

Figuren visar ett fragment av sanningstabellen för funktionen F, som innehåller alla uppsättningar argument för vilka funktionen F är sant. Bestäm vilken kolumn i sanningstabellen för funktionen F var och en av variablerna x, y, z motsvarar.

I svaret skriver du bokstäverna x, y, z i den ordning som motsvarande kolumner går i (först - bokstaven som motsvarar den första kolumnen; sedan - bokstaven som motsvarar den andra kolumnen, etc.) Skriv bokstäverna i svaret i rad, inga separatorer du behöver inte sätta mellan bokstäverna.

R lösning:

Låt oss skriva det givna uttrycket i enklare notation:

(x * y * ¬z) + (x * y * z) + (x * ¬y * ¬z) \u003d 1

Detta uttryck är sant om minst en av (x * y * ¬z), (x * y * z), (x * ¬y * ¬z) är lika med 1. Sammankopplingen (logisk multiplikation) är sant om och bara om, när alla uttalanden är sanna.

Åtminstone en av dessa disjunktioner x * y * ¬z; x * y * z; x * ¬y * ¬z kommer bara att vara sant om x \u003d 1.

Så variabeln x matchar kolumn med variabel 2 (kolumn 2).

Låta y-variabel 1, z-premiär 3. I det första fallet x * ¬y * ¬zkommer att vara sant, i det andra fallet x * y * ¬zoch i det tredje x * y * z.

Svar: yxz

Symbol F betecknar ett av följande logiska uttryck från tre argument: X, Y, Z. Ett fragment av sanningstabellen för uttryck F ges (se tabellen till höger). Vilket uttryck matchar F?

X	Y	Z	F
0	0	0	0
1	0	1	1
0	1	0	1

1) X ∧ Y ∧ Z 2) ¬X ∨ Y ∨¬Z 3) X ∧ Y ∨ Z 4) X ∨ Y ∧ ¬Z

Beslut:

1) X ∧ Y ∧ Z \u003d 1.0.1 \u003d 0 (matchar inte på andra raden)

2) ¬X ∨ Y ∨¬Z \u003d ¬0 ∨ 0 ∨ ¬0 \u003d 1 + 0 + 1 \u003d 1 (matchar inte på första raden)

3) X ∧ Y ∨ Z \u003d 0,1 + 0 \u003d 0 (matchar inte på 3: e raden)

4) X ∨ Y ∧ ¬Z (motsvarar F)

X ∨ Y ∧ ¬Z \u003d 0 ∨ 0 ∧ ¬0 \u003d 0 + 0,1 \u003d 0

X ∨ Y ∧ ¬Z \u003d 1 ∨ 0 ∧ ¬1 \u003d 1 + 0,0 \u003d 1

X ∨ Y ∧ ¬Z \u003d 0 ∨ 1 ∧ ¬0 \u003d 0 + 1.1 \u003d 1

Svar: 4

Givet ett fragment av sanningstabellen för uttryck F. Vilket uttryck motsvarar F?

A	B	C	F
0	1	1	1
1	0	0	0
1	0	1	1

1) (A → ¬B) ∨ C 2) (¬A ∨ B) ∧ C 3) (A ∧ B) → C 4) (A ∨ B) → C

Beslut:

1) (A → ¬B) ∨ C \u003d (1 → ¬0) ∨ 0 \u003d (1 → 1) + 0 \u003d 1 + 0 \u003d 1 (matchar inte på andra raden)

2) (¬A ∨ B) ∧ C \u003d (¬1 ∨ 0) ∧ 1 \u003d (0 + 0) .1 \u003d 0 (matchar inte på tredje raden)

3) (A ∧ B) → C \u003d (1 ∧ 0) → 0 \u003d 0 → 0 \u003d 1 (matchar inte på andra raden)

4) (A ∨ B) → C (motsvarar F)

(A ∨ B) → C \u003d (0 ∨ 1) → 1 \u003d 1

(A ∨ B) → C \u003d (1 ∨ 0) → 0 \u003d 0

(A ∨ B) → C \u003d (1 ∨ 0) → 1 \u003d 1

Svar: 4

Ett logiskt uttryck ges som beror på 6 logiska variabler:

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6

Hur många olika uppsättningar av variabla värden finns det som ett uttryck är sant för?

1) 1 2) 2 3) 63 4) 64

Beslut:

Falskt uttryck endast i 1 fall: X1 \u003d 0, X2 \u003d 1, X3 \u003d 0, X4 \u003d 1, X5 \u003d 0, X6 \u003d 0

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6 \u003d 0 ∨ ¬1 ∨ 0 ∨ ¬1 ∨ 0 ∨ 0 \u003d 0

Det finns totalt 2 6 \u003d 64 alternativ, vilket betyder sant

Svar: 63

Ett fragment av sanningstabellen för uttryck F ges.

x1	x2	x3	x4	x5	x6	x7	F
0	1	0	1	1	1	0	0
1	1	0	1	0	1	0	1
0	1	0	1	1	0	1	0

Vilket uttryck matchar F?

1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7

Beslut:

1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 \u003d 0 + 1 + ... \u003d 1 (matchar inte på första raden)

2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 \u003d 0 + 0 + 0 + 0 + 0 + 1 + 0 \u003d 1 (matchar inte på första raden)

3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 \u003d 1.0. ... \u003d 0 (matchar inte på andra raden)

4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (motsvarar F)

x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 \u003d 1.1.1.1.1.1.1 \u003d 1

x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 \u003d 0.… \u003d 0

Svar: 4

x1	x2	x3	x4	x5	x6	x7	x8	F
		0				1		1
1		0			1			0
			1				0	1

Vilket uttryck kan F vara?

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8

Beslut:

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 \u003d x1. ¬x2. 0. … \u003d 0 (matchar inte på första raden)

2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (motsvarar F)

3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 \u003d… ¬x7 ∧ ¬x8 \u003d… ¬1 ∧ ¬x8 \u003d… 0 ∧ ¬x8 \u003d 0 (motsvarar inte 1- raden)

4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 \u003d ¬x1 ∨ ¬x2 ∨ ¬x3 ... \u003d ¬1 ∨ ¬x2 ∨ ¬0 .. \u003d 1 (inte matcher på andra raden)

Svar: 2

Ett fragment av sanningstabellen för uttrycket F ges:

x1	x2	x3	x4	x5	x6	x7	F
0	0	1	1	0	0	1	0
0	1	0	0	1	1	0	1
0	0	0	0	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	1	0	1

Ange det minsta möjliga antalet distinkta rader i den fullständiga sanningstabellen för detta uttryck där x5 matchar F.

Beslut:

Minsta möjliga antal distinkta rader där x5 matchar F \u003d 4

Svar: 4

Ett fragment av sanningstabellen för uttrycket F ges:

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	1	1	0	0	1	0	0
0	1	0	0	1	1	0	1	1
0	0	0	0	1	1	1	1	1
1	0	1	0	1	1	0	1	1
0	1	1	1	0	1	0	0	1

Ange maximalt möjligt antal distinkta rader i den fullständiga sanningstabellen för detta uttryck där x6 inte matchar F.

Beslut:

Maximalt antal \u003d 2 8 \u003d 256

Maximalt antal distinkta rader där x6 inte matchar F \u003d 256 - 5 \u003d 251

Svar: 251

Ett fragment av sanningstabellen för uttrycket F ges:

x1	x2	x3	x4	x5	x6	x7	F
0	0	1	1	0	0	1	0
0	1	0	0	1	1	0	1
0	0	0	0	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	1	0	1

Ange maximalt möjligt antal distinkta rader i den fullständiga sanningstabellen för detta uttryck där värdet ¬x5 ∨ x1 sammanfaller med F.

Beslut:

1 + 0 \u003d 1 - matchar inte F

0 + 0 \u003d 0 - matchar inte F

0 + 0 \u003d 0 - matchar inte F

0 + 1 \u003d 1 - sammanfaller med F

1 + 0 \u003d 1 - sammanfaller med F

2 7 = 128 — 3 = 125

Svar: 125

Varje booleskt uttryck A och B beror på samma uppsättning av 6 variabler. I sanningstabellerna för vart och ett av dessa uttryck finns exakt 4 enheter i värdekolumnen. Vad är det minsta möjliga antalet i värdekolumnen i sanningstabellen för uttrycket A ∨ B?

Beslut:

Svar: 4

Varje booleskt uttryck A och B beror på samma uppsättning med 7 variabler. I sanningstabellerna för vart och ett av dessa uttryck finns exakt 4 enheter i värdekolumnen. Vad är det maximalt möjliga antalet i värdekolumnen i sanningstabellen för uttrycket A ∨ B?

Beslut:

Svar: 8

Varje booleskt uttryck A och B beror på samma uppsättning av åtta variabler. I sanningstabellerna för vart och ett av dessa uttryck innehåller värdekolumnen exakt 5 enheter. Vad är det minsta möjliga antalet nollor i värdekolumnen i sanningstabellen för uttrycket A ∧ B?

Beslut:

2 8 = 256 — 5 = 251

Svar: 251

Varje booleskt uttryck A och B beror på samma uppsättning av åtta variabler. I sanningstabellerna för vart och ett av dessa uttryck innehåller värdekolumnen exakt 6 enheter. Vad är det maximalt möjliga antalet nollor i värdekolumnen i sanningstabellen för uttrycket A ∧ B?

Beslut:

Svar: 256

Booleska uttryck A och B beror vardera på samma uppsättning av 5 variabler. Det finns inga matchande rader i sanningstabellerna för båda uttrycken. Hur många kommer att finnas i värdekolumnen i sanningstabellen för uttryck A ∧ B?

Beslut:

Det finns inga matchande rader i sanningstabellerna för båda uttrycken.

Svar: 0

Booleska uttryck A och B beror vardera på samma uppsättning med 6 variabler. Det finns inga matchande rader i sanningstabellerna för båda uttrycken. Hur många kommer att finnas i värdekolumnen i sanningstabellen för uttryck A ∨ B?

Beslut:

(a. ¬c) + (¬b. ¬c)

När c är 1 är F noll så den sista kolumnen är c.

För att bestämma den första och andra kolumnen kan vi använda värdena från den tredje raden.

(a. 1) + (¬b. 1) \u003d 0

Svar: abc

Den logiska funktionen F ges av uttrycket (a ∧ c) ∨ (¬a ∧ (b ∨ ¬c)). Bestäm vilken kolumn i sanningstabellen för funktionen F som motsvarar var och en av variablerna a, b, c.

¬a. b

?	?	?	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1	0
1	1	1

Baserat på det faktum att för a \u003d 0 och c \u003d 0, då F \u003d 0 och data från andra raden kan vi dra slutsatsen att den tredje kolumnen innehåller b.

Svar: hytt

Den logiska funktionen F ges av x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). Figuren visar ett fragment av sanningstabellen för funktionen F, som innehåller alla uppsättningar argument för vilka funktionen F är sant. Bestäm vilken kolumn i sanningstabellen för funktionen F som motsvarar var och en av variablerna x, y, z, w.

?	?	?	?	F
0	1	0	1	1
0	1	1	0	1
1	1	0	1	1

I svaret skriver du bokstäverna x, y, z, w i den ordning som motsvarande kolumner visas i.

Beslut:

x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)

x. (¬y. Z. ¬w. Y. ¬z)

Baserat på det faktum att vid x \u003d 0, då F \u003d 0, kan vi dra slutsatsen att den andra kolumnen innehåller x.

Svar: wxzy

I digitala kretsar är en digital signal en signal som kan ta två värden, betraktade som en logisk "1" och en logisk "0".

Logiska kretsar kan innehålla upp till 100 miljoner ingångar och sådana gigantiska kretsar finns. Tänk dig att den booleska funktionen (ekvationen) för en sådan krets har gått förlorad. Hur återställer man den med minst tidsförlust och utan fel? Det mest produktiva sättet är att planera schemat. Med denna metod registreras utgångsfunktionen för varje element i föregående nivå och ersätts med motsvarande ingång på nästa nivå. Idag kommer vi att överväga denna metod för att analysera logiska kretsar med alla nyanser.

Logiska kretsar är implementerade på logiska grindar: "NOT", "AND", "OR", "AND-NOT", "OR-NOT", "Exclusive OR" och "Equivalence". De första tre logiska elementen gör att du kan implementera valfri, godtyckligt komplex logisk funktion på en boolsk bas. Vi kommer att lösa problem för logiska kretsar som implementeras på en boolsk bas.

Flera standarder används för att beteckna logiska element. De vanligaste är amerikanska (ANSI), europeiska (DIN), internationella (IEC) och ryska (GOST). Figuren nedan visar beteckningarna på logiska element i dessa standarder (för att förstora, klicka på bilden med vänster musknapp).

I den här lektionen kommer vi att lösa problem på logiska kretsar, på vilka de logiska elementen anges i GOST-standarden.

Uppgifter för logiska kretsar är av två typer: uppgiften att syntetisera logiska kretsar och uppgifterna att analysera logiska kretsar. Vi börjar med den andra typen av problem, eftersom det i denna ordning är möjligt att snabbt lära sig att läsa logiska kretsar.

Oftast beaktas i samband med konstruktionen av logiska kretsar funktionerna för logisk algebra:

• tre variabler (kommer att beaktas i analysproblem och i ett syntesproblem);
• fyra variabler (i syntesproblem, det vill säga i de två sista styckena).

Tänk på uppbyggnaden (syntesen) av logiska kretsar

• på den booleska grunden "OCH", "ELLER", "INTE" (i näst sista stycket);
• i vanliga baser "AND-NOT" och "OR-NOT" (i sista stycket).

Logikanalysproblem

Analysens uppgift är att definiera funktionen f implementeras av en given logisk krets. När du löser ett sådant problem är det bekvämt att följa följande åtgärdssekvens.

1. Logikdiagrammet är kaklat. Nivåer tilldelas löpnummer.
2. Utgångarna för varje logiskt element indikeras av namnet på den önskade funktionen, försett med ett digitalt index, där den första siffran är nivånumret, och de återstående siffrorna är elementets ordinarie nummer i nivån.
3. För varje element skrivs ett analytiskt uttryck som förbinder dess utgångsfunktion med inmatningsvariabler. Ett uttryck definieras av en boolesk funktion implementerad av en given boolean.
4. Substitution av vissa utgångsfunktioner genom andra utförs tills en boolsk funktion uttryckt genom inmatningsvariabler erhålls.

Exempel 1.

Beslut. Vi delar logikkretsen i nivåer, vilket redan visas i figuren. Låt oss skriva ner alla funktioner, med början från första nivån:

x, y, z :

x	y	z					f
1	1	1	0	1	1	1	1
1	1	0	0	0	0	1	0
1	0	1	0	0	0	1	0
1	0	0	0	0	0	1	0
0	1	1	0	0	0	1	0
0	1	0	0	0	0	1	0
0	0	1	0	0	0	1	0
0	0	0	1	0	1	0	0

Exempel 2. Hitta den booleska funktionen hos den logiska kretsen och skapa en sanningstabell för den logiska kretsen.

Exempel 3 Hitta den booleska funktionen hos den logiska kretsen och skapa en sanningstabell för den logiska kretsen.

Låt oss fortsätta leta efter den booleska logikfunktionen tillsammans

Exempel 4 Hitta den booleska funktionen hos den logiska kretsen och skapa en sanningstabell för den logiska kretsen.

Beslut. Vi delar upp logikkretsen i nivåer. Låt oss skriva ner alla funktioner, med början från första nivån:

Låt oss nu skriva alla funktioner och ersätta ingångsvariablerna x, y, z :

Som ett resultat får vi funktionen som den logiska kretsen implementerar vid utgången:

.

Sanningstabell för en given logisk krets:

x	y	z			f
1	1	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
1	0	0	0	0	0
0	1	1	0	1	1
0	1	0	0	1	1
0	0	1	0	1	1
0	0	0	0	1	1

Exempel 5. Hitta den booleska funktionen hos den logiska kretsen och skapa en sanningstabell för den logiska kretsen.

Beslut. Vi bryter logikkretsen i nivåer. Strukturen för denna logiska krets har, till skillnad från tidigare exempel, 5 nivåer, inte 4. Men en ingångsvariabel - den lägsta - går genom alla nivåerna och går direkt in i det logiska elementet i det första nivån. Låt oss skriva ner alla funktioner, med början från första nivån:

Låt oss nu skriva alla funktioner och ersätta ingångsvariablerna x, y, z :

Som ett resultat får vi funktionen som den logiska kretsen implementerar vid utgången:

.

Sanningstabell för en given logisk krets:

x	y	z			f
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	0	1
0	0	0	1	0	1

Problemet med syntes av logiska kretsar på en boolsk bas

Utvecklingen av ett logiskt schema enligt dess analytiska beskrivning kallas uppgiften för syntes av ett logiskt schema.

Varje disjunktion (logisk summa) motsvarar ett ELLER-element, vars antal ingångar bestäms av antalet variabler i disjunktionen. Varje konjunktion (logisk produkt) motsvarar ett AND-element vars antal ingångar bestäms av antalet variabler i konjunktionen. Varje negation (inversion) motsvarar elementet "INTE".

Ofta börjar utformningen av en logisk krets med att definiera den logiska funktion som den logiska kretsen måste implementera. I det här fallet anges endast logiktabellens sanningstabell. Vi kommer att analysera bara ett sådant exempel, det vill säga vi kommer att lösa ett problem som är helt motsatt problemet med att analysera logiska kretsar som övervägs ovan.

Exempel 6. Bygg en logisk krets som implementerar en funktion med en given sanningstabell.

Problemet med att bestämma sanningens uttryck uppstår inför många vetenskaper. Varje bevisdisciplin måste förlita sig på vissa kriterier för bevisens giltighet. Vetenskapen som studerar dessa kriterier kallas logikens algebra. Huvudpostulatet för logikens algebra är att alla mest utsmyckade uttalanden kan representeras i form av ett algebraiskt uttryck från enklare uttalanden, vars sanning eller falskhet är lätt att bestämma.

För varje "algebraisk" åtgärd på ett uttalande ställs en regel för att bestämma sanningen eller falskheten i det ändrade uttalandet, baserat på sanningen eller falskheten i det ursprungliga uttalandet. Dessa regler skrivs igenom uttryck sanningstabeller... Innan du sammanställer sanningstabeller måste du bekanta dig med logikens algebra.

Algebraiska omvandlingar av logiska uttryck

Varje logiskt uttryck, som dess variabler (uttalanden), tar två värden: falskt eller sant... Falskt indikeras med noll och sanningen indikeras av en. Efter att ha behandlat definitionsdomänen och utbudet av giltiga värden kan vi överväga handlingarna i logikens algebra.

Negation

Negation och inversion - den enklaste logiska omvandlingen. Det motsvarar partikeln "inte". Denna omvandling vänder helt enkelt påståendet. Följaktligen är innebörden av uttalandet också omvänd. Om uttalande A är sant är "inte A" falskt. Till exempel är uttalandet "en rät vinkel är en vinkel på nittio grader" sant. Då är hans negation "rätt vinkel inte lika med nittio grader" en lögn.

Sanningstabell för negation skulle vara så här:

Åtskiljande

Denna operation kan vara regelbunden eller strikt, deras resultat kommer att variera.

Regelbunden disjunktion eller logisk addition matchar konjunktionen "eller". Det kommer att vara sant om minst ett av uttalandena i det är sant. Exempelvis kommer uttrycket "Jorden är rund eller står på tre valar" att vara sant, eftersom det första uttalandet är sant, även om det andra är falskt. I tabellen kommer det att se ut så här:

Stark disjunktion eller modultillägg kallas också "exklusiv eller"... Denna operation kan ta formen av den grammatiska konstruktionen "en av två saker: antingen ... eller ...". Här kommer värdet av ett logiskt uttryck att vara falskt om alla uttalanden som ingår i det har samma sanning. Båda uttalandena är antingen sanna tillsammans eller falska tillsammans.

Tabell över värden för exklusiv eller

Implikation och likvärdighet

Implikationen är följd och kan uttrycks grammatiskt som "från A följer B". Här kommer uttalande A att kallas en förutsättning och B - en konsekvens. Implikationen kan bara vara falsk i ett fall: om förutsättningen är sann och konsekvensen är falsk. Det vill säga en lögn kan inte följa sanningen. I alla andra fall är innebörden sant. Alternativ när båda uttalandena har samma sanning väcker inte frågor. Men varför är den korrekta konsekvensen av fel förutsättning sant? Poängen är att allt kan följa av en falsk premiss. Det är detta som skiljer implikation från ekvivalens.

I matematik (och andra evidensbaserade discipliner) används implikationer för att indikera ett nödvändigt tillstånd. Till exempel, uttalande A - "punkt O är extremum av en kontinuerlig funktion", uttalande B - "derivatet av en kontinuerlig funktion vid punkt O försvinner". Om O verkligen är ytterpunkten för en kontinuerlig funktion, kommer derivatet vid denna punkt faktiskt att vara lika med noll. Om O inte är en extrem punkt, kan derivatet vid denna punkt eller inte vara noll. Det vill säga, B är nödvändigt för A, men inte tillräckligt.

Sanningstabell för implikation som följer:

Den logiska driftsekvivalensen är i huvudsak ömsesidig implikation... "A motsvarar B" betyder att "från A följer B" och "från B följer A" samtidigt. Likvärdighet är sant när båda påståenden är antingen samtidigt sanna eller samtidigt falska.

I matematik används ekvivalens för att definiera ett nödvändigt och tillräckligt villkor. Till exempel, uttalande A - "Punkt O är ytterpunkten för en kontinuerlig funktion", uttalande B - "Vid punkt O försvinner funktionens derivat och ändrar tecken." Dessa två påståenden är likvärdiga. B innehåller ett nödvändigt och tillräckligt villkor för A. Observera att i detta exempel på uttalanden B faktiskt är sammankopplingen av två andra: "derivatet vid O försvinner" och "derivatet vid O ändrar tecken".

Andra logiska funktioner

Ovan har vi diskuterat de grundläggande logiska operationerna som ofta används. Det finns andra funktioner som används:

• Schaeffers stroke eller inkompatibilitet är förnekandet av sammankopplingen av A och B.
• Pierces pil representerar ett disjunktionsnegationsfel.

Bygga sanningstabeller

För att skapa en sanningstabell för alla logiska uttryck måste du agera i enlighet med algoritmen:

1. Dela upp uttrycket i enkla uttalanden och märk var och en som en variabel.
2. Definiera logiska transformationer.
3. Bestäm åtgärdsordningen för dessa omvandlingar.
4. Räkna raderna i framtida tabell. Deras antal är lika med två till kraften för N, där N är antalet variabler plus en rad för tabellhuvudet.
5. Bestäm antalet kolumner. Det är lika med summan av antalet variabler och antalet åtgärder. Du kan representera resultatet av varje åtgärd som en ny variabel, om det är vettigt.
6. Rubriken fylls i sekventiellt, först alla variablerna, sedan resultaten av åtgärder i den ordning de körs.
7. Du bör börja fylla tabellen med den första variabeln. För det halveras antalet rader. Den ena halvan är fylld med nollor, den andra hälften med enarna.
8. För varje efterföljande variabel växlar nollor och en två gånger så ofta.
9. Således fylls alla kolumner med variabler och för den sista variabeln ändras värdet i varje rad.
10. Sedan fylls resultaten av alla åtgärder i följd.

Som ett resultat visar den sista kolumnen värdet för hela uttrycket beroende på variabelns värde.

Separat bör det sägas om logisk ordning... Hur definierar man det? Här, som i algebra, finns det regler som bestämmer sekvensen av åtgärder. De körs i följande ordning:

1. uttryck inom parentes;
2. negation eller inversion;
3. samband;
4. strikt och ordinarie uppdelning;
5. inblandning;
6. likvärdighet.

Exempel på

För att konsolidera materialet kan du försöka sammanställa en sanningstabell för de tidigare nämnda logiska uttrycken. Låt oss titta på tre exempel:

• Schaeffers stroke.
• Pierces pil.
• Bestämning av ekvivalens.

Schaeffers stroke

Schaeffers stroke är ett logiskt uttryck som kan skrivas som "inte (A och B)". Det finns två variabler och två åtgärder. Sammankopplingen inom parentes betyder att den utförs först. Tabellen kommer att ha en rubrik och fyra rader med variabla värden, samt fyra kolumner. Låt oss fylla i tabellen:

A	B	A och B	inte (A och B)
L	L	L	OCH
L	OCH	L	OCH
OCH	L	L	OCH
OCH	OCH	OCH	L

Negation av konjunktion ser ut som en disjunktion av negation. Detta kan verifieras genom att sammanställa en sanningstabell för uttrycket "inte A eller inte B". Gör det själv och notera att det redan kommer att finnas tre operationer.

Pierce's Arrow

Med tanke på Peirce Arrow, som är förnekandet av disjunktionen "inte (A eller B)", låt oss jämföra den med sammanslutningen av negativa "inte A och inte B". Låt oss fylla i två tabeller:

A	B	inte A	inte B	inte A och inte B
L	L	OCH	OCH	OCH
L	OCH	OCH	L	L
OCH	L	L	OCH	OCH
OCH	OCH	L	L	L

Värdena för uttrycken matchade. Efter att ha granskat dessa två exempel kan du komma till slutsatsen hur man expanderar parenteser efter negation: negation tillämpas på alla variabler inom parentes, konjunktionsändringar till disjunktion och disjunktion till konjunktion.

Bestämning av ekvivalens

Om uttalanden A och B kan vi säga att de är ekvivalenta om och bara om A följer från A och från B följer A. Låt oss skriva detta som ett logiskt uttryck och bygga en sanningstabell för det. "(A motsvarar B) motsvarar (från A följer B) och (från B följer A)".

Det finns två variabler och fem åtgärder. Vi bygger ett bord:

I den sista kolumnen är alla värden sanna. Detta betyder att ovanstående definition av ekvivalens är sant för alla värden på A och B. Därför är det alltid sant. Exakt med hjälp av en sanningstabell du kan kontrollera riktigheten av alla definitioner och logiska konstruktioner.

Logikens algebra

Logikens algebra

Logikens algebra (eng. logikens algebra) - en av de viktigaste delarna av matematisk logik, där metoderna för algebra används i logiska transformationer.

Grundaren av logikens algebra är den engelska matematikern och logikern J. Boole (1815-1864), som baserade sin logiska undervisning på analogin mellan algebra och logik. Han skrev ned alla yttranden med hjälp av symbolerna för det språk han utvecklade och fick "ekvationer", vars sanning eller falskhet kunde bevisas baserat på vissa logiska lagar, såsom lagar om kommutativitet, distribution, associativitet etc.

Modern logikens algebraär en gren av matematisk logik och studerar logiska operationer på uttalanden med hänsyn till deras sanningsvärde (sant, falskt). Uttalanden kan vara sanna, falska eller innehålla sanning och falskhet i olika proportioner.

Logiskt uttalande - är alla deklarativa meningar för vilka det entydigt kan hävdas att dess innehåll är sant eller falskt.

Till exempel är "3 gånger 3 lika med 9", "Arkhangelsk norr om Vologda" är sanna uttalanden, och "Fem är mindre än tre", "Mars är en stjärna" är falska.

Uppenbarligen kan inte alla meningar vara ett logiskt uttalande, eftersom det inte alltid är vettigt att prata om dess falskhet eller sanning. Uttrycket "Datavetenskap är ett intressant ämne" är till exempel vagt och kräver ytterligare information, och uttalandet "För en 10-årig student A. A. Ivanov är datavetenskap ett intressant ämne", beroende på A. A. Ivanovs intressen, kan få betydelsen av "sanning" "Liggande".

Förutom tvåvärderad propositionell algebra, där endast två värden accepteras - "true" och "false", finns det mångsidig propositionell algebra. I sådan algebra används, förutom betydelserna "sant" och "falskt", sådana sanningsvärden som "troligen", "möjligt", "omöjligt", etc.

I algebra skiljer sig logiken enkel (elementärt) yttranden, betecknad med latinska bokstäver (A, B, C, D, ...), och komplex (komposit), sammansatt av flera enkla som använder logiska anslutningar, till exempel "Inte", "och", "eller", "då och bara då", "om ... då"... Sanningen eller falskheten hos komplexa uttalanden som erhållits på detta sätt bestäms av innebörden av enkla uttalanden.

Låt oss beteckna som A uttalandet "Logikens algebra tillämpas framgångsrikt i teorin om elektriska kretsar", och genom I - "Logikalgebra används i syntesen av reläkontaktkretsar."

Sedan kan det sammansatta påståendet "Logikens algebra framgångsrikt tillämpas i teorin om elektriska kretsar och i syntesen av reläkontaktkretsar" kan skrivas kort som A och B; här "och" är en logisk koppling. Det är uppenbart att eftersom elementära uttalanden A och B är sanna, då sammansatta uttalandet A och B.

Varje logiskt bindemedel betraktas som en operation på logiska uttalanden och har sitt eget namn och beteckning.

Det finns bara två logiska värden: sant sant) och false (FALSE)... Detta motsvarar den digitala representationen - 1 och 0 ... Resultaten av varje logisk operation kan registreras i en tabell. Sådana tabeller kallas sanningstabeller.

Grundläggande funktioner för boolesk algebra

1. Logisk negation, inversion (lat. inversion- inversion) är en logisk operation, som ett resultat av vilket ett nytt uttalande erhålls från ett givet uttalande (till exempel A) ( inte A), som kallas förnekande av det ursprungliga uttalandet, betecknas symboliskt med en stapel ovan ($ A↖ (-) $) eller med sådana konventioner som ¬, "inte"och läser: "Inte A", "A är falskt", "det är inte sant att A", "negation av A"... Till exempel "Mars är en planet i solsystemet" (säger A); ”Mars är inte en planet i solsystemet” ($ A↖ (-) $); påståendet "10 är ett primtal" (uttalande B) är falskt; uttalandet "10 är inte ett primtal" (uttalande B) är sant.

En operation som används med avseende på en kvantitet kallas unary... Tabellen över värden för denna operation har formen

Påståendet $ A↖ (-) $ är falskt när A är sant och sant när A är falskt.

Geometriskt kan negationen representeras på följande sätt: om A är någon uppsättning punkter är $ A↖ (-) $ komplementet till uppsättningen A, det vill säga alla punkter som inte tillhör uppsättningen A.

2. Samband (lat. konjunktio - anslutning) - logisk multiplikation, en operation som kräver minst två logiska värden (operander) och ansluter två eller flera uttalanden med en länk "och" (t.ex, "A och B"), som symboliskt betecknas med tecknet ∧ (A ∧ B) och lyder: "A och B". Följande tecken används också för att indikera konjunktion: A ∙ B; A & B, A och B, och ibland sätts inget tecken mellan uttalandena: AB. Ett exempel på logisk multiplikation: "Den här triangeln är likbenad och rätvinklig." Ett givet uttalande kan bara vara sant om båda villkoren är uppfyllda, annars är uttalandet falskt.

A	B	A ∧ B
1	0	0
0	1	0
0	0	0
1	1	1

Yttrande A ∧ I är sant endast om båda påståenden - A och I är sanna.

Geometriskt kan en förening representeras enligt följande: if A, B A ∧ I det finns en korsning av uppsättningar A och I.

3. Åtskiljande (lat. åtskiljande - separation) - logiskt tillägg, en operation som ansluter två eller flera uttalanden med hjälp av en bunt "eller" (t.ex, "A eller B"), vilket symboliskt betecknas med tecknet ∨ (A∨ I) och lyder: "A eller B"... Följande tecken används också för att indikera disjunktion: A + B; A eller B; A | B... Ett exempel på logiskt tillägg: "Antalet x är delbart med 3 eller 5". Detta uttalande kommer att vara sant om båda villkoren är sanna, eller åtminstone ett av villkoren.

Sanningstabellen för operationen är

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Yttrande A∨ I är endast falskt om båda påståenden - Aoch I är falska.

Geometriskt logiskt tillägg kan representeras enligt följande: om A, B Är det några uppsättningar poäng då A ∨ I Är föreningen av uppsättningar Aoch Idet vill säga figuren som förenar både fyrkanten och cirkeln.

4. Strikt åtskiljande disjunktion, tillägg mod två - en logisk operation som ansluter två påståenden med hjälp av en länk "eller", används i exklusiv mening, vilket symboliskt betecknas med tecknen ∨ ∨ eller ⊕ ( A ∨ ∨ B, A ⊕ I) och lyder: "Antingen a eller B"... Ett exempel på tilläggsmodul två är ordspråket "Denna triangel är trubbig eller akut." Uttalandet är sant om något av villkoren är sant.

Sanningstabellen för operationen är

A	I	A⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Uttalande A ⊕ B är sant endast när påståenden A och B har olika betydelse.

5. Inblandning (lat. implisito - nära besläktad) - en logisk operation som förbinder två påståenden med hjälp av en bunt "Om då" till ett komplext uttalande, vilket symboliskt betecknas med tecknet → ( A → I) och lyder: "Om A, då B", "A innebär B", "B följer från A", "A innebär B"... Tecknet ⊃ (A ⊃ B) används också för att beteckna implikationer. Ett exempel på en implikation: "Om den resulterande fyrkanten är en kvadrat kan en cirkel beskrivas runt den." Denna operation förbinder två enkla logiska uttryck, varav det första är ett tillstånd och det andra är en följd. Resultatet av en operation är endast falskt när förutsättningen är sant och effekten är falsk. Till exempel, ”Om 3 * 3 \u003d 9 (A), då är solen en planet (B)”, är resultatet av implikationen A → B falskt.

Sanningstabellen för operationen är

A	I	A→ I
1	0	0
0	1	1
0	0	1
1	1	1

För implikationens funktion är det sant att allt kan följa av en lögn, men bara sanningen kan följa av sanningen.

6. Likvärdighet, dubbel implikation, ekvivalens (lat. aequalis- lika och valentis - valid) - en logisk operation som tillåter två påståenden A och I få ett nytt uttalande A ≡ Bsom lyder: "A motsvarar B"... Följande symboler används också för att beteckna ekvivalens: ⇔, ∼. Denna operation kan uttryckas av ligament "Då och bara då", "nödvändigt och tillräckligt", "motsvarande"... Ett exempel på ekvivalens är uttalandet: "En triangel kommer att vara rektangulär om och endast om en av vinklarna är 90 grader."

Sanningstabellen för ekvivalensoperationen har formen

A	I	A∼ I
1	0	0
0	1	0
0	0	1
1	1	1

Operationen av ekvivalens är motsatsen till additionsmodul två och har resultatet "sant" om och endast om värdena för variablerna sammanfaller.

Att känna till betydelsen av enkla uttalanden är det möjligt att bestämma betydelsen av komplexa uttalanden på grundval av sanningstabeller. Det är viktigt att veta att tre operationer är tillräckliga för att representera alla funktioner i logikens algebra: konjunktion, disjunktion och negation.

Prioriteten för att utföra logiska operationer är följande: negation ( "inte") har högsta prioritet, sedan konjunktion ( "och"), efter konjunktion - disjunktion ( "eller").

Med hjälp av logiska variabler och logiska operationer kan alla logiska uttalanden formaliseras, det vill säga ersättas med en logisk formel. Samtidigt kan elementära påståenden som bildar ett sammansatt uttalande vara helt orelaterade i betydelse, men detta stör inte bestämningen av sanningen eller falskheten i ett sammansatt uttalande. Till exempel uttalandet ”Om fem är mer än två ( A), då kommer tisdag alltid efter måndag ( I) "- implikation A→ I, och resultatet av operationen i detta fall är "sant". I logiska operationer tas inte betydelsen av uttalanden med i beräkningen, bara deras sanning eller falskhet beaktas.

Tänk till exempel på konstruktionen av ett sammansatt uttalande från uttalanden A och Ivilket skulle vara falskt om och endast om båda uttalandena är sanna. I sanningstabellen för funktionen av additionsmodul två hittar vi: 1 ⊕ 1 \u003d 0. Och uttalandet kan till exempel vara detta: "Den här bollen är helt röd eller helt blå." Därför, om uttalandet A "Den här bollen är helt röd" är sant, och uttalandet I ”Den här bollen är helt blå” är sant, då är det sammansatta uttalandet en lögn, eftersom bollen inte kan vara både röd och blå samtidigt.

Exempel på problemlösning

Exempel 1. Bestäm för det angivna värdet av X värdet för det logiska uttalandet ((X\u003e 3) ∨ (X< 3)) → (X < 4) :

1) X \u003d 1; 2) X \u003d 12; 3) X \u003d 3.

Beslut. Sekvensen av operationer är som följer: först utförs jämförelseoperationer inom parentes, sedan disjunktion, och den sista operationen är implikation. Disjunktionsoperationen ∨ är falsk om och endast om båda operanderna är falska. Sanningstabellen för implikationen är

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

Härifrån får vi:

1) för X \u003d 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) för X \u003d 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) för X \u003d 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Exempel 2. Ange uppsättningen helvärden X för vilka uttrycket ¬ ((X\u003e 2) → (X\u003e 5)) är sant.

Beslut. Negationsoperationen tillämpas på hela uttrycket ((X\u003e 2) → (X\u003e 5)), och därför, när uttrycket ¬ ((X\u003e 2) → (X\u003e 5)) är sant, är uttrycket ((X\u003e 2) → (X \u003e 5)) är falskt. Därför är det nödvändigt att bestämma för vilka värden för X uttrycket ((X\u003e 2) → (X\u003e 5)) är falskt. Implikationsåtgärden tar endast på värdet "falskt" i ett fall: när sanningen följer falskt. Och detta görs endast för X \u003d 3; X \u003d 4; X \u003d 5.

Exempel 3 För vilka av de givna orden är påståendet ¬ (första bokstaven i en vokal ∧ tredje bokstaven i en vokal) ⇔ en sträng på 4 tecken falsk? 1) assa; 2) kakor; 3) majs; 4) fel; 5) stark man.

Beslut. Låt oss överväga alla föreslagna ord i ordning:

1) för ordet ass får vi: ¬ (1 ∧ 0) ⇔ 1, 1 ⇔ 1 - påståendet är sant;

2) för ordet kuku får vi: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - påståendet är sant;

3) för ordet majs får vi: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - påståendet är falskt;

4) för ordet fel får vi: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - påståendet är sant;

5) för ordet starkman får vi: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - påståendet är falskt.

Booleska uttryck och deras transformation

Under logiskt uttryck det bör förstås att en sådan post kan ta det logiska värdet "true" eller "false". Med denna definition är det nödvändigt att skilja mellan logiska uttryck:

• uttryck som använder jämförelseoperationer ("större än", "mindre än", "lika", "inte lika", etc.) och tar logiska värden (till exempel uttrycket a\u003e b, där a \u003d 5 och b \u003d 7, är lika med värdet "falskt");
• direkta logiska uttryck associerade med logiska värden och logiska operationer (till exempel A ∨ B ∧ C, där A \u003d true, B \u003d false och C \u003d true).

Booleska uttryck kan inkludera funktioner, algebraiska operationer, jämförelseoperationer och logiska operationer. I det här fallet är prioriteten för att utföra åtgärder följande:

1. beräkning av befintliga funktionella beroenden;
2. utförande av algebraiska operationer (först multiplicering och delning, sedan subtraktion och addition);
3. genomföra jämförelseåtgärder (i ingen särskild ordning);
4. utförande av logiska operationer (i början utförs negationsoperationer, sedan utförs operationer av logisk multiplikation, logisk addition, de senaste operationerna av implikation och ekvivalens).

Booleska uttryck kan använda parenteser som ändrar ordningen i vilken operationer utförs.

Exempel.Hitta värdet av ett uttryck:

$ 1 ≤ a ∨ A ∨ sin (π / a - π / b)< 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B) $ för a \u003d 2, b \u003d 3, A \u003d sant, B \u003d falskt.

Beslut. Räknarens ordning:

1) b a + a b\u003e a + b, efter substitution får vi: 3 2 + 2 3\u003e 2 + 3, dvs 17\u003e 2 + 3 \u003d sant;

2) A ∧ B \u003d true ∧ false \u003d false.

Därför är uttrycket inom parentes (b a + a b\u003e a + b ∨ A ∧ B) \u003d sant ∨ falskt \u003d sant;

3) 1 ≤ a \u003d 1 ≤ 2 \u003d sant;

4) sin (π / a - π / b)< 1 = sin(π/2 - π/3) < 1 = истина.

Efter dessa beräkningar får vi äntligen: sanning ∨ A ∧ sanning ∧ ¬В ∧ ¬ sant.

Negationsoperationer bör nu utföras, följt av logisk multiplikation och tillägg:

5) ¬В \u003d ¬falskt \u003d sant; Sant \u003d falskt;

6) A ∧ sant ∧ sant ∧ falskt \u003d sant ∧ sant ∧ sant ∧ falskt \u003d falskt;

7) sant ∨ falskt \u003d sant.

Således är resultatet av ett booleskt uttrycksvärde "sant".

Notera. Med tanke på att det ursprungliga uttrycket i slutändan är summan av två termer och värdet av ett av dem är 1 ≤ a \u003d 1 ≤ 2 \u003d sant, utan ytterligare beräkningar kan vi säga att resultatet för hela uttrycket också är "sant".

Identiska omvandlingar av logiska uttryck

I logikens algebra uppfylls de grundläggande lagarna som gör det möjligt att genomföra identiska omvandlingar av logiska uttryck.

Lag	För ∨	För ∧
Drivning	A ∨ B \u003d B ∨ A	A ∧ B \u003d B ∧ A
Kombination	A ∨ (B ∨ C) \u003d (B ∨ A) ∨ C	A ∧ (B ∧ C) \u003d (A ∧ B) ∧ C
Korsning	A ∧ (B ∨ C) \u003d (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C \u003d (A ∨ B) ∧ (A ∨ C)
De Morgans regler	$ (A ∨ B) ↖ (-) $ \u003d $ A↖ (-) ∧ B↖ (-) $	$ (A ∧ B) ↖ (-) $ \u003d $ A↖ (-) ∨ B↖ (-) $
Idempotencies	A ∨ A \u003d A	A ∧ A \u003d A
Absorption	A ∨ A ∧ B \u003d A	A ∧ (A ∨ B) \u003d A
Limning	(A ∧ B) ∨ (A↖ (-) ∧ B) \u003d B	(A ∨ B) ∧ (A↖ (-) ∨ B) \u003d B
Variabel drift med dess inversion	$ A ∨ A↖ (-) $ \u003d 1	$ A ∧ A↖ (-) $ \u003d 0
Drift med konstanter	A ∨ 0 \u003d A A ∨ 1 \u003d 1	A ∧ 1 \u003d A. A ∧ 0 \u003d 0
Dubbel negation	$ A↖ (\u003d) $ \u003d A.

Bevis för dessa uttalanden görs på grundval av att konstruera sanningstabeller för motsvarande poster.

Motsvarande transformationer av logiska formler har samma syfte som transformationer av formler i vanlig algebra. De tjänar till att förenkla formler eller ta dem till en viss form genom att använda de grundläggande lagarna i logikens algebra. Under förenkla formeln, som inte innehåller operationerna av implikation och ekvivalens, förstås vara en ekvivalent transformation som leder till en formel som innehåller antingen mindre än det initiala antalet operationer eller färre variabler.

Vissa transformationer av logiska formler liknar transformationer av formler i vanlig algebra (tar den gemensamma faktorn utanför parenteserna, använder förskjutnings- och kombinationslagar, etc.), medan andra transformationer baseras på egenskaper som vanlig algebra inte har (med hjälp av fördelningslagen för konjunktion) , absorptionslagar, limning, de Morgan, etc.).

Låt oss titta på exempel på några av de tekniker och metoder som används för att förenkla logiska formler:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 \u003d X1 ∧ X2 ∨ ¬X1 ∧ X2 \u003d (X1 ∨ ¬X1) ∧ X2 \u003d 1 ∧ X2 \u003d X2.

För transformation här kan du tillämpa lagen om idempotens, distributionslagen; en invers variabel operation och en konstant operation.

2) X1 ∨ X1 ∧ X2 \u003d X1 ∨ (1 ∨ 1 ∧ X2) \u003d X1 ∨ (1 ∨ X2) \u003d X1.

Här, för enkelhetens skull, tillämpas absorptionslagen.

3) ¬ (X1 ∧ X2) ∨ X2 \u003d (¬X1 ∨ ¬X2) ∨ X2 \u003d ¬X1 ∨ ¬X2 ∨ X2 \u003d ¬X1 ∨ 1 \u003d 1.

Vid transformering tillämpas de Morgans regel, funktionen för en variabel med dess inversion, en operation med en konstant

Exempel på problemlösning

Exempel 1. Hitta ett booleskt uttryck som motsvarar A ∧ ¬ (¬B ∨ C).

Beslut. Vi tillämpar de Morgans regel för B och C: ¬ (¬B ∨ C) \u003d B ∧ ¬C.

Vi får ett uttryck som motsvarar det ursprungliga: A ∧ ¬ (¬B ∨ C) \u003d A ∧ B ∧ ¬C.

Svar: A ∧ B ∧ ¬C.

Exempel 2. Ange värdet på de logiska variablerna A, B, C, för vilka värdet på det logiska uttrycket (A ∨ B) → (B ∨ ¬C ∨ B) är falskt.

Beslut. Implikationens funktion är falsk endast i fallet när en falsk följer av den verkliga förutsättningen. För ett givet uttryck måste därför förutsättningen A ∨ B ta värdet "sant", och konsekvensen, det vill säga uttrycket B ∨ ¬C ∨ B, måste ta värdet "falskt".

1) A ∨ B - resultatet av disjunktionen är "true" om minst en av operanderna är "true";

2) B ∨ ¬C ∨ B - uttrycket är falskt om alla termer har värdet "falskt", det vill säga B - "falskt"; ¬C - "falskt", och därför har variabeln C värdet "sant";

3) om vi tar hänsyn till förutsättningen och tar hänsyn till att B är ”falskt”, får vi att värdet på A är ”sant”.

Svar: A är sant, B är falskt, C är sanning.

Exempel 3 Vad är det största heltalet X för vilket påståendet (35

Beslut. Låt oss skriva ner sanningstabellen för implikationsoperationen:

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

Uttryck X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Svar: X \u003d 5.

Använda booleska uttryck för att beskriva geometriska regioner

Booleska uttryck kan användas för att beskriva geometriska områden. I det här fallet formuleras problemet enligt följande: för ett givet geometriskt område, skriv ner ett sådant logiskt uttryck som tar värdet "true" för värden x, y om och endast om någon punkt med koordinater (x; y) tillhör det geometriska området.

Låt oss överväga beskrivningen av ett geometriskt område med hjälp av ett logiskt uttryck med hjälp av exempel.

Exempel 1. En bild av ett geometriskt område specificeras. Skriv ett booleskt uttryck som beskriver uppsättningen punkter som tillhör det.

1) .

Beslut. En given geometrisk region kan representeras som en uppsättning av följande regioner: den första regionen - D1 - halvplan $ (x) / (- 1) + (y) / (1) ≤ 1 $, den andra - D2 - cirkel med centrum vid ursprunget $ x ^ 2 + y ^ 2 ≤ 1 $. Deras korsning D1 $ ∩ $ D2 är önskad domän.

Resultat:booleskt uttryck $ (x) / (- 1) + (y) / (1) ≤ 1 ∧ x ^ 2 + y ^ 2 ≤ 1 $.

2)

Detta område kan skrivas så här: | x | ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1.

Notera. När man konstruerar ett logiskt uttryck används icke-strikta ojämlikheter, vilket innebär att figurernas gränser också tillhör det skuggade området. Om strikta ojämlikheter används kommer inte gränserna att beaktas. Gränser som inte tillhör regionen visas vanligtvis med en prickad linje.

Du kan lösa det omvända problemet, nämligen: rita ett område för ett givet logiskt uttryck.

Exempel 2.Rita och skugga ett område för vars punkter det logiska tillståndet är uppfyllt y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Beslut.Det eftertraktade området är skärningspunkten mellan tre halvplan. Vi bygger på planet (x, y) raka linjer y \u003d x; y \u003d -x; y \u003d 2. Dessa är områdets gränser, och den sista gränsen y \u003d 2 tillhör inte området, så vi drar den med en prickad linje. För att tillfredsställa ojämlikheten y ≥ x är det nödvändigt att punkterna är till vänster om linjen y \u003d x, och ojämlikheten y \u003d -x är uppfylld för punkterna som är till höger om linjen y \u003d -x. Villkor y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Använda logiska funktioner för att beskriva elektriska kretsar

Logiska funktioner är mycket användbara för att beskriva hur elektriska kretsar fungerar. Så, för kretsen som visas i fig., Där värdet på variabeln X är strömställarens tillstånd (om den är på, är värdet X "sant", och om den är av, är den "falsk"), är detta värde på Y tillståndet för glödlampan (om den är på - värde "true", och om inte - "false") kommer den logiska funktionen att skrivas på följande sätt: Y \u003d X. Funktionen Y kallas ledningsförmåga.

För den krets som visas i fig. Har den logiska funktionen Y formen: Y \u003d X1 ∪ X2, eftersom en påslagen omkopplare räcker för att ljuset ska brinna. I kretsen i fig., För att ljuset ska brinna måste båda omkopplarna vara påslagna, därför är konduktivitetsfunktionen: Y \u003d X1 ∧ X2.

För en mer komplex krets blir konduktansfunktionen: Y \u003d (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

Kretsen kan också innehålla förslutningskontakter. I det här fallet säkerställer den öppna kontakten som en omkopplare att lampan tänds när knappen släpps snarare än att man trycker på den. För sådana kretsar beskrivs kopplingsbrytaren genom förnekande.

De två scheman kallas likvärdigom strömmen passerar genom en av dem när den också passerar genom den andra. Av de två ekvivalenta kretsarna är kretsen enklare, vars ledningsförmåga innehåller färre element. Uppgiften att hitta de enklaste systemen bland motsvarande är mycket viktig.

Använda apparaten för logisk algebra vid utformningen av logiska kretsar

Algebra för logisk matematik är mycket praktiskt för att beskriva hur datorhårdvara fungerar. All information när den bearbetas på en dator representeras i binär form, det vill säga den kodas av någon sekvens av 0 och 1. Behandlingen av binära signaler motsvarande 0 och 1 utförs i datorn av logiska element. Logiska grindar som utför grundläggande logiska operationer OCH, ELLER, INTE, visas i fig.

Symboler för logiska element är standard och används vid upprättande av logiska kretsar på en dator. Med hjälp av dessa scheman kan du implementera vilken logisk funktion som helst som beskriver hur en dator fungerar.

Tekniskt är ett datalogiskt element implementerat i form av en elektrisk krets, som är en anslutning av olika delar: dioder, transistorer, motstånd, kondensatorer. Ingången till ett logiskt element, som också kallas en grind, tar emot elektriska signaler med höga och låga spänningsnivåer, och en utsignal ges också antingen hög eller låg nivå. Dessa nivåer motsvarar en av tillstånden i det binära systemet: 1 - 0; SANT är FALSKT. Varje logiskt element har sin egen beteckning som uttrycker sin logiska funktion men inte anger vilken typ av elektronisk krets som är implementerad i den. Detta gör det lättare att skriva och förstå komplexa logiska kretsar. Driften av logiska kretsar beskrivs med hjälp av sanningstabeller. Konventionell beteckning på ELLER-kretsen, tecknet "1" - från den föråldrade beteckningen för disjunktion som "\u003e \u003d 1" (värdet för disjunktionen är 1 om summan av de två operanderna är större än eller lika med 1). "&" -Tecknet i AND-diagrammet är en förkortning av det engelska ordet och.

Elektroniska logikkretsar består av logiska element som utför mer komplexa logiska operationer. En uppsättning logiska element som består av INTE, ELLER OCH element, med vilka du kan bygga en logisk struktur av vilken komplexitet som helst, kallas funktionellt komplett.

Bygga booleska sanningstabeller

För en logisk formel kan du alltid skriva sanningstabellen, det vill säga att representera en given logisk funktion i tabellform. I detta fall måste tabellen innehålla alla möjliga kombinationer av funktionsargument (formler) och motsvarande funktionsvärden (formelresultat för en given uppsättning värden).

En bekväm form av notering för att hitta värdena för en funktion är en tabell som, förutom värdena för variabler och funktionsvärden, också värdena för mellanliggande beräkningar. Tänk på ett exempel på att konstruera en sanningstabell för formeln $ (X1) ↖ (-) ∧ X2 ∨ (X1 ∨ X2) ↖ (-) ∨ X1 $.

X1	X2	$ (X1) ↖ (-) $	$ (X1) ↖ (-) $ \\ X2	X1 ∧ X2	$ (X1 ∨ X2) ↖ (-) $	$ (X1) ↖ (-) $ ∧ X2 ∨ $ (X1 ∨ X2) ↖ (-) $	$ (X1) ↖ (-) $ ∧ X2 ∨ $ (X1 ∨ X2) ↖ (-) $ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Om en funktion tar värdet 1 för alla uppsättningar variabla värden är det identiskt sant; om funktionen för alla uppsättningar ingångsvärden tar värdet 0 är det identiskt falsk; om uppsättningen utgångsvärden innehåller både 0 och 1 kallas funktionen möjlig... Ovanstående exempel är ett exempel på en identiskt sant funktion.

Att känna till den analytiska formen för en logisk funktion kan du alltid gå till tabellformen för logiska funktioner. Med hjälp av en given sanningstabell kan du lösa det omvända problemet, nämligen: för en given tabell, konstruera en analytisk formel för en logisk funktion. Det finns två former för att konstruera det analytiska beroendet av en logisk funktion enligt en given tabellfunktion.

1. Disjunktiv normal form (DNF) - summan av produkter bildade av variabler och deras negationer för falska värden.

Algoritmen för att konstruera DNF är som följer:

1. i sanningstabellen för funktionen väljs uppsättningar av argument för vilka de logiska formerna är lika med 1 ("sant");
2. alla valda logiska uppsättningar skrivs ned som logiska produkter av argument, som sekventiellt förbinder dem med varandra genom att använda en logisk summa (disjunktion);
3. för argument som är falska tillämpas negationsoperationen på den konstruerade posten.

Exempel. Konstruera en funktion som bestämmer att det första numret är lika med det andra med DNF-metoden. Sanningstabellen för funktionen är

X1	X2	F (X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Beslut. Vi väljer de uppsättningar av argumentvärden där funktionen är lika med 1. Dessa är de första och fjärde raderna i tabellen (rubrikraden tas inte med i beräkningen vid numreringen).

Vi skriver ner de logiska produkterna för argumenten för dessa uppsättningar och kombinerar dem med en logisk summa: X1 ∧ X2 ∨ X1 ∧ X2.

Vi skriver ner negationen med avseende på argumenten för de valda uppsättningarna som har ett falskt värde (den fjärde raden i tabellen; den andra uppsättningen i formeln; det första och andra elementet): X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

Svar: F (X1, X2) \u003d X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

2. Konjunktiv normal form (CNF)- produkten av de summor som bildats av variablerna och deras negationer för de verkliga värdena.

Algoritmen för att konstruera CNF är som följer:

1. uppsättningar av argument väljs i sanningstabellen för vilka logiska former är lika med 0 ("falsk");
2. alla de valda logiska uppsättningarna skrivs sekventiellt som logiska summor av argument, som förbinder dem genom operationen av en logisk produkt (konjunktion);
3. för argument som är sanna läggs negationsoperationen ner i den konstruerade posten.

Exempel på problemlösning

Exempel 1. Tänk på föregående exempel, det vill säga vi konstruerar en funktion som bestämmer att det första numret är lika med det andra med CNF-metoden. För en given funktion har dess sanningstabell formen

X1	X2	F (X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Beslut. Vi väljer uppsättningar av argumentvärden där funktionen är lika med 0. Dessa är andra och tredje raderna (titelraden tas inte med i beräkningen vid numreringen).

Vi skriver ner de logiska summorna av argumenten för dessa uppsättningar och kombinerar dem med en logisk produkt: X1 ∨ X2 ∧ X1 ∨ X2.

Vi skriver negationen i förhållande till argumenten för de valda uppsättningarna som har ett sant värde (den andra raden i tabellen, den första uppsättningen av formeln, det andra elementet; för den tredje raden är detta den andra uppsättningen av formeln, det första elementet): X1 ∨ $ (X2) ↖ (-) $ ∧ $ ( X1) ↖ (-) $ ∨ X2.

Således erhålls en registrering av den logiska funktionen i CNF.

Svar: X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2.

Funktionsvärdena erhållna med de två metoderna är ekvivalenta. För att bevisa detta uttalande använder vi logikreglerna: F (X1, X2) \u003d X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2 \u003d X1 ∧ $ (X1) ↖ (-) $ X1 ) $ ∧ $ (X1) ↖ (-) $ ∨ 0 \u003d X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

Exempel 2... Konstruera en boolesk funktion för en given sanningstabell:

Den sökte formeln: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2.

Det kan förenklas: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2 \u003d X2 ∧ (X1 ∨ $ (X1) ↖ (-) $) \u003d X2 ∧ 1 \u003d X2.

Exempel 3 För den angivna sanningstabellen, konstruera en logisk funktion med DNF-metoden.

X1	X2	X3	F (X1, X2, X3)
1	1	1	1		X1, X2, X3
1	0	1	0
0	1	1	1		$ (X1) ↖ (-) $ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $ (X3) ↖ (-) $
1	0	0	1		X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $
0	1	0	0
0	0	0	0

Den sökte formeln: X1 ∧ X2 ∧ X ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∪ X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $.

Formeln är ganska besvärlig och bör förenklas:

X1 ∧ X2 ∧ X3 ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∨ X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $ \u003d X2 ∧ X3 ∧ (X1 ∨ $ (X1) ↖ (-) $) ∨ X1 ∧ $ (X3) ↖ (-) $ ∧ (X2 ∨ $ (X2) ↖ (-) $) \u003d X2 ∧ X3 ∨ X1 ∧ $ (X3) ↖ (-) $.

Sanningstabeller för att lösa logiska problem

Sammanställningen av sanningstabeller är ett av sätten att lösa logiska problem. När du använder den här lösningen åtgärdas villkoren som problemet innehåller med hjälp av speciellt sammanställda tabeller.

Exempel på problemlösning

Exempel 1. Skapa en sanningstabell för en säkerhetsenhet som använder tre sensorer och utlöses när bara två av dem är stängda.

Beslut. Uppenbarligen blir resultatet av lösningen en tabell där den önskade funktionen Y (X1, X2, X3) kommer att ha värdet "true" om två variabler har värdet "true".

X1	X2	X3	Y (X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

Exempel 2. Gör ett schema för lektioner för dagen, med hänsyn till att en datavetenskapslektion endast kan vara den första eller andra, en matematiklektion - den första eller tredje, och fysik - den andra eller tredje. Är det möjligt att skapa ett schema som uppfyller alla krav? Hur många schemaläggningsalternativ finns det?

Beslut. Problemet löses enkelt om du upprättar lämplig tabell:

	1: a lektionen	2: a lektionen	3: e lektionen
Informatik	1	1	0
Matte	1	0	1
Fysik	0	1	1

Tabellen visar att det finns två alternativ för önskat schema:

1. matematik, datavetenskap, fysik;
2. informatik, fysik, matematik.

Exempel 3 Tre vänner kom till sportlägret - Peter, Boris och Alexey. Var och en av dem älskar två sporter. Det är känt att det finns sex sådana sporter: fotboll, hockey, skidåkning, simning, tennis, badminton. Det är också känt att:

1. Boris är den äldsta;
2. en som spelar fotboll är yngre än en som spelar hockey;
3. spelar fotboll och hockey och Peter bor i samma hus;
4. när en strid uppstår mellan en skidåkare och en tennisspelare försonar Boris dem;
5. Peter kan inte spela tennis eller badminton.

Vilka typer av sporter tycker var och en av pojkarna?

Beslut. Låt oss komponera en tabell och återspegla villkoren för problemet i den, fylla i motsvarande celler med siffrorna 0 och 1, beroende på om motsvarande uttalande är falskt eller sant.

Eftersom det finns sex typer av sporter visar det sig att alla pojkar tycker om olika sporter.

Av villkor 4 följer att Boris inte gillar skidåkning eller tennis, utan av villkor 3 och 5 att Peter inte vet hur man spelar fotboll, hockey, tennis och badminton. Därför är Petras favoritsporter skidåkning och simning. Låt oss skriva in detta i tabellen och fylla i de återstående cellerna i kolumnerna "Ski" och "Swimming" med nollor.

Tabellen visar att endast Alexey kan spela tennis.

Av villkor 1 och 2 följer att Boris inte är en fotbollsspelare. Således spelar Alexey fotboll. Låt oss fortsätta fylla i tabellen. Låt oss ange nollor i de tomma cellerna på raden "Alexey".

Slutligen får vi att Boris är förtjust i hockey och badminton. Finalbordet kommer att se ut så här:

Svar: Peter gillar skidåkning och simning, Boris spelar hockey och badminton, och Alexei spelar fotboll och tennis.

Konstruktion av sanningstabeller för komplexa uttalanden.

Boolsk prioritet

1) inversion 2) konjunktion 3) disjunktion 4) implikation och ekvivalens

Hur man gör en sanningstabell?

Per definition uttrycker sanningstabellen för en logisk formel överensstämmelsen mellan olika uppsättningar variabla värden och värdena för en formel.

För en formel som innehåller två variabler finns det bara fyra sådana uppsättningar av variabla värden:

(0, 0), (0, 1), (1, 0), (1, 1).

Om formeln innehåller tre variabler, finns det åtta möjliga uppsättningar värden för variabler (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0) ), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Antalet uppsättningar för en formel med fyra variabler är sexton, och så vidare.

En bekväm form av notering när man hittar värdena för en formel är en tabell som, förutom värdena för variabler och formelvärden, också värdena för mellanformler.

Exempel.

1. Låt oss skapa en sanningstabell för formeln 96% "style \u003d" width: 96.0% "\u003e

Tabellen visar det för alla uppsättningar värden för variablerna x och y tar formeln värdet 1det vill säga är identiskt sant.

2. Sanningstabell för formel 96% "style \u003d" width: 96.0% "\u003e

Tabellen visar det för alla uppsättningar värden för variablerna x och y, formeln tar värdet 0det vill säga är identiskt falsk .

3. Sanningstabell för formel 96% "style \u003d" width: 96.0% "\u003e

Tabellen visar det formel 0 "style \u003d" border -aps: kollaps; border: none "\u003e

Slutsats: vi har alla enheter i den sista kolumnen. Det betyder att betydelsen av ett komplext uttalande är sant för alla värden för enkla uttalanden K och C. Därför resonerade läraren logiskt korrekt.