Logikák. Logikai függvények

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:

Mérlegeljük redukciós módszer egy egyenletre . Ez a módszer magában foglalja a logikai egyenletek átalakítását úgy, hogy a jobb oldaluk egyenlő legyen az igazságértékkel (azaz 1-gyel). Ehhez használja a logikai tagadási műveletet. Ezután, ha az egyenletek összetett logikai műveleteket tartalmaznak, azokat alapvető műveletekkel helyettesítjü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 átalakítani, és a rendszerre konkrét megoldást kapni.

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

Képzeljük el a következményt az „OR” és a „NOT” alapvető műveleteken keresztül:

Mivel az egyenletek bal oldala egyenlő 1-gyel, az „ÉS” művelettel összevonhatjuk őket egy egyenletté, amely ekvivalens az eredeti rendszerrel:

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

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

A következő módszer az igazságtáblázatok összeállítása . Mivel a logikai mennyiségeknek 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 egy adott egyenletrendszer teljesül. Ez azt jelenti, hogy egy közös igazságtáblázatot készítünk a rendszer összes egyenletére, és keresünk egy sort a szükséges értékekkel.

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

0	0	1	1	0	1

Az a sor, amelyre a feladat feltételei teljesülnek, félkövérrel vannak kiemelve. Tehát A=0, B=0 és C=1.

Út bomlás . Az ötlet az egyik változó értékének rögzítése (0 vagy 1 értékre állítása), és ezáltal az egyenletek egyszerűsítése. 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 - C = 1. A rendszer megoldása: A = 0, B = 0 és C = 1.

A számítástechnika egységes államvizsgáján nagyon gyakran meg kell határozni egy logikai egyenletrendszer megoldásainak számát, anélkül, hogy maguk a megoldások találnának, erre is vannak bizonyos módszerek. A logikai egyenletrendszer megoldásainak számának megtalálásának fő módja azváltozók cseréje. Először a logikai algebra törvényei alapján lehetőleg egyszerűsíteni kell az egyenleteket, majd az egyenletek összetett részeit új változókkal kell 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 egyenletet a következőképpen írjuk fel: 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 azt jelenti, hogy ennek az egyenletnek az összes lehetséges megoldása 3+9=15.

A logikai egyenletrendszer megoldásainak számának meghatározásának következő módja az bináris fa. Nézzük meg ezt a módszert egy példa segítségével.

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. Hagyja most x 1 =0, akkor az első egyenletből megvan x 2 =0 vagy x 2 =1.

Amikor x 2 igaz, azt kapjuk, hogy a fennmaradó változók is igazak, vagyis a halmaz (0; 1; ...; 1) 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 találjuk, hogy az egyenlet megoldásai a következő változóhalmazok (m +1 megoldás, minden megoldás m változót tartalmaz):

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

	Fa	Megoldások száma
x 1
x 2
x 3
		…

Érvelési nehézségek esetén kutatás és építésmegoldások közül, amelyekkel megoldást kereshet segítségével igazságtáblázatok, egy vagy két egyenlethez.

Írjuk át az egyenletrendszert a következő alakba:

És hozzunk létre egy igazságtáblázatot külön egy egyenlethez:

x 1	x 2	(x 1 → x 2)

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

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

A szolgáltatás célja. Az online számológépet arra tervezték igazságtáblázat felépítése egy logikai kifejezéshez.
Igazságtábla – a bemeneti változók és a hozzájuk tartozó kimeneti értékek összes lehetséges kombinációját tartalmazó táblázat.
Az igazságtáblázat 2n sort tartalmaz, ahol n a bemeneti változók száma, és n+m oszlopok, ahol m a kimeneti változók.

Utasítás. Amikor a billentyűzetről ír be, használja a következő konvenciókat:

Logikai kifejezés:

Köztes táblák származtatása az igazságtáblázathoz
SKNF építése
SDNF építése
A Zhegalkin-polinom felépítése
A Veitch-Karnaugh térkép készítése
Boole-függvény minimalizálása

Például az abc+ab~c+a~bc logikai kifejezést így kell megadni: a*b*c+a*b=c+a=b*c
Adatok logikai diagram formájában történő beviteléhez használja ezt a szolgáltatást.

A logikai függvény bevitelének szabályai

