Loogilised operatsioonid. Disjunktsioon, konjunktsioon ja eitus

Loogiline liitmine (disjunktsioon) moodustatakse kahe väite ühendamisel üheks, kasutades sidet “või”.

Vene keeles kasutatakse sidesõna “või” kahes tähenduses.

Näiteks, V ettepanek Tavaliselt kell 20 vaatan telekat või joon teed sidesõna “või” on võetud mittevälistavaks (ühendav) mõtet, kuna saad ainult telekat vaadata või ainult teed juua, aga teed juua ja telekat vaadata võib ka samal ajal, sest ema pole range. Seda operatsiooni nimetatakse mitterange disjunktsioon.(Kui mu ema oleks range, lubaks ta mul ainult televiisorit vaadata või ainult teed juua, kuid mitte ühendada söömist teleka vaatamisega.)

Avalduses Sellel tegusõnal on I või II konjugatsioon side "või"
kasutatakse eranditult (jagades) meel. Selline operatsioon
helistas range disjunktsioon.. ,. ,-> „,... > (, r>

Näited rangetest ja mitterangetest disjunktsioonidest:

avaldus	Disjunktsiooni tüüp
Petya istub staadioni lääne- või idatribüünidel	Range
Õpilane sõidab rongiga või loeb raamatut	Lax
Olyale meeldib kirjutada esseesid või lahendada loogikaülesandeid	Lax
Seryozha õpib koolis või on selle lõpetanud	Range
Homme sajab või ei saja (kolmandat valikut pole)	Range
Võitleme puhtuse eest. Puhtus saavutatakse sel viisil: kas ärge prügi või puhastage sageli	Lax
Zelia liigub ringikujulisel või elliptilisel orbiidil	Range
Numbreid saab liita või korrutada	Lax
Lapsed on kas heade kommetega või mitte meie omad	?

Nõrga disjunktsiooni märge:A VÕI IN; AVÕIIN; A| IN; A V IN; A + B.(Selles õpetuses: A V IN.)

Toome näite kahe lihtsa väite disjunktsioonist.

Oletame, et teie aknast on näha parkla, kus on tavaliselt kaks autot: Mercedes ja Žiguli, kuid neid võib olla üks või mitte.

Tähistame väiteid:

A = Parklas on Mercedes. IN= Parklas on Žiguli autod.

(A disjunktsioon B) = See on parklas "Mercedes" või "žiguli".

Peatükk 3. Loogilised tehted ____________ [___________________________ SCH

Tabel., ^"-"n..;ch; i■.■;- >i ,;,

Tõetabelist järeldub, et kahe väite disjunktsioon on väär siis ja ainult siis, kui mõlemad väited on valed, ja tõene, kui vähemalt üks väide on tõene. Mõnikord kasutatakse seda omadust disjunktsioonioperatsiooni määratlusena.

Mnemooniline reegel: disjunktsioon on loogiline liitmine ja meil pole kahtlust, et märkasite, et võrrandid 0 + 0 = 0; 0+1 = 1;1+0=1, tõene tavalise liitmise korral, kehtib ka disjunktsioonitehte puhul, kuid 1 V 1 = 1.

Sõnal "konjunktsioon" on üks täht "ja" ja sõnas "disjunktsioon" on kaks tähte "ja", nagu Ja sõnas "või".

V L-Sümbol V (disjunktsioon) on moodustatud ladinakeelse sõna Vel (“või”) esimesest tähest.

"Dis" - "märkige alla" - V.

Hulgateoorias vastab tehtele disjunktsioon ühendused komplektid.

Hulkade ühendusele vastava Euleri-Venni diagrammi koostamiseks valime tõetabeli need read, milles AvB=\. Neid on kolm. Diagrammil varjutame kolm ala, kus väärtused on AJaIN sama mis valitud ridadel. ^ _ h." " * "o L su J I J

30 ____________________________ 1. osa. Matemaatilise loogika elemendid

Graafiline illustratsioon: ».*■.

A IN A\jB- klassis palju õpilasi, kes on suurepärased õpilased või sportlased.

j Kaaluge toimingut range disjunktsioonid (eksklusiivne "või"). i Toome näite rangest disjunktsioonist.

,)■ Olgu toodud järgmised väited:

"■ A= Parklas on Mercedes.

>; B = Parklas on Žiguli autod.

i (A range disjunktsioon B) = Parklas seisab “Mvrsedve”*või

"Žiguli". v ?;;

Operatsiooni "eksklusiivne "või" kasutamine viitab sellele, et parklas võib olla kas ainult Mercedes või ainult Žiguli, ning keelab olukorra, kui parklas on korraga Mercedes ja Žiguli.

; . - "4",

Range disjunktsiooni tähis:A XOR IN; A v IN.

peatükk 3. Loogilised tehted ______________________________________ 31

Tõetabelist järeldub, et range disjunktsiooni tehte on tõene siis ja ainult siis, kui ainult üks väidetest on tõene, ja väär, kui mõlemad väited on tõesed või mõlemad on valed. Mõnikord peetakse seda omadust range disjunktsioonioperatsiooni määratluseks.

Ranget disjunktsiooni kujutav Euleri-Venni diagramm koostatakse tõetabeli abil samamoodi nagu teiste loogikatehete puhul.

Graafiline illustratsioon:

<ЗЭ

A- klassis palju suurepäraseid õpilasi; IN- klassis palju sportlasi;

A juures B- klassis palju õpilasi, kes on kas suurepärased õpilased või sportlased.

d "TUALETT. J

Loogiline tagajärg (implikatsioon) -wr™

Loogiline tagajärg (implikatsioon) moodustub kahe ühendamisel!,

väited üheks kasutades kõnekuju „kui..., See ... ». ■

Näited tagajärgedest: "

E = Kui vanne on antud, siis tuleb see täita.{

P = Kui arv jagub 9-ga, siis jagub see 3-ga. I

Loogikas on lubatud (aktsepteeritud, kokku lepitud) pidada ka mitte-.;:

väited, mis on igapäevasest vaatenurgast mõistlikud. i

Toome näiteid kohtuotsustest, mida ei arvestata mitte ainult õiguspäraselt; loogikast läbi, kuid millel on ka tähendus "tõene":

KOOS= Kui lehmad lendavad, siis 2 + 2 = 5. X = Kui- Napoleon, siis on kassil neli jalga.

Implikatsiooni tähistus:A -> B; A=e IN.(Selles õpetuses: A=» IN.) Nad ütlevad: kui A, See IN; A tähendab IN; A toob kaasa IN; IN tuleneb sellest A.

Osa 1. Matemaatilise loogika elemendid

Peatükk 3. Loogikatehted f; L.______________________________ 33

See toiming ei ole nii ilmne kui eelmised. Seda saab seletada näiteks järgmiselt.

Olgu toodud järgmised väited: .>--.< а «<, .<-. *>,w ""ihw

L A = Väljas sajab vihma.>..;; j .„ , | G,., d

B = asfalt on märg. ts

(A implikatsioon 2?) = £bш sisse Väljas sajab vihma, siis on asfalt märg.

Siis kui vihma sajab (A= 1) ja asfalt on märg (5=1), siis on see suhe
vastab tegelikkusele, st tõele. Aga kui nad sulle seda ütlevad
väljas sajab (A= 1) ja asfalt jääb kuivaks (B = 0), siis loete
sa varjad seda valedega. Aga kui väljas ei saja (A= 0), siis asfalt
võib olla nii kuiv kui märg (näiteks sõitsite just läbi a
võllimismasin). ъ. ?; t | rfl]

Tabel

Avalduse vorm: kui A, See IN,

G SOW! ,chi , T"/1

"? , L ■ Ja ". "L\ ja h > < "L

Lt S.Ch;":\0"1 "

Selgitame diagrammi ülesehitust. Oleme huvitatud implikatsiooni tõesusest, seega valime tõesuse tabeli need read, milles A=> IN= 1. Selliseid jooni on kolm. Diagrammil varjutame kolm ala, kus väärtused on A Ja IN sama mis valitud ridadel:

Tõetabelist järeldub, et kahe väite implikatsioon on väär siis ja ainult siis, kui tõesest väitest tuleneb vale väide (kui tõene eeldus viib vale järelduseni). Mõnikord võetakse seda omadust implikatsioonitehte definitsioonina.

Vaatame ühte ülaltoodud näidetest terve mõistusega vastuolus olevate tagajärgede kohta.

(A = 0)n(B = 0)

(A = 0)p (B = 1)

(L = 1)n (I = 1)

Loogiline võrdsus (ekvivalentsus)

Loogiline võrdsus (ekvivalentsus) moodustatakse kahe väite ühendamisel üheks, kasutades fraasi pööret "... siis ja ainult siis, kui ...».

Osa 1. Matemaatilise loogika elemendid^

Peatükk 3. Loogilised operatsioonid

Võrdluste näited: "

1) Nurka nimetatakse õigeks siis ja just siis, kui ta võrdub 90°.

