Loogikavõrrandisüsteemid arvutiteaduses. Loogika

Süsteemne lahendus loogilised võrrandid muutujate muutmise meetod

Muutujate muutmise meetodit kasutatakse juhul, kui mõned muutujad sisalduvad võrrandites ainult konkreetse avaldise kujul, mitte midagi muud. Siis saab seda avaldist tähistada uue muutujaga.

Näide 1

Mitu erinevat loogiliste muutujate x1, x2, x3, x4, x5, x6, x7, x8 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

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

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

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

Vastuses ei pea loetlema kõiki muutujate x1, x2, x3, x4, x5, x6, x7, x8 erinevaid väärtuste komplekte, mille alusel see võrdsussüsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Seejärel saab süsteemi kirjutada ühe võrrandina:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunktsioon on 1 (tõene), kui iga operandi väärtus on 1. See tähendab, kõik implikatsioonid peavad olema tõesed ja see kehtib kõigi väärtuste puhul, välja arvatud (1 → 0). Need. muutujate y1, y2, y3, y4 väärtuste tabelis ei tohi ühik olla nullist vasakul:

Need. tingimused on täidetud 5 komplekti y1-y4 puhul.

Sest y1 = x1 → x2, siis saavutatakse väärtus y1 = 0 ühel hulgal x1, x2: (1, 0) ja väärtus y1 = 1 saavutatakse kolmel hulgal x1, x2: (0,0) , ( 0,1), (1,1). Samamoodi y2, y3, y4 jaoks.

Kuna muutuja y1 iga hulk (x1,x2) kombineeritakse muutuja y2 iga komplektiga (x3,x4) ja nii edasi, korrutatakse muutujate x hulkade arv:

				Komplektide arv x1…x8 kohta

Liidame komplektide arvu: 1 + 3 + 9 + 27 + 81 = 121.

Vastus: 121

Näide 2

Mitu erinevat tõeväärtuste muutujate x1, x2, ... x9, y1, y2, ... y9 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

Vastuseks pole tarvis loetlege kõik muutujate x1, x2, ... x9, y1, y2, ... y9 erinevad väärtuste komplektid, mille korral antud võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

Teeme muutujate muudatuse:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Süsteemi saab kirjutada ühe võrrandina:

(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)

Ekvivalentsus on tõene ainult siis, kui mõlemad operandid on võrdsed. Selle võrrandi lahendused on kaks komplekti:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Sest zi = (xi ≡ yi), siis väärtus zi = 0 vastab kahele hulgale (xi,yi): (0,1) ja (1,0) ning väärtus zi = 1 vastab kahele hulgale (xi,yi) ): (0 ,0) ja (1,1).

Siis vastab esimene hulk z1, z2,…, z9 2 9 komplektile (x1,y1), (x2,y2),…, (x9,y9).

Sama number vastab teisele hulgale z1, z2,…, z9. Siis on kokku 2 9 +2 9 = 1024 komplekti.

Vastus: 1024

Loogikavõrrandisüsteemide lahendamine rekursiooni visuaalse definitsiooni abil.

Seda meetodit kasutatakse juhul, kui võrrandisüsteem on piisavalt lihtne ja hulkade arvu suurendamise järjekord muutujate lisamisel ilmne.

Näide 3

Kui palju erinevaid lahendeid on võrrandisüsteemil

¬x9 ∨ x10 = 1,

kus x1, x2, ... x10 on tõeväärtuslikud muutujad?

Vastuses ei ole vaja loetleda kõiki erinevaid väärtuste komplekte x1, x2, ... x10, mille jaoks antud võrduste süsteem kehtib. Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

Lahendame esimese võrrandi. Disjunktsioon on võrdne 1-ga, kui vähemalt üks selle operandidest on võrdne 1-ga. lahendused on komplektid:

Kui x1=0 on kaks x2 väärtust (0 ja 1) ja x1=1 puhul on ainult üks x2 väärtus (1), siis hulk (x1,x2) on võrrandi lahendus. Ainult 3 komplekti.

