2013 m. liepos 11 d., ketvirtadienis

3.2. Logikos algebros tapatybės

 

3.2. LOGIKOS ALGEBROS TAPATYBĖS

Logikos algebroje, kaip ir matematikoje, ryšiai tarp kintamųjų nusakomi aksiomomis teoremomis ir tapatybėmis.
Logikos algebros tapatybės pateiktos poromis - dviem stulpeliais.Pagal logikos algebros dualumo dėsnį kairiojo stulpelio tapatybes galime gauti iš dešinio ir priešingai. Šis dėsnis teigia: tapatybės loginę sandaugą pakeitus logine suma, o sumą sandauga; nulį vienetu, o vienetą nuliu ir skliaustais išlaikius tą pačią veiksmų tvarką, bus gauta nauja tapatybė, vadinama dualia:


Pagal 5 tapatybę:prie loginės sumos galime pridėti bet kiek tokių pat kintamųjų arba kelių vienodų kintamųjų sumą pakeisti vienu tokiu pat kintamuoju.
Pagal 6 tapatybę: loginę sandaugą galime dauginti iš bet kiek jau esančių kintamųjų arba kelis vienodus kintamuosius pakeisti vienu.
Pagal de Morgano teoremą:
  1. kintamųjų sumos inversija lygi kintamųjų inversijų sandaugai.
  2. kintamųjų sandaugos inversija lygi kintamųjų inversijų sumai.
Dėsniai taikomi bet kokiam kintamųjų skaičiui: dviem, trim ir daugiau.
Pasinaudoję pagrindinėmis tapatybėmis galime įrodyti ir daugiau tapatybių. Dažnai naudojami absorbavimo ir jungimo dėsniai.

3.1. Loginės funkcijos

3. LOGIKOS ALGEBRA

Skaitmeniniai grandynai projektuojami naudojantis loginės algebros teorija, kuri dar vadinama Bulio algebra – ją sukūrusio anglų mokslininko (J.Boole) vardu.

 

3.1 LOGINĖS FUNKCIJOS

Pagrindinė loginės algebros sąvoka – loginė funkcija. Tai tokia funkcija, kuri pati arba jos argumentai gali būti tik dviejų reikšmių – teisinga arba neteisinga. Tai esminis skirtumas nuo įprastų matematinių funkcijų. Loginės funkcijos ir jos kintamųjų reikšmes žymėsime simboliais 1 ir 0. Šie simboliai naudojami ir dvejetainėje skaičiavimo sistemoje.
Funkcijos argumentus vadiname loginiais kintamaisiais. Jei funkcija turi n loginių  kintamųjų, tai iš jų galime sudaryti 2n kintamųjų rinkinių. Iš dviejų kintamųjų galime sudaryti keturis rinkinius - 00, 01, 10, 11; iš keturių - šešiolika ir t.t.
Loginę funkciją galime pateikti keliais būdais:
· nusakyti žodžiais t.y. aprašyti;
· užrašyti jos algebrinę išraišką;
· pavaizduoti grafikų t.y. laiko diagramų pavidalu;
· pavaizduoti teisingumo lentele.

Algebrinei išraiškai galime naudoti įvairius simbolius. Dažniausiai sutinkami žymėjimai:
F= φ (A,B,C,… ); F= φ (X,Y,Z,… ) ; Y= φ (x1x2x3…) ir kt.
Teisingumo arba reikšmių lentelėje surašomi visi įmanomi kintamųjų rinkiniai ir juos atitinkančios funkcijos reikšmės.
Loginė funkcija nurodo kokią loginę operaciją norime atlikti. Skaitmeninėje technikoje logines operacijas atlieka loginiai elementai (angl. gates).
Loginių funkcijų teorijoje svarbią reikšmę turi 1 ir 2 kintamųjų funkcijos ,nes jų pagrindu sudaromos loginės funkcijos turinčios ir daugiau kintamųjų
Toliau aprašysime pagrindines 1ir 2 kintamųjų funkcijas.
KARTOJIMAS - tai vieno kintamojo funkcija.. Funkcijos reikšmė visuomet lygi kintamojo reikšmei: F = X
NE - loginis neigimas, inversija - tai vieno kintamojo funkcija. Loginis elementas vadinamas inverteriu. Funkcijos reikšmė  priešinga kintamojo reikšmei, žymima „¯ “ t.y. brūkšniu virš kintamojo:

Kitos nagrinėjamos funkcijos, tai dviejų kintamųjų funkcijos, tačiau išraiškos gali būti taikomos trims ir daugiau kintamųjų.
IR – loginė daugyba, konjunkcija. Funkcijos reikšmė lygi 1 tik tuomet , jei visi kintamieji lygūs 1. Loginė operacija žymima simboliais: „&“, „∧“, „•“, paskutinis simbolis dažniausiai nerašomas:
F = X ∧Y = X • Y = X & Y
Loginės operacijos IR rezultatus galime užrašyti:
0 • 0 = 0
0 • 1 = 0
1 • 0 = 0
1 • 1 = 1

Skaitome ne vienas dauginti iš vienobet vienas ir vienas, turime prisiminti, kad atliekame loginę operaciją.
ARBA - loginė sudėtis ,disjunkcija. Funkcijos reikšmė 1, jei bent vieno kintamojo reikšmė lygi 1. Loginė operacija žymima simboliais: „ + “, „∨ “:
F = X + Y = X ∨ Y
Loginės operacijos ARBA rezultatus galime užrašyti:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Skaitome ne vienas plius vienas, bet vienas arba vienas, visuomet turime prisiminti, kad atliekame loginę operaciją.
XOR - šiai funkcijai naudojamas angliškas sutrumpinimas, nes nėra lietuviško. Lietuviškai ši funkcija vadinama: suma moduliu 2 arba loginis nelygiavertiškumas.Tai dviejų kintamųjų loginė funkcija, jos reikšmė lygi 1, jei tik vienas kintamasis lygus 1. Loginė operacija žymima simboliu ⊕.


Loginės operacijos XOR rezultatus galime užrašyti:
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
IR-NE, ARBA-NE, XNOR yra jau minėtų funkcijų neigimas, inversija.
Funkcijos, į kurių išraišką įeina ne daugiau kaip viena loginė operacija, vadinamos elementariomis. Tai funkcijos IR,  ARBA,  NE.
Užrašant funkciją algebrinėmis išraiškomis, jos kintamieji susiejami loginių operacijų ženklais, kurie nurodo kokią loginę operaciją ir kokia tvarka reikia atlikti. Pirmiausia atliekama loginė operacija NE, sekanti – IR, po to – ARBA.
Pagrindinės vieno ir dviejų kintamųjų funkcijos parodytos lentelėje 3–1. Lentelėje taip pat parodytos teisingumo lentelės ir loginių elementų grafinio žymėjimo du variantai. Funkcijų sutrumpinti žymėjimai pateikti lietuvių, anglų ir rusų kalbomis.
Literatūroje ir kompiuterinėse programose yra naudojami abu loginių elementų žymėjimo variantai, todėl loginių schemų piešimui pakaitomis abu juos ir naudosime.
Lentelė 3-1

Lentelė 3-2. Laiko diagramos dviejų kintamųjų loginėms funkcijoms.

 

2.6. ASCII kodas

 

2.5. ASCII KODAS

Kompiuteriuose ir kituose skaitmeniniuose įtaisuose koduojami ne tik skaičiai, bet ir raidės, ir kiti simboliai. Dažniausiai naudojamas ASCII (American Standart Code for Information Interchange – Amerikos kodavimo standartas skirtas informacijos pasikeitimui) parodytas 2.6 lentelėje. Šis standartas 1963 metais priimtas JAV, o dabar naudojamas kaip tarptautinis standartas. Tai septynių bitų kodas.
Kodavimui ASCII kodais naudojama lentelė sudaryta iš 128 langelių, kurie suskirstyti į 16 eilučių ir 8 stulpelius. Eilutės sunumeruotos šešioliktainiais skaičiais nuo 0 iki F ir dvejetainiais skaičiais nuo 0000 iki 1111, kurie pažymėti B4B3B2B1. Stulpeliai sunumeruoti šešioliktainiais skaičiais nuo 0 iki 7 ir dvejetainiais skaičiais nuo 000 iki 111, kurie pažymėti B7B6B5. Dvejetainiai skaičiai naudojami ASCII kodų sudarymui, o šešioliktainiai naudojami norint sutrumpinti kodų užrašus, pav.ekrane.
Lentelė užpildyta dešimtainiais skaičiais, raidėmis, simboliais ir specialių komandų sutrumpinimais. Komandos skirtos informacijos pasikeitimo tarp kompiuterio ir įvedimo – išvedimo įtaisų operacijoms valdyti ir užima 32 langelius. Šias komandas, o tiksliau jų kodus dažniausiai formuoja procesorius ar kitas valdymo įtaisas.
Likę langeliai tai skaičiai raidės ir simboliai, kuriuos matome užrašytus ant kompiuterio klaviatūros klavišų. Nuspaudus klavišą formuojamas jį atitinkantis kodas. Užrašas SP – atitinka klavišą “Space”, o DEL – klavišą “Delete”.

2.6. lentelė

Eilutės kodas
Stulpelio kodas
B7B6B5 / HEX
000
001
010
011
100
101
110
111
B4B3B2B1
HEX
0
1
2
3
4
5
6
7
0000
0
NUL
DLE
SP
0
@
P
`
p
0001
1
SOH
DC1
!
1
A
Q
a
q
0010
2
STX
DC2
2
B
R
b
r
0011
3
ETX
DC3
#
3
C
S
c
s
0100
4
EOT
DC4
$
4
D
T
d
t
0101
5
ENQ
NAK
%
5
E
U
e
u
0110
6
ACK
SYK
&
6
F
V
f
v
0111
7
BEL
ETB
´
7
G
W
g
w
1000
8
BS
CAN
(
8
H
X
h
x
1001
9
HT
EM
)
9
I
Y
i
y
1010
A
LF
SUB
*
:
J
Z
j
z
1011
B
VT
ESC
+
;
K
[
k
{
1100
C
FF
FS
,
L
\
l
|
1101
D
CR
GS
-
=
M
]
m
}
1110
E
SO
RS
.
N
^
n
~
1111
F
SI
US
/
?
O
_
o
DEL
Langelio kodas tai jį atitinkančios eilutės ir stulpelio numerių užrašas dvejetainiais skaičiais:
B7B6B5B4B3B2B1,
kur
B4B3B2B1 – eilutės numeris;
B7B6B5 - stulpelio numeris.
Lentelėje 2.6. tamsia spalva pažymėti 3 langeliai – SP, 3 ir K. Užrašysime jų kodus:
Langelis
Dvejetainis kodas
Šešioliktainis kodas
SP
0 0 1 0  0 0 0 0
20
3
0 0 1 1  0 0 1 1
33
K
0 1 0 0  1 0 1 1
4B
ASCII kodas yra 7 bitų kodas. Kompiuteriuose informacija užrašoma 8, 16, ir t.t. bitais.Todėl ASCII kodai papildomi dar vienu bitu B8, kuris pažymimas 0. Šis bitas panaudojamas papildomos informacijos kodavimui: grafiniams simboliams, įvedant kitas kalbas, šriftus ir t.t. Tokios informacijos kodavimui sudarytos specialios lentelės, kurias galima rasti literatūroje apie kompiuterius.
ASCII kodas tai ne vienintelis kodas skirtas skaičių, raidžių ir simbolių kodavimui. Daugelyje šalių naudojami ir kiti standartai, tačiau ASCII yra naudojamas dažniausiai.

2.5. Dešimtainių skaičių kodavimas dvejetainiais - dešimtainiais kodais

 

2.5. DEŠIMTAINIŲ SKAIČIŲ KODAVIMAS DVEJETAINIAIS – DEŠIMTAINIAIS KODAIS

Jau žinome kaip dešimtainiai skaičiai užrašomi pozicinėse skaičiavimo sistemose. Informacijos vaizdavimui, saugojimui ir apdorojimui kompiuteriuose naudojama dvejetainė skaičiavimo sistema.
Dažnai informaciją patogiau apdoroti ir analizuoti, jei ji vaizduojama specialiais kodais, kurie vadinami dvejetainiais – dešimtainiais kodais. Šie kodai sudaromi naudojant du simbolius – 1 ir 0, kaip ir dvejetainėje skaičiavimo sistemoje.
Skaitmeniniuose įtaisuose naudojami 4 bitų ilgio dvejetainiai – dešimtainiai kodai, kuriuose kiekvienas dešimtainio skaičiaus skaitmuo yra užrašomas keturiais dvejetainiais simboliais t.y. tetrada. Lentelėje 2.5 pavaizduoti 3 dvejetainiai - dešimtainiai kodai. Skaitmeniniuose įtaisuose naudojama ir daugiau dvejetainių – dešimtainių kodų.
Dažniausiai naudojamas BCD kodas, jo skilčių vertės – 8 4 2 1. BCD – tai angliškas kodo sutrumpinimas - Binary Coded Decimal, verčiama – dvejetainiais koduoti dešimtainiai.
Naudojama daug skaitmeninių grandinių, kurios gali apdoroti informaciją BCD kode – tai dešifratoriai, skaitikliai ir kiti įtaisai.

Lentelė 2. 5.

Dešimtainiai
skaitmenys
Kodai ir jų skilčių vertės
B C D
8 4 2 1

2 4 2 1
Excess-3
8 4 2 1 + 3
0
1
2
3
4
5
6
7
8
9
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0

Nenaudoja-
mos kombi-
nacijos
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
0 0 0 0
0 0 0 1
0 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
Užrašant skaičius dvejetainiais – dešimtainiais kodais tarp tetradų paliekamas tarpas. Dešimtainį skaičių 1936 užrašysime skirtingais kodais, kodo pavadinimą atitinka indeksas prie raidės A:
A10 =
1
9
3
6
ABCD =
0 0 0 1
1 0 0 1
0 0 1 1
0 1 1 0
A2421 =
0 0 0 1
1 1 1 1
0 0 1 1
1 1 0 0
A8421+3 =
0 1 0 0
1 1 0 0
0 1 1 0
1 0 0 1
A2 =

0 1 1 1
1 0 0 1
0 0 0 0
Paskutinėje eilutėje ,palyginimui, užrašytas dvejetainis skaičius.
BCD kodas yra 4 bitų kodas. Kartais naudojamas 8 bitų BCD kodas – jis vadinamas išplėstu BCD kodu. Šiam kodui naudojamas angliškas sutrumpinimas EBCD – Extended BCD.

2.4. Aritmetiniai veiksmai

 

2.4. ARITMETINIAI VEIKSMAI

Mokame sudėti, atimti, dauginti ir dalinti dešimtainius skaičius. Kitose skaičiavimo sistemose šias operacijas atliekame panašiai kaip ir dešimtainėje. Daugiausiai dėmesio skirsime dvejetainei sistemai.

2.4.1 Paprasčiausios aritmetinės operacijos.

Dvejetainėje sistemoje sudėtį atliekame pagal sudėties lentelę:
0+0=  0,
0+1=  1,
1+0=  1,
1+1=10, vienas pernešamas į vyresnę skiltį.
Pavyzdys:
1 1 0 1 1 0 1
+   1 0 0 1 1 1 1

0 1 0 0 0 1 0
+ 1.     1 1    1

suma neįvertinus pernašos
1 0 1 1 1 1 0 0
galutinė suma
Sudėtį galima atlikti nenurodant pernašų, o iš karto užrašant galutinę sumą.
Šešioliktainių skaičių sudėties pavyzdys:
Veiksmai su šešioliktainiais
Atitinkami veiksmai su dešimtainiais


    1
5 9 F H

    5    9   15
+    E  4  6 H


+14

+  4

+   6

1  3  E  5 H

  19 = 16 + 3  14   21 = 16 + 5
Dešinėje pusėje paaiškinta kaip atliekama sudėtis. Jauniausioje skiltyje skaitmenį F (F = 15) sudėję su 6 gavome 21,kurį užrašėme suma 16 su 5. 16 pernešame į sekančią skiltį kaip 1. Taip pat atliekame sudėtį ir kitose skiltyse.
Dvejetainių skaičių atimties pavyzdys:
1 0 1 1 0

- 1 0 0 1 1

0 0 0 1 1
Atimdami iš nulio vienetą, skolinamės iš vyresnės skilties.
Atimties operacija, skolinantis 1 iš vyresnės skilties, skaičiavimo technikoje netaikoma. Ši operacija keičiama sudėtimi, kur skaičiai užrašomi specialiais kodais.
Visos aritmetinės operacijos kompiuteriuose ir kituose skaitmeniniuose įtaisuose atliekamos su dvejetainiais skaičiais. Sudėtis – svarbiausias veiksmas, nes visi kiti trys aritmetiniai veiksmai (atimtis, daugyba, dalyba) kompiuteriuose verčiami sudėtimi.
Dauginant, dauginamas skaičius sudedamas tiek kartų, iš kiek reikia dauginti. Dalijant atliekama daugkartinė atimtis.
Dauginant iš dviejų, vietoje sudėties galime atlikti skaičiaus perstūmimą per vieną skiltį į kairę, t.y. skaičiaus dešinėje prirašyti 0:
Dvejetainis
Dešimtainis
1 0 1
5
1 0 1 0
10
1 0 1 0 0
20
1 0 1 0 0 0
40
1 0 1 0 0 0 0
80

2.4.2 Skaičių papildymai

Skaičių papildymais vadinami skaičių specialūs kodai, kurie naudojami atimties operacijoms atlikti , o taip pat atlikti veiksmams su neigiamais skaičiais.
Skaičiavimo technikoje naudojami du skaičių papildymo variantai:
papildymas iki p-1 ;
papildymas iki  p     (p- skaičiavimo sistemos pagrindas).
Papildymas iki  p-1 
Papildymas randamas: pp-1 = (pn - 1) - N , kur: N – skaičius, n – skilčių skaičius.
Skaičius skliaustuose : dešimtainei sistemai -  9999999… ,
dvejetainei sistemai -   1111111… .
Dešimtainėje sistemoje: p-1 = 10 – 1 = 9. Todėl kodas vadinamas papildymu iki 9 ir užrašomas skaitmenimis papildančiais turimo skaičiaus skaitmenis iki 9.
Rasime skaičiaus 546700 papildymą iki 9:
999999
-  546700
 skaičius
453299
 papildymas iki 9
Dvejetainėje sistemoje : p-1  = 2 – 1 = 1. Todėl kodas vadinamas papildymu iki 1 ir užrašomas skaitmenimis papildančiais turimo skaičiaus skaitmenis iki1
Rasime skaičiaus 1 0 1 1 0 0 1 papildymą iki 1:
1 1 1 1 1 1 1
1 0 1 1 0 0 1
  skaičius
0 1 0 0 1 1 0
 papildymas iki 1
Matome, kad papildymas iki 1, tai invertuotas skaičius. Dvejetainių skaičių papildymas iki 1 vadinamas atvirkštiniu kodu ir randamas skaičiuje visus 1 pakeičiant 0, o 0 pakeičiant 1 (invertuojant skaičių).
Papildymas iki p. 
Papildymas randamas: pp-1 = pn - N , kur: N – skaičius, n – skilčių skaičius.
Skaičius pn dešimtainei ir  dvejetainei sistemoms -  10000000… ,
Dešimtainėje sistemoje:  = 10. Todėl ir šis kodas vadinamas  papildymu iki 10 ir užrašomas skaitmenimis papildančiais turimo skaičiaus skaitmenis iki10.
Rasime skaičiaus 546700 papildymą iki 10:
1000000
-   546700
 skaičius
453300
 papildymas iki 10
Dvejetainėje sistemoje p = 2 Todėl ir šis kodas yra vadinamas papildymu iki 2 ir užrašomas skaitmenimis papildančiais turimo skaičiaus skaitmenis iki2, tai dvejetainėje sistemoje atitinka dvejetainį skaičių 10.
Rasime skaičiaus 1 0 1 1 0 0 1 papildymą iki 2 :
1 0 0 0 0 0 0 0
-    1 0 1 1 0 0 1
 skaičius
0 1 0 0 1 1 1
 papildymas iki 2
Dvejetainių skaičių papildymas iki 2 vadinamas papildomu kodu. Randamas užrašant skaičiaus atvirkštinį kodą ir pridedant prie jo 1:
1 0 1 1 0 0 1
 skaičius
0 1 0 0 1 1 0
 atvirkštinis kodas
+                  1
0 1 0 0 1 1 1
 papildomas kodas

2.4.3 Dvejetainių skaičių atimtis atvirkštiniame Ir papildomame koduose.

Išsami aritmetinių operacijų analizė nėra šios mokymo programos tikslas. Apsiribosime keliais atimties operacijų pavyzdžiais.
Atliksime atimties operaciją su dešimtainiais skaičiais: 22 – 13 = 9, dvejetainėje sistemoje.
Skaičius užrašysime jų dvejetainiais kodais, kurių prireiks atlikti atimties operacijoms:
Dešimtainiai:
Dvejetainiai:
22
1 0 1 1 0
 tiesioginis 22 kodas
13
0 1 1 0 1
 tiesioginis 13 kodas

1 0 0 1 0
 atvirkštinis 13 kodas

1 0 0 1 1
 papildomas 13 kodas
9
0 1 0 0 1
 tiesioginis 9 kodas
Atimtis atvirkštiniame kode:
  • atimamas skaičius užrašomas atvirkštiniame kode;
  • atimtis keičiama sudėtimi;
  • papildomoje skiltyje atsiradusį 1 pridedame prie jauniausios skilties:
1 0 1 1 0
 tiesioginis 22 kodas
+    1 0 0 1 0
 atvirkštinis 13 kodas
1 0 1 0 0 0
→    →   1
 0 1 0 0 1
 rezultatas 9 dešimtainis
Atimtis papildomame kode:
  • atimamas skaičius užrašomas papildomame kode;
  • atimtis keičiama sudėtimi:
  • į papildomoje skiltyje atsiradusį 1 nekreipiame dėmesio
1 0 1 1 0
 tiesioginis 22 kodas
+    1 0 0 1 1
 papildomas 13 kodas
1 0 1 0 0 1
 0 1 0 0 1
 rezultatas 9 dešimtainis
Atimties operacijos tampa sudėtingesnėmis, kai atimamas skaičius didesnis už skaičių ,iš kurio atimama.Šiuo atveju užrašomi ir skaičių ženklai, kurie taip pat sudedami.operacija atliekama ir rezultatai gaunami atvirkštiniame ar papildomame kode.Apie tai, jei įdomu, paskaitykite specialioje literatūroje.
Skaičiaus ženklo užrašymas. Skaičiaus ženklo užrašymui skiriama vyriausia skiltis.Teigiami dvejetainiai skaičiai žymimi 0, neigiami 1. Jeigu vaizduojamas skaičiaus ženklas, apie tai būtinai informuojama.
Aritmetinės operacijos supaprastėja, kai nurodomas skaičiaus ženklas. Neigiami skaičiai šiuo atveju užrašomi atvirkštiniame arba papildomame koduose. Tai neįeina į mokymo programą ir apie tai galime sužinoti specialioje literatūroje.

 

Etiketės