2) Kaks sirget on paralleelsed siis ja ainult siis, kui nadära ristu..,

3) Iga materiaalne punkt säilitab puhkeseisundi või ühtlase sirgjoonelise liikumise siis ja ainult siis, kui puudub väline mõju.(Newtoni esimene seadus.)

4) Pea mõtleb siis ja alles siis, kui keel puhkab.(Nali.)

Kõik matemaatika, füüsika seadused, kõik definitsioonid on väidete samaväärsus.

Samaväärsuse tähis: A = B; A<=>IN; A ~ B.(Selles õpetuses: A O IN.)

Toome näite samaväärsuse kohta. Olgu järgmised väited:

A= Arv jagub 3-ga ilma jäägita (kolme kordsed). IN= Arvu numbrite summa jagub 3-ga.

(A samaväärne B) = Arv jagub 3-ga siis ja ainult siis
selle numbrite summa jagub 3-ga., ;

Selgitus:

A	IN	A<^В

Tõe tabel:

	Tähendus
	avaldused
Väidete tähendus	Arv on 3 kordne
A Ja IN täpsustatud jaoks< значений "*"	siis ja ainult siis
*	selle numbrite summa täielikult jagatud poolt 3
Number ei ole	Arvude summa ei ole	Tõsi
kolmekordne	kolmekordne
Number ei ole	Numbrite summa	Valetage
kolmekordne	kolmekordne
Arv on kordne	Arvude summa ei ole	Valetage
kolm	kolmekordne
Arv on kordne	Numbrite summa	Tõsi
kolm	kolmekordne

Tõetabelist järeldub, et kahe väite samaväärsus on tõene siis ja ainult siis, kui mõlemad väited on tõesed või mõlemad on valed. Mõnikord võetakse seda omadust ekvivalenttehte definitsioonina.

Hulgateoorias vastab see tehe tehtele samaväärsust komplektid.

Euleri-Venni diagrammi hulkade vastava ekvivalentsuse konstrueerimiseks valime tõesuse tabeli need read, milles A<=> IN= 1. Neid on kaks. Diagrammil varjutame kaks ala, kus väärtused on AnV sama mis valitud ridadel.

Graafiline illustratsioon: c~J_ ........ 1l...Li

Ш PÕHIMÕISTED JA MÕISTED

Loogiline toimimine- meetod keeruka väite koostamiseks etteantud väidetest, mille puhul kompleksväite tõeväärtus määratakse täielikult esialgsete väidete tõeväärtustega.

Inversioon(loogiline eitus) moodustatakse väitest, lisades predikaadile partikli “ei” või kasutades kõnekuju “pole tõsi, et...”.

Inversiooni sümbol: EI A;-. A; A; MITTE A.>"i,t

Tabel
tõde: ■■■ g -

A	A

Väite ümberpööramine on tõene, kui
näitamine on vale ja vale, kui väide
tõsi. ■--■

! t■ .■ " N ■

Osa 1. Matemaatilise loogika elemendid

G Peatükk 3. Loogikatehted

Konjunktsioon(loogiline korrutamine) moodustatakse kahe väite liitmisel üheks, kasutades sidet “ja”.

Sidesõna tähistus: A I B; A L IN; A& IN; A ■ B; A JA IN.

; (G">* „*

Samaväärsus(loogiline võrdsus) moodustatakse kahe väite liitmisel üheks, kasutades fraasi pööret “... siis ja ainult siis, kui...”.

Samaväärsuse tähis: A = B; A<=> IN; A ~ B.

Tõe tabel:

Kahe väite samaväärsus on tõene siis ja ainult siis, kui mõlemad väited on tõesed või mõlemad on valed.

Disjunktsioon(loogiline liitmine) moodustatakse ühendades kaks laused üheks, kasutades sidet "või". ,

Disjunktsiooni tähis: A VÕI IN; A\B; L V IN; A+ IN.

Tõe tabel:

Implikatsioon(loogiline tagajärg) moodustub ühenduse kaudu kaks väited üheks, kasutades kõnekuju “kui..., siis...”. Mõju tähistus: A->B;A=$B.

Põhiline kokkuvõte “Loogiliste operatsioonide omadused”

Tõe tabel:

A	IN	A^B

Kahe väite implikatsioon on vale siis ja ainult siis, kui tõesest väitest tuleneb vale väide.

Ch1ya" | ; - VI

. ..,... , .-. . kui . ............... --,-

■*}■

<Ч. 1

Seotud Informatsioon.

Loogilised operatsioonid. Disjunktsioon, konjunktsioon ja eitus

Niisiis, kuidas lihtsad loogilised väited omavahel ühendavad, et moodustada keerukaid? Loomulikus keeles kasutame erinevaid sidesõnu ja muid kõneosi. Näiteks "ja", "või", "kas", "ei", "kui", "siis", "siis". Näide keerukatest väidetest: „tal on teadmised Ja oskused", "ta saabub teisipäeval, või kolmapäeval", "Ma mängin Siis, kui ma teen kodutööd", "5 Mitte võrdub 6". Kuidas me otsustame, kas see, mis meile on öeldud, on tõsi või mitte? Kuidagi loogiliselt, isegi kuskil alateadlikult, eelnevale elukogemusele tuginedes saame aru, et tõde ühendusega “ja” esineb mõlema lihtlause tõepärasuse puhul. Kui ühest saab vale, on kogu keeruline väide vale. Kuid sidesõnaga "või" peab tõene olema ainult üks lihtne väide ja siis saab tõeseks kogu väljend.

Boole'i algebra kandis selle elukogemuse üle matemaatika aparatuuri, vormistas selle ja kehtestas ranged reeglid üheselt mõistetava tulemuse saamiseks. Ametiühinguid hakati siin nimetama loogilisteks operaatoriteks.

Loogika algebra sisaldab palju loogilisi tehteid. Kolm neist väärivad aga erilist tähelepanu, sest... nende abiga saate kirjeldada kõiki teisi ja seetõttu kasutada vooluahelate kujundamisel vähem erinevaid seadmeid. Sellised toimingud on sidesõna(JA), disjunktsioon(VÕI) ja eitus(MITTE). Sageli tähistatakse sidesõna & , disjunktsioon - || , ja eitus on väidet tähistava muutuja kohal olev riba.

Sidesõnaga tekib kompleksavaldise tõesus ainult siis, kui kõik kompleksi moodustavad lihtväljendid on tõesed. Kõigil muudel juhtudel on kompleksavaldis vale.

Disjunktsiooni korral ilmneb keerulise avaldise tõesus, kui vähemalt üks selles sisalduv lihtne avaldis on tõene või kaks korraga. Juhtub, et keeruline avaldis koosneb rohkem kui kahest lihtsast. Sel juhul piisab ühest lihtsast, et olla tõsi ja siis on kogu väide tõene.

Eitus on unaarne tehe, kuna seda tehakse seoses ühe lihtsa avaldise või kompleksse avaldise tulemusega. Eituse tulemusena saadakse uus väide, mis on vastupidine algsele.

Tõe tabelid

Loogilisi tehteid on mugav kirjeldada nn tõetabelid, mis kajastavad keerukate väidete arvutuste tulemusi algsete lihtsate väidete erinevate väärtuste jaoks. Lihtlauseid tähistatakse muutujatega (näiteks A ja B).

Arvuti loogilised alused

Arvutites kasutatakse erinevaid seadmeid, mille tööd kirjeldab suurepäraselt loogika algebra. Selliste seadmete hulka kuuluvad lülitite, päästikute, lisajate rühmad.

Lisaks peitub seos Boole'i algebra ja arvutite vahel arvutis kasutatavas numbrisüsteemis. Nagu teate, on see binaarne. Seetõttu saavad arvutiseadmed salvestada ja teisendada nii numbreid kui ka loogiliste muutujate väärtusi.

Lülitusahelad

Arvutid kasutavad paljudest lülititest koosnevaid elektriskeeme. Lüliti saab olla ainult kahes olekus: suletud ja avatud. Esimesel juhul vool läbib, teisel - mitte. Selliste ahelate toimimist on väga mugav kirjeldada loogika algebra abil. Sõltuvalt lülitite asendist võite väljunditest signaale vastu võtta või mitte.

Väravad, plätud ja lisaseadmed

Värav on loogiline element, mis võtab vastu mõned binaarväärtused ja toodab teisi sõltuvalt selle rakendamisest. Näiteks on väravad, mis rakendavad loogilist korrutamist (konjunktsiooni), liitmist (disjunktsiooni) ja eitamist.

