Elibriális logikai egyenletek. Logikai egyenletek megoldása a matematikában

Néhány probléma megoldása a számítástechnika vizsga A és B részében

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

Számos USE feladatot szentelnek a javaslatok logikájának. 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.

1. A diszjunkció és a konjunkció kommutativitása:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. A diszjunkcióra és a konjunkcióra vonatkozó elosztási törvény:
   a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negatív tagadás:
   ¬(¬a) ≡ a
4. Következetesség:
   a ^ ¬a ≡ hamis
5. Exkluzív harmadik:
   a ˅ ¬a ≡ igaz
6. De Morgan törvényei:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Egyszerűsítés:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ igaz ≡ a
   a ˄ hamis ≡ hamis
8. Abszorpció:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Az implikáció cseréje
   a → b ≡ ¬a ˅ b
10. Identitásváltás
    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) definiálható igazságtáblázattal. Egy ilyen tábla 2 n változókészletet tartalmaz, amelyek mindegyikéhez meg van adva az ezen a halmazon lévő függvény értéke. Ez a módszer akkor jó, ha a változók száma viszonylag kicsi. Még n > 5 esetén is rosszul látható az ábrázolás.

Egy másik lehetőség, hogy a függvényt valamilyen képlettel definiáljuk, jól ismert, meglehetősen egyszerű függvényekkel. A függvényrendszert (f 1 , f 2 , … f k ) teljesnek nevezzük, 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 arra, hogy az implikáció és az azonosság hogyan fejeződik ki tagadással, konjunkcióval és diszjunkcióval.

Valójában a két függvény rendszere is teljes – a tagadás és a konjunkció vagy a tagadás és a diszjunkció. A reprezentációk De Morgan törvényeiből következnek, amelyek lehetővé teszik a konjunkció kifejezését tagadással és diszjunkcióval, és ennek megfelelően a diszjunkció kifejezésé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 Pierce nyílnak és Schaeffer ütésének 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ó. BAN BEN HASZNÁLJON feladatokat ezekkel a funkciókkal együtt gyakran van egy következmény.

Nézzünk meg néhány egyszerű feladatot a logikai függvényekkel kapcsolatban.

15. feladat:

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?

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

3. számú funkció.

A probléma megoldásához ismerni kell az alapfüggvények igazságtáblázatait, és szem előtt kell tartania a műveletek prioritásait. Hadd emlékeztesselek arra, hogy a konjunkció (logikai szorzás) magasabb prioritású, és a diszjunkció (logikai összeadás) előtt kerül végrehajtásra. Számításkor jól látható, hogy a harmadik halmaz 1-es és 2-es számú függvényei 1-es értékkel rendelkeznek, és emiatt nem felelnek meg a töredéknek.

16. feladat:

Az alábbi számok közül melyik felel meg a feltételnek:

(a számjegyek, a legjelentősebb számjeggyel kezdve, csökkenő sorrendben) → (szám - páros) ˄ (legalacsonyabb számjegy - páros) ˄ (legmagasabb számjegy - páratlan)

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

1. 13579
2. 97531
3. 24678
4. 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ám esetében teljesülnek a szám kis- és nagy számjegyére támasztott feltételek. A kötőszó első tagja is igaz, hiszen egy implikáció akkor igaz, ha a premisszája hamis, ami itt a helyzet.

17. probléma: Két tanú a következőket vallotta:

Első tanú: Ha A bűnös, akkor B biztosan bűnös, 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 pontosan megmondani, hogy ki.

Milyen következtetéseket lehet levonni A, B és C bűnösségére vonatkozóan a bizonyítékokból?

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

Megoldás: Természetesen józan ész alapján is meg lehet adni a választ. 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 mindegyike igaz (1), 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))

Feltételezzük, hogy mindkét tanú vallomása igaz, és a megfelelő formulák kötődését jelenti.

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

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

E táblázat elemzéséből az is következik, hogy a második tanú vallomása informatívabb. Tanúvallomása igazságából csak két lehetséges lehetőség következik: A és B bűnös, C pedig ártatlan, vagy A és C bűnös, B pedig ártatlan. Az első tanú vallomása kevésbé informatív - 5 különböző lehetőség van, amelyek megfelelnek a vallomásának. Mindké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 a következő:

F(x 1, x 2, ... x n) \u003d C,

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

Egy logikai egyenletnek 0-2n 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, amelyeken az F függvény az igaz (1) értéket veszi fel. A fennmaradó halmazok a C egyenletének nullával egyenlő megoldásai. Mindig csak az alábbi alakú egyenleteket vehetjük 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 egyenértékű egyenlethez léphet:

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

Tekintsünk egy k logikai egyenletrendszert:

F 1 (x 1, x 2, ... x n) \u003d 1