Lisame muutuja x3 ja vaatleme teist võrrandit. See on sarnane esimesega, mis tähendab, et x2=0 korral on x3 kaks väärtust (0 ja 1) ning x2=1 puhul on ainult üks x3 (1) väärtus, nii et komplekt ( x2,x3) on võrrandi lahend. Kokku on 4 komplekti.

On hästi näha, et teise muutuja lisamisel lisandub üks komplekt. Need. rekursiivne valem (i+1) muutujate hulkade arvu jaoks:

N i +1 = N i + 1. Siis saame kümne muutuja jaoks 11 hulka.

Vastus: 11

Erinevat tüüpi loogikavõrrandisüsteemide lahendamine

Näide 4

Mitu erinevat Boole'i ​​muutujate x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

Vastuseks pole tarvis loetlege kõik erinevad muutujate x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 väärtuste komplektid, mille korral antud võrdussüsteem on täidetud .

Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

Pange tähele, et süsteemi kolm võrrandit on erinevatel sõltumatutel muutujate kogumitel samad.

Mõelge esimesele võrrandile. Konjunktsioon on tõene (võrdne 1-ga) ainult siis, kui kõik selle operandid on tõesed (võrdsed 1-ga). Järeldus on 1 kõigis komplektides, välja arvatud (1,0). See tähendab, et esimese võrrandi lahenduseks on sellised hulgad x1, x2, x3, x4, milles 1 ei asu 0-st (5 komplekti) vasakul:

Samamoodi on teise ja kolmanda võrrandi lahendused täpselt samad y1,…,y4 ja z1,…,z4 komplektid.

Nüüd analüüsime süsteemi neljandat võrrandit: x 4 ∧ y 4 ∧ z 4 = 0. Lahenduseks on kõik hulgad x4, y4, z4, milles vähemalt üks muutujatest on võrdne 0-ga.

Need. x4 = 0 korral sobivad kõik võimalikud hulgad (y4, z4) ja x4 = 1 korral sobivad hulgad (y4, z4), mis sisaldavad vähemalt ühte nulli: (0, 0), (0,1) , ( 1, 0).

				Komplektide arv

Komplektide koguarv on 25 + 4*9 = 25 + 36 = 61.

Vastus: 61

Loogikavõrrandisüsteemide lahendamine korduvate valemite konstrueerimise teel

Korduvate valemite konstrueerimise meetodit kasutatakse keeruliste süsteemide lahendamiseks, mille puhul komplektide arvu suurendamise järjekord pole ilmne ja puu ehitamine on mahtude tõttu võimatu.

Näide 5

Mitu erinevat tõeväärtuste muutujate x1, x2, ... x7, y1, y2, ... y7 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

Vastuses ei pea loetlema kõiki muutujate x1, x2, ..., x7, y1, y2, ..., y7 erinevaid väärtuste komplekte, mille alusel antud võrdsuste süsteem kehtib. Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

Pange tähele, et süsteemi kuus esimest võrrandit on samad ja erinevad ainult muutujate hulgast. Mõelge esimesele võrrandile. Selle lahenduseks on järgmised muutujate komplektid:

Tähistage:

komplektide arv (0,0) muutujatel (x1,y1) kuni A 1 ,

komplektide arv (0,1) muutujatel (x1,y1) kuni B 1 ,

komplektide arv (1,0) muutujatel (x1,y1) C 1 kaudu,

komplektide arv (1,1) muutujatel (x1,y1) D 1 kaudu.

komplektide arv (0,0) muutujatel (x2,y2) kuni A 2 ,

komplektide arv (0,1) muutujatel (x2,y2) B ​​2 kaudu,

komplektide arv (1,0) muutujatel (x2,y2) C 2 kaudu,

komplektide arv (1,1) muutujatel (x2,y2) D 2 kaudu.

Otsuste puust näeme seda

A 1 = 0, B 1 = 1, C 1 = 1, D 1 = 1.

Pange tähele, et muutujate (x2,y2) korteež (0,0) saadakse muutujate (x1,y1) kordadest (0,1), (1,0) ja (1,1). Need. A 2 \u003d B 1 + C 1 + D 1.

Hulk (0,1) muutujatel (x2,y2) saadakse muutujate (x1,y1) hulkadest (0,1), (1,0) ja (1,1). Need. B 2 \u003d B 1 + C 1 + D 1.