Päästikud ja summaarid on suhteliselt keerulised seadmed, mis koosnevad lihtsamatest elementidest – väravatest.

Päästik on võimeline salvestama ühte kahendnumbrit, kuna see võib olla kahes stabiilses olekus. Päästikuid kasutatakse peamiselt protsessoriregistrites.

Summeerijaid kasutatakse laialdaselt protsessori aritmeetilises loogikaühikus (ALU) ja need teostavad kahendbittide liitmist.

Arvutite, õigemini riistvara ehitus põhineb nn ventiilid. Need on üsna lihtsad elemendid, mida saab omavahel kombineerida, luues seeläbi erinevaid skeeme. Mõned skeemid sobivad rakendamiseks aritmeetilised tehted, ja teiste põhjal ehitavad nad erinevaid mälu ARVUTI.

Ventel on seade, mis toodab sellesse sisestatud andmetest (signaalidest) Boole'i operatsiooni tulemuse.

Lihtsaim klapp on transistor-inverter, mis muundab madalpinge kõrgepingeks või vastupidi (kõrgest madalaks). Seda võib käsitleda kui loogilise nulli teisendamist loogiliseks nulliks või vastupidi. Need. saame klapi kätte MITTE.

Transistoride paari erineval viisil ühendades saadakse väravad VÕI EI Ja JA MITTE. Need väravad ei aktsepteeri enam ühte, vaid kahte või enamat sisendsignaali. Väljundsignaal on alati sama ja sõltub (toodab kõrget või madalat pinget) sisendsignaalidest. NOR-värava puhul saab kõrget pinget (loogilist) saavutada ainult siis, kui kõik sisendid on madalad. NAND-värava puhul on vastupidi: loogiline saadakse, kui kõik sisendsignaalid on nullid. Nagu näete, on see vastupidine sellistele tuttavatele loogilistele operatsioonidele nagu JA ja VÕI. Tavaliselt kasutatakse aga NAND- ja NOR-väravaid, kuna nende teostus on lihtsam: AND-NOT ja NOR-NOT realiseerivad kaks transistori, loogilist JA ja VÕI aga kolm.

Värava väljundit saab väljendada funktsioonina sisenditest.

Transistori ühest olekust teise lülitumiseks kulub väga vähe aega (lülitusaega mõõdetakse nanosekundites). Ja see on nende põhjal koostatud skeemide üks olulisi eeliseid.

Loogiliste väärtuste jaoks kasutatakse tavaliselt kolme toimingut:

Konjunktsioon– loogiline korrutamine (JA) – ja, &, ∧.
Disjunktsioon– loogiline lisamine (OR) – või, |, v.
Loogiline eitus (EI) – mitte,.

Loogilisi avaldisi saab teisendada vastavalt loogika algebra seadused:

Refleksiivsuse seadused
a ∨ a = a
a ∧ a = a
Kommutatiivsuse seadused
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Assotsiatiivsuse seadused
(a ∧ b) ∧ c = a ∧ (b ∧ c)
(a ∨ b) ∨ c = a ∨ (b ∨ c)
Jaotuse seadused
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Eituse eitamise seadus
(a) = a
De Morgani seadused
(a ∧ b) = a ∨ b
(a ∨ b) = a ∧ b
Neeldumise seadused
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a

Iga loogiline valem määratleb mõne Boole'i funktsiooni. Teisest küljest võib iga Boole'i funktsiooni jaoks kirjutada lõputult palju seda esindavaid valemeid. Loogilise algebra üks peamisi ülesandeid on leidmine kanooniliselt x vormid (st teatud reegli, kaanoni järgi konstrueeritud valemid), aga ka lihtsaimad Boole'i funktsioone esindavad valemid.

Kui loogilist funktsiooni väljendatakse muutujate disjunktsiooni, konjunktsiooni ja eituse kaudu, siis seda esitusviisi nimetatakse normaalne. Tavavormide hulgas on selliseid, milles funktsioonid on kirjutatud ainulaadsel viisil. Neid nimetatakse täiuslik.

Erilist rolli loogika algebras mängivad disjunktiivsete ja konjunktiivsete täiuslike normaalvormide klassid. Need põhinevad elementaardisjunktsiooni ja elementaarkonjunktsiooni mõistetel.

Valemit nimetatakse elementaarne side, kui see on ühe või mitme muutuja konjunktsioon koos eitusega või ilma. Vaadeldakse ühte muutujat või selle eitust ühetermiline elementaarliit.

Valemit nimetatakse elementaarne disjunktsioon, kui see on muutujate disjunktsioon (võib-olla monoomne) ja muutujate eitused.

DNF JA SDNF

Valemit nimetatakse disjunktiivne normaalvorm(DNF), kui see on mittekorduvate elementaarsidendite disjunktsioon. DNF-id on kirjutatud järgmiselt: А1 v А2 v ... v Аn, kus iga An- elementaarne sidesõna.

Valem A alates k muutujaid nimetatakse täiuslik disjunktiivne normaalvorm(SDNF), kui:
1.A on DNF, milles iga elementaarkonjunktsioon on konjunktsioon k muutujad x1, x2, …, xk, ja selle sidesõna i-ndal kohal on kas muutuja xi või selle eitamine;
2. Sellises DNF-is on kõik elementaarkonjunktsioonid paarikaupa erinevad.

Näiteks: A = x1 & MITTE x2 v x1 & x2

Täiuslik disjunktiivne normaalvorm on valem, mis on konstrueeritud rangelt määratletud reeglite järgi kuni selles sisalduvate elementaarsidendite (disjunktiivsete terminite) järjekorrani.

See on näide Boole'i funktsiooni ainulaadsest esitusest valemi (algebralise) tähise kujul.

SDNF teoreem

Lase f(x1 x2, …, xn)- Boole'i funktsioon n muutujad, mis ei ole identsed nullid. Siis on olemas täiuslik disjunktiivne normaalvorm, mis väljendab funktsiooni f.

Algoritm SDNF-i koostamiseks tõetabeli abil:

1. Tõetabelis märgime need muutujate hulgad, mille puhul funktsiooni väärtus f = 1.
2.Iga märgitud hulga kohta kirjutame kõikide muutujate konjunktsiooni järgmiselt: kui mõne muutuja väärtus selles hulgas on 1, siis arvestame konjunktsiooni muutuja enda, vastasel juhul selle eituse.
3. Ühendame kõik saadud konjunktsioonid disjunktsioonitehtega.

KNF JA SKNF

Valemit nimetatakse konjunktiivne normaalvorm(CNF), kui see on mittekorduvate elementaardisjunktsioonide konjunktsioon. CNF-id on kirjutatud järgmisel kujul: A1 & A2 & ... & An, kus iga An- elementaarne disjunktsioon.

Valem A alates k muutujaid nimetatakse täiuslik konjunktiivne normaalvorm(SKNF), kui:
1. A on CNF, milles iga elementaardisjunktsioon on disjunktsioon k muutujad x1, x2, …, xk, ja selle disjunktsiooni i-ndal kohal on kas muutuja xi või selle eitus;
2. Sellises CNF-is on kõik elementaardisjunktsioonid paarikaupa erinevad.

Näiteks: A = (x1 v MITTE x2) & (x1 v x2)

SCNF teoreem

Lase f(x1 x2, …, xn)- Boole'i funktsioon n muutujad, mis ei ole identsed nullid. Siis on olemas täiuslik konjunktiivne normaalvorm, mis väljendab funktsiooni f.

Algoritm SCNF-i koostamiseks tõetabeli abil:

1. Tõetabelis märgime need muutujate hulgad, mille puhul funktsiooni väärtus f = 0.
2. Iga märgitud hulga kohta kirjutame kõigi muutujate disjunktsiooni järgmiselt: kui mõne muutuja väärtus selles hulgas on 0, siis kaasame disjunktsiooni ka muutuja enda, vastasel juhul selle eituse.
3. Ühendame kõik saadud disjunktsioonid konjunktsioonitehtega.

SDNF-i ja SCNF-i koostamise algoritmidest järeldub, et kui enamiku muutujaväärtuste komplektide puhul on funktsioon võrdne 0-ga, siis on selle valemi saamiseks lihtsam konstrueerida SDNF-i, vastasel juhul - SCNF-i.

Loogiliste funktsioonide minimeerimine Karnaugh Mapsi abil

Karnaugh' kaart on graafiline viis lülitamise (tõve) funktsioonide minimeerimiseks, pakkudes suhteliselt lihtsat tööd suurte avaldistega ja välistades võimalikud rassid. Esindab paarikaupa mittetäieliku liimimise ja elementaarse neeldumise toiminguid. Karnaugh' kaarte peetakse funktsiooni tõesuse tabeliks, mis on vastavalt ümber paigutatud. Carnaugh' kaarte võib käsitleda kui n-mõõtmelise Boole'i kuubi spetsiifilist lamedat edasiarendust.

