A logikai egyenletek megoldásának módja. Logikai egyenletek megoldása a matematikai példákban a logikai egyenletek megoldásaira

A logikai egyenletek megoldása a változók cseréjével

A változó csere-módszert akkor alkalmazzák, ha bizonyos változók csak egy specifikus kifejezésként szerepelnek az egyenletekben, és semmilyen módon nem más módon. Ezután ez a kifejezés új változót lehet kijelölni.

1. példa.

Hány különböző értékű logikai változók X1, X2, X3, X4, X5, X6, X7, X8, akik megfelelnek az alábbiakban felsorolt \u200b\u200bösszes feltételnek?

(x1 → x2) → (x3 → x4) \u003d 1

(x3 → x4) → (x5 → x6) \u003d 1

(x5 → x6) → (x7 → x8) \u003d 1

Válaszul, nem kell felsorolni az X1, X2, X3, X4, X5, X6, X7, X8 változók összes különböző értékét, amely alatt ezt az egyenlőtlenségi rendszert elvégzik. Válaszként meg kell adnia az ilyen készletek számát.

Döntés:

(x1 → x2) \u003d y1; (x3 → x4) \u003d y2; (x5 → x6) \u003d y3; (x7 → x8) \u003d Y4.

Ezután írhatja a rendszert egy egyenlet formájában:

(Y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) \u003d 1. A konjunkció 1 (igaz), ha minden operand elfogadja az értéket 1. Azok. Mindegyik következménynek igaznak kell lennie, és ezt minden értéken végezzük, kivéve (1 → 0). Azok. Az Y1, Y2, Y3, Y4 változók értékeiben a készülék nem állhat a nulla bal oldali bal oldalán:

Azok. A feltételeket 5 y1-y4 készlet esetén végezzük.

Mivel Y1 \u003d X1 → X2, akkor az Y1 \u003d 0 érték egy X1, X2: (1, 0) szetten érhető el, és az Y1 \u003d 1 értéket három X1, X2: (0,0) , 1), (1,1). Hasonló y2, y3, y4.

Mivel az Y1 változó mindegyik beállítása (X1, X2) egyesítettük (X3, X4) egy Y2 változóhoz stb., Az X változók számának száma megszorozódik:

				A készletek száma az x1 ... x8-on

A készletek száma: 1 + 3 + 9 + 27 + 81 \u003d 121.

Válasz: 121

2. példa.

Hány különböző logikai változók X1, X2, X9, Y1, Y2, ... Y9, amelyek megfelelnek az alábbiakban felsorolt \u200b\u200bösszes feltételnek?

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

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

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

Válaszul nem szükségessorolja fel az x1, x2, ... x9, y1, y2, ... y9 változók összes különböző értékét, amely alatt ez az egyenlőtlenségi rendszer készül. Válaszként meg kell adnia az ilyen készletek számát.

Döntés:

Cseréljük ki a változókat:

(x1 ≡ y1) \u003d z1, (x2 ≡ y2) \u003d Z2, .... , (x9 ≡ y9) \u003d z9

A rendszer egyetlen egyenletként írható:

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

Az egyenértékűség csak akkor igaz, ha mindkét operand egyenlő. Az egyenlet döntései két készlet lesz:

z1.	z2.	z3	z 4.	z5.	z6.	z7	z8.	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Mivel Zi \u003d (xi ≡ yi), akkor a Zi \u003d 0 érték megfelel két készletnek (XI, YI): (0,1) és (1,0), és a Zi \u003d 1 érték két készlet (XI, YI): (0 0 ) és (1,1).

Ezután az első Z1, Z2, ..., Z9 2 9 készlet (X1, Y1), (X2, Y2), ..., (X9, Y9).

Ugyanez az összeg megfelel a második Z1, Z2, ..., Z9. Ezután csak 2 9 +2 9 \u003d 1024 készlet.

Válasz:1024

A logikai egyenletek megoldása a rekurzió vizuális meghatározásának módszerével.

Ezt a módszert akkor alkalmazzák, ha az egyenletek rendszere meglehetősen egyszerű, és a változók hozzáadásakor a készletek számának növelése nyilvánvaló.

3. példa.

Hány különböző megoldás van egy egyenletrendszerrel

¬x9 ∨ x10 \u003d 1,

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

Válaszul, nem kell felsorolni az X1, X2, ... X10 összes értékét, amelyen az egyenlőtlenségi rendszer készül. Válaszként meg kell adnia az ilyen készletek számát.

Döntés:

Hajtsa végre az első egyenletet. A dysiaction 1, ha legalább az egyik operandusa 1. Azok. A döntések a készletek:

Az x1 \u003d 0 esetében két x2 (0 és 1) érték van, és x1 \u003d 1, csak egy x2 (1) érték, így a készlet (X1, X2) az egyenlet oldata. Összesen 3 készlet.

Adjon hozzá egy X3 változót, és vegye figyelembe a második egyenletet. Az elsőhöz hasonló, ez az x2 \u003d 0 esetében két x3 érték (0 és 1), az x2 \u003d 1 esetében csak egy x3 (1) értéke van, így a készlet (X2, X3) az egyenlet megoldása. Összesen 4 készlet.

Könnyű észrevenni, hogy egy másik változó hozzáadásakor egy készlet hozzáadódik. Azok. Rekurzív képlet az (i + 1) változók beállításainak számához:

N I +1 \u003d N I + 1. Ezután tíz változó esetében 11 készletet kapunk.

Válasz: 11

Különböző típusú logikai egyenletek megoldása

4. példa.

Hány különböző logikai változók x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, amelyek megfelelnek az alábbiakban felsorolt \u200b\u200bösszes feltételnek?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) \u003d 1

(Y 1 → Y 2) ∧ (y 2 → y 3) ∧ (Y 3 → y 4) \u003d 1

(Z 1 → Z 2) ∧ (Z 2 → Z 3) ∧ (Z 3 → Z 4) \u003d 1

x 4 ∧ y 4 ∧ z 4 \u003d 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 összes értékét, amely alatt ez az egyenlőtlenségi rendszer.

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

Döntés:

Ne feledje, hogy a rendszer három egyenlete ugyanaz a különböző független változókészleteken.

Fontolja meg az első egyenletet. A konjunkció csak akkor igaz (1) csak akkor, ha az összes operandusa igaz (1). Az implikáció 1 minden készleten, kivéve (1,0). Ez azt jelenti, hogy az első egyenlet megoldása olyan X1, X2, X3, X4 készletek lesz, amelyekben az 1 nem éri meg 0 (5 készlet):

Hasonlóképpen, a második és a harmadik egyenletek megoldásai teljesen ugyanazok a készletek Y1, ..., Y4 és Z1, ..., Z4.

Most elemezzük a rendszer negyedik egyenletét: x 4 ∧ Y 4 ∧ Z 4 \u003d 0. Az oldat mind az X4, Y4, Z4 készlet, amelyben a változók legalább egyike 0.

Azok. Az x4 \u003d 0 esetében minden lehetséges készlet (Y4, Z4) alkalmas, és az x4 \u003d 1, a készletek (Y4, Z4) alkalmasak, amelyekben legalább egy nulla jelen van: (0, 0), (0,1) ), (1, 0).

				A készletek száma

A 25 + 4 * 9 \u003d 25 + 36 \u003d 61 készletek teljes száma.

Válasz: 61

Logikai egyenletek rendszerének megoldása az ismétlődő képletek megépítésének módszerével

Az ismétlődő képletek megépítésének módját komplex rendszerek megoldására használják, amelyekben a készletek számának növelése nem nyilvánvaló, és a fák építése lehetetlen a mennyiségek miatt.

5. példa.

Hány különböző logikai változók x1, x2, ... x7, y1, y2, ... x7, y1, y2, ... y7, amelyek megfelelnek az alábbiakban felsorolt \u200b\u200bösszes feltételnek?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) \u003d 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) \u003d 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) \u003d 1

A válasz nem kell felsorolni az x1, x2, ..., x7, y1, y2, ..., x7, y1, y2, ..., y7 változók különböző értékeit, amelyek alatt Ez az egyenlőtlenségi rendszer történik. Válaszként meg kell adnia az ilyen készletek számát.

