Logiske operasjoner. Disjunksjon, konjunksjon og negasjon

Logisk addisjon (disjunksjon) dannes ved å kombinere to utsagn til ett ved å bruke konjunksjonen "eller".

På russisk brukes konjunksjonen "eller" i dobbel betydning.

For eksempel, V forslag Vanligvis klokken 20 ser jeg på TV eller drikker te konjunksjonen "eller" er tatt i en ikke-eksklusiv (forenende) mening, siden du bare kan se på TV eller bare drikke te, men du kan også drikke te og se på TV samtidig, fordi moren din ikke er streng. Denne operasjonen kalles ikke-streng disjunksjon.(Hvis moren min var streng, ville hun bare tillate meg å enten se på TV eller bare drikke te, men ikke kombinere spising med å se på TV.)

I en uttalelse Dette verbet har I eller II bøying konjunksjon "eller"
brukes utelukkende (deling) føle. En slik operasjon
kalt streng disjunksjon.. ,. ,-> „,... > (, r>

Eksempler på strenge og ikke-strenge disjunksjoner:

Uttalelse	Type disjunksjon
Petya sitter på den vestlige eller østlige tribunen på stadion	Streng
En student kjører tog eller leser en bok	Slapp
Olya liker å skrive essays eller løse logiske problemer	Slapp
Seryozha studerer på skolen eller ble uteksaminert fra den	Streng
I morgen vil det regne eller ikke (det er ikke noe tredje alternativ)	Streng
La oss kjempe for renhet. Renslighet oppnås på denne måten: enten ikke søppel, eller rengjør ofte	Slapp
Zelia beveger seg i en sirkulær eller elliptisk bane	Streng
Tall kan legges til eller multipliseres	Slapp
Barn er enten veloppdragne eller ikke våre	?

Notasjon for en svak disjunksjon:EN ELLER I; ENELLERI; EN| I; EN V I; A + B.(I denne opplæringen: EN V I.)

La oss gi et eksempel på en disjunksjon av to enkle utsagn.

La oss si at du fra vinduet ditt kan se en parkeringsplass, hvor det vanligvis er to biler: en Mercedes og en Zhiguli, men det kan være en av dem, eller det kan være ingen.

La oss betegne utsagnene:

A = Det er en Mercedes på parkeringsplassen. I= Det er Zhiguli-biler på parkeringsplassen.

(EN disjunksjon B) = Det er på parkeringsplassen "Mercedes" eller "Zhiguli".

Kapittel 3. Logiske operasjoner ____________ [___________________________ SCH

Tabell., ^"-"n..;ch; Jeg■.■;- >i ,;,

Fra sannhetstabellen følger det at en disjunksjon av to utsagn er usann hvis og bare hvis begge utsagnene er usanne, og sann når minst ett utsagn er sant. Noen ganger blir denne egenskapen tatt som definisjonen av disjunksjonsoperasjonen.

Mnemonisk regel: disjunksjon er logisk addisjon, og vi er ikke i tvil om at du la merke til at likhetene 0 + 0 = 0; 0+1 = 1;1+0=1, sant for vanlig addisjon, er også sant for disjunksjonsoperasjonen, men 1 V 1 = 1.

Ordet "konjunksjon" har én bokstav "og", og ordet "disjunksjon" har to bokstaver "og", som Og i ordet "eller".

V L-Symbolet V (disjunksjon) er dannet av den første bokstaven i det latinske ordet Vel ("eller").

"Dis" - "kryss ned" - V.

I settteori tilsvarer disjunksjon operasjonen foreninger settene.

For å konstruere Euler-Venn-diagrammet som tilsvarer foreningen av sett, velger vi de radene i sannhetstabellen der AvB=\. Det er tre av dem. På diagrammet skygger vi tre områder der verdiene ENOgI det samme som i de valgte linjene. ^ _ h."" " * "o L su J I J

30 ___________________________ Del 1. Elementer i matematisk logikk

Grafisk illustrasjon: ».*■.

EN I A\jB– mange elever i klassen som er fremragende elever eller idrettsutøvere.

j Vurder operasjonen streng disjunksjoner (eksklusivt "eller"). i La oss gi et eksempel på en streng disjunksjon.

,)■ La følgende utsagn gis:

"■ EN= Det er en Mercedes på parkeringsplassen.

>; B = Det er Zhiguli-biler på parkeringsplassen.

jeg (A streng disjunksjon B) = På parkeringsplassen står “Mvrsedve”*or

"Zhiguli". v?;;

Bruken av den "eksklusive "eller"-operasjonen innebærer at det enten bare kan være en Mercedes eller bare en Zhiguli på parkeringsplassen, og forbyr situasjonen når en Mercedes og en Zhiguli er på parkeringsplassen samtidig.

; . - "4",

Strenge disjunksjonsnotasjon:EN XOR I; EN v I.

kapittel 3. Logiske operasjoner ______________________________________ 31

Fra sannhetstabellen følger det at operasjonen med streng disjunksjon er sann hvis og bare hvis bare ett av utsagnene er sant, og usant når begge utsagnene er sanne eller begge er usanne. Noen ganger blir denne egenskapen tatt for å være definisjonen av den strenge disjunksjonsoperasjonen.

Et Euler-Venn-diagram som viser en streng disjunksjon er konstruert ved hjelp av en sannhetstabell på samme måte som for andre logiske operasjoner.

Grafisk illustrasjon:

<ЗЭ

EN- mange utmerkede elever i klassen; I- mange idrettsutøvere i klassen;

A ved B– mange elever i klassen som enten er fremragende elever eller idrettsutøvere.

d "TOALETT. J

Logisk konsekvens (implikasjon) -wr™

Logisk konsekvens (implikasjon) dannes ved å koble sammen to!,

utsagn til en ved hjelp av talemåten "hvis..., At ... ». ■

Eksempler på implikasjoner: "

E = Hvis en ed gis, må den oppfylles.{

P = Hvis et tall er delelig med 9, er det delelig med 3. Jeg

I logikk er det tillatt (akseptert, avtalt) å vurdere også ikke-.;:

utsagn som gir mening fra et hverdagslig synspunkt. Jeg

La oss gi eksempler på dommer som ikke bare er lovlig vurdert; river i logikk, men som også har betydningen "sant":

MED= Hvis kyrne flyr, så er 2 + 2 = 5. X = If- Napoleon, så har en katt fire bein.

Implikasjonsbetegnelse:A -> B; EN=e I.(I denne opplæringen: EN=» I.) De sier: hvis EN, At I; EN innebærer I; EN innebærer I; I følger av EN.

Del 1. Elementer i matematisk logikk

Kapittel 3. Logiske operasjoner f; L._________________________ 33

Denne operasjonen er ikke like åpenbar som de forrige. Det kan for eksempel forklares som følger.

La følgende utsagn gis: .>--.< а «<, .<-. *>,w ""ihw

L A = Det regner ute.>..;; j .„ , | G,., d

B = Asfalten er våt. ts

(EN implikasjon 2?) = £bш på Det regner ute, så er asfalten våt.

Så hvis det regner (EN= 1) og asfalten er våt (5=1), så er dette forholdet
samsvarer med virkeligheten, dvs. sant. Men hvis de forteller deg det
det regner ute (EN= 1), og asfalten forblir tørr (B = 0), så teller du
du skjuler det med løgner. Men når det ikke regner ute (EN= 0), deretter asfalt
kan være både tørr og våt (for eksempel har du nettopp kjørt gjennom en
akselmaskin). ъ. ?; t | rfl]

Bord

Uttalelsesskjema: if EN, At I,

G SÅ! ,chi , T "/1

"? , L ■ Og ". "L\ og h > < "L

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

La oss forklare konstruksjonen av diagrammet. Vi er interessert i sannheten om implikasjonen, så vi velger de radene i sannhetstabellen der EN=> I= 1. Det er tre slike linjer. På diagrammet skygger vi tre områder der verdiene EN Og I det samme som i de valgte linjene:

Fra sannhetstabellen følger det at implikasjonen av to utsagn er usann hvis og bare hvis en falsk utsagn følger av en sann utsagn (når en sann premiss fører til en falsk konklusjon). Noen ganger blir denne egenskapen tatt som definisjonen av implikasjonsoperasjonen.

La oss se på et av eksemplene ovenfor på konsekvenser som strider mot sunn fornuft.

(A = 0)n(B = 0)

(A = 0)s (B = 1)

(L = 1)n(I = 1)

Logisk likhet (ekvivalens)

Logisk likhet (ekvivalens) dannes ved å kombinere to utsagn til ett ved å bruke vendingen "... hvis og bare hvis ...».

Del 1. Elementer i matematisk logikk^

Kapittel 3. Logiske operasjoner

Eksempler på ekvivalenser: "

1) En vinkel kalles rett da og akkurat når han er lik 90°.