F 2 (x 1, x 2, ... x n) \u003d 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. A logikai függvények szempontjából a logikai egyenletrendszer megoldásához keresni kell egy halmazt, amelyre igaz a Ф logikai függvény, amely az eredeti F függvények konjunkcióját reprezentálja:

Ф = 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.

A logikai egyenletrendszerre megoldást kereső Egységes Államvizsga egyes feladataiban a változók száma eléri a 10 értéket. Ekkor az igazságtábla készítése szinte megoldhatatlan feladattá válik. A probléma megoldása más megközelítést igényel. Egy tetszőleges egyenletrendszerhez nincs általános módon, amely eltér a felsorolástó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, egy változóhalmaz összes változatának felsorolásán kívül 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. Egy másik hasznos technika a probléma megoldása a következő. Nem minden halmaz érdekel, hanem csak azok, amelyeken a Ф függvény értéke 1. Ahelyett, hogy egy teljes igazságtáblázatot szerkesztenénk, megépítjük annak 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.

Mi az a bináris döntési fa, és hogyan épül fel, több feladat példáján fogom elmagyarázni.

18. probléma

Hány különböző x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változó értékkészlete elégít ki egy 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 meg az első egyenlet megoldásainak számát 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 logikai függvények konjunkciója. A fordított állítás is igaz - a feltételek konjunkciója egyenletrendszernek tekinthető.

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

A fa két szintből áll az egyenletben szereplő változók számának megfelelően. 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 értéket vesz fel. Mivel az egyenlet implikációt definiál, az az ág, amelyen X 1 értéke 1, megköveteli, hogy X 2 ezen az ágon 1 legyen. Az az ág, amelyen X 1 értéke 0, két ágat generál, amelyek X 2 értéke 0 és 1 A megszerkesztett fa három ágat határoz meg megoldások, amelyekre az X 1 → X 2 implikáció 1 értéket vesz fel. Minden ágon kiírják a 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 ágon, ahol az X 2 változó értéke 1, az X 3 változó is 1-es lesz. Az ilyen ágak esetében a fa felépítése folytatódik a következő szintre, de nem jelennek meg új ágak. Az egyetlen ág, ahol az X 2 változó értéke 0, két elágazást ad, ahol az X 3 változó a 0 és az 1 értéket kapja. Így egy új egyenlet minden egyes hozzáadása, annak specifikussága miatt, hozzáad egyet. megoldás. Eredeti első egyenlet:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
6 megoldása van. Így néz ki az egyenlet teljes döntési fája:

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 minden X i változó megoldás kombinálható minden Y j változó megoldással, a megoldások száma összesen 36.

Figyeljük meg, hogy a felépített döntési fa nem csak a megoldások számát adja meg (az ágak számának megfelelően), hanem magát a megoldást is, a fa minden ágára felírva.

19. probléma

Hány különböző x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változó értékhalmaza van, amely kielégíti az összes alábbi feltételt?