Döntés:

Ne feledje, hogy az első hat rendszeregyenlet ugyanaz, és csak a változókészletben különbözik. Fontolja meg az első egyenletet. A megoldás a következő változókészletek lesznek:

Jelöli:

a készletek száma (0,0) a változókon (x1, y1) egy 1,

a készletek száma (0,1) a változókon (X1, Y1) a B 1-en keresztül,

az (1,0) a változók (X1, Y1) a C 1-en keresztül,

a változók (1,1) a változókon (X1, Y1) d 1-en keresztül.

a készletek száma (0,0) a változókon (x2, y2) egy 2-es,

készletek száma (0,1) a változókon (X2, Y2) a B 2-en keresztül,

a SETS (1.0) a változókon (X2, Y2) a C 2-en keresztül,

a SETS (1.1) a változókon (X2, Y2) a D 2-en keresztül.

A fa megoldásokból ezt látják

A 1 \u003d 0, B 1 \u003d 1, C 1 \u003d 1, D 1 \u003d 1.

Ne feledje, hogy a változók (X2, Y2) beállítása (0,0) a változók (0,1), (1,0) és (1,1) a változókon (X1, Y1). Azok. A 2 \u003d B 1 + C 1 + D 1.

A változók (X2, Y2) beállítása (0,1) a (0,1), (1,0) és (1,1) a változókon (X1, Y1) beállításokból származik. Azok. B 2 \u003d B 1 + C 1 + D 1.

Hasonlóképpen, vitatkozunk, megjegyezzük, hogy 2 \u003d B 1 + C 1 + D 1 esetén. D 2 \u003d D 1.

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

A i + 1 \u003d b i + c i + d i

B i + 1 \u003d b i + c i + d i

C i + 1 \u003d b i + c i + d i

D I + 1 \u003d A I + B I + C I + D I

Asztalt készít

Készlet	Saját.	Képlet	A készletek száma
			i \u003d 1.	i \u003d 2.	i \u003d 3.	i \u003d 4.	i \u003d 5.	i \u003d 6.	i \u003d 7.
(0,0)	I.	A i + 1 \u003d b i + c i + d i	0	3	7	15	31	63	127
(0,1)	B I.	B i + 1 \u003d b i + c i + d i	1	3	7	15	31	63	127
(1,0)	C I.	C i + 1 \u003d b i + c i + d i	1	3	7	15	31	63	127
(1,1)	D I.	D i + 1 \u003d d i	1	1	1	1	1	1	1

Az utolsó egyenlet (x7 ∨ y7) \u003d 1 kielégíti az összes készletet, kivéve azokat, amelyekben X7 \u003d 0 és Y7 \u003d 0. Táblázatunk az ilyen készletek száma 7.

Ezután a készletek teljes száma B 7 + C 7 + D 7 \u003d 127 + 127 + 1 \u003d 255

Válasz: 255

Az 1. egyenlet megoldása 1. Transzfix az egyenlet rögzítésének előtag formájához, a megtagadási megjelölés helyettesítése ¬ 2.Pust az igazság táblázatának címét. 3. Az igazság táblázat sorának kitöltése mindenki számára A és B kombinációk, az X - 0 vagy 1. helyett helyettesítve az X \u003d F (A, B) 5. ábrát az Igazságtáblában, szükség esetén meg kell határozni az X funkció formáját, ha szükséges Az SCPF és az SDNF konstrukciójának módszerei, amelyeket az alábbiakban tárgyalunk.

Egy speciális forma ¬ (a + b) · (x a · b) \u003d ¬ (B + ¬ (x a))

Az X \u003d F (A, B) ABX igazolási táblázat megfelel a válaszban lévő implikáció megtagadásának:

Logikai készülékek kombinációs diagramjai Base Elements (GOST): 1 A diszjunkcionálás az egyenértékűségben és az M2 a Xor-ban

Kombinációs diagramok logikai eszközök alapelemek (GOST): 1 A implication & és a hedere elem és és az 1 egy tekercs a WebB-ben

F 1 & 1 & 1m2 b A séma

Az 1-es rendszerek megoldása Az áramkör átalakítása összetett logikai kifejezésre, majd egyszerűsíti azt a logikai törvények szerint. 2 Opció - Igazságasztal építése, majd szükség esetén az SKFF vagy az IDNF-en keresztül (lásd alább). Tekintsük a második lehetőséget egyszerűbbé és érthetővé.

Az igazság beépítése AB A + B + · B B · A + A B A + · · ·

Az F (A, B) ABX igazság táblázata megfelel a válaszadás megtagadásának:

Az elemi összefüggés SDNF és SCFF (definíciója) az elutasítással vagy tagadással vett számos változó összekapcsolása, és a változók között ugyanazok az elemi diszjunkció, amelyet a megtagadott vagy negatív vagy negatív változók diszjunkciójának neveznek Legyen ugyanaz az elemi konjunktumok hiánya. Hívunk egy diszjunktív normál formát (DNF) bármely elemi diszjunkciók konjunktív normál formájú (DNF)

A tökéletes diszjunktív normál forma (CDNF) SDNF és definíciója (definíciója) DNF-nek nevezhető, amelyben nincs azonos elemi konjunktusok, és az összes kötődés ugyanolyan változókészülékből áll, amelyekben minden változó csak egyszer lép be (esetleg megtagadva) . A tökéletes konjunktív normál formát (SCPF) a KNF-nek nevezik, amelyben nincs azonos elemi diszjunktionok, és az összes diszjunkció ugyanazon változókészülékből áll, amelyekben minden változó csak egyszer (esetleg tagadással) lép.

Algoritmus a CDNF megszerzéséhez az igazság táblázatban 1. Az utolsó oszlopban az utolsó oszlopban lévő összes igazságos asztali sorok 1. 2. Az egyes jelölt sorok írása Az összes változó összekapcsolása az alábbiak szerint: Ha a változó értéke ebben a sorban van 1, majd a konjunkcióban magában foglalja ezt a változót, ha ugyanúgy 0, akkor a megtagadása. 3. A kapott konjunktusok a diszjunkcióhoz kapcsolódnak. Algoritmus az Igazságban az 1. táblázatban. Az utolsó oszlopban az igazság táblázatának figyelembevétele. Az utolsó oszlopban az igazság táblázat sorai. 2. Nézze meg az egyes jelzett vonalat, hogy az összes változót az alábbiak szerint diszjunktusolja: Ha a változó értéke ebben a sorban van 0, majd a kapcsolat, hogy ezt a változót maga is, ha egyenlően 1, akkor a megtagadása. 3. Az összes kapott diszjunkció összefüggésben van.

Egy példa egy SKNF xy f (x, y) megtérítésére a nullák megjegyzésére. 2. Dissuniction: x + y 3. Communkció: (x + y) · (x + y)

A logikai egyenletrendszerek megoldásának különböző módjai megkülönböztethetők. Ez egy egyenletre csökken, igazságos táblát és bomlást.

Egy feladat:A logikai egyenletek rendszerének megoldása:

Fontolgat információs módszer egy egyenlethez . Ez a módszer magában foglalja a logikai egyenletek átalakulását, hogy a megfelelő részük egyenlő legyen a valóban értékkel (azaz 1). Ehhez egy logikai megtagadás működését használják. Ezután, ha összetett logikai műveletek vannak az egyenletekben, cserélje ki őket alapvető: "és", ",", "nem". A következő lépés az egyenleteket egy, egyenértékű rendszerbe ötvözi, logikai művelet alkalmazásával "és". Ezt követően a kapott egyenlet átalakítására kell átalakítani a logikai algebra törvényei alapján, és kap egy speciális rendszer megoldást.

1. megoldás:Az első egyenlet mindkét részére inverziót alkalmazunk:

Képzeld el az alapvető műveletek "vagy" nem ":

Mivel az egyenletek bal részei 1, kombinálhatják őket a művelet használatával "és" egy egyenletbe, a forrásrendszer egyenértékének:

Az első tartót a törvény de Morgan, és átalakítjuk az eredményt:

A kapott egyenletnek van egy megoldása: A \u003d 0, B \u003d 0 és C \u003d 1.