Carnot' kaardid leiutas 1952. aastal Edward W. Veitch ja 1953. aastal täiustas neid Bell Labsi füüsik Maurice Carnot ning need olid mõeldud digitaalsete elektrooniliste vooluringide lihtsustamiseks.

Carnaugh' kaardil kantakse tõesuse tabelist Boole'i muutujad ja järjestatakse Gray koodi abil, milles iga järgmine number erineb eelmisest vaid ühe numbri võrra.

Peamine meetod SDNF-i või SCNF-i kujul esitatud loogiliste funktsioonide minimeerimiseks on paarikaupa mittetäielik liimimine ja elementaarne neeldumine. Paariliimimine toimub kahe identseid muutujaid sisaldava termini (liikme) vahel, mille esinemised (otsene ja pöördvõrdeline) langevad kokku kõigi muutujate puhul peale ühe. Sel juhul saab sulgudest välja võtta kõik muutujad peale ühe ning liimida kokku ühe sulgudesse jääva muutuja otsesed ja pöördesinemised. Näiteks:

Imendumisvõimalus tuleneb ilmsetest võrdsustest

Seega on SDNF-i ja SCNF-i minimeerimisel põhiülesanne leida liimimiseks sobivad terminid koos järgneva neeldumisega, mis võib suurte kujundite puhul olla üsna keeruline ülesanne. Carnaugh' kaardid pakuvad visuaalset viisi selliste terminite leidmiseks.

Joonisel on kahe muutuja funktsiooni jaoks lihtne tõepära tabel, sellele tabelile vastav 2-mõõtmeline kuup (ruut), samuti kahemõõtmeline kuup SDNF-i terminite tähistusega ja samaväärne tabel terminite rühmitamiseks:

Veitchi diagrammi meetod.

"Meetod võimaldab teil kiiresti saada väikese arvu muutujate Boole'i funktsiooni f minimaalseid DNF-e. Meetod põhineb Boole'i funktsioonide täpsustamisel teatud tüüpi diagrammide abil, mida nimetatakse Veitchi diagrammideks. Kahest muutujast koosneva Boole'i funktsiooni korral Veitch diagrammil on vorm (tabel 4.4.1).

Diagrammi iga lahter vastab tõesuse tabelis Boole'i funktsiooni muutujate komplektile. See vastavus on näidatud (Tabel 4.4.1) Veitchi diagrammi lahtrisse paigutatakse ühik, kui Boole'i funktsioon võtab vastava hulga ühikuväärtuse. Boole'i funktsiooni nullväärtusi ei ole Veitchi diagrammis seatud. Kolme muutuja Boole'i funktsiooni puhul on Veitchi diagrammil järgmine kuju (tabel 4.4.2).

Sellele sama tabeli lisamine annab diagrammi 4 muutuja funktsiooni jaoks (tabel 4.4.3).

Samamoodi, st lisades äsja vaadeldavale veel ühe 3 muutuja diagrammi, saate diagrammi 5 muutuja funktsiooni jaoks jne, kuid rohkem kui 4 muutujaga funktsioonide diagramme kasutatakse harva. Järgmised diagrammid on tüüpilised:

Kombinatsiooniahelate sünteesi saab illustreerida lihtsa ülesande lahendamisega.

Probleem 1

Vastuvõtukomisjon, mis koosneb kolmest komisjoni liikmest ja ühest esimehest, otsustab kandidaadi saatuse häälteenamusega. Häälte võrdse jagunemise korral määrab häälteenamuse see rühm, kuhu valimiskomisjoni esimees asub. Ehitage automaat, mis tagab enamuse häälte määramise.

Lahendus

Võttes arvesse ülaltoodud eeldusi, saab probleemitingimust üheselt esitada tõesuse tabeli kujul.

Täidame tabeli, võttes arvesse asjaolu, et funktsioon f on täielikult defineeritud, s.t. see on määratletud kõigi võimalike muutujate x1 - x4 kogumitega. N sisendmuutuja jaoks on N = 2n muutujate komplekti. Meie näites N = 24 = 16 komplekti.

Neid komplekte saab kirjutada mis tahes järjekorras, kuid see on parem kahendkoodi kasvavas järjekorras.

Kümnendarvude süsteem

Selle arvusüsteemi p alus on võrdne kümnega. See numbrisüsteem kasutab kümmet numbrit. Praegu on nende arvude tähistamiseks kasutatavad sümbolid 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Arv kümnendarvusüsteemis kirjutatakse ühikute, kümnete, sadade, tuhandete summana. , ja nii edasi. See tähendab, et külgnevate numbrite kaalud erinevad kümnekordselt. Ühest väiksemad numbrid kirjutatakse samamoodi. Sel juhul nimetatakse numbri numbreid ühiku kümnendikuteks, sajandikuteks või tuhandikuteks.

Vaatame kümnendarvu kirjutamise näidet. Näitamaks, et näites kasutatakse kümnendarvusüsteemi, kasutame indeksit 10. Kui lisaks arvude kirjutamise kümnendvormile ei ole ette nähtud kasutada muud salvestusviisi, siis indeksit tavaliselt ei kasutata:

A 10 = 247,56 10 = 2*10 2 +4*10 1 +7*10 0 +5*10 -1 +6*10 -2 = 200 10 +40 10 +7 10 +0,5 10 +0 ,06 10

Siin nimetatakse arvu kõige olulisemat numbrit sadadeks. Ülaltoodud näites vastavad sajad arvule 2. Järgmist numbrit nimetatakse kümneteks. Ülaltoodud näites vastab number 4 kümnetele. Järgmist numbrit nimetatakse ühtedeks. Ülaltoodud näites vastavad ühikud arvule 7. Kümnendik vastab numbrile 5 ja sajandik – 6.

Kahendarvusüsteem

Selle arvusüsteemi p alus on võrdne kahega. See numbrisüsteem kasutab kahte numbrit. Et numbrite tähistamiseks ei leiutaks uusi sümboleid, kasutati kahendarvusüsteemis kümnendnumbrite tähiseid 0 ja 1, et numbrite kirjutamisel mitte segamini ajada, kasutatakse indeksit 2, in Lisaks arvude kirjutamise kahendvormile ei ole ette nähtud kasutada ühtegi teist vormi, siis võib selle indeksi ära jätta.

Arv selles arvusüsteemis kirjutatakse ühtede, kahe, nelja, kaheksa jne summana. See tähendab, et külgnevate numbrite kaalud erinevad kahekordselt. Ühest väiksemad numbrid kirjutatakse samamoodi. Sel juhul nimetatakse numbri numbreid ühiku pooleks, veerandiks või kaheksandikuks.

Vaatame näidet kahendarvu kirjutamise kohta:

A 2 = 101110,101 2 = 1*2 5 +0*2 4 +1*2 3 +1*2 2 +1*2 1 +0*2 0 +1*2 -1 +0*2 -2 + 1* 2-3 = 32 10 +8 10 +4 10 +2 10 +0,5 10 +0,125 10 =46,625 10

Kui kirjutasime teisele reale näite kahendnumbrite kümnendekvivalentidest, ei kirjutanud me nulliga korrutatavaid kahe astmeid, kuna see tooks kaasa valemi segaduse ja raskendaks materjali mõistmist. .

Kahendarvusüsteemi miinuseks võib pidada arvude kirjutamiseks vajalikku suurt numbrite arvu. Selle numbrisüsteemi eeliseks on aritmeetiliste toimingute tegemise lihtsus, millest tuleb juttu hiljem.

Kaheksandikarvude süsteem

Selle arvusüsteemi p alus võrdub kaheksaga. Kaheksandarvude süsteemi võib pidada lühemaks viisiks kahendarvude kirjutamiseks, kuna arv kaheksa on kahe aste. See numbrisüsteem kasutab kaheksakohalist numbrit. Et numbrite tähistamiseks uusi sümboleid ei leiutaks, kasutati kaheksandarvusüsteemis kümnendarvude sümboleid 0, 1, 2, 3, 4, 5, 6 ja 7. Et numbrisüsteemi mitte segamini ajada, kasutati indeksit 8 kasutatakse arvu kirjutamisel Lisaks numbrite kirjutamise kaheksandvormile ei eeldata muu tähistusviisi kasutamist, siis võib selle indeksi ära jätta.

Arv selles arvusüsteemis kirjutatakse ühtede, kaheksate, kuuekümne nelja jne summana. See tähendab, et külgnevate numbrite kaalud erinevad kaheksa korda. Ühest väiksemad numbrid kirjutatakse samamoodi. Sel juhul nimetatakse numbri numbreid kaheksandikuteks, kuuekümne neljadeks ja nii edasi, ühe murdosadeks.