Sarnaselt arutledes märgime, et C 2 \u003d B 1 + C 1 + D 1. D2 = D1.

Seega saame rekursiivsed valemid:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i + B i + C i + D i

Teeme laua

Komplektid	Sümbol.	Valem	Komplektide arv
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	Ai	Ai+1 =Bi +Ci +Di	0	3	7	15	31	63	127
(0,1)	B i	B i+1 = B i + C i + D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 = B i + C i + D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Viimane võrrand (x7 ∨ y7) = 1 on täidetud kõigi hulgaga, välja arvatud need, milles x7=0 ja y7=0. Meie tabelis on selliste komplektide arv A 7 .

Siis on komplektide koguarv B 7 + C 7 + D 7 = 127+127+1 = 255

Vastus: 255

Olgu n muutuja loogiline funktsioon. Loogiline võrrand on järgmine:

Konstandi C väärtus on 1 või 0.

Loogilisel võrrandil võib olla 0 kuni erinevate lahenditeni. Kui C on võrdne 1-ga, siis on lahendusteks kõik need tõesuse tabelist pärit muutujate hulgad, millel funktsioon F saab väärtuse tõene (1). Ülejäänud hulgad on nulliga võrdse C võrrandi lahendid. Alati võime arvestada ainult järgmise kujuga võrrandeid:

Tõepoolest, olgu võrrand antud:

Sel juhul võite minna samaväärse võrrandi juurde:

Vaatleme k loogilise võrrandi süsteemi:

Süsteemi lahendus on muutujate kogum, millel on täidetud kõik süsteemi võrrandid. Loogiliste funktsioonide osas tuleks loogikavõrrandisüsteemi lahenduse saamiseks leida hulk, millel on tõene loogiline funktsioon Ф, mis esindab algfunktsioonide konjunktsiooni:

Kui muutujate arv on väike, näiteks alla 5, siis ei ole keeruline koostada funktsioonile tõesuse tabelit, mis võimaldab öelda, mitu lahendust süsteemil on ja millised on lahendusi andvad hulgad.

Mõnes KASUTAGE ülesandeid loogikavõrrandisüsteemile lahendusi leides jõuab muutujate arv väärtuseni 10. Siis muutub tõetabeli koostamine peaaegu lahendamatuks ülesandeks. Probleemi lahendamine nõuab teistsugust lähenemist. Sest suvaline süsteem võrrandid, pole muud üldist meetodit peale loendamise, mis võimaldaks selliseid ülesandeid lahendada.

Eksamil välja pakutud ülesannetes lähtutakse enamasti võrrandisüsteemi eripärade arvestamisest. Kordan, peale muutujate komplekti kõigi variantide loetlemise pole probleemi lahendamiseks üldist viisi. Lahendus tuleb üles ehitada lähtuvalt süsteemi spetsiifikast. Sageli on kasulik läbi viia võrrandisüsteemi esialgne lihtsustamine, kasutades teadaolevaid loogikaseadusi. Veel üks kasulik tehnika selle probleemi lahendamiseks on järgmine. Meid ei huvita kõik hulgad, vaid ainult need, millel on funktsiooni väärtus 1. Täieliku tõetabeli koostamise asemel ehitame selle analoogi – binaarse otsustuspuu. Selle puu iga haru vastab ühele lahendile ja määrab hulga, millel on funktsiooni väärtus 1. Otsustuspuu harude arv langeb kokku võrrandisüsteemi lahendite arvuga.

Mis on binaarne otsustuspuu ja kuidas see on üles ehitatud, selgitan mitme ülesande näidetega.

Probleem 18

Mitu erinevat Boole'i ​​muutujate x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 väärtuste komplekti on olemas, mis rahuldavad kahe võrrandi süsteemi?

Vastus: Süsteemil on 36 erinevat lahendust.

Lahendus: võrrandisüsteem sisaldab kahte võrrandit. Leiame esimese võrrandi lahendite arvu sõltuvalt 5 muutujast - . Esimest võrrandit võib omakorda käsitleda 5 võrrandisüsteemina. Nagu näidatud, kujutab võrrandisüsteem tegelikult loogiliste funktsioonide konjunktsiooni. Tõene on ka vastupidine väide – tingimuste konjunktsiooni võib käsitleda võrrandisüsteemina.