1. A v (disjunkció, VAGY) szimbólum helyett használja a + jelet.
2. Nincs szükség függvényjelölés megadására a logikai függvény előtt. Például az F(x,y)=(x|y)=(x^y) helyett egyszerűen be kell írnia (x|y)=(x^y) .
3. A változók maximális száma 10.

A számítógépes logikai áramkörök tervezését és elemzését a matematika egy speciális ága - a logikai algebra - segítségével végzik. A logika algebrájában három fő logikai függvény különböztethető meg: „NEM” (negáció), „ÉS” (kötőszó), „VAGY” (diszjunkció).
Bármely logikai eszköz létrehozásához meg kell határozni az egyes kimeneti változók függőségét a meglévő bemeneti változóktól, ezt a függőséget kapcsolófüggvénynek vagy logikai algebrai függvénynek nevezzük.
Egy logikai algebrai függvényt teljesen definiáltnak nevezünk, ha mind a 2n értéke adott, ahol n a kimeneti változók száma.
Ha nincs minden érték definiálva, a függvényt részben meghatározottnak nevezzük.
Egy eszközt logikainak nevezünk, ha állapotát logikai algebrai függvény segítségével írjuk le.
A következő módszereket használjuk a logikai algebrai függvények ábrázolására:
Algebrai formában egy logikai eszköz áramkörét építheti fel logikai elemek felhasználásával.


1. ábra - Logikai eszköz diagram

A logikai algebra összes művelete definiált igazságtáblázatokértékeket. Az igazságtábla határozza meg a for művelet eredményét mindenki lehetséges x az eredeti állítások logikai értéke. A műveletek alkalmazásának eredményét tükröző opciók száma a logikai kifejezésben lévő utasítások számától függ. Ha egy logikai kifejezésben az állítások száma N, akkor az igazságtábla 2 N sort fog tartalmazni, mivel a lehetséges argumentumértékeknek 2 N különböző kombinációja van.

Művelet NOT – logikai negáció (inverzió)

A logikai művelet NEM egyetlen argumentumra vonatkozik, amely lehet egyszerű vagy összetett logikai kifejezés. A művelet eredménye NEM a következő:

• ha az eredeti kifejezés igaz, akkor a tagadásának eredménye hamis lesz;
• ha az eredeti kifejezés hamis, akkor a tagadásának eredménye igaz lesz.

A következő konvenciók NEM fogadhatók el a negációs művelethez:
nem A, Ā, nem A, ¬A, !A
A negációs művelet eredményét NEM határozza meg a következő igazságtábla:

A	nem A
0	1
1	0

A tagadási művelet eredménye igaz, ha az eredeti állítás hamis, és fordítva.

VAGY művelet - logikai összeadás (disjunkció, egyesülés)

A logikai VAGY művelet két utasítás kombinálásának funkcióját látja el, amely lehet egyszerű vagy összetett logikai kifejezés. Azokat az állításokat, amelyek a logikai műveletek kiindulópontjai, argumentumoknak nevezzük. A VAGY művelet eredménye egy olyan kifejezés, amely akkor és csak akkor lesz igaz, ha az eredeti kifejezések közül legalább egy igaz.
Használt megnevezések: A vagy B, A V B, A vagy B, A||B.
A VAGY művelet eredményét a következő igazságtáblázat határozza meg:
A VAGY művelet eredménye igaz, ha A igaz, vagy B igaz, vagy A és B is igaz, és hamis, ha az A és B argumentum hamis.

ÉS művelet – logikai szorzás (kötőszó)

Az ÉS logikai művelet két állítás (argumentum) metszéspontjának funkcióját látja el, amely lehet egyszerű vagy összetett logikai kifejezés. Az ÉS művelet eredménye egy olyan kifejezés, amely akkor és csak akkor lesz igaz, ha mindkét eredeti kifejezés igaz.
Használt megnevezések: A és B, A Λ B, A & B, A és B.
Az ÉS művelet eredményét a következő igazságtáblázat határozza meg:

A	B	A és B
0	0	0
0	1	0
1	0	0
1	1	1

Az ÉS művelet eredménye akkor és csak akkor igaz, ha A és B állítások is igazak, és hamis minden más esetben.

„HA-THEN” művelet – logikai következmény (implikáció)