Vaatame kaheksandarvu kirjutamise näidet:

A 8 = 125,46 8 = 1*8 2 +2*8 1 +5*8 0 +4*8 -1 +6*8 -2 = 64 10 +16 10 +5 10 +4 10 /8 10 + 6 10 /64 10 = 85,59375 10

Ülaltoodud näite teine rida teisendab tegelikult kaheksandkujul kirjutatud arvu sama arvu kümnendarvuks. See tähendab, et me vaatasime tegelikult ühte viisi, kuidas numbreid ühest esitusviisist teise teisendada.

Kuna valem kasutab lihtmurde, on võimalik, et täpne tõlkimine ühest esitusvormist teise muutub võimatuks. Sel juhul on need piiratud kindla arvu murdarvudega.

Digitaalsete komparaatorite tüübid

Komparaator erinevate polaarsussignaalide võrdlemiseks

Võrdleja unipolaarsete signaalide võrdlemiseks

Komparaator unipolaarsete pingete võrdlemiseks hüstereesikarakteristikuga. Vaadeldavates võrdlusseadmetes on võimalik saada hüstereesiomadustega karakteristikud. Hüstereesi lisamine võrdlusseadme töösse vähendab mõnevõrra võrdluse täpsust, kuid muudab selle immuunseks müra ja häirete suhtes. Hüsterees saavutatakse kõrgema võrdluspinge sisselülitamisega, kui pinge muutub madalalt kõrgeks, võrreldes väärtusega, mida kasutatakse pinge muutumisel kõrgelt madalale. Sel juhul nimetatakse kõrget võrdluspinge väärtust ülemiseks reaktsiooniläveks ja madalat väärtust alumiseks reaktsiooniläveks. See saavutatakse positiivse tagasiside sisseviimisega.

Mitmebitised komparaatorid

Vaatleme näitena K555SP1 seeria neljabitist digitaalset komparaatorit, mille kaheksa sisendit kasutatakse kahe neljabitise sõna ühendamiseks: A0. A3, B0. B3 võrrelda. Juhtsisendid I(A>B), (A = B) ja I(A< В) могут быть использованы для наращивания разрядности компаратора. Предусмотрены три выхода результата сравнения: А>B, A = B ja A<В.

Sellise komparaatori tõetabel (tabel 1) on jagatud ridade kaupa kolmeks osaks.

Esimene jaotis (tabeli kaheksa ülemist rida) määratleb juhu, kui komparaator töötab, kui võrreldavad neljabitised sõnad ei ole üksteisega võrdsed. Sellisel juhul ei mõjuta bitisügavuse suurendamise sisendites olevad signaalid reaktsioonina võrreldavate sõnade madalamate bittide signaalidele võrdluse tulemust.

Riis. 1. SP1 tüüpi komparaatori tavapärane graafiline esitus

Selle tabeli teise jaotise kolm rida iseloomustavad komparaatori tööd bitisügavuse järjestikuse suurendamise meetodiga, s.o. kui madalat järku komparaatori väljundid on ühendatud kõrget järku komparaatori juhtsisenditega.

Ühebitised komparaatorid

Ühebitisel komparaatoril on kaks sisendit, mis võtavad samaaegselt vastu ühebitised kahendarvud x1 ja x2, ning kolm väljundit (=, >,<). Из таблицы истинности логические уравнения компаратора при сравнении x1 с x2 получаются в виде

Sellise komparaatori rakendamine NAND-alusel annab järgmise joonise (joonis 2):

Joonis 2. Ühebitine kahendarvude komparaator.

Tabel 1. Neljabitise komparaatori tüüp SP1 tõesuse tabel

Võrdleja(analoogsignaalid) (ing. komparaator - võrdlusseade) - elektrooniline ahel, mis võtab oma sisenditest vastu kaks analoogsignaali ja annab loogilise "1", kui signaal otsesisendis ("+") on suurem kui pöördsisendis ("−" ) ja loogiline "0", kui signaal otsesisendis on väiksem kui pöördsisendis.

Binaarse komparaatori üks võrdluspinge jagab kogu sisendpinge vahemiku kaheks alamvahemikuks. Binaarne loogikasignaal (bitt) binaarkomparaatori väljundis näitab, millises kahest alamvahemikust sisendpinge on.

Lihtsaim komparaator on diferentsiaalvõimendi. Võrdlusseade erineb lineaarsest operatsioonivõimendist (op-amp) nii sisend- kui ka väljundastme konstruktsiooni poolest:

Võrdlussisendaste peab taluma laias vahemikus inverteerivate ja mitteinverteerivate sisendite vahelisi sisendpingeid kuni toitepingete kõikumiseni ning selle pinge märgi muutumisel kiiresti taastuma.
Komparaatori väljundaste ühildub loogiliste tasemete ja voolude poolest kindlat tüüpi loogikaahela sisenditega (TTL, ESL tehnoloogiad jne). Võimalikud on avatud kollektoriga ühel transistoril põhinevad väljundastmed (ühilduvad TTL ja CMOS loogikaga).
Hüstereetilise ülekandekarakteristiku moodustamiseks on komparaatorid sageli kaetud positiivse tagasisidega. See meede väldib väljundi oleku kiiret soovimatut ümberlülitamist sisendsignaali müra tõttu, kui sisendsignaal muutub aeglaselt.

Kui võrdluspinge on rakendatud inverteerivale sisendile, suunatakse sisendsignaal mitteinverteerivale sisendile ja komparaator on mitteinverteeriv (järgija, puhver).

Rakendades võrdluspinge mitteinverteerivale sisendile, suunatakse sisendsignaal inverteerivale sisendile ja komparaator inverteerib (inverteerib).

Mõnevõrra harvemini kasutatakse tagasisidega kaetud loogilistel elementidel põhinevaid komparaatoreid (vt nt Schmitti päästik - olemuselt mitte komparaator, vaid väga sarnase kasutusalaga seade).

Komparaatori matemaatilisel modelleerimisel tekib komparaatori väljundpinge probleem siis, kui komparaatori mõlema sisendi pinged on samad. Sel hetkel on komparaator ebastabiilses tasakaalus. Probleemi saab lahendada mitmel erineval viisil, mida on kirjeldatud alajaotises "Tarkvara võrdlus".

Pulsiloendur– elektrooniline seade, mis on ette nähtud sisendile antud impulsside arvu lugemiseks. Vastuvõetud impulsside arvu väljendatakse kahendarvusüsteemis.

Impulsiloendurid on teatud tüüpi registrid (loendusregistrid) ja on üles ehitatud vastavalt flip-flopidele ja loogikaelementidele.

Loendurite peamised näitajad on loenduskoefitsient K 2n - impulsside arv, mida loendur suudab lugeda. Näiteks neljast plätudest koosneva loenduri maksimaalne loendustegur võib olla 24=16. Nelja päästikuga loenduri puhul on minimaalne väljundkood 0000, maksimaalne on -1111 ja loenduskoefitsiendiga Kc = 10 peatub väljundi loendus koodiga 1001 = 9.

Joonisel fig 1 on kujutatud neljabitise loenduri vooluring, mis kasutab järjestikku ühendatud T-flip-flops. Loendusimpulsid suunatakse esimese flip-flopi loendussisendisse. Järgmiste plätude loendussisendid on ühendatud eelmiste plätude väljunditega.

Ahela tööd illustreerivad joonisel 1, b näidatud ajastusskeemid. Kui saabub esimene loendusimpulss, läheb selle langusel esimene päästik olekusse Q1 = 1, st. Digitaalne kood 0001 kirjutatakse loendurisse Teise loendusimpulsi lõpus lülitub esimene päästik olekusse "0" ja teine lülitub olekusse "1". Loendur registreerib numbri 2 koodiga 0010.

Joonis 1 – binaarne neljabitine loendur: a) vooluahel, b) graafiline tähistus, c) töö ajastusskeemid

Diagrammilt (joon. 1, b) selgub, et näiteks 5. impulsi languse järgi kirjutatakse loendurisse kood 0101, 9. järgi - 1001 jne. 15. impulsi lõpus seatakse kõik loenduri bitid olekusse "1" ja 16. impulsi langemisel lähtestatakse kõik trigerid, st loendur läheb algsesse olekusse. Loenduri nullimiseks sundimiseks on olemas lähtestamine.

Binaarse loenduri loenduskoefitsient leitakse seosest Ксч = 2n, kus n on loenduri bittide (trigerite) arv.

Impulsside arvu loendamine on digitaalsetes teabetöötlusseadmetes kõige tavalisem toiming.