Koostame otsustuspuu implikatsiooni () jaoks - sidesõna esimene liige, mida võib pidada esimeseks võrrandiks. Selle puu graafiline pilt näeb välja järgmine

Puu koosneb kahest tasemest vastavalt võrrandi muutujate arvule. Esimene tase kirjeldab esimest muutujat. Selle taseme kaks haru kajastavad selle muutuja võimalikke väärtusi - 1 ja 0. Teisel tasemel kajastavad puu harud ainult neid muutuja võimalikke väärtusi, mille puhul võrrand võtab tõeseks. Kuna võrrand defineerib implikatsiooni, nõuab haru, millel selle väärtus on 1, selle haru väärtust 1. Haru, mille väärtus on 0, genereerib kaks haru väärtustega 0 ja 1. Konstrueeritud puu defineerib kolm lahendit, kus implikatsioon saab väärtuse 1. Igal harul kirjutatakse välja vastav muutujate väärtuste komplekt, mis annab võrrandile lahendi.

Need komplektid on: ((1, 1), (0, 1), (0, 0))

Jätkame otsustuspuu loomist, lisades järgmise võrrandi, järgmise järelmõju. Meie võrrandisüsteemi eripära seisneb selles, et süsteemi iga uus võrrand kasutab ühte muutujat eelmisest võrrandist, lisades ühe uue muutuja. Kuna muutujal on puus juba väärtused, siis kõigil harudel, kus muutuja väärtus on 1, on muutuja väärtus ka 1. Selliste harude puhul jätkub puu ehitamine järgmisele tasemele, kuid uusi oksi ei ilmu. Ainus haru, kus muutuja väärtus on 0, annab haru kaheks haruks, kus muutuja saab väärtused 0 ja 1. Seega iga uue võrrandi lisamine, arvestades selle spetsiifilisust, lisab ühe lahendi. Algne esimene võrrand:

on 6 lahendust. Selle võrrandi täielik otsustuspuu näeb välja järgmine:

Meie süsteemi teine ​​võrrand on sarnane esimesega:

Ainus erinevus seisneb selles, et võrrandis kasutatakse muutujaid Y. Ka sellel võrrandil on 6 lahendit. Kuna iga muutujalahendust saab kombineerida iga muutujalahendusega, siis koguarv lahendusi on 36.

Pange tähele, et konstrueeritud otsustuspuu ei anna mitte ainult lahenduste arvu (vastavalt harude arvule), vaid ka lahendusi ise, mis on igale puu harule välja kirjutatud.

Probleem 19

Mitu erinevat Boole'i ​​muutujate x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

See ülesanne on eelmise ülesande modifikatsioon. Erinevus seisneb selles, et lisatakse veel üks võrrand, mis seob X- ja Y-muutujaid.

Võrrandist tuleneb, et kui selle väärtus on 1 (üks selline lahendus on olemas), siis on sellel väärtus 1. Seega on üks hulk, millel ja mille väärtused on 1. Kui see on võrdne 0-ga, võib sellel olla mis tahes väärtus, nii 0 kui ka 1. Seetõttu vastab iga hulk, mis on võrdne 0-ga ja selliseid hulki on 5, kõigile 6-le muutujatega Y. Seetõttu on lahenduste koguarv 31.

Probleem 20

Lahendus. Peamist ekvivalentsust meeles pidades kirjutame oma võrrandi järgmiselt:

Mõjutuste tsükliline ahel tähendab, et muutujad on identsed, seega on meie võrrand võrdne:

Sellel võrrandil on kaks lahendit, kui kõik on kas 1 või 0.

Probleem 21

Mitu lahendit on võrrandil:

Lahendus: nagu ülesandes 20, liigume tsüklilistest implikatsioonidest identiteetide juurde, kirjutades võrrandi ümber järgmisel kujul:

Koostame selle võrrandi jaoks otsustuspuu:

Probleem 22

Mitu lahendit on järgmisel võrrandisüsteemil?

142. Leia võrrandi suurim ühebaidine kahendlahend
.

143. Leia X, kui .

