Metode loģisko vienādojumu sistēmu risināšanai. Loģisko vienādojumu sistēmas vienotā valsts eksāmena uzdevumos datorzinātnēs Loģisko vienādojumu risināšana datorzinātnēs tiešsaistē

Vienādojuma atrisinājums 1. Pārejiet uz vienādojuma rakstīšanas prefiksa formu, noliegumu simbolus aizstājot ar ¬ 2. Konstruējiet īpaša veida patiesības tabulas nosaukumu 3. Aizpildiet patiesības tabulas rindas visām kombinācijām A un B, X vietā aizstājot ar 0 vai 1. 4. Izveidojiet patiesības tabulu X = F (A,B) 5. Izmantojot patiesības tabulu, nosakiet funkcijas X veidu, ja nepieciešams, izmantojot SCNF konstruēšanas metodes. un SDNF, kas tiks apspriesti turpmāk.

Īpašas formas patiesības tabulas konstruēšana ¬((A+B)·(X A·B))=¬(B+¬(X A))

Patiesības tabula X=F(A, B) ABX atbilst implikācijas B noliegumam A ATBILDE:

Loģisko ierīču kombinētās shēmas Pamatelementi (GOST): 1 A B Disjunkcija A B Ekvivalence & A B Savienojums M2 A B XOR

Loģisko ierīču kombinētās shēmas Pamatelementi (GOST): 1 A B Implikācijas & A B Šēfera elements un A B Koimlikācija 1 A B Webb elements

Shēmas piemērs F 1 & 1 & & 1M2 B A

Shēmu risināšana 1 Variants - ķēdes pārvēršana sarežģītā loģiskā izteiksmē un pēc tam vienkāršota saskaņā ar loģikas likumiem. 2. variants – patiesības tabulas konstruēšana un pēc tam, ja nepieciešams, konstruēšana caur SKNF vai SDNF (skatīt zemāk). Apsvērsim otro iespēju, jo tā ir vienkāršāka un saprotamāka.

Patiesības tabulas uzbūve AB A + B + · B B · A + A B A + · ·

Patiesības tabula F(A, B) ABX atbilst implikācijas B noliegumam A ATBILDE:

SDNF un SKNF (definīcijas) Elementārais konjunkcija ir vairāku mainīgo konjunkcija, kas ņemta ar noliegumu vai bez tā, un starp mainīgajiem var būt identiski.Elementāro disjunkciju sauc par vairāku mainīgo lielumu konjunkciju, kas ņemti ar noliegumu vai bez tā, un starp mainīgajiem var būt identiski Jebkurš elementāro savienojumu disjunkts Sauksim to par disjunktīvo normālu formu (DNF) Sauksim jebkuru elementāro disjunkciju konjunkciju par konjunktīvo normālo formu (DNF)

SDNF un SCNF (definīcijas) Par perfektu disjunktīvu normālu formu (PDNF) sauc par DNF, kurā nav identisku elementāru savienojumu un visi savienojumi sastāv no vienas un tās pašas mainīgo kopas, kurā katrs mainīgais parādās tikai vienu reizi (iespējams, ar noliegumu). Perfekta konjunktīva normālā forma (PCNF) ir CNF, kurā nav identisku elementāru disjunkciju un visas disjunkcijas sastāv no vienas un tās pašas mainīgo kopas, kurā katrs mainīgais parādās tikai vienu reizi (iespējams, ar noliegumu).

Algoritms SDNF iegūšanai no patiesības tabulas 1. Atzīmējiet patiesības tabulas rindas, kuru pēdējā kolonnā ir 1. 2. Katrai atzīmētajai rindai pierakstiet visu mainīgo konjunkciju šādi: ja mainīgā vērtība dotā rinda ir 1, tad savienojumā iekļaujiet šo mainīgo, ja tas ir vienāds ar 0, tad tā noliegumu. 3. Saistiet visus iegūtos savienojumus disjunkcijā. Algoritms SCNF iegūšanai no patiesības tabulas 1. Atzīmējiet patiesības tabulas rindas, kuru pēdējā kolonnā ir 0. 2. Katrai atzīmētajai rindai izrakstiet visu mainīgo disjunkciju šādi: ja mainīgā vērtība dotā rinda ir 0, tad šo mainīgo iekļaujiet savienojumā, ja ir vienāds ar 1, tad tā noliegumu. 3. Saistiet visus iegūtos disjunkcijas konjunkcijā.

SKNF konstruēšanas piemērs XY F(X,Y) Atzīmējiet nulles 2. Disjunkcijas: X + Y 3. Savienojums: (X + Y) · (X + Y)

Izmērs: px

Sāciet rādīt no lapas:

Atšifrējums

