Kaip išspręsti loginių lygčių sistemas USE. Logikos. Loginės funkcijos. Lygčių sprendimas

Kaip išspręsti kai kurias informatikos egzamino A ir B dalis

3 pamoka. Logikos. Loginės funkcijos. Lygčių sprendimas

Daugybė vieningo valstybinio egzamino problemų 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 dėsnis dėl disjunkcijos ir konjunkcijos:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Neigimo neigimas:
¬(¬a) ≡ a
Nuoseklumas:
a ^ ¬а ≡ klaidingas
Išskirtinis trečiasis:
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
Implikacijos pakeitimas
a → b ≡ ¬a ˅ b
Tapatybės pakeitimas
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Loginių funkcijų vaizdavimas

Bet kurią n kintamųjų – F(x 1, x 2, ... x n) loginę funkciją galima nurodyti tiesos lentele. Tokioje lentelėje yra 2n kintamųjų rinkinių, kiekvienam iš kurių yra nurodyta šios rinkinio funkcijos reikšmė. Šis metodas yra geras, kai kintamųjų skaičius yra palyginti mažas. Jau n > 5 vaizdas tampa blogai matomas.

Kitas būdas yra apibrėžti funkciją tam tikra formule naudojant ž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, parodantys, kaip implikacija ir tapatybė išreiškiami neigimu, konjunkcija ir disjunkcija.

Tiesą sakant, dviejų funkcijų – neigimo ir konjunkcijos arba neigimo ir disjunkcijos – sistema taip pat yra baigta. Iš De Morgano dėsnių seka idėjos, leidžiančios išreikšti konjunkciją per neigimą ir disjunkciją ir atitinkamai išreikšti disjunkciją per neigimą ir konjunkciją:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradoksalu, bet sistema, kurią sudaro tik viena funkcija, yra baigta. Yra dvi dvejetainės funkcijos – antikonjunkcija ir antidisjunkcija, vadinamos Peirce'o rodykle ir Schaefferio smūgiu, vaizduojančiu tuščiavidurę sistemą.

Pagrindinės programavimo kalbų funkcijos paprastai apima tapatybę, neigimą, konjunkciją ir disjunkciją. Vieningo valstybinio egzamino problemose, kartu su šiomis funkcijomis, dažnai randama implikacija.

Pažvelkime į keletą paprastų problemų, susijusių su loginėmis funkcijomis.

15 problema:

Pateikiamas tiesos lentelės fragmentas. Kuri iš trijų pateiktų funkcijų atitinka šį fragmentą?

X 1	X 2	X 3	X 4	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.

Norėdami išspręsti problemą, turite žinoti pagrindinių funkcijų tiesos lenteles ir atsiminti operacijų prioritetus. Priminsiu, kad konjunkcija (loginė daugyba) turi didesnį prioritetą ir yra vykdoma anksčiau nei disjunkcija (loginis sudėjimas). 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 problema:

Kuris iš pateiktų skaičių atitinka sąlygą:

(skaitmenys, pradedant nuo reikšmingiausio skaitmens, pateikiami mažėjimo tvarka) → (skaičius – lyginis) ˄ (žemas skaitmuo – lyginis) ˄ (didelis 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 tenkinamos sąlygos, nustatytos mažiesiems ir dideliems skaičiaus skaitmenims. Pirmasis jungtuko narys taip pat yra teisingas, nes implikacija yra teisinga, jei jos prielaida yra klaidinga, kaip yra šiuo atveju.

17 problema: Du liudytojai davė tokius parodymus:

Pirmasis liudytojas: jei A kaltas, tai B dar labiau kaltas, o C nekaltas.

Antrasis liudytojas: Du kalti. Ir vienas iš likusių tikrai kaltas ir kaltas, bet negaliu pasakyti kas tiksliai.

Kokias išvadas apie A, B ir C kaltę galima padaryti iš parodymų?

Atsakymas: Iš parodymų matyti, kad A ir B yra kalti, o C yra nekaltas.

Sprendimas: Žinoma, atsakymas gali būti pateiktas remiantis sveiku protu. 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 loginius kintamuosius – A, B ir C, kurių kiekvienas turi reikšmę true (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	F 1	F 2	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 liudijimo tiesos išplaukia tik du dalykai: 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 – yra 5 skirtingi jo parodymus atitinkantys variantai. Abiejų liudytojų parodymai kartu duoda aiš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 atrodo taip:

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

Konstantos C reikšmė yra 1 arba 0.

Loginė lygtis gali turėti nuo 0 iki 2 n skirtingų sprendinių. Jei C lygus 1, tai sprendiniai yra visos tos tiesos lentelės kintamųjų aibės, kurių funkcija F įgyja reikšmę true (1). Likusios aibės yra C lygties sprendiniai, lygus nuliui. Visada galite atsižvelgti 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

Šiuo atveju galime pereiti prie lygiavertės lygties:

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

Apsvarstykite k sistemą logines lygtis:

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

F 2 (x 1, x 2, …x n) = 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 jungtį:

Ф = F 1 ˄ F 2 ˄ … F k

Jei kintamųjų skaičius mažas, pavyzdžiui, mažesnis nei 5, tuomet nesunku sukonstruoti funkcijos Ф tiesos lentelę, leidžiančią pasakyti, kiek sprendinių turi sistema ir kokios yra sprendimus pateikiančios aibės.

Kai kuriose USE problemose ieškant sprendimų loginių lygčių sistemai kintamųjų skaičius siekia 10. Tada tiesos lentelės sudarymas tampa beveik neįmanomu uždaviniu. Problemos sprendimas reikalauja kitokio požiūrio. Savavališkai lygčių sistemai nėra kito bendro metodo, išskyrus surašymą, kuris leistų išspręsti tokias problemas.

Egzamino metu siūlomose problemose dažniausiai sprendžiama atsižvelgiant į lygčių sistemos specifiką. Kartoju, neskaitant visų kintamųjų rinkinio parinkčių išbandymo, 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 sudarę 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.

Paaiškinsiu, kas yra dvejetainis sprendimų medis ir kaip jis kuriamas, naudodamas kelių problemų pavyzdžius.

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ų reprezentuoja loginių funkcijų jungtį. Taip pat yra atvirkščiai: sąlygų konjunkcija gali būti laikoma 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 yra teisinga. Kadangi lygtis nurodo implikaciją, šaka, kurios X 1 reikšmė yra 1, reikalauja, kad toje šakoje X 2 būtų 1. Šaka, kurios X 1 reikšmė yra 0, sukuria dvi šakas, kurių reikšmės X 2 lygus 0 ir 1 Sukurtas medis apibrėžia tris sprendinius, kuriuose implikacija X 1 → X 2 įgyja reikšmę 1. Ant kiekvienos šakos išrašomas atitinkamas kintamųjų reikšmių rinkinys, suteikiantis lygties sprendinį.

Š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 1 reikšmę. Tokioms šakoms medžio konstrukcija tęsiasi į kitą lygį, tačiau naujų šakų neatsiranda. Viena šaka, kurioje kintamasis X 2 turi reikšmę 0, išsišakos į dvi šakas, kuriose kintamasis X 3 gaus reikšmes 0 ir 1. Taigi, kiekvienas naujos lygties pridėjimas, atsižvelgiant į jos specifiką, prideda vieną sprendimą. Pradinė 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

Vienintelis skirtumas yra tas, kad lygtis naudoja Y kintamuosius. Ši lygtis taip pat turi 6 sprendinius. Kadangi kiekvienas kintamųjų X i sprendinys gali būti derinamas su kiekvienu kintamųjų Y j sprendiniu, 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, atitinkančių visas toliau išvardytas 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 kintamuosius X ir Y.

Iš lygties X 1 → Y 1 išplaukia, kad kai X 1 reikšmė yra 1 (egzistuoja vienas toks sprendimas), tada Y 1 taip pat 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ė su X 1 lygi 0, o tokių aibių yra 5, atitinka visas 6 aibes su Y kintamaisiais. Todėl 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 pagrindinius atitikmenis, 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ė lygčiai:

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 ≡X 4)) = 0

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

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

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Atsakymas: 64

Sprendimas: pereikime nuo 10 kintamųjų prie 5 kintamųjų, įvesdami tokį kintamųjų pakeitimą:

Y1 = (X1 ≡ X 2); Y2 = (X3 ≡ X 4); Y3 = (X5 ≡ X 6); Y4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Tada pirmoji lygtis bus tokia:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Lygtį galima supaprastinti užrašant ją taip:

(Y 1 ≡ Y 2) = 0

Pereinant prie tradicinės formos, sistemą rašome 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 kiekvienai Y kintamojo vertei yra 2 X kintamųjų reikšmės, todėl kiekvienas Y kintamųjų sprendimas sukuria 2 5 sprendimus X kintamuosiuose 5 sprendimai, taigi bendras sprendinių skaičius yra 64.

Kaip matote, kiekviena lygčių sistemos sprendimo problema reikalauja savo požiūrio. Įprasta technika yra atlikti lygiavertes transformacijas, kad būtų supaprastintos lygtys. Įprasta technika yra sprendimų medžių kūrimas. Naudojamas 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 (true). Dažnai siūlomose problemose nereikia kurti pilno sprendimų medžio, nes jau Pradinis etapas galima nustatyti naujų šakų atsiradimo modelį kiekviename paskesniame lygyje, kaip buvo padaryta, pavyzdžiui, 18 uždavinyje.

Apskritai problemos, susijusios su loginių lygčių sistemos sprendimų paieška, yra geri matematiniai pratimai.

Jeigu problemą sunku išspręsti rankiniu būdu, tuomet sprendimą galite patikėti kompiuteriui parašydami atitinkamą lygčių ir lygčių sistemų sprendimo programą.