Ez a művelet két egyszerű logikai kifejezést köt össze, amelyek közül az első egy feltétel, a második pedig ennek a feltételnek a következménye.
Használt megnevezések:
ha A, akkor B; A B-t jelent; ha A, akkor B; A→B.
Igazság táblázat:

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

Az implikáció műveletének eredménye csak akkor hamis, ha az A premissza igaz, és a B következtetés (következmény) hamis.

„A akkor és csak akkor, ha B” művelet (ekvivalencia, egyenértékűség)

Használt megnevezés: A ↔ B, A ~ B.
Igazság táblázat:

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

„Addition modulo 2” művelet (XOR, kizárólagos vagy szigorú diszjunkció)

Felhasznált jelölések: A XOR B, A ⊕ B.
Igazság táblázat:

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

Az ekvivalencia művelet eredménye csak akkor igaz, ha A és B egyszerre igaz vagy hamis.

A logikai műveletek prioritása

• Műveletek zárójelben
• Inverzió
• Kötőszó (&)
• Diszjunkció (V), kizárólagos VAGY (XOR), modulo 2. összeg
• Következmény (→)
• Egyenértékűség (↔)

Tökéletes diszjunktív normál forma

A képlet tökéletes diszjunktív normál formája(SDNF) egy ekvivalens képlet, amely elemi kötőszók diszjunkciója, és a következő tulajdonságokkal rendelkezik:

1. A képlet minden logikai tagja tartalmazza az F(x 1,x 2,...x n) függvényben szereplő összes változót.
2. A képlet minden logikai tagja eltérő.
3. Egyetlen logikai kifejezés sem tartalmaz változót és annak tagadását.
4. Egy képletben egyetlen logikai kifejezés sem tartalmazza kétszer ugyanazt a változót.

Az SDNF-t igazságtáblázatokkal vagy azzal egyenértékű transzformációkkal lehet megszerezni.
Minden funkció esetében az SDNF és az SCNF egyedileg van definiálva a permutációig.

Tökéletes konjunktív normál forma

A képlet tökéletes konjunktív normál formája (SCNF) Ez egy vele egyenértékű képlet, amely elemi diszjunkciók konjunkciója, és kielégíti a tulajdonságokat:

1. Minden elemi diszjunkció tartalmazza az F(x 1 ,x 2 ,...x n) függvényben szereplő összes változót.
2. Minden elemi diszjunkció más.
3. Minden elemi diszjunkció egyszer tartalmaz egy változót.
4. Egyetlen elemi diszjunkció sem tartalmaz változót és annak tagadását.

Önkormányzati költségvetési oktatási intézmény

"18. számú középiskola"

városi kerülete a Baskír Köztársaság Salavat városának

Logikai egyenletrendszerek

c. Egységes államvizsga-problémák a számítástechnikában

Az Egységes államvizsga-feladatok „A logikai algebra alapjai” részt az egyik legnehezebben és legnehezebben megoldhatónak tartják. Az ebben a témában elvégzett feladatok átlagos százaléka a legalacsonyabb, 43,2.

Tanfolyam rész	A teljesítések átlagos százalékos aránya feladatcsoportonként
Információk kódolása és mennyiségének mérése
Információs modellezés
Számrendszerek
A logikai algebra alapjai
Algoritmizálás és programozás
Az információs és kommunikációs technológiák alapjai

A 2018-as KIM specifikáció alapján ez a blokk négy különböző nehézségi szintű feladatot tartalmaz.

№ feladatokat	Igazolható tartalmi elemek	Feladat nehézségi szintje
	Képes igazságtáblázatok és logikai áramkörök készítésére
	Képes információ keresni az interneten
	Alapfogalmak és törvényszerűségek ismerete matematikai logika
	Képes logikai kifejezések létrehozására és átalakítására

A 23. feladat magas nehézségi fokú, ezért ennek teljesítése a legalacsonyabb. A felkészült érettségizők (81-100 pont) 49,8%-a, a közepesen (61-80 pont) végzettek 13,7%-a teljesítette a feladatot, a többi hallgatói csoport nem teljesítette a feladatot.

A logikai egyenletrendszer megoldásának sikere a logika törvényeinek ismeretén és a megoldási módszerek pontos alkalmazásán múlik.

Tekintsük egy logikai egyenletrendszer megoldását a leképezési módszerrel.

(23.154 Polyakov K.Yu.) Hány különböző megoldása van az egyenletrendszernek?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

