Lygčių naudojimas yra plačiai paplitęs mūsų gyvenime. Jie naudojami atliekant daugybę skaičiavimų, statant konstrukcijas ir net sportuojant. Lygtis žmogus naudojo nuo seniausių laikų ir nuo to laiko jų naudojimas tik išaugo. Matematikoje yra tam tikrų užduočių, skirtų teiginių logikai. Norėdami išspręsti tokio pobūdžio lygtį, turite turėti tam tikrą žinių kiekį: teiginių logikos dėsnių išmanymą, 1 arba 2 kintamųjų loginių funkcijų tiesos lentelių išmanymą, loginių išraiškų transformavimo metodus. Be to, reikia žinoti šias loginių operacijų ypatybes: konjunkcijas, disjunkcijas, inversijas, implikacijas ir atitikmenis.
Bet kurią loginę funkciją iš \ variables - \ galima nurodyti tiesos lentele.
Išspręskime keletą loginių lygčių:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Pradėkime sprendimą nuo \[X1\] ir nustatykime, kokias reikšmes gali turėti šis kintamasis: 0 ir 1. Tada apsvarstykite kiekvieną iš aukščiau nurodytų reikšmių ir pažiūrėkite, kokia yra \[X2.\] gali būti šiuo atveju
Kaip matyti iš lentelės, mūsų loginėje lygtyje yra 11 sprendinių.
Kur galiu išspręsti loginę lygtį internete?
Galite išspręsti lygtį mūsų svetainėje https: //. Laisvas internetinis sprendėjas leis jums per kelias sekundes išspręsti bet kokio sudėtingumo lygtį internete. Viskas, ką jums reikia padaryti, tai tiesiog įvesti savo duomenis į sprendiklį. Taip pat galite peržiūrėti vaizdo įrašo instrukcijas ir sužinoti, kaip išspręsti lygtį mūsų svetainėje. Ir jei turite klausimų, galite juos užduoti mūsų „Vkontakte“ grupėje http://vk.com/pocketteacher. Prisijunkite prie mūsų grupės, mes visada džiaugiamės galėdami jums padėti.
Tegu yra n kintamųjų loginė funkcija. Loginė lygtis yra tokia:
Konstantos C reikšmė yra 1 arba 0.
Loginė lygtis gali būti nuo 0 iki įvairių sprendimų. Jei C yra lygus 1, tai sprendiniai yra visos tos tiesos lentelės kintamųjų aibės, kuriose funkcija F įgyja reikšmę true (1). Likusios aibės yra C lygties sprendiniai, lygūs nuliui. Visada galime svarstyti tik formos lygtis:
Iš tiesų, tegul bus pateikta lygtis:
Tokiu atveju galite pereiti prie lygiavertės lygties:
Apsvarstykite k sistemą logines lygtis:
Sistemos sprendimas yra kintamųjų rinkinys, kuriame tenkinamos visos sistemos lygtys. Kalbant apie logines funkcijas, norint gauti loginių lygčių sistemos sprendimą, reikia rasti aibę, kurioje loginė funkcija Ф yra teisinga, vaizduojanti pradinių funkcijų jungtį:
Jei kintamųjų skaičius mažas, pavyzdžiui, mažesnis nei 5, tuomet nesunku sukonstruoti funkcijos tiesos lentelę, kuri leidžia pasakyti, kiek sprendinių turi sistema ir kokios yra aibės, duodančios sprendimus.
Kai kuriose Vieningo valstybinio egzamino loginių lygčių sistemos sprendinių paieškos užduotyse kintamųjų skaičius siekia 10. Tada tiesos lentelės sudarymas tampa beveik neišsprendžiamu uždaviniu. Problemos sprendimas reikalauja kitokio požiūrio. Savavališkai lygčių sistemai nėra bendras būdas, kuris skiriasi nuo surašymo, leidžiančio išspręsti tokias problemas.
Egzamine siūlomose problemose dažniausiai sprendžiama atsižvelgiant į lygčių sistemos specifiką. Kartoju, be visų kintamųjų aibės variantų išvardijimo, nėra bendro problemos sprendimo būdo. Sprendimas turi būti sukurtas atsižvelgiant į sistemos specifiką. Dažnai naudinga atlikti preliminarų lygčių sistemos supaprastinimą naudojant žinomus logikos dėsnius. Kitas naudingas šios problemos sprendimo būdas yra toks. Mus domina ne visos aibės, o tik tos, kuriose funkcijos reikšmė yra 1. Užuot sukūrę pilną tiesos lentelę, sukursime jos analogą – dvejetainį sprendimų medį. Kiekviena šio medžio šaka atitinka vieną sprendinį ir nurodo aibę, kurioje funkcijos reikšmė yra 1. Šakų skaičius sprendimų medyje sutampa su lygčių sistemos sprendinių skaičiumi.
Kas yra dvejetainis sprendimų medis ir kaip jis kuriamas, paaiškinsiu kelių užduočių pavyzdžiais.
18 problema
Kiek skirtingų loginių kintamųjų x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 reikšmių rinkinių yra, tenkinančių dviejų lygčių sistemą?
Atsakymas: Sistema turi 36 skirtingus sprendimus.
Sprendimas: lygčių sistemą sudaro dvi lygtys. Raskime pirmosios lygties sprendinių skaičių priklausomai nuo 5 kintamųjų - . Pirmąją lygtį savo ruožtu galima laikyti 5 lygčių sistema. Kaip buvo parodyta, lygčių sistema iš tikrųjų yra loginių funkcijų junginys. Teisingas ir atvirkštinis teiginys – sąlygų konjunkciją galima laikyti lygčių sistema.
Sukurkime sprendimų medį implikacijai () – pirmajam jungtuko nariui, kurį galima laikyti pirmąja lygtimi. Štai kaip tai atrodo grafinis vaizdasšis medis
Medis turi du lygius lygties kintamieji. Pirmasis lygis apibūdina pirmąjį kintamąjį. Dvi šio lygio šakos atspindi galimas šio kintamojo reikšmes – 1 ir 0. Antrame lygyje medžio šakos atspindi tik tas galimas kintamojo reikšmes, kurioms lygtis įgyja teisingą reikšmę. Kadangi lygtis apibrėžia implikaciją, šaka, kurios reikšmė yra 1, reikalauja, kad toje šakoje jos reikšmė būtų 1. Šaka, kurios reikšmė yra 0, sukuria dvi šakas, kurių reikšmės yra lygios 0 ir 1. Sukurtas medis apibrėžia tris sprendinius, kur implikacija įgauna reikšmę 1. Ant kiekvienos šakos išrašomas atitinkamas kintamųjų reikšmių rinkinys, kuris pateikia lygties sprendimą.
Šie rinkiniai yra: ((1, 1), (0, 1), (0, 0))
Tęskime sprendimų medžio kūrimą pridėdami šią lygtį, tokią implikaciją. Mūsų lygčių sistemos specifika yra ta, kad kiekviena nauja sistemos lygtis naudoja vieną kintamąjį iš ankstesnės lygties, pridedant vieną naują kintamąjį. Kadangi kintamasis medyje jau turi reikšmes, tai visose šakose, kuriose kintamojo reikšmė yra 1, kintamasis taip pat turės 1 reikšmę. Tokioms šakoms medžio konstrukcija tęsiama į kitą lygį, bet naujų šakų neatsiranda. Vienintelė šaka, kurioje kintamasis turi reikšmę 0, duos šaką į dvi šakas, kur kintamasis gaus reikšmes 0 ir 1. Taigi, kiekvienas naujos lygties pridėjimas, atsižvelgiant į jos specifiškumą, prideda vieną sprendimą. Originali pirmoji lygtis:
turi 6 sprendimus. Štai kaip atrodo visas šios lygties sprendimų medis:
Antroji mūsų sistemos lygtis yra panaši į pirmąją:
Skirtumas tik tas, kad lygtis naudoja kintamuosius Y. Ši lygtis taip pat turi 6 sprendinius. Kadangi kiekvienas kintamasis sprendimas gali būti derinamas su kiekvienu kintamu sprendimu, tada iš viso sprendimai yra 36.
Atkreipkite dėmesį, kad sukonstruotas sprendimų medis pateikia ne tik sprendinių skaičių (pagal šakų skaičių), bet ir pačius sprendinius, užrašytus ant kiekvienos medžio šakos.
19 problema
Kiek skirtingų loginių kintamųjų x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 reikšmių rinkinių yra, kurie tenkina visas toliau nurodytas sąlygas?
Ši užduotis yra ankstesnės užduoties modifikacija. Skirtumas tas, kad pridedama dar viena lygtis, kuri susieja X ir Y kintamuosius.
Iš lygties išplaukia, kad kai jo reikšmė yra 1 (egzistuoja vienas toks sprendimas), tada jis turi reikšmę 1. Taigi yra vienas rinkinys, kuriame ir turi reikšmes 1. Kai lygi 0, jis gali turėti bet kokia reikšmė, ir 0, ir 1. Todėl kiekviena aibė, lygi 0, ir tokių aibių yra 5, atitinka visas 6 aibes su kintamaisiais Y. Todėl bendras sprendinių skaičius yra 31.
20 problema
Sprendimas: Prisimindami pagrindinį lygiavertiškumą, rašome savo lygtį taip:
Ciklinė implikacijų grandinė reiškia, kad kintamieji yra identiški, todėl mūsų lygtis yra lygiavertė:
Ši lygtis turi du sprendinius, kai visi yra 1 arba 0.
21 problema
Kiek sprendinių turi lygtis:
Sprendimas: Kaip ir 20 užduotyje, nuo ciklinių implikacijų pereiname prie tapatybių, perrašydami lygtį į formą:
Sukurkime šios lygties sprendimų medį:
22 problema
Kiek sprendinių turi ši lygčių sistema?
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kur J, K, L, M, N yra Būlio kintamieji?
Paaiškinimas.
Išraiška (N ∨ ¬N) yra teisinga bet kuriam N, taigi
J ∧ ¬K ∧ L ∧ ¬M = 0.
Taikykite neigimą abiem loginės lygties pusėms ir naudokite De Morgano dėsnį ¬ (A ∧ B) = ¬ A ∨ ¬ B. Gauname ¬J ∨ K ∨ ¬L ∨ M = 1.
Loginė suma lygi 1, jei bent vienas iš ją sudarančių teiginių yra lygus 1. Todėl bet koks loginių kintamųjų derinys tenkina gautą lygtį, išskyrus atvejį, kai visi į lygtį įtraukti dydžiai yra lygūs 0. iš 4 kintamųjų gali būti lygus 1 arba 0, todėl galimi deriniai 2 2 2 2 = 16. Todėl lygtis turi 16 −1 = 15 sprendinių.
Belieka pastebėti, kad rasti 15 sprendimų atitinka bet kurį iš dviejų galimas vertes loginio kintamojo N reikšmės, todėl pradinėje lygtyje yra 30 sprendinių.
Atsakymas: 30
Kiek skirtingų sprendinių turi lygtis
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
kur J, K, L, M, N yra loginiai kintamieji?
Atsakyme nereikia išvardyti visų skirtingų J, K, L, M ir N reikšmių rinkinių, kuriems galioja ši lygybė. Kaip atsakymą turite nurodyti tokių rinkinių skaičių.
Paaiškinimas.
Mes naudojame formules A → B = ¬A ∨ B ir ¬(A ∨ B) = ¬A ∧ ¬B
Apsvarstykite pirmąją formulę:
(J → K) → (M ∧ N ∧ L) = ¬ (¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Apsvarstykite antrąją formulę
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨
Apsvarstykite trečiąją formulę
1) M → J = 1, vadinasi
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Sujungti:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1, taigi 4 sprendimai.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Sujungti:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L, todėl yra 4 sprendiniai.
c) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Atsakymas: 4 + 4 = 8.
Atsakymas: 8
Kiek skirtingų sprendinių turi lygtis
((K ∨ L) → (L ∧ M ∧ N)) = 0
kur K, L, M, N yra loginiai kintamieji? Atsakyme nereikia išvardyti visų skirtingų reikšmių rinkinių K, L, M ir N, kuriems galioja ši lygybė. Kaip atsakymą turite nurodyti tokių rinkinių skaičių.
Paaiškinimas.
Perrašykime lygtį naudodami paprastesnę operacijų žymėjimą:
((K + L) → (L M N)) = 0
1) iš operacijos „implikacijos“ tiesos lentelės (žr. pirmąją problemą) išplaukia, kad ši lygybė yra teisinga tada ir tik tada, kai tuo pačiu metu
K + L = 1 ir L M N = 0
2) iš pirmosios lygties išplaukia, kad bent vienas iš kintamųjų K arba L yra lygus 1 (arba abu kartu); taigi apsvarstykite tris atvejus
3) jei K = 1 ir L = 0, tai antroji lygybė galioja bet kuriam M ir N; kadangi yra 4 dviejų loginių kintamųjų deriniai (00, 01, 10 ir 11), turime 4 skirtingus sprendimus
4) jei K = 1 ir L = 1, tada antroji lygybė galioja M · N = 0; yra 3 tokie deriniai (00, 01 ir 10), turime dar 3 sprendimus
5) jei K = 0, tai būtinai L = 1 (iš pirmosios lygties); šiuo atveju antroji lygybė tenkinama esant М · N = 0; yra 3 tokie deriniai (00, 01 ir 10), turime dar 3 sprendimus
6) iš viso gauname 4 + 3 + 3 = 10 sprendinių.
Atsakymas: 10
Kiek skirtingų sprendinių turi lygtis
(K ∧ L) ∨ (M ∧ N) = 1
Paaiškinimas.
Išraiška teisinga trimis atvejais, kai (K ∧ L) ir (M ∧ N) yra atitinkamai 01, 11, 10.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N yra 1, o K ir L yra bet kokie, išskyrus abu 1. Taigi 3 sprendiniai.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 tirpalas.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 sprendiniai.
Atsakymas: 7.
Atsakymas: 7
Kiek skirtingų sprendinių turi lygtis
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
kur X, Y, Z, P yra loginiai kintamieji? Atsakyme nebūtina išvardyti visų skirtingų vertybių rinkinių, kuriems galioja ši lygybė. Kaip atsakymą tereikia nurodyti tokių rinkinių skaičių.
Paaiškinimas.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Loginis ARBA klaidingas tik vienu atveju: kai abi išraiškos yra klaidingos.
Vadinasi,
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Todėl yra tik vienas lygties sprendimas.
Atsakymas: 1
Kiek skirtingų sprendinių turi lygtis
(K ∨ L) ∧ (M ∨ N) = 1
kur K, L, M, N yra loginiai kintamieji? Atsakyme nereikia išvardyti visų skirtingų K, L, M ir N reikšmių rinkinių, kuriems galioja ši lygybė. Kaip atsakymą tereikia nurodyti tokių rinkinių skaičių.
Paaiškinimas.
Loginis AND teisingas tik vienu atveju: kai visos išraiškos teisingos.
K ∨ L = 1, M ∨ N = 1.
Kiekviena iš lygčių pateikia 3 sprendinius.
Apsvarstykite lygtį A ∧ B = 1, jei ir A, ir B įgyja tikrąsias reikšmes trimis atvejais, tada iš esmės lygtis turi 9 sprendinius.
Taigi atsakymas yra 9.
Atsakymas: 9
Kiek skirtingų sprendinių turi lygtis
((A → B)∧ C) ∨ (D ∧ ¬D) = 1,
kur A, B, C, D yra loginiai kintamieji?
Atsakyme nereikia išvardyti visų skirtingų reikšmių rinkinių A, B, C, D, kuriems galioja ši lygybė. Kaip atsakymą turite nurodyti tokių rinkinių skaičių.
Paaiškinimas.
Loginis „ARBA“ yra teisingas, kai bent vienas iš teiginių yra teisingas.
(D ∧ ¬D) = 0 bet kuriam D.
Vadinasi,
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, todėl kiekvienam D gauname 3 sprendimus.
(D ∧ ¬ D)=0 bet kuriam D, o tai duoda du sprendinius (kai D = 1, D = 0).
Taigi: suminiai sprendiniai 2*3 = 6.
Iš viso 6 sprendimai.
Atsakymas: 6
Kiek skirtingų sprendinių turi lygtis
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
kur K, L, M, N yra loginiai kintamieji? Atsakyme nereikia išvardyti visų skirtingų K, L, M ir N reikšmių rinkinių, kuriems galioja ši lygybė. Kaip atsakymą tereikia nurodyti tokių rinkinių skaičių.
Paaiškinimas.
Taikykite neigimą abiejose lygties pusėse:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Loginis ARBA yra teisingas trimis atvejais.
1 variantas.
K ∧ L ∧ M = 1, tada K, L, M = 1 ir ¬L ∧ M ∧ N = 0. Bet kuris N, tai yra, 2 sprendiniai.
2 variantas.
¬L ∧ M ∧ N = 1, tada N, M = 1; L = 0, K bet koks, tai yra, 2 sprendiniai.
Todėl atsakymas yra 4.
Atsakymas: 4
A, B ir C yra sveikieji skaičiai, kuriems teiginys yra teisingas
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Kam lygi B, jei A = 45 ir C = 43?
Paaiškinimas.
1) ¬(A = B); (A > B)→ (B > C); (B>A) → (C>B);
2) šiuos paprastus teiginius jungia operacija ∧ (IR, konjunkcija), tai yra, jie turi būti atliekami vienu metu;
3) iš ¬(А = B)=1 iš karto išeina, kad А B;
4) tarkime, kad A > B, tada iš antrosios sąlygos gauname 1→(B > C)=1; ši išraiška gali būti teisinga tada ir tik tada, kai B > C = 1;
5) todėl turime A > B > C, šią sąlygą atitinka tik skaičius 44;
6) tik tuo atveju patikrinkite variantą A 0 →(B > C)=1;
ši išraiška tinka bet kuriam B; dabar žiūrime į trečiąją sąlygą, gauname
ši išraiška gali būti teisinga tada ir tik tada, kai C > B, ir čia yra prieštaravimas, nes nėra tokio skaičiaus B, kuriam C > B > A.
Atsakymas: 44.
Atsakymas: 44
Padarykite tiesos lentelę loginei funkcijai
X = (A ↔ B) ∨ ¬(A → (B ∨ C))
kuriame argumento A reikšmių stulpelis yra dvejetainis skaičiaus 27 žymėjimas, argumento B reikšmių stulpelis yra skaičius 77, argumento C reikšmių stulpelis yra skaičius 120. Skaičius stulpelyje rašomas iš viršaus į apačią nuo reikšmingiausio skaitmens iki mažiausiai reikšmingo (įskaitant nulių rinkinį). Konvertuokite gautą dvejetainį funkcijos X reikšmių vaizdą į dešimtainę skaičių sistemą.
Paaiškinimas.
Lygtį rašome naudodami paprastesnę operacijų žymėjimą:
1) tai išraiška su trimis kintamaisiais, todėl tiesos lentelėje bus eilučių; todėl skaičių, pagal kuriuos sudaromi A, B ir C stulpeliai, dvejetainis žymėjimas turi būti sudarytas iš 8 skaitmenų
2) išversime skaičius 27, 77 ir 120 į dvejetainę sistemą, iškart papildydami įrašą iki 8 simbolių su nuliais skaičių pradžioje
3) mažai tikėtina, kad galėsite iš karto parašyti kiekvienos kombinacijos X funkcijos reikšmes, todėl patogu į lentelę pridėti papildomų stulpelių tarpiniams rezultatams apskaičiuoti (žr. lentelę žemiau)
| A | IN | SU | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) užpildykite lentelės stulpelius:
| A | IN | SU | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
reikšmė yra 1 tik tose eilutėse, kur A = B
reikšmė yra 1 tose eilutėse, kuriose B arba C = 1
reikšmė yra 0 tik tose eilutėse, kur A = 1 ir B + C = 0
reikšmė yra atvirkštinė ankstesnio stulpelio vertė (0 pakeičiama 1, o 1 pakeičiama 0)
rezultatas X (paskutinis stulpelis) yra dviejų stulpelių ir loginė suma
5) norėdami gauti atsakymą, išrašome bitus iš X stulpelio iš viršaus į apačią:
6) išverskite šį skaičių į dešimtainę sistemą:
Atsakymas: 171
Koks yra didžiausias sveikasis skaičius X, kurio teiginys (10 (X+1)·(X+2)) yra teisingas?
Paaiškinimas.
Lygtis yra implikacijos operacija tarp dviejų santykių:
1) Žinoma, čia galite taikyti tą patį metodą kaip ir 2208 pavyzdyje, tačiau tokiu atveju turėsite išspręsti kvadratines lygtis(Aš nenoriu…);
2) Atkreipkite dėmesį, kad pagal sąlygą mus domina tik sveikieji skaičiai, todėl galite pabandyti kažkaip transformuoti pradinę išraišką, gaudami lygiavertį teiginį (tikslios šaknų reikšmės mūsų visai nedomina!);
3) Apsvarstykite nelygybę : akivaizdu, kad ji gali būti ir teigiamas, ir neigiamas skaičius;
4) Nesunku patikrinti, ar teiginys teisingas visiems domeno sveikiesiems skaičiams ir visiems domeno sveikiesiems skaičiams (kad nesusipainiotumėte, patogiau naudoti negriežtas nelygybes, ir , vietoj ir );
5) Todėl sveikiesiems skaičiams jį galima pakeisti lygiaverte išraiška
6) išraiškos tiesos sritis yra dviejų begalinių intervalų sąjunga;
7) Dabar apsvarstykite antrąją nelygybę: akivaizdu, kad ji taip pat gali būti ir teigiamas, ir neigiamas skaičius;
8) Regione teiginys teisingas visiems sveikiesiems skaičiams , o regione - visiems sveikiesiems skaičiams , todėl sveikiesiems skaičiams jis gali būti pakeistas lygiaverte išraiška
9) išraiškos tiesos sritis yra uždaras intervalas;
10) Pateikta išraiška teisinga visur, išskyrus sritis, kur ir ;
11) Atkreipkite dėmesį, kad reikšmė nebetelpa, nes ten ir , tai yra, implikacija suteikia 0;
12) Keičiant 2, (10 (2+1) · (2+2)) arba 0 → 0, kuris tenkina sąlygą.
Taigi atsakymas yra 2.
Atsakymas: 2
Koks yra didžiausias sveikasis skaičius X, kuriam teiginys yra teisingas?
(50 (X+1) (X+1))?
Paaiškinimas.
Taikykite implikacijos transformaciją ir transformuokite išraišką:
(50 (X+1) (X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Loginis ARBA yra teisingas, kai yra teisingas bent vienas loginis teiginys. Išsprendę abi nelygybes ir atsižvelgę į tai, kad matome, kad didžiausias sveikasis skaičius, kuriam bent viena iš jų yra teisinga, yra 7 (paveiksle antrosios nelygybės teigiamas sprendimas pavaizduotas geltonai, o pirmosios – mėlynai) .
Atsakymas: 7
Nurodykite kintamųjų K, L, M, N reikšmes, kurių loginė išraiška
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
klaidinga. Parašykite savo atsakymą kaip 4 simbolių eilutę: kintamųjų K, L, M ir N reikšmės (ta tvarka). Taigi, pavyzdžiui, 1101 eilutė atitinka K=1, L=1, M=0, N=1.
Paaiškinimas.
Pasikartoja 3584 užduotis.
Atsakymas: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Paaiškinimas.
Taikykime implikacijos transformaciją:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Taikykite neigimą abiejose lygties pusėse:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Transformuokime:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Todėl M = 0, N = 0, apsvarstykite dabar (¬K ∧ L ∨ M ∧ L):
tai, kad M = 0, N = 0, reiškia, kad M ∧ L = 0, tada ¬K ∧ L = 1, ty K = 0, L = 1.
Atsakymas: 0100
Nurodykite kintamųjų K, L, M, N reikšmes, kurių loginė išraiška
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
klaidinga. Parašykite savo atsakymą kaip keturių simbolių eilutę: kintamųjų K, L, M ir N reikšmės (ta tvarka). Taigi, pavyzdžiui, 1101 eilutė atitinka K=1, L=1, M=0, N=1.
Paaiškinimas.
Parašykime lygtį naudodami paprastesnį operacijų žymėjimą (sąlyga „išraiška klaidinga“ reiškia, kad ji lygi loginiam nuliui):
1) iš sąlygos teiginio išplaukia, kad išraiška turi būti klaidinga tik vienam kintamųjų rinkiniui
2) iš „implikacijos“ operacijos tiesos lentelės išplaukia, kad ši išraiška yra klaidinga tada ir tik tada, kai tuo pačiu metu
3) pirmoji lygybė (loginė sandauga lygi 1) yra teisinga tada ir tik tada, kai ir ; taigi išplaukia (loginė suma lygi nuliui), kuri gali būti tik tada, kai ; taigi, jau apibrėžėme tris kintamuosius
4) iš antrosios sąlygos, , už ir gauname .
Pasikartoja užduotis
Atsakymas: 1000
Nurodykite loginių kintamųjų P, Q, S, T reikšmes, kurių loginė išraiška
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) yra klaidingas.
Atsakymą parašykite kaip keturių simbolių eilutę: kintamųjų P, Q, S, T reikšmės (ta tvarka).
Paaiškinimas.
(1) (Р ∨ ¬Q) = 0
(2) (Q → (S ∨ T)) = 0
(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Taikykite implikacijos transformaciją:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Atsakymas: 0100
Nurodykite kintamųjų K, L, M, N reikšmes, kurių loginė išraiška
(K → M) ∨ (L ∧ K) ∨ ¬N
klaidinga. Parašykite savo atsakymą kaip keturių simbolių eilutę: kintamųjų K, L, M ir N reikšmės (ta tvarka). Taigi, pavyzdžiui, 1101 eilutė atitinka K=1, L=1, M=0, N=1.
Paaiškinimas.
Loginis „ARBA“ yra klaidingas tada ir tik tada, kai abu teiginiai yra klaidingi.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Taikykime implikacijos transformaciją pirmajai išraiškai:
¬K ∨ M = 0 => K = 1, M = 0.
Apsvarstykite antrąją išraišką:
(L ∧ K) ∨ ¬N = 0 (žr. pirmosios išraiškos rezultatą) => L ∨ ¬N = 0 => L = 0, N = 1.
Atsakymas: 1001.
Atsakymas: 1001
Nurodykite kintamųjų K, L, M, N reikšmes, kurių loginė išraiška
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
tiesa. Parašykite savo atsakymą kaip keturių simbolių eilutę: kintamųjų K, L, M ir N reikšmės (ta tvarka). Taigi, pavyzdžiui, 1101 eilutė atitinka K=1, L=1, M=0, N=1.
Paaiškinimas.
Loginis "IR" yra teisingas tada ir tik tada, kai abu teiginiai yra teisingi.
1) (K → M) = 1 Taikykite implikacijos transformaciją: ¬K ∨ M = 1
2) (K → ¬M) = 1 Taikykite implikacijos transformaciją: ¬K ∨ ¬M = 1
Tai reiškia, kad K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Atsakymas: 0011
Yra žinoma, kad sveikiesiems skaičiams X, Y ir Z teiginys yra teisingas
(Z Kam Z lygus, jei X = 25 ir Y = 48?
Paaiškinimas.
Pakeitę skaičius, gauname, kad Z = 47.
Atkreipkite dėmesį, kad šis sudėtingas teiginys susideda iš trijų paprastų teiginių.
1) (Z 2) šiuos paprastus teiginius jungia operacija ∧ (IR, konjunkcija), tai yra, jie turi būti atliekami vienu metu.
3) iš ¬(Z+1 24, ir nuo ¬(Z+1 47.
4) iš (Z Z Atsakymas: 47.
Atsakymas: 47
A, B ir C yra sveikieji skaičiai, kuriems teiginys yra teisingas:
(C kam C lygus, jei A=45 ir B=18?
Paaiškinimas.
Loginis "IR" yra teisingas tada ir tik tada, kai abu teiginiai yra teisingi.
Pakeiskite skaičių reikšmes išraiškoje:
1) (C (C 2) ¬(C+1, C ≥ 44.
3) ¬(C+1, C ≥ 17.
Iš 2) ir 1) matyti, kad C
Atsakymas: 44
¬(A = B) ∧ ((B A)) ∧ ((A 2C))
Kam A lygi, jei C = 8 ir B = 18?.
Paaiškinimas.
Loginis "IR" yra teisingas tada ir tik tada, kai abu teiginiai yra teisingi.
1) ¬(A \u003d B) \u003d 1, tai yra, A ≠ 18 \u003d 1.
2) ((B A)) Taikykite implikacijos transformaciją: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Taikykite implikacijos transformaciją: (A > 18) ∨ (A > 16) = 1
Iš 2) ir 3) išplaukia, kad (18 > A) ir (A > 16), nes priešingu atveju atsiranda prieštaravimas A = 17.
Atsakymas: 17
A, B ir C yra sveikieji skaičiai, kuriems teiginys yra teisingas
¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
Kam lygi B, jei A = 45 ir C = 18?
Paaiškinimas.
Loginis "IR" yra teisingas tik tada, kai visi teiginiai yra teisingi.
Kaip išspręsti kai kurias kompiuterių mokslo egzamino A ir B sekcijų problemas
Pamoka numeris 3. Logikos. Loginės funkcijos. Lygčių sprendimas
Daugybė USE užduočių yra skirtos teiginių logikai. Daugeliui jų išspręsti pakanka žinoti pagrindinius teiginių logikos dėsnius, žinoti vieno ir dviejų kintamųjų loginių funkcijų tiesos lenteles. Pateiksiu pagrindinius teiginių logikos dėsnius.
- Disjunkcijos ir konjunkcijos komutaciškumas:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - Paskirstymo įstatymas dėl disjunkcijos ir konjunkcijos:
a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Neigiamas neigimas:
¬(¬a) ≡ a - Nuoseklumas:
a ^ ¬a ≡ klaidingas - Išskirtinis trečiasis:
a ˅ ¬a ≡ tiesa - De Morgano dėsniai:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Supaprastinimas:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ tiesa ≡ a
a ˄ klaidingas ≡ klaidingas - Absorbcija:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Potekstės pakeitimas
a → b ≡ ¬a ˅ b - Tapatybės pasikeitimas
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Loginių funkcijų vaizdavimas
Bet kuri n kintamųjų – F(x 1 , x 2 , ... x n) loginė funkcija gali būti apibrėžta tiesos lentele. Tokioje lentelėje yra 2 n kintamųjų rinkinių, kurių kiekvienam yra nurodyta šios rinkinio funkcijos reikšmė. Šis metodas yra geras, kai kintamųjų skaičius yra palyginti mažas. Net jei n > 5, vaizdas tampa prastai matomas.
Kitas būdas yra apibrėžti funkciją tam tikra formule, naudojant gerai žinomas gana paprastas funkcijas. Funkcijų sistema (f 1 , f 2 , … f k ) vadinama užbaigta, jei bet kurią loginę funkciją galima išreikšti formule, kurioje yra tik funkcijos f i .
Funkcijų sistema (¬, ˄, ˅) baigta. 9 ir 10 dėsniai yra pavyzdžiai, kaip implikacija ir tapatybė išreiškiami neigimu, konjunkcija ir disjunkcija.
Tiesą sakant, dviejų funkcijų sistema taip pat yra baigta – neigimo ir konjunkcijos arba neigimo ir disjunkcijos. Pateikimai išplaukia iš De Morgano dėsnių, leidžiančių išreikšti konjunkciją neigimu ir disjunkcija ir atitinkamai išreikšti disjunkciją neigimu ir konjunkcija:
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Paradoksalu, bet sistema, susidedanti tik iš vienos funkcijos, yra baigta. Yra dvi dvejetainės funkcijos – antikonjunkcija ir antidisjunkcija, vadinamos Pierce'o rodykle ir Schaefferio smūgiu, vaizduojančios tuščiavidurę sistemą.
Pagrindinės programavimo kalbų funkcijos paprastai apima tapatybę, neigimą, konjunkciją ir disjunkciją. Egzamino užduotyse kartu su šiomis funkcijomis dažnai yra ir potekstė.
Pažvelkime į keletą paprastų užduočių, susijusių su loginėmis funkcijomis.
15 užduotis:
Pateikiamas tiesos lentelės fragmentas. Kuri iš trijų pateiktų funkcijų atitinka šį fragmentą?
| x1 | x2 | x3 | x4 | F |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Funkcijos numeris 3.
Norint išspręsti problemą, reikia žinoti pagrindinių funkcijų tiesos lenteles ir nepamiršti operacijų prioritetų. Priminsiu, kad konjunkcija (loginė daugyba) turi didesnį prioritetą ir atliekama prieš disjunkciją (loginį sudėjimą). Skaičiuojant nesunku pastebėti, kad funkcijos su skaičiais 1 ir 2 trečioje aibėje turi reikšmę 1 ir dėl šios priežasties neatitinka fragmento.
16 užduotis:
Kuris iš šių skaičių atitinka sąlygą:
(skaitmenys, pradedant reikšmingiausiu skaitmeniu, eiti mažėjimo tvarka) → (skaičius – lyginis) ˄ (mažiausias skaitmuo – lyginis) ˄ (didžiausias skaitmuo – nelyginis)
Jei tokių skaičių yra keli, nurodykite didžiausią.
- 13579
- 97531
- 24678
- 15386
Sąlygą tenkina skaičius 4.
Pirmieji du skaičiai neatitinka sąlygos, nes mažiausias skaitmuo yra nelyginis. Sąlygų jungtis yra klaidinga, jei vienas iš jungtuko sąlygų yra klaidingas. Trečiajam skaičiui aukščiausio skaitmens sąlyga netenkinama. Ketvirtajam skaičiui įvykdytos sąlygos, nustatytos mažiesiems ir didžiiesiems skaičiaus skaitmenims. Pirmasis jungtuko narys taip pat yra teisingas, nes implikacija yra teisinga, jei jos prielaida yra klaidinga, kaip yra Ši byla.
17 problema: Du liudytojai paliudijo taip:
Pirmasis liudytojas: jei A yra kaltas, tai B tikrai yra kaltas, o C yra nekaltas.
Antrasis liudytojas: Du kalti. Ir vienas iš likusių tikrai kaltas ir kaltas, bet negaliu tiksliai pasakyti kas.
Kokias išvadas apie A, B ir C kaltę galima padaryti iš įrodymų?
Atsakymas: Iš parodymų matyti, kad A ir B yra kalti, bet C nekaltas.
Sprendimas: Žinoma, atsakymas gali būti pateiktas remiantis Sveikas protas. Tačiau pažiūrėkime, kaip tai galima padaryti griežtai ir formaliai.
Pirmas dalykas, kurį reikia padaryti, yra įforminti pareiškimus. Įveskime tris Būlio kintamuosius A, B ir C, kurių kiekvienas yra teisingas (1), jei atitinkamas įtariamasis yra kaltas. Tada pirmojo liudytojo parodymai duodami pagal formulę:
A → (B ˄ ¬C)
Antrojo liudytojo parodymai duodami pagal formulę:
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
Manoma, kad abiejų liudytojų parodymai yra teisingi ir atspindi atitinkamų formulių jungtį.
Sukurkime tiesos lentelę šiems skaitymams:
| A | B | C | F1 | F2 | F 1 F 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Suvestiniai įrodymai yra teisingi tik vienu atveju, todėl galima gauti aiškų atsakymą – A ir B yra kalti, o C yra nekaltas.
Iš šios lentelės analizės taip pat matyti, kad antrojo liudytojo parodymai yra informatyvesni. Iš jo parodymų teisingumo išplaukia tik du galimi variantai – A ir B yra kalti, o C yra nekaltas, arba A ir C yra kalti, o B yra nekaltas. Pirmojo liudytojo parodymai yra mažiau informatyvūs – jų yra 5 įvairių variantų atitinkantis jo parodymus. Abiejų liudytojų parodymai kartu duoda vienareikšmišką atsakymą apie įtariamųjų kaltę.
Loginės lygtys ir lygčių sistemos
Tegul F(x 1 , x 2 , …x n) yra n kintamųjų loginė funkcija. Loginė lygtis yra tokia:
F(x 1, x 2, ... x n) \u003d C,
Konstantos C reikšmė yra 1 arba 0.
Loginė lygtis gali turėti nuo 0 iki 2n skirtingų sprendinių. Jei C yra lygus 1, tai sprendiniai yra visos tos tiesos lentelės kintamųjų aibės, kuriose funkcija F įgyja reikšmę true (1). Likusios aibės yra C lygties sprendiniai, lygūs nuliui. Visada galime svarstyti tik formos lygtis:
F(x 1 , x 2 , …x n) = 1
Iš tiesų, tegul bus pateikta lygtis:
F(x 1 , x 2 , …x n) = 0
Tokiu atveju galite pereiti prie lygiavertės lygties:
¬F(x 1 , x 2 , …x n) = 1
Apsvarstykite k loginių lygčių sistemą:
F 1 (x 1, x 2, ... x n) \u003d 1
F 2 (x 1, x 2, ... x n) \u003d 1
F k (x 1 , x 2 , …x n) = 1
Sistemos sprendimas yra kintamųjų rinkinys, kuriame tenkinamos visos sistemos lygtys. Kalbant apie logines funkcijas, norint gauti loginių lygčių sistemos sprendimą, reikia rasti aibę, kurioje loginė funkcija Ф yra teisinga, vaizduojanti pradinių funkcijų F konjunkciją:
Ф = F 1 ˄ F 2 ˄ … F k
Jei kintamųjų skaičius mažas, pavyzdžiui, mažesnis nei 5, tuomet nesunku sukurti funkcijos Ф tiesos lentelę, leidžiančią pasakyti, kiek sprendinių turi sistema ir kokios yra aibės, duodančios sprendimus.
Kai kuriose Vieningo valstybinio egzamino loginių lygčių sistemos sprendinių paieškos užduotyse kintamųjų skaičius siekia 10. Tada tiesos lentelės sudarymas tampa beveik neišsprendžiamu uždaviniu. Problemos sprendimas reikalauja kitokio požiūrio. Savavališkai lygčių sistemai nėra bendro būdo, išskyrus surašymą, kuris leistų išspręsti tokias problemas.
Egzamine siūlomose problemose dažniausiai sprendžiama atsižvelgiant į lygčių sistemos specifiką. Kartoju, be visų kintamųjų aibės variantų išvardijimo, nėra bendro problemos sprendimo būdo. Sprendimas turi būti sukurtas atsižvelgiant į sistemos specifiką. Dažnai naudinga atlikti preliminarų lygčių sistemos supaprastinimą naudojant žinomus logikos dėsnius. Kitas naudingas šios problemos sprendimo būdas yra toks. Mus domina ne visos aibės, o tik tos, kuriose funkcija Ф turi reikšmę 1. Užuot sukūrę pilną tiesos lentelę, sukursime jos analogą – dvejetainį sprendimų medį. Kiekviena šio medžio šaka atitinka vieną sprendinį ir nurodo aibę, kurioje funkcijos Ф reikšmė yra 1. Šakų skaičius sprendimų medyje sutampa su lygčių sistemos sprendinių skaičiumi.
Kas yra dvejetainis sprendimų medis ir kaip jis kuriamas, paaiškinsiu kelių užduočių pavyzdžiais.
18 problema
Kiek skirtingų loginių kintamųjų x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 reikšmių rinkinių yra, tenkinančių dviejų lygčių sistemą?
Atsakymas: Sistema turi 36 skirtingus sprendimus.
Sprendimas: lygčių sistemą sudaro dvi lygtys. Raskime pirmosios lygties sprendinių skaičių, priklausomai nuo 5 kintamųjų – x 1 , x 2 , …x 5 . Pirmąją lygtį savo ruožtu galima laikyti 5 lygčių sistema. Kaip buvo parodyta, lygčių sistema iš tikrųjų yra loginių funkcijų junginys. Teisingas ir atvirkštinis teiginys – sąlygų konjunkciją galima laikyti lygčių sistema.
Sukurkime sprendimų medį implikacijai (x1→ x2), pirmajam jungtuko nariui, kurį galima laikyti pirmąja lygtimi. Štai kaip atrodo grafinis šio medžio vaizdas:
Medis susideda iš dviejų lygių pagal kintamųjų skaičių lygtyje. Pirmasis lygis apibūdina pirmąjį kintamąjį X 1 . Dvi šio lygio šakos atspindi galimas šio kintamojo reikšmes – 1 ir 0. Antrame lygyje medžio šakos atspindi tik tas galimas kintamojo X 2 reikšmes, kurioms lygtis įgyja teisingą reikšmę. Kadangi lygtis apibrėžia implikaciją, šaka, kurioje X 1 turi reikšmę 1, reikalauja, kad X 2 toje šakoje būtų 1. Šaka, kurioje X 1 yra 0, sukuria dvi šakas, kurių X 2 reikšmės yra lygios 0 ir 1 Sukurtas medis nurodo tris sprendinius, kuriuose implikacija X 1 → X 2 įgyja reikšmę 1. Ant kiekvienos šakos išrašoma atitinkama kintamųjų reikšmių rinkinys, kuris suteikia lygties sprendimą.
Šie rinkiniai yra: ((1, 1), (0, 1), (0, 0))
Tęskime sprendimų medžio kūrimą pridėdami tokią lygtį, tokią implikaciją X 2 → X 3 . Mūsų lygčių sistemos specifika yra ta, kad kiekviena nauja sistemos lygtis naudoja vieną kintamąjį iš ankstesnės lygties, pridedant vieną naują kintamąjį. Kadangi kintamasis X 2 jau turi reikšmes medyje, tai visose šakose, kuriose kintamojo X 2 reikšmė yra 1, kintamasis X 3 taip pat turės reikšmę 1. Tokioms šakoms medžio konstrukcija tęsiama į kitą lygį, bet neatsiranda jokių naujų šakų. Vienintelė šaka, kurioje kintamasis X 2 turi reikšmę 0, duos šaką į dvi šakas, kur kintamasis X 3 gaus reikšmes 0 ir 1. Taigi kiekvienas naujos lygties pridėjimas, atsižvelgiant į jos specifiškumą, prideda vieną sprendimas. Originali pirmoji lygtis:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
turi 6 sprendimus. Štai kaip atrodo visas šios lygties sprendimų medis:
Antroji mūsų sistemos lygtis yra panaši į pirmąją:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
Skirtumas tik tas, kad lygtis naudoja kintamuosius Y. Ši lygtis taip pat turi 6 sprendinius. Kadangi kiekvienas kintamasis sprendimas X i gali būti derinamas su kiekvienu kintamojo sprendiniu Y j , bendras sprendinių skaičius yra 36.
Atkreipkite dėmesį, kad sukonstruotas sprendimų medis pateikia ne tik sprendinių skaičių (pagal šakų skaičių), bet ir pačius sprendinius, užrašytus ant kiekvienos medžio šakos.
19 problema
Kiek skirtingų loginių kintamųjų x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 reikšmių rinkinių yra, kurie tenkina visas toliau nurodytas sąlygas?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1 → y1) = 1
Ši užduotis yra ankstesnės užduoties modifikacija. Skirtumas tas, kad pridedama dar viena lygtis, kuri susieja X ir Y kintamuosius.
Iš lygties X 1 → Y 1 išplaukia, kad kai X 1 reikšmė yra 1 (egzistuoja vienas toks sprendimas), tai Y 1 turi reikšmę 1. Taigi yra vienas rinkinys, kuriame X 1 ir Y 1 turi reikšmes. 1. Kai X 1 lygus 0, Y 1 gali turėti bet kokią reikšmę – ir 0, ir 1. Todėl kiekviena aibė, kurios X 1 lygi 0, ir tokių rinkinių yra 5, atitinka visus 6 rinkinius su Y kintamaisiais. , bendras sprendinių skaičius yra 31 .
20 problema
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Sprendimas: Prisimindami pagrindinį lygiavertiškumą, rašome savo lygtį taip:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
Ciklinė implikacijų grandinė reiškia, kad kintamieji yra identiški, todėl mūsų lygtis yra lygiavertė:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
Ši lygtis turi du sprendinius, kai visi X i yra 1 arba 0.
21 problema
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Sprendimas: Kaip ir 20 užduotyje, nuo ciklinių implikacijų pereiname prie tapatybių, perrašydami lygtį į formą:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Sukurkime šios lygties sprendimų medį: 
22 problema
Kiek sprendinių turi ši lygčių sistema?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0
((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0
((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0
((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0
Atsakymas: 64
Sprendimas: pereikime nuo 10 kintamųjų prie 5 kintamųjų, įvesdami tokį kintamųjų pakeitimą:
Y1 = (X1 ≡ X 2); Y 2 \u003d (X 3 ≡ X 4); Y3 = (X5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);
Tada pirmoji lygtis bus tokia:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
Lygtį galima supaprastinti parašant ją taip:
(Y 1 ≡ Y 2) = 0
Atsigręžęs į tradicinė forma, rašome sistemą po supaprastinimų formoje:
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
Šios sistemos sprendimų medis yra paprastas ir susideda iš dviejų šakų su kintamomis reikšmėmis:
Grįžtant prie pradinių X kintamųjų, atkreipkite dėmesį, kad kiekviena Y kintamojo reikšmė atitinka 2 X kintamųjų reikšmes, todėl kiekvienas Y kintamųjų sprendimas sukuria 2 5 X kintamųjų sprendimus. Dvi šakos generuoja 2 * 2 5 sprendimus , taigi bendras sprendinių skaičius yra 64.
Kaip matote, kiekviena lygčių sistemos sprendimo užduotis reikalauja savo požiūrio. Bendras priėmimas yra atlikti lygiavertes transformacijas, kad būtų supaprastintos lygtys. Įprasta technika yra sprendimų medžių kūrimas. Taikomas metodas iš dalies primena tiesos lentelės sudarymą su ypatumu, kad sudaromi ne visi galimų kintamųjų reikšmių rinkiniai, o tik tie, kurių funkcija įgauna reikšmę 1 (tiesa). Dažnai siūlomose problemose nereikia kurti pilno sprendimų medžio, nes jau yra Pradinis etapas galima nustatyti naujų šakų atsiradimo dėsningumą kiekviename kitame lygyje, kaip buvo padaryta, pavyzdžiui, 18 uždavinyje.
Apskritai, loginių lygčių sistemos sprendimų paieškos problemos yra geri matematiniai pratimai.
Jeigu problemą sunku išspręsti rankiniu būdu, tuomet problemos sprendimą galite patikėti kompiuteriui, parašydami atitinkamą lygčių ir lygčių sistemų sprendimo programą.
Parašyti tokią programą paprasta. Tokia programa nesunkiai susidoros su visomis egzamine siūlomomis užduotimis.
Kaip bebūtų keista, bet užduotį rasti loginių lygčių sistemų sprendimus kompiuteriui taip pat sunku, pasirodo, kompiuteris turi savo ribas. Kompiuteris gali lengvai susidoroti su užduotimis, kuriose kintamųjų skaičius yra 20-30, tačiau jis pradės ilgai galvoti apie užduotis didesnio dydžio. Esmė ta, kad funkcija 2 n, nurodanti aibių skaičių, yra eksponentas, kuris sparčiai auga kartu su n. Taip greitai, kad įprastas asmeninis kompiuteris negali susidoroti su užduotimi su 40 kintamųjų per dieną.
C# programa loginėms lygtims spręsti
Parašyti loginių lygčių sprendimo programą naudinga dėl daugelio priežasčių, jau vien todėl, kad ja galima patikrinti savo paties USE testo problemų sprendimo teisingumą. Kita priežastis yra ta, kad tokia programa yra puikus programavimo problemos pavyzdys, atitinkantis C kategorijos problemų reikalavimus USE.
Programos kūrimo idėja yra paprasta - ji pagrįsta visu galimų kintamųjų reikšmių rinkinių išvardinimu. Kadangi tam tikros loginės lygties ar lygčių sistemos kintamųjų skaičius n yra žinomas, žinomas ir aibių skaičius – 2 n , kurias reikia surūšiuoti. Naudojant pagrindines C# kalbos funkcijas – neigimą, disjunkciją, konjunkciją ir tapatumą, nesunku parašyti programą, kuri tam tikram kintamųjų rinkiniui apskaičiuoja loginės funkcijos reikšmę, atitinkančią loginę lygtį ar lygčių sistemą.
Tokioje programoje reikia sudaryti ciklą pagal aibių skaičių, ciklo pagrinde pagal aibės skaičių, suformuoti patį aibę, apskaičiuoti šios aibės funkcijos reikšmę ir jei ši reikšmė lygi. iki 1, tada aibė pateikia lygties sprendimą.
Vienintelis sunkumas, kylantis įgyvendinant programą, yra susijęs su užduotimi suformuoti kintamųjų reikšmių rinkinį pagal nustatytą skaičių. Šios užduoties grožis yra tas, kad ši iš pažiūros sudėtinga užduotis iš tikrųjų yra paprasta užduotis, kuri jau buvo ne kartą iškilusi. Iš tiesų, pakanka suprasti, kad skaičių i atitinkančių kintamųjų reikšmių rinkinys, susidedantis iš nulių ir vienetų, reiškia dvejetainį skaičiaus i vaizdą. Taigi sunki užduotis kintamųjų reikšmių rinkinio gavimas pagal aibės skaičių yra sumažintas iki gerai žinomos problemos konvertuoti skaičių į dvejetainę sistemą.
Štai kaip C# funkcija, išsprendžianti mūsų problemą, atrodo taip:
///
/// sprendinių skaičiavimo programa
/// loginė lygtis (lygčių sistema)
///
///
/// loginė funkcija – metodas,
/// kurio parašą nustato DF delegatas
///
/// kintamųjų skaičius
///
statinis int SolveEquations (DF įdomus, int n)
bool rinkinys = naujas bool[n];
int m = (int)Math.Pow(2, n); //rinkinių skaičius
int p = 0, q = 0, k = 0;
//Visas surašymas pagal rinkinių skaičių
už (int i = 0; i< m; i++)
//Kito rinkinio formavimas – rinkinys,
//duota dvejetainiu skaičiaus i vaizdavimu
už (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Apskaičiuokite funkcijos reikšmę rinkinyje
Norint suprasti programą, tikiuosi, kad pakaks programos idėjos paaiškinimų ir komentarų jos tekste. Aš apsistosiu tik prie aukščiau pateiktos funkcijos antraštės paaiškinimo. Funkcija SolveEquations turi du įvesties parametrus. Funkcijos parametras nurodo loginę funkciją, atitinkančią sprendžiamą lygtį arba lygčių sistemą. Parametras n nurodo skaičių funkcijų kintamieji linksma. Dėl to funkcija SolveEquations grąžina loginės funkcijos sprendinių skaičių, tai yra aibių, kuriose funkcija įvertina kaip tiesa, skaičių.
Moksleiviams įprasta, kai kuriai nors funkcijai F(x) įvesties parametras x yra aritmetinio, eilutės arba loginio tipo kintamasis. Mūsų atveju naudojamas galingesnis dizainas. Funkcija SolveEquations nurodo funkcijas aukštesnė tvarka– F(f) tipo funkcijos, kurių parametrais gali būti ne tik paprasti kintamieji, bet ir funkcijos.
Funkcijų klasė, kurią galima perduoti kaip parametrą funkcijai SolveEquations, apibrėžiama taip:
deleguoti bool DF(bool vars);
Ši klasė apima visas funkcijas, kurios kaip parametras perduodamos loginių kintamųjų reikšmių rinkinys, nurodytas vars masyve. Rezultatas yra Būlio reikšmė, nurodanti šios rinkinio funkcijos reikšmę.
Baigdamas pateiksiu programą, kurioje SolveEquations funkcija naudojama kelioms loginių lygčių sistemoms išspręsti. Funkcija SolveEquations yra šios ProgramCommon klasės dalis:
klasės ProgramCommon
deleguoti bool DF(bool vars);
statinė tuštuma Main (eilutės args)
Console.WriteLine("Funkcija ir sprendimai - " +
IšspręskiteEquations(FunAnd, 2));
Console.WriteLine("Funkcija turi 51 sprendimą - " +
IšspręskiteEquations(Fun51, 5));
Console.WriteLine("Funkcija turi 53 sprendimus - " +
IšspręskiteEquations(Fun53, 10));
statinis bool FunAnd(bool vars)
grąžinti vars && vars;
statinis bool Fun51 (bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
statinis bool Fun53 (bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vars) || (vars == vars)));
Štai kaip atrodo šios programos sprendimo rezultatai:
10 užduočių savarankiškam darbui
- Kurios iš trijų funkcijų yra lygiavertės:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄ Y
- Pateikiamas tiesos lentelės fragmentas:
| x1 | x2 | x3 | x4 | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Kuri iš trijų funkcijų atitinka šį fragmentą:
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- Žiuri susideda iš trijų žmonių. Sprendimas priimamas, jeigu už jį balsuoja komisijos pirmininkas, kuriam pritaria bent vienas komisijos narys. Priešingu atveju sprendimas nepriimamas. Sukurkite loginę funkciją, kuri formalizuoja sprendimų priėmimo procesą.
- X laimi prieš Y, jei keturi monetų metimai iškyla tris kartus. Apibrėžkite loginę funkciją, apibūdinančią išmoką X.
- Žodžiai sakinyje numeruojami pradedant nuo vieno. Sakinys laikomas gerai suformuotu, jei laikomasi šių taisyklių:
- Jei lyginis žodis baigiasi balse, tai kitas žodis, jei toks yra, turi prasidėti balse.
- Jei nelyginis žodis baigiasi priebalsiu, tada kitas žodis, jei toks yra, turi prasidėti priebalsiu ir baigtis balse.
Kurie iš šių sakinių yra teisingi: - Mama nuplovė Mašą su muilu.
- Lyderis visada yra modelis.
- Tiesa yra gera, bet laimė yra geresnė.
- Kiek sprendinių turi lygtis:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - Išvardykite visus lygties sprendinius:
(a → b) → c = 0 - Kiek sprendinių turi ši lygčių sistema:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1 - Kiek sprendinių turi lygtis:
(((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
Atsakymai į užduotis:
- Funkcijos b ir c yra lygiavertės.
- Fragmentas atitinka funkciją b.
- Tegul loginis kintamasis P įgyja reikšmę 1, kai komisijos pirmininkas balsuoja „už“ sprendimą. Kintamieji M 1 ir M 2 atspindi žiuri narių nuomonę. Būlio funkcija, nurodant teigiamo sprendimo priėmimą, gali būti rašoma taip:
P ˄ (M 1 ˅ M 2) - Tegul loginis kintamasis P i įgyja 1 reikšmę, kai i-asis monetos metimas iškyla. Loginė funkcija, apibrėžianti išmoką X, gali būti parašyta taip:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Pasiūlyti b.
- Lygtis turi 3 sprendinius: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)
Noskin Andrejus Nikolajevičius,
IT mokytojas
aukščiausia kvalifikacinė kategorija,
Karo mokslų kandidatas, docentas
GBOU licėjus Nr. 1575 Maskva
Optimizuotas žemėlapių sudarymo metodas 23 uždaviniui išspręsti iš KIM USE informatikoje ir IKT
Viena iš sunkiausių KIM USE užduočių yra 23 užduotis, kurioje reikia rasti skirtingų loginių kintamųjų reikšmių rinkinių, atitinkančių nurodytą sąlygą, skaičių.
Ši užduotis yra bene sunkiausia KIM USE užduotis informatikos ir IKT srityse. Paprastai su tuo susidoroja ne daugiau kaip 5% egzaminuojamųjų (1).
Toks mažas procentas mokinių, atlikusių šią užduotį, paaiškinamas taip:
- mokiniai gali supainioti (pamiršti) loginių operacijų ženklus;
- matematinės klaidos atliekant skaičiavimus;
- samprotavimo klaidos ieškant sprendimo;
- klaidų loginių išraiškų supaprastinimo procese;
- mokytojai rekomenduoja šią problemą išspręsti atlikus visą darbą, nes yra tikimybė padaryti prielaidą
klaidų yra labai daug, o užduoties „svoris“ yra tik vienas pirminis balas.
Be to, kai kurie mokytojai patys sunkiai sprendžia tokio pobūdžio problemas, todėl su vaikais stengiasi spręsti paprastesnes problemas.
Tai taip pat apsunkina situaciją, kuri yra šiame bloke didelis skaičius užduočių įvairovė ir neįmanoma rasti šabloninio sprendimo.
Siekdama ištaisyti šią situaciją, pedagogų bendruomenė baigia taikyti du pagrindinius problemų sprendimo būdus šio tipo: bitų eilutės sprendimas (2) ir atvaizdavimo metodas (3).
Šiuos metodus reikia tobulinti (optimizuoti) dėl to, kad užduotys nuolat kinta tiek struktūra, tiek kintamųjų skaičiumi (tik vieno tipo kintamieji X, dviejų tipų kintamieji X ir Y, trys tipai: X, Y). , Z).
Šių problemų sprendimo būdų įsisavinimo sudėtingumą patvirtina faktas, kad K.Yu. Polyakovo, tokio tipo problemų analizė yra 38 vienetai (4). Kai kuriose analizėse pateikiami daugiau nei vieno tipo problemos sprendimas.
Pastaruoju metu KIM USE kompiuterių moksle yra užduočių su dviejų tipų kintamaisiais X ir Y.
Optimizavau rodymo metodą ir siūlau savo mokiniams naudoti patobulintą metodą.
Tai duoda rezultatą. Mano mokinių, atlikusių šią užduotį, procentas svyruoja iki 43% išlaikiusiųjų. Paprastai informatikos egzaminą kasmet išlaiko nuo 25 iki 33 žmonių iš visų 11 klasių.
Prieš atsirandant užduočių su dviejų tipų kintamasis metodas mokiniai labai sėkmingai naudojo ekraną, tačiau po Y atsiradimo loginėje išraiškoje pradėjau pastebėti, kad vaikų atsakymai nebesutapo su testais. Paaiškėjo, kad jie ne visai aiškiai suprato, kaip sukurti atvaizdavimo lentelę su naujo tipo kintamaisiais. Tada man kilo mintis, kad patogumo dėlei reikia visą išraišką perkelti į vieno tipo kintamąjį, nes tai patogu vaikams.
Leiskite man apibūdinti šį metodą išsamiau. Patogumo dėlei panagrinėsiu tai naudodamas (4) pateiktą loginių išraiškų sistemos pavyzdį.
Kiek skirtingų sprendinių turi loginių lygčių sistema
(x 1 ^ y1)=(¬x 2 V ¬
y 2
)
(x2 ^ y2)= (¬
x 3
V ¬
y 3
)
...
(x5 ^ y 5)
= (¬
x 6
V ¬
y 6
)
Sprendimas:
1. Iš loginių lygčių sistemos analizės matome, kad yra 6 kintamieji X ir 6 kintamieji At. Kadangi bet kuris iš šių kintamųjų gali turėti tik dvi reikšmes (0 ir 1), šiuos kintamuosius pakeisime 12 to paties tipo kintamųjų, pavyzdžiui, Z.
2. Dabar perrašykime sistemą naujais to paties tipo kintamaisiais. Užduoties sudėtingumas priklausys nuo kruopštaus žymėjimo keičiant kintamuosius.
(z1 ^ z2)=
(¬z 3V¬
z 4
)
(z3 ^ z4)=
(¬
z 5
V¬
z 6
)
...
(z9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Sudarykime lentelę, kurioje surūšiuosime visus variantus z 1 , z 2 , z 3 , z 4 , kadangi pirmoje loginėje lygtyje yra keturi kintamieji, lentelėje bus 16 eilučių (16=2 4); pašalinti tokias vertes iš lentelės z 4 , kurios pirmoji lygtis neturi sprendinio (perbraukti skaičiai).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Analizuodami lentelę sukuriame kintamųjų porų rodymo taisyklę (pavyzdžiui, pora Z 1 Z 2 =00 atitikmenų pora Z 3 Z 4 = 11) .
5. Užpildykite lentelę apskaičiuodami kintamųjų porų, kurioms sistema turi sprendimą, skaičių. 
6. Sudėkite visus rezultatus: 9 + 9 + 9 + 27 = 54
7. Atsakymas: 54.
Aukščiau pateiktas optimizuotas 23 problemos sprendimo būdas iš KIM USE leido studentams atgauti pasitikėjimą ir sėkmingai išspręsti tokio tipo problemas.
Literatūra:
1. FIPI. Gairės mokytojams, parengta remiantis tipinių dalyvių klaidų analize 2015 m. Prieigos režimas: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Poliakovas, M.A. Roitbergas.Loginių lygčių sistemos: sprendimas naudojant bitų eilutes. Žurnalas Informatika, Nr.12, 2014, p. 4-12. Leidykla „Rugsėjo pirmoji“, Maskva.3. E.A. Mirončikas, Rodymo metodas.Žurnalas Informatika, Nr.10, 2013, p. 18-26. Leidykla „Rugsėjo pirmoji“, Maskva.
