Hogyan kell megoldani a logikai egyenleteket. Logikai egyenletek megoldása a matematikában

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, ahol J, K, L, M, N logikai változók?

Magyarázat.

Az (N ∨ ¬N) kifejezés tehát bármely N-re igaz

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

Alkalmazzuk a tagadást a logikai egyenlet mindkét oldalára, és használjuk a De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B törvényt. ¬J ∨ K ∨ ¬L ∨ M = 1.

Egy logikai összeg egyenlő 1-gyel, ha legalább az egyik alkotó állítása egyenlő 1-gyel. Ezért az eredményül kapott egyenlet a logikai változók bármely kombinációjával teljesül, kivéve azt az esetet, amikor az egyenletben szereplő összes mennyiség egyenlő 0-val. a 4 változó lehet 1 vagy 0, ezért minden lehetséges kombináció 2·2·2·2 = 16. Ezért az egyenletnek 16 −1 = 15 megoldása van.

Megjegyzendő, hogy a talált 15 megoldás megfelel az N logikai változó két lehetséges értékének bármelyikének, ezért eredeti egyenlet 30 megoldása van.

Válasz: 30

Hány különféle megoldások egyenlettel rendelkezik

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

ahol J, K, L, M, N logikai változók?

A válasznak nem kell felsorolnia a J, K, L, M és N összes különböző értékkészletét, amelyekre ez az egyenlőség érvényes. Válaszként meg kell adnia az ilyen készletek számát.

Magyarázat.

Az A → B = ¬A ∨ B és ¬(A ∨ B) = ¬A ∧ ¬B képleteket használjuk.

Tekintsük az első részképletet:

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

Tekintsük a második részképletet

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

Tekintsük a harmadik részképletet

1) M → J = 1, ezért

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

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

Kombináljuk:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 tehát 4 megoldás.

(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

Kombináljuk:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L tehát 4 megoldás.

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.

Válasz: 4 + 4 = 8.

Válasz: 8

Hány különböző megoldása van az egyenletnek?

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

ahol K, L, M, N logikai változók? A válasznak nem kell felsorolnia a K, L, M és N összes különböző értékkészletét, amelyre ez az egyenlőség vonatkozik. Válaszként meg kell adni az ilyen készletek számát.

Magyarázat.

írjuk át az egyenletet több használatával egyszerű jelölés műveletek:

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

1) az „implikáció” művelet igazságtáblázatából (lásd az első feladatot) az következik, hogy ez az egyenlőség akkor és csak akkor igaz

K + L = 1 és L M N = 0

2) az első egyenletből az következik, hogy a változók közül legalább az egyik, K vagy L egyenlő 1-gyel (vagy mindkettő együtt); nézzünk tehát három esetet

3) ha K = 1 és L = 0, akkor a második egyenlőség bármely M és N esetén teljesül; mivel két logikai változónak 4 kombinációja van (00, 01, 10 és 11), ezért 4 különböző megoldásunk van

4) ha K = 1 és L = 1, akkor a második egyenlőség érvényes M · N = 0-ra; 3 ilyen kombináció van (00, 01 és 10), van még 3 megoldásunk

5) ha K = 0, akkor L = 1 (az első egyenletből); ebben az esetben a második egyenlőség teljesül, ha M · N = 0; 3 ilyen kombináció van (00, 01 és 10), van még 3 megoldásunk

6) összesen 4 + 3 + 3 = 10 megoldást kapunk.

Válasz: 10

Hány különböző megoldása van az egyenletnek?

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

Magyarázat.

A kifejezés három esetben igaz, amikor (K ∧ L) és (M ∧ N) 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N egyenlő 1-gyel, és K és L bármi, kivéve egyszerre 1. Ezért 3 megoldás létezik.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 megoldás.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 megoldás.

Válasz: 7.

Válasz: 7

Hány különböző megoldása van az egyenletnek?

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

ahol X, Y, Z, P logikai változók? A válasznak nem kell felsorolnia az összes különböző értékkészletet, amelyre ez az egyenlőség vonatkozik. Válaszként csak az ilyen készletek számát kell megadnia.

Magyarázat.

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

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

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

A logikai VAGY csak egy esetben hamis: amikor mindkét kifejezés hamis.

Ezért,

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

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

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

Ezért az egyenletnek csak egy megoldása van.

Válasz: 1

Hány különböző megoldása van az egyenletnek?

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

ahol K, L, M, N logikai változók? A válasznak nem kell felsorolnia a K, L, M és N összes különböző értékkészletét, amelyekre ez az egyenlőség érvényes. Válaszként csak az ilyen készletek számát kell megadnia.

Magyarázat.

Logikai És csak egy esetben igaz: amikor minden kifejezés igaz.

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

Mindegyik egyenlet 3 megoldást ad.

Tekintsük az A ∧ B = 1 egyenletet, ha A és B is három esetben vesz igaz értéket, akkor az egyenletnek összesen 9 megoldása van.

Ezért a válasz 9.

Válasz: 9

Hány különböző megoldása van az egyenletnek?

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

ahol A, B, C, D logikai változók?

A válasznak nem kell felsorolnia az összes különböző A, B, C, D értékkészletet, amelyre ez az egyenlőség érvényes. Válaszként meg kell adnia az ilyen készletek számát.

Magyarázat.

A logikai „VAGY” akkor igaz, ha legalább az egyik állítás igaz.

(D ∧ ¬D)= 0 bármely D esetén.

Ezért,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, ami minden D-re 3 lehetséges megoldást ad.

(D ∧ ¬ D)= 0 bármely D-re, ami két megoldást ad (D = 1 esetén D = 0).

Ezért: teljes megoldások 2*3 = 6.

Összesen 6 megoldás.

Válasz: 6

Hány különböző megoldása van az egyenletnek?

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

Magyarázat.

Alkalmazzuk a tagadást az egyenlet mindkét oldalára:

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

A logikai VAGY három esetben igaz.

1. lehetőség.

K ∧ L ∧ M = 1, akkor K, L, M = 1 és ¬L ∧ M ∧ N = 0. N tetszőleges, azaz 2 megoldás.

2. lehetőség.

¬L ∧ M ∧ N = 1, akkor N, M = 1; L = 0, K tetszőleges, azaz 2 megoldás.

Ezért a válasz a 4.

Válasz: 4

A, B és C egész számok, amelyekre az állítás igaz

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

Mi egyenlő B, ha A = 45 és C = 43?

Magyarázat.

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

2) ezek egyszerű mondások az ∧ (ÉS, konjunkció) művelettel kapcsolódnak össze, vagyis egyidejűleg kell végrehajtani;

3) ¬(A = B)=1-ből azonnal következik, hogy A B;

4) tegyük fel, hogy A > B, akkor a második feltételből 1→(B > C)=1; ez a kifejezés akkor és csak akkor lehet igaz, ha B > C = 1;

5) ezért van A > B > C, csak a 44-es szám felel meg ennek a feltételnek;

6) minden esetre ellenőrizzük az A opciót is 0 →(B > C)=1;

ez a kifejezés bármely B-re igaz; most nézzük meg a kapott harmadik feltételt

ez a kifejezés akkor és csak akkor lehet igaz, ha C > B, és itt van egy ellentmondás, mert nincs olyan B szám, amelyre C > B > A.

Válasz: 44.

Válasz: 44

Szerkesszünk igazságtáblázatot egy logikai függvényhez

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

amelyben az A argumentum értékoszlopa a 27-es szám bináris ábrázolása, a B argumentum értékoszlopa a 77-es, a C argumentum értékoszlopa a 120-as szám. az oszlopban felülről lefelé a legjelentősebbtől a legkevésbé jelentősig (beleértve a nulla halmazt is). Alakítsa át az X függvény értékeinek így kapott bináris reprezentációját decimális rendszer Leszámolás

Magyarázat.

Írjuk fel az egyenletet a műveletek egyszerűbb jelölésével:

1) ez egy három változós kifejezés, tehát sorok lesznek az igazságtáblázatban; ezért a táblázat A, B és C oszlopainak összeállításához használt számok bináris ábrázolásának 8 számjegyből kell állnia

2) alakítsa át a 27, 77 és 120 számokat bináris rendszerré, azonnal adjon hozzá 8 számjegyű nullát a számok elejéhez

3) nem valószínű, hogy azonnal meg tudja írni az X függvény értékeit minden kombinációhoz, ezért kényelmes további oszlopokat hozzáadni a táblázathoz a köztes eredmények kiszámításához (lásd az alábbi táblázatot)

A	IN	VEL
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) töltse ki a táblázat oszlopait:

A	IN	VEL					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

az érték csak azokban a sorokban 1, ahol A = B

az érték 1 azokban a sorokban, ahol B vagy C = 1

az érték csak azokban a sorokban 0, ahol A = 1 és B + C = 0

az érték az előző oszlop inverze (a 0 helyett 1, az 1 helyett 0)

az X (utolsó oszlop) eredménye a két oszlop logikai összege és

5) a válasz megszerzéséhez írja ki az X oszlop bitjeit felülről lefelé:

6) konvertálja ezt a számot decimális rendszerre:

Válasz: 171

Melyik az a legnagyobb X egész szám, amelyre a (10 (X+1)·(X+2)) állítás igaz?

Magyarázat.

Az egyenlet két reláció közötti implikációs művelet:

1) Természetesen itt ugyanazt a módszert alkalmazhatja, mint a 2208-as példában, de meg kell oldania másodfokú egyenletek(nem akarom...);

2) Vegyük észre, hogy feltétel alapján csak az egész számok érdekelnek minket, így megpróbálhatjuk valahogy átalakítani az eredeti kifejezést, így egy ekvivalens utasítást kapunk ( pontos értékek minket egyáltalán nem érdekelnek a gyökerek!);

3) Tekintsük az egyenlőtlenséget: nyilvánvalóan lehet pozitív vagy negatív szám;

4) Könnyen ellenőrizhető, hogy a tartományban az állítás minden egész számra igaz-e, a tartományban pedig minden egész számra (hogy ne legyen összetévedés, kényelmesebb használni gyenge egyenlőtlenségek, és , és helyett );

5) Ezért egész számok esetén helyettesíthető egy ekvivalens kifejezéssel

6) egy kifejezés igazságtartománya két végtelen intervallum uniója;

7) Tekintsük most a második egyenlőtlenséget: nyilvánvaló, hogy lehet pozitív vagy negatív szám is;

8) A régióban az állítás minden egész számra igaz, a régióban pedig minden egész számra, ezért egész számokra helyettesíthető egy ekvivalens kifejezéssel

9) a kifejezés igazságtartománya zárt intervallum;

10) A megadott kifejezés mindenhol igaz, kivéve azokat a területeket, ahol és ;

11) Vegye figyelembe, hogy az érték már nem megfelelő, mert ott és , vagyis az implikáció 0-t ad;

12) 2, (10 (2+1) · (2+2)) vagy 0 → 0 helyettesítésekor, amely kielégíti a feltételt.

Tehát a válasz a 2.

Válasz: 2

Mi az a legnagyobb X egész szám, amelyre az állítás igaz?

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

Magyarázat.

Alkalmazzuk az implikációs transzformációt és alakítsuk át a kifejezést:

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

A logikai VAGY akkor igaz, ha legalább az egyik igaz logikai kijelentés. Mindkét egyenlőtlenség megoldása után azt látjuk, hogy a legnagyobb egész szám, amelyre legalább az egyik teljesül, a 7 (az ábrán a második egyenlőtlenség pozitív megoldása sárga, az első pedig kék színnel látható).

Válasz: 7

Adja meg a K, L, M, N változók értékét, amelyeknél a logikai kifejezés érvényes

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

hamis. Írja le a választ 4 karakterből álló sztringként: a K, L, M és N változók értékei (ebben a sorrendben). Így például az 1101. sor megfelel annak, hogy K=1, L=1, M=0, N=1.

Magyarázat.

A 3584. feladat megkettőzése.

Válasz: 1000

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

Magyarázat.

Alkalmazzuk az implikációs transzformációt:

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

Alkalmazzuk a tagadást az egyenlet mindkét oldalára:

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

Konvertáljuk:

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

Ezért M = 0, N = 0, most vegyük figyelembe (¬K ∧ L ∨ M ∧ L):

abból, hogy M = 0, N = 0, az következik, hogy M ∧ L = 0, akkor ¬K ∧ L = 1, azaz K = 0, L = 1.

Válasz: 0100

Adja meg a K, L, M, N változók értékét, amelyekre a logikai kifejezés vonatkozik

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

hamis. Válaszát írja le négy karakterből álló sztringként: a K, L, M és N változók értékei (ebben a sorrendben). Így például az 1101. sor megfelel annak, hogy K=1, L=1, M=0, N=1.

Magyarázat.

Írjuk fel az egyenletet a műveletek egyszerűbb jelölésével (a „kifejezés hamis” feltétel azt jelenti, hogy egyenlő a logikai nullával):

1) a feltétel megfogalmazásából az következik, hogy a kifejezés csak egy változóhalmaz esetén lehet hamis

2) az „implikáció” művelet igazságtáblázatából az következik, hogy ez a kifejezés akkor és csak akkor hamis

3) az első egyenlőség (a logikai szorzat egyenlő 1-gyel) akkor és csak akkor teljesül, ha és ; ebből következik (a logikai összeg egyenlő nullával), ami csak akkor történhet meg, ha ; Így már három változót definiáltunk

4) a második feltételből, , mert és megkapjuk .

Megkettőzi a feladatot

Válasz: 1000

Adja meg a P, Q, S, T logikai változók értékét, amelyeknél a logikai kifejezés

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) hamis.

Írja le a választ négy karakterből álló sztringként: a P, Q, S, T változók értékei (ebben a sorrendben).

Magyarázat.

(1) (P ∨ ¬Q) = 0

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

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

(2) (Q → (S ∨ Т)) = 0 Alkalmazzuk az implikáció transzformációt:

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

Válasz: 0100

Adja meg a K, L, M, N változók értékét, amelyekre a logikai kifejezés vonatkozik

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

hamis. Válaszát írja le négy karakterből álló sztringként: a K, L, M és N változók értékei (ebben a sorrendben). Így például az 1101. sor megfelel annak, hogy K=1, L=1, M=0, N=1.

Magyarázat.

A logikai VAGY akkor és csak akkor hamis, ha mindkét állítás hamis.

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

Alkalmazzuk az implikációs transzformációt az első kifejezésre:

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

Tekintsük a második kifejezést:

(L ∧ K) ∨ ¬N = 0 (lásd az első kifejezés eredményét) => L ∨ ¬N = 0 => L = 0, N = 1.

Válasz: 1001.

Válasz: 1001

Adja meg a K, L, M, N változók értékét, amelyekre a logikai kifejezés vonatkozik

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

igaz. Válaszát írja le négy karakterből álló sztringként: a K, L, M és N változók értékei (ebben a sorrendben). Így például az 1101. sor megfelel annak, hogy K=1, L=1, M=0, N=1.

Magyarázat.

A logikai „ÉS” akkor és csak akkor igaz, ha mindkét állítás igaz.

1) (K → M) = 1 Alkalmazza az implikáció transzformációt: ¬K ∨ M = 1

2) (K → ¬M) = 1 Alkalmazza az implikációs transzformációt: ¬K ∨ ¬M = 1

Ebből következik, hogy K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Alkalmazzuk az implikációs transzformációt: K ∨ (M ∧ ¬L ∧ N) = 1 abból, hogy K = 0 kapjuk:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Válasz: 0011

Ismeretes, hogy X, Y és Z egész számokra a következő állítás igaz:

(Z Mit jelent Z, ha X=25 és Y=48?

Magyarázat.

A számok behelyettesítése után azt kapjuk, hogy Z = 47.

Kérjük, vegye figyelembe, hogy ez az összetett állítás három egyszerű állításból áll

1) (Z 2) ezeket az egyszerű utasításokat az ∧ (ÉS, konjunkció) művelettel kapcsoljuk össze, azaz egyidejűleg kell végrehajtani.