Következő út - az igazság táblázatok építése . Mivel csak két érték van logikai értékkel, egyszerűen átmegy az összes lehetőséggel, és megtalálhatja azokat, amelyeken az egyenletrendszert végezzük. Vagyis egy általános igazságtáblát építünk a rendszer valamennyi egyenletére, és találunk egy karakterláncot a kívánt értékekkel.

2. megoldás: A rendszer igazságát fogjuk tenni:

0	0	1	1	0	1

Az emelés kiemelve van, amelyre a probléma feltételeit elvégzik. Így a \u003d 0, b \u003d 0 és c \u003d 1.

Módszer bomlás . Az ötlet az, hogy rögzítse az egyik változó értékét (0 vagy 1) értéke, és ennek köszönhetően az egyenletek egyszerűsítése. Ezután javíthatja a második változó értékét stb.

3. megoldás:Legyen a \u003d 0, akkor:

Az első egyenletből B \u003d 0, és a második - C \u003d 1-ből kapunk. Megoldás Megoldás: A \u003d 0, B \u003d 0 és C \u003d 1.

Az EGE számítástechnika, nagyon gyakran kell határozni a megoldások száma a rendszer logikája egyenletek nélkül megtalálni a megoldásokat magukat, erre is vannak bizonyos módszerek. A logikai egyenletek rendszerének megoldásainak meghatározásának fő módja -a változók cseréje. Először is egyszerűsíteni kell az egyes egyenleteket a logikai algebra törvényei alapján, majd az egyenletek összetett részeit új változókkal helyettesíti, és meghatározza az új rendszer megoldásainak számát. Következő visszatérés a cserére és meghatározására a megoldások számát.

Egy feladat:Hány megoldás van egy (a → b) + (a b) + (c → d) \u003d 1? Ahol A, B, C, D logikai változók.

Döntés:Új változókat vezetünk be: X \u003d A → B és Y \u003d C → D. Figyelembe véve az új változókat, az egyenlet rögzül: x + y \u003d 1.

A diszjunkció három esetben igaz: (0; 1), (1; 0) és (1; 1), X és Y-vel olyan implikáció, vagyis három esetben és hamis. Ezért az ügy (0; 1) megfelel a paraméterek három lehetséges kombinációjának. Az ügy (1; 1) - megfelel a forrásegyenlet paramétereinek kilenc lehetséges kombinációjához. Tehát ezen egyenlet minden lehetséges megoldása 3 + 9 \u003d 15.

A logikai egyenletek rendszerének megoldásainak meghatározására szolgáló következő módszer - bináris fa. Tekintsük ezt a módszert a példában.

Egy feladat:Hány különböző megoldás van a logikai egyenletek rendszerével:

Az egyenletek csökkentett rendszere megegyezik az egyenletkel:

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

Tegyük fel, hogy ez x. 1 - igaz, majd az első egyenletből kapjuk ezt x. 2 Is valóban, a második - x. 3 \u003d 1, és így tovább x M. \u003d 1. Tehát állítsa (1, 1, ..., 1) az M egységekből a rendszer megoldása. Hadd most x. 1 \u003d 0, majd az első egyenletből x. 2 \u003d 0 vagy x. 2 =1.

Mikor x. 2 Valóban megkapjuk, hogy a fennmaradó változók is igazak, vagyis egy készlet (0, 1, ...; 1) a rendszer megoldása. -Ért x. 2 \u003d 0 Ezt kapjuk x. 3 \u003d 0 vagy x. 3 \u003d, és így tovább. Továbbra is az utolsó változó, beszerzünk, hogy az egyenlet megoldásai a következő változók (M +1 oldat, mindegyik oldatban M-értékekben M +1 oldatban):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ezt a megközelítést jól illusztrálják egy bináris fa építésével. A lehetséges megoldások száma az épített fa különböző ágai száma. Könnyű észrevenni, hogy M +1-vel egyenlő.

	Faipari	A megoldások száma
x 1
x 2
x 3.
		…

Az oka esetén nehézségek esetén és megépítvea REVA megoldások kereshetőkhasználat az igazság ízléseEgy-két egyenletre.

Átírom az egyenletek rendszerét az űrlapon:

És készítsen egy rendellenességet külön-külön egy egyenletre:

x 1	x 2	(x 1 → x 2)

Két egyenlethez rendeljünk egy igazságot:

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

Ez az anyag tartalmaz olyan előadást, amelyben bemutatják a logikai egyenletek megoldására szolgáló módszereket és logikai egyenletek rendszerét a Számítástechnika B15. Ismeretes, hogy ez a feladat az EGE feladatainak egyik legösszetettebb része. Az előadás hasznos lehet vezető tanulságokat a témában „logika” profil osztályok, valamint akkor, amikor készül a szállítás a USE.

Letöltés:

Előnézet:

Az előnézeti prezentációk megtekintéséhez hozzon létre egy fiókot (fiók) Google-t, és jelentkezzen be hozzá: https://accounts.google.com

A diákok aláírásai:

A B15 feladatának megoldása (logikai egyenletek rendszere) Vishnevskaya M.p., Maou "Gimnázia №3" 2013. november 18., Saratov

A B15 feladat az egyik legnehezebb a vizsga a számítástechnika !!! A készségek ellenőrzése: logikai változókat tartalmazó kifejezések átalakítása; a természetes nyelven leírni, több logikai változó értéket, amelyben egy adott logikai változócsoport igaz; Számítsa ki a megadott feltételeket kielégítő bináris készletek számát. A legnehezebb dolog, mert Nincs hivatalos szabályok Hogyan kell csinálni, megbízás szükséges.

Már nem tegyünk!

Már nem tegyünk!

Csatlakoztatás Csatlakozás: A / B, A  B, AB, A & B, A és B DYUMUTTION: A \\ / B, A + B, A | B, és vagy B negáció:  a, a, nem egyenértékűség: a  b, a  b, a  b kizárva "vagy": a  b, egy xor b

A változók cseréjére szolgáló módszer Hány különböző X1, X2, ..., X9, X10 logikai változók, amelyek megfelelnek az alábbiakban felsorolt \u200b\u200bösszes feltételnek: ((x1 ≡ x2) \\ / (x3 ≡ x4)) / \\ (¬ (¬) X1 ≡ X2) / ¬ (x3 ≡ x4)) \u003d 1 ((x3 ≡ x4) / (x5 ≡ x6)) / (x3 ≡ x4)) / \\ (¬ (x3 ≡ x4) \\ / ¬ (x5 ≡ x6)) \u003d 1 ( (x5 ≡ x6) / (x7 ≡ x8)) / \\ (¬ (x5 ≡ x7) / ¬ (x7 ≡ x8)) \u003d 1 ((x7 ≡ x8) \\ / (x9 ≡ x10)) / (x9 ≡ x10)) / \\ ( ¬ (x7 ≡ x8) / ¬ (x9 ≡ x10)) \u003d 1 Válaszolva, nem kell felsorolnia az összes X1, X2, ..., X9, X10 készüléket, amelyen az egyenlőtlenségi rendszert végezzük. Válaszként meg kell adnia az ilyen készletek számát (Demo verzió 2012)