144. Lausete jada defineeritakse järgmise kordusseosega: . Väited on antud ja mõlemad on tõesed, valed. Kas väide on õige või vale? Kuidas see väljendub?

145. Mitu erinevat lahendit on loogilisel võrrandil
?

146. Mitu erinevat lahendit on loogilisel võrrandil
?

147. Mitu erinevat lahendit on loogilisel võrrandil:
.

148. Mitu erinevat lahendit on loogilisel võrrandil:.

149. Mitu erinevat lahendit on loogilisel võrrandil:.

150. Mitu erinevat lahendit on loogilisel võrrandil:.

151. Mitu erinevat lahendit on loogilisel võrrandil:
.

152. Lahenda võrrand:

153. Leia kõik erinevaid lahendusi võrrandid: .

Leidke loogilise võrrandi juured:

Leidke loogikavõrrandisüsteemide juured:

Leidke lahenduste arv järgmistele loogikavõrrandisüsteemidele:

x 3

l 2

l 3

k

M

N

Elektriahel punktide vahel M ja N koostatud vastavalt joonisel näidatud skeemile. Mõelge järgmistele neljale väitele:
A= (Keti element k korrast ära),
B i= (Keti element l i korrast ära). Kas ahel on suletud, kui:
a) väide on tõene
b) kas väide on tõene?
Kas üks neist väidetest on teise eitus?

183. (Majandusprobleem) Konstrueeri vooluring elektriahel kolmekorruselise maja sissepääsu jaoks, et mis tahes korruse lüliti saaks kogu sissepääsu valgust sisse ja välja lülitada.

184. (Avarii masin) Töökoja platsil on kolm masinat - kaks töölist, kolmas on avarii. Masinad tuleb ühendada automaatse liiniga nii, et kolmas masin lülitub sisse siis ja ainult siis, kui vähemalt üks kahest esimesest masinast peatub.

185. Olgu mõnel konkursil otsustatud ühe või teise osaleja järgmisse vooru pääsemise küsimus kolme žüriiliikme poolt: A, B, C. Otsus on positiivne siis ja ainult siis, kui vastuvõtmise poolt on vähemalt kaks žürii liiget, kelle hulgas peab olema ka žürii esimees KOOS. Hääletamiseks on vaja välja töötada seade, mille puhul iga žürii liige vajutab ühte kahest nupust - "poolt" või "vastu" ning kõigi kolme žüriiliikme hääletustulemus selgub selle järgi, kas signaaltuli põleb (otsus on tehtud) või mitte (otsust ei tehta).pirn.

186. Kolm õpetajat valivad olümpiaadiks ülesanded. Valikus on mitu ülesannet. Iga ülesande kohta avaldab iga õpetaja oma arvamust: kas kerge ülesanne (0) või raske ülesanne (1). Ülesanne arvatakse olümpiaadi ülesande hulka, kui vähemalt kaks õpetajat on selle raskeks märkinud, kuid kui kõik kolm õpetajat peavad seda raskeks, siis selline ülesanne olümpiaadi ülesande hulka liiga raskena ei kuulu. Tehke funktsionaalne diagramm seadmest, mis väljastab 1, kui ülesanne on olümpiaadi ülesandes ja 0, kui see pole kaasatud.

187. Kirjutage üles järgmise loogikaahela struktuurivalem:

&

a

b

c

f

191. Seal on ainult kaks konjunktorit ja üks inverter. Kas neid kolme loogilist elementi (väravaid) saab kasutada avaldisahelaga võrdväärse loogikalülituse tegemiseks. Mis on selle skeemi vorm?

192. Seal on ainult 1 konjunktor, 1 disjunktor ja 1 inverter. Kas neid elemente saab ühendada loogiliseks vooluringiks, mis on samaväärne loogilise avaldise ahelaga? Kõik kolm klappi tuleb kasutada. Mis on selle skeemi vorm?

Tunni teema: Loogikavõrrandite lahendamine

Haridus - loogikavõrrandite lahendamise õppimine, oskuste ja vilumuste kujundamine loogikavõrrandite lahendamiseks ning loogilise avaldise koostamiseks tõetabeli järgi;