1 Loģisko vienādojumu un loģisko vienādojumu sistēmu risināšana Lai F(x, x2, xn) ir n mainīgo loģiskā funkcija. Loģiskajam vienādojumam ir šāda forma: F(x, x2, xn) = C, kur konstantei C ir vērtība vai. Loģiskajam vienādojumam var būt līdz 2n dažādi risinājumi. Ja C ir vienāds, tad risinājumi ir visas tās mainīgo kopas no patiesības tabulas, kurās funkcija F iegūst vērtību true (). Atlikušās kopas ir vienādojuma atrisinājumi ar C vienādu ar nulli. Vienmēr var ņemt vērā tikai vienādojumus šādā formā: F(x, x2, xn) = Patiešām, dosim vienādojumu: F(x, x2, xn) = Šajā gadījumā varat pāriet uz līdzvērtīgu vienādojumu: F( x, x2, xn) = Apsveriet k loģisko vienādojumu sistēmu: F(x, x2, xn) = F2(x, x2, xn) = ( Fk(x, x2, xn) = sistēmas risinājums ir kopa mainīgo, uz kuriem ir izpildīti visi sistēmas vienādojumi. Loģiskā izteiksmē funkcijas, lai iegūtu loģisko vienādojumu sistēmas atrisinājumu, jāatrod kopa, uz kuras ir patiesa loģiskā funkcija Ф, kas attēlo sākotnējo funkciju F konjunkciju: Ф = F F2 Fk Ja mainīgo lielumu skaits ir mazs, piemēram, mazāks par 5, tad nav grūti izveidot patiesības tabulu funkcijai Ф, kas ļauj pateikt, cik daudz risinājumu sistēmai ir un kādas ir kopas, sniegt risinājumus Dažās USE problēmās loģisko vienādojumu sistēmas risinājumu meklēšanai mainīgo skaits sasniedz vērtību. Tad patiesības tabulas konstruēšana kļūst par praktiski neatrisināmu uzdevumu. Lai atrisinātu problēmu, nepieciešama cita pieeja. Patvaļīgai vienādojumu sistēmai nav citas vispārīgas metodes, izņemot uzskaitīšanu, kas ļautu atrisināt šādas problēmas. Eksāmenā piedāvātajās problēmās risinājums parasti balstās uz vienādojumu sistēmas specifikas ņemšanu vērā. Tomēr es atkārtoju, ka, izņemot visu mainīgo lielumu kopas opciju izmēģināšanu, nav vispārēja veida problēmas risināšanai. Risinājums jāveido, pamatojoties uz piedāvāto sistēmu. Bieži vien ir lietderīgi veikt vienādojumu sistēmas iepriekšēju vienkāršošanu, izmantojot zināmus loģikas likumus. Vēl viens noderīgs paņēmiens šīs problēmas risināšanai ir šāds. Mūs neinteresē visas kopas, bet tikai tās, kurās funkcijai Φ ir vērtība. Tā vietā, lai izveidotu pilnīgu patiesības tabulu, mēs izveidosim tās analogu - bināro lēmumu koku. Katrs šī koka zars atbilst

2 vienam risinājumam un norāda kopu, kurā funkcijai Ф ir vērtība. Zaru skaits lēmumu kokā sakrīt ar vienādojumu sistēmas atrisinājumu skaitu. Es paskaidrošu, kas ir binārais lēmumu koks un kā tas tiek veidots, izmantojot vairāku problēmu piemērus. Uzdevums Cik dažādas loģisko mainīgo x, x2, x3, x4, x5, y, y2, y3, y4, y5 vērtību kopas ir, kas apmierina divu vienādojumu sistēmu? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ( (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Atbilde: sistēma ir 36 dažādi atrisinājumi Vienādojumu sistēma ietver divus vienādojumus.Atradīsim atrisinājumu skaitu pirmajam vienādojumam atkarībā no 5 mainīgajiem x,x2,x5.Pirmo vienādojumu savukārt var uzskatīt par 5 vienādojumu sistēmu.Kā bija parādīts, vienādojumu sistēma faktiski attēlo savienojumu loģiskās funkcijas.Arī apgrieztais apgalvojums ir patiess - nosacījumu konjunkciju var uzskatīt par vienādojumu sistēmu. Veidosim lēmumu koku implikācijai (x x2) - pirmais termins savienojums, ko var uzskatīt par pirmo vienādojumu.Lūk, kā izskatās šī koka grafiskais attēlojums: X X2 Koks sastāv no diviem līmeņiem atbilstoši mainīgo skaitam vienādojumā.Pirmais līmenis apraksta pirmo mainīgo X Divi šī līmeņa zari atspoguļo šī mainīgā iespējamās vērtības un. Otrajā līmenī koka zari atspoguļo tikai tās iespējamās mainīgā X2 vērtības, kurām vienādojums ir patiess. Tā kā vienādojums norāda implikāciju, zaram, kurā X ir vērtība, ir nepieciešams, lai X2 šajā atzarā būtu vērtība. Atzars, kurā X ir vērtība, rada divus zarus, kuru X2 vērtības ir vienādas ar un. Konstruētais koks norāda trīs risinājumus, kuros X X2 implikācija iegūst vērtību. Katrā zarā tiek izrakstīts atbilstošs mainīgo vērtību kopums, kas sniedz vienādojuma risinājumu. Šīs kopas ir: ((,), (,), (,)) Turpināsim lēmumu koka veidošanu, pievienojot šādu vienādojumu, sekojošu implikāciju X2 X3. Mūsu vienādojumu sistēmas specifika ir tāda, ka katrā jaunajā sistēmas vienādojumā tiek izmantots viens mainīgais no iepriekšējā vienādojuma, pievienojot vienu jaunu mainīgo. Tā kā mainīgajam X2 jau ir vērtības kokā, tad visos zaros, kur mainīgajam X2 ir vērtība, mainīgajam X3 būs arī vērtība. Šādiem zariem koku celtniecība turpinās uz nākamo līmeni, bet jauni zari neparādās. Vienīgā filiāle, kurā mainīgajam X2 ir vērtība, sazarosies divās filiālēs, kur mainīgais X3 saņems vērtības un. Tādējādi katra jauna vienādojuma pievienošana, ņemot vērā tā specifiku, pievieno vienu risinājumu.

3 Sākotnējam pirmajam vienādojumam: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ir 6 risinājumi. Lūk, kā izskatās šī vienādojuma pilns atrisinājumu koks: X X2 X3 X4 X5 Mūsu sistēmas otrais vienādojums ir līdzīgs pirmajam: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4) y5) = Vienīgā atšķirība ir tā, ka vienādojumā ir izmantoti Y mainīgie. Arī šim vienādojumam ir 6 risinājumi. Tā kā katru mainīgo Xi risinājumu var apvienot ar katru mainīgo Yj risinājumu, kopējais risinājumu skaits ir 36. Ņemiet vērā, ka konstruētais lēmumu koks sniedz ne tikai risinājumu skaitu (pēc zaru skaita), bet arī paši risinājumi uzrakstīti uz katra koka zara. 2. uzdevums Cik dažādu loģisko mainīgo x, x2, x3, x4, x5, y, y2, y3, y4, y5 vērtību kopu ir, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem? (x x2) ^ (x2 x 3) ^ (x3 x4) ^ (x4 x5) = ((y y2) ^ (y2 y3) ^ (y3 y4) ^ (y4 y5) = (x y) = Atbilde: 3 Šī problēma ir iepriekšējās problēmas modifikācija. Atšķirība ir tāda, ka tiek pievienots cits vienādojums, kas attiecas uz mainīgajiem lielumiem X un Y. No vienādojuma X Y izriet, ka, ja X ir vērtība (viens šāds risinājums pastāv), tad Y ir vērtība. ir viens komplekts, uz kura

4 X un Y ir nozīme. Ja X ir vienāds, Y var būt jebkura vērtība, gan un. Tāpēc katra kopa, kurā X ir vienāds ar un ir 5 šādas kopas, atbilst visām 6 kopām ar mainīgajiem Y. Tāpēc kopējais atrisinājumu skaits ir 3. 3. uzdevums Cik atrisinājumu ir vienādojumam: (X X2) ( X2 X3) (X3 X4) (X4 X5) (X5 X) = Atbilde: 2 Atgādinot pamata ekvivalences, mēs rakstām vienādojumu šādā formā: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5) X) = Implikāciju cikliskā ķēde nozīmē mainīgo identitāti, lai mūsu vienādojums būtu līdzvērtīgs vienādojumam: X X2 X3 X4 X5 = Šim vienādojumam ir divi risinājumi, ja visi Xi ir vai nu vai. 4. uzdevums Cik atrisinājumu ir vienādojumam: (X X2) (X2 X3) (X3 X4) (X4 X2) (X4 X5) = Atbilde: 4 Tāpat kā 2. uzdevumā, pāriesim no cikliskām implikācijām uz identitātēm, pārrakstot vienādojums formā: (X X2) (X2 X3 X4) (X4 X5) = Izveidosim lēmuma koku šim vienādojumam: X X2 X3 X4 X5