Parašyti tokią programą nėra sunku. Tokia programa lengvai susidoros su visomis vieningo valstybinio egzamino užduotimis.

Kad ir kaip būtų keista, užduotis surasti loginių lygčių sistemų sprendimus kompiuteriui yra sunki, ir pasirodo, kad kompiuteris turi savo ribas. Kompiuteris gali gana lengvai susidoroti su užduotimis, kuriose kintamųjų skaičius yra 20–30, tačiau jis pradės ilgai galvoti apie problemas didesnio dydžio. Faktas yra tas, kad funkcija 2 n, nurodanti aibių skaičių, yra eksponentinė, kuri sparčiai auga, kai n didėja. Taip greitai, kad paprastas asmeninis kompiuteris negali susidoroti su užduotimi, kuri turi 40 kintamųjų per dieną.

Programa C# kalba loginėms lygtims spręsti

Programą, skirtą loginėms lygtims spręsti, rašyti naudinga dėl daugelio priežasčių, jau vien todėl, kad galite ją naudoti norėdami patikrinti savo Unified State Exam testo problemų sprendimo teisingumą. Kita priežastis – tokia programa yra puikus programavimo užduoties, atitinkančios Vieningo valstybinio egzamino C kategorijos užduočių reikalavimus, pavyzdys.

Programos kūrimo idėja yra paprasta - ji pagrįsta visapusiška visų galimų kintamųjų reikšmių rinkinių paieška. Kadangi tam tikrai loginei lygčiai ar lygčių sistemai yra žinomas kintamųjų skaičius n, tai žinomas ir aibių skaičius - 2 n, kurias reikia surūšiuoti. Naudojant pagrindines C# kalbos funkcijas – neigimą, disjunkciją, konjunkciją ir tapatybę, 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 sukurti kilpą pagal aibių skaičių, ciklo turinyje, naudojant aibės numerį, suformuoti patį aibę, apskaičiuoti šio rinkinio funkcijos reikšmę ir, jei tai reikšmė yra 1, tada aibė pateikia lygties sprendimą.

Vienintelis sunkumas, kylantis įgyvendinant programą, yra susijęs su užduotimi sukurti kintamųjų reikšmių rinkinį pagal nustatytą skaičių. Šios problemos grožis yra tas, kad ši iš pažiūros sudėtinga užduotis iš tikrųjų susiveda į paprastą problemą, kuri jau daug kartų iškilo. 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 sudėtinga užduotis gauti kintamųjų reikšmių rinkinį pagal nustatytą skaičių sumažinama iki žinomos užduoties konvertuoti skaičių į dvejetainį.

Štai kaip atrodo C# funkcija, kuri išsprendžia mūsų problemą:

///

/// sprendinių skaičiavimo programa

/// loginė lygtis (lygčių sistema)

///

/// loginė funkcija – metodas,

/// kurio parašą nurodo DF delegatas

///

/// kintamųjų skaičius

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

//Užbaikite paiešką pagal rinkinių skaičių

už (int i = 0; i< m; i++)

//Kito rinkinio formavimas - rinkinys,

//nurodomas dvejetainiu skaičiaus i vaizdu