Haridus - luua tingimused õpilaste kognitiivse huvi arendamiseks, edendada mälu, tähelepanu arengut, loogiline mõtlemine;

Hariduslik : aitab kasvatada oskust kuulata teiste arvamusi, tahte ja visaduse kasvatamine lõpptulemuste saavutamiseks.

Tunni tüüp: kombineeritud õppetund

Varustus: arvuti, multimeediaprojektor, esitlus 6.

Tundide ajal

Põhiteadmiste kordamine ja täiendamine. Uurimine kodutöö(10 minutit)

Eelmistes tundides tutvusime loogika algebra põhiseadustega, õppisime neid seadusi kasutama loogikaväljendite lihtsustamiseks.

Vaatame loogiliste avaldiste lihtsustamise kodutööd:

1. Milline järgmistest sõnadest vastab loogilisele tingimusele:

(esimene konsonant → teine ​​kaashäälik)٨ (viimase tähe vokaal → eelviimane tähtvokaal)? Kui selliseid sõnu on mitu, märkige neist väikseim.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Tutvustame tähistust:

A on kaashääliku esimene täht

B on kaashääliku teine ​​täht

S on viimane täishäälik

D - eelviimane täishäälik

Teeme väljendi:

Teeme tabeli:

2. Märkige, milline loogiline avaldis on avaldisega samaväärne

Lihtsustame algse väljendi ja pakutud valikute kirjutamist:

3. Avaldise F tõesuse tabeli fragment on antud:

Milline avaldis vastab F-le?

Määrame nende avaldiste väärtused argumentide määratud väärtuste jaoks:

Tunni teemaga tutvumine, uue materjali esitamine (30 minutit)

Jätkame loogika põhitõdede ja tänase tunni "Loogikavõrrandite lahendamine" teema uurimist. Olles õppinud see teema, õpid põhilisi loogikavõrrandite lahendamise viise, omandad oskused nende võrrandite lahendamiseks kasutades loogikalgebra keelt ja oskust koostada tõetabelil loogilist avaldist.

1. Lahendage loogiline võrrand

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

Kirjutage oma vastus neljast märgist koosneva stringina: muutujate K, L, M ja N väärtused (selles järjekorras). Nii näiteks vastab rida 1101 K=1, L=1, M=0, N=1.

Lahendus:

Teisendame väljendit(¬K  M) → (¬L  M  N)

Avaldis on väär, kui mõlemad terminid on valed. Teine liige on 0, kui M=0, N=0, L=1. Esimeses liikmes K = 0, kuna M = 0 ja
.

Vastus: 0100

2. Mitu lahendit on võrrandil (vastuses märkige ainult arv)?

Lahendus: teisenda avaldist

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

A+B=1 ja C+D=1

2. meetod: tõetabeli koostamine

3 viis: SDNF konstruktsioon - funktsiooni täiuslik disjunktiivne normaalvorm - täielike korrapäraste elementaarsidendite disjunktsioon.

Teisendame algse avaldise, avame sulud, et saada sidesõnade disjunktsioon:

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

Täiendame sidesõnu täielikeks sidesõnadeks (kõikide argumentide korrutis), avage sulud:

Mõelge samadele sidesõnadele:

Selle tulemusena saame SDNF-i, mis sisaldab 9 sidesõna. Seetõttu on selle funktsiooni tõesuse tabeli väärtus 1 9 real 2 4 =16 muutujaväärtuste komplektist.

3. Mitu lahendit on võrrandil (vastuses märkige ainult arv)?

Lihtsustame väljendit:

,

3 viis: SDNF ehitus

Mõelge samadele sidesõnadele:

Selle tulemusena saame SDNF-i, mis sisaldab 5 sidesõna. Seetõttu on selle funktsiooni tõesuse tabeli väärtus 1 5 real 2 4 =16 muutujaväärtuste komplekti.

Loogilise avaldise koostamine tõetabeli järgi:

iga 1-t sisaldava tõetabeli rea jaoks koostame argumentide korrutise ja 0-ga võrdsed muutujad kaasatakse eitusega korrutisesse ning 1-ga võrdseid muutujaid ei eitata. Soovitud avaldis F koosneb saadud toodete summast. Siis tuleks võimalusel seda väljendit lihtsustada.