Megoldás 1. lépés: A T1 \u003d X1  X2 T2 \u003d X3  X4 T3 \u003d X5  X6 T3 \u003d X7  X8 T4 \u003d X9  X8 T4 \u003d X9  X10 Az egyszerűsítés után: (T1 \\ / t2) / \\ / ¬ t2) \u003d 1 (t2 / t3) / \\ (¬t2 / ¬ t3) \u003d 1 (T3 \\ / t4) / \\ (¬t3 / ¬ t4) \u003d 1 (T4 \\ / t5) / \\ (¬t4 / ¬ t5) \u003d 1 fontolja meg az egyenletek egyikét: (T1 \\ t2) / \\ (¬t1 / ¬ t2) \u003d 1 nyilvánvalóan, csak akkor, ha az egyik változó 0, és A másik 1. A XOR művelet kifejezésére szolgáló képletet alkalmazzuk, és diszzsírálással: (T1 / t2) / \\ (¬t1 / ¬ t2) \u003d t1  t2 \u003d ¬ (t1 ≡ t2) \u003d 1 ¬ ( T1 ≡ t2) \u003d 1 ¬ (T2 ≡ T3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1

2. lépés. A rendszer analízise ¬ (t1 ≡ t2) \u003d 1 ¬ (t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (T4 ≡ T5) \u003d 1 t1 t2 T3 T4 T5 0 1 0 1 0 1 0 1 T .nak nek. TK \u003d X2K-1 ≡ X2K (T1 \u003d X1  X2, ....), a TK minden értéke két x2k-1 és x2k értéknek felel meg, például: tk \u003d 0 megfelel két párnak - (0,1) és (1, 0) és TK \u003d 1 - pár (0,0) és (1,1).

3. lépés. A megoldások számának számítása. Mindegyik T 2 megoldást tartalmaz, a T-5. számú A T változók esetében létezik 2 5 \u003d 32 megoldás. De mindegyik T megfelel egy x döntéshozatalnak, azaz A forrásrendszer 2 * 32 \u003d 64 megoldással rendelkezik. Válasz: 64.

A megoldások egy részének kizárására szolgáló módszer. Hány különböző értékű logikai változók X1, X2, ..., X5, Y1, Y2, ..., Y5, amelyek megfelelnek az alábbiakban felsorolt \u200b\u200bösszes feltételnek: (X1 → X2 ) ∧ (x2 → x4) ∧ (x3 → x4) ∧ (x4 → x5) \u003d 1; (Y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) \u003d 1; Y5 → X5 \u003d 1. A válasz nem kell felsorolnia az összes X1, X2, ..., X5, Y 1, Y2, ..., Y5-ot, amelyben ezt az egyenlőtlenségi rendszert végezzük. Válaszként meg kell adnia az ilyen készletek számát.

Döntés. 1. lépés. Következetes egyenletek megoldása X1 1 0 X2 1 0 1 X3 1 0 1 1 X4 1 0 1 1 1 1 X5 1 0 1 1 1 1 Első egyenlet - A több implációs műveletek összekapcsolása 1, vagyis az 1., azaz. Mindegyik következménye igaz. A FALSE implicitása csak egy esetben, ha 1  0, minden más esetben (0  0, 0  1, 1  1) Üzemeltetési hozam 1. Írja be az asztal formájában:

1. lépés. A T.O. egyenletek következetes megoldása 6 készlet megoldások x1, x2, x3, x4, x5, x3, x4, x5 kapunk: (00000), (00001), (00011), (00111), (01.111), (11111). Hasonlóan vitatkozunk arra a következtetésre, hogy Y1, Y2, Y3, Y4, Y5 esetében ugyanaz a megoldás. Mivel Ezek az egyenletek függetlenek, vagyis Nem rendelkeznek közös változókkal, majd az egyenletrendszer megoldása (a harmadik egyenlet kivételével) 6 * 6 \u003d 36 pár "IKS" és "Igarekov" lesz. Tekintsük a harmadik egyenletet: Y5 → X5 \u003d 1 A megoldás párok: 0 0 0 1 1 1 nem gőzoldat: 1 0

Összehasonlítjuk a kapott megoldásokat, ahol Y5 \u003d 1 nem megfelelő X5 \u003d 0. Ilyen pár 5. A rendszer megoldások száma: 36-5 \u003d 31. Válasz: 31 Szükség volt egy kombinatorics !!!

A dinamikus programozás módja Hány különböző megoldás van egy logikai egyenlet x 1 → x 2 → x 3 → x 4 → x 5 → x 6 \u003d 1, ahol x 1, x 2, ..., x 6 logikai változók? Válaszul, nem kell felsorolnia az összes különböző változót, amelyben ezt az egyenlőséget elvégzik. Válaszként meg kell adnia az ilyen készletek mennyiségét.

Határozat 1. lépés. A bal oldali állapot elemzését az egyenletben egymás után rögzíti a következménye, a prioritás ugyanaz. Átírjuk: ((((x 1 → x 2) → x 3) → x 4) → x 5) → x 6 \u003d 1 NB! Mindegyik következő változó nem az előzőtől függ, hanem az előző implikáció eredménye miatt!

2. lépés. A minták kimutatása Az első implicitációt figyelembe vesszük, x 1 → x 2. TATAC az igazság: x 1 x 2 x 1 → x 2 0 0 1 0 1 1 1 0 0 1 1 1 Az egyik 0-tól 2 egység érkezett, és 1 érkezett Egy 0 és egy 1. Csak egy 0 és három 1, ez az első művelet eredménye.

2. lépés. A minták kimutatása az első művelet eredményének összekapcsolásával X 3, kapunk: f (x 1, x 2) x 3 f (x 1, x 2)  x 3 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 két 0 - két 1, mindegyik 1 (ehhez 3) 1 és 1 (3 + 3)

3. lépés. A T.O képlet kimenete. A képleteket képezheti a n Zeros n i számának számításához és az E I egységek számának számításához az i változókkal való egyenlethez :,

4. lépés: A táblázat feltöltése Balról jobbra az i \u003d 6-ra, a nullák és egységek számának kiszámítása a fenti képletek szerint; A táblázat azt mutatja, hogy a következő oszlopban szerint épült az előzőhöz :: változók száma 1 2 3 4 5 6 nullák száma N i 1 1 3 5 11 21 egységek száma E i 1 2 * 1 + 1 \u003d 3 2 * 1 + 3 \u003d 5 11 21 43 Válasz: 43

Módszer A logikai kifejezések egyszerűsítéseinek használatával Hány különböző megoldás van egyenlete ((J → K) → (M  N  L))  ((m  n  l) → (¬ j  k)) ) \u003d 1 ahol J, K, L, M, N logikai változók? Válaszul, nem kell felsorolnia a J, K, L, M és N értékek különböző értékeit, amelyek alapján ez az egyenlőség történik. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás jébe J → k \u003d ¬ j  K Bemutatjuk a csere a változók: j → k \u003d a, m  n  L \u003d a újraírás egyenletben, figyelembe véve a helyettesítő: (A → B)  (B → a)  (m → j) \u003d 1 4. (A  b)  (m → j) \u003d 1 5. Nyilvánvaló, hogy a  b az A és a 6. pont azonos értékével rendelkezik következtetés: m → j \u003d 1 lehetséges, ha: m \u003d j \u003d 0 m \u003d 0, j \u003d 1 m \u003d j \u003d 1

Megoldás, mert A  B, majd m \u003d j \u003d 0-nál kapunk 1 + k \u003d 0-at. Nincs megoldás. Ha m \u003d 0, j \u003d 1, 0 + k \u003d 0, k \u003d 0, és n és l - bármely, 4 megoldás: ¬ j  k \u003d m  n  lnl 0 0 0 0 0 1 0 1 0 0 1 1

10. megoldás 10. M \u003d J \u003d 1, kapunk 0 + k \u003d 1 * n * l, vagy k \u003d n * l, 4 megoldások: 11. 4 + 4 \u003d 8 megoldás Válasz: 8 KNL 0 0 0 0 0 1 0 1 0 1 1 1

Információs források: ob Bogomolova, D.YU. Usenkov. B15: Új feladatok és új megoldás // Informatika, No. 6, 2012, p. 35 - 39. K.YU. Pólusok. Logikai egyenletek // informatika, 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [elektronikus erőforrás]. http://kpolyakov.narod.ru/school/ege.htm, [elektronikus erőforrás].

UDC 004.023

SEMENOV Sergey Maksimovich

Vladivostok Állami Közgazdaságtudományi Egyetem Oroszország. Vladivostok.

A logikai egyenletek megoldásának egyik módjában

Figyelembe kell venni a logikai egyenletek rendszerének megoldásainak meghatározását. Az eljárás alapja a faoldatok építésén alapul, és meghatározó aránya N. A kifejlesztett módszer alkalmazása konstruktív megközelítést biztosít a B15 EGE problémájának megoldásához.

Kulcsszavak és kifejezések: logikai egyenletek rendszere, fa megoldások, ismétlődő kapcsolatok, B15, EGE.

A gyakorlatban a logikai egyenletek rendszere hasznos a digitális logikai eszközök fejlesztésében. Az EGE egyik feladata a számítógépes tudományról a logikai egyenletek megoldására szolgál. Sajnos a probléma megoldásának különböző ismert módjai nem teszik lehetővé a feladat megoldásának egy megközelítését. Ennek eredményeképpen a probléma megoldása nagy nehézségeket okoz a diplomások számára. Kínálunk módot a logikai egyenletek rendszereinek megoldására, amely lehetővé teszi a diplomás egy jól meghatározott algoritmus követését. Ennek a módszernek az elképzelése szerepel. Ezt az ötletet alkalmaztuk és fejlesztettük (fa megoldások építése), majdnem az igazi fák igazságos tábláit használva. Különböző problémák megoldásakor kiderült, hogy a logikai egyenletek sok rendszerének megoldásainak száma ismétlődő arányok, például Fibonacci stb.

Logikai egyenletek rendszerei. A következő megnevezéseket tartjuk meg: diszjunkcionálás (+), összefüggés (), kivéve vagy (©), következtetése (-\u003e ■), egyenértékűség (\u003d), megtagadás (\u003d ■). Az ábrákon a sötétkör 1, és a fénykör 0. fl - az X1-es oldatok számát, amely az X1-es oldatok számával egyenlő. az egyenletrendszer. F (n) \u003d f1 (n) + f0 (n) a megoldások teljes száma.

1. feladat: Meg kell találni az egyenletrendszerek megoldásainak számát (a 2. tesztszámot)

Először azt feltételezzük, hogy x1 \u003d 1. Ezután az első egyenlethez az X2 és XS értékei lehetnek. Így a fa harmadik szintre épül. Ezután az x2 és az xs figyelembe vétele, válassza az X4 lehetőséget. Ezután az algoritmust megismételjük minden változó háromszorosára (1. ábra). A negyedik szinttől kezdve megjegyezhető, hogy fl (4) \u003d fl (3) + fl (1), fl (5) \u003d fl (4) + fl (2). Így kapunk fl (n) \u003d fl (n - 1) + fl (n-3) (1)

Ábra. 1. 1. feladat.

Az (1) egyenletből következik:

Bh (8) \u003d 16 + 7 \u003d 23,

Fl (9) \u003d 23 + 11 \u003d 34.

Ahhoz, hogy épít egy fa nulla, akkor az alsó ág ábrából. 1. Könnyű látni, hogy megismétli a főfát, de a 2-re való jobbra változik, azaz

Összesen, F (9) \u003d FL (9) + FO (9) \u003d 34 + 16 \u003d 50.

A fa megoldások építésénél vizuálisan hozza létre ismétlődő kapcsolatokat az N. megoldások számának meghatározásához.

A matematikai indukció elve: Legyen az FL, F2, FD utasítások sorozata, és hagyja, hogy az első FL utasítás helyesen legyen. Bizonyíthatjuk, hogy az Fn-nyilatkozat képzelete az Fn + L hűségét követi. Ezután az összes kijelentés ebben a sorozatban igaz.

Figyelembe kell venni. 2 az 1. feladathoz.

k2\u003e 3 x5 hb x7

Ábra. 2. A megoldások elemzése

A 2. ábra az első öt rendszeregyenlethez tartozó teljes csúcs (változó értékek kombinációja) formáját mutatja. Mindegyik egyenletben három változó érintett, így az ábrák három változó értékétől (három fát) állapítják össze. Az ábrák azonosítása érdekében lehetőség nyílik a jelölés bevezetésére. Azonban a következőképpen fogjuk folytatni: minden egyes ábrát a körök (változó értékek) összetevőinek számával összhangba teszik. Ezután megkapjuk a következő egyenleteket a sorrendben:

4. 7, 4, 4, 1, 7

5. 7, 4, 4, 1, 7, 7, 4.

A 4. egyenletből látható, hogy az N egyenlet számai az N-1 egyenlet és az N-3 egyenlet ábrákból állnak. Fontos, hogy nincsenek más alakok, és nem lehetnek ilyen típusú egyenletek, vagyis az egyik egyenletből való átmenet a szigorúan meghatározott szabályok szerint korlátozott készletből származó számok számának növelésével történik. Ez a tény az indukció érvényesítéséhez szükséges, hogy az N + 1 egyenlethez egy adatkészlet az N egyenlet és az N-2 egyenlet ábrákból áll.

Az ábrák azonosításának másik módja az, hogy meghatározzuk a változók értékeinek számát, az utolsó szinten az egyenlethez, vagyis a fa szintszámának egyenletéből kell mennie, mivel meg kell határoznunk a Az egyenletek rendszerének megoldásai száma, majd az épített fára kapunk egy sorozatot: 1, 2, 4, 5, 7, 11, 16. Ehhez a szekvenciához a képlet érvényes: fn \u003d fn - 1 + fn- 3.

Érveink szerint ez a képlet igaz az N + 1, az indukció és az N.

A meghatározott bizonyítási módszer alkalmazható az ilyen típusú rendszerekhez. A gyakorlatban elegendő az N szintű szint visszatérő arányának meghatározása, mivel az N + 1 szintnek megfelelő egyenlethez tartozó egyenletből való átmenet korlátozott számú ábrákon és módszerein alapul szint.

2. feladat: Meg kell találni az egyenletrendszerek megoldásainak számát (4.16)

(X1 \u003d x2) + (x1 \u003d x3) \u003d 1 (x2 \u003d xs) + (x2 \u003d x4) \u003d 1 (xs \u003d x4) + (xs \u003d x5) \u003d 1 (x4 \u003d x5) + (x4 \u003d x6) \u003d 1 (x5 \u003d x6) + (x5 \u003d x7) \u003d 1

XI X2 XS\u003e: 1 X5 HB X7

Ábra. 3. 2. feladat.

A 2. feladat megoldásainak számának megszerzéséhez lehetővé tenné, hogy ne építsük ki teljesen a megoldásokat (3. ábra), mivel nyilvánvaló, hogy az FL (N) \u003d N. Hasonlóképpen, FO (n) \u003d N. összesen f (7) \u003d 7 + 7 \u003d tizennégy.

3. feladat: Meg kell találni az egyenletrendszerek megoldásainak számát (az 1. tesztszámot)

(X1 ^ x2) ■ (x2 ^ xs) ■ (xs ^ x4) ■ (x4 ^ x5) \u003d 1

(Yl ^ y2) ■ (u2 ^ yz) ■ (yz ^ y4) ■ (yz ^ y5) \u003d 1

(Yl ^ x1) ■ (U2 ^ x2) ■ (yz ^ xs) ■ (Y4 ^ x4) ■ (y5 ^ x5) \u003d 1

A 4. ábra az X és Y megoldások fáit mutatja be, és a megfelelő igazságos táblák láthatóak.

Ábra. 4. 3. feladat.

Az első két egyenletből, mivel az x és y független, következik, hogy az F (5) \u003d 6 * 6 \u003d 36 megoldások teljes száma. A harmadik egyenlet megfontolása érdekében minden Y változó számára kiszámítható, Az X táblázatból származó készletek száma nem felel meg az egyenletnek. A Yi ^ Xi \u003d 0, ha Yi \u003d 1 és Xi \u003d 0. Más szavakkal, az Yl \u003d 1 esetében a harmadik egyenlet nem felel meg az X táblázatból származó összes vonalat, ahol X1 \u003d 0. A szám Az ilyen húrok 5. az y2 \u003d 1 sorokhoz - 4, stb. A harmadik egyenletnek nem teljesítő sorok teljes száma 5 + 4 + 3 + 2 + 1 \u003d 15.

Így a megengedett oldatok teljes száma megegyezik 36 - 15 \u003d 21. 4. feladat. Meg kell találni az egyenletrendszerek megoldásainak számát (4.17.a)

(X1 \u003d x2) + (x1 \u003d x3) \u003d (x2 \u003d x3) + (x2 \u003d x4) \u003d (x4 \u003d x5) + (x4 \u003d x6) \u003d (x5 \u003d x6) + (x5 \u003d x7) \u003d (HB) \u003d X7) + (hb \u003d x8) \u003d (x5 \u003d x6) \u003d 0