(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 értéke 1. Tehát 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, 0 és 1 is. Ezért minden olyan halmaz, ahol X 1 egyenlő 0, és 5 ilyen halmaz van, mind a 6 Y változós halmaznak felel meg. , 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ára, az egyenletünket így í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ővel:

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. feladatban, a ciklikus implikációkról az azonosságokra úgy térünk át, hogy az egyenletet a következő alakba írjuk át:

(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ása van a következő egyenletrendszernek?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0

((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0

((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0

((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 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 \u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (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

A hagyományos formára áttérve 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ókhoz, vegyük figyelembe, hogy az Y változó minden értéke az X változó 2 értékének felel meg, így az Y változók mindegyik megoldása 25 megoldást generál az X változókban. Két ág 2 * 25 megoldást generál , tehát a megoldások száma összesen 64.

Mint látható, minden egyenletrendszer megoldási feladathoz saját megközelítésre van szükség. Általános recepció Az egyenletek egyszerűsítése érdekében ekvivalens transzformációkat kell végrehajtani. Elterjedt technika a döntési fák felépítése. Az alkalmazott megközelítés részben hasonlít egy igazságtábla felépítésére, 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 az is kezdeti szakaszban minden következő szinten meg lehet állapítani az új ágak megjelenésének szabályosságát, mint például a 18. feladatnál.

Általában a logikai egyenletrendszerek megoldásának problémái jó matematikai gyakorlatok.

Ha a probléma manuálisan nehezen megoldható, akkor a feladat megoldását a számítógépre bízhatja egy megfelelő egyenlet- és egyenletrendszer-megoldó program megírásával.

Könnyű ilyen programot írni. Egy ilyen program könnyen megbirkózik a vizsgán felkínált összes feladattal.

Furcsa módon, de a logikai egyenletrendszerek megoldásának a feladata is nehéz egy számítógép számára, kiderül, hogy a számítógépnek megvannak a határai. A számítógép könnyen megbirkózik azokkal a feladatokkal, ahol a változók száma 20-30, de sokáig elkezd gondolkodni a feladatokon nagyobb méretű. A lényeg az, hogy a halmazok számát meghatározó 2 n függvény egy olyan kitevő, amely n-nel gyorsan növekszik. Olyan gyorsan, hogy egy normál személyi számítógép nem tud egy nap alatt 40 változót tartalmazó feladatot kezelni.

C# program logikai egyenletek megoldására

A logikai egyenletek megoldására szolgáló programot több okból is hasznos írni, már csak azért is, mert ezzel ellenőrizhető a saját megoldás helyessége a USE tesztfeladatokra. Egy másik ok az, hogy egy ilyen program kiváló példa egy olyan programozási problémára, amely megfelel a C kategóriás problémák követelményeinek az USE-ban.

A program felépítésének ötlete egyszerű - az összes lehetséges változóérték-készlet teljes felsorolásán alapul. Mivel egy adott logikai egyenlethez vagy egyenletrendszerhez ismert az n változók száma, a halmazok száma is ismert - 2 n , amelyeket rendezni kell. A C# nyelv alapfunkcióinak - tagadás, diszjunkció, konjunkció és azonosság - felhasználásával könnyen írható olyan program, amely adott változóhalmazra kiszámolja 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ámával, a ciklus törzsében a halmaz számával, magát a halmazt képezni, ki kell számítani a függvény értékét ezen a halmazon, és ha ez az érték egyenlő 1-hez, 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 változó értékek halmazát a beállított szám alapján alakítsák ki. Ennek a feladatnak az a szépsége, hogy ez a látszólag nehéz feladat valójában egy olyan egyszerű feladathoz vezet, amely már többször felmerült. Valójában elég megérteni, hogy az i számnak megfelelő változók nullákból és egyesekből álló értékkészlete az i szám bináris reprezentációját jelenti. Így nehéz feladat a változók értékeinek a halmaz számával történő megszerzése a számok bináris rendszerré alakításának jól ismert problémájára redukálódik.

Így néz ki a problémánkat megoldó C# függvény:

///

///

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

/// amelynek aláírását a DF delegáltja állítja be

///

/// 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;

//Teljes felsorolás a készletek számával

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

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

//az i szám bináris reprezentációja adja

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 halmaznál

A program megértéséhez remélem, hogy elegendő lesz a program ötletének magyarázata és a szövegében található megjegyzések. Csak a fenti függvény fejlécének magyarázatánál fogok időzni. 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 határozza meg a fun függvény változóinak számát. 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 bevett szokás, ha valamilyen F(x) függvénynél az x bemeneti paraméter egy aritmetikai, karakterlánc vagy logikai típusú változó. Esetünkben erősebb kialakítást alkalmazunk. A SolveEquations függvény magasabb rendű függvényekre vonatkozik - F(f) típusú függvényekre, 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ő:

delegate bool DF(bool vars);

Ez az osztály tartalmazza az összes olyan függvényt, amely paraméterként a vars tömb által meghatározott logikai változók értékkészletét adja át. Az eredmény egy logikai érték, amely a függvény értékét képviseli ebben a halmazban.

Befejezésül adok egy programot, amelyben a SolveEquations függvényt több logikai egyenletrendszer megoldására használjuk. A SolveEquations függvény a következő ProgramCommon osztály része:

osztályú ProgramCommon

delegate bool DF(bool vars);

static void Main (string args)

Console.WriteLine("Funkciók és megoldások - " +

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

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

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

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

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

statikus bool Fun53 ​​(bool vars)

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

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

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

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

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

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

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

Így néz ki a program megoldásának eredménye:

10 feladat önálló munkához

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

A három funkció közül melyik felel meg ennek a töredéknek:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. 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. BAN BEN másképp nem születik döntés. Építsen fel egy logikai függvényt, amely formalizálja a döntéshozatali folyamatot.
5. X nyer Y felett, ha négy érmefeldobás háromszor ér fel. Határozzon meg egy logikai függvényt, amely leírja az X kifizetést.
6. A mondatban lévő szavak egytől kezdődően vannak számozva. Egy mondat akkor tekinthető jól megformáltnak, ha a következő szabályok teljesülnek:
   1. Ha egy páros számú szó magánhangzóra végződik, akkor a következő szónak, ha létezik, magánhangzóval kell kezdődnie.
   2. Ha egy páratlan számú szó mássalhangzóra 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.
      Az alábbi mondatok közül melyik a helyes:
   3. Anya szappannal megmosta Mashát.
   4. A vezető mindig modell.
   5. Az igazság jó, de a boldogság jobb.
7. Hány megoldása van az egyenletnek:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Sorolja fel az egyenlet összes megoldását:
   (a → b) → c = 0
9. 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
10. Hány megoldása van az egyenletnek:
    (((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Válaszok a feladatokra:

1. A b és c függvények egyenértékűek.
2. A töredék a b függvénynek felel meg.
3. A P logikai változó vegye fel az 1 értéket, 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. A pozitív döntés elfogadását meghatározó logikai függvény a következőképpen írható fel:
   P ˄ (M 1 ˅ M 2)
4. A P i logikai változó vegye fel az 1 értéket, amikor az i-edik érmefeldobás fejjel jön fel. 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))
5. Ajánlat b.
6. Az egyenletnek 3 megoldása van: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)

Legyen n változó logikai függvénye. A logikai egyenlet a következő:

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

Egy logikai egyenletnek 0-tól többféle megoldása lehet. Ha C egyenlő 1-gyel, akkor a megoldások mindazok az igazságtáblázatbeli változók, amelyeken az F függvény az igaz (1) értéket veszi fel. A fennmaradó halmazok a C egyenletének nullával egyenlő megoldásai. Mindig csak az alábbi alakú egyenleteket vehetjük figyelembe:

Valóban, legyen adott az egyenlet:

Ebben az esetben az egyenértékű egyenlethez léphet:

Tekintsünk egy k logikai egyenletrendszert:

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 Ф logikai függvény, amely az eredeti függvények konjunkcióját reprezentálja:

Ha a változók száma kicsi, például kevesebb, mint 5, akkor nem nehéz a függvényhez 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.

A logikai egyenletrendszerre megoldást kereső Egységes Államvizsga egyes feladataiban a változók száma eléri a 10 értéket. Ekkor az igazságtábla készítése szinte megoldhatatlan feladattá válik. A probléma megoldása más megközelítést igényel. Egy tetszőleges egyenletrendszer esetében a felsoroláson kívül nincs más általános út, amely lehetővé tenné 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, egy változóhalmaz összes változatának felsorolásán kívül 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. A probléma megoldására egy másik hasznos technika a következő. Nem minden halmaz érdekel, hanem csak azok, amelyeken a függvény értéke 1. A teljes igazságtáblázat felépítése helyett annak analógját, egy bináris döntési fát építünk. Ennek a fának minden ága egy megoldásnak felel meg, és megadja azt a 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.

Mi az a bináris döntési fa, és hogyan épül fel, több feladat példáján fogom elmagyarázni.

18. probléma

Hány különböző x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változó értékkészlete elégít ki egy 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 meg az első egyenlet megoldásainak számát 5 változótól függően - . Az első egyenlet pedig 5 egyenletrendszernek tekinthető. Mint látható, az egyenletrendszer valójában logikai függvények konjunkciója. A fordított állítás is igaz - a feltételek konjunkciója egyenletrendszernek tekinthető.

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

A fa két szintből áll az egyenletben szereplő változók számának megfelelően. Az első szint az első 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 a változó azon lehetséges értékeit tükrözik, amelyekre az egyenlet igaz értéket vesz fel. Mivel az egyenlet implikációt határoz meg, az ág, amelyen 1-es értéke van, megköveteli, hogy ezen az ágon 1 legyen. Az az ág, amelyiken 0 értéke van, két 0-val egyenlő értékű ágat generál, és 1. A megszerkesztett fa három megoldást definiál, ahol az implikáció az 1-es értéket veszi fel. Minden ágra kiírják a változók megfelelő értékkészletét, ami 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óval. 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 a változónak már vannak értékei a fában, ezért minden ágon, ahol a változó értéke 1, a változó értéke is 1 lesz. Az ilyen ágaknál a fa felépítése a következő szintre megy tovább, de új ágak nem jelennek meg. Az egyetlen ág, ahol a változó értéke 0, két elágazást ad, ahol a változó a 0 és az 1 értéket kapja. Így egy új egyenlet minden egyes hozzáadása, annak specifikussága miatt, egy megoldást ad hozzá. Eredeti első egyenlet:

6 megoldása van. Így néz ki az egyenlet teljes döntési fája:

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

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 minden változó megoldás kombinálható minden változó megoldással, a megoldások száma összesen 36.

Figyeljük meg, hogy a felépített döntési fa nem csak a megoldások számát adja meg (az ágak számának megfelelően), hanem magát a megoldást is, a fa minden ágára felírva.

19. probléma

Hány különböző x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 logikai változó értékhalmaza van, amely kielégíti az összes alábbi feltételt?

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 egyenletből következik, hogy ha értéke 1 (egy ilyen megoldás létezik), akkor 1-es. Így van egy halmaz, amelyen és az 1-es értékekkel rendelkezik. Ha egyenlő 0-val, akkor lehet tetszőleges érték, 0 és 1 is. Ezért minden 0-val egyenlő halmaz, és 5 ilyen halmaz van, mind a 6 Y változós halmaznak felel meg. Ezért a megoldások száma összesen 31.

20. probléma

Megoldás: Emlékezve az alapvető ekvivalenciára, az egyenletünket így írjuk fel:

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

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

21. probléma

Hány megoldása van az egyenletnek:

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

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

22. probléma

Hány megoldása van a következő egyenletrendszernek?

A logikai egyenletrendszerek megoldásának többféle módja van. Ez egy egyenletre való redukció, igazságtáblázat felépítése és dekompozíció.

Feladat: Oldjon meg egy logikai egyenletrendszert:

Fontolgat az egyenletre való redukció módszere . Ez a módszer magában foglalja a logikai egyenletek transzformációját úgy, hogy a jobb oldaluk egyenlő legyen az igazságértékkel (azaz 1-gyel). Ehhez használja a logikai tagadás műveletét. Ezután, ha az egyenletekben összetett logikai műveletek vannak, azokat alapműveletekre cseréljük: „ÉS”, „VAGY”, „NEM”. A következő lépés az egyenletek összevonása a rendszerrel ekvivalenssé, az "ÉS" logikai művelettel. Ezt követően a kapott egyenletet a logikai algebra törvényei alapján kell transzformálni, és egy konkrét megoldást kapni a rendszerre.

1. megoldás: Alkalmazza az inverziót az első egyenlet mindkét oldalára:

Képzeljük el az implikációt az "OR", "NOT" alapműveletekkel:

Mivel az egyenletek bal oldala egyenlő 1-gyel, az „ÉS” művelettel kombinálhatja őket egy egyenletté, amely egyenértékű az eredeti rendszerrel:

Megnyitjuk az első zárójelet de Morgan törvénye szerint, és átalakítjuk az eredményt:

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

A következő út az igazságtáblázatok felépítése . Mivel a logikai értékeknek csak két értéke van, egyszerűen végignézheti az összes lehetőséget, és megtalálhatja közöttük azokat, amelyekre az adott egyenletrendszer teljesül. Ez azt jelenti, hogy felállítunk egy közös igazságtáblázatot a rendszer összes egyenletére, és keresünk egy sort a kívánt értékekkel.

2. megoldás: Készítsünk egy igazságtáblázatot a rendszerhez:

Félkövér az a vonal, amelyre a probléma feltételei teljesülnek. Tehát A=0, B=0 és C=1.

Út bomlás . Az ötlet az, hogy rögzítjük az egyik változó értékét (tegyük egyenlővé 0-val vagy 1-gyel), és ezzel egyszerűsítsük az egyenleteket. Ezután rögzítheti a második változó értékét, és így tovább.

3. megoldás: Legyen A = 0, akkor:

Az első egyenletből B = 0, a másodikból pedig С=1 kapjuk. Rendszermegoldás: A = 0, B = 0 és C = 1.

A számítástechnikában az USE-ban nagyon gyakran meg kell határozni a megoldások számát egy logikai egyenletrendszerre, anélkül, hogy maguknak a megoldásokat találnánk, erre is vannak bizonyos módszerek. A logikai egyenletrendszer megoldásainak számának megtalálásának fő módja azváltozók változása. Először minden egyenletet a lehető legnagyobb mértékben le kell egyszerűsíteni a logikai algebra törvényei alapján, majd az egyenletek összetett részeit új változókkal helyettesíteni, és meg kell határozni az új rendszer megoldásainak számát. Ezután térjen vissza a helyettesítéshez, és határozza meg a megoldások számát.

Feladat: Hány megoldása van az (A → B ) + (C → D ) = 1 egyenletnek? Ahol A, B, C, D logikai változók.

Megoldás: Vezessünk be új változókat: X = A → B és Y = C → D . Az új változókat figyelembe véve az egyenlet a következő formában lesz felírva: X + Y = 1.

A diszjunkció három esetben igaz: (0;1), (1;0) és (1;1), míg X és Y implikáció, azaz három esetben igaz, egyben hamis. Ezért a (0;1) eset a paraméterek három lehetséges kombinációjának felel meg. Eset (1;1) - az eredeti egyenlet paramétereinek kilenc lehetséges kombinációjának felel meg. Ezért ennek az egyenletnek 3+9=15 lehetséges megoldása van.

A logikai egyenletrendszer megoldásainak számának meghatározásának következő módja a − bináris fa. Tekintsük ezt a módszert egy példával.

Feladat: Hány különböző megoldása van a logikai egyenletrendszernek:

Az adott egyenletrendszer ekvivalens a következő egyenlettel:

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

Tegyünk úgy, mintha x 1 igaz, akkor az első egyenletből azt kapjuk x 2 szintén igaz, a másodiktól - x 3 =1, és így tovább, amíg x m= 1. Ez azt jelenti, hogy az (1; 1; …; 1) m egységből álló halmaz a rendszer megoldása. Most engedd x 1 =0, akkor az első egyenletből megvan x 2 =0 vagy x 2 =1.

Amikor x 2 igaz, azt kapjuk, hogy a többi változó is igaz, vagyis a (0; 1; ...; 1) halmaz a rendszer megoldása. Nál nél x 2 =0 ezt kapjuk x 3 =0 vagy x 3 =, és így tovább. Folytatva az utolsó változót, azt kapjuk, hogy az egyenlet megoldásai a következő változóhalmazok (m + 1 megoldás, minden megoldásban m változó érték van):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ezt a megközelítést jól szemlélteti egy bináris fa felépítése. A lehetséges megoldások száma a megépített fa különböző ágainak száma. Könnyen belátható, hogy egyenlő m + 1-gyel.

Érvelési nehézségek esetén niyah és építési demegoldások üvöltése, ezzel kereshet megoldást segítségével igazságtáblázatok, egy vagy két egyenlethez.

Átírjuk az egyenletrendszert a következő formában:

És készítsünk egy igazságtáblázatot külön egy egyenlethez:

Készítsünk igazságtáblázatot két egyenlethez:

Ez az anyag egy előadást tartalmaz, amely az Egységes Informatikai Államvizsga B15 (2015. évi 23. sz.) feladatának logikai egyenletek és logikai egyenletrendszereinek megoldási módszereit mutatja be. Ismeretes, hogy ez a feladat az egyik legnehezebb a vizsgafeladatok közül. Az előadás hasznos lehet a "Logika" témában leckék vezetése során profil osztályok, valamint a vizsga leadására való felkészülés során.

Letöltés:

Előnézet:

A prezentációk előnézetének használatához hozzon létre egy Google-fiókot (fiókot), és jelentkezzen be: https://accounts.google.com

Diák feliratai:

A B15 feladat megoldása (logikai egyenletrendszer) Vishnevskaya M.P., MAOU "Gymnasium No. 3" 2013. november 18., Szaratov

A B15-ös feladat az egyik legnehezebb a számítástechnika vizsgán !!! A készségek ellenőrzése: logikai változókat tartalmazó kifejezések átalakítása; természetes nyelven írja le a logikai változók azon értékkészletét, amelyre a logikai változók adott halmaza igaz; számolja meg az adott feltételeket kielégítő bináris halmazok számát. A legnehezebb, mert erre nincs hivatalos szabály, találgatás szükséges.

Mit ne nélkülözz!

Mit ne nélkülözz!

Konvenciók konjunkció: A /\ B , A  B , AB , А &B, A és B diszjunkció: A \ / B , A + B , A | B , A vagy B tagadása:  A , A, nem A ekvivalens: A  B, A  B, A  B XOR: A  B , A xor B

Változóhelyettesítési módszer Hány különböző x1, x2, ..., x9, x10 logikai változó értékkészlete létezik, amelyek kielégítik az összes alábbi feltételt: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5) ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 A válasznak nem kell felsorolnia az összes különböző x1, x2, …, x9, x10 halmazt, amelyek alatt az adott egyenlőségrendszer teljesül. Válaszként meg kell adnia az ilyen készletek számát (2012-es demóverzió)

Megoldás 1. lépés: Egyszerűsítés változók változtatásával t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Egyszerűsítés után: (t1 \/ t2) /\/ (¬t1 ) t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Tekintsük az egyik egyenletet: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Nyilvánvalóan csak akkor =1, ha az egyik változó 0, a másik pedig 1 Az XOR műveletet a konjunkció és diszjunkció kifejezésére a következő képlet segítségével fejezzük ki: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

2. lépés. A rendszer elemzése .To. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), akkor minden tk érték két x2k-1 és x2k értékpárnak felel meg, például: tk =0 két pár - (0, 1) és (1, 0) , és tk =1 a (0,0) és (1,1) párok.

3. lépés. A megoldások számának számolása. Minden t-nek 2 megoldása van, t száma 5. Így t változókra 2 5 = 32 megoldás létezik. De minden t egy x megoldáspárnak felel meg, azaz. az eredeti rendszernek 2*32 = 64 megoldása van. Válasz: 64

Részleges megoldás eliminációs módszer Hány különböző x1, x2, …, x5, y1,y2,…, y5 logikai változó értékkészlete létezik, amelyek kielégítik az összes alábbi feltételt: (x1→x2)∧(x2→x3)∧ (x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 =1. A válaszhoz nem kell felsorolni az összes különböző x1, x2, ..., x5, y 1, y2, ..., y5 halmazt, amelyek alapján ez az egyenlőségrendszer teljesül. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás. 1. lépés. Az x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 egyenletek szekvenciális megoldása mindegyik következmény igaz. Az implikáció csak egy esetben hamis, amikor 1  0, minden más esetben (0  0, 0  1, 1  1) a művelet 1-et ad vissza. Ezt írjuk fel táblázatba:

1. lépés. Egyenletek szekvenciális megoldása Т.о. 6 megoldáskészlet х1,х2,х3,х4,х5 érkezett: (00000), (00001), (00011), (00111), (01111), (11111). Hasonlóan érvelve arra a következtetésre jutunk, hogy y1, y2, y3, y4, y5 esetén ugyanaz a megoldáshalmaz. Mert ezek az egyenletek függetlenek, azaz. nincsenek bennük közös változók, akkor ennek az egyenletrendszernek a megoldása (a harmadik egyenlet figyelembevétele nélkül) 6 * 6 = 36 "X" és "Y" pár lesz. Tekintsük a harmadik egyenletet: y5→ x5 =1 A párok a megoldások: 0 0 0 1 1 1 A pár nem megoldás: 1 0

Hasonlítsuk össze a kapott megoldásokat, ahol y5 =1, x5=0 nem illik. ilyen pár van 5. A rendszer megoldásainak száma: 36-5= 31. Válasz: 31 Kombinatorika kellett!!!

Dinamikus programozási módszer Hány különböző megoldása van az x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 logikai egyenletnek, ahol x 1, x 2, ..., x 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. lépés. A feltétel elemzése Az egyenlet bal oldalán az implikációs műveletek szekvenciálisan vannak felírva, a prioritás ugyanaz. Írd át: (((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Minden következő változó nem az előzőtől, hanem az előző implikáció eredményétől függ!

2. lépés. A minta feltárása Tekintsük az első implikációt, X 1 → X 2. Igazságtáblázat: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Egy 0-ból 2-t kaptunk, 1-ből pedig kapott egy 0 és egy 1. Csak egy 0 és három 1, ez az első művelet eredménye.

2. lépés. Mintázat feltárása Az első művelet eredményéhez x 3-at kapcsolva a következőt kapjuk: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Két 0-ból két 1-es, mindegyikből 1 (3 van) egy-egy 0 és 1 (3 + 3)

3. lépés: A képlet levezetése Képleteket készíthet az N i nullák és az egyesek számának E i kiszámításához egy i változós egyenlethez: ,

4. lépés Táblázat kitöltése Töltsük ki a táblázatot i = 6-ra balról jobbra, a fenti képletek segítségével számítsuk ki a nullák és egyesek számát; a táblázat azt mutatja, hogyan épül fel a következő oszlop az előző szerint: : változók száma 1 2 3 4 5 6 Nullák száma N i 1 1 3 5 11 21 Egyesek száma E i 1 2*1+1= 3 2 *1+3= 5 11 21 43 Válasz: 43

Logikai kifejezések egyszerűsítését alkalmazó módszer Hány különböző megoldása van az egyenletnek ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 ahol J , K, L, M, N logikai változók? A válasznak nem kell felsorolnia az összes különböző J , K, L, M és N értékkészletet, amelyekre ez az egyenlőség érvényes. Válaszként meg kell adnia az ilyen készletek számát.

Megoldás Figyeljük meg, hogy J → K = ¬ J  K Változóváltozást vezetünk be: J → K=A, M  N  L =B A változás figyelembevételével átírjuk az egyenletet: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Nyilvánvaló, hogy A  B ugyanazok az értékek A és B 6. Tekintsük az utolsó implikációt M → J =1 Ez akkor lehetséges, ha: M=J=0 M=0, J=1 M=J=1

Megoldás A  B , akkor M=J=0-val 1 + K=0-t kapunk. Nincsenek megoldások. M=0, J=1 esetén 0 + K=0, K=0, N és L pedig tetszőleges, 4 megoldást kapunk: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

10. megoldás M=J=1 esetén 0+K=1 *N * L , vagy K=N*L, 4 megoldás: 11. Összesen 4+4=8 megoldása van Válasz: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Információforrások: O.B. Bogomolova, D. Yu. Usenkov. В15: új feladatok és új megoldás // Informatika, 6. sz., 2012, p. 35 – 39. K.Yu. Poljakov. Logikai egyenletek // Informatika, 2011. 14. szám, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronikus forrás]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronikus forrás].

Az óra témája: Logikai egyenletek megoldása

Oktatási - feltételeket teremt a tanulók kognitív érdeklődésének fejlesztéséhez, elősegíti a memória, a figyelem, a logikus gondolkodás fejlődését;

Nevelési : hozzájárul a mások véleményének meghallgatásának képességének neveléséhez, akarat és kitartás nevelése a végső eredmények elérése érdekében.

Az óra típusa: kombinált óra

Felszerelés: számítógép, multimédiás projektor, prezentáció 6.

Az órák alatt

Az alapismeretek ismétlése, aktualizálása. Házi feladat ellenőrzése (10 perc)

Az előző leckéken megismerkedtünk a logika algebra alaptörvényeivel, megtanultuk, hogyan lehet ezeket a törvényeket felhasználni a logikai kifejezések egyszerűsítésére.

Nézzük meg a házi feladatot a logikai kifejezések egyszerűsítéséről:

1. Az alábbi szavak közül melyik felel meg a logikai feltételnek:

(első mássalhangzó → második mássalhangzó)٨ (utolsó betűs magánhangzó → utolsó előtti betű magánhangzó)? Ha több ilyen szó van, jelölje meg közülük a legkisebbet.

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

Bemutatjuk a jelölést:

Az A a mássalhangzó első betűje

A B a mássalhangzó második betűje

S az utolsó magánhangzó

D - utolsó előtti magánhangzó

Tegyünk egy kifejezést:

Készítsünk egy táblázatot:

2. Jelölje meg, hogy melyik logikai kifejezés ekvivalens a kifejezéssel

Egyszerűsítsük az eredeti kifejezés és a javasolt opciók írását:

3. Adott az F kifejezés igazságtáblázatának egy részlete:

Határozzuk meg ezeknek a kifejezéseknek az értékeit az argumentumok megadott értékeihez:

Az óra témájával való ismerkedés, új anyag bemutatása (30 perc)

Folytatjuk a logika alapjainak tanulmányozását és mai leckénk „Logikai egyenletek megoldása” témáját. A téma tanulmányozása után elsajátítja a logikai egyenletek megoldásának alapvető módjait, elsajátítja az egyenletek megoldásának készségeit a logikai algebra nyelvének használatával, valamint képes logikai kifejezést összeállítani az igazságtáblázaton.

1. Oldja meg a logikai egyenletet!

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

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 a következőnek felel meg: K=1, L=1, M=0, N=1.

Megoldás:

Alakítsuk át a kifejezést(¬K  M) → (¬L  M  N)

A kifejezés hamis, ha mindkét kifejezés hamis. A második tag 0, ha M=0, N=0, L=1. Az első tagban K = 0, mivel M = 0, és
.

Válasz: 0100

2. Hány megoldása van az egyenletnek (válaszában csak a számot tüntesse fel)?

Megoldás: a kifejezés átalakítása

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

A+B=1 és C+D=1

2. módszer: igazságtáblázat összeállítása

Alakítsuk át az eredeti kifejezést, nyissuk meg a zárójeleket, hogy megkapjuk a kötőszavak diszjunkcióját:

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

Adjunk hozzá kötőszót a teljes kötőszóhoz (az összes argumentum szorzata), nyissuk meg a zárójeleket:

Tekintsük ugyanazokat a kötőszavakat:

Ennek eredményeként egy 9 kötőszót tartalmazó SDNF-et kapunk. Ezért ennek a függvénynek az igazságtáblázatának értéke 1 a 2 4 =16 változóérték-készletből 9 sorban.

3. Hány megoldása van az egyenletnek (válaszában csak a számot tüntesse fel)?

Egyszerűsítsük a kifejezést:

,

3 út: SDNF építése

Tekintsük ugyanazokat a kötőszavakat:

Ennek eredményeként egy SDNF-et kapunk, amely 5 kötőszót tartalmaz. Ezért ennek a függvénynek az igazságtáblázatának értéke 1 2 4 =16 változóérték-készlet 5 sorában.

Logikai kifejezés felépítése az igazságtáblázat szerint:

az igazságtábla minden 1-et tartalmazó sorára az argumentumok szorzatát állítjuk össze, és a 0-val egyenlő változókat tagadással, az 1-gyel egyenlő változókat pedig tagadás nélkül tartalmazza. A kívánt F kifejezés a kapott termékek összegéből áll. Ezután, ha lehetséges, ezt a kifejezést le kell egyszerűsíteni.

Példa: adott egy kifejezés igazságtáblázata. Építsen fel egy logikai kifejezést.

3. Házi feladat (5 perc)

Oldja meg az egyenletet:

Hány megoldása van az egyenletnek (csak a számra válaszoljon)?

A megadott igazságtáblázat szerint alkosson logikai kifejezést és

egyszerűsítse.