18. feladat számítástechnikából
Ismeretes, hogy a kifejezés
((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))
igaz (azaz 1 értéket vesz fel) az x változó bármely értékére. Határozzuk meg az A halmaz elemeinek lehető legnagyobb számát!
Megoldás.
Bemutatjuk a jelölést:
(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ ; ∨ ≡ +.
Ezután az implikációs transzformációt alkalmazva kapjuk:
(¬A + P) (¬Q + ¬A) ⇔ ¬A ¬Q + ¬Q P + ¬A + ¬A P ⇔
⇔ ¬A (¬Q + P + 1) + ¬Q P ⇔ ¬A + ¬Q P.
Szükséges, hogy ¬A + ¬Q · P = 1. A ¬Q · P kifejezés igaz, ha x ∈ (2, 4, 8, 10, 14, 16, 20). Ekkor ¬A-nak igaznak kell lennie, ha x ∈ (1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...).
Ezért az A halmaz elemeinek maximális száma akkor lesz, ha A tartalmazza a ¬Q · P halmaz összes elemét, hét ilyen elem van.
Válasz: 7.
Válasz: 7
Az A halmaz elemei természetes számok. Ismeretes, hogy a kifejezés
(x (2, 4, 6, 8, 10, 12)) → (((x (3, 6, 9, 12, 15)) ∧ ¬(x A)) → ¬(x (2, 4, 6) , 8, 10, 12)))
Megoldás.
Bemutatjuk a jelölést:
(x ∈ (2, 4, 6, 8, 10, 12)) ≡ P; (x ∈ (3, 6, 9, 12, 15)) ≡ Q; (x ∈ A) ≡ A.
Átalakítva a következőket kapjuk:
P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ ¬Q ∨ A.
A logikai VAGY igaz, ha legalább az egyik állítás igaz. A ¬P ∨ ¬Q kifejezés igaz x minden értékére, kivéve a 6 és 12 értékeket. Ezért az A intervallumnak tartalmaznia kell a 6 és 12 pontokat. A ≡ (6, 12). Az A halmaz elemeinek összege 18.
Válasz: 18.
Válasz: 18
Az A, P, Q halmazok elemei természetes számok, és P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).
Ismeretes, hogy a kifejezés
igaz (azaz az 1 értéket veszi fel) az x változó bármely értékére. Határozzuk meg az A halmaz elemeinek összegének lehető legkisebb értékét!
Megoldás.
Egyszerűsítsünk:
¬(x P) ∨ ¬(x Q) csak akkor ad 0-t, ha a szám mindkét halmazban van. Ez azt jelenti, hogy ahhoz, hogy az egész kifejezés igaz legyen, az összes P-ben és Q-ban lévő számot el kell helyeznünk A-ban. Ilyen számok: 6, 12, 18. Összegük 36.
Válasz: 36.
Válasz: 36
Forrás: Képzési munka INFORMATIKA 11. évfolyamon 2017. január 18. IN10304 opció
Az A, P, Q halmazok elemei természetes számok, és P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).
Ismeretes, hogy az ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A)) kifejezés
igaz (azaz az 1 értéket veszi fel) az x változó bármely értékére.
Határozzuk meg az A halmaz elemeinek lehető legnagyobb számát!
Megoldás.
Alakítsuk át ezt a kifejezést:
((x A) → (x P)) ∨ ((x Q) → (x A))
((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))
(x A) ∨ (x P) ∨ (x Q)
Így egy elemnek vagy szerepelnie kell P-ben vagy Q-ban, vagy nem szerepelnie kell az A-ban. Így csak P és Q elemei lehetnek A-ban. És ebben a két halmazban 17 nem ismétlődő elem van.
Válasz: 17
Az A, P, Q halmazok elemei természetes számok, és P = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30). Ismeretes, hogy a kifejezés
((x P) → (x A)) ∨ (¬(x A) → ¬(x Q))
igaz (azaz az 1 értéket veszi fel) az x változó bármely értékére. Határozzuk meg az A halmaz elemeinek összegének lehető legkisebb értékét!
Megoldás.
Vizsgáljuk meg két következményét. Kapunk:
(¬(x P) ∨ (x A)) ∨ ((x A) ∨ ¬(x Q))
Egyszerűsítsünk:
(¬(x P) ∨ (x A) ∨ ¬(x Q))
¬(x P) ∨ ¬(x Q) csak akkor ad 0-t, ha a szám mindkét halmazban van. Ez azt jelenti, hogy ahhoz, hogy az egész kifejezés igaz legyen, a P-ben és Q-ban szereplő összes számot A-ba kell tenni. Ilyen számok a 3, 9, 15 és 21. Összegük 48.
Válasz: 48.
Válasz: 48
Forrás: Képzési munka INFORMATIKA 11. évfolyamon 2017. január 18. IN10303 opció
És a kifejezés
(y + 2x30) ∨ (y > 20)
x és y?
Megoldás.
Vegye figyelembe, hogy ennek a kifejezésnek az azonos igazságához a kifejezés (y + 2x Válasz: 81.
Válasz: 81
Forrás: USE - 2018. Korai hullám. 1. lehetőség, HASZNÁLAT - 2018. Korai hullám. 2. lehetőség.
A számegyenesen egy A szakasz van megadva. Ismeretes, hogy a képlet
((x ∈ A) → (x2 ≤ 100)) ∧ ((x2 ≤ 64) → (x ∈ A))
ugyanúgy igaz minden valódira x. Mekkora az A szakasz legrövidebb hossza?
Megoldás.
Kibővítve az implikációt az A → B = ¬A + B szabály szerint, a logikai összeget egy halmazzal, a logikai szorzatot pedig egy összefüggésrendszerrel helyettesítve meghatározzuk a paraméter értékeit. A, amely alapján a gyűjtések rendszere
bármilyen valós számra lesz megoldása.
Ahhoz, hogy a rendszer megoldásai mind valós számok legyenek, szükséges és elegendő, hogy az egyes gyűjtemények megoldásai mind valós számok legyenek.
Az egyenlőtlenség megoldásai mind a [−10; 10]. Annak érdekében, hogy a gyűjtemény minden valós számra érvényes legyen, a számok x, amelyek nem a megadott szakaszon fekszenek, az A szegmenshez kell tartozniuk. Ezért az A szegmens nem haladhatja meg a [−10; 10].
Hasonlóképpen az egyenlőtlenség megoldásai a sugarakból származó számok és Ahhoz, hogy a halmaz minden valós számra teljesüljön, a számok x, amely nem fekszik a jelzett sugarakon, az A szakaszon kell feküdnie. Ezért az A szakasznak tartalmaznia kell a [−8; 8].
Így az A szakasz legkisebb hossza 8 + 8 = 16 lehet.
Válasz: 16.
Válasz: 16
A kifejezés
(y + 2x ≠ 48) ∨ (A x) ∨ ( x y)
ugyanúgy igaz, azaz bármely nem negatív egész számhoz 1 értéket vesz fel xÉs y?
Megoldás.
A xÉs y, fontolja meg, hogy milyen esetekben a feltételek ( y + 2x≠ 48) és ( x y) hamisak.
y = 48 − 2x) és (x ≥ y). Ez x 16 és 24 között y 0 és 16 közötti tartományban. Vegyük észre, hogy ahhoz, hogy a kifejezés alkalmas legyen bármely xÉs y, kötelező venni x= 16 és y= 16. Akkor A Egy akarat egyenlő 15-tel.
Válasz: 15.
Válasz: 15
Forrás: USE az Informatikában 2018.05.28. A fő hullám, A. Imaev variánsa - "Kotolis".
Mi a legnagyobb nemnegatív egész szám A kifejezés
(y + 2x ≠ 48) ∨ (A x) ∨ ( A y)
ugyanúgy igaz, azaz bármely nem negatív egész számhoz 1 értéket vesz fel xÉs y?
Megoldás.
A legnagyobb nemnegatív egész szám megtalálása A, amelynél a kifejezés lesz xÉs y, fontolja meg, hogy mely esetekben a feltétel ( y + 2x≠ 48) hamis.
Így minden megoldást megtalálunk, amikor ( y = 48 − 2x). Ez x 0 és 24 között y 48 és 0 közötti tartományban. Vegyük észre, hogy ahhoz, hogy a kifejezés alkalmas legyen bármely xÉs y, kötelező venni x= 16 és y= 16. Akkor A Egy akarat egyenlő 15-tel.
Válasz: 15.
Válasz: 15
Forrás: A USE-2019 demóverziója az informatikában.
Mi a legkisebb nemnegatív egész szám A kifejezés
(2x + 3y > 30) ∨ (x + y ≤ A)
ugyanúgy igaz minden nem negatív egész számra xÉs y?
Megoldás.
A, amely alatt a kifejezés azonosan igaz lesz bármely nem negatív egész számra xÉs yy + 2x> 30) hamis.
y + 2x≤ 30). Ez x 0-tól 15-ig és y 10-től 0-ig terjedő tartományban. Vegye figyelembe, hogy ahhoz, hogy a kifejezés alkalmas legyen bármely xÉs y, kötelező venni x= 15 és y= 0. Akkor 15 + 0 ≤ A. Ezért a legkisebb egész szám, nem negatív szám A 15 lesz.
Válasz: 15.
Válasz: 15
Mi a legnagyobb nemnegatív egész szám A kifejezés
(2x + 3y x + y ≥ A)
ugyanúgy igaz minden nem negatív egész számra xÉs y?
Megoldás.
A legnagyobb nemnegatív egész szám megtalálása A, amely alatt a kifejezés azonosan igaz lesz bármely nem negatív egész számra xÉs y, fontolja meg, mely esetekben a feltétel (3 y + 2xÍgy minden megoldást megtalálunk, amikor (3 y + 2x≥ 30). Ez x 15 év felett és y nagyobb, mint 10. Vegyük észre, hogy ahhoz, hogy a kifejezés alkalmas legyen bármely xÉs y, kötelező venni x= 0 és y= 10. Akkor 0 + 10 ≤ A. Ezért a legnagyobb nemnegatív egész szám A egyenlő lesz 10.
Válasz: 10.
Válasz: 10
Mi a legkisebb nemnegatív egész szám A kifejezés
(3x + 4y ≠ 70) ∨ (A > x) ∨ (A > y)
ugyanúgy igaz minden nem negatív egész számra xÉs y?
Megoldás.
A legkisebb, nem negatív egész szám megtalálása A, amely alatt a kifejezés azonosan igaz lesz bármely nem negatív egész számra xÉs y, fontolja meg, mely esetekben a feltétel (3 x + 4y≠ 70) hamis.
Így minden megoldást megtalálunk, amikor (3 x + 4y= 70). Ez x 2 és 22 között y 16-tól 1-ig terjedő tartományban. Vegye figyelembe, hogy ahhoz, hogy a kifejezés alkalmas legyen bármely xÉs y, kötelező venni x= 10 és y= 10. Akkor A> 10. Ezért a legkisebb nemnegatív egész szám A egyenlő lesz a 11.
18. feladat Munkakönyvtár. Logikai kijelentések
1. 18. feladat 701. sz. Melyik névre hamis az állítás:
(A név első betűje magánhangzó→ A név negyedik betűje mássalhangzó).
1) ELENA
2) VADIM
3) ANTON
4) FEDOR
Magyarázat.
Az implikáció akkor és csak akkor hamis, ha az előfeltevés igaz, a következmény pedig hamis. Esetünkben, ha a név első betűje magánhangzó, a negyedik betű pedig magánhangzó. Az Anton név eleget tesz ennek a feltételnek.
Jegyzet.
Ugyanez az eredmény következik a következő transzformációkból: ¬ (A→ B) = ¬(¬A∨ B)=A∧ (¬B).
A helyes válasz a 3.
2. 18. feladat 8666. sz. Két szegmens van megadva a számegyenesen: P = és Q = . Adja meg az A intervallum lehető legnagyobb hosszát, amelyre a képlet
(¬ (xA)→ (xP))→ ((xA)→ (xK))
azonosan igaz, azaz az x változó bármely értékére 1 értéket vesz fel.
Magyarázat.
Alakítsuk át ezt a kifejezést:
(¬ ( xA) → ( x P)) → (( x A) → ( xK))
((xA)∨ (x P))→ ((x Nem A)∨ (x K))
¬(( xtulajdonában vanA) ∨ ( xtulajdonában vanP)) ∨ (( x nem birtokoltA) ∨ ( x tulajdonában vanK))
( xnem birtokoltA) ∧ ( xnem birtokoltP) ∨ ( x tulajdonában vanA) ∨ ( x nem birtokoltK)
( xnem birtokoltA) ∨ ( x tulajdonában vanK)
Tehát x-nek vagy Q-hoz kell tartoznia, vagy nem tartozik A-hoz. Ez azt jelenti, hogy ahhoz, hogy minden x-re igaz legyen, szükséges, hogy A-t teljesen tartalmazza Q. Ekkor a maximum, amivé válhat, a Q egésze, vagyis 15 hosszúságú.
3. 18. feladat 9170. sz. Két szegmens van megadva a számegyenesen: P = és Q = .
Adja meg az A szegmens lehető legnagyobb hosszát, amelyre a képlet
((xA)→ ¬(xP))→ ((xA)→ (xK))
azonosan igaz, azaz a változó bármely értékére 1-et vesz felx .
Magyarázat.
Alakítsuk át ezt a kifejezést.
(( x€ A) → ¬( xtulajdonában vanP)) → (( x tulajdonában vanA) → ( x tulajdonában vanK))
(( xnem birtokoltA) ∨ ( xnem birtokoltP)) → (( x nem birtokoltA) ∨ ( x tulajdonában vanK))
¬((x nem tartozik A-hoz)∨ (xnem tartozik a P-hez))∨ ((xnem tartozik A-hoz)∨ (xQ-hoz tartozik))
Igaz, hogy A∧ B∨ ¬A = ¬A∨ B. Ezt itt alkalmazva a következőket kapjuk:
(x P-hez tartozik)∨ (xnem tartozik A-hoz)∨ (x a Q-hoz tartozik)
Vagyis a pontnak vagy Q-hoz kell tartoznia, vagy P-hez kell tartoznia, vagy nem A-hoz. Ez azt jelenti, hogy A lefedheti az összes olyan pontot, amely lefedi P-t és Q-t. Vagyis A = P Q = = . |A| = 48 - 10 = 38.
4. 18. feladat 9202. sz. Az A, P, Q halmazok elemei természetes számok, és P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).
Ismeretes, hogy a kifejezés
((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))
igaz (azaz az 1 értéket veszi fel) az x változó bármely értékére.
5. 18. feladat 9310. sz. Az A, P, Q halmazok elemei természetes számok, és P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (5, 10, 15, 20, 25, 30, 35, 40, 45, 50).
Ismeretes, hogy a kifejezés
((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))
igaz (azaz 1 értéket vesz fel) az x változó bármely értékére.
Határozzuk meg az A halmaz elemeinek lehető legnagyobb számát!
6. 18. feladat 9321. sz. JelöljeDEL ( n, m ) „egy n természetes szám maradék nélkül osztható természetes számmalm ". Hogy mi a legnagyobb természetes számA képlet
¬ DEL ( x, A ) → (¬ DEL ( x , 21) ∧ ¬ DEL ( x , 35))
azonosan igaz (vagyis a változó bármely természetes értékére 1-et vesz felx )?
(M. V. Kuznyecovához való megbízás)
7. 18. feladat 9768. sz. Jelölje m & n m És n 2 & 0101 2 = 0100 2 A képlet
x & 29 ≠ 0 → (x & 12 = 0 → x & A ≠ 0)
azonosan igaz (azaz 1 értéket vesz fel a változó bármely nem negatív egész értékére x )?
8. 18. feladat 9804 sz. Jelölje m & n nemnegatív egész számok bitenkénti kötőszava m És n . Tehát például 14 és 5 = 1110 2 & 0101 2 = 0100 2 = 4. Mi a legkisebb nemnegatív egész szám A képlet
x & 29 ≠ 0 → (x & 17 = 0 → x & A ≠ 0)
azonosan igaz (azaz 1 értéket vesz fel a változó bármely nem negatív egész értékére x )?
9. 18. feladat 723. sz. Melyik névre igaz az állítás:
A harmadik betű egy magánhangzó→ ¬ (Az első betű mássalhangzó \/ 4 magánhangzó van a szóban)?
1) Rimma
2) Anatolij
3) Szvetlana
4) Dmitrij
Magyarázat.
Alkalmazzuk az implikációs transzformációt:
Harmadik betű Mássalhangzó∨ (Az első betű magánhangzó∧ A NEM szónak 4 magánhangzója van)
A diszjunkció akkor igaz, ha az állítások közül legalább egy igaz. Ezért csak az 1. lehetőség megfelelő.
10. 18. feladat 4581. sz. Az alábbi nevek közül melyik felel meg a logikai feltételnek:
(első betű mássalhangzó→ az utolsó betű mássalhangzó) /\ (az első betű magánhangzó→ az utolsó betű magánhangzó)
Ha több ilyen szó van, jelölje meg közülük a leghosszabbat.
1) ANNA
2) BELLA
3) ANTON
4) BORIS
Magyarázat.
A logikai ÉS csak akkor igaz, ha mindkét állítás igaz.(1)
Egy következtetés csak akkor hamis, ha az igazságból hamis következik.(2)
Az 1. lehetőség minden körülményre alkalmas.
A 2. lehetőség a (2) feltétel miatt nem megfelelő.
A 3. lehetőség a (2) feltétel miatt nem megfelelő.
A 4. lehetőség minden körülményre alkalmas.
Meg kell adnia a leghosszabb szót, ezért a válasz 4.
Önálló megoldási feladatok
1. 18. feladat 711. sz. A következő országnevek közül melyik felel meg a következő logikai feltételnek: ((utolsó mássalhangzó) \/ (első mássalhangzó))→ (a név tartalmazza a "p" betűt)?
1) Brazília
2) Mexikó
3) Argentína
4) Kuba
2. 18. feladat 709. sz. Az alábbi nevek közül melyik felel meg a logikai feltételnek:
(Az első betű egy magánhangzó)∧ ((Negyedik betű mássalhangzó)∨ (Négy betű van a szóban))?
1) Szergej
2) Vadim
3) Anton
4) Ilja
№3
№4 
№5. 18. feladat 736. sz. A megadott nevek közül melyik felel meg a logikai feltételnek
Az első betű egy magánhangzó∧ negyedik mássalhangzó∨ A szónak négy betűje van?
1) Szergej
2) Vadim
3) Anton
4) Ilja
Belova T.V.
hogyan tanítsunk megoldani 18. feladat vizsgát számítástechnikából
"Líceum" önkormányzati költségvetési oktatási intézmény,
Arzamas, igen. bellova. tatyana@ yandex. hu
Mielőtt folytatnánk a számítástechnikai vizsgadolgozat 18. „Egy logikai kifejezés igazságának ellenőrzése” feladat megoldását, el kell magyarázni (vagy emlékezni) a hallgatóknak, hogy mit jelent a több halmaz „egyesülése” és „metszéspontja” fogalma. van. És mivel a 18. feladat a szegmensek meghatározásához kapcsolódik, a legjobb ezeket a fogalmakat szegmensekben magyarázni. De ezeket a fogalmakat össze kell kapcsolni a logikai algebra fogalmaival - "konjunkció" és "diszjunkció", és természetesen "inverzió". Mindezt egy példával mutatom be. Kezdésként vegyük figyelembe egy szegmens megfordítását, vagy egyszerűbben egy szegmens tagadását.
A P= szegmens adott. Keresse meg azokat a szakaszokat, amelyek a P= szegmens inverzióját jelentik. Tekintsük a koordináta egyenest (1. ábra):
rizs. 1
Az egyenes vonalon jelöljük meg a P szakaszt (kék terület), akkor egyértelmű, hogy a rések nem P lesznek hézagok és (zöld terület) - ábra. 1. Ügyelve arra, hogy a 6. és 15. pont nem kerül bele a szakasz megfordításába.
Tekintsünk egy másik példát: két P= és Q= szegmens van megadva (ugyanazok a jelölések, mint az USE feladatban, hogy a tanulók azonnal hozzászokjanak a jelölésekhez). Keressen egy szakaszt, amely jelöli ezeknek a szegmenseknek a konjunkcióját (egyesülését) és diszjunkcióját (metszéspontját)
A koordináta egyenesre szakaszokat rajzolunk (2. ábra):
rizs. 2
Először a koordinátavonalon jelöljük meg azokat a területeket, amelyek a P (kék) és Q (sárga) szakaszokat jelzik. Ezután meghatározzuk, hogy a koordinátaegyenes melyik része szolgál e két szakasz konjunkciójaként. Itt felidézzük, hogy a konjunkció egy logikai művelet, amely két egyszerű állítást egy komplexté kombinál a logikai „és” kapcsoló segítségével, és az összetett állítás akkor és csak akkor kapja meg az „igaz” értéket, ha mindkét eredeti egyszerű állítás igaz. Így azt kapjuk, hogy meg kell találnunk azokat a területeket, ahol mind a P szegmens, mind a Q szegmens található, és csak egy ilyen régió van - a szegmens (piros szín). Részletesebben megvizsgáljuk az egyenes minden szakaszát, hogy a tanulók tisztábban és érthetőbben érzékelhessék az anyagot, tehát:
Most hasonló módon foglalkozunk e szegmensek diszjunkciójával. Ismét térjünk rá ennek a logikai műveletnek a definíciójára - „a diszjunkció olyan logikai művelet, amely két vagy több logikai állításnak megfelelően egy újat tesz, amely akkor és csak akkor igaz, ha a bemeneti kezdeti utasítások közül legalább az egyik igaz." Vagyis olyan hézagokat kell találnunk a koordináta egyenesen, ahol legalább egy eredeti szakaszunk van, ez a kívánt rés zöld lesz (2. ábra). Ezenkívül elemezzük az egyes intervallumokat, és megmutatjuk, hogy ez valóban így van:
A talált hézagokat kombinálva azt kapjuk, hogy a kívánt szegmens, amely az eredeti szegmensek diszjunkcióját jelöli, egy szegmens - zöld (2. ábra).
A példa elemzése után a tanulók megpróbálhatják megtalálni a logikai műveletek különféle kombinációit – diszjunkciót, konjunkciót és tagadást. Például adott két szegmens: P=[-4,10] és Q=. Keressen egy szegmenst, amely a következő logikai műveleteket jelöli: , , (e logikai műveletek más különböző kombinációira is gondolhat).
rizs. 3
rizs. 4
rizs. 5
Az összes példa elemzése után nem okoz nehézséget a tanulóknak az egységes informatika államvizsga vizsgadolgozatának 18. számú feladatának megértése és megoldása.
Íme néhány feladat megoldási példái:
Két szegmens van megadva a számegyenesen: P = és Q =. Válasszon egy A szegmenst úgy, hogy a képlet
(x A) → ((x P) → (x K)) azonosan igaz, azaz a változó bármely értékére 1-et vesz fel x. Lehetséges válaszok:
1) 2) 3) 4)
Megoldás (6. ábra): a kifejezés megértésének egyszerűsítése érdekében az egyes állításokat betűkkel jelöljük - A: x A,P: x P,K: x K.Így a következő kifejezést kapjuk, figyelembe véve a helyettesítést: → ( P→ )=1. Az 1-es kifejezés egyenlősége azt mondja, hogy a változó bármely értéke x nem vettük, logikai kifejezésünk az 1 értéket veszi fel, vagyis a teljes számegyenesen. Idézzünk fel néhány logikai törvényt és egyenlőséget, és alakítsuk át a kifejezésünket: =1. Ennek eredményeként azt kapjuk, hogy három szegmens diszjunkcióját kell megszerkesztenünk, amelyek közül kettőt ismerünk. Megépítjük őket (7. ábra). Először is, mint az összes fenti példában, meg kell építeni a P (narancssárga) és Q (piros) szegmensek inverzióit. Ekkor a teljes kifejezésből meghatározhatjuk a diszjunkciós intervallumokat =1 (zöld területek a 7. ábrán). Így azt kapjuk, hogy van egy „szabad” részünk a - koordinátaegyenesen. Ez a rész egyenes, és át kell fednie a kívánt szegmenst A.
A probléma megoldásához néhány logikus következtetést kell levonnunk, ezért "figyelje a kezét".
- Azt akarják, hogy megtaláljuk azt a minimális, nem negatív A egész számot, amelyre a kifejezés mindig igaz.
- Mi a kifejezés egésze? ott valami következmény valami zárójelben.
- Emlékezzünk vissza az igazságtáblázatra a következményhez:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1 - Tehát három lehetőség van, amikor ez igaz lesz. Ha ezt a három lehetőséget mérlegeljük, akkor megöljük magunkat, és nem élünk. Gondolkodjunk el azon, hogy el tudunk-e menni "az ellenkezőjéről".
- Ahelyett, hogy A-t keresnénk, próbáljuk meg megkeresni azt az x-et, amelyre ez a kifejezés hamis.
- Vagyis vegyünk egy A számot (még nem tudjuk, mit, csak néhányat). Ha hirtelen olyan x-et találunk, amelyre az egész állítás hamis, akkor a választott A rossz (mert a feltétel megköveteli, hogy a kifejezés mindig igaz legyen)!
- Így az A számra valamilyen korlátozást kaphatunk.
- Tehát menjünk el az ellenkezőjéről, és ne feledjük, mikor hamis a következtetés? Amikor az első rész igaz és a második rész hamis.
- Eszközök
\((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Jobbra \mathrm(x)\&\mathrm(A)\neq 0) = 0\) - Mit jelent, hogy \((x\&25\neq 0) = 1\) ? Ez azt jelenti, hogy valóban \(\mathrm(x)\&25\neq 0\) .
- Alakítsuk át a 25-öt binárisra. A következőt kapjuk: 11001 2 .
- Milyen korlátozásokat jelent ez x-re? Mivel nem egyenlő nullával, ez azt jelenti, hogy bitenkénti kötőszóval valahol egy egységet kell szerezni. De hol lehet? Csak ott, ahol már van egység 25-ben!
- Ez azt jelenti, hogy az x számban legalább egy keresztnek tartalmaznia kell egy egységet: XXX.
- Rendben, most fontolja meg a második szorzót: \((\mathrm(x)\&17=0\Jobbra \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
- Ez a kifejezés is egy következmény. Ez azonban ugyanolyan hamis.
- Ezért az első részének igaznak, a másodiknak pedig hamisnak kell lennie.
- Eszközök
\((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\) - Mit jelent a \(\mathrm(x)\&17=0\)? Az, hogy minden helyen, ahol 17-ben egyesek vannak, x-ben nulláknak kell lenniük (különben nem lesz 0 az eredmény).
- Alakítsuk át a 17-et binárissá: 10001 2 . Ez azt jelenti, hogy x-ben a végétől az utolsó helyen és a végétől az 5. helyen nulláknak kell lenniük.
- De állj meg, a 13. bekezdésben az utolsóhoz jutottunk VAGY 4 a végétől VAGY 5 a végétől egy legyen.
- Mivel a 19. sor szerint nem lehet egység az utolsó vagy a véghelyek 5-én, ezért kell, hogy legyen 4. hely a végétől.
- Vagyis ha azt akarjuk, hogy az egész kifejezés hamis legyen az x-ünkkel, akkor a végétől számított 4. helynek egynek kell lennie: XX...XX1XXX 2 .
- Rendben, most nézzük az utolsó feltételt: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Mit is jelent ez?
- Ez azt jelenti, hogy ez nem igaz \(\mathrm(x)\&\mathrm(A)\neq 0\).
- Ez valójában \(\mathrm(x)\&\mathrm(A)=0\) .
- Mit tudunk az x-ről? Hogy a hely végétől 4-re van egy egység. Minden más tekintetben x szinte bármi lehet.
- Ha azt akarjuk, hogy a problémafelvetésben szereplő eredeti kifejezés mindig igaz legyen, akkor mi nem szabad megtalálni x, amely minden feltételt kielégít. Hiszen valóban, ha találnánk egy ilyen x-et, akkor kiderülne, hogy az eredeti kifejezés nem mindig igaz, ami ellentmond a probléma feltételének.
- Ez azt jelenti, hogy ennek az utolsó feltételnek egyszerűen nem szabad teljesülnie.
- Hogy nem lehet megtenni? Ha csak 100%-ig biztosak vagyunk abban, hogy bitenkénti kötőszóval egy egység valahol megmarad.
- És ez lehetséges: ha A-ban a végétől a 4. helyen is van egy egység, akkor bitenkénti kötőszó hatására a végétől a 4. helyen marad egy egység.
- Mi az a legkisebb lehetséges bináris szám, amelynek a hely végétől 1-szer 4 van? Nyilvánvalóan 1000 2 . Tehát ez a szám lesz a válasz.
- Csak decimálisra kell konvertálni: \(1000_2=0\szer 2^0 + 0\szor 2^1 + 0\szor 2^2 + 1\szer 2^3=8\)
Válasz: a lehető legkisebb A, amely megfelel a feltételeknek, egyenlő 8.
Jevgenyij Szmirnov
Informatika szakértő, számítástechnika tanár
2. megoldás
Valamivel rövidebb megközelítés javasolható. Jelöljük kijelentésünket F = (A->(B->C)), ahol A az "X&25 nem egyenlő 0-val", B= "X&17=0" és C="X&A nem egyenlő 0-val ".
Bővítsük ki az implikációkat a jól ismert X->Y = nem(X) VAGY Y törvény segítségével, megkapjuk F = A -> (not(B) VAGY C) = not(A) VAGY nem(B) VAGY C A 25 és 17 konstansok bináris értékeit is felírjuk:
Kifejezésünk három állítás logikai VAGY:
1) not(A) - ez azt jelenti, hogy X&25 = 0 (X 0,3,4 bitjei mind 0)
2) nem(B) - tehát X&17 nem egyenlő 0-val (X 0 és 4 bitje legalább egy egyenlő 1-gyel)
3) C - tudja, hogy X&A nem egyenlő 0-val (az A maszk által beállított bitek, legalább 1 egyenlő 1-gyel)
X egy tetszőleges szám. Minden bitje független. Ezért egy tetszőleges szám bitjein csak egyetlen esetben lehet követelni valamilyen feltétel teljesítését - ha ugyanarról a maszkról (bitkészletről) van szó. Észrevehetjük, hogy a 17-es bináris maszk majdnem megegyezik a 25-össel, csak a 3-as bit hiányzik.Most, ha a 17-et kiegészítjük a 3-as bittel, akkor a (nem (B) VAGY C) kifejezés nem (nem)-re alakulna. A ), azaz in A = (X&25 nem egyenlő 0-val). Másképpen: mondjuk A=8 (3. bit=1). Ekkor a követelmény (nem (B) B vagy C) ekvivalens a következővel: (a 4,0 bitek közül legalább az egyik 1) VAGY (a 3. bit értéke 1) = (a 0,3,4 bitek közül legalább az egyik nem 1) - azok. inverzió not(A) = A = (X&25 nem egyenlő 0-val).
Ennek eredményeként azt vettük észre, hogy ha A = 8, akkor kifejezésünk F = nem (A) VAGY A alakot ölt, ami a kizárt középső törvénye szerint mindig azonosan igaz. Más, kisebb A-értékeknél az X értékétől való függetlenség nem érhető el, mivel a maszkok mások. Nos, ha az A magas bitjeiben 4 feletti bitekben vannak olyanok, semmi sem változik, mert a többi maszkban nullák vannak. Kiderül, hogy a képlet csak akkor válik tetszőleges X tautológiájává, ha A=8.
Dmitrij Lisin
