Binární logika, logické operace a jejich vlastnosti, funkce a jejich úpravy, logické obvody

Binární logika

• Je to výroková logika, která zkoumá pravdivostní hodnotu výroků (pravda/nepravda) a používá logické operátory jako $\to ,\vee ,\wedge ,\leftrightarrow ,\neg$.

• Výroky jako logické výrazy vyhodnocované na hodnoty (pravda/nepravda, $1/0$)

• Pro práci s dvouhodnotovými logickými výrazy se používá Booleova algebra, což je základ binární logiky

• Fyzická realizace: Binární logika se fyzicky realizuje prostřednictvím elektronických binárních logických obvodů, které jsou základem digitálních zařízení.

• Logická proměnná $x$

  • Může nabývat dvou možných diskrétních logických hodnot: $0$ a $1$
  • definice: $x=1$, jestliže $x\ne 0$ a $x=0$, jestliže $x\ne 1$.

• Logická funkce $f(x_1,...,x_n)$

  • Funkce $n$ logických proměnných $x_1,...,x_n$ nabývající dvou možných diskrétních hodnot $0$ a $1$
  • Logická proměnná = logická funkce identity proměnné, skládání funkcí
  • Základními logickými operacemi jsou např. AND ($\wedge$), OR ($\vee$), NOT ($\neg$), atd.

• Booleova algebra (binární logika)

  • Algebra logických proměnných a funkcí: Zahrnuje práci s logickými proměnnými a logickými funkcemi pomocí matematických principů.
  • Používá pouze dvě hodnoty, $0$ a $1$.
  • Relace rovnost: $f=g$, právě když $(f=1$ a $g=1)$ nebo $(f=0$ a $g=0)$

• Logický výraz

  • Definice: Správně vytvořená posloupnost symbolů logických proměnných a funkcí (operátorů), spolu se závorkami.
  • Priority sestupně: negace($\neg$), log. součin($\wedge$), log. součet()
  • Význam: Slouží k zápisu logické funkce.

• Logická rovnice

  • Definice: Rovnost dvou logických výrazů.
  • ekvivalentní úpravy = zachování (pravdivosti rovnosti výrazů: např. negace obou stran, logický součin/součet obou stran se stejným výrazem, …, log. funkce obou stran se stejnými ostatními operandy funkce
  • Ekvivalentní úpravy: Změny, které zachovávají pravdivost rovnice, například:
    • Negace obou stran.
    • Logický součin nebo součet obou stran se stejným výrazem.
    • Použití stejné logické funkce na obě strany s identickými ostatními operandy.
  • Neekvivalentní úpravy: Změny, které mohou narušit pravdivost rovnice, například “krácení” obou stran o stejný podvýraz.

Axiomy (Booleovy algebry)

• Komutativa: $x\cdot y=y\cdot xx+y=y+x$
• Distributivita: $x\cdot (y+z)=x\cdot y+x\cdot zx+y\cdot z=(x+y)\cdot (x+z)$
• Identita/neutrálnost/existence neutrální hodnoty: $1\cdot x=x0+x=x$
• Komplementárnost: $x\cdot \neg x=0x+\neg x=1$

Logické operace

3 základní:

Negace (inverze) - $\neg$

• Pravdivá, když operand je nepravdivý, jinak nepravdivá

Logický součin (konjunkce) - $\wedge$

• Pravdivá, když oba operandy pravdivé, jinak nepravdivá

Logický součet (disjunkce) - $\vee$

• Nepravdivá, když oba operandy jsou nepravdivé, jinak pravda

Vlastnosti základních logických operací

• agresivita (nuly a jedničky): $0\cdot x=01+x=1$
• idempotence: $x\cdot x=xx+x=x$
• asociativita: $x\cdot (y\cdot z)=(x\cdot y)\cdot zx+(y+z)=(x+y)+z$
• involuce (dvojí negace): $\neg \neg x=x$
• De Morganovy zákony: $\neg (x\cdot y)=\neg x+\neg y\neg (x+y)=\neg x\cdot \neg y$
• absorpce: $x\cdot (x+y)=xx+x\cdot y=x$
• a další

Implikace - $\to$

• Nepravdivá, když první operand je pravdivý a druhý nepravdivý, jinak pravdivá

Ekvivalence - $\leftrightarrow$

• Pravdivá, když operandy mají stejnou hodnotu
• $xXNORy$, $x\equiv y$

Nonekvivalence (negace ekvivalence) - $\oplus$

• pravdivá, když operandy mají různou hodnotu, jinak nepravdivá
• $xXORy$ , $x\not\equiv y$, $x\oplus y$

Shefferova funkce (negace logického součinu) - $\uparrow$

• nepravdivá, když oba operandy pravdivé, jinak pravdivá
• $xNANDy$

Piercova funkce (negace logického součtu) - $\downarrow$

• pravdivá, když oba operandy nepravdivé, jinak nepravdivá
• $xNORy$

Fyzická realizace logických funkcí

• dnes pomocí tranzistorů (a diod) v integrovaných obvodech: technologie RTL, DTL, TTL, CMOS…
• realizace log. operací pomocí integrovaných obvodů – logických členů, hradel

Logické obvody

• jeden výstup: realizace jedné log. funkce

• více výstupů: realizace více log. funkcí zároveň → realizace vícebitové log. funkce ${}^{n}f$

• n-tice vstupů: reprezentace vícebitových (n-bitových) log. proměnných $x^n$ = vícebitový log. obvod

• kombinační: stavy na výstupech obvodu (tj. funkční hodnota) závisí pouze na okamžitých stavech na vstupech (tj. hodnotách proměnných)

• sekvenční: stavy na výstupech obvodu (tj. funkční hodnota) závisí nejen na okamžitých stavech na vstupech (tj. hodnotách proměnných), ale také na předchozích stavech na vstupech

Kombinační

Komparátor

• provádí srovnání hodnot dvou log. proměnných $A$ a $B$ na vstupu

Multiplexor

• přepíná na výstup $Q$ log. hodnotu na jednom z $2^n$ datových vstupů $D_i$ vybraném na základě $n-$bitové hodnoty na adresním vstupu $A$
• kromě výstupu $Q$ navíc ještě negovaný (invertovaný) výstup $\overline{Q}$
• použití: multiplexování datových vstupů na základě adresy

Binární dekodér

• nastaví (na $1$) jeden z $2^n$ výstupů $S_i$ odpovídající $n-$bitové hodnotě na adresním vstupu $A$
• použití: dekodér adresy pro výběr místa v paměti

Binární sčítačka

• sčítačka sečte binární hodnoty v každém řádu dvou $n-$bitových proměnných $A$ a $B$ podle pravidel aritmetiky pro sčítání, tj. s přenosem hodnoty do vyššího řádu
• platí stejná pravidla aritmetiky jako v desítkové soustavě, např. (+ je zde aritmetické sčítání!):
  • $0+0=00+1=11+1=10$
• použití: (aritmetické) sčítání binárně reprezentovaných 8-, 16-, 32-, atd. bitových čísel

Sekvenční

• stavy na výstupech obvodu (tj. funkční hodnota) závisí nejen na okamžitých stavech na vstupech (tj. hodnotách proměnných), ale také na předchozích stavech na vstupech
• předchozí stavy na vstupech zachyceny vnitřním stavem obvodu
• nutné identifikovat a synchronizovat stavy obvodu v čase

Přenos dat (hodnot vícebitových log. proměnných):

• sériový: bity (hodnoty 0/I) přenášeny postupně v čase za sebou po jednom datovém vodiči
• paralelní: bity přenášeny zároveň v čase po více datových vodičích

Klopné obvody

• nejjednodušší sekvenční obvody
• astabilní: nemají žádný stabilní stav, periodicky překlápí výstupy z jednoho stavu do druhého („kmitají“); použití jako generátory impulsů
• monostabilní: jeden stabilní stav na výstupech, po vhodném řídícím signálu je po definovanou dobu v nestabilním stavu; použití k vytváření impulsů dané délky
• bistabilní: oba stavy na výstupech stabilní, zůstává v jednom stabilním stavu dokud není vhodným řídícím signálem překlopen do druhého; použití pro realizaci pamětí

Řízení:

• asynchronně signály ($0$ nebo $1$) na datových vstupech
• synchronně hodinovým signálem
• hladinou signálu: horní ($1$) nebo dolní ($0$)
• hranami signálu: nástupní ($0\to 1$ u horní hladiny) nebo sestupní ($0\to 1$ u dolní hladiny)

Klopný obvod (typu) RS

• nejjednodušší bistabilní, základ ostatních
• asynchronní vstupy $R$ (Reset) pro nulování log. hodnoty na výstupu $Q$ (v čase $i$) a $S$ (Set) pro nastavení hodnoty
• kromě výstupu $Q$ navíc ještě negovaný (invertovaný) výstup $Q$
• varianty: varianta se synchronizačním vstupem CLK s hodinových signálem, varianta Master-Slave

Klopný obvod (typu) D

Klopný obvod (typu) JK

Obvody v počítačích:

Paralelní registr (střádač)

• vícebitová paměť pro hodnotu dodanou paralelně na více vstupů, paralelní zapojení klopných obvodů D

Sériový (posuvný) registr:

• vícebitová paměť pro hodnotu dodanou sériově na vstupu, sériové zapojení klopných obvodů D, použití pro transformaci sériových dat na paralelní

Čítač:

• paměť počtu impulsů na hodinovém vstupu, binárně reprezentovaný počet na vícebitovém výstupu, zřetězené zapojení klopných obvodů JK

Sériová sčítačka

• (aritmetické) sčítání log. hodnot dodávaných na vstupy v sériovém tvaru po jednotlivých řádech

Navigace

Předchozí: Číselné soustavy Následující: Reprezentace čísel a znaků v počítači Celý okruh: 2. Informační technologie