už (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Apskaičiuokite funkcijos reikšmę rinkinyje

Norint suprasti programą, tikiuosi pakaks programos idėjos paaiškinimų ir komentarų jos tekste. Aš sutelksiu dėmesį tik į pateiktos funkcijos pavadinimo paaiškinimą. Funkcija SolveEquations turi du įvesties parametrus. Funkcijos parametras nurodo loginę funkciją, atitinkančią sprendžiamą lygtį arba lygčių sistemą. Parametras n nurodo įdomių kintamųjų skaičių. Dėl to funkcija SolveEquations grąžina loginės funkcijos sprendinių skaičių, tai yra tų rinkinių, kuriuose funkcija įvertina kaip tiesa, skaičių.

Moksleiviams įprasta, kai kuri nors funkcija F(x) įvesties parametras x yra aritmetinio, eilutės arba loginio tipo kintamasis. Mūsų atveju naudojamas galingesnis dizainas. Funkcija SolveEquations reiškia aukštesnės eilės funkcijas – F(f) tipo funkcijas, kurių parametrai gali būti ne tik paprasti kintamieji, bet ir funkcijos.

Funkcijų klasė, kurią galima perduoti kaip parametrą funkcijai SolveEquations, nurodyta taip:

deleguoti bool DF(bool vars);

Šiai klasei priklauso visos funkcijos, 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ę.

Galiausiai, čia yra programa, kuri naudoja SolveEquations funkciją, kad išspręstų kelias loginių lygčių sistemas. Funkcija SolveEquations yra toliau pateiktos ProgramCommon klasės dalis:

klasės ProgramCommon

deleguoti bool DF(bool vars);

statinė tuštuma Pagrindinis (eilutės args)

Console.WriteLine("Ir funkcijos - " +

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

statinis bool Fun53 (bool 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:
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
Pateikiamas tiesos lentelės fragmentas:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Kurią iš trijų funkcijų šis fragmentas atitinka:

(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 lemia tris kartus galva. Apibrėžkite loginę funkciją, apibūdinančią X išmokėjimą.
Žodžiai sakinyje numeruojami pradedant nuo vieno. Sakinys laikomas teisingai sudarytu, jei laikomasi šių taisyklių:
1. Jei lyginis žodis baigiasi balse, tai kitas žodis, jei toks yra, turi prasidėti balse.
2. Jei nelyginis žodis baigiasi priebalsiu, tai kitas žodis, jei toks yra, turi prasidėti priebalsiu ir baigtis balse.
  Kuris iš šių sakinių yra teisingai sudarytas:
3. Mama nuplovė Mašą su muilu.
4. Lyderis visada yra modelis.
5. Tiesa yra gerai, bet laimė yra geriau.
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 į problemas:

Funkcijos b ir c yra lygiavertės.
Fragmentas atitinka funkciją b.
Tegu loginis kintamasis P įgyja reikšmę 1, kai komisijos pirmininkas balsuoja „už“ sprendimą. Kintamieji M 1 ir M 2 atspindi žiuri narių nuomonę. Loginė funkcija, nurodanti teigiamo sprendimo priėmimą, gali būti parašyta taip:
P ˄ (M 1 ˅ M 2)
Tegul loginis kintamasis P i įgauna reikšmę 1, kai i-asis monetos metimas patenka ant galvų. Loginė funkcija, nurodanti išmokėjimą 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))
Sakinys b.
Lygtis turi 3 sprendinius: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Tegul yra n kintamųjų loginė funkcija. Loginė lygtis atrodo taip:

Konstantos C reikšmė yra 1 arba 0.

Loginė lygtis gali turėti nuo 0 iki skirtingų sprendinių. Jei C lygus 1, tai sprendiniai yra visos tos tiesos lentelės kintamųjų aibės, kurių funkcija F įgyja reikšmę true (1). Likusios aibės yra lygties, kai C lygus nuliui, sprendiniai. Visada galite atsižvelgti tik į formos lygtis:

Iš tiesų, tegul bus pateikta lygtis:

Šiuo atveju galime pereiti prie lygiavertės lygties:

Apsvarstykite k loginių lygčių sistemą:

Jei kintamųjų skaičius mažas, pavyzdžiui, mažesnis nei 5, tuomet nesunku sukonstruoti funkcijos tiesos lentelę, leidžiančią pasakyti, kiek sprendinių turi sistema ir kokios yra sprendimus pateikiančios aibės.

Egzamino metu siūlomose problemose dažniausiai sprendžiama atsižvelgiant į lygčių sistemos specifiką. Kartoju, neskaitant visų kintamųjų rinkinio parinkčių išbandymo, 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.

Paaiškinsiu, kas yra dvejetainis sprendimų medis ir kaip jis kuriamas, naudodamas kelių problemų pavyzdžius.

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ų reprezentuoja loginių funkcijų jungtį. 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. Taip 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į. 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 įvertinama kaip teisinga. Kadangi lygtis nurodo implikaciją, šaka, kurios reikšmė yra 1, reikalauja, kad šioje šakoje būtų 1 reikšmė. Šaka, kurios reikšmė 0, sukuria dvi šakas, kurių reikšmės yra lygios 0 ir 1. medis nurodo tris sprendinius, iš kurių implikacija įgyja reikšmę 1. Ant kiekvienos šakos išrašomas atitinkamas kintamųjų reikšmių rinkinys, suteikiantis 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. Viena šaka, kurioje kintamojo reikšmė yra 0, išsišakos į dvi šakas, kuriose kintamasis gaus 0 ir 1 reikšmes. Taigi, kiekviena 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ą:

Vienintelis skirtumas yra tas, kad lygtis naudoja Y kintamuosius. Ši lygtis taip pat turi 6 sprendinius. Kadangi kiekvienas kintamasis sprendimas gali būti derinamas su kiekvienu kintamu sprendimu, bendras sprendimų 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, atitinkančių visas toliau išvardytas sąlygas?

Ši užduotis yra ankstesnės užduoties modifikacija. Skirtumas tas, kad pridedama dar viena lygtis, kuri susieja kintamuosius X ir Y.

Iš lygties išplaukia, kad kai reikšmė yra 1 (egzistuoja vienas toks sprendimas), tada jis turi reikšmę 1. Taigi, yra vienas rinkinys, kuriame ir kurių reikšmės yra 1. Kai lygi 0, ji gali turėti bet kokią reikšmę, tiek 0, tiek ir 1. Todėl kiekviena aibė su , 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 pagrindinius atitikmenis, rašome savo lygtį taip:

Ciklinė implikacijų grandinė reiškia, kad kintamieji yra identiški, todėl mūsų lygtis yra lygiavertė lygčiai:

Š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?

Paslaugos paskirtis. Internetinė skaičiuoklė skirta tiesos lentelės konstravimas loginei išraiškai.
Tiesos lentelė – lentelė, kurioje yra visos galimos įvesties kintamųjų deriniai ir juos atitinkančios išvesties reikšmės.
Tiesos lentelėje yra 2n eilučių, kur n yra įvesties kintamųjų skaičius, o n+m yra stulpeliai, kur m yra išvesties kintamieji.

Instrukcijos. Įvesdami klaviatūra, naudokite šiuos susitarimus:

Pavyzdžiui, loginė išraiška abc+ab~c+a~bc turi būti įvesta taip: a*b*c+a*b=c+a=b*c
Norėdami įvesti duomenis loginės diagramos pavidalu, naudokite šią paslaugą.

Loginės funkcijos įvedimo taisyklės

Vietoj v (disjunkcijos, ARBA) simbolio naudokite ženklą +.
Prieš loginę funkciją nereikia nurodyti funkcijos pavadinimo. Pavyzdžiui, vietoj F(x,y)=(x|y)=(x^y) reikia tiesiog įvesti (x|y)=(x^y) .
Didžiausias kintamųjų skaičius yra 10.

Kompiuterinių loginių grandinių projektavimas ir analizė atliekama naudojant specialią matematikos šaką – loginę algebrą. Logikos algebroje galima išskirti tris pagrindines logines funkcijas: „NE“ (neigimas), „AND“ (junginys), „ARBA“ (disjunkcija).
Norint sukurti bet kokį loginį įrenginį, būtina nustatyti kiekvieno išvesties kintamojo priklausomybę nuo esamų įvesties kintamųjų ši priklausomybė vadinama perjungimo funkcija arba loginės algebros funkcija.
Loginė algebros funkcija vadinama visiškai apibrėžta, jei pateikiamos visos 2n jos reikšmės, kur n yra išvesties kintamųjų skaičius.
Jei apibrėžtos ne visos reikšmės, funkcija vadinama iš dalies apibrėžta.
Įrenginys vadinamas loginiu, jei jo būsena aprašoma naudojant loginės algebros funkciją.
Loginei algebros funkcijai pavaizduoti naudojami šie metodai:
Algebrine forma galite sukurti loginio įrenginio grandinę naudodami loginius elementus.

1 paveikslas – loginio įrenginio schema

Visi logikos algebros veiksmai yra apibrėžti tiesos lenteles vertybes. Tiesos lentelė nustato operacijos rezultatą visi yra įmanoma x pradinių teiginių loginės reikšmės. Parinkčių, atspindinčių operacijų taikymo rezultatą, skaičius priklausys nuo teiginių skaičiaus loginėje išraiškoje. Jei teiginių skaičius loginėje išraiškoje yra N, tada tiesos lentelėje bus 2 N eilučių, nes yra 2 N skirtingų galimų argumentų reikšmių kombinacijų.

Operacija NOT – loginis neigimas (inversija)

Loginė operacija NĖRA taikoma vienam argumentui, kuris gali būti paprasta arba sudėtinga loginė išraiška. Operacijos rezultatas NĖRA toks:

jei pradinė išraiška teisinga, tai jos neigimo rezultatas bus klaidingas;
jei pradinė išraiška klaidinga, tada jos neigimo rezultatas bus teisingas.

Neigimo operacijai NĖRA priimtinos šios sutartys:
ne A, Ā, ne A, ¬A, !A
Neigimo operacijos rezultatas NĖRA nustatomas pagal šią tiesos lentelę:

A	ne A
0	1
1	0

Neigimo operacijos rezultatas yra teisingas, kai pradinis teiginys yra klaidingas, ir atvirkščiai.

ARBA operacija – loginis sudėjimas (atskyrimas, sujungimas)

Loginė ARBA operacija atlieka dviejų teiginių, kurie gali būti paprasta arba sudėtinga loginė išraiška, sujungimo funkciją. Teiginiai, kurie yra loginės operacijos pradžios taškai, vadinami argumentais. Operacijos ARBA rezultatas yra išraiška, kuri bus teisinga tada ir tik tada, kai bent viena iš pradinių išraiškų yra teisinga.
Naudojami pavadinimai: A arba B, A V B, A arba B, A||B.
ARBA operacijos rezultatas nustatomas pagal šią tiesos lentelę:
Operacijos ARBA rezultatas yra teisingas, kai A yra teisingas, arba B yra teisingas, arba A ir B yra teisingi, ir klaidingas, kai argumentai A ir B yra klaidingi.

Operacija AND – loginis dauginimas (jungtukas)

Loginė operacija IR atlieka dviejų teiginių (argumentų) susikirtimo funkciją, kuri gali būti paprasta arba sudėtinga loginė išraiška. Operacijos IR rezultatas yra išraiška, kuri bus teisinga tada ir tik tada, kai teisingos abi pradinės išraiškos.
Naudojami pavadinimai: A ir B, A Λ B, A ir B, A ir B.
Operacijos IR rezultatas nustatomas pagal šią tiesos lentelę:

A	B	A ir B
0	0	0
0	1	0
1	0	0
1	1	1

Operacijos IR rezultatas teisingas tada ir tik tada, kai teiginiai A ir B yra teisingi, o visais kitais atvejais klaidingi.

Operacija „IF-THEN“ – loginė pasekmė (implikacija)

Ši operacija sujungia dvi paprastas logines išraiškas, iš kurių pirmoji yra sąlyga, o antroji yra šios sąlygos pasekmė.
Naudojami pavadinimai:
jei A, tai B; A reiškia B; jei A, tai B; A → B.
Tiesos lentelė:

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

Implikacijos operacijos rezultatas klaidingas tik tuo atveju, jei prielaida A yra teisinga, o išvada B (pasekmė) yra klaidinga.

Operacija „A tada ir tik jei B“ (lygiavertiškumas, lygiavertiškumas)

Naudojamas pavadinimas: A ↔ B, A ~ B.
Tiesos lentelė:

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

Operacija „Addition modulo 2“ (XOR, išskirtinė arba griežta disjunkcija)

Naudojamas žymėjimas: A XOR B, A ⊕ B.
Tiesos lentelė:

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

Ekvivalentiškumo operacijos rezultatas teisingas tik tuo atveju, jei A ir B yra teisingi arba klaidingi tuo pačiu metu.

Loginių operacijų prioritetas

Veiksmai skliausteliuose
Inversija
Jungtukas (&)
Disjunkcija (V), išskirtinis ARBA (XOR), 2 modulio suma
Potekstė (→)
Ekvivalentiškumas (↔)

Tobula disjunkcinė normali forma

Tobula disjunkcinė normalioji formulės forma(SDNF) yra lygiavertė formulė, kuri yra elementariųjų jungtukų disjunkcija ir turi šias savybes:

Kiekvienas formulės loginis narys turi visus kintamuosius, įtrauktus į funkciją F(x 1,x 2,...x n).
Visi loginiai formulės terminai yra skirtingi.
Nė viename loginiame termine nėra kintamojo ir jo neigimo.
Joks loginis formulės terminas neturi to paties kintamojo du kartus.

SDNF galima gauti naudojant tiesos lenteles arba lygiavertes transformacijas.
Kiekvienai funkcijai SDNF ir SCNF yra unikaliai apibrėžti iki permutacijos.

Tobula konjunktyvinė normali forma

Tobula jungtinė normalioji formulės forma (SCNF) Tai jai lygiavertė formulė, kuri yra elementariųjų disjunkcijų konjunkcija ir tenkina savybes:

Visose elementariosiose disjunkcijose yra visi kintamieji, įtraukti į funkciją F(x 1 ,x 2 ,...x n).
Visos elementarios disjunkcijos yra skirtingos.
Kiekviena elementari disjunkcija turi kintamąjį vieną kartą.
Nė viename elementariame disjunkcijoje nėra kintamojo ir jo neigimo.

Galite pasirinkti įvairių būdų loginių lygčių sistemų sprendimas. Tai redukcija į vieną lygtį, tiesos lentelės konstravimas ir skaidymas.

Užduotis: Išspręskite loginių lygčių sistemą:

Pasvarstykime redukcinis metodas į vieną lygtį . Šis metodas apima loginių lygčių transformavimą taip, kad jų dešinės pusės būtų lygios tiesos vertei (ty 1). Norėdami tai padaryti, naudokite loginio neigimo operaciją. Tada, jei lygtyse yra sudėtingų loginių operacijų, jas pakeičiame pagrindinėmis: „IR“, „ARBA“, „NE“. Kitas žingsnis – sujungti lygtis į vieną, lygiavertę sistemai, naudojant loginę operaciją „IR“. Po to gautą lygtį turėtumėte transformuoti pagal loginės algebros dėsnius ir gauti konkretų sistemos sprendimą.

1 sprendimas: Taikykite inversiją abiejose pirmosios lygties pusėse:

Įsivaizduokime pasekmes per pagrindines operacijas „ARBA“ ir „NE“:

Kadangi kairiosios lygčių pusės yra lygios 1, galime jas sujungti naudodami operaciją „IR“ į vieną lygtį, kuri yra lygiavertė pradinei sistemai:

Mes atidarome pirmąjį skliaustą pagal De Morgano dėsnį ir transformuojame gautą rezultatą:

Gauta lygtis turi vieną sprendinį: A =0, B=0 ir C=1.

Kitas metodas yra tiesos lentelių kūrimas . Kadangi loginiai dydžiai turi tik dvi reikšmes, galite tiesiog peržiūrėti visas parinktis ir rasti tarp jų tuos, kuriems tenkinama nurodyta lygčių sistema. Tai yra, mes sudarome vieną bendrą tiesos lentelę visoms sistemos lygtims ir randame eilutę su reikiamomis reikšmėmis.

2 sprendimas: Sukurkime sistemos tiesos lentelę:








0	0	1	1	0	1

Eilutė, kuriai įvykdytos užduoties sąlygos, paryškinta pusjuodžiu šriftu. Taigi A = 0, B = 0 ir C = 1.

Būdas skilimas . Idėja yra nustatyti vieno iš kintamųjų reikšmę (nustatykite ją 0 arba 1) ir taip supaprastinti lygtis. Tada galite pataisyti antrojo kintamojo reikšmę ir pan.

3 sprendimas: Tegul A = 0, tada:

Iš pirmosios lygties gauname B = 0, o iš antrosios - C = 1. Sistemos sprendimas: A = 0, B = 0 ir C = 1.

Vieningame informatikos valstybiniame egzamine labai dažnai reikia nustatyti loginių lygčių sistemos sprendinių skaičių, nerandant pačių sprendinių, tam yra ir tam tikrų metodų. Pagrindinis būdas rasti loginių lygčių sistemos sprendinių skaičių yrapakeičiant kintamuosius. Pirmiausia turite kiek įmanoma supaprastinti kiekvieną lygtį remiantis loginės algebros dėsniais, o tada pakeisti sudėtingas lygčių dalis naujais kintamaisiais ir nustatyti sprendinių skaičių. nauja sistema. Tada grįžkite į pakeitimą ir nustatykite jo sprendimų skaičių.

Užduotis: Kiek sprendinių turi lygtis (A →B) + (C →D) = 1? Kur A, B, C, D yra loginiai kintamieji.

Sprendimas:Įveskime naujus kintamuosius: X = A →B ir Y = C →D. Atsižvelgiant į naujus kintamuosius, lygtis bus parašyta taip: X + Y = 1.

Disjunkcija teisinga trimis atvejais: (0;1), (1;0) ir (1;1), o X ir Y yra implikacijos, tai yra, tiesa trimis atvejais, o klaidinga vienu. Todėl atvejis (0;1) atitiks tris galimas parametrų kombinacijas. Atvejis (1;1) – atitiks devynias galimas pradinės lygties parametrų kombinacijas. Taigi, iš viso galimi sprendimaišios lygties 3+9=15.

Kitas būdas nustatyti loginių lygčių sistemos sprendinių skaičių yra dvejetainis medis. Pažvelkime į šį metodą naudodami pavyzdį.

Užduotis: Kiek skirtingų sprendinių turi loginių lygčių sistema:

Pateikta lygčių sistema yra lygiavertė lygčiai:

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

Apsimeskime tai x 1 – tiesa, tada iš pirmosios lygties gauname tai x 2 taip pat tiesa, nuo antrojo - x 3 =1 ir taip toliau iki x m= 1. Tai reiškia, kad aibė (1; 1; …; 1) iš m vienetų yra sistemos sprendimas. Leisk tai dabar x 1 =0, tada iš pirmosios lygties turime x 2 =0 arba x 2 =1.

Kada x 2 tiesa, gauname, kad likę kintamieji taip pat yra teisingi, tai yra, aibė (0; 1; ...; 1) yra sistemos sprendimas. At x 2 =0 mes tai gauname x 3 =0 arba x 3 = ir taip toliau. Tęsdami paskutinį kintamąjį, matome, kad lygties sprendiniai yra šios kintamųjų rinkiniai (m +1 sprendimas, kiekviename sprendinyje yra m kintamųjų reikšmių):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Šį požiūrį gerai iliustruoja dvejetainio medžio sukūrimas. Galimų sprendimų skaičius – tai skirtingų sukonstruoto medžio šakų skaičius. Nesunku pastebėti, kad jis lygus m +1.

	Medis	Sprendimų skaičius
x 1
x 2
x 3
		…

Iškilus sunkumų samprotaujant tyrimai ir statybasprendimų, su kuriais galite ieškoti sprendimo naudojant tiesos lenteles, vienai ar dviem lygtims.

Perrašykime lygčių sistemą į formą:

Ir sukurkime tiesos lentelę atskirai vienai lygčiai:

x 1	x 2	(x 1 → x 2)

Sukurkime dviejų lygčių tiesos lentelę:

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

Pamokos tema: Logikos lygčių sprendimas

Mokomasis – studijuoti loginių lygčių sprendimo metodus, lavinti loginių lygčių sprendimo ir loginės išraiškos konstravimo įgūdžius naudojant tiesos lentelę;

Vystomasis – sudaryti sąlygas vystymuisi pažintinis susidomėjimas mokinius, skatinti lavinti atmintį, dėmesį, loginį mąstymą;

Švietimo : skatinti gebėjimą įsiklausyti į kitų nuomonę, ugdant valią ir užsispyrimą siekiant galutinių rezultatų.

Pamokos tipas: kombinuota pamoka

Įranga: kompiuteris, multimedijos projektorius, pristatymas 6.

Per užsiėmimus

Pagrindinių žinių kartojimas ir atnaujinimas. Namų darbų tikrinimas (10 minučių)

Ankstesnėse pamokose susipažinome su pagrindiniais loginės algebros dėsniais ir išmokome šiuos dėsnius panaudoti loginėms išraiškoms supaprastinti.

Patikrinkime namų darbus, kaip supaprastinti logines išraiškas:

1. Kuris iš šių žodžių atitinka loginę sąlygą:

(pirmos raidės priebalsis → antrosios raidės priebalsis)٨ (paskutinės raidės balsis → priešpaskutinės raidės balsis)? Jei tokių žodžių yra keli, nurodykite mažiausią iš jų.

1) ANNA 2) MARIJA 3) OLEGAS 4) STEPANAS