Ábra. 5. 4. feladat.

Ebben a példában nehéz meghatározni az F (n) végső képletet, könnyebben felépíthet egy megoldásokat a végére (vagy legalább x6-ig). Az 5. ábra az épített megoldásokat mutatja. Ennek eredményeként f (8) \u003d fl (8) + fo (8) \u003d 5 + 5 \u003d 10.

5. feladat: Meg kell találni az egyenletrendszerek megoldásainak számát (4.17.b)

(X1 \u003d x2) + (x1 \u003d x3) \u003d 1 (x2 \u003d x3) + (x2 \u003d x4) \u003d 1 (x3 \u003d x4) + (x3 \u003d x5) \u003d 1 (x4 \u003d x5) + (x4 \u003d x6) \u003d 1 (x5 \u003d x6) + (x5 \u003d x7) \u003d 1 (x6 \u003d x8) \u003d 1

Ebben a példában, mint az előző, könnyebben építeni egy fa megoldásokat a végére (6. ábra). Ennek eredményeként f (8) \u003d fl (8) + fo (8) \u003d 7 + 7 \u003d 14.

2. feladat: Meg kell találni az egyenletrendszer megoldásainak számát ([!]\u003e 4.17.V)

(X! 8 "x2) + (x2Hz) \u003d 1 (x2fx) + (xs \u003d x4) \u003d 1 (XS8" x4) + (x4 \u003d X5) \u003d 1 (x4 \u003d x5) + (x5 \u003d hb) \u003d 1 (X5fhb) + (HB \u003d x7) \u003d 1 (HB © x7) + (x7 \u003d x8) \u003d 1 A megoldásokat a 2. ábrán mutatjuk be. 7.