2) To linjer er parallelle da og bare når de ikke krysse hverandre..,

3) Ethvert materiell punkt opprettholder en tilstand av hvile eller jevn rettlinjet bevegelse hvis og bare hvis det ikke er noen ytre påvirkning.(Newtons første lov.)

4) Hodet tenker da og først når tungen er i ro.(Vits.)

Alle lover i matematikk, fysikk, alle definisjoner er ekvivalens av utsagn.

Ekvivalensbetegnelse: A = B; EN<=>I; A ~ B.(I denne opplæringen: EN O I.)

La oss gi et eksempel på ekvivalens. La følgende utsagn gis:

EN= Tallet er delelig med 3 uten en rest (multipler av tre). I= Summen av sifrene i et tall er delelig med 3.

(EN tilsvarende B) = Et tall er delelig med 3 hvis og bare når
summen av sifrene er delelig med 3., ;

Forklaring:

EN	I	EN<^В

Sannhetstabell:

	Betydning
	uttalelser
Betydningen av utsagn	Tallet er et multiplum av 3
EN Og I for det spesifiserte< значений "*"	da og bare når
*	summen av sifrene delt helt innen 3
Nummeret er det ikke	Summen av tallene er ikke	ekte
multiplum av tre	multiplum av tre
Nummeret er det ikke	Sum av sifre	Å ligge
multiplum av tre	multiplum av tre
Tallet er et multiplum	Summen av tallene er ikke	Å ligge
tre	multiplum av tre
Tallet er et multiplum	Sum av sifre	ekte
tre	multiplum av tre

Fra sannhetstabellen følger det at ekvivalensen til to utsagn er sann hvis og bare hvis begge utsagnene er sanne eller begge er usanne. Noen ganger brukes denne egenskapen for å definere ekvivalensoperasjonen.

I settteori tilsvarer denne operasjonen operasjonen ekvivalens settene.

For å konstruere den tilsvarende ekvivalensen av sett i Euler-Venn-diagrammet, velger vi de radene i sannhetstabellen der EN<=> I= 1. Det er to av dem. På diagrammet skygger vi to områder der verdiene AnV det samme som i de valgte linjene.

Grafisk illustrasjon: c~J_ ........ 1l...Li

Ш GRUNNLEGGENDE KONSEPT OG DEFINISJONER

Logisk operasjon- en metode for å konstruere et komplekst utsagn fra gitte utsagn, der sannhetsverdien til det komplekse utsagnet er fullstendig bestemt av sannhetsverdiene til de originale utsagnene.

Inversjon(logisk negasjon) dannes fra et utsagn ved å legge til partikkelen «ikke» til predikatet eller bruke talemåten «det er ikke sant at...».

Inversjonssymbol: IKKE EN;-. EN; EN; IKKE A.>"i, t

Bord
sannhet: ■■■ g -

EN	EN

Inversjonen av et utsagn er sant når
viser er falsk, og falsk når påstanden
ekte. ■--■

! t■ .■ " N ■

Del 1. Elementer i matematisk logikk

G Kapittel 3. Logiske operasjoner

Konjunksjon(logisk multiplikasjon) dannes ved å kombinere to utsagn til ett ved å bruke konjunksjonen "og".

Konjunksjonsnotasjon: A I B; EN L I; EN& I; A ■ B; EN OG I.

; (G">* „*

Ekvivalens(logisk likhet) dannes ved å kombinere to utsagn til ett ved å bruke vendingen "... hvis og bare hvis...".

Ekvivalensbetegnelse: A = B; EN<=> I; A ~ B.

Sannhetstabell:

Ekvivalensen til to utsagn er sann hvis og bare hvis begge utsagnene er sanne eller begge er usanne.

Disjunksjon(logisk addisjon) dannes ved å koble to utsagn til ett ved å bruke konjunksjonen "eller". ,

Disjunksjonsnotasjon: EN ELLER I; A\B; L V I; EN+ I.

Sannhetstabell:

Implikasjon(logisk konsekvens) dannes ved forbindelse to utsagn til en ved hjelp av talemåten "hvis ..., da ...". Implikasjonsbetegnelse: A->B;A=$B.

Grunnleggende sammendrag "Egenskaper for logiske operasjoner"

Sannhetstabell:

EN	I	A^B

En implikasjon av to utsagn er usann hvis og bare hvis en falsk utsagn følger av en sann utsagn.

Ch1ya" | ; - VI

. ..,... . , .-. . hvis . ............... --,-

■*}■

<Ч. 1

Relatert informasjon.

Logiske operasjoner. Disjunksjon, konjunksjon og negasjon

Så hvordan forbinder enkle logiske utsagn hverandre for å danne komplekse utsagn? I naturlig språk bruker vi ulike konjunksjoner og andre deler av tale. For eksempel "og", "eller", "enten", "ikke", "hvis", "da", "da". Eksempel på komplekse utsagn: «han har kunnskap Og ferdigheter", "hun kommer på tirsdag, eller på onsdag", "Jeg skal spille Deretter, når jeg gjør leksene mine", "5 Ikke tilsvarer 6". Hvordan avgjør vi at det vi har blitt fortalt er sant eller ikke? På en eller annen måte logisk, selv et ubevisst sted, basert på tidligere livserfaring, forstår vi at sannheten med foreningen "og" forekommer i tilfelle av sannheten til begge enkle utsagn. Når man først blir en løgn, vil hele det komplekse utsagnet være falskt. Men med det bindende "eller" må bare ett enkelt utsagn være sant, og da vil hele uttrykket bli sant.

Boolsk algebra overførte denne livserfaringen til matematikkens apparat, formaliserte den og innførte strenge regler for å oppnå et entydig resultat. Fagforeninger begynte å bli kalt logiske operatører her.

Logikkens algebra involverer mange logiske operasjoner. Tre av dem fortjener imidlertid spesiell oppmerksomhet, fordi... med deres hjelp kan du beskrive alle de andre, og derfor bruke mindre utvalg av enheter når du designer kretser. Slike operasjoner er konjunksjon(OG), disjunksjon(ELLER) og negasjon(IKKE). Ofte er konjunksjonen betegnet & , disjunksjon - || , og negasjonen er en stolpe over variabelen som indikerer setningen.

Med en konjunksjon oppstår sannheten til et komplekst uttrykk bare hvis alle de enkle uttrykkene som utgjør komplekset er sanne. I alle andre tilfeller vil det komplekse uttrykket være usant.

Med disjunksjon oppstår sannheten til et komplekst uttrykk når minst ett enkelt uttrykk inkludert i det er sant, eller to på en gang. Det hender at et komplekst uttrykk består av mer enn to enkle. I dette tilfellet er det nok at en enkel er sann, og da vil hele utsagnet være sant.

Negasjon er en unær operasjon, fordi den utføres i forhold til ett enkelt uttrykk eller i forhold til resultatet av et komplekst. Som et resultat av negasjon oppnås en ny uttalelse som er motsatt av den opprinnelige.

Sannhetstabeller

Det er praktisk å beskrive logiske operasjoner ved den såkalte sannhetstabeller, som gjenspeiler resultatene av beregninger av komplekse utsagn for forskjellige verdier av de originale enkle utsagn. Enkle utsagn er angitt med variabler (for eksempel A og B).

Logiske grunnprinsipper for datamaskin