Ahol x1 , x2 ,…, x8, nál nél1 ,y2 ,…,y8 - 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. A rendszerben szereplő összes egyenlet azonos típusú, és minden egyenlet négy változót tartalmaz. Az x1 és y1 ismeretében megtalálhatjuk x2 és y2 összes lehetséges értékét, amely kielégíti az első egyenletet. Hasonlóan okoskodva, az ismert x2 és y2 közül találhatunk x3, y3-at, amely kielégíti a második egyenletet. Vagyis az (x1, y1) pár ismeretében és a pár értékének meghatározásában (x2, y2) megtaláljuk az (x3, y3) párt, ami viszont az (x4, y4) párhoz vezet. stb.

Keressük meg az első egyenlet összes megoldását. Ezt kétféleképpen lehet megtenni: igazságtáblázatot készíteni érveléssel és a logika törvényeinek alkalmazásával.

Igazság táblázat:

				x 1  y 1	x 2  y 2	(x 1  y 1)  (x2  y2)	(x 1  x2)	(y 1  y2)	(x 1  x2)  (y 1  y2)

Az igazságtábla összeállítása munkaigényes és időigénytelen, ezért a második módszert használjuk - a logikai érvelést. A szorzat akkor és csak akkor egyenlő 1-gyel, ha minden tényező egyenlő 1-gyel.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Nézzük az első egyenletet. A következmény egyenlő 1-gyel, ha 0 0, 0 1, 1 1, ami azt jelenti, hogy (x1 y1)=0 (01), (10), akkor a pár (x2  y2 ) bármilyen (00), (01), (10), (11) lehet, és amikor (x1 y1) = 1, azaz (00) és (11) az (x2 y2) = 1 pár felveszi a ugyanazok az értékek (00) és (11). Zárjuk ki ebből a megoldásból azokat a párokat, amelyekre a második és a harmadik egyenlet hamis, azaz x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

Párok összlétszáma 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Hány különböző megoldása van a logikai egyenletrendszernek?

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Megoldás. 1) Az egyenletek azonos típusúak, így okoskodással megtaláljuk az első egyenlet összes lehetséges (x1,y1), (x2,y2) párját.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

A második egyenlet megoldása a (00), (01), (11) párok.

Keressünk megoldásokat az első egyenletre. Ha x1=0, akkor x2, y2 - bármilyen, ha x1=1, akkor x2, y2 veszi fel a (11) értéket.

Hozzunk létre kapcsolatokat az (x1, y1) és (x2, y2) párok között.

(x1 , y1 )	(x2 , y2 )

Hozzon létre egy táblázatot, amely kiszámítja a párok számát az egyes szakaszokban.

							0

Az utolsó egyenlet megoldásait figyelembe véve x 7  y 7 = 1, zárjuk ki a (10) párt. Határozza meg a megoldások teljes számát 1+7+0+34=42!

3)(23.180) Hány különböző megoldása van egy logikai egyenletrendszernek?

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

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

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

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Megoldás. 1) Az egyenletek azonos típusúak, így okoskodással megtaláljuk az első egyenlet összes lehetséges (x1,x2), (x3,x4) párját.

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

Zárjuk ki a megoldásból azokat a párokat, amelyek a sorozatban 0-t (1 0) adnak, ezek a (01, 00, 11) és (10) párok.

Kössünk kapcsolatokat a párok között (x1,x2), (x3,x4)

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

Oktatási – logikai egyenletek megoldási módszereinek tanulmányozása, logikai egyenletek megoldási készségeinek fejlesztése és logikai kifejezés felépítése igazságtáblázat segítségével;

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

Nevelési : elősegíti mások véleményének meghallgatásának képességét, a végső eredmények eléréséhez szükséges akarat és kitartás ápolása.

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 logikai algebra alaptörvényeivel, és megtanultuk ezeket a törvényeket a logikai kifejezések egyszerűsítésére használni.

Nézzük meg házi feladatunkat 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ő betű mássalhangzó → második betű 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

Vezessük be a következő jelölést:

A – első betű mássalhangzó

B – második betű mássalhangzó

S – utolsó betű magánhangzó

D – utolsó előtti magánhangzós betű

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 le az eredeti kifejezés rögzítését és a javasolt opciókat:

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