XI x2 xs x4 x5 x6 x7 x7 x2 x x x x4 x5 x6 x7 x8

Ábra. 6. 5. feladat Ábra 7. 6. feladat.

Ebből az egyenletrendszerhez nem volt lehetséges egy teljes megoldás fa építése, mivel már a harmadik negyedévből származik, egyértelmű, hogy az F1 (n) \u003d N. Könnyű látni, hogy a FO (n) egy fa, amely a második szinten kezdődik nulla. Ezután fo (n) \u003d n. Összesen, f (8) \u003d fl (8) + fo (8) \u003d 8 + 8 \u003d 16.

7. feladat Meg kell találnia az egyenletek rendszerének megoldásainak számát

(X4H5) + (x4 © x6) \u003d 1 (x5 © hb) + (x5 © x7) \u003d 1

Ne feledje, hogy ha x! \u003d X2 \u003d 1, az első egyenlet az XS \u003d 0-nál történik. Először egy fát építünk XL \u003d X2 \u003d 1 (8. ábra). Ezután az fl (n) \u003d fll (n) + fll (n).

XI X2 XS X4 X5 X6 X7 X8

Ábra. 8. 7. feladat.

A 8. ábrából látható, hogy az F11 (N) \u003d F11 (N - 1) + F11 (N-2) oldatok száma. Más szóval, a megoldások számát a Fibonacci számok írják le. Az F10 második faága nem épül fel, mivel az 1. ábrából kiderül. 1, a második szinttől kezdve. Ezután f10 (n) \u003d f11 (n + 1). Végül megkapjuk, hogy fll (8) \u003d 1z és flo (8) \u003d fll (9) \u003d 1z + 8 \u003d 21. Ezután fl (8) \u003d fll (8) + fll (8) \u003d 1z + 21 \u003d C4.

Az F0 (n) előállításához nem szükséges a megoldások fa felépítése, mivel az 1. ábrából származik. 1 A harmadik szinttől kezdődően. Ezután FO (n) \u003d fll (n + 2). Innen kapjuk, hogy FO (8) \u003d fll (10) \u003d fll (9) + fll (8) \u003d 21 + 1Z \u003d C4. Így az F (8) \u003d F1 (8) + F0 (8) \u003d Z4 + Z4 \u003d 68 oldatok teljes száma.

2. feladat: Meg kell találni az egyenletrendszer ([S], 2. feladat) megoldásainak számát

(X1 + x2) ^ (xs + x4) \u003d 1 (XS + x4) ^ (x5 + x6) \u003d 1 (x5 + x6) ^ (x7 + x8) \u003d 1 (x7 + x8) ^ (x7 + x8) ^ (x9 + x10) \u003d 1.

Szubsztitúció (X1 + X2) \u003d Yl, stb. És megkapjuk az egyenletrendszert:

^ ^ Y2 \u003d 1 y2 ^ yz \u003d 1 yz ^ y4 \u003d 1 y4 ^ y5 \u003d 1

Az oldatokat fa és az igazság táblázat ez a rendszer pontosan egybeesnek a fa és az asztal ábrán látható. 4. Figyelembe véve a szubsztitúciót, megjegyezzük, hogy az expresszió (x1 + x2) három esetben egyenlő (az opció kivételével, ha mindkét változó nulla).

Mivel az Y változók függetlenek, akkor az ábrán bemutatott igazságtábla első sorához. 4, a különböző kombinációk száma 35, a második sorban - 34, stb. A különböző kombinációk száma 35 + 34 + 33 + 32 + 31 + 30 \u003d 364.

2. feladat Meg kell találni az egyenletrendszer (a 4. feladat) megoldásainak számát

(^ ^) ■ (-x ^ x) ■ № ^ x) ■ (-x ^ kz) \u003d 1 No. ^ y2) ■ (u1 ^ yz) ■ (-G1 ^ y4) ■ (u1 ^ y5) \u003d 1 (-x + y 1) ■ (-x + y5) \u003d 1

Az x és y esetében a következő megoldások fái vannak

Ábra. 9. 8. feladat.

Figyelembe véve a harmadik egyenletet, a következő négy kombinációt kapjuk:

A - C: 4 * 4 \u003d 16 ((- £ 1 + y 1) ■ (-x + y5) \u003d (0 + 1) ■ (0 + 1) \u003d 1) B - C: 4 * 4 \u003d 16 ( (-X + y 1) ■ (-x + y5) \u003d (1 + 1) ■ (1 + 1) \u003d 1) A - D: \u003d 0 (0 + 0) ■ (-x + y5) \u003d 0) B - D: 4 * 4 \u003d 16 (1 + 0) ■ (1 + y5) \u003d 1) Összesen 48 oldatcsoport.

2. feladat. Meg kell találni az egyenletrendszerek megoldásainak számát (^ 1 \u003d b) + (xz \u003d x)) ■ \u003d ъ) + -fz \u003d X4) \u003d 1 ((x3 x4) + ( X5 \u003d X6)) ■ (- (x \u003d x) + - (x \u003d x6)) \u003d 1 ((x5 \u003d x6) + ^ 7 \u003d x ")) ■ (- (x \u003d x6) + - (^ 7) \u003d x8)) \u003d 1

((X7 \u003d x8) + (x9 \u003d xlo)) ■ (- ^ 7 \u003d x8) + \u003d xlo)) \u003d 1 Cseréljük: (xl \u003d b) \u003d yl (xz \u003d x4) \u003d y2

(X5 \u003d x) \u003d yz (x7 \u003d x8) \u003d y4 (x9 \u003d x10) \u003d y5

(Y ^ 2) ■ (- + ^) \u003d 1

(Y2 + YZ) ■ № + -TZ) \u003d 1

(YZ + Y4) ■ № + ^) \u003d 1

(Y4 + Y5) ■ (^ 4 + ^) \u003d 1

A 10. ábra mutatja a megoldásokat

U1 U2 UZ U4 U5

Ábra. 10. 2. feladat.

11. feladat. Meg kell találni az egyenletrendszerek megoldásainak számát (2. példa)

X1 + x2 \u003d 1 -4 + xs \u003d 1

A 11. ábra a megoldásokat mutatja. Tíz helyett a négy szintre korlátozódunk, mivel nyilvánvaló, hogy az F1 (n) \u003d 1 és f0 (n) \u003d n., majd p (s) \u003d p1 (s) + bosi) \u003d 1 + N. A mi esetünkben p (10) \u003d 1 + 10 \u003d 11.

Ábra. 11. 11. feladat.

12. feladat. Meg kell találni az egyenletek rendszerének (H. példa) megoldásainak számát

(X1 \u003d x2) + (x2 \u003d xs) \u003d 1