Datamaskiner bruker forskjellige enheter, hvis drift er perfekt beskrevet av logikkens algebra. Slike enheter inkluderer grupper av brytere, utløsere, addere.

I tillegg ligger sammenhengen mellom boolsk algebra og datamaskiner i tallsystemet som brukes i datamaskinen. Som du vet, er det binært. Derfor kan dataenheter lagre og transformere både tall og verdiene til logiske variabler.

Bytte kretser

Datamaskiner bruker elektriske kretser som består av mange brytere. Bryteren kan bare være i to tilstander: lukket og åpen. I det første tilfellet går strømmen, i det andre - ikke. Det er veldig praktisk å beskrive driften av slike kretser ved å bruke logikkens algebra. Avhengig av posisjonen til bryterne, kan det hende du mottar signaler ved utgangene.

Porter, flipflops og huggorm

En port er et logisk element som aksepterer noen binære verdier og produserer andre avhengig av implementeringen. For eksempel er det porter som implementerer logisk multiplikasjon (konjunksjon), addisjon (disjunksjon) og negasjon.

Triggere og addere er relativt komplekse enheter som består av enklere elementer - porter.

Utløseren er i stand til å lagre ett binært siffer, på grunn av det faktum at den kan være i to stabile tilstander. Triggere brukes hovedsakelig i prosessorregistre.

Addere er mye brukt i prosessor aritmetiske logiske enheter (ALU) og utfører summering av binære biter.

Konstruksjonen av datamaskiner, eller rettere sagt maskinvare, er basert på den såkalte ventiler. De er ganske enkle elementer som kan kombineres med hverandre, og dermed skape ulike ordninger. Noen ordninger egner seg for gjennomføring aritmetiske operasjoner, og på grunnlag av andre bygger de annerledes hukommelse DATAMASKIN.

En ventel er en enhet som produserer resultatet av en boolsk operasjon fra dataene (signalene) som er lagt inn i den.

Den enkleste ventilen er en transistor-inverter som konverterer lavspenning til høyspenning eller omvendt (høy til lav). Dette kan tenkes å konvertere en logisk null til en logisk eller omvendt. De. vi får ventilen IKKE.

Ved å koble et par transistorer på forskjellige måter oppnås porter ELLER IKKE Og OG IKKE. Disse portene aksepterer ikke lenger ett, men to eller flere inngangssignaler. Utgangssignalet er alltid det samme og avhenger (produserer høy eller lav spenning) av inngangssignalene. Når det gjelder en NOR-port, kan en høy spenning (logisk) kun oppnås hvis alle innganger er lave. Når det gjelder en NAND-port, er det motsatte: en logisk en er oppnådd hvis alle inngangssignaler er null. Som du kan se, er dette det motsatte av slike kjente logiske operasjoner som AND og OR. Imidlertid brukes NAND- og NOR-porter ofte pga implementeringen deres er enklere: AND-NOT og NOR-NOT implementeres av to transistorer, mens logiske AND og OR er implementert av tre.

Portutgangen kan uttrykkes som en funksjon av inngangene.

Det tar svært kort tid for en transistor å bytte fra en tilstand til en annen (svitsjetiden måles i nanosekunder). Og dette er en av de betydelige fordelene med ordninger bygget på deres grunnlag.

For logiske verdier brukes tre operasjoner vanligvis:

Konjunksjon– logisk multiplikasjon (AND) – og, &, ∧.
Disjunksjon– logisk addisjon (ELLER) – eller, |, v.
Logisk negasjon (IKKE) – ikke,.

Logiske uttrykk kan konverteres iht logikkens algebralover:

Refleksivitetens lover
a ∨ a = a
a ∧ a = a
Kommutativitetslover
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Assosiativitetens lover
(a ∧ b) ∧ c = a ∧ (b ∧ c)
(a ∨ b) ∨ c = a ∨ (b ∨ c)
Fordelingslover
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Loven om negasjon av negasjon
(a) = a
De Morgans lover
(a ∧ b) = a ∨ b
(a ∨ b) = a ∧ b
Lover for absorpsjon
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a

Hver logisk formel definerer en boolsk funksjon. På den annen side, for enhver boolsk funksjon kan man skrive uendelig mange formler som representerer den. En av hovedoppgavene til logisk algebra er å finne kanonisk x-former (dvs. formler konstruert i henhold til en bestemt regel, kanon), samt de enkleste formlene som representerer boolske funksjoner.

Hvis en logisk funksjon uttrykkes gjennom disjunksjon, konjunksjon og negasjon av variabler, kalles denne representasjonsformen normal. Blant vanlige former er det de der funksjoner er skrevet på en unik måte. De kalles perfekt.

En spesiell rolle i logikkens algebra spilles av klassene av disjunktive og konjunktive perfekte normalformer. De er basert på begrepene elementær disjunksjon og elementær konjunksjon.

Formelen kalles elementær konjunksjon, hvis det er konjunksjonen av en eller flere variabler, tatt med eller uten negasjon. En variabel eller dens negasjon vurderes ettledd elementær konjunksjon.

Formelen kalles elementær disjunksjon, hvis det er en disjunksjon (kanskje monomial) av variabler og negasjoner av variabler.

DNF OG SDNF

Formelen kalles disjunktiv normalform(DNF), hvis det er en disjunksjon av ikke-repeterende elementære konjunksjoner. DNF-er er skrevet som: А1 v А2 v ... v Аn, hvor hver An- elementær konjunksjon.

Formel EN fra k variabler kalles perfekt disjunktiv normalform(SDNF), hvis:
1.A er en DNF der hver elementær konjunksjon er en konjunksjon k variabler x1, x2, …, xk, og på det i-te stedet i denne konjunksjonen er det enten en variabel xi eller dens fornektelse;
2. Alle elementære konjunksjoner i en slik DNF er parvis distinkte.

For eksempel: A = x1 & IKKE x2 v x1 & x2

En perfekt disjunktiv normalform er en formel konstruert i henhold til strengt definerte regler opp til rekkefølgen til de elementære konjunksjonene (disjunktive leddene) i den.

Det er et eksempel på en unik representasjon av en boolsk funksjon i form av en formel (algebraisk) notasjon.

SDNF-teorem

La f(x1 x2, …, xn)– Boolsk funksjon av n variabler som ikke er identisk null. Så er det en perfekt disjunktiv normalform som uttrykker funksjonen f.

Algoritme for å konstruere SDNF ved hjelp av en sannhetstabell:

1. I sannhetstabellen markerer vi settene med variabler der verdien av funksjonen f = 1.
2.For hvert markert sett skriver vi konjunksjonen av alle variabler som følger: hvis verdien av en variabel i dette settet er lik 1, inkluderer vi selve variabelen i konjunksjonen, ellers negasjonen.
3. Vi kobler alle de resulterende konjunksjonene med disjunksjonsoperasjoner.

KNF OG SKNF

Formelen kalles konjunktiv normalform(CNF), hvis det er en konjunksjon av ikke-repeterende elementære disjunksjoner. CNF-er er skrevet i formen: A1 & A2 & ... & An, hvor hver An– elementær disjunksjon.

Formel EN fra k variabler kalles perfekt konjunktiv normalform(SKNF), hvis:
1. A er en CNF der hver elementær disjunksjon er en disjunksjon k variabler x1, x2, …, xk, og på det i-te stedet for denne disjunksjonen er det enten variabelen xi eller dens negasjon;
2. Alle elementære disjunksjoner i en slik CNF er parvis distinkte.

For eksempel: A = (x1 v IKKE x2) & (x1 v x2)

SCNF-teorem

La f(x1 x2, …, xn)– Boolsk funksjon av n variabler som ikke er identisk null. Så er det en perfekt konjunktiv normalform som uttrykker funksjonen f.

Algoritme for å konstruere SCNF ved å bruke en sannhetstabell:

1. I sannhetstabellen markerer vi settene med variabler der verdien av funksjonen f = 0.
2. For hvert markert sett skriver vi disjunksjonen av alle variabler som følger: hvis verdien av en variabel i dette settet er lik 0, inkluderer vi selve variabelen i disjunksjonen ellers negasjonen.
3. Vi kobler alle de resulterende disjunksjonene med konjunksjonsoperasjoner.