Įveskime tokį užrašą:

A – pirmosios raidės priebalsis

B – antrosios raidės priebalsis

S – paskutinės raidės balsis

D – priešpaskutinė balsės raidė

Padarykime išraišką:

Padarykime lentelę:

2. Nurodykite, kuri loginė išraiška atitinka išraišką

Supaprastinkime pradinės išraiškos ir siūlomų parinkčių įrašymą:

3. Pateiktas F išraiškos tiesos lentelės fragmentas:

Kuri išraiška atitinka F?

Nustatykime šių išraiškų reikšmes nurodytoms argumentų reikšmėms:

Įvadas į pamokos temą, naujos medžiagos pristatymas (30 minučių)

Mes ir toliau studijuojame logikos pagrindus, o šiandienos pamokos tema yra „Loginių lygčių sprendimas“. Išstudijavę šią temą, išmoksite pagrindinių loginių lygčių sprendimo būdų, įgysite šių lygčių sprendimo įgūdžių naudojant loginės algebros kalbą ir gebėsite sudaryti loginę išraišką tiesos lentele.

1. Išspręskite loginę lygtį

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

Atsakymą parašykite kaip keturių simbolių eilutę: kintamųjų K, L, M ir N reikšmės (ta tvarka). Taigi, pavyzdžiui, 1101 eilutė atitinka tai, kad K=1, L=1, M=0, N=1.

Sprendimas:

Pakeiskime išraišką(¬K  M) → (¬L  M  N)

Išraiška yra klaidinga, kai abu terminai yra klaidingi. Antrasis narys lygus 0, jei M =0, N =0, L =1. Pirmajame termine K = 0, nes M = 0, ir
.

Atsakymas: 0100

2. Kiek sprendinių turi lygtis (atsakyme nurodykite tik skaičių)?

Sprendimas: transformuokite išraišką

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

A +B =1 ir C +D =1

2 metodas: tiesos lentelės sudarymas

3 būdas: SDNF konstrukcija – tobula funkcijos disjunkcinė normalioji forma – visiškų taisyklingų elementariųjų jungtukų disjunkcija.

Transformuokime pradinę išraišką, atidarykime skliaustus, kad gautume jungtukų disjunkciją:

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

Papildykime jungtukus iki užbaigtų jungtukų (visų argumentų sandauga), atidarykite skliaustus:

Atsižvelkime į tuos pačius jungtukus:

Dėl to gauname SDNF, kuriame yra 9 jungtukai. Todėl šios funkcijos tiesos lentelė turi reikšmę 1 9 eilutėse iš 2 4 =16 kintamųjų reikšmių rinkinių.

3. Kiek sprendinių turi lygtis (atsakyme nurodykite tik skaičių)?

Supaprastinkime išraišką:

3 būdas: SDNF statyba

Atsižvelkime į tuos pačius jungtukus:

Dėl to gauname SDNF, kuriame yra 5 jungtukai. Todėl šios funkcijos tiesos lentelė turi reikšmę 1 5 eilutėse iš 2 4 =16 kintamųjų reikšmių rinkinių.

Loginės išraiškos konstravimas naudojant tiesos lentelę:

kiekvienai tiesos lentelės eilutei, kurioje yra 1, sudarome argumentų sandaugą, o kintamieji, lygūs 0, įtraukiami į sandaugą su neigimu, o kintamieji, lygūs 1, įtraukiami be neigimo. Norima išraiška F bus sudaryta iš gautų sandaugų sumos. Tada, jei įmanoma, ši išraiška turėtų būti supaprastinta.

Pavyzdys: pateikta išraiškos teisingumo lentelė. Sukurkite loginę išraišką.

Sprendimas:

3. Namų darbai (5 min.)

Išspręskite lygtį:

Kiek sprendinių turi lygtis (atsakyme nurodykite tik skaičių)?

Naudodamiesi duota tiesos lentele, sukonstruokite loginę išraišką ir

supaprastinti.