(X1 \u003d xs) + (xs \u003d x4) (x1 \u003d x4) + (x4 \u003d x5) (x1 \u003d X5) + (X5 \u003d X6) (X1 \u003d X6) + (X1 \u003d X6) + (X6 \u003d X7) (X1 \u003d X7) + (X7 \u003d x8) (x1 \u003d x) + (x8 \u003d x9) (x1 \u003d x9) + (x9 \u003d x10) (x1 \u003d x10) \u003d 0

Ábra. 12. 12. feladat.

Az "1" -es (öt szintre), megjegyezzük, hogy az FL (n) \u003d N. és a HN értékei N-1 "0" értékekből és egy értékből állnak ". A rendszerünk utolsó egyenlete azonban megtiltja az "1" értéket az x10-re. Ezért a megoldások száma fl (10) \u003d 10 - 1. Nem nehéz megjegyezni, hogy a "0" -ból származó megoldások szimmetrikusak lesznek (a nullák helyett egységek lesznek). Ezért az F0 \u003d 10 - 1. Végül

F (n) \u003d 2 x 9 \u003d 18.

13. feladat. Meg kell találni az egyenletrendszer (4. példa 4. példájának) megoldásainak számát

- (x1 \u003d x2) + (xs \u003d x4) \u003d 1

- (xs \u003d x4) + (x5 \u003d x) \u003d 1

- (x \u003d x) + (x7 \u003d x) \u003d 1

- (x7 \u003d x8) + (x9 \u003d x10) \u003d 1

Cseréljük:

(X1 \u003d x2) \u003d yl

(X5 \u003d x) \u003d yz

(X7 \u003d x8) \u003d y4

(X9 \u003d x10) \u003d y5

A helyettesítő egyenletek rendszerét átírjuk:

A 11. feladatból látható, hogy f (5) \u003d 5 + 1 \u003d 6. Az igazságtáblát az 1. ábrán mutatjuk be. 13.

U1 U2 UZ U4 U5

Ábra. 13. 13. feladat.

Figyelembe véve a helyettesítési, megjegyezzük, hogy az expressziós ^ \u003d X2) egyenlő egy (vagy nulla) két esetben (amikor a változók értékét egybeesnek). Figyelembe véve a változók függetlenségét a táblázat minden sorához, azt kapjuk, hogy a megoldások száma 25 \u003d 32. A megoldások teljes száma 6 * 32 \u003d 192.

14. feladat. Meg kell találni az egyenletrendszer (, 1. feladat) megoldásainak számát

((X \u003d ъ) ■ (xz \u003d x4)) + (4x1 \u003d ъ) ■ - (x \u003d x)) \u003d 0 ((xl \u003d x4) ■ (x5 \u003d x6)) + (4x3 \u003d x4) ■ - (X \u003d x6)) \u003d 0

((X5 \u003d x) ■ (x7 \u003d x8)) + (- (x \u003d x6) ■ 4x7 \u003d x8)) \u003d 0 ((x7 \u003d x8) ■ (x9 \u003d x ",)) + (- (^) 7 \u003d x8) ■ ^ 9 \u003d XLO)) \u003d 0 Cseréljük:

Kommersant) \u003d yl (x \u003d ^ 4) \u003d y2

(X5 \u003d x6) \u003d yz ^ 7 \u003d x8) \u003d y4 ^ 9 \u003d xlo) \u003d y5

A helyettesítő egyenletek rendszerét átírjuk:

(UL) + (-U "■ -U2) \u003d 0

(Y2 YZ) + (-U2 ■ -U3) \u003d 0 (U3-U4) + (-U3 ■ -U4) \u003d 0 (U4-U5) + (-U4 ■ -U5) \u003d 0

(U2 \u003d YZ) \u003d 0 (UZ \u003d U4) \u003d 0 (U4 \u003d U5) \u003d 0

A 14. ábra a megoldásokat mutatja

U1 U2 UZ U4 U5

Ábra. 14. 2. feladat.

Figyelembe véve a szubsztitúciót, megjegyezzük, hogy az expresszió (x1 \u003d x2) két esetben egy (vagy nulla) egyenlő (ha a változók értékei egybeesnek). Figyelembe véve a változók függetlenségét minden fára kapjuk, hogy a megoldások száma 25 \u003d з2. A megoldások teljes száma 64.

15. feladat. Meg kell találni az egyenletrendszer (, 2. feladat) megoldásainak számát

(X4 x5) + (-h4 -45) + (x4 \u003d x) \u003d 1

(X5 x) + (-х -х6) + (x5 \u003d x7) \u003d 1

(X x7) + (-х -х7) + (x \u003d x8) \u003d 1

(X7 x) + (-h7-h8) + (x7 \u003d x9) \u003d 1

(X8 x9) + (-х -х9) + (x8 \u003d x10) \u003d 1

(X1 \u003d x2) + (x1 \u003d xs) \u003d 1

(X \u003d xs) + (x2 \u003d x4) \u003d 1

(Xs \u003d x4) + (xs \u003d x5) \u003d 1

(X4 \u003d x5) + (x4 \u003d x) \u003d 1

(X5 \u003d x6) + (x5 \u003d x7) \u003d 1

(X \u003d x7) + (x6 \u003d x8) \u003d 1

(X7 \u003d x8) + (x7 \u003d x9) \u003d 1

(X \u003d x9) + (x8 \u003d x10) \u003d 1

De ez a rendszer megismétli a rendszert az 5. feladatból, csak az n \u003d 10-es határérték nélkül. Ezután az oldatok száma f (n) \u003d f1 (n) + f0 (n) \u003d n + n. N \u003d 10 F (n) \u003d 20 értéket kapunk.

16. feladat. Meg kell találni az egyenletrendszer (a 3. feladat) megoldásainak számát

(X1 x2) + (-h1-h2) + (x1 \u003d xs) \u003d 1

(X2 xs) + (-m -khz) + (x2 \u003d x4) \u003d 1

(XS X4) + (-khz -х4) + (xs \u003d x5) \u003d 1

(X4 x5) + (-х -х5) + (x4 \u003d hb) \u003d 1

(X5 Hb) + (-H-CHB) + (x5 \u003d x7) \u003d 1

(HB X7) + (-CHB -х7) + (hb \u003d x8) \u003d 1

(X7 x8) + (-4--48) + (x7 \u003d x9) \u003d 1

(X8 x9) + (-4--х9) + (x8 \u003d x10) \u003d 0

Ez az egyenletrendszer, mint az előző feladat, újraírható:

(Xi \u003d x2) + (xi \u003d xs) \u003d 1 (x \u003d xs) + (x2 \u003d x) \u003d 1 (xs \u003d x) + (xs \u003d x5) \u003d 1 (x \u003d x5) + (x4 \u003d hb) \u003d 1 (x5 \u003d hb) + (x5 \u003d x7) \u003d 1 (Hb \u003d X7) + (HB \u003d X8) \u003d 1 (X \u003d X8) + (x7 \u003d x9) \u003d 1 (x \u003d x9) + (x8 \u003d Xx) \u003d 0

Az utolsó egyenletből könnyen ellenőrizhető, hogy n \u003d 8 után a megoldások száma megszűnik. Ezután f (10) \u003d f (8) \u003d 8 + 8 \u003d 16.

17. feladat. Meg kell találni az egyenletrendszer (a 4. feladat) megoldásainak számát

(X1 x2) + (-h1-h2) + (x2 xs) + (-h2-kHz) \u003d 1

(X2 xs) + (-h2--kHz) + (xs x) + (-khz ■ -h4) \u003d 1

(XS X) + (-khz -х4) + (x4 x5) + (-h4 -45) \u003d 1

(X4 x) + (-x5) + (x5 Hb) + (-H5-CHB) \u003d 1

(X5 HB) + (-H-CHB) + (HB X7) + (-CHB ■ -h7) \u003d 1

(HB X7) + (-khb -х7) + (x7 x8) + (-h7 -48) \u003d 1

(X7 x) + (-4--48) + (x8 x9) + (-h8 -49) \u003d 1

(X8 x9) + (-4--49) + (x9 x10) + (-49 ■ -410) \u003d 1

Ne feledje, hogy az egyenletek rendszere átírható, mint:

(X \u003d x2) + (x \u003d xs) \u003d 1 (x \u003d xs) + (x \u003d x) \u003d 1 (XS \u003d X4) + (x4 \u003d X5) \u003d 1 (X \u003d X5) + (X5 \u003d HB) \u003d 1 (x5 \u003d hb) + (hb \u003d x7) \u003d 1

(HB \u003d X7) + (x7 \u003d x) \u003d 1 (x7 \u003d x8) + (x8 \u003d x9) \u003d 1 (x9 \u003d x 9) + (x9 \u003d x10) \u003d 1

A 15. ábrán a fa ötödik szintre épül, és látható, hogy a megoldások számát a fibonacci számok, azaz fl (n) \u003d fl (n - 1) + fl (N-2 ). Ezután fl (10) \u003d 89. Könnyű ellenőrizni, hogy az f0 (n) a fa szimmetrikusan lesz. Ezért (10) \u003d 89. B (10) \u003d P1 (10) + PO (10) \u003d 89 + 89 \u003d 178.

Ábra. 15. 17. feladat.

18. feladat. Meg kell találni az egyenletrendszer (az 5. feladat) megoldásainak számát

(X1 x2) + (-h1-h2) + (x2 xs) + (-h2 ■ -khz) \u003d 1

(X2 xs) + (-h -khz) + (XS X4) + (-khz -х4) \u003d 1

(XS X4) + (-khz -х4) + (x4 x5) + (-4 ■ -h5) \u003d 1

(X4 x5) + (-h4 -45) + (x HB) + (-h5 ■ -HB) \u003d 1

(X5 HB) + (-H5-HB) + (HB X7) + (-kb ■ -h7) \u003d 1

(HB X7) + (-HB -H7) + (x7 x8) + (-h7 ■ -h8) \u003d 1

(X7 x8) + (-4--48) + (x8 x9) + (-h8-h9) \u003d 1

(X8 x9) + (-4--49) + (x9 x10) + (-h9 ■ -h10) \u003d 0

Ne feledje, hogy az egyenletek rendszere átírható, mint:

(X \u003d x2) + (x2 \u003d x3) \u003d 1 (x2 \u003d xs) + (xs \u003d x4) \u003d 1

(Xs \u003d x) + (x4 \u003d x5) \u003d 1 (x \u003d x5) + (x5 \u003d hb) \u003d 1 (x \u003d hb) + (hb \u003d x7) \u003d 1 (Hb \u003d X7) + (x7 \u003d x8) \u003d 1 (x7 \u003d x8) + (x8 \u003d x9) \u003d 1 (x8 \u003d x 9) + (x \u003d x10) \u003d 0

A 18. feladat hasonló a 17. feladathoz, azonban az utóbbi egyenlet azt eredményezi, hogy a hetedik szint óta a megoldások száma nem növekszik. Ennek eredményeként f (10) \u003d fl (10) + fo (10) \u003d fl (7) + fo (7) \u003d 21 + 21 \u003d 42.

5. feladat. Meg kell találni az egyenletek rendszerének (, B. feladat) megoldásainak számát

(X \u003d x2) + (x \u003d x10) \u003d 1 (x \u003d XS) + (X \u003d X10) \u003d 1 (XS \u003d X4) + (X \u003d X10) \u003d 1 (X \u003d X5) + (X \u003d X10) \u003d 1 (x \u003d hb) + (x5 \u003d x10) \u003d 1 (HB \u003d X7) + (HB \u003d X10) \u003d 1 (x7 \u003d x) + (x \u003d x10) \u003d 1 (x8 \u003d x9) + (x \u003d X10) \u003d 1 (x9 \u003d x10) + (x9 \u003d x10) \u003d 1 (x \u003d x10) \u003d 0

- - - -*- - - -*-ról ről

Ábra. 1b. 19. feladat.

Az F1 (N) és F0 (N) előállítására szolgáló oldatok fái az 1. ábrán láthatóak. 1b. Az (X9 \u003d X10) \u003d 1 egyenlet azonban nem hajtható végre. Ezért az egyenletrendszernek nincs megoldása.

20. feladat. Meg kell találni az egyenletrendszer (a 7. feladat) megoldásainak számát

(X ^ x2) + (x ^ xz) \u003d 1 (x2 ^ x) + (x2 * x4) \u003d 1 (xs ^ x4) + (xs ^ x5) \u003d 1 (x ^ x5) + (x4 ^ hb) \u003d 1 (x5 ^ hb) + (x5 ^ x7) \u003d 1 (HB ^ x7) + (HB ^ x8) \u003d 1

(X7 ^ xs) + (x7 ^ x9) \u003d 1 (xs ^ x9) + (xs ^ x10) \u003d 1

A 17. ábra az "1" -ből származó megoldásokat mutatja.

Ábra. 17. 20. feladat. 18. 2. feladat.

Tíz szint helyett ötre korlátozódunk, mivel a feladat hasonló a 17. feladathoz. A "0" -tól azonban a fa különbözik (18. ábra).

Ne feledje, hogy f0 (n) \u003d fx (n + 1) - 1., majd FX (10) \u003d 89 és F0 (10) \u003d FX (11) - 1 \u003d 144 - 1. Összesen, F (10) \u003d F1 ( 10) + F0 (10) \u003d 89 + 143 \u003d 232.

Összefoglalva, adunk egy programot egy alap VBA-nál, amellyel megoldhatja a logikai egyenletek rendszerét. A programra szükség lehet az új egyenletek összeállításához. A 19. ábra azt mutatja meg, hogy a 7. feladat egyenletrendszerének megoldása megoldódott.

Az 1. ábrán bemutatott programban. 19, egy M tömb és a C változó olyan változók értékeit tartalmazza, amelyek megfelelnek az egyenletek rendszerének a 7. feladatból. A program megadja a 68. válaszot. A program azt a tényt használja, hogy az N logika különböző értékeinek száma A változók 2n. Az összes készlet beszerzéséhez 0-tól 2 N-1-ig kell elvégeznie a ciklust. Az egyes lépésekben bekövetkező ciklusváltozót a bináris rendszerbe lefordítják, az eredményt M-re írják, majd az egyenletrendszerből származó körülmények már ellenőrizzük. Egy másik egyenletrendszer megoldásához elegendő az M tömb mérete megváltoztatásához, módosítsa a VG változó értékét (egyenlő a dimenzióval), és módosítsa az ellenőrzés érvényességét.

Dim M (S) mint egész szám, K egész szám, J. Egész számként. _ J, mint egész szám. N, mint egész szám, a vg, mint a vg \u003d s j-0 karakterlánc

1-től 2-ig ■ "" ■ VG "ciklus az 1-től 2-ig. Ahol n \u003d ,. g a k \u003d 1-től a vg-ig

N \u003d) .- 1: bináris e pr e c telepített e NNO kezdődik a Scratch K \u003d 1

Do "^ tiils n\u003e 0" fordítás e bináris xuramp m (k) \u003d n mod 2 k \u003d n ■ 2 k \u003d K +! Hurok.

Haim (l) o m (2) vagy m (l) 0- ni (3)) és_ "egyenlet feltételei (m (2)

c \u003d "" "A változó minden lépésből képes lesz a rendszer megoldása a k \u003d 1, hogy a vg

c \u003d C - FOIMAT (M (K) J Next K J-J-1 Vége, ha a következő I.

MS ^ EOX I "Megoldások száma

Vvvvvvvvvvvvv-1 I.

Ábra. 19. A 7. feladat programja

1. Wings S.S. Ege 2014. Informatika. Tematikus vizsgálati feladatok / S.S. WIONS, D.M. Ushakov. - M.: Kiadó "vizsga". - 245 p.

2. Site K.YU. Polyakova. Hozzáférési mód: http: //kpolyakov.namd.-ru/download/in-2011-14.pdf

3. Módszertani tanúsított tanfolyam a cég "1c" "Készítés a vizsga a számítógép-tudományban. 1. modul. - M.: "1c kiadó". - 218 p.

4. Sikeres az ECH a számítógép-tudományon. Hozzáférési mód: http://inoegehelp.ru/index.php?itemid\u003d77&id\u003d103&option\u003dcom_con-