Fra algoritmene for å konstruere SDNF og SCNF følger det at hvis funksjonen for de fleste settene med variabelverdier er lik 0, så er det lettere å konstruere SDNF for å oppnå formelen, ellers - SCNF.

Minimere logiske funksjoner ved å bruke Karnaugh-kart

Karnaugh-kartet er en grafisk måte å minimere svitsjfunksjoner (boolske) funksjoner på, noe som gir relativt enkelt arbeid med store uttrykk og eliminerer potensielle raser. Representerer operasjonene med parvis ufullstendig liming og elementær absorpsjon. Karnaugh-kart betraktes som sannhetstabellen for en funksjon som er omorganisert tilsvarende. Carnaugh-kart kan betraktes som en spesifikk flat utvikling av en n-dimensjonal boolsk kube.

Carnot-kart ble oppfunnet i 1952 av Edward W. Veitch og forbedret i 1953 av Maurice Carnot, en fysiker ved Bell Labs, og var ment å bidra til å forenkle digitale elektroniske kretser.

I et Carnaugh-kart blir boolske variabler overført fra sannhetstabellen og ordnet ved hjelp av grå kode, der hvert neste tall skiller seg fra det forrige med bare ett siffer.

Hovedmetoden for å minimere logiske funksjoner presentert i form av SDNF eller SCNF er operasjonen av parvis ufullstendig liming og elementær absorpsjon. Operasjonen av parvis liming utføres mellom to termer (medlemmer) som inneholder identiske variabler, hvis forekomster (direkte og invers) sammenfaller for alle variabler unntatt én. I dette tilfellet kan alle variabler bortsett fra én tas ut av parentes, og de direkte og inverse forekomstene av én variabel som er igjen i parentes kan limes sammen. For eksempel:

Muligheten for absorpsjon følger av de åpenbare likhetene

Dermed er hovedoppgaven med å minimere SDNF og SCNF å finne termer som egner seg for liming med påfølgende absorpsjon, noe som kan være en ganske vanskelig oppgave for store former. Carnaugh-kart gir en visuell måte å finne slike termer på.

Figuren viser en enkel sannhetstabell for en funksjon av to variabler, en 2-dimensjonal kube (kvadrat) som tilsvarer denne tabellen, samt en 2-dimensjonal kube med betegnelsen SDNF-ledd og en ekvivalent tabell for gruppering av termer:

Veitch diagram metode.

"Metoden lar deg raskt få minimale DNF-er for en boolsk funksjon f av et lite antall variabler. Metoden er basert på å spesifisere boolske funksjoner ved hjelp av diagrammer av en spesiell type, kalt Veitch-diagrammer. For en boolsk funksjon av to variabler, Veitch diagram har formen (tabell 4.4.1).

Hver celle i diagrammet tilsvarer et sett med boolske funksjonsvariabler i sannhetstabellen. I (Tabell 4.4.1) vises denne korrespondansen. I cellen i Veitch-diagrammet plasseres en enhet hvis den boolske funksjonen tar enhetsverdien på det tilsvarende settet. Nullverdier for den boolske funksjonen er ikke satt i Veitch-diagrammet. For en boolsk funksjon av tre variabler har Veitch-diagrammet følgende form (tabell 4.4.2).

Ved å legge til samme tabell til den gir det et diagram for en funksjon av 4 variabler (tabell 4.4.3).

På samme måte, det vil si, ved å legge til et annet diagram med 3 variabler til den som nettopp er vurdert, kan du få et diagram for en funksjon av 5 variabler osv., men diagrammer for funksjoner med mer enn 4 variabler brukes sjelden. Følgende diagrammer er typiske:

Syntesen av kombinasjonskretser kan illustreres ved å løse et enkelt problem.

Oppgave 1

Opptaksutvalget, som består av tre kommisjonsmedlemmer og en leder, avgjør søkerens skjebne med flertall. Ved lik stemmefordeling avgjøres flertallet av den gruppe valgkomiteens leder befinner seg i. Bygg en automat som sikrer fastsettelse av flertallet av stemmene.

Løsning

Ved å ta hensyn til forutsetningene ovenfor, kan problemtilstanden representeres entydig i form av en sannhetstabell.

Vi fyller ut tabellen under hensyntagen til at funksjonen f er fullstendig definert, dvs. den er definert på alle mulige sett med variabler x1 - x4. For n inngangsvariabler er det N = 2n sett med variabler. I vårt eksempel er N = 24 = 16 sett.

Disse settene kan skrives i hvilken som helst rekkefølge, men det er bedre i stigende binær koderekkefølge.

Desimaltallsystem

Grunnlaget for dette tallsystemet p er lik ti. Dette tallsystemet bruker ti sifre. For øyeblikket er symbolene som brukes for å betegne disse tallene 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Et tall i desimaltallsystemet skrives som summen av enheter, tiere, hundrevis, tusenvis , og så videre. Det vil si at vektene til tilstøtende sifre avviker med en faktor på ti. Tall mindre enn ett skrives på samme måte. I dette tilfellet vil sifrene i tallet kalles tideler, hundredeler eller tusendeler av en enhet.

La oss se på et eksempel på å skrive et desimaltall. For å vise at eksemplet bruker desimaltallsystemet, bruker vi indeksen 10. Hvis det i tillegg til desimalformen for å skrive tall ikke er ment å brukes annen form for registrering, så brukes vanligvis ikke indeksen:

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

Her vil det viktigste sifferet i tallet bli kalt hundrevis. I eksemplet ovenfor tilsvarer hundrevis tallet 2. Det neste sifferet vil bli kalt tiere. I eksemplet ovenfor tilsvarer tallet 4 tiere. Det neste sifferet vil bli kalt enere. I eksemplet ovenfor tilsvarer enheter tallet 7. Tiendedeler tilsvarer tallet 5, og hundredeler – 6.

Binært tallsystem

Grunnlaget for dette tallsystemet p er lik to. Dette tallsystemet bruker to sifre. For ikke å finne opp nye symboler for å betegne tall, ble symbolene til desimalsifrene 0 og 1 brukt i det binære tallsystemet For ikke å forveksle tallsystemet ved å skrive et tall, brukes indeksen 2 tillegg til den binære formen for å skrive tall, er ingen annen form ment å brukes, da kan denne indeksen utelates.

Et tall i dette tallsystemet skrives som summen av enere, toere, firere, åttere og så videre. Det vil si at vektene til tilstøtende sifre avviker med en faktor på to. Tall mindre enn ett skrives på samme måte. I dette tilfellet vil sifrene i tallet kalles halvdeler, fjerdedeler eller åttendedeler av en enhet.

La oss se på et eksempel på å skrive et binært tall:

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

Når vi skrev i den andre linjen et eksempel på desimalekvivalenter av binære sifre, skrev vi ikke potenser av to som multipliseres med null, siden dette bare ville føre til rot i formelen og som et resultat gjøre det vanskelig å forstå materialet .

En ulempe med det binære tallsystemet kan betraktes som det store antallet sifre som kreves for å skrive tall. En fordel med dette tallsystemet er at det er enkelt å utføre aritmetiske operasjoner, som vil bli diskutert senere.

Oktalt tallsystem

Grunnlaget for dette tallsystemet p er lik åtte. Det oktale tallsystemet kan tenkes på som en kortere måte å skrive binære tall på, siden tallet åtte er en potens av to. Dette tallsystemet bruker åtte sifre. For ikke å finne opp nye symboler for å betegne tall, ble desimaltallsymbolene 0, 1, 2, 3, 4, 5, 6 og 7 brukt i det oktale tallsystemet, for ikke å forvirre tallsystemet, indeksen 8 brukes til å skrive tallet I tillegg til den oktale formen for å skrive tall, forventes ingen annen notasjonsform, da kan denne indeksen utelates.