Kahendloenduri töötamise ajal väheneb iga järgneva päästiku väljundi impulsi kordussagedus poole võrra võrreldes selle sisendimpulsside sagedusega (joonis 1, b). Seetõttu kasutatakse loendureid ka sagedusjagajatena.

Kodeerija(nimetatakse ka kodeerijaks) teisendab signaali digitaalseks koodiks, enamasti kümnendarvud kahendarvusüsteemiks.

Kodeerijal on m sisendit, mis on nummerdatud järjestikku kümnendarvudega (0, 1,2,..., m - 1), ja n väljundit. Sisendite ja väljundite arv määratakse sõltuvusega 2n = m (joon. 2, a). Sümbol "CD" on moodustatud ingliskeelse sõna Coder tähtedest.

Signaali rakendamine ühele sisendile toob kaasa sisendnumbrile vastava n-bitise kahendarvu ilmumise väljunditesse. Näiteks kui 4. sisendile antakse impulss, ilmub väljunditesse digitaalne kood 100 (joonis 2, a).

Dekoodereid (nimetatakse ka dekooderiteks) kasutatakse kahendarvude teisendamiseks tagasi väikesteks kümnendarvudeks. Dekoodri sisendid (joonis 2, b) on ette nähtud kahendarvude edastamiseks, väljundid on järjestikku nummerdatud kümnendarvudega. Kui sisenditele on rakendatud binaararv, ilmub kindlasse väljundisse signaal, mille number vastab sisendi numbrile. Näiteks koodi 110 rakendamisel ilmub signaal 6. väljundisse.

Joonis 2 – a) UGO kodeerija, b) UGO dekooder

Multiplekser- seade, mille väljund on vastavalt aadressikoodile ühendatud ühe sisendiga. See. Multiplekser on elektrooniline lüliti või kommutaator.

Joonis 3 – Multiplekser: a) graafiline tähistus, b) olekutabel

Sisenditele A1, A2 antakse aadressikood, mis määrab, milline signaalisisenditest edastatakse seadme väljundisse (joonis 3).

Teabe teisendamiseks digitaalsest analoogvormingusse kasutavad nad digitaal-analoogmuundurid (DAC), ja pöördteisenduseks - analoog-digitaalmuundurid (ADC).

DAC-i sisendsignaal on binaarne mitmebitine arv ja väljundsignaaliks on võrdluspinge põhjal genereeritud pinge Uout.

Analoog-digitaal muundamise protseduur (joonis 4) koosneb kahest etapist: ajaproovi võtmine (diskreetimine) ja taseme kvantimine. Proovivõtuprotsess seisneb pideva signaali väärtuste mõõtmises ainult diskreetsetel ajahetkedel.

Joonis 4 – Analoog-digitaal muundamise protsess

Kvantimiseks jagatakse sisendsignaali muutuste vahemik võrdseteks intervallideks – kvantimistasemeteks. Meie näites on neid kaheksa, kuid tavaliselt on neid palju rohkem. Kvantimisoperatsioon taandub intervalli kindlaksmääramisele, millesse diskreetne väärtus langeb, ja väljundväärtusele digitaalse koodi määramisele.

Registritüübid:

1) Lukustusregistrid– ehitatud lukustatud päästikutele (K155TM5; K155TM7), millesse salvestamine toimub strobosignaali taseme järgi.

Päästikus K155TM8 toimub salvestamine strobosignaali positiivse serva abil.

2) Nihkeregistrid– täidab ainult järjestikuse koodi vastuvõtmise funktsiooni.

3) Universaalsed registrid– saab vastu võtta informatsiooni paralleel- ja jadakoodiga.

4) Spetsiaalsed registrid– K589IR12-l on lisavõimalused kasutamiseks.

Vahetuste register

See on register, mille sisu saab juhtsignaali rakendamisel nihutada suuremate või madalamate numbrite suunas. Näiteks vasak nihe on näidatud tabelis 9.

Tabel 9 Koodinihe vasakule

Universaalsed registrid

Neil on välised väljundid ja sisendid kõigi bittide jaoks, samuti jada-DS-sisend.

Universaalseid registreid on kahte tüüpi:

1) register, mis teostab nihet ainult ühes suunas ja võtab vastu koodi paralleelselt (näiteks K155IR1; K176IR3).

2) nelja töörežiimiga: käiguvahetus paremale/vasakule; paralleelne vastuvõtt; salvestusruum (näiteks 8-bitine register K155IR13; 4-bitine register K500IR141).

Peamine elementaarne toiming, mida digitaalseadmetes numbrikoodidega tehakse, on aritmeetiline liitmine.

Loogiline liitja tegutsev sõlm, mis täidab aritmeetika kahe numbri koodide liitmine. Aritmeetilise liitmise käigus tehakse muid lisatehteid: arvude märkide arvestamine, terminite järjekordade joondamine jms. Need toimingud tehakse aritmeetilises loogikaühikus (ALU) või töötlemiselementides, mille tuumaks on liitjad.

Lisajaid klassifitseeritakse erinevate kriteeriumide järgi.

Olenevalt numbrisüsteemist eristama:

binaarne;
binaarne kümnendkoht (üldiselt binaarne kodeering);
koma;
teised (näiteks amplituud).

Lisatud numbrite samaaegselt töödeldud numbrite arvu järgi:

ühekohaline,
mitmebitine.

Ühebitiste binaarsummarite sisendite ja väljundite arvu järgi:

veerandliitjad ("sum modulo 2" elemendid; "eksklusiivsed VÕI" elemendid), mida iseloomustab kahe sisendi olemasolu, millele antakse kaks ühekohalist arvu, ja üks väljund, mille juures nende aritmeetiline summa realiseeritakse;
poolliitjad, mida iseloomustab kahe sisendi olemasolu, millele antakse kahe numbri samad numbrid, ja kaks väljundit: üks realiseerib antud numbri aritmeetilise summa ja teine kannab ülekande järgmisele (kõrgemale numbrile) ;
täielikud ühebitised binaarsummarid, mida iseloomustab kolme sisendi olemasolu, millele lisatakse samad kahe numbri numbrid ja ülekanne eelmisest (alumisest) numbrist, ja kaks väljundit: ühel aritmeetiline summa selles number realiseeritakse ja teisalt ülekanne järgmisele (kõrgemale) tühjenemisele).

Lisatud numbrite esitamise ja töötlemise teel mitmebitised liitjad jagunevad:

järjestikune, milles numbreid töödeldakse ükshaaval, number numbri haaval samal seadmel;
paralleelselt, kus terminid liidetakse üheaegselt kõigi numbrite peale ja igal numbril on oma varustus.

Kõige lihtsamal juhul koosneb paralleelsummer n-st ühebitisest liitjast, mis on järjestikku (vähem olulisest kuni kõige olulisemani) ühendatud kandeahelatega. Sellist liitmisahelat iseloomustab aga suhteliselt madal jõudlus, kuna iga i-nda biti summa- ja kandesignaalide genereerimine toimub alles pärast edastussignaali saabumist (i-1) bitilt summari määrab signaali levimise aeg ülekandeahelas. Selle aja vähendamine on peamine ülesanne paralleelsummajate konstrueerimisel.

Edastussignaali leviaja vähendamiseks kasutage: Konstruktiivsed otsused

LOOGILISTE TEGEVUSTE OMADUSED

1. Nimetused

1.1. Loogiliste ühenduste (toimingute) märge:

a) eitus(inversioon, loogiline EI) on tähistatud ¬-ga (näiteks ¬A);

b) sidesõna(loogiline korrutamine, loogiline JA) tähistatakse /\
(näiteks A /\ B) või & (näiteks A & B);

c) disjunktsioon(loogiline lisamine, loogiline VÕI) on tähistatud \/
(näiteks A \/ B);

d) järgnev(implikatsioon) tähistatakse → (näiteks A → B);

e) identiteet tähistatakse ≡ (näiteks A ≡ B). Avaldis A ≡ B on tõene siis ja ainult siis, kui A ja B väärtused on samad (kas mõlemad on tõesed või mõlemad valed);

f) sümbolit 1 kasutatakse tõe (tõene väide) tähistamiseks; sümbol 0 – valele viitamine (vale väide).

1.2. Kutsutakse kahte muutujaid sisaldavat Boole'i avaldist samaväärne (ekvivalent), kui nende avaldiste väärtused langevad kokku muutujate mis tahes väärtustega. Seega on avaldised A → B ja (¬A) \/ B samaväärsed, aga A /\ B ja A \/ B mitte (avaldiste tähendused on erinevad, näiteks kui A = 1, B = 0 ).

1.3. Loogiliste operatsioonide prioriteedid: inversioon (eitamine), konjunktsioon (loogiline korrutis), disjunktsioon (loogiline liitmine), implikatsioon (järgimine), identsus. Seega tähendab ¬A \/ B \/ C \/ D sama, mis