5 4. uzdevums Cik atrisinājumu ir šādai vienādojumu sistēmai? Atbilde: 64 ((X X2) (X3 X4)) ((X X2) (X3 X4)) = ((X3 X4) (X5 X6)) ((X3 X4) (X5 X6)) = ((X5 X6) (X7 X8)) ((X5 X6) (X7 X8)) = (((X7 X8) (X9 X)) ((X7 X8) (X9 X)) = Pārejam no mainīgajiem uz 5 mainīgajiem, ieviešot šādas izmaiņas no mainīgajiem: Y = (X X2); Y2 = (X3 X4); Y3 = (X5 X6); Y4 = (X7 X8); Y5 = (X9 X); Tad pirmais vienādojums būs šādā formā: (Y Y2 ) (Y Y2) = Vienādojumu var vienkāršot, ierakstot to formā: (Y Y2) = Pārejot uz tradicionālo formu, mēs ierakstām sistēmu pēc vienkāršojumiem formā: (Y Y2) = (Y2 Y3) = ( (Y3 Y4) = (Y4 Y5) = šīs sistēmas lēmumu koks ir vienkāršs un sastāv no diviem zariem ar mainīgām mainīgo vērtībām: Y Y2 Y3 Y4 Y5 Atgriežoties pie sākotnējiem mainīgajiem X, mēs atzīmējam, ka katra vērtība no mainīgā Y atbilst 2 mainīgo X vērtībām, tāpēc katrs Y mainīgais risinājums ģenerē 2 5 risinājumus mainīgajos X. Abi atzari veido 2 * 2 5 risinājumus, tātad kopējais risinājumu skaits ir 64. Kā redzat, katrai vienādojumu sistēmas risināšanas problēmai ir nepieciešama atšķirīga pieeja. Izplatīts paņēmiens ir veikt līdzvērtīgas transformācijas, lai vienkāršotu vienādojumus.

6 Izplatīts paņēmiens ir lēmumu koku konstruēšana. Izmantotā pieeja daļēji atgādina patiesības tabulas izveidošanu ar īpatnību, ka tiek konstruētas ne visas iespējamo mainīgo vērtību kopas, bet tikai tās, kurām funkcijai ir vērtība (true). Bieži vien piedāvātajās problēmās nav nepieciešams izveidot pilnīgu lēmumu koku, jo jau sākotnējā posmā ir iespējams noteikt jaunu zaru parādīšanās modeli katrā nākamajā līmenī, kā tas tika darīts, piemēram, uzdevumā. .

Putilovs Viktors Vasiļjevičs MAOU vidusskola 46 Loģisko vienādojumu sistēmas. Saturs Piezīme par mainīgo aizstāšanu.... Problēmas, kas satur implikāciju vai tai līdzvērtīgu apzīmējumu...2 Papildnosacījuma esamība...6

Loģisko vienādojumu sistēmas atrisināšana. Cik atrisinājumu ir vienādojumam A BB C C D = 0 Mainīgo kopu skaits ir =. Varat izveidot patiesības tabulu un pārbaudīt, cik kopas atbilst

Loģisko izteiksmju patiesības tabulu konstruēšana un analīze. Vienotais valsts eksāmens 2015 2 (pamata līmenis, laiks 3 minūtes) Piemērs P-13. Katra Būla izteiksme A un B ir atkarīga no vienas un tās pašas 5 mainīgo kopas.

N B Rogovs Kā iemācīties atrisināt Vienotā valsts eksāmena datorzinātnēs (loģisko vienādojumu sistēmas) uzdevumu B15 180+ minūtēs Materiāli nodarbībām Online sadaļa: http://basicschoolru/?page=eam_info_b15 Teorētiskais ievads:

B4 Tēma: Loģisko izteiksmju konvertēšana. Par apzīmējumiem Diemžēl “nopietnā” matemātiskajā loģikā (,) pieņemto loģisko operāciju UN, VAI un NĒ apzīmējumi ir neērti un nav intuitīvi skaidri

Matemātika un matemātiskā modelēšana UDK 004.023 Semenovs Sergejs Maksimovičs Vladivostokas Valsts ekonomikas un pakalpojumu universitāte Krievija. Vladivostoka Par vienu veidu, kā atrisināt loģiskās sistēmas

B4 (augsts līmenis, laiks 1 min) Tēma: Loģisko izteiksmju konvertēšana. Par apzīmējumiem Diemžēl “nopietnā” matemātiskajā loģikā pieņemtie loģisko operāciju UN, VAI un NĒ apzīmējumi (,),

B0 (augsts līmenis, laiks 0 min) Tēma: Loģisko izteiksmju konvertēšana. Par apzīmējumiem Diemžēl “nopietnā” matemātiskajā loģikā pieņemtie loģisko operāciju UN, VAI un NĒ apzīmējumi (,),

19022017 Bitu operācijas KIM vienotā valsts eksāmena datorzinātnēs problēmās II daļa KYu Poļakovs, tehnisko zinātņu doktors, datorzinātņu skolotājs GBOU 163. vidusskola, Sanktpēterburga Šajā rakstā pirmo reizi aplūkotas šāda veida problēmas

Patstāvīgais darbs par tēmu “Loģisko funkciju noteikšanas metodes” 1. Aprēķināt funkcijas F(x, y, z) = vērtību uz mainīgo lielumu kopas (1, 1, 0). 3. Nosakiet funkciju F(x, y, z) = un G(x,

Loģika ir zinātne, kas pēta metodes, kā noteikt dažu apgalvojumu patiesumu vai nepatiesību, pamatojoties uz citu apgalvojumu patiesumu vai nepatiesību. Paziņojums (spriedums) ir kāds teikums, kas

B augsts līmenis, laiks 0 min) K. Poļakovs, 009-0 Tēma: Loģisko izteiksmju transformācija. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

1. uzdevums: Dots izteiksmes F patiesuma tabulas fragments: Kāda izteiksme var būt F? X Y Z F 0 0 0 0 0 0 1 0 1 1 1 1 1) X /\ Y /\ Z 2) X \/ Y \/ Z 3) X \/ Y \/ Z 4) X /\ Y /\ Z Apsveriet pirmā izteiksme

LOĢISKĀS ALGEBRAS FUNKCIJAS (turpinājums) Būla funkciju skaitu no n mainīgajiem nosaka pēc formulas: P2 (n) = 2 2n Divu mainīgo loģiskās funkcijas 6 Visbiežāk tiek izmantotas šādas funkcijas: f (x,

Problēmu risinājumi divvērtību loģikā F.G. Korablev uzdevums 1. Funkcijai f(x, y, z) = ((x y) (x z)) (z x), atrodiet būtiskos un fiktīvos mainīgos, veiciet fiktīvo mainīgo likvidēšanas operāciju. Risinājums.

051216 Bitu operācijas KIM vienotā valsts eksāmena datorzinātnēs II daļas problēmās KYu Poļakovs, tehnisko zinātņu doktors, datorzinātņu skolotājs GBOU 163. vidusskola, Sanktpēterburga Šajā rakstā pirmo reizi aplūkotas šāda veida problēmas:

Mirončiks E.A., informātikas skolotājs, Novokuzņecka Vienotā valsts eksāmena-18 uzdevuma risināšana ar bitu operācijām Aprakstītā metode demonstrē risinājuma metodi, kuras pamatā ir identiskas pārejas, t.i. = "darbojas"

Tēma: Matemātiskās loģikas pamatjēdzieni. Jautājumu paraugi par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi, kas pieņemti “nopietnā” matemātiskajā loģikā (,), ir neērti un intuitīvi.

1. daļa 1. Norādiet, kura loģiskā izteiksme ir ekvivalenta izteiksmei A /\ (B \/ C). 1) A \/ B \/ C 2) A /\ B /\ C 3) A /\ B /\ C 4) A /\ B /\ C Risinājums: izmantojot de Morgana formulu (B \/ C) = B /\ C un