Näide: on antud avaldise tõesuse tabel. Looge loogiline avaldis.

Lahendus:

3. Kodutöö (5 minutit)

Lahenda võrrand:

Mitu lahendit on võrrandil (vasta ainult arvule)?

Koosta antud tõesuse tabeli järgi loogiline avaldis ja

seda lihtsustada.

Teenindusülesanne. Interneti-kalkulaator on mõeldud loogilise avaldise tõesuse tabeli koostamine.
Tõetabel – tabel, mis sisaldab kõiki võimalikke sisendmuutujate kombinatsioone ja neile vastavaid väljundväärtusi.
Tõetabelis on 2n rida, kus n on sisendmuutujate arv ja n+m veerud, kus m on väljundmuutujad.

Juhend. Klaviatuurilt sisestamisel kasuta järgmisi kokkuleppeid: Näiteks loogiline avaldis abc+ab~c+a~bc tuleks sisestada järgmiselt: a*b*c+a*b=c+a=b*c
Andmete sisestamiseks loogilise diagrammi kujul kasutage seda teenust.

Loogikafunktsiooni sisestusreeglid

1. Kasutage v asemel + märki (disjunktsioon, VÕI).
2. Enne loogilist funktsiooni ei pea te funktsiooni tähistust täpsustama. Näiteks F(x,y)=(x|y)=(x^y) asemel tippige lihtsalt (x|y)=(x^y) .
3. Maksimaalne muutujate arv on 10.

Arvuti loogikaahelate projekteerimine ja analüüs viiakse läbi matemaatika spetsiaalse osa - loogika algebra - abil. Loogika algebras saab eristada kolme peamist loogilist funktsiooni: "EI" (eitamine), "AND" (konjunktsioon), "OR" (disjunktsioon).
Mis tahes loogilise seadme loomiseks on vaja määrata iga väljundmuutuja sõltuvus praegusest sisendmuutujast, sellist sõltuvust nimetatakse lülitusfunktsiooniks või loogikalgebra funktsiooniks.
Loogikaalgebra funktsiooni nimetatakse täielikult määratletuks, kui kõik 2 n selle väärtust on antud, kus n on väljundmuutujate arv.
Kui kõik väärtused pole määratletud, nimetatakse funktsiooni osaliselt määratletuks.
Seadet nimetatakse loogiliseks, kui selle olekut kirjeldatakse loogikaalgebra funktsiooni abil.
Loogikaalgebra funktsiooni esitamiseks kasutatakse järgmisi meetodeid:
Algebralisel kujul on võimalik loogiliste elementide abil koostada loogilise seadme diagramm.


Joonis 1 – loogilise seadme skeem

Kõik loogika algebra operatsioonid on määratletud tõetabelid väärtused. Tõelisuse tabel määrab toimingu sooritamise tulemuse kõik võimalik x algsete väidete loogilised väärtused. Toimingute rakendamise tulemust kajastavate valikute arv sõltub loogilises avaldises olevate väidete arvust. Kui loogikavaldises olevate väidete arv on N, siis tõesuse tabelis on 2 N rida, kuna võimalikke argumentide väärtusi on 2 N erinevat kombinatsiooni.

Toiming NOT – loogiline eitus (inversioon)

Loogilist operatsiooni EI rakendata ühele argumendile, mis võib olla kas lihtne või keeruline loogiline avaldis. Operatsiooni tulemus EI OLE järgmine:

• kui algne avaldis on tõene, on selle eituse tulemus väär;
• kui algne avaldis on väär, siis on selle eituse tulemus tõene.

Järgmisi kokkuleppeid EI aktsepteerita eitamistoimingu jaoks:
mitte A, Ā, mitte A, ¬A, !A
Eitustoimingu tulemus EI ole määratud järgmise tõesuse tabeliga:

A	mitte A
0	1
1	0

Eitustehte tulemus on tõene, kui algne väide on väär, ja vastupidi.

Operatsioon VÕI – loogiline liitmine (disjunktsioon, liit)