((¬A) \/ B) \/ (C \/ D).

(A \/ B) \/ C asemel on võimalik kirjutada A \/ B \/ C. Sama kehtib ka sidesõna kohta: (A /\ B asemel on võimalik kirjutada A /\ B /\ C ) /\ C.

2. Omadused

Allolev nimekiri EI ole mõeldud täielikuks, kuid on loodetavasti piisavalt esinduslik.

2.1. Üldised omadused

Komplekti jaoks n seal on täpselt loogilised muutujad 2 n erinevaid tähendusi. Tõdetabel loogilise väljenduse jaoks alates n muutujad sisaldavad n+1 veerg ja 2 n read.

2.2.Disjunktsioon

Kui vähemalt üks alamavaldistest, millele disjunktsiooni rakendatakse, on tõene mõne muutujate väärtuste komplekti puhul, siis on selle väärtuste kogumi puhul tõene kogu disjunktsioon.
Kui kõik avaldised teatud loendist on tõesed teatud muutujaväärtuste kogumi puhul, siis on tõene ka nende avaldiste disjunktsioon.
Kui kõik avaldised teatud loendist on teatud muutujate väärtuste kogumi puhul valed, siis on ka nende avaldiste disjunktsioon väär.
Disjunktsiooni tähendus ei sõltu alamväljendite kirjutamisjärjekorrast, millele seda rakendatakse.

2.3. Konjunktsioon

Kui vähemalt üks alamavaldistest, millele sidet rakendatakse, on mõne muutujaväärtuste komplekti puhul väär, siis on kogu side selle väärtuste komplekti puhul väär.
Kui kõik avaldised teatud loendist on tõesed teatud muutujaväärtuste kogumi puhul, siis on tõene ka nende avaldiste konjunktsioon.
Kui kõik avaldised teatud loendist on teatud muutujaväärtuste kogumi puhul valed, siis on ka nende avaldiste konjunkts väär.
Sidesõna tähendus ei sõltu alamväljendite kirjutamisjärjekorrast, millele seda rakendatakse.

2.4. Lihtsad disjunktsioonid ja konjunktsioonid

Nimetagem (mugavuse huvides) sidesõna lihtne, kui alamavaldised, millele sidet rakendatakse, on erinevad muutujad või nende eitused. Samamoodi nimetatakse disjunktsiooni lihtne, kui alamavaldised, millele disjunktsiooni rakendatakse, on erinevad muutujad või nende eitused.

Lihtsa sidesõna väärtus on 1 (tõene) täpselt ühe muutujaväärtuste komplekti puhul.
Lihtne disjunktsioon annab väärtuseks 0 (väär) täpselt ühe muutujaväärtuste komplekti puhul.

2.5. Implikatsioon

Implikatsioon A →B on võrdväärne disjunktsiooniga (¬ A) \/ B. Selle disjunktsiooni võib kirjutada ka järgmiselt: ¬ A\/B.
Implikatsioon A →B võtab väärtuse 0 (väär) ainult siis, kui A=1 Ja B = 0. Kui A=0, siis järelmõju A →B tõsi iga väärtuse puhul B.

Sidesõna: vastab sidesõnale: “ja”, mida tähistatakse märgiga^, tähistab loogilist korrutamist.

Kahe loogilise ~ konjunktsioon on tõene siis ja ainult siis, kui mõlemad väited on tõesed. Saab üldistada suvalise arvu muutujate jaoks A^B^C = 1, kui A=1, B=1, C=1.

Operatsiooni “Conjunction” tõetabel:

Tabel nr 2

Disjunktsioon

Loogiline tehe vastab ühendusele VÕI, mida tähistatakse märgiga v, mida muidu nimetatakse LOOGILISEKS LISANDIKS.

Kahe loogilise muutuja disjunktsioon on väär, kui ja pebble on väär, kui mõlemad väited on valed.

Seda määratlust saab üldistada mis tahes arvule loogilistele muutujatele, mis on kombineeritud disjunktsiooniga.

A v B v C = 0 ainult siis, kui A = O, B = O, C - 0.

Operatsiooni “Disjunktsioon” tõetabel:

Tabel nr 3

Inversioon

Loogiline tehe vastab osakesele mitte, seda tähistatakse ¬ või ¯-ga ja see on loogiline eitus.

Tõene muutuja pöördväärtus on tõene, kui muutuja on väär ja vastupidi: pöördväärtus on väär, kui muutuja on tõene.

Operatsiooni "Inversioon" tõetabel:

Tabel nr 5

Ekvivalentsust “Ja siis B ja alles siis” tähistatakse A ~ B-ga

Tabel nr 6

Loogikavaldise (valemi) väärtuse arvutamisel arvutatakse loogilised toimingud kindlas järjekorras, vastavalt nende prioriteedile:

ümberpööramine;

sidesõna;

disjunktsioon;

implikatsioon ja samaväärsus;

Sama prioriteediga toiminguid tehakse vasakult paremale. Toimingute järjekorra muutmiseks kasutatakse sulgusid.

Väidete vormistamine

Loomulikke keeli kasutatakse kirjeldavate teabemudelite loomiseks. Teadusajaloost on teada arvukalt kirjeldavaid infomudeleid; Näiteks heliotsentriline maailmamudel, mille Kopernik pakkus, sõnastati järgmiselt:

Maa pöörleb ümber oma telje ja ümber Päikese;

kõik planeedid tiirlevad ümber Päikese;

Formaalsete keelte abil ehitatakse üles formaalsed infomudelid (matemaatilised, loogilised jne). Üks enim kasutatavaid ametlikke keeli on matemaatika. Matemaatiliste kontseptsioonide ja valemite abil loodud mudeleid nimetatakse matemaatiliseks mudeliks. Matemaatika keel on formaalsete keelte kogum.

Algebra keel võimaldab formaliseerida suuruste vahelisi funktsionaalseid sõltuvusi. Nii vormistas Newton maailma heliotsentrilise süsteemi, avastades mehaanika ja universaalse gravitatsiooni seaduse ning kirjutades need üles algebraliste funktsionaalsete sõltuvuste kujul. Näiteks koolifüüsika kursusel käsitletakse paljusid erinevaid algebra keeles väljendatud funktsionaalseid sõltuvusi, mis on uuritavate nähtuste või protsesside matemaatilised mudelid.

Loogikalgebra keel (propositsioonialgebra) võimaldab koostada formaalseid loogilisi mudeleid. Propositsioonialgebra abil saate formaliseerida (kirjutada loogiliste avaldiste kujul) loomulikus keeles väljendatud lihtsaid ja keerulisi väiteid. Loogiliste mudelite koostamine võimaldab lahendada loogilisi probleeme, koostada arvutiseadmete loogilisi mudeleid (liitja, päästik) jne.

Formaalsete keelte abil teabemudelite loomise protsessi nimetatakse formaliseerimiseks.

Inimkond kasutab meid ümbritseva maailma mõistmise protsessis pidevalt modelleerimist ja vormistamist. Uue objekti uurimisel ehitatakse esiteks selle kirjeldav teabemudel tavaliselt loomulikus keeles, seejärel formaliseeritakse, st väljendatakse formaalsete keelte (matemaatika, loogika jne) abil.

Loogika algebra ja arvuti loogilised alused