Et tall i dette tallsystemet skrives som summen av enere, åttere, sekstifirere og så videre. Det vil si at vektene til tilstøtende sifre avviker med en faktor på åtte. Tall mindre enn ett skrives på samme måte. I dette tilfellet vil sifrene i tallet bli kalt åttendedeler, sekstifire og så videre, brøkdeler av én.

La oss se på et eksempel på å skrive et oktalt tall:

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

Den andre linjen i eksemplet ovenfor konverterer faktisk et tall skrevet i oktal form til desimalrepresentasjonen av det samme tallet. Det vil si at vi faktisk så på en av måtene å konvertere tall fra en representasjonsform til en annen.

Siden formelen bruker enkle brøker, er det mulig at eksakt oversettelse fra en representasjonsform til en annen blir umulig. I dette tilfellet er de begrenset til et spesifisert antall brøksiffer.

Typer digitale komparatorer

Komparator for å sammenligne forskjellige polaritetssignaler

Komparator for å sammenligne unipolare signaler

Komparator for å sammenligne unipolare spenninger med en hysteresekarakteristikk. I de betraktede komparatorene kan egenskaper med hystereseegenskaper oppnås. Innføringen av hysterese i driften av komparatoren reduserer nøyaktigheten av sammenligningen noe, men gjør den immun mot støy og forstyrrelser. Hysterese oppnås ved å skru på en høyere referansespenning når spenningen endres fra lavt til høyt nivå, sammenlignet med verdien som brukes når spenningen endres fra høyt til lavt nivå. I dette tilfellet kalles en høy referansespenningsverdi den øvre responsterskelen, og en lav verdi kalles den nedre responsterskelen. Dette oppnås ved å innføre positive tilbakemeldinger.

Multi-bit komparatorer

La oss som et eksempel vurdere en fire-bits digital komparator av K555SP1-serien, hvis åtte innganger brukes til å koble to fire-bits ord: A0. A3, B0. B3 skal sammenlignes. Kontrollinnganger I(A>B), (A = B) og I(A< В) могут быть использованы для наращивания разрядности компаратора. Предусмотрены три выхода результата сравнения: А>B, A = B og A<В.

Sannhetstabellen til en slik komparator (tabell 1) er delt rad for rad i tre seksjoner.

Den første seksjonen (de øverste åtte radene i tabellen) definerer tilfellet når komparatoren fungerer når firebitsordene som skal sammenlignes ikke er like med hverandre. I dette tilfellet har ikke signalene ved inngangene for å øke bitdybden som en reaksjon på signalene til de nedre bitene til ordene som sammenlignes, noen effekt på resultatet av sammenligningen.

Ris. 1. Konvensjonell grafisk representasjon av en komparator type SP1

De tre radene i den andre delen av denne tabellen karakteriserer operasjonen til komparatoren med en sekvensiell metode for å øke bitdybden, dvs. når utgangene til lavordens komparatoren er koblet til kontrollinngangene til høyordens komparatoren.

Enkeltbits komparatorer

En enkeltbits komparator har to innganger, som samtidig mottar enkeltbits binære tall x1 og x2, og tre utganger (=, >,<). Из таблицы истинности логические уравнения компаратора при сравнении x1 с x2 получаются в виде

Implementeringen av en slik komparator i NAND-grunnlaget fører til følgende figur (fig. 2):

Figur 2. Enkeltbits binær komparator.

Tabell 1. Sannhetstabell for en fire-bits komparator type SP1

Komparator(analoge signaler) (eng. komparator - sammenligningsenhet) - en elektronisk krets som mottar to analoge signaler ved sine innganger og produserer en logisk "1" hvis signalet på den direkte inngangen ("+") er større enn ved den inverse inngangen (“−” ), og logisk “0” hvis signalet ved den direkte inngangen er mindre enn ved den inverse inngangen.

En sammenligningsspenning til den binære komparatoren deler hele inngangsspenningsområdet i to underområder. Det binære logiske signalet (bit) ved utgangen til den binære komparatoren indikerer hvilken av de to underområdene inngangsspenningen er innenfor.

Den enkleste komparatoren er en differensialforsterker. Komparatoren skiller seg fra en lineær operasjonsforsterker (op-amp) i utformingen av både inngangs- og utgangstrinn:

Komparatorinngangstrinnet må tåle et bredt spekter av inngangsspenninger mellom de inverterende og ikke-inverterende inngangene, opp til svingningen av forsyningsspenningene, og raskt komme seg når tegnet på denne spenningen endres.
Utgangstrinnet til komparatoren er kompatibelt når det gjelder logiske nivåer og strømmer med en spesifikk type logiske kretsinnganger (TTL, ESL-teknologier, etc.). Utgangstrinn basert på en enkelt transistor med åpen kollektor er mulig (kompatibel med TTL- og CMOS-logikk).
For å danne en hysteretisk overføringskarakteristikk, er komparatorer ofte dekket med positive tilbakemeldinger. Dette tiltaket unngår rask uønsket veksling av utgangstilstanden på grunn av støy i inngangssignalet når inngangssignalet endres sakte.

Når rtilføres den inverterende inngangen, tilføres inngangssignalet til den ikke-inverterende inngangen, og komparatoren er ikke-inverterende (følger, buffer).

Ved å tilføre rtil den ikke-inverterende inngangen, blir inngangssignalet tilført den inverterende inngangen og komparatoren inverterer (inverterer).

Komparatorer basert på logiske elementer dekket av tilbakemelding er noe sjeldnere brukt (se for eksempel en Schmitt-utløser - ikke en komparator av natur, men en enhet med svært likt bruksområde).

Ved matematisk modellering av en komparator, oppstår problemet med utgangsspenningen til komparatoren når spenningene ved begge inngangene til komparatoren er de samme. På dette tidspunktet er komparatoren i en tilstand av ustabil likevekt. Problemet kan løses på mange forskjellige måter, beskrevet i underavsnittet "programvarekomparator".

Pulsteller– en elektronisk enhet utformet for å telle antall pulser påført inngangen. Antall mottatte pulser uttrykkes i det binære tallsystemet.

Pulsetellere er en type registre (telleregistre) og er bygget på henholdsvis flip-flops og logiske elementer.

Hovedindikatorene for tellere er tellekoeffisienten K 2n - antall pulser som kan telles av telleren. For eksempel kan en teller som består av fire flip-flops ha en maksimal tellefaktor på 24=16. For en fire-trigger teller er minimum utgangskode 0000, maksimum er -1111, og med en tellekoeffisient Kc = 10, stopper uttellingen ved kode 1001 = 9.

Figur 1, a viser kretsen til en fire-bit teller som bruker T-flip-flops koblet i serie. Tellepulser tilføres telleinngangen til den første flip-flop. Telleinngangene til påfølgende flip-flops er koblet til utgangene til tidligere flip-flops.

Virkemåten til kretsen er illustrert av tidsdiagrammene vist i figur 1, b. Når den første tellepulsen ankommer, etter dens nedgang, går den første utløseren inn i tilstand Q1 = 1, dvs. Den digitale koden 0001 skrives i telleren. Ved slutten av den andre tellepulsen bytter den første utløseren til "0"-tilstanden, og den andre til "1"-tilstanden. Telleren registrerer tallet 2 med kode 0010.

Figur 1 – Binær fire-bit teller: a) krets, b) grafisk betegnelse, c) tidsdiagrammer for operasjonen

Fra diagrammet (fig. 1, b) er det klart at, for eksempel, i henhold til nedgangen til den 5. pulsen, er kode 0101 skrevet i telleren, i henhold til 9. - 1001, etc. På slutten av den 15. pulsen settes alle biter av telleren til "1"-tilstanden, og ved fallet av den 16. pulsen tilbakestilles alle triggere, det vil si at telleren går til sin opprinnelige tilstand. For å tvinge telleren til null, er det en "reset"-inngang.

Tellekoeffisienten til en binær teller er funnet fra relasjonen Ксч = 2n, hvor n er antall biter (triggere) til telleren.

Å telle antall pulser er den vanligste operasjonen i digitale informasjonsbehandlingsenheter.

Under drift av den binære telleren halveres pulsrepetisjonshastigheten ved utgangen av hver påfølgende trigger sammenlignet med frekvensen til dens inngangspulser (fig. 1, b). Derfor brukes tellere også som frekvensdelere.