Glinka N.V. Izmantotais apzīmējums Negācija Reizināšana (savienojums) Saskaitīšana (disjunkcija) Implikācijas ekvivalence Problēmu piemēri pirms 2010. mācību gada Cik dažādu atrisinājumu veido vienādojums ((K

Bitu operācijas KIM problēmās datorzinātnēs Problēmu veidi Šajā vebinārā tiek apspriestas šāda veida problēmas (šīs problēmas pirmo reizi parādījās KIM 2015. gada vienotajā valsts eksāmenā): Ieviesiet izteicienu M & K, apzīmējot

Praktiskais darbs 6 Loģisko uzdevumu risināšana, izmantojot loģiskās algebras likumus Darba mērķis: nostiprināt prasmes pārveidot loģiskās izteiksmes, izmantojot loģiskās algebras likumus, aprēķināt

A10 (pamatlīmenis, laiks 1 min) Tēma: Loģisko izteiksmju transformācija. De Morgana formulas. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

Gurskaja K.A., Ivins V.V., Semenovs S.M. Matemātiskās loģikas uzdevumu risināšana Vienotajā valsts eksāmenā datorzinātnēs 1 UDC 004.9 Gurskaya K.A., Ivin V.V., Semenov S.M. Mācību grāmata “Matemātiskās loģikas uzdevumu risināšana vienotajā valsts eksāmenā”

SATURS Priekšvārds.................................. 3 1. nodaļa. Matemātiskā loģika...... ........ .... 4 1. Propozīcijas algebra.................. 4 2. Būla algebra.......... ........ .... 12 3. Aprēķini

5. LEKCIJA INFORMĀCIJAS ZINĀTNES LOĢISKĀS OPERĀCIJAS 1. Matemātiskā loģika un datorzinātne 2. Loģiskās izteiksmes un loģiskās darbības 3. Patiesību tabulu un loģisko funkciju konstruēšana 4. Loģikas likumi un noteikumi

B5 augsts līmenis, laiks 0 min) Tēma: Loģisko izteiksmju transformācija. Par apzīmējumiem Diemžēl “nopietnā” matemātiskā loģikā pieņemtie loģisko operāciju UN, VAI un NOT apzīmējumi ir neērti,

Loģiskā algebra Loģiskā algebra ir formāla loģiskā teorija, matemātiskās loģikas nozare, ko 19. gadsimtā izstrādāja angļu matemātiķis Džordžs Būls. Loģikas algebra izmanto algebriskās metodes

2 (pamatlīmenis, laiks min) Tēma: Loģisko izteiksmju patiesības tabulu konstruēšana un analīze. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

A8 (pamatlīmenis, laiks 1 min) Tēma: Loģisko izteiksmju transformācija. De Morgana formulas. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

B15 Norādiet mainīgo K, L, M, N vērtības, kurām loģiskā izteiksme (K M) (L K) N ir nepatiesa. Uzrakstiet savu atbildi kā četru zīmju virkni: mainīgo K, L, M un N vērtības (šajā secībā).

Loģikas pamati. Loģiskās darbības un patiesības tabulas Loģikas pamati. Loģiskās darbības un patiesības tabulas Šajā lapā tiks aplūkotas 6 loģiskās darbības: konjunkcija, disjunkcija, inversija,

Būla algebras identitātes Matemātiskās loģikas galvenais uzdevums ir noteikt sarežģīta apgalvojuma nozīmi, pamatojoties uz vienkāršu apgalvojumu nepatiesību vai patiesumu. Loģiskās darbības propozīcijas algebrā

Abakānas pilsētas pašvaldības budžeta izglītības iestāde “11. vidusskola” Metodiskā izstrāde par tēmu 18. tipa uzdevumu risinājums Vienotais valsts eksāmens datorzinātnēs Atyushkina Marina Valerievna,

4. tēma. DATORA loģiskie pamati 1. PAMATINFORMĀCIJA NO LOĢISKĀS ALGEBRAS... 1 2. LOĢISKĀS ALGEBRAS LIKUMI... 4 3. LOĢISKO FUNKCIJU MINIMIZĀCIJAS JĒDZIENS... 6 4. TEHNISKĀS INTERPRETĀCIJAS LOGISKAS INTERPRETĀCIJAS

9. tēma. Datoru loģiskie pamati. 1. Loģika. Datorā apstrādātā informācija tiek attēlota, izmantojot fiziskus lielumus, kuriem var būt tikai divi stabili stāvokļi un kurus sauc par "binārajiem mainīgajiem".

Iracionālās nevienādības Nevienādības, kurās mainīgais atrodas zem saknes zīmes, sauc par iracionālām.Galvenā iracionālo nevienādību risināšanas metode ir sākotnējās samazināšanas metode.

26 transformācijas, izveidojiet pareizu spriešanas ķēdi un pieļaujiet aritmētisko kļūdu pēdējā darbībā. Ņemiet vērā, ka, risinot šo uzdevumu, sasniedz tikai aritmētisko darbību skaits

Reģionālais skolēnu izglītības, pētniecisko un dizaina darbu konkurss “Matemātikas lietišķie jautājumi” Algebra Loģikas algebra Alena Sergeevna Semušheva, Pašvaldības izglītības iestāde “Lyceum” Perma, kl. Borkova Olga Vladimirovna,

K. Poļakovs, 009-0 B5 augsts līmenis, laiks 0 min) Tēma: Loģisko izteiksmju transformācija. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