Melyik kifejezés illik F-re?

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

Bevezetés az óra témájába, új anyag bemutatása (30 perc)

Folytatjuk a logika alapjainak tanulmányozását, és mai leckénk témája a „Logikai egyenletek megoldása”. 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 lesz logikai kifejezést összeállítani igazságtáblázat segítségével.

1. Oldjon meg egy 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 megfelel annak, hogy K=1, L=1, M=0, N=1.

Megoldás:

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

Egy 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 készítése

3 út: SDNF felépítése - tökéletes diszjunktív normálforma egy függvényhez - teljes szabályos elemi kötőszók diszjunkciója.

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=

Egészítsük ki a kötőszavakat teljes kötőszóra (az összes argumentum szorzata), nyissuk meg a zárójeleket:

Vegyük figyelembe 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ázata 1 értéket tartalmaz a 2 4 =16 változóérték-készlet 9 sorában.

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

Vegyük figyelembe 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ázata 1 értéket tartalmaz 2 4 =16 változóérték-készlet 5 sorában.

Logikai kifejezés összeállítása igazságtáblázat segítségével:

az igazságtábla 1-et tartalmazó soraira állítunk össze egy argumentumok szorzatát, és a 0-val egyenlő változók tagadással, az 1-gyel egyenlő változók pedig tagadás nélkül szerepelnek a szorzatban. A kívánt F kifejezés a kapott szorzatok összegéből fog állni. Ezután, ha lehetséges, ezt a kifejezést le kell egyszerűsíteni.

Példa: adott egy kifejezés igazságtáblázata. Alkoss logikai kifejezést.

Megoldás:

3. Házi feladat (5 perc)

Oldja meg az egyenletet:

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

Adott igazságtáblázat segítségével alkoss logikai kifejezést és

egyszerűsítse.

Logikai egyenletrendszerek megoldási módszerei

Kirgizova E.V., Nemkova A.E.

Lesosibirsk Pedagógiai Intézet -

Szibériai Szövetségi Egyetem ága, Oroszország

A következetes gondolkodás, a meggyőző érvelés, a hipotézisek felállítása és a negatív következtetések cáfolatának képessége nem jön létre önmagában, ezt a képességet a logika tudománya fejleszti. A logika olyan tudomány, amely bizonyos állítások igazságának vagy hamisságának megállapítására szolgáló módszereket tanulmányozza más állítások igazsága vagy hamissága alapján.

E tudomány alapjainak elsajátítása lehetetlen logikai problémák megoldása nélkül. A tudás egy új helyzetben történő alkalmazásához szükséges készségek fejlesztésének tesztelése áthaladással történik. Ez különösen a logikai problémák megoldásának képessége. Az egységes államvizsga B15-ös feladatai fokozottan összetett feladatok, mivel logikai egyenletrendszereket tartalmaznak. 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, dekompozíció, egyenletek szekvenciális megoldása stb.

Feladat:Oldjon meg egy logikai egyenletrendszert:

Mérlegeljük redukciós módszer egy egyenletre . Ez a módszer magában foglalja a logikai egyenletek átalakítását úgy, hogy a jobb oldaluk egyenlő legyen az igazságértékkel (azaz 1-gyel). Ehhez használja a logikai tagadási műveletet. Ezután, ha az egyenletek összetett logikai műveleteket tartalmaznak, azokat alapvető műveletekkel helyettesítjü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 átalakítani, és a rendszerre konkrét megoldást kapni.

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

Képzeljük el a következményt az „OR” és a „NOT” alapvető műveleteken keresztül:

Mivel az egyenletek bal oldala egyenlő 1-gyel, az „ÉS” művelettel összevonhatjuk őket egy egyenletté, amely ekvivalens az eredeti rendszerrel:

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

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

A következő módszer az igazságtáblázatok összeállítása . Mivel a logikai mennyiségeknek 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 egy adott egyenletrendszer teljesül. Ez azt jelenti, hogy egy közös igazságtáblázatot készítünk a rendszer összes egyenletére, és keresünk egy sort a szükséges értékekkel.

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

0	0	1	1	0	1

Az a sor, amelyre a feladat feltételei teljesülnek, félkövérrel vannak kiemelve. Tehát A =0, B =0 és C =1.