Kryptering(også kalt enkoder) konverterer signalet til en digital kode, oftest desimaltall til det binære tallsystemet.

Enkoderen har m innganger, nummerert sekvensielt med desimaltall (0, 1,2,..., m - 1), og n utganger. Antall innganger og utganger bestemmes av avhengigheten 2n = m (fig. 2, a). Symbolet "CD" er dannet av bokstavene i det engelske ordet Coder.

Påføring av et signal til en av inngangene resulterer i at utgangene vises til et n-bit binært tall som tilsvarer inngangsnummeret. For eksempel, når en puls tilføres den 4. inngangen, vises en digital kode 100 ved utgangene (fig. 2, a).

Dekodere (også kalt dekodere) brukes til å konvertere binære tall tilbake til små desimaltall. Dekoderinngangene (fig. 2, b) er ment å levere binære tall, utgangene er sekvensielt nummerert med desimaltall. Når et binært tall brukes på inngangene, vises et signal ved en bestemt utgang, hvis nummer tilsvarer inngangsnummeret. For eksempel, når du bruker kode 110, vil signalet vises på den 6. utgangen.

Figur 2 – a) UGO-koder, b) UGO-dekoder

Multiplekser- en enhet der utgangen er koblet til en av inngangene, i samsvar med adressekoden. At. En multiplekser er en elektronisk bryter eller kommutator.

Figur 3 – Multiplekser: a) grafisk betegnelse, b) tilstandstabell

En adressekode leveres til inngangene A1, A2, som bestemmer hvilke av signalinngangene som skal overføres til utgangen på enheten (fig. 3).

For å konvertere informasjon fra digital til analog form bruker de digital-til-analog-omformere (DAC), og for den inverse transformasjonen - analog-til-digital omformere (ADC).

Inngangssignalet til DAC er et binært multi-bit tall, og utgangssignalet er spenningen Uout, generert basert på referansespenningen.

Analog-til-digital konverteringsprosedyren (fig. 4) består av to trinn: tidssampling (sampling) og nivåkvantisering. Samplingsprosessen består av å måle verdiene til et kontinuerlig signal kun på diskrete tidspunkter.

Figur 4 – Analog-til-digital konverteringsprosess

For kvantisering er endringsområdet i inngangssignalet delt inn i like intervaller - kvantiseringsnivåer. I vårt eksempel er det åtte, men vanligvis er det mange flere. Kvantiseringsoperasjonen kommer ned til å bestemme intervallet som den samplede verdien faller i og tilordne en digital kode til utgangsverdien.

Et register er en funksjonell enhet som kombinerer flere triggere av samme type.

Registertyper:

1) Låseregistre– bygget på låste triggere (K155TM5; K155TM7), opptak som utføres av nivået til strobesignalet.

I K155TM8-utløseren utføres opptak av den positive kanten av strobesignalet.

2) Skiftregistre– utføre funksjonen for kun sekvensiell kodemottak.

3) Universelle registre– kan motta informasjon i parallell og seriell kode.

4) Spesialregistre– K589IR12 har flere alternativer for bruk.

Skiftregister

Dette er et register, hvis innhold, når et styresignal påføres, kan forskyves mot de høyere eller lavere sifrene. For eksempel er venstre skift vist i tabell 9.

Tabell 9 Kodeskift venstre

Universelle registre

De har eksterne utganger og innganger for alle biter, samt en seriell DS-inngang.

Det finnes to typer universelle registre:

1) et register som utfører et skift i bare én retning og mottar kode parallelt (for eksempel K155IR1; K176IR3).

2) med fire driftsmoduser: gir høyre/venstre; parallell mottak; lagring (for eksempel 8-bits register K155IR13; 4-bits register K500IR141).

Den viktigste elementære operasjonen som utføres på tallkoder i digitale enheter er aritmetisk addisjon.

Logisk huggorm driftsnode som utfører aritmetikk legge til kodene til to tall. Under aritmetisk addisjon utføres andre tilleggsoperasjoner: tar i betraktning tegnene til tall, justere rekkefølgen av ledd og lignende. Disse operasjonene utføres i aritmetiske logiske enheter (ALU) eller prosesseringselementer, hvis kjerne er addere.

Huggorm klassifiseres etter ulike kriterier.

Avhengig av tallsystemet skille:

binær;
binær desimal (generelt binærkodet);
desimal;
andre (for eksempel amplitude).

Ved antall samtidig behandlede sifre i de lagte tallene:

enkeltsifret,
multi-bit.

Ved antall innganger og utganger til enkeltbits binære addere:

kvartaddere ("sum modulo 2"-elementer; "eksklusive ELLER"-elementer), karakterisert ved tilstedeværelsen av to innganger, som to ensifrede tall leveres til, og en utgang, hvor deres aritmetiske sum er realisert;
halv-addere, karakterisert ved tilstedeværelsen av to innganger, som de samme sifrene av to tall leveres til, og to utganger: en implementerer den aritmetiske summen i et gitt siffer, og den andre bærer en overføring til neste (høyere siffer) ;
komplette enkeltbits binære addere, karakterisert ved tilstedeværelsen av tre innganger, som de samme sifrene av to tall som legges til og en overføring fra forrige (nedre) siffer leveres til, og to utganger: på den ene, den aritmetiske summen i dette siffer er realisert, og på den andre overføringen til neste (høyere) utladning).

Ved å representere og behandle lagte tall multi-bit addere er delt inn i:

sekvensiell, der tall behandles ett etter ett, siffer for siffer på samme utstyr;
parallell, der begrepene legges til samtidig på tvers av alle sifre, og hvert siffer har sitt eget utstyr.

I det enkleste tilfellet består en parallell adderer av n en-bit adderere, sekvensielt (fra minst signifikante til mest signifikante) forbundet med bærekretser. Imidlertid er en slik adderingskrets preget av en relativt lav ytelse, siden genereringen av sum- og bæresignaler i hver i-te bit skjer først etter at overføringssignalet ankommer fra (i-1)'te bit addereren bestemmes av signalforplantningstiden langs overføringskjeden. Å redusere denne tiden er hovedoppgaven ved konstruksjon av parallelle hoggormer.

For å redusere forplantningstiden til overføringssignalet, bruk: Konstruktive beslutninger

EGENSKAPER TIL LOGISKE OPERASJONER

1. Betegnelser

1.1. Notasjon for logiske koblinger (operasjoner):

en) negasjon(inversjon, logisk IKKE) er merket med ¬ (for eksempel ¬A);

b) konjunksjon(logisk multiplikasjon, logisk OG) er merket med /\
(for eksempel A /\ B) eller & (for eksempel A & B);

c) disjunksjon(logisk addisjon, logisk ELLER) er merket med \/
(for eksempel A \/ B);

d) følgende(implikasjon) er betegnet med → (for eksempel A → B);

e) identitet betegnet med ≡ (for eksempel A ≡ B). Uttrykket A ≡ B er sant hvis og bare hvis verdiene til A og B er de samme (enten er de begge sanne, eller de er begge usanne);

f) symbol 1 brukes for å betegne sannhet (sann utsagn); symbol 0 – for å indikere en løgn (falsk påstand).

1.2. To boolske uttrykk som inneholder variabler kalles tilsvarende (tilsvarende) hvis verdiene til disse uttrykkene sammenfaller for noen verdier av variablene. Dermed er uttrykkene A → B og (¬A) \/ B ekvivalente, men A /\ B og A \/ B er ikke det (betydningen av uttrykkene er forskjellige, for eksempel når A = 1, B = 0 ).

1.3. Prioriteringer av logiske operasjoner: inversjon (negasjon), konjunksjon (logisk multiplikasjon), disjunksjon (logisk addisjon), implikasjon (følgende), identitet. Dermed betyr ¬A \/ B \/ C \/ D det samme som

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

Det er mulig å skrive A \/ B \/ C i stedet for (A \/ B) \/ C. Det samme gjelder for konjunksjonen: det er mulig å skrive A /\ B /\ C i stedet for (A /\ B ) /\ C.