1. PRAKTISKĀ NODARBĪBA Pirmās kārtas lineārie vienādojumi, Bernulli vienādojums Vienādojums kopējos diferenciāļos Pirmās kārtas lineārais diferenciālvienādojums ir vienādojums + p(= q(Ja

Maskavas Valsts tehniskā universitāte, kas nosaukta N.E. Baumana Fundamentālo zinātņu fakultāte Matemātiskās modelēšanas katedra A.N. CAPITAL DAŠMANS

A9 (pamatlīmenis, laiks 2 min) Tēma: Loģisko izteiksmju patiesības tabulu konstruēšana. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

Mironchik E.A., MB NOU "Lyceum", Novokuzņecka Displeja metode Uzdevums. Cik daudz risinājumu ir sistēmai: Visi sistēmā iekļautie vienādojumi ir viena veida, un katrā vienādojumā ir iekļauti trīs mainīgie. Zinot

Federālā izglītības aģentūra Urālas Valsts ekonomikas universitāte Ju. B. Meļņikovs Būla un loģiskās funkcijas Elektroniskās mācību grāmatas sadaļa, kas jāpievieno lekcijai e-pasts: [aizsargāts ar e-pastu],

E.V.Prosolupovs 42. Būla algebra. Loģiskās algebras funkcijas 1 Būla funkcijas Mēs apskatīsim Būla funkcijas - funkcijas, kuru argumenti un vērtības ir patiesas un nepatiesas. Patiesība un meli būs

Federālā izglītības aģentūra Urālas Valsts ekonomikas universitāte Ju.B. Meļņikovs Būla un loģiskās funkcijas Elektroniskās mācību grāmatas sadaļa lekcijai Ed. 3., rev.

KF IZGLĪTĪBAS UN ZINĀTNES MINISTRIJA Federālā valsts autonomā augstākās profesionālās izglītības iestāde "NACIONĀLĀ PĒTNIECĪBA TOMSKAS POLITEHNIKAS UNIVERSITĀTE"

Praktiskais darbs 1 Loģiskās darbības. Formulu ekvivalence Darba mērķis: Iemācīties veidot loģisko apgalvojumu patiesuma tabulas un pārveidot formulas, izmantojot pamata ekvivalences Saturs

Viņi saka, ka tad, kad Aristotelis izdomāja loģiku, viņš svinēja ar mielastu un lika nokaut 40 aitas. Kopš tā laika aitām loģika nav patikusi. Loģiskās algebras pamatjēdzieni, 10. klase, 2017.-2018.m.g.

Pirmās kārtas diferenciālvienādojumi, kas atrisināti attiecībā uz atvasinājumu risinājuma eksistences un unikalitātes teorēma Vispārējā gadījumā pirmās kārtas diferenciālvienādojumam ir forma F ()

Lekcija 2. Konjunktīvās normālās formas. Implicenta, vienkārša funkcijas implicenta. Samazināts loģiskās algebras funkciju CNF. Metodes saīsinātā CNF konstruēšanai. Lektore Svetlana Nikolajevna Selezņeva [aizsargāts ar e-pastu]

IZTEIKUMU LOĢIKA Apgalvojumi Apgalvojums ir deklaratīvs teikums, kura saturu var novērtēt vai nu kā patiesu, vai nepatiesu. Atšķirt: absolūti patiesi apgalvojumi, absolūti

Dalies P.G. Harkovas Nacionālās mehānikas un matemātikas universitātes Diskrētās matemātikas fakultāte. Lekciju piezīmes. Saturs 1. Propozīcijas algebra un loģika. 1.1. Izteikumi un loģiskās darbības...

Algebras loģikas likumi Tas ir interesanti! Matemātika un De Morgana likums Kā matemātiski pierakstīt, vai punkts x pieder segmentam? To var izdarīt šādi: 2 x 5. Tas nozīmē, ka tajā pašā laikā mums ir

Matemātiskā loģika un algoritmu teorija Pervuhins Mihails Aleksandrovičs Loģiskās sekas AB Viņi saka, ka formula ψ x 1, x n AB ir loģiskas sekas formulām φ 1 (x 1, x n), φ m x 1,

Maskavas Valsts tehniskā universitāte, kas nosaukta N.E. Baumana Fundamentālo zinātņu fakultāte Matemātiskās modelēšanas katedra A.N. KASIATOVIKOVS

21. LEKCIJA POISSON KRAVAS. JACOBI-POISSON TEORĒMA. KANONISKĀS TRANSFORMĀCIJAS 1. Puasona kronšteini Pēdējā lekcijā tika iepazīstināts ar Lagranža kronšteina jēdzienu. Šo izteiksmi veidoja daļēji atvasinājumi

LIETOŠANAS 8. uzdevums (“Zināšanas par matemātiskās loģikas pamatjēdzieniem un likumiem”) LOĢISKĀS ALGEBRAS LIKUMI X = X X /\ Y = Y /\ X X \/ Y = Y \/ X (X /\ Z) \/ (Y / \ Z )=(X \/ Y) /\ Z A\/ = A A/\ = A A/\ =. ALGEBRAS LIKUMI

6. NODAĻA Puasona iekavu formālisms klasiskajā mehānikā 61 Puasona iekavas Puasona iekavas Doti divi dinamiskie lielumi, divas kanonisko mainīgo funkcijas un laiks t: (un (Puasona iekava

Laboratorijas darbs BERLEKAMP-MESSIE ALGORITMS PSEUDONEJAUTAS SEKCIJAS ĢENERATORA ATSAUKSMES KOEFICIENTU ATRAŠANĀ Apskatīsim, kā atjaunot atgriezenisko saiti definējošo polinomu

K.Yu. Poļakovs, M.A. Roitbergs Loģisko vienādojumu sistēmas vienotā valsts eksāmena uzdevumos datorzinātnēs K.Yu. Poļakovs, M.A. Roitberg, 0 http://kpolkov.sp.ru K.Yu. Poļakovs, M.A. Roitberg, 0 http://kpolkov.sp.ru Ražošana

Bitu operācijas KIM vienotā valsts eksāmena datorzinātnēs problēmās K.Yu. Poļakovs, tehnisko zinātņu doktors, informātikas skolotājs GBOU 163. vidusskola, Sanktpēterburga Šajā rakstā aplūkotas šāda veida problēmas (šīs problēmas parādījās pirmo reizi

Krievijas Federācijas Izglītības ministrija Donas Valsts tehniskā universitāte Augstākās matemātikas katedra Diskrētās matemātikas problēmas Rostova pie Donas 2001 UDC 517 Sastādījis: Baranovs

Puiši, mēs turpinām pētīt lielo logaritmu tēmu, šodien apskatīsim, kā atrisināt dažādus vienādojumus, kas satur logaritmus. Logaritmisks vienādojums ir šāds vienādojums

A3 (pamatlīmenis, laiks 2 min) Tēma: Loģisko izteiksmju patiesības tabulu konstruēšana. Par apzīmējumiem Diemžēl loģisko operāciju UN, VAI un NOT apzīmējumi pieņemti “nopietnā” matemātikā

Darbības laiks 4 stundas. 2. LABORATORIJAS DARBS LOĢIKAS ALGEBRAS Darba mērķis Apgūt loģikas algebras pamatus. Laboratorijas darba mērķi Nodarbības pabeigšanas rezultātā skolēnam: 1) jāzina: definīcijas

Nevienādības C C Sagatavošanās vienotajam valsts eksāmenam 0 (materiāls lekcijai skolotājiem 8040) Prokofjevs AA aaprokof@yanderu Risināšanas pamatmetodes: Uzdevumi C Nevienādību risināšana uz intervāliem Nevienādību vienkāršošana un samazināšana

1.pielikums GRUPAS, Gredzeni, LAUKI Kriptogrāfijai algebra ir viens no galvenajiem instrumentiem teorētiskajā izpētē un kriptogrāfisko transformāciju praktiskajā konstruēšanā.Tādēļ šajā

Pašvaldības budžeta izglītības iestāde

"18. vidusskola"

Baškortostānas Republikas Salavatas pilsētas pilsētas rajons

Loģisko vienādojumu sistēmas

Vienotā valsts eksāmena uzdevumos datorzinātnēs

Vienotā valsts pārbaudījuma uzdevumos sadaļa “Loģikas algebras pamati” tiek uzskatīta par vienu no grūtākajiem un grūtāk risināmajiem. Vidējais izpildīto uzdevumu procents par šo tēmu ir viszemākais un ir 43,2.

Kursu sadaļa	Vidējais izpildes procents pa uzdevumu grupām
Informācijas kodēšana un tās daudzuma mērīšana
Informācijas modelēšana
Skaitļu sistēmas
Loģiskās algebras pamati
Algoritmizācija un programmēšana
Informācijas un komunikācijas tehnoloģiju pamati

Pamatojoties uz 2018. gada KIM specifikāciju, šajā blokā ir iekļauti četri dažādu sarežģītības līmeņu uzdevumi.

№ uzdevumus	Pārbaudāms satura elementi	Uzdevuma grūtības pakāpe
	Spēja konstruēt patiesības tabulas un loģiskās shēmas
	Spēja meklēt informāciju internetā
	Pamatjēdzienu un likumu zināšanas matemātiskā loģika
	Spēja konstruēt un pārveidot loģiskās izteiksmes

23. uzdevumam ir augsta grūtības pakāpe, tāpēc tam ir viszemākais izpildes procents. No sagatavotajiem absolventiem (81-100 punkti) uzdevumu izpildīja 49,8%, vidēji sagatavoti absolventi (61-80 punkti) izpildīja 13,7%, pārējā studentu grupa šo uzdevumu neizpildīja.

Loģisko vienādojumu sistēmas risināšanas panākumi ir atkarīgi no loģikas likumu zināšanām un no precīzas metožu pielietošanas sistēmas risināšanai.

Apsvērsim loģisko vienādojumu sistēmas risināšanu, izmantojot kartēšanas metodi.

(23.154 Poļakovs K.Ju.) Cik dažādu atrisinājumu ir vienādojumu sistēmai?

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

Kur x1 , x2 ,…, x8, plkst1 ,y2 ,…,y8 - loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās mainīgo vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits.

Risinājums. Visi sistēmā iekļautie vienādojumi ir viena veida, un katrā vienādojumā ir iekļauti četri mainīgie. Zinot x1 un y1, mēs varam atrast visas iespējamās x2 un y2 vērtības, kas atbilst pirmajam vienādojumam. Spriežot līdzīgi, no zināmajiem x2 un y2 varam atrast x3, y3, kas apmierina otro vienādojumu. Tas ir, zinot pāri (x1, y1) un nosakot pāra vērtību (x2, y2), mēs atradīsim pāri (x3, y3), kas, savukārt, novedīs pie pāra (x4, y4) un tā tālāk.

Atradīsim visus pirmā vienādojuma risinājumus. To var izdarīt divos veidos: izveidot patiesības tabulu, izmantojot argumentāciju un loģikas likumu piemērošanu.

Patiesības tabula:

				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)

Patiesības tabulas konstruēšana ir darbietilpīga un laika ziņā neefektīva, tāpēc izmantojam otro metodi – loģisko spriešanu. Produkts ir vienāds ar 1 tad un tikai tad, ja katrs koeficients ir vienāds ar 1.

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

(x1  x2 ) =1

(y1  y2 ) =1

Apskatīsim pirmo vienādojumu. Sekas ir vienādas ar 1, ja 0 0, 0 1, 1 1, kas nozīmē (x1 y1)=0 priekš (01), (10), tad pāris (x2  y2 ) var būt jebkurš (00), (01), (10), (11) un, ja (x1 y1) = 1, tas ir, (00) un (11) pāris (x2 y2) = 1 ņem vienādas vērtības (00) un (11). Izslēgsim no šī risinājuma tos pārus, kuriem otrais un trešais vienādojums ir nepatiess, tas ir, x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

Kopējais pāru skaits 1+1+1+22= 25

2) (23.160 Poļakovs K.Ju.) Cik dažādu risinājumu ir loģisko vienādojumu sistēmai?

(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

Risinājums. 1) Vienādojumi ir viena veida, tāpēc, izmantojot spriešanu, mēs atradīsim visus iespējamos pirmā vienādojuma pārus (x1,y1), (x2,y2).

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Otrā vienādojuma risinājums ir pāri (00), (01), (11).

Atradīsim pirmā vienādojuma risinājumus. Ja x1=0, tad x2, y2 - jebkurš, ja x1=1, tad x2, y2 ņem vērtību (11).

Izveidosim savienojumus starp pāriem (x1, y1) un (x2, y2).

(x1 , y1 )	(x2 , y2 )

Izveidosim tabulu, lai aprēķinātu pāru skaitu katrā posmā.

							0

Ņemot vērā pēdējā vienādojuma atrisinājumus x 7  y 7 = 1, izslēgsim pāri (10). Atrodi kopējo risinājumu skaitu 1+7+0+34=42

3)(23.180) Cik dažādu risinājumu ir loģisko vienādojumu sistēmai?

(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

Risinājums. 1) Vienādojumi ir viena veida, tāpēc, izmantojot argumentāciju, mēs atradīsim visus iespējamos pirmā vienādojuma pārus (x1,x2), (x3,x4).

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

Izslēgsim no risinājuma pārus, kuri secībā dod 0 (1 0), tie ir pāri (01, 00, 11) un (10).

Izveidosim savienojumus starp pāriem (x1,x2), (x3,x4)

Pakalpojuma mērķis. Tiešsaistes kalkulators ir paredzēts loģiskās izteiksmes patiesības tabulas konstruēšana.
Patiesības tabula – tabula, kurā ir visas iespējamās ievades mainīgo kombinācijas un tām atbilstošās izvades vērtības.
Patiesības tabulā ir 2n rindas, kur n ir ievades mainīgo skaits, un n+m ir kolonnas, kur m ir izvades mainīgie.

Instrukcijas. Ievadot no tastatūras, izmantojiet šādus apzīmējumus: Piemēram, loģiskā izteiksme abc+ab~c+a~bc jāievada šādi: a*b*c+a*b=c+a=b*c
Lai ievadītu datus loģiskās diagrammas veidā, izmantojiet šo pakalpojumu.

Noteikumi loģiskās funkcijas ievadīšanai

1. Simbola v (disjunkcija, VAI) vietā izmantojiet zīmi +.
2. Pirms loģiskās funkcijas nav nepieciešams norādīt funkcijas apzīmējumu. Piemēram, F(x,y)=(x|y)=(x^y) vietā vienkārši jāievada (x|y)=(x^y) .
3. Maksimālais mainīgo skaits ir 10.

Datoru loģisko shēmu projektēšana un analīze tiek veikta, izmantojot īpašu matemātikas nozari - loģisko algebru. Loģikas algebrā var izdalīt trīs galvenās loģiskās funkcijas: “NOT” (negācija), “UN” (konjunkcija), “OR” (disjunkcija).
Lai izveidotu jebkuru loģisku ierīci, ir jānosaka katra izejas mainīgā atkarība no esošajiem ievades mainīgajiem, šo atkarību sauc par pārslēgšanas funkciju vai loģiskās algebras funkciju.
Loģiskās algebras funkciju sauc par pilnībā definētu, ja ir norādītas visas 2n tās vērtības, kur n ir izvades mainīgo skaits.
Ja visas vērtības nav definētas, funkcija tiek saukta par daļēji definētu.
Ierīci sauc par loģisku, ja tās stāvoklis ir aprakstīts, izmantojot loģiskās algebras funkciju.
Loģiskās algebras funkcijas attēlošanai tiek izmantotas šādas metodes:
Algebriskā formā jūs varat izveidot loģiskās ierīces ķēdi, izmantojot loģiskos elementus.


1. attēls - loģiskās ierīces diagramma

Visas loģikas algebras darbības ir definētas patiesības tabulas vērtības. Patiesības tabula nosaka operācijas rezultātu ar katrs ir iespējams x sākotnējo paziņojumu loģiskās vērtības. Opciju skaits, kas atspoguļo operāciju piemērošanas rezultātu, būs atkarīgs no loģiskās izteiksmes priekšrakstu skaita. Ja apgalvojumu skaits loģiskajā izteiksmē ir N, tad patiesības tabulā būs 2 N rindas, jo ir 2 N dažādas iespējamo argumentu vērtību kombinācijas.

Operācija NOT — loģiskā noliegšana (inversija)

Loģiska darbība NETIEK lietota vienam argumentam, kas var būt vienkārša vai sarežģīta loģiska izteiksme. Operācijas rezultāts NAV šāds:

• ja sākotnējā izteiksme ir patiesa, tad tās nolieguma rezultāts būs nepatiess;
• ja sākotnējā izteiksme ir nepatiesa, tad tās nolieguma rezultāts būs patiess.

Noliegšanas darbībai NAV pieņemtas šādas vienošanās:
nevis A, Ā, nevis A, ¬A, !A
Noliegšanas darbības rezultāts NAV noteikts pēc šādas patiesības tabulas:

A	nevis A
0	1
1	0

Noliegšanas darbības rezultāts ir patiess, ja sākotnējais apgalvojums ir nepatiess, un otrādi.

VAI operācija — loģiska pievienošana (disjunkcija, savienošana)

Loģiskā VAI operācija veic divu priekšrakstu apvienošanas funkciju, kas var būt gan vienkārša, gan sarežģīta loģiska izteiksme. Paziņojumus, kas ir loģiskās darbības sākumpunkts, sauc par argumentiem. Operācijas VAI rezultāts ir izteiksme, kas būs patiesa tad un tikai tad, ja vismaz viena no sākotnējām izteiksmēm ir patiesa.
Izmantotie apzīmējumi: A vai B, A V B, A vai B, A||B.
Operācijas VAI rezultātu nosaka šāda patiesības tabula:
Operācijas VAI rezultāts ir patiess, ja A ir patiess vai B ir patiess, vai gan A, gan B ir patiess, un nepatiess, ja argumenti A un B ir nepatiesi.

Operācija UN — loģiskā reizināšana (savienojums)

Loģiskā darbība UN veic divu apgalvojumu (argumentu) krustošanās funkciju, kas var būt gan vienkārša, gan sarežģīta loģiska izteiksme. Operācijas UN rezultāts ir izteiksme, kas būs patiesa tad un tikai tad, ja abas sākotnējās izteiksmes ir patiesas.
Izmantotie apzīmējumi: A un B, A Λ B, A un B, A un B.
Operācijas UN rezultātu nosaka šāda patiesības tabula:

A	B	A un B
0	0	0
0	1	0
1	0	0
1	1	1

Operācijas UN rezultāts ir patiess tad un tikai tad, ja apgalvojumi A un B ir patiesi un visos citos gadījumos ir nepatiesi.

Operācija “IF-THEN” - loģiskas sekas (implikācija)

Šī darbība savieno divas vienkāršas loģiskās izteiksmes, no kurām pirmā ir nosacījums, bet otrā ir šī nosacījuma sekas.
Izmantotie apzīmējumi:
ja A, tad B; A nozīmē B; ja A, tad B; A→B.
Patiesības tabula:

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

Implikācijas darbības rezultāts ir nepatiess tikai tad, ja premisa A ir patiesa un secinājums B (sekas) ir nepatiess.

Operācija “A tad un tikai tad, ja B” (ekvivalence, ekvivalence)

Izmantotais apzīmējums: A ↔ B, A ~ B.
Patiesības tabula:

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

Operācija “Addition modulo 2” (XOR, ekskluzīva vai stingra disjunkcija)

Izmantotais apzīmējums: A XOR B, A ⊕ B.
Patiesības tabula:

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

Ekvivalences darbības rezultāts ir patiess tikai tad, ja A un B vienlaikus ir patiesi vai nepatiesi.

Loģisko operāciju prioritāte

• Darbības iekavās
• Inversija
• Saikne (&)
• Disjunkcija (V), ekskluzīva VAI (XOR), summa modulo 2
• Ietekme (→)
• Ekvivalence (↔)

Perfekta disjunktīva normālā forma

Perfekta disjunktīva formulas normālā forma(SDNF) ir līdzvērtīga formula, kas ir elementāru savienojumu disjunkcija un kurai ir šādas īpašības:

1. Katrs formulas loģiskais termins satur visus funkcijā F(x 1,x 2,...x n) iekļautos mainīgos.
2. Visi formulas loģiskie termini ir atšķirīgi.
3. Neviens loģiskais termins nesatur mainīgo un tā noliegumu.
4. Neviens loģiskais termins formulā nesatur vienu un to pašu mainīgo divreiz.

SDNF var iegūt, izmantojot patiesības tabulas vai līdzvērtīgas transformācijas.
Katrai funkcijai SDNF un SCNF ir unikāli definēti līdz permutācijai.

Perfekta konjunktīva parastā forma

Perfekta konjunktīva parastā formulas forma (SCNF)Šī ir tai līdzvērtīga formula, kas ir elementāru disjunkciju konjunkcija un apmierina īpašības:

1. Visas elementārās disjunkcijas satur visus funkcijā F(x 1 ,x 2 ,...x n) iekļautos mainīgos.
2. Visas elementārās disjunkcijas ir atšķirīgas.
3. Katra elementārā disjunkcija vienreiz satur mainīgo.
4. Neviena elementārā disjunkcija nesatur mainīgo un tā noliegumu.

Šajā materiālā ir iekļauta prezentācija, kurā ir izklāstītas loģisko vienādojumu risināšanas metodes un loģisko vienādojumu sistēmas Vienotā valsts eksāmena datorzinātnēs uzdevumā B15 (Nr. 23, 2015). Zināms, ka šis uzdevums ir viens no grūtākajiem Vienotā valsts pārbaudījuma uzdevumiem. Prezentācija var būt noderīga, pasniedzot nodarbības par tēmu “Loģika” specializētajās nodarbībās, kā arī gatavojoties vienotajam valsts eksāmenam.

Lejupielādēt:

Priekšskatījums:

Lai izmantotu prezentāciju priekšskatījumus, izveidojiet Google kontu un piesakieties tajā: ​​https://accounts.google.com

Slaidu paraksti:

B15 uzdevuma atrisinājums (loģisko vienādojumu sistēmas) Višņevska M.P., MAOU “Ģimnāzija Nr.3” 2013.gada 18.novembris, Saratova

B15 uzdevums ir viens no grūtākajiem Vienotajā valsts eksāmenā datorzinībās!!! Tiek pārbaudītas šādas prasmes: konvertēt izteiksmes, kas satur loģiskos mainīgos; aprakstiet dabiskajā valodā loģisko mainīgo vērtību kopu, kurai ir patiesa dotā loģisko mainīgo kopa; saskaitīt bināro kopu skaitu, kas atbilst dotajiem nosacījumiem. Grūtākais ir tāpēc, ka... nav formālu noteikumu, kā to izdarīt, tas prasa minējumus.

Bez kā nevar iztikt!

Bez kā nevar iztikt!

Simbolu konjunkcija: A /\ B , A  B , AB , A & B, A un B disjunkcija: A \ / B , A + B , A | B , A vai B noliegums:  A , A, nevis A ekvivalence: A  B, A  B, A  B ekskluzīvs “vai”: A  B , A xor B

Mainīgo aizstāšanas metode Cik dažādu loģisko mainīgo x1, x2, ..., x9, x10 vērtību kopu pastāv, kas atbilst visiem tālāk uzskaitītajiem nosacījumiem: ((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 Atbildē nav jānorāda visas dažādās kopas x1, x2, …, x9, x10, kurām šī vienlīdzības sistēma ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits (2012. gada demonstrācijas versija)

Risinājums 1. solis. Vienkāršojiet, mainot mainīgos t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Pēc vienkāršošanas: (t1 \/ t2) /\/¬t1 t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Apsveriet vienu no vienādojumiem: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Acīmredzot tas =1 tikai tad, ja viens no mainīgajiem ir 0 un otrs ir 1 . Izmantosim formulu, lai izteiktu XOR darbību, izmantojot konjunkciju un disjunkciju: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

2. darbība. Sistēmas analīze ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 01 0 Т1 .Uz. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), tad katra tk vērtība atbilst diviem vērtību pāriem x2k-1 un x2k, piemēram: tk =0 atbilst diviem pāriem - (0 ,1) un (1, 0) , un tk =1 – pāri (0,0) un (1,1).

3. darbība. Risinājumu skaita skaitīšana. Katram t ir 2 atrisinājumi, ts skaits ir 5. Tādējādi. mainīgajiem t ir 2 5 = 32 atrisinājumi. Bet katram t atbilst atrisinājumu pāris x, t.i. sākotnējā sistēmā ir 2*32 = 64 risinājumi. Atbilde: 64

Daļas risinājumu likvidēšanas metode Cik dažādas loģisko mainīgo vērtību kopas ir x1, x2, ..., x5, y1,y2,..., y5, kas atbilst visiem zemāk uzskaitītajiem nosacījumiem: (x1 → x2 )∧(x2→x3)∧(x3→x4 )∧(x4→x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 =1. Atbildē nav jāuzskaita visas dažādās kopas x1, x2, ..., x5, y 1 , y2, ... , y5, kurām šī vienādību sistēma ir spēkā. Atbildē jānorāda šādu komplektu skaits.

Risinājums. 1. darbība. Vienādojumu secīgs risinājums 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 Pirmais vienādojums ir vairāku implikācijas operāciju konjunkcija, kas vienāda ar 1, t.i. katra no sekām ir patiesa. Implikācija ir nepatiesa tikai vienā gadījumā, kad 1  0, visos pārējos gadījumos (0  0, 0  1, 1  1) darbība atgriež 1. Rakstīsim to tabulas formā:

1. darbība. Vienādojumu secīgs risinājums T.o. Tika iegūti 6 risinājumu komplekti x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Spriežot līdzīgi, mēs nonākam pie secinājuma, ka y1, y2, y3, y4, y5 ir tāda pati risinājumu kopa. Jo šie vienādojumi ir neatkarīgi, t.i. tiem nav kopīgu mainīgo, tad šīs vienādojumu sistēmas risinājums (neņemot vērā trešo vienādojumu) būs 6 * 6 = 36 pāri “X” un “Y”. Aplūkosim trešo vienādojumu: y5→ x5 =1 Atrisinājums ir pāri: 0 0 0 1 1 1 Pāris nav risinājums: 1 0

Salīdzināsim iegūtos risinājumus, kur y5 =1, x5=0 neder. tādu pāru ir 5. Sistēmas atrisinājumu skaits: 36-5= 31. Atbilde: Vajadzēja 31 kombinatoriku!!!

Dinamiskās programmēšanas metode Cik dažādu risinājumu ir loģiskajam vienādojumam x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kur x 1, x 2, …, x 6 ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās mainīgo vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu daudzums.

Risinājuma solis 1. Nosacījuma analīze Pa kreisi vienādojumā implikācijas operācijas ir rakstītas secīgi, prioritāte ir vienāda. Pārrakstīsim: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Katrs nākamais mainīgais ir atkarīgs nevis no iepriekšējā, bet gan no iepriekšējās implikācijas rezultāta!

2. darbība. Modeļa atklāšana Apskatīsim pirmo implikāciju X 1 → X 2. Patiesības tabula: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 No viena 0 mēs saņēmām 2 vienības, bet no 1 mēs saņēmām vienu 0 un vienu 1. Ir tikai viens 0 un trīs 1, tas ir pirmās darbības rezultāts.

2. darbība. Parauga atklāšana Savienojot x 3 ar pirmās darbības rezultātu, iegūstam: 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 No diviem 0 – divi 1, no katra 1 (ir 3) viens 0 un viens 1 (3+3)

Solis 3. Formulas atvasināšana T.o. jūs varat izveidot formulas nullju skaita N i un vieninieku skaita E i aprēķināšanai vienādojumam ar i mainīgajiem: ,

4. solis. Tabulas aizpildīšana Aizpildīsim tabulu no kreisās puses uz labo, ja i = 6, aprēķinot nulles un vieniniekus, izmantojot iepriekš minētās formulas; tabulā parādīts, kā tiek veidota nākamā kolonna no iepriekšējās: mainīgo skaits 1 2 3 4 5 6 Nuļļu skaits N i 1 1 3 5 11 21 Vieninieku skaits E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Atbilde: 43

Metode, izmantojot loģisko izteiksmju vienkāršojumus Cik dažādu risinājumu ir vienādojumam ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1, kur J, K, L, M, N ir loģiskie mainīgie? Atbildē nav jāuzskaita visas dažādās J, K, L, M un N vērtību kopas, kurām šī vienlīdzība ir spēkā. Kā atbilde jums jānorāda šādu komplektu skaits.

Risinājums Ņemiet vērā, ka J → K = ¬ J  K Ieviesīsim mainīgo izmaiņu: J → K=A, M  N  L =B Pārrakstīsim vienādojumu, ņemot vērā izmaiņas: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Acīmredzot A  B vienādām A un B vērtībām 6. Apsveriet pēdējo implikāciju M → J = 1 Tas ir iespējams, ja: M = J = 0 M = 0, J = 1 M = J = 1

Risinājums Jo A  B, tad Kad M=J=0 iegūstam 1 + K=0. Nav risinājumu. Ja M=0, J=1 iegūstam 0 + K=0, K=0, un N un L ir jebkuri, 4 risinājumi: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

10. risinājums. Kad M=J=1 iegūstam 0+K=1 *N * L, jeb K=N*L, 4 risinājumi: 11. Kopā ir 4+4=8 risinājumi Atbilde: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Informācijas avoti: O.B. Bogomolova, D.Ju. Usenkovs. B15: jauni uzdevumi un jauni risinājumi // Informātika, Nr. 6, 2012, lpp. 35 – 39. K.Yu. Poļakovs. Loģiskie vienādojumi // Informātika, Nr. 14, 2011, lpp. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektroniskais resurss]. http://kpolyakov.narod.ru/school/ege.htm, [Elektroniskais resurss].