Loogika algebra (Boole'i algebra) on matemaatika haru, mis tekkis 19. sajandil tänu inglise matemaatiku pingutustele J. Boulya. Alguses ei olnud Boole'i algebral praktilist tähtsust. Kuid juba 20. sajandil leidsid selle sätted rakendust erinevate elektroonikalülituste toimimise ja arengu kirjeldamisel. Loogilise algebra seadusi ja aparaati hakati kasutama arvutite erinevate osade (mälu, protsessor) projekteerimisel. Kuigi see pole selle teaduse ainus rakendusvaldkond.

Mis see on? loogika algebra? Esiteks uurib see keerukate loogiliste väidete tõesuse või vääruse tuvastamise meetodeid, kasutades algebralisi meetodeid. Teiseks teeb Boole'i algebra seda nii, et keerulist loogilist väidet kirjeldab funktsioon, mille tulemus võib olla kas tõene või väär (1 või 0). Sel juhul võib funktsiooni argumentidel (lihtlausetel) olla ka ainult kaks väärtust: 0 või 1.

Mis on lihtne loogiline väide? Need on fraasid nagu "kaks on rohkem kui üks", "5,8 on täisarv". Esimesel juhul on meil tõde ja teisel juhul vale. Loogika algebra ei puuduta nende väidete olemust. Kui keegi otsustab, et väide “Maa on ruut” vastab tõele, siis loogika algebra aktsepteerib seda kui tõsiasja. Fakt on see, et Boole'i algebra tegeleb keerukate loogiliste väidete tulemuse arvutamisega, mis põhinevad lihtsate väidete varem teadaolevatel väärtustel.

Loogilised operatsioonid. Disjunktsioon, konjunktsioon ja eitus

Kuidas me otsustame, kas see, mis meile on öeldud, on tõsi või mitte? Kuidagi loogiliselt, isegi kuskil alateadlikult, eelnevale elukogemusele tuginedes saame aru, et tõde ühendusega “ja” esineb mõlema lihtlause tõepärasuse puhul. Kui ühest saab vale, on kogu keeruline väide vale. Kuid sidesõnaga "või" peab tõene olema ainult üks lihtne väide ja siis saab tõeseks kogu väljend.

Loogika algebra sisaldab palju loogilisi tehteid. Kolm neist väärivad aga erilist tähelepanu, sest... nende abiga saate kirjeldada kõiki teisi ja seetõttu kasutada vooluahelate kujundamisel vähem erinevaid seadmeid. Sellised operatsioonid on konjunktsioon (AND), disjunktsioon (OR) ja eitus (NOT). Sageli tähistatakse sidesõna &, disjunktsiooni ||-ga ja eitust lauset tähistava muutuja kohal oleva ribaga.

Kell konjunktsioon@/a> tõsi koos vääravaldis tekib ainult siis, kui kõik kompleksi moodustavad lihtsad avaldised on tõesed. Kõigil muudel juhtudel on kompleksavaldis vale.

Kell disjunktsioonid tõde keeruline avaldis tekib siis, kui vähemalt üks selles sisalduv lihtne avaldis on tõene või kaks korraga. Juhtub, et keeruline avaldis koosneb rohkem kui kahest lihtsast. Sel juhul piisab ühest lihtsast, et olla tõsi ja siis on kogu väide tõene.

Eitus- see on unaarne tehe, kuna seda tehakse seoses ühe lihtsa avaldise või keeruka avaldise tulemusega. Eituse tulemusena saadakse uus väide, mis on vastupidine algsele.

Loogiliste väärtuste jaoks kasutatakse tavaliselt kolme toimingut:

Sidesõna – loogiline korrutamine (AND) – ja, &, ∧.

Disjunktsioon – loogiline liitmine (OR) – või, |, v.

Loogiline eitus (EI) - mitte,.

Loogilisi operatsioone on mugav kirjeldada niinimetatud tõetabelitega, mis kajastavad keerukate väidete arvutuste tulemusi algsete lihtsate väidete erinevate väärtuste jaoks. Lihtlauseid tähistatakse muutujatega (näiteks A ja B).

Arvuti loogilised alused

Arvutites kasutatakse erinevaid seadmeid, mille tööd kirjeldab suurepäraselt loogika algebra. Selliste seadmete hulka kuuluvad lülitite, päästikute, lisajate rühmad.

Lülitusahelad

Väravad, plätud ja lisaseadmed

Päästikud Ja lisajad- need on suhteliselt keerukad seadmed, mis koosnevad lihtsamatest elementidest - ventiilidest.

Päästik on võimeline salvestama ühte kahendnumbrit, kuna see võib olla kahes stabiilses olekus. Päästikuid kasutatakse peamiselt protsessoriregistrites.

Summeerijaid kasutatakse laialdaselt protsessori aritmeetilises loogikaühikus (ALU) ja need teostavad kahendbittide liitmist.

Teave ja teabeprotsessid. Teabe liigid, selle binaarne kodeerimine. Teabe hulk, lähenemisviisid mõiste "teabe hulk" määratlemiseks, teabe mõõtühikud. Numbri-, teksti-, graafilise, heliteabe binaarne kodeerimine

Teave(ladina keelest informatio - "seletus, esitlus, teadlikkus") - teave millegi kohta, olenemata selle esitusviisist.

Praegu puudub teabe kui teadusliku termini ühtne definitsioon. Erinevate teadmusvaldkondade seisukohast kirjeldab seda mõistet selle spetsiifiline tunnuste kogum. Mõiste “informatsioon” on informaatikakursusel põhiline, kus seda ei ole võimalik defineerida muude, “lihtsamate” mõistete kaudu.

Teabe omadused:

objektiivsus (informatsioon on objektiivne, kui see ei sõltu kellegi arvamusest või hinnangust);

Usaldusväärsus (teave on usaldusväärne, kui see kajastab asjade tegelikku seisu);

täielikkus (informatsioon on täielik, kui see on piisav mõistmiseks ja otsuse tegemiseks);

asjakohasus (informatsioon on asjakohane, õigeaegne, kui see on oluline, oluline praeguse aja jaoks);

Kasulikkus (hinnatakse ülesannete järgi, mida saame selle abil lahendada);

Arusaadavus (info on arusaadav, kui see on väljendatud vastuvõtjale arusaadavas keeles);

Kättesaadavus (info on olemas, kui saame kätte).

Teabeprotsess- teabega (andmete, teabe, faktide, ideede kujul) tehtud järjestikuste toimingute (operatsioonide) kogum, hüpoteesid, teooriad jne) mis tahes tulemuse saavutamiseks (eesmärgi saavutamiseks).

Informatsioon avaldub just infoprotsessides. Infoprotsessid toimuvad alati mingis süsteemis (sotsiaalses, sotsiotehnilises, bioloogilises jne).

Kõige üldistatumad teabeprotsessid on teabe kogumine, teisendamine ja kasutamine.

Peamised infoprotsessid, mida arvutiteaduse kursusel õpitakse, on: teabe otsing, valik, salvestamine, edastamine, kodeerimine, töötlemine ja kaitsmine.

Teatud infotehnoloogiate abil läbiviidavad infoprotsessid on inimese infotegevuse aluseks.

Arvuti on universaalne seade infoprotsesside automatiseeritud täitmiseks.

Inimesed tegelevad erinevat tüüpi teabega. Inimeste omavaheline suhtlemine kodus ja koolis, tööl ja tänaval on info edastamine. Õpetaja või sõbra jutt, telesaade, telegramm, kiri, suuline teade jne. - kõik need on näited teabe edastamisest.

Ja me juba rääkisime sellest et sama teavet saab edastada ja vastu võtta erineval viisil. Nii et võõras linnas asuvasse muuseumisse tee leidmiseks võite küsida mööduja käest, saada abi infoletist, proovida linnakaardi abil ise välja mõelda või tutvuda teejuhiga. Kui kuulame õpetaja selgitusi, loeme raamatuid või ajalehti, vaatame teleuudiseid, külastame muuseume ja näitusi – sel ajal saame infot.

Inimene salvestab saadud info oma pähe. Inimese aju on tohutu teabehoidla. Märkmik või märkmik, teie päevik, kooli vihikud, raamatukogu, muuseum, kassett teie lemmiklugude salvestistega, videokassett - kõik need on näited teabe salvestamisest.

Teavet saab töödelda: teksti tõlkimine inglise keelest vene keelde ja vastupidi, etteantud terminite summa arvutamine, ülesande lahendamine, piltide või kontuurkaartide värvimine - kõik need on näited teabe töötlemisest. Teile kõigile meeldis ühel või teisel ajal värvimisraamatutes värvimine. Selgub, et sel ajal tegelesite olulise protsessiga - teabe töötlemisega, mustvalge joonise muutmisega värviliseks.

Teave võib isegi kaduda. Oletame, et Dima Ivanov unustas päeviku koju ja pani seetõttu kodutöö paberile kirja. Kuid vahetunnis mängides tegi ta sellest lennuki ja lasi selle välja. Koju jõudes ei saanud Dima kodutööd teha, ta kaotas teabe. Nüüd peab ta kas proovima meelde jätta, mida talt küsiti, või helistama klassikaaslasele, et saada vajalikku teavet, või minna kooli pooleli jäänud kodutöödega.

Binaarne kodeerimine -üks levinumaid teabe esitamise viise. Arvutites, robotites ja arvjuhtimisega masinates on reeglina kogu teave, millega seade tegeleb, kodeeritud kahendtähestiku sõnade kujul.

Binaartähestik koosneb kahest numbrist 0 ja 1.

Digitaalarvutid (personaalarvutid kuuluvad digitaalklassi) kasutavad igasuguse teabe binaarset kodeerimist. See on peamiselt seletatav asjaoluga, et tehniliselt oli lihtsam ehitada tehnilist seadet, mis eristab täpselt 2 erinevat signaali olekut, kui sellist, mis eristab täpselt 5 või 10 erinevat olekut.

Binaarse kodeerimise miinuste hulka kuuluvad väga pikad binaarkoodikirjed, mis teeb nendega töötamise keeruliseks.