2. Egenskaper

Listen nedenfor er IKKE ment å være komplett, men er forhåpentligvis representativ nok.

2.1. Generelle egenskaper

For et sett med n det er nøyaktig logiske variabler 2 n forskjellige betydninger. Sannhetstabell for logisk uttrykk fra n variabler inneholder n+1 kolonne og 2 n linjer.

2.2.Disjunksjon

Hvis minst ett av underuttrykkene som disjunksjonen brukes på, er sant for et sett med verdier av variablene, er hele disjunksjonen sann for dette settet med verdier.
Hvis alle uttrykk fra en bestemt liste er sanne på et bestemt sett med variabelverdier, er disjunksjonen av disse uttrykkene også sanne.
Hvis alle uttrykk fra en bestemt liste er falske på et bestemt sett med variabelverdier, så er disjunksjonen av disse uttrykkene også falsk.
Betydningen av en disjunksjon avhenger ikke av skriverekkefølgen til underuttrykkene den brukes på.

2.3. Konjunksjon

Hvis minst ett av underuttrykkene som konjunksjonen brukes på er usann på et sett med variabelverdier, er hele konjunksjonen usann for dette settet med verdier.
Hvis alle uttrykk fra en bestemt liste er sanne på et bestemt sett med variabelverdier, så er konjunksjonen av disse uttrykkene også sanne.
Hvis alle uttrykk fra en bestemt liste er falske på et bestemt sett med variabelverdier, så er konjunksjonen til disse uttrykkene også falsk.
Betydningen av en konjunksjon avhenger ikke av skriverekkefølgen til underuttrykkene den brukes på.

2.4. Enkle disjunksjoner og konjunksjoner

La oss kalle (for enkelhets skyld) konjunksjonen enkel, hvis underuttrykkene som konjunksjonen brukes på er distinkte variabler eller deres negasjoner. På samme måte kalles disjunksjonen enkel, hvis underuttrykkene som disjunksjonen brukes på er distinkte variabler eller deres negasjoner.

En enkel konjunksjon evalueres til 1 (sann) på nøyaktig ett sett med variabelverdier.
En enkel disjunksjon evalueres til 0 (false) på nøyaktig ett sett med variabelverdier.

2.5. Implikasjon

Implikasjon EN →B tilsvarer disjunksjon (¬ A) \/ B. Denne disjunksjonen kan også skrives som følger: ¬ A\/B.
Implikasjon EN →B tar verdien 0 (false) bare hvis A=1 Og B=0. Hvis A=0, så implikasjonen EN →B sant for enhver verdi B.

Konjunksjon: tilsvarer konjunksjonen: "og", angitt med tegnet^, angir logisk multiplikasjon.

En konjunksjon av to logiske ~ er sann hvis og bare hvis begge utsagnene er sanne. Kan generaliseres for et hvilket som helst antall variabler A^B^C = 1 hvis A=1, B=1, C=1.

Sannhetstabell for operasjonen "Konjunksjon":

Tabell nr. 2

Disjunksjon

Den logiske operasjonen tilsvarer foreningen OR, betegnet med tegnet v, ellers kalt LOGISK ADDITION.

En disjunksjon av to logiske variabler er falsk hvis og en småstein er falsk hvis begge utsagnene er usanne.

Denne definisjonen kan generaliseres til et hvilket som helst antall logiske variabler kombinert med en disjunksjon.

A v B v C = 0, bare hvis A = O, B = O, C - 0.

Sannhetstabell for operasjonen "Disjunksjon":

Tabell nr. 3

Inversjon

Den logiske operasjonen tilsvarer partikkelen ikke, er betegnet med ¬ eller ¯ og er en logisk negasjon.

Inversen av en boolsk variabel er sann hvis variabelen er usann og omvendt: inversen er usann hvis variabelen er sann.

Sannhetstabell for operasjon "Inversjon":

Tabell nr. 5

Ekvivalensen "Og så B og bare da" er betegnet med A ~ B

Tabell nr. 6

Når du beregner verdien av et logisk uttrykk (formel), beregnes logiske operasjoner i en bestemt rekkefølge, i henhold til deres prioritet:

inversjon;

konjunksjon;

disjunksjon;

implikasjon og ekvivalens;

Operasjoner med samme prioritet utføres fra venstre til høyre. Parenteser brukes til å endre rekkefølgen på handlinger.

Formalisering av uttalelser

Naturlige språk brukes til å lage beskrivende informasjonsmodeller. Tallrike beskrivende informasjonsmodeller er kjent i vitenskapshistorien; for eksempel ble den heliosentriske modellen av verden som Copernicus foreslo, formulert som følger:

Jorden roterer rundt sin akse og rundt solen;

alle planeter går i bane rundt solen;

Ved hjelp av formelle språk bygges formelle informasjonsmodeller (matematiske, logiske osv.). Et av de mest brukte formelle språkene er matematikk. Modeller bygget ved hjelp av matematiske konsepter og formler kalles matematiske modeller. Matematikkens språk er en samling av formelle språk.

Algebraspråket lar en formalisere funksjonelle avhengigheter mellom mengder. Dermed formaliserte Newton det heliosentriske systemet i verden, oppdaget mekanikkens lover og loven om universell gravitasjon og skrev dem ned i form av algebraiske funksjonelle avhengigheter. For eksempel, i et skolefysikkkurs vurderes mange forskjellige funksjonelle avhengigheter, uttrykt i algebraspråket, som er matematiske modeller av fenomenene eller prosessene som studeres.

Språket i logisk algebra (proposisjonalgebra) lar deg bygge formelle logiske modeller. Ved å bruke proposisjonalgebra kan du formalisere (skrive i form av logiske uttrykk) enkle og komplekse utsagn uttrykt i naturlig språk. Å bygge logiske modeller lar deg løse logiske problemer, bygge logiske modeller av dataenheter (adder, trigger) og så videre.

Prosessen med å bygge informasjonsmodeller ved hjelp av formelle språk kalles formalisering.

I prosessen med å forstå verden rundt oss, bruker menneskeheten hele tiden modellering og formalisering. Når du studerer et nytt objekt, først er dens beskrivende informasjonsmodell vanligvis bygget i naturlig språk, deretter er den formalisert, det vil si uttrykt ved hjelp av formelle språk (matematikk, logikk, etc.).

Algebra av logikk og logiske grunnlag for datamaskinen

Algebra for logikk (boolsk algebra) er en gren av matematikken som oppsto på 1800-tallet takket være innsatsen til en engelsk matematiker J. Boulya. Til å begynne med hadde boolsk algebra ingen praktisk betydning. Imidlertid fant bestemmelsene allerede på 1900-tallet anvendelse i å beskrive funksjonen og utviklingen av forskjellige elektroniske kretser. Lovene og apparatet til logisk algebra begynte å bli brukt i utformingen av forskjellige deler av datamaskiner (minne, prosessor). Selv om dette ikke er det eneste anvendelsesområdet for denne vitenskapen.

Hva er det? algebra av logikk? Først studerer den metoder for å fastslå sannheten eller usannheten til komplekse logiske utsagn ved bruk av algebraiske metoder. For det andre gjør boolsk algebra dette på en slik måte at en kompleks logisk setning beskrives av en funksjon, hvis resultat kan være enten sant eller usant (1 eller 0). I dette tilfellet kan funksjonsargumenter (enkle utsagn) også ha bare to verdier: 0 eller 1.

Hva er enkelt logisk påstand? Dette er setninger som "to er mer enn én", "5.8 er et heltall". I det første tilfellet har vi sannhet, og i det andre har vi usann. Logikkens algebra angår ikke essensen av disse utsagnene. Hvis noen bestemmer seg for at utsagnet "Jorden er kvadratisk" er sant, vil logikkens algebra akseptere dette som et faktum. Faktum er at boolsk algebra omhandler å beregne resultatet av komplekse logiske utsagn basert på de tidligere kjente verdiene til enkle utsagn.

Logiske operasjoner. Disjunksjon, konjunksjon og negasjon