Út bomlás . Az ötlet az egyik változó értékének rögzítése (0 vagy 1 értékre állítása), és ezáltal az egyenletek egyszerűsítése. Ezután rögzítheti a második változó értékét, és így tovább.

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

Az első egyenletből kapjuk B =0, a másodiktól pedig – C=1. A rendszer megoldása: A = 0, B = 0 és C = 1.

Használhatja a módszert is egyenletek szekvenciális megoldása , minden lépésben hozzáad egy változót a vizsgált halmazhoz. Ehhez az egyenleteket úgy kell átalakítani, hogy a változók ábécé sorrendben legyenek megadva. Ezután létrehozunk egy döntési fát, amelyhez szekvenciálisan változókat adunk.

A rendszer első egyenlete csak A-tól és B-től, a második egyenlete A-tól és C-től függ. Az A változó 2 0 és 1 értéket vehet fel:

Az első egyenletből az következik , így amikor A = 0 és B = 0, A = 1 esetén pedig B = 1. Tehát az első egyenletnek két megoldása van az A és B változókra vonatkozóan.

Ábrázoljuk a második egyenletet, amelyből minden opcióhoz meghatározzuk C értékeit. Ha A =1, az implikáció nem lehet hamis, vagyis a fa második ágának nincs megoldása. Nál nél A= 0 mi kapjuk az egyetlen megoldást C= 1 :

Így megkaptuk a rendszer megoldását: A = 0, B = 0 és C = 1.

A számítástechnika egységes államvizsgáján nagyon gyakran meg kell határozni egy logikai egyenletrendszer megoldásainak számát, anélkül, hogy maguk a megoldások találnának, erre is vannak bizonyos módszerek. A logikai egyenletrendszer megoldásainak számának megtalálásának fő módja az változók cseréje. Először a logikai algebra törvényei alapján lehetőleg egyszerűsíteni kell az egyenleteket, majd az egyenletek összetett részeit új változókkal kell 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 egyenletnek ( A → B ) + (C → D ) = 1? 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őképpen 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 azt jelenti, hogy ennek az egyenletnek az összes lehetséges megoldása 3+9=15.

A logikai egyenletrendszer megoldásainak számának meghatározásának következő módja az bináris fa. Nézzük meg ezt a módszert egy példa segítségével.

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, minthax 1 – igaz, akkor az első egyenletből azt kapjukx 2 szintén igaz, a másodiktól -x 3 =1, és így tovább, amíg x m= 1. Tehát az (1; 1; …; 1) halmaza m egységek a rendszer megoldása. Hagyja mostx 1 =0, akkor az első egyenletből megvanx 2 =0 vagy x 2 =1.

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

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

Változók	Fa	Megoldások száma
x 1
x 2
x 3

Ha az érvelés és a döntési fa felépítése nehézségekbe ütközik, a segítségével kereshet megoldást igazságtáblázatok, egy vagy két egyenlethez.

Írjuk át az egyenletrendszert a következő alakba:

És hozzunk létre egy igazságtáblázatot külön egy egyenlethez:

x 1	x 2	(x 1 → x 2)

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

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

Ezután láthatja, hogy egy egyenlet a következő három esetben igaz: (0; 0), (0; 1), (1; 1). A két egyenletrendszer négy esetben igaz (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Ebben az esetben azonnal világos, hogy van olyan megoldás, amely csak nullákból és többből áll m megoldások, amelyekben egy-egy egységet adnak hozzá, az utolsó pozíciótól kezdve az összes lehetséges hely betöltéséig. Feltételezhető, hogy az általános megoldásnak ugyanaz lesz a formája, de ahhoz, hogy egy ilyen megközelítés megoldássá váljon, bizonyítani kell, hogy a feltételezés helyes.

Összefoglalva a fentieket, szeretném felhívni a figyelmet arra, hogy nem minden tárgyalt módszer univerzális. Az egyes logikai egyenletrendszerek megoldásánál figyelembe kell venni azok jellemzőit, amelyek alapján a megoldási módot kell kiválasztani.

Irodalom:

1. Logikai problémák / O.B. Bogomolov – 2. kiadás. – M.: BINOM. Tudáslaboratórium, 2006. – 271 p.: ill.

2. Polyakov K. Yu. Logikai egyenletrendszerek / Oktatási és módszertani újság számítástechnika tanároknak: Informatika 2011. 14. sz.