Loogiline VÕI-operatsioon täidab kahe lause kombineerimise funktsiooni, mis võib olla kas lihtne või keeruline loogiline avaldis. Avaldusi, mis on loogilise operatsiooni algsed, nimetatakse argumentideks. Operatsiooni VÕI tulemus on avaldis, mis on tõene siis ja ainult siis, kui vähemalt üks algsetest avaldistest on tõene.
Kasutatud tähistused: A või B, A V B, A või B, A||B.
VÕI-toimingu tulemus määratakse järgmise tõesuse tabeli abil:
Operatsiooni VÕI tulemus on tõene, kui A on tõene või B on tõene või A ja B on tõesed, ja väär, kui nii A kui ka B on väärad.

Tehe JA – loogiline korrutamine (konjunktsioon)

Loogikatehe JA täidab kahe väite (argumendi) lõikumisfunktsiooni, mis võib olla kas lihtne või kompleksne loogiline avaldis. Operatsiooni JA tulemus on avaldis, mis on tõene siis ja ainult siis, kui mõlemad algsed avaldised on tõesed.
Kasutatud sümbolid: A ja B, A Λ B, A & B, A ja B.
Tehte JA tulemus määratakse järgmise tõesuse tabeli abil:

A	B	A ja B
0	0	0
0	1	0
1	0	0
1	1	1

Tehte JA tulemus on tõene siis ja ainult siis, kui väited A ja B on mõlemad tõesed ja väärad kõigil muudel juhtudel.

Operatsioon "IF-THEN" - loogiline tagajärg (implikatsioon)

See toiming ühendab kaks lihtsat tõeväärtuslikud avaldised, millest esimene on tingimus ja teine ​​on selle tingimuse tagajärg.
Rakendatud nimetused:
kui A, siis B; A tõmbab B-d ligi; kui A, siis B; A → B.
Tõe tabel:

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

Tagajärje (implikatsiooni) tehte tulemus on väär ainult siis, kui eeldus A on tõene ja järeldus B (tagajärg) on ​​väär.

Toiming "A siis ja ainult siis, kui B" (ekvivalentsus, samaväärsus)

Kohaldatav tähistus: A ↔ B, A ~ B.
Tõe tabel:

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

Modulo 2 liitmisoperatsioon (XOR, eksklusiivne või range disjunktsioon)

Kasutatud tähistus: A XOR B, A ⊕ B.
Tõe tabel:

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

Ekvivalentsustehe tulemus on tõene ainult siis, kui nii A kui ka B on mõlemad tõesed või mõlemad väärad.

Loogikatehete ülimuslikkus

• Toimingud sulgudes
• Inversioon
• Sidesõna (&)
• Disjunktsioon (V), välistav VÕI (XOR), mooduli 2 summa
• Implikatsioon (→)
• Samaväärsus (↔)

Täiuslik disjunktiivne normaalvorm

Valemi täiuslik disjunktiivne normaalvorm(SDNF) on sellega samaväärne valem, mis on elementaarsidendite disjunktsioon, millel on järgmised omadused:

1. Iga valemi loogiline liige sisaldab kõiki muutujaid, mis sisalduvad funktsioonis F(x 1 ,x 2 ,...x n).
2. Kõik valemi loogilised terminid on erinevad.
3. Ükski loogiline termin ei sisalda muutujat ja selle eitust.
4. Ükski loogiline termin valemis ei sisalda sama muutujat kaks korda.

SDNF-i saab hankida kas tõetabelite või samaväärsete teisenduste abil.
Iga funktsiooni jaoks on SDNF ja SKNF üheselt määratletud kuni permutatsioonini.

Täiuslik konjunktiivne normaalvorm

Valemi täiuslik konjunktiivne normaalvorm (SKNF) on sellega samaväärne valem, mis on elementaardisjunktsioonide konjunktsioon, mis vastab järgmistele omadustele:

1. Kõik elementaardisjunktsioonid sisaldavad kõiki muutujaid, mis sisalduvad funktsioonis F(x 1 ,x 2 ,...x n).
2. Kõik elementaarsed disjunktsioonid on erinevad.
3. Iga elementaarne disjunktsioon sisaldab muutujat üks kord.
4. Ükski elementaarne disjunktsioon ei sisalda muutujat ja selle eitust.