Hvordan avgjør vi at det vi har blitt fortalt er sant eller ikke? På en eller annen måte logisk, selv et ubevisst sted, basert på tidligere livserfaring, forstår vi at sannheten med foreningen "og" forekommer i tilfelle av sannheten til begge enkle utsagn. Når man først blir en løgn, vil hele det komplekse utsagnet være falskt. Men med det bindende "eller" må bare ett enkelt utsagn være sant, og da vil hele uttrykket bli sant.

Logikkens algebra involverer mange logiske operasjoner. Tre av dem fortjener imidlertid spesiell oppmerksomhet, fordi... med deres hjelp kan du beskrive alle de andre, og derfor bruke mindre utvalg av enheter når du designer kretser. Slike operasjoner er konjunksjon (AND), disjunksjon (OR) og negasjon (NOT). Ofte er konjunksjonen betegnet med &, disjunksjonen med ||, og negasjonen med en strek over variabelen som angir utsagnet.

På konjunksjon@/a> sant med et falskt uttrykk oppstår bare hvis alle de enkle uttrykkene som utgjør komplekset er sanne. I alle andre tilfeller vil det komplekse uttrykket være usant.

På disjunksjoner sannhet et komplekst uttrykk oppstår når minst ett enkelt uttrykk inkludert i det er sant, eller to samtidig. Det hender at et komplekst uttrykk består av mer enn to enkle. I dette tilfellet er det nok at en enkel er sann, og da vil hele utsagnet være sant.

Negasjon- dette er en unær operasjon, fordi den utføres i forhold til ett enkelt uttrykk eller i forhold til resultatet av et komplekst. Som et resultat av negasjon oppnås en ny uttalelse som er motsatt av den opprinnelige.

For logiske verdier brukes tre operasjoner vanligvis:

Konjunksjon - logisk multiplikasjon (AND) - og, &, ∧.

Disjunksjon - logisk addisjon (OR) - eller, |, v.

Logisk negasjon (IKKE) - ikke,.

Det er praktisk å beskrive logiske operasjoner med såkalte sannhetstabeller, som gjenspeiler resultatene av beregninger av komplekse utsagn for ulike verdier av de originale enkle utsagn. Enkle utsagn er angitt med variabler (for eksempel A og B).

Logiske grunnprinsipper for datamaskin

Datamaskiner bruker forskjellige enheter, hvis drift er perfekt beskrevet av logikkens algebra. Slike enheter inkluderer grupper av brytere, utløsere, addere.

Bytte kretser

Porter, flipflops og huggorm

Utløsere Og hoggormer- dette er relativt komplekse enheter som består av enklere elementer - ventiler.

Utløseren er i stand til å lagre ett binært siffer, på grunn av det faktum at den kan være i to stabile tilstander. Triggere brukes hovedsakelig i prosessorregistre.

Addere er mye brukt i prosessor aritmetiske logiske enheter (ALU) og utfører summering av binære biter.

Informasjon og informasjonsprosesser. Typer informasjon, dens binære koding. Mengde informasjon, tilnærminger til å definere begrepet "mengde informasjon", måleenheter for informasjon. Binær koding av numerisk, tekst, grafikk, lydinformasjon

Informasjon(fra latin informatio - "forklaring, presentasjon, bevissthet") - informasjon om noe, uavhengig av presentasjonsformen.

Foreløpig er det ingen enkelt definisjon av informasjon som et vitenskapelig begrep. Fra synspunktet til ulike kunnskapsfelt er dette konseptet beskrevet av dets spesifikke sett med egenskaper. Begrepet "informasjon" er grunnleggende i et informatikkkurs, der det er umulig å definere det gjennom andre, mer "enkle" begreper.

Informasjonsegenskaper:

Objektivitet (informasjon er objektiv hvis den ikke avhenger av noens mening eller vurdering);

Pålitelighet (informasjon er pålitelig hvis den gjenspeiler den sanne tilstanden);

Fullstendighet (informasjonen er fullstendig hvis den er tilstrekkelig for å forstå og ta en beslutning);

Relevans (informasjon er relevant, betimelig, hvis den er viktig, viktig for det nåværende tidspunkt);

Nytteverdi (vurdert av oppgavene som vi kan løse med dens hjelp);

Forståelighet (informasjon er forståelig hvis den er uttrykt på et språk som er tilgjengelig for mottakeren);

Tilgjengelighet (informasjon er tilgjengelig hvis vi kan få det).

Informasjonsprosess- et sett med sekvensielle handlinger (operasjoner) utført på informasjon (i form av data, informasjon, fakta, ideer, hypoteser, teorier osv.) for å oppnå et hvilket som helst resultat (oppnå et mål).

Informasjon manifesteres nettopp i informasjonsprosesser. Informasjonsprosesser foregår alltid i et eller annet system (sosialt, sosioteknisk, biologisk osv.).

De mest generaliserte informasjonsprosessene er innsamling, transformasjon og bruk av informasjon.

De viktigste informasjonsprosessene som studeres i et informatikkkurs inkluderer: søk, utvalg, lagring, overføring, koding, prosessering og beskyttelse av informasjon.

Informasjonsprosesser utført ved bruk av visse informasjonsteknologier danner grunnlaget for menneskelig informasjonsaktivitet.

En datamaskin er en universell enhet for automatisert utførelse av informasjonsprosesser.

Folk håndterer mange typer informasjon. Kommunikasjon mellom mennesker med hverandre hjemme og på skolen, på jobb og på gaten er overføring av informasjon. En lærers historie eller en venns historie, et fjernsynsprogram, et telegram, et brev, en muntlig melding osv. – alt dette er eksempler på informasjonsoverføring.

Og det har vi allerede snakket om at samme informasjon kan overføres og mottas på forskjellige måter. Så for å finne veien til et museum i en ukjent by, kan du spørre en forbipasserende, få hjelp fra informasjonsskranken, prøve å finne ut av det selv ved hjelp av et bykart, eller konsultere en guidebok. Når vi lytter til en lærers forklaring, leser bøker eller aviser, ser på TV-nyheter, besøker museer og utstillinger – på denne tiden får vi informasjon.

En person lagrer informasjonen mottatt i hodet hans. Den menneskelige hjernen er et enormt arkiv med informasjon. En notatblokk eller notatbok, dagboken din, skolenotatbøker, et bibliotek, et museum, en kassett med opptak av favorittlåtene dine, videobånd - alt dette er eksempler på lagring av informasjon.

Informasjon kan behandles: oversette tekst fra engelsk til russisk og omvendt, beregne summen av gitte termer, løse et problem, fargelegge bilder eller konturkart - alt dette er eksempler på informasjonsbehandling. Dere elsket alle å fargelegge fargebøker på et eller annet tidspunkt. Det viser seg at du på dette tidspunktet var engasjert i en viktig prosess - informasjonsbehandling, forvandling av en svart-hvitt-tegning til en farge.

Informasjon kan til og med gå tapt. La oss si at Dima Ivanov glemte dagboken hjemme og derfor skrev ned leksene sine på et stykke papir. Men mens han lekte i friminuttene, laget han et fly av det og lanserte det. Da han kom hjem, kunne Dima ikke gjøre leksene sine, han mistet informasjonen. Nå må han enten prøve å huske hva han ble spurt om, eller ringe en klassekamerat for å få nødvendig informasjon, eller gå på skolen med uferdige lekser.

Binær koding - en av de vanligste måtene å presentere informasjon på. I datamaskiner, roboter og numerisk styrte maskiner er som regel all informasjon som enheten omhandler kodet i form av ord i det binære alfabetet.

Det binære alfabetet består av to sifre 0 og 1.

Digitale datamaskiner (personlige datamaskiner tilhører den digitale klassen) bruker binær koding av all informasjon. Dette forklares hovedsakelig med at det teknisk sett var enklere å bygge en teknisk enhet som nøyaktig skiller mellom 2 forskjellige signaltilstander enn en som nøyaktig skiller mellom 5 eller 10 forskjellige tilstander.

Ulempene med binær koding inkluderer svært lange binære kodeposter, noe som gjør dem vanskelige å jobbe med.