3) ¬(Z+1 24-ből és ¬(Z+1 47.

4) -tól (Z Z Válasz: 47.

Válasz: 47

A, B és C olyan egész számok, amelyekre igaz a következő állítás:

(C Mi a C értéke, ha A=45 és B=18?

Magyarázat.

A logikai „ÉS” akkor és csak akkor igaz, ha mindkét állítás igaz.

Helyettesítsük be a számokat a kifejezésbe:

1) (C (C 2) ¬(C+1, C ≥ 44.

3) ¬(C+1, C ≥ 17.

A 2) és 1) pontból az következik, hogy C

Válasz: 44

¬(A = B) ∧ ((B A)) ∧ ((A 2C))

Mekkora A értéke, ha C = 8 és B = 18?

Magyarázat.

A logikai „ÉS” akkor és csak akkor igaz, ha mindkét állítás igaz.

1) ¬(A = B) = 1, azaz A ≠ 18 = 1.

2) ((B A)) Alkalmazza az implikáció transzformációt: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Alkalmazza az implikáció transzformációt: (A > 18) ∨ (A > 16) = 1

A 2) és 3) pontból az következik, hogy (18 > A) és (A > 16), mivel egyébként ellentmondás adódik: A = 17.

Válasz: 17

A, B és C egész számok, amelyekre az állítás igaz

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

Mekkora B értéke, ha A = 45 és C = 18?

Magyarázat.

A logikai „ÉS” csak akkor igaz, ha minden állítás igaz.

Noskin Andrej Nyikolajevics,
informatika tanár
legmagasabb minősítési kategória,
A hadtudományok kandidátusa, egyetemi docens
GBOU Lyceum No. 1575, Moszkva

Optimalizált leképezési módszer a 23. feladat megoldására a KIM Egységes Államvizsga számítástechnikából és IKT-ból

A KIM egységes államvizsga egyik legnehezebb feladata a 23. probléma, amelyben meg kell találnia a logikai változók különböző értékkészleteinek számát, amelyek megfelelnek a megadott feltételnek.
Ez a feladat talán a KIM Egységes Számítástechnika és IKT Államvizsga legnehezebb feladata. Általában a vizsgázók legfeljebb 5%-a birkózik meg vele (1).
A feladatot teljesítő tanulók ilyen kis százalékát a következők magyarázzák:
- a tanulók összetéveszthetik (elfelejtik) a jeleket logikai műveletek;
- matematikai hibák a számítások végrehajtása során;
- érvelési hibák a megoldás keresése során;
- hibák az egyszerűsítési folyamatban logikai kifejezések;
- megoldást javasolnak a tanárok ezt a feladatot, miután az összes munka elkészült, mivel a feltételezés valószínűsége
a hibák nagyon nagyok, és a feladat „súlya” csak egy elsődleges szempont.
Ráadásul néhány tanár maga is nehezen tudja megoldani az ilyen típusú problémákat, ezért megpróbálnak egyszerűbb problémákat megoldani a gyerekekkel.
Az is bonyolítja a helyzetet, hogy ebben a blokkban van nagy számban különféle feladatokat, és lehetetlen sablonmegoldást választani.
A helyzet javítására pedagógus közösség A problémamegoldás két fő módszere véglegesítés alatt áll ebből a típusból: megoldás bitláncokkal (2) és leképezési módszerrel (3).
Ezen módszerek finomításának (optimalizálásának) szükségessége abból adódik, hogy a feladatok folyamatosan változnak mind szerkezetükben, mind a változók számában (csak egyfajta X változó, kétféle X és Y változó, három típus: X, Y , Z).
A problémamegoldási módszerek elsajátításának nehézségét megerősíti az a tény, hogy a K.Yu. Polyakovnak 38 elemzése született az ilyen típusú problémákról (4). Egyes elemzések egynél több típusú megoldást kínálnak egy problémára.
Utóbbi időben az informatika KIM egységes államvizsgáján kétféle X és Y változóval van probléma.
Optimalizáltam a megjelenítési módszert, és a továbbfejlesztett módszer használatára ösztönöztem a hallgatóimat.
Ez eredményeket ad. Tanítványaim aránya, aki megbirkózik ezzel a feladattal, az átmenők 43%-áig terjed. Általános szabály, hogy minden évben 25-33 ember tesz le egységes államvizsgát számítástechnikából az összes 11. évfolyamból.
A kétféle feladat megjelenése előtt változó módszer A diákok nagyon sikeresen alkalmazták a leképezéseket, de az Y megjelenése után a logikai kifejezésben kezdtem észrevenni, hogy a gyerekek válaszai már nem esnek egybe a tesztekkel. Kiderült, hogy nem egészen világos, hogyan kell egy új típusú változóval leképezési táblázatot készíteni. Aztán az a gondolat jutott eszembe, hogy a kényelem kedvéért az egész kifejezést egyfajta változóra kell redukálni, ahogy az a gyermekek számára kényelmes.
További részleteket adok ezt a technikát. A kényelem kedvéért a (4)-ben megadott logikai kifejezésrendszer példáján fogom megvizsgálni.
Hány különböző megoldása van a rendszernek? logikai egyenletek

(x 1 ^ y 1)=(¬x 2 V ¬ y 2 )
(x 2 ^ y 2)= (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5) = (¬ x 6 V ¬ y 6 )

Aholx 1 , …, x 6 , y 1 , …, y 6 , - logikai változók? A válasznak nem kell felsorolnia az összes különböző változóérték-készletet, amelyre ez az egyenlőség vonatkozik. Válaszként meg kell adnia az ilyen készletek számát.
Megoldás:
1. A logikai egyenletrendszer elemzéséből azt látjuk, hogy 6 változó van Xés 6 változó U. Mivel ezen változók bármelyike csak két értéket vehet fel (0 és 1), ezeket a változókat 12 azonos típusú változóra cseréljük, például Z-re.
2. Most írjuk át a rendszert új, azonos típusú változókkal. A feladat nehézsége az lesz, hogy gondos jegyzeteket kell készíteni a változók cseréjekor.

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

3. Készítsünk egy táblázatot, amelyben végigmegyünk az összes lehetőségen z 1 , z 2 , z 3 , z 4 , mivel az első logikai egyenletben négy változó van, a táblázat 16 soros lesz (16=2 4); távolítsa el az ilyen értékeket a táblázatból z 4 , amelyre az első egyenletnek nincs megoldása (áthúzott számok).


0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. A táblázat elemzése során felállítunk egy szabályt a változópárok megjelenítésére (például egy pár Z 1 Z 2 =00 felel meg pár Z 3 Z 4 = 11) .

5. Töltse ki a táblázatot a változópárok számának kiszámításával, amelyekre a rendszernek van megoldása.

6. Adja össze az összes eredményt: 9 + 9 + 9 + 27 = 54
7. Válasz: 54.
A KIM egységes államvizsga 23. feladatának fent optimalizált megoldása lehetővé tette a hallgatók számára, hogy visszanyerjék önbizalmukat és sikeresen megoldják az ilyen típusú problémákat.

Irodalom:

1. FIPI. Módszertani ajánlások pedagógusok számára, elemzés alapján készült tipikus hibák az INFORMÁCIÓTUDOMÁNY és IKT 2015-ös Egységes Államvizsga résztvevői. Hozzáférési mód: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. K.Yu. Poljakov, M.A. Roitberg.Logikai egyenletrendszerek: megoldás bitsorok felhasználásával. Informatikai Közlöny, 2014. 12. szám, p. 4-12. Kiadó "Szeptember elseje", Moszkva.
3. E.A. Mironchik, Megjelenítési mód. Magazin Informatika, 2013. 10. szám, p. 18-26. Kiadó "Szeptember elseje", Moszkva.

Logikai egyenletrendszerek megoldása változók változtatásával

A változók helyettesítésének módszerét akkor alkalmazzuk, ha egyes változók csak meghatározott kifejezés formájában szerepelnek az egyenletekben, semmi másban. Ekkor ez a kifejezés új változóként jelölhető ki.

1. példa

Hány különböző értékkészlete van az x1, x2, x3, x4, x5, x6, x7, x8 logikai változóknak, amelyek megfelelnek az alább felsorolt feltételeknek?

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

A válasznak nem kell felsorolnia az x1, x2, x3, x4, x5, x6, x7, x8 változók összes különböző értékkészletét, amelyekre ez az egyenlőségrendszer teljesül. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Ekkor felírhatjuk a rendszert egyetlen egyenlet formájában:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. A konjunkció 1 (igaz), ha minden operandus 1 értéket vesz fel. minden implikációnak igaznak kell lennie, és ez igaz minden értékre, kivéve (1 → 0). Azok. az y1, y2, y3, y4 változók értéktáblázatában egy nem lehet a nullától balra:

Azok. a feltételek 5 y1-y4 halmazra teljesülnek.

Mert y1 = x1 → x2, akkor az y1 = 0 érték egyetlen x1, x2: (1, 0) halmazon érhető el, az y1 = 1 érték pedig három halmazon x1, x2: (0,0) , (0 ,1), (1.1). Hasonlóképpen y2, y3, y4 esetén.

Mivel az y1 változó minden halmazát (x1,x2) kombináljuk az y2 változó minden halmazával (x3,x4) stb., az x változók halmazainak száma megszorozódik:

				Készletek száma x1…x8-onként

Adjuk össze a halmazok számát: 1 + 3 + 9 + 27 + 81 = 121.

Válasz: 121

2. példa

Az x1, x2, ... x9, y1, y2, ... y9 logikai változóknak hány különböző értékkészlete van, amelyek megfelelnek az alább felsorolt feltételeknek?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

Válaszul nem szükséges sorolja fel az x1, x2, ... x9, y1, y2, ... y9 változók összes különböző értékkészletét, amelyekre a ezt a rendszert egyenlő Válaszként meg kell adnia az ilyen készletek számát.

Megoldás:

Változtassuk meg a változókat:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

A rendszer felírható egyetlen egyenletként:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Az ekvivalencia csak akkor igaz, ha mindkét operandus egyenlő. Ennek az egyenletnek két megoldása van:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Mert zi = (xi ≡ yi), akkor a zi = 0 érték két halmaznak (xi,yi): (0,1) és (1,0), a zi = 1 pedig két halmaznak (xi,yi) felel meg. ): (0 ,0) és (1,1).

Ekkor az első z1, z2,…, z9 halmaz 2 9 halmaznak felel meg (x1,y1), (x2,y2),…, (x9,y9).

Ugyanez a szám felel meg a második z1, z2,…, z9 halmaznak. Ekkor összesen 2 9 +2 9 = 1024 készlet van.

Válasz: 1024

Logikai egyenletrendszerek megoldása a módszerrel vizuális definíció rekurzió.

Ezt a módszert akkor alkalmazzuk, ha az egyenletrendszer meglehetősen egyszerű, és a halmazok számának növelésének sorrendje változók összeadásakor nyilvánvaló.

3. példa

Hány különböző megoldása van az egyenletrendszernek?

¬x9 ∨ x10 = 1,

ahol x1, x2, … x10 logikai változók?

A válasznak nem kell felsorolnia az összes különböző x1, x2, ... x10 értékkészletet, amelyre ez az egyenlőségrendszer teljesül. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás:

Oldjuk meg az első egyenletet. Egy diszjunkció akkor egyenlő 1-gyel, ha legalább az egyik operandusa egyenlő 1-gyel a megoldások a halmazok:

x1=0 esetén x2 két értéke (0 és 1), x1=1 esetén pedig csak egy x2 (1) értéke van, így az (x1,x2) halmaz az egyenlet megoldása. . Összesen 3 készlet van.

Adjuk hozzá az x3 változót, és tekintsük a második egyenletet. Hasonló az elsőhöz, ami azt jelenti, hogy x2=0 esetén x3 két értéke van (0 és 1), x2=1 esetén pedig csak egy x3 (1), így az (x2) ,x3) az egyenlet megoldása. Összesen 4 szett van.

Könnyen belátható, hogy egy másik változó hozzáadásakor egy halmaz kerül hozzáadásra. Azok. rekurzív képlet az (i+1) változók számához:

N i +1 = N i + 1. Ekkor tíz változóra 11 halmazt kapunk.

Válasz: 11

Különféle típusú logikai egyenletrendszerek megoldása

4. példa

Hány különböző értékkészlete van az x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 logikai változóknak, amelyek kielégítik az összes alább felsorolt feltételt ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

Válaszul nem szükséges sorolja fel az x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 változók azon különböző értékkészleteit, amelyekre az adott egyenlőségrendszer teljesül .

Válaszként meg kell adnia az ilyen készletek számát.

Megoldás:

Vegyük észre, hogy a rendszer három egyenlete azonos különböző független változóhalmazokon.

Nézzük az első egyenletet. Egy kötőszó csak akkor igaz (egyenlő 1-gyel), ha minden operandusa igaz (egyenlő 1-gyel). Az implikáció 1 minden sorra, kivéve (1,0). Ez azt jelenti, hogy az első egyenlet megoldása a következő x1, x2, x3, x4 halmazok, amelyekben az 1 nem jelenik meg a 0 bal oldalán (5 halmaz):

Hasonlóképpen, a második és a harmadik egyenlet megoldása is teljesen azonos y1,…,y4 és z1,…, z4 halmazokkal.

Most elemezzük a rendszer negyedik egyenletét: x 4 ∧ y 4 ∧ z 4 = 0. A megoldás minden olyan x4, y4, z4 halmaz lesz, amelyben legalább az egyik változó 0-val egyenlő.

Azok. x4 = 0 esetén minden lehetséges halmaz (y4, z4) megfelelő, x4 = 1 esetén pedig olyan (y4, z4) halmaz, amelyben van legalább egy nulla: (0, 0), (0,1) ), (1, 0).

				A készletek száma

A készletek száma összesen 25 + 4*9 = 25 + 36 = 61.

Válasz: 61

Logikai egyenletrendszerek megoldása ismétlődő képletek készítésével

A megoldáshoz az ismétlődő képletek összeállításának módszerét alkalmazzuk összetett rendszerek, amelyben a halmazok számának növelésének sorrendje nem egyértelmű, a fa építése pedig a térfogat miatt lehetetlen.

5. példa.

Az x1, x2, ... x7, y1, y2, ... y7 logikai változóknak hány különböző értékkészlete van, amelyek megfelelnek az alább felsorolt feltételeknek?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

A válasznak nem kell felsorolnia az x1, x2, ..., x7, y1, y2, ..., y7 változók összes különböző értékkészletét, amelyekre ez az egyenlőségrendszer teljesül. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás:

Vegye figyelembe, hogy a rendszer első hat egyenlete azonos, és csak a változók halmazában térnek el egymástól. Nézzük az első egyenletet. Megoldása a következő változók lesznek:

Jelöljük:

sorok száma (0,0) a változókon (x1,y1) A 1-ig,

sorok száma (0,1) a változókon (x1,y1) B 1-ig,

sorok száma (1,0) az (x1,y1) és C 1 változókon,

a sorok száma (1,1) az (x1,y1) és D 1 változókon.

sorok száma (0,0) az (x2,y2) és A 2 változókon,

sorok száma (0,1) a változókon (x2,y2) B 2-ig,

sorok száma (1,0) a változókon (x2,y2) C 2-ig,

a sorok száma (1,1) az (x2,y2) és D 2 változókon.

A döntési fából ezt látjuk

A1=0, B1=1, C1=1, D1=1.

Figyeljük meg, hogy az (x2,y2) változókra vonatkozó (0,0) halmazt az (x1,y1) változók (0,1), (1,0) és (1,1) halmazaiból kapjuk. Azok. A 2 =B 1 + C 1 + D 1.

Az (x2,y2) változókra vonatkozó (0,1) halmazt az (x1,y1) változók (0,1), (1,0) és (1,1) halmazaiból kapjuk. Azok. B 2 =B 1 +C 1 +D 1.

Hasonlóan érvelve megjegyezzük, hogy C 2 =B 1 +C 1 +D 1. D2 = D1.

Így ismétlődő képleteket kapunk:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Csináljunk egy asztalt

Készletek	Kijelölés.	Képlet	A készletek száma
Készletek	Kijelölés.	Képlet	i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Az utolsó egyenlet (x7 ∨ y7) = 1 minden halmazra teljesül, kivéve azokat, amelyekben x7=0 és y7=0. A táblázatunkban az ilyen halmazok száma A 7.

Majd teljes mennyiség halmaz egyenlő: B 7 + C 7 + D 7 = 127+127+1 = 255

Válasz: 255

Néhány feladat megoldása az informatika vizsga A és B részében

3. lecke. Logikák. Logikai függvények. Egyenletek megoldása

Nagy mennyiségben Egységes államvizsga problémák a propozíciós logikának szentelt. Legtöbbjük megoldásához elegendő a propozicionális logika alaptörvényeinek ismerete, az egy és két változó logikai függvényeinek igazságtáblázatainak ismerete. Leírom a propozíciós logika alaptörvényeit.

A diszjunkció és a konjunkció kommutativitása:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Diszjunkcióra és konjunkcióra vonatkozó elosztási törvény:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Tagadás tagadása:
¬(¬a) ≡ a
Következetesség:
a ^ ¬а ≡ hamis
Exkluzív harmadik:
a ˅ ¬а ≡ igaz
De Morgan törvényei:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Egyszerűsítés:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ igaz ≡ a
a ˄ hamis ≡ hamis
Abszorpció:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
Az implikáció cseréje
a → b ≡ ¬a ˅ b
Az identitás cseréje
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Logikai függvények ábrázolása

Bármely n változóból álló logikai függvény - F(x 1, x 2, ... x n) - megadható igazságtáblázattal. Egy ilyen táblázat 2n változóhalmazt tartalmaz, amelyek mindegyikéhez meg van adva egy függvény értéke ezen a halmazon. Ez a módszer akkor jó, ha a változók száma viszonylag kicsi. Már n > 5 esetén az ábrázolás rosszul láthatóvá válik.

Egy másik lehetőség, hogy a függvényt valamilyen képlettel határozzuk meg, kellőképpen ismert felhasználásával egyszerű funkciók. Egy függvényrendszert (f 1, f 2, ... f k) teljesnek nevezünk, ha bármely logikai függvény kifejezhető olyan képlettel, amely csak f i függvényeket tartalmaz.

A függvényrendszer (¬, ˄, ˅) elkészült. A 9. és 10. törvény példák annak bemutatására, hogy az implikáció és az azonosság hogyan fejeződik ki tagadáson, konjunkción és diszjunkción keresztül.

Valójában egy két függvény – a tagadás és a konjunkció vagy a tagadás és a diszjunkció – rendszere is teljes. De Morgan törvényeiből olyan elképzelések következnek, amelyek lehetővé teszik a konjunkció kifejezését tagadással és diszjunkcióval, és ennek megfelelően a disjunkciót tagadással és konjunkcióval:

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

Paradox módon az egyetlen funkcióból álló rendszer teljes. Két bináris függvény létezik - az antikonjunkció és az antidisjunkció, amelyeket Peirce-nyílnak és Schaeffer-vonásnak neveznek, és egy üreges rendszert képviselnek.

A programozási nyelvek alapvető funkciói általában az identitás, a negáció, a konjunkció és a diszjunkció. Az egyesített államvizsga-problémákban ezekkel a funkciókkal együtt gyakran találkozunk implikációkkal.

Nézzünk meg néhányat egyszerű feladatokat logikai függvényekkel kapcsolatos.

15. probléma:

Megadjuk az igazságtáblázat egy töredékét. A három megadott függvény közül melyik felel meg ennek a töredéknek?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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

3. számú funkció.

A probléma megoldásához ismernie kell az alapvető függvények igazságtáblázatait, és emlékeznie kell a műveletek prioritásaira. Hadd emlékeztesselek arra, hogy a kötőszónak (logikai szorzásnak) több is van magas prioritásúés a diszjunkció (logikai összeadás) előtt végrehajtódik. A számítások során könnyen észrevehető, hogy a harmadik halmaz 1-es és 2-es számú függvényei 1-esek, ezért nem felelnek meg a töredéknek.

16. probléma:

A megadott számok közül melyik felel meg a feltételnek:

(a számjegyek, a legjelentősebb számjegytől kezdve, csökkenő sorrendben vannak) → (szám - páros) ˄ (alacsony számjegy - páros) ˄ (magas számjegy - páratlan)

Ha több ilyen szám van, jelölje meg a legnagyobbat.

13579
97531
24678
15386

A feltételt a 4-es szám teljesíti.

Az első két szám nem felel meg a feltételnek, mert a legalacsonyabb számjegy páratlan. A feltételek kötőszava hamis, ha a kötőszó egyik tagja hamis. A harmadik szám esetében a legmagasabb számjegyre vonatkozó feltétel nem teljesül. A negyedik számra a kiskorúval szemben támasztott feltételeket ill legmagasabb számjegy számok. A kötőszó első tagja is igaz, hiszen az implikáció akkor igaz, ha a premisszája hamis, ami ebben az esetben igaz.

17. probléma: Két tanú a következő vallomást tette:

Első tanú: Ha A bűnös, akkor B még bűnösebb, C pedig ártatlan.

Második tanú: Ketten bűnösek. És a maradékok közül az egyik határozottan bűnös és bűnös, de nem tudom megmondani, hogy pontosan ki.

Milyen következtetéseket lehet levonni A, B és C bűnösségére vonatkozóan a tanúvallomásból?

Válasz: A tanúvallomásból az következik, hogy A és B bűnös, C pedig ártatlan.

Megoldás: Természetesen a válasz megadható az alapján józan ész. De nézzük meg, hogyan lehet ezt szigorúan és formálisan megtenni.

Az első dolog az állítások formalizálása. Vezessünk be három logikai változót – A, B és C, amelyek mindegyikének igaz (1) az értéke, ha a megfelelő gyanúsított bűnös. Ekkor az első tanú vallomását a következő képlet adja meg:

A → (B ˄ ¬C)

A második tanú vallomását a következő képlet adja meg:

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

Mindkét tanú vallomását igaznak tekintjük, és a megfelelő formulák kötődését jelenti.

Készítsünk igazságtáblázatot ezekhez az olvasmányokhoz:

A	B	C	F 1	F 2	F 1˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Az összefoglaló bizonyíték csak egy esetben igaz, ami egyértelmű válaszhoz vezet - A és B bűnös, C pedig ártatlan.

A táblázat elemzéséből az is következik, hogy a második tanú vallomása informatívabb. Csak két dolog következik tanúságtételének igazságából: lehetséges opciók- A és B bűnös, és C ártatlan, vagy A és C bűnös, és B ártatlan. Az első tanú vallomása kevésbé informatív – 5 van különféle lehetőségeket, amely megfelel a vallomásának. A két tanú vallomása együttesen egyértelmű választ ad a gyanúsítottak bűnösségére.

Logikai egyenletek és egyenletrendszerek

Legyen F(x 1, x 2, …x n) n változó logikai függvénye. A logikai egyenlet így néz ki:

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

A C állandó értéke 1 vagy 0.

Egy logikai egyenletnek 0-2 n különböző megoldása lehet. Ha C egyenlő 1-gyel, akkor a megoldások mindazok az igazságtáblázatbeli változók, amelyekre az F függvény igaz (1) értéket vesz fel. A fennmaradó halmazok a C egyenlet megoldásai, egyenlő nullával. Mindig csak a következő alakú egyenleteket veheti figyelembe:

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

Valóban, legyen adott az egyenlet:

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

Ebben az esetben az ekvivalens egyenlethez juthatunk:

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

Tekintsünk egy k logikai egyenletrendszert:

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

A rendszer megoldása olyan változók halmaza, amelyeken a rendszer összes egyenlete teljesül. Ami a logikai függvényeket illeti, a logikai egyenletrendszer megoldásához keresni kell egy halmazt, amelyre igaz a kötőszót reprezentáló Ф logikai függvény. eredeti funkciók F:

Ф = F 1 ˄ F 2 ˄ … F k

Ha a változók száma kicsi, például kevesebb, mint 5, akkor nem nehéz az Ф függvényre igazságtáblázatot készíteni, amely lehetővé teszi, hogy megmondjuk, hány megoldása van a rendszernek, és melyek azok a halmazok, amelyek megoldást adnak.

Egyes USE-problémákban, amelyek egy logikai egyenletrendszer megoldására keresnek megoldást, a változók száma eléri a 10-et. Ekkor az igazságtábla összeállítása szinte lehetetlen feladattá válik. A probléma megoldása más megközelítést igényel. Mert tetszőleges rendszer nincsenek egyenletek általános módszer, eltér a nyers erőtől, amely lehetővé teszi az ilyen problémák megoldását.

A vizsgán javasolt feladatoknál a megoldás általában az egyenletrendszer sajátosságainak figyelembevételén alapul. Ismétlem, azon kívül, hogy egy változókészlet összes opcióját kipróbáljuk, nincs általános módja a probléma megoldásának. A megoldást a rendszer sajátosságai alapján kell felépíteni. Gyakran hasznos egy egyenletrendszer előzetes egyszerűsítését végrehajtani az ismert logikai törvények segítségével. Másik hasznos trükk A probléma megoldása a következő. Nem minden halmaz érdekel, hanem csak azok, amelyeken a Φ függvény értéke 1. Konstrukció helyett tele asztal igaz, meg fogjuk építeni analógját - egy bináris döntési fát. Ennek a fának minden ága egy megoldásnak felel meg, és meghatároz egy halmazt, amelyen a Ф függvény értéke 1. A döntési fában lévő ágak száma egybeesik az egyenletrendszer megoldásainak számával.

Több probléma példáján keresztül elmagyarázom, mi az a bináris döntési fa, és hogyan épül fel.

18. probléma

Hány különböző értékhalmaza van az x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változóknak, amelyek kielégítik a két egyenletrendszert?

Válasz: A rendszernek 36 különböző megoldása van.

Megoldás: Az egyenletrendszer két egyenletet tartalmaz. Keressük a számot megoldások az első egyenlethez, 5 változótól függően – x 1, x 2, …x 5. Az első egyenlet pedig 5 egyenletrendszernek tekinthető. Mint látható, az egyenletrendszer valójában a logikai függvények konjunkcióját reprezentálja. Ennek fordítva is igaz: a feltétel konjunkciója egyenletrendszernek tekinthető.

Építsünk döntési fát az (x1→ x2) implikációra - a kötőszó első tagjára, amely az első egyenletnek tekinthető. Így néz ki grafikus kép ez a fa:

A fa szám szerint két szintből áll egyenletváltozók. Az első szint az első X 1 változót írja le. Ennek a szintnek két ága tükrözi ennek a változónak a lehetséges értékeit - 1 és 0. A második szinten a fa ágai csak az X 2 változó lehetséges értékeit tükrözik, amelyekre az egyenlet igaz. Mivel az egyenlet implikációt ad meg, egy olyan elágazáshoz, amelyen X 1 értéke 1, megköveteli, hogy azon az ágon X 2 értéke 1 legyen. Az az ág, amelyen X 1 értéke 0, két ágat hoz létre X 2 értékkel. egyenlő 0 és 1 A megszerkesztett fa három megoldást definiál, amelyekre az X 1 → X 2 implikáció 1 értéket vesz fel. Minden ágon kiírunk egy megfelelő változóérték-készletet, amely megoldást ad az egyenletre.

Ezek a készletek: ((1, 1), (0, 1), (0, 0))

Folytassuk a döntési fa felépítését a következő egyenlet hozzáadásával, a következő implikáció X 2 → X 3 . Egyenletrendszerünk sajátossága, hogy a rendszer minden új egyenlete egy változót használ az előző egyenletből, hozzáadva egy új változót. Mivel az X 2 változónak már vannak értékei a fában, ezért minden olyan ágon, ahol az X 2 változó értéke 1, az X 3 változó is 1-es lesz. Az ilyen ágaknál a fa felépítése továbblép a következő szintre, de új ágak nem jelennek meg. Az egyetlen ág, ahol az X 2 változó értéke 0, két ágra ágazik, ahol az X 3 változó a 0 és 1 értékeket kapja. Így egy új egyenlet minden egyes hozzáadása, annak sajátosságai miatt, egy megoldást ad hozzá. Eredeti első egyenlet:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
6 megoldása van. Így néz ki teli fa megoldások erre az egyenletre:

Rendszerünk második egyenlete hasonló az elsőhöz:

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

Az egyetlen különbség az, hogy az egyenlet Y változókat használ. Ennek az egyenletnek is van 6 megoldása. Mivel az X i változók minden megoldása kombinálható az Y j változók minden megoldásával, akkor teljes szám 36 megoldás létezik.

Kérjük, vegye figyelembe, hogy a felépített döntési fa nemcsak a megoldások számát adja meg (az ágak számával), hanem magát a fa egyes ágaira írt megoldásokat is.

19. probléma

Hány különböző értékkészlete van az x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változóknak, amelyek megfelelnek az alább felsorolt feltételeknek?

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

Ez a feladat az előző feladat módosítása. A különbség az, hogy hozzáadunk egy másik egyenletet, amely az X és Y változókat kapcsolja össze.

Az X 1 → Y 1 egyenletből az következik, hogy ha X 1 értéke 1 (egy ilyen megoldás létezik), akkor Y 1 is 1. Így van egy halmaz, amelyen X 1 és Y 1 értékei 1. Ha X 1 egyenlő 0-val, Y 1-nek tetszőleges értéke lehet, mind 0, mind 1. Ezért minden halmaz, ahol X 1 egyenlő 0-val, és 5 ilyen halmaz van, megfelel mind a 6 Y változós halmaznak. Ezért a megoldások száma összesen 31.

20. probléma

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

Megoldás: Emlékezve az alapvető ekvivalenciákra, az egyenletünket a következőképpen írjuk fel:

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

A ciklikus implikációs lánc azt jelenti, hogy a változók azonosak, így az egyenletünk ekvivalens a következő egyenlettel:

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

Ennek az egyenletnek két megoldása van, ha minden X i 1 vagy 0.

21. probléma

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

Megoldás: Csakúgy, mint a 20. feladatnál, a ciklikus implikációkról az azonosságokra térünk át, átírva az egyenletet a következő alakba:

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

Építsünk döntési fát ehhez az egyenlethez:

22. probléma

Hány megoldást tesz következő rendszer egyenletek?

((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

Válasz: 64

Megoldás: Térjünk át 10 változóról 5 változóra a következő változóváltás bevezetésével:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Ekkor az első egyenlet a következő alakot veszi fel:

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

Az egyenlet leegyszerűsíthető a következőképpen írva:

(Y 1 ≡ Y 2) = 0

Továbblépve a hagyományos forma, a rendszert egyszerűsítések után a következő formában írjuk:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Ennek a rendszernek a döntési fája egyszerű, és két ágból áll, változó értékekkel:

Visszatérve az eredeti X változóhoz, vegye figyelembe, hogy az Y változó minden értékéhez 2 érték tartozik az X változókban, tehát az Y változókban minden megoldás 25 megoldást generál az X változókban. A két ág 2 * 2-t generál 5 megoldás, így a megoldások száma összesen 64.

Amint láthatja, egy egyenletrendszer megoldásának minden problémája saját megközelítést igényel. Általános recepció a végrehajtás ekvivalens transzformációk hogy egyszerűsítsük az egyenleteket. Elterjedt technika a döntési fák létrehozása. Az alkalmazott megközelítés részben egy igazságtáblázat felépítésére emlékeztet, azzal a sajátossággal, hogy a változók lehetséges értékeinek nem minden halmaza épül fel, hanem csak azok, amelyeken a függvény 1 (igaz) értéket vesz fel. A javasolt problémákban gyakran nincs szükség teljes döntési fa felépítésére, hiszen már kezdeti szakaszban mindegyiken kialakítható az új ágak megjelenési mintája következő szintre, ahogy ez például a 18. feladatnál történt.

Általánosságban elmondható, hogy a logikai egyenletrendszerek megoldásával kapcsolatos problémák jó matematikai gyakorlatok.

Ha a probléma manuálisan nehezen megoldható, akkor a megoldást a számítógépre bízhatja egyenletek és egyenletrendszerek megoldására alkalmas program megírásával.

Nem nehéz ilyen programot írni. Egy ilyen program könnyen megbirkózik az egységes állami vizsgán kínált összes feladattal.

Furcsa módon a logikai egyenletrendszerekre megoldást találni nehéz feladat a számítógép számára, és kiderül, hogy a számítógépnek megvannak a határai. A számítógép meglehetősen könnyen megbirkózik azokkal a feladatokkal, ahol a változók száma 20-30, de hosszú ideig elkezd gondolkodni a problémákon nagyobb méretű. A helyzet az, hogy a 2 n függvény, amely a halmazok számát adja meg, egy exponenciális, amely gyorsan növekszik n növekedésével. Olyan gyorsan, hogy egy átlagos személyi számítógép nem tud megbirkózni egy olyan feladattal, amely 40 változót tartalmaz egy nap.

C# nyelvű program logikai egyenletek megoldására

A logikai egyenletek megoldására szolgáló program megírása több okból is hasznos, már csak azért is, mert segítségével ellenőrizheti az egységes államvizsga tesztfeladatainak saját megoldásának helyességét. Egy másik ok, hogy egy ilyen program kiváló példája az egységes államvizsga C kategóriás feladatok követelményeinek megfelelő programozási feladatnak.

A program felépítésének ötlete egyszerű - az összes lehetséges változóérték-készlet teljes keresésén alapul. Mivel egy adott logikai egyenlethez vagy egyenletrendszerhez ismert az n változók száma, így a halmazok száma is ismert - 2 n, amelyeket le kell rendezni. A C# nyelv alapfunkcióit - tagadás, diszjunkció, konjunkció és azonosság - felhasználva nem nehéz olyan programot írni, amely adott változóhalmazra kiszámítja a logikai egyenletnek vagy egyenletrendszernek megfelelő logikai függvény értékét. .

Egy ilyen programban fel kell építeni egy ciklust a halmazok száma alapján, magát a halmazt képezni kell a ciklus törzsében a halmaz száma alapján, ki kell számítani a függvény értékét ezen a halmazon, és ha ez az érték 1, akkor a halmaz megoldást ad az egyenletre.

Az egyetlen nehézség, amely a program végrehajtása során felmerül, azzal a feladattal kapcsolatos, hogy a beállított szám alapján a változóértékek halmazát állítsák elő. A probléma szépsége az, hogy úgy tűnik nehéz feladat, valójában egy egyszerű, már többször felmerült problémára vezethető vissza. Valóban, elég ezt megérteni számnak megfelelő i, nullákból és egyesekből álló változóértékek halmaza, az i szám bináris reprezentációja. Így nehéz feladat a változóértékek halmazának megszerzése meghatározott számokkal a szám bináris rendszerré alakításának jól ismert problémájához vezet.

Így néz ki egy függvény a C#-ban, amely megoldja a problémánkat:

///

/// program a megoldások számának számlálására

/// logikai egyenlet (egyenletrendszer)

///

/// logikai függvény - módszer,

/// amelynek aláírását a DF delegáltja megadja

///

/// változók száma

/// megoldások száma

statikus int SolveEquations(DF fun, int n)

bool halmaz = új bool[n];

int m = (int)Math.Pow(2, n); //halmazok száma

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

//A keresés befejezése készletek száma szerint

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

//A következő halmaz kialakulása - halmaz,

//meghatározott bináris reprezentáció számok i

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

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

//A függvény értékének kiszámítása a halmazon

A program megértéséhez remélem, a program ötletének magyarázata és a szövegében található megjegyzések elegendőek. Csak az adott függvény címének magyarázatára koncentrálok. A SolveEquations függvénynek két bemeneti paramétere van. A fun paraméter a megoldandó egyenletnek vagy egyenletrendszernek megfelelő logikai függvényt határoz meg. Az n paraméter a számot adja meg függvényváltozók szórakoztató. Ennek eredményeként a SolveEquations függvény a logikai függvény megoldásainak számát adja vissza, vagyis azoknak a halmazoknak a számát, amelyeken a függvény igazra értékel.

Iskolásoknál gyakori, hogy valamelyik F(x) függvénynek van egy x bemeneti paramétere, amely egy aritmetika, karakterlánc vagy logikai típusú. Esetünkben erősebb kialakítást alkalmazunk. A SolveEquations függvény a függvényekhez tartozik magasabb rendű– F(f) típusú függvények, amelyek paraméterei nemcsak egyszerű változók, hanem függvények is lehetnek.

A SolveEquations függvénynek paraméterként átadható függvények osztálya a következőképpen van megadva:

delegate bool DF(bool vars);

Ez az osztály birtokolja az összes függvényt, amelyet paraméterként adnak át a vars tömb által megadott logikai változók értékeinek halmazaként. Az eredmény egy logikai érték, amely a függvény értékét képviseli ebben a halmazban.

Végül itt van egy program, amely a SolveEquations függvényt használja több logikai egyenletrendszer megoldására. A SolveEquations függvény az alábbi ProgramCommon osztály része:

osztályú ProgramCommon

delegate bool DF(bool vars);

static void Main (string args)

Console.WriteLine("És függvények - " +

Oldja meg az egyenleteket (FunAnd, 2));

Console.WriteLine("A függvénynek 51 megoldása van - " +

Oldja meg az egyenleteket (Fun51, 5));

Console.WriteLine("A függvénynek 53 megoldása van - " +

Oldja meg az egyenleteket (Fun53, 10));

statikus bool FunAnd(bool vars)

return vars && vars;

statikus bool Fun51 (bool vars)

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

statikus bool Fun53 (bool vars)

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

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

Így néznek ki a program megoldási eredményei:

10 feladat önálló munkához

A három függvény közül melyik ekvivalens:
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
Adott egy részlet az igazságtáblázatból:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

A három funkció közül melyiknek felel meg ez a töredék:

(X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
A zsűri három főből áll. A döntés akkor születik, ha a zsűri elnöke megszavazza, és legalább egy zsűritag támogatja. Ellenkező esetben nem születik döntés. Készítsen egy logikai függvényt, amely formalizálja a döntéshozatali folyamatot.
X nyer Y felett, ha négy érmefeldobás háromszor fejet eredményez. Határozzon meg egy logikai függvényt, amely leírja X kifizetését.
A mondatban lévő szavak egytől kezdődően vannak számozva. Egy mondat akkor tekinthető helyesen megszerkesztettnek, ha a következő szabályok teljesülnek:
1. Ha egy páros számú szó magánhangzóval végződik, akkor következő szó, ha létezik, magánhangzóval kell kezdődnie.
2. Ha egy páratlan számú szó mássalhangzóval végződik, akkor a következő szónak, ha létezik, mássalhangzóval kell kezdődnie, és magánhangzóval kell végződnie.
  Melyik a következő javaslatokat helyesen felépített:
3. Anya szappannal megmosta Mashát.
4. A vezető mindig modell.
5. Az igazság jó, de a boldogság jobb.
Hány megoldása van az egyenletnek:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Sorolja fel az egyenlet összes megoldását:
(a → b) → c = 0
Hány megoldása van a következő egyenletrendszernek:
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
Hány megoldása van az egyenletnek:
(((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Válaszok a problémákra:

A b és c függvények egyenértékűek.
A töredék a b függvénynek felel meg.
Legyen a P logikai változó 1 értéke, amikor a zsűri elnöke megszavazza a döntést. Az M 1 és M 2 változók a zsűritagok véleményét képviselik. Az elfogadást meghatározó logikai függvény pozitív döntésígy írható:
P ˄ (M 1 ˅ M 2)
Legyen a P i logikai változó 1 értéke, amikor at i-edik dobásérmék jönnek elő. Az X kifizetést meghatározó logikai függvény a következőképpen írható fel:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
b mondat.
Az egyenletnek 3 megoldása van: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Logikai egyenletrendszerek megoldási módszerei

Megoldhat egy logikai egyenletrendszert, például igazságtáblázat segítségével (ha a változók száma nem túl nagy) vagy döntési fa használatával, először minden egyenletet egyszerűsítve.

1. Változó helyettesítési módszer.

Az új változók bevezetése lehetővé teszi az egyenletrendszer egyszerűsítését, csökkentve az ismeretlenek számát.Az új változóknak függetleneknek kell lenniük egymástól. Az egyszerűsített rendszer megoldása után vissza kell térnünk az eredeti változókhoz.

Tekintsük ennek a módszernek az alkalmazását egy konkrét példán keresztül.

Példa.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Megoldás:

Vezessünk be új változókat: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Figyelem! Az x1, x2, ..., x10 változók mindegyikét csak egy új változónak kell tartalmaznia A, B, C, D, E változók, azaz az új változók függetlenek egymástól).

Ekkor az egyenletrendszer így fog kinézni:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Építsünk döntési fát az eredményül kapott rendszerhez:

Tekintsük az A=0 egyenletet, azaz. (X1≡ X2)=0. 2 gyökere van:

		X1 ≡ X2

Ugyanebből a táblázatból látható, hogy az A=1 egyenletnek is 2 gyöke van. Rendezzük el a gyökerek számát a döntési fán:

Egy ág megoldásainak számának meghatározásához minden szinten meg kell szorozni a megoldások számát. A bal ágnak 2 van⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 oldat; a jobb oldali ágnak is 32 megoldása van. Azok. az egész rendszernek 32+32=64 megoldása van.

Válasz: 64.

2. Az érvelés módja.

A logikai egyenletrendszerek megoldásának nehézsége a teljes döntési fa nehézkességében rejlik. Az érvelési módszer lehetővé teszi, hogy ne építse fel a teljes fát, hanem megértse, hány ága lesz. Nézzük meg ezt a módszert konkrét példák segítségével.

1. példa Hány különböző értékkészlete van az x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változóknak, amelyek megfelelnek az alább felsorolt feltételeknek?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

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

x1\/y1 =1

A válasznak nem kell felsorolnia az x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 változók összes különböző értékkészletét, amelyekre ez az egyenlőségrendszer teljesül. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás:

Az első és a második egyenlet független változókat tartalmaz, amelyeket a harmadik feltétel kapcsol össze. Építsünk megoldásfát az első és a második egyenlethez.

Ahhoz, hogy az első és a második egyenletrendszer megoldásfáját ábrázoljuk, az első fa minden ágát a változókhoz tartozó fával kell folytatni. at . Az így felépített fa 36 ágat fog tartalmazni. Ezen ágak némelyike nem felel meg a rendszer harmadik egyenletének. Az első fán jelöljük meg a fa ágainak számát"y" , amelyek kielégítik a harmadik egyenletet:

Magyarázzuk el: a harmadik feltétel teljesüléséhez, amikor x1 = 0, y1 = 1-nek kell lennie, azaz a fa összes ágának."X" , ahol x1=0 csak egy ággal folytatható a fából"y" . És csak a fa egyik ágára"X" (jobbra) a fa összes ága elfér"y". Így a teljes rendszer teljes fája 11 ágat tartalmaz. Mindegyik ág az eredeti egyenletrendszer egy-egy megoldását jelenti. Ez azt jelenti, hogy a teljes rendszernek 11 megoldása van.

Válasz: 11.

2. példa Hány különböző megoldása van az egyenletrendszernek?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) = 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10) = 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10) = 1

(X1 ≡ X10) = 0

ahol x1, x2, …, x10 logikai változók? A válasznak nem kell felsorolnia az összes különböző változóérték-készletet, amelyre ez az egyenlőség vonatkozik. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás: Egyszerűsítsük a rendszert. Készítsünk igazságtáblázatot az első egyenlet egy részére:

X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

Ügyeljen az utolsó oszlopra, az megegyezik a művelet eredményével X1 ≡ X10.

X1 ≡ X10

Egyszerűsítés után a következőket kapjuk:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Tekintsük az utolsó egyenletet:(X1 ≡ X10) = 0, azaz. x1 nem eshet egybe x10-el. Ahhoz, hogy az első egyenlet egyenlő legyen 1-gyel, az egyenlőségnek igaznak kell lennie(X1 ≡ X2)=1, azaz. x1-nek egyeznie kell x2-vel.

Építsünk megoldásfát az első egyenlethez:

Tekintsük a második egyenletet: x10=1 és x2=0 esetén a zárójelegyenlőnek kell lennie 1-gyel (azaz x2 egybeesik x3-mal); x10=0 és x2=1 zárójel esetén(X2 ≡ X10)=0, ami a zárójelet jelenti (X2 ≡ X3) egyenlőnek kell lennie 1-gyel (azaz x2 ugyanaz, mint x3):

Ily módon érvelve létrehozunk egy döntési fát az összes egyenlethez:

Így az egyenletrendszernek csak 2 megoldása van.

Válasz: 2.

3. példa

Hány különböző értékkészlete van az x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 logikai változóknak, amelyek kielégítik az összes alább felsorolt feltételt?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Megoldás:

Építsünk megoldásfát az 1. egyenlethez:

Tekintsük a második egyenletet:

Amikor x1=0 : a második és harmadik zárójel 0 lesz; hogy az első zárójel egyenlő legyen 1-gyel, y1=1, z1=1 (azaz ebben az esetben - 1 megoldás)
Amikor x1=1 : az első zárójel 0 lesz; második vagy a harmadik zárójelnek 1-nek kell lennie; a második zárójel 1 lesz, ha y1=0 és z1=1; a harmadik zárójel 1 lesz, ha y1=1 és z1=0 (azaz ebben az esetben - 2 megoldás).

Hasonlóképpen a többi egyenlet esetében is. Jegyezzük fel az eredményül kapott megoldások számát az egyes facsomópontokhoz:

Az egyes ágakhoz tartozó megoldások számának megtudásához szorozza meg a kapott számokat minden ágra külön-külön (balról jobbra).

1 ág: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 megoldás

2. ág: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 megoldás

3. ág: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 megoldás

4. ág: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 megoldás

5. ág: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 megoldás

Adjuk össze a kapott számokat: összesen 31 megoldás van.

Válasz: 31.

3. A gyökerek számának természetes növekedése

Egyes rendszerekben a következő egyenlet gyökeinek száma az előző egyenlet gyökeinek számától függ.

1. példa Hány különböző értékkészlete van az x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 logikai változóknak, amelyek kielégítik az összes alább felsorolt feltételt?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Egyszerűsítsünk első egyenlet:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Ezután a rendszer a következő formában jelenik meg:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Stb.

Minden következő egyenletnek 2-vel több gyöke van, mint az előzőnek.

4 egyenletnek 12 gyöke van;

Az 5. egyenletnek 14 gyöke van

A 8-as egyenletnek 20 gyöke van.

Válasz: 20 gyökér.

Néha a gyökerek száma a Fibonacci törvény szerint nő.

A logikai egyenletrendszer megoldása kreatív megközelítést igényel.

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete

A	IN	VEL					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

A	IN	VEL					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

A	IN	VEL					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1