Chương 2
Đại cương về MTĐT
(tiếp theo)
2.3. Cơ sở số học và logic
2.3. Cơ sở số học và logic
2.3.1. Hệ đếm trong MTĐT
Các hệ đếm thường dùng trong MTĐT
Hệ thập phân (DECimal) gồm 10 chữ số 0, 1, … và 9. Đếm bình thường.
Dạng khai triển một số tự nhiên D có n chữ số là một Đa thức Pn(10), bậc n và các hệ số lần lượt là các chữ số từ 0 đến 9.
Ví dụ: 32579 = 3*104 + 2*103 + 5*102 + 7*10 + 9.
Các phép tính số học là bình thường: 1 + 1 = 2.
Hệ nhị phân (BINary) chỉ có 2 chữ số 0 và 1.
Đếm 0, 1, 10, 11, 100, 101, 110, 111, 1000,…
Để đổi số BIN sang hệ DEC ta khai triển số đó thành D có thành
Đa thức Pn(2), bậc n với các hệ số là 0 hoặc 1.
Để ám chỉ số nhị phân ta viết thêm chỉ số 2.
Ví dụ: 11012 = 1*23 + 1*22 + 0*21 + 1*20 = 13
Phép nhân bình thường.
Phép cộng thì lại có: 12 + 12 = 102.
Hệ bát phân (OCTal) có 8 chữ số 0, 1, … và 7. Nhưng ta bỏ qua không đi sâu...
Trừ hai số nhị phân
1101011
10111
1010100

Trừ số nhỏ đi số lớn hơn phải mượn và sau đó phải trả.
Ví dụ 0 trừ 1, thì phải mượn 1 ở hàng cao hơn thành 10 trừ 1 bằng 1, sau đó phải trả....
Trừ hai số nhị phân
Hệ thập lục phân (HEXadecimal)
gồm 16 chữ số 0, 1, …, 9, A, B, C, D, E và F.
Đếm: 0, 1, …,9, A, …, F, 10, 11, ..., FF, 100, 101, …,
Để ám chỉ hệ HEX ta viết thêm chữ $ hoặc # phía trước chữ số đầu tiên hoặc chỉ số dưới 16 hay chữ h phía sau.
$1F, #1F, 1F16, 1Fh, #1f, $1f là đều như nhau.
Để đổi số HEX ra hệ DEC ta khai triển thành Đa thức Pn(16), bậc n với các hệ số 0 ... F, tức từ 0 ... 15.
Ví dụ:
$1F = $1*$101 + $F*$100 = 1.16 + 15 = 31,
$FF = $F*$101 + $F*100 = 15.16 +15 = 255.
Chú ý: $1 + $ 9 = $A, $1 + $F = $10,...



Chuyển đổi số tự nhiên từ hệ đếm khác ra hệ DEC
Phương pháp dễ nhớ để đổi một số các hệ BIN, OCT hay HEX ra DEC là dùng Lược đồ Horner để tính giá trị của đa thức P(x) theo cách triển khai của ông Horner.

P(x) = ax3 + bx2 + cx + d
= ((ax + b)x + c)x +d,

Lược đồ cũng mang tên ông ấy như sau:
Lược đồ Horner
Ví dụ: Tính P(x) = ax3+bx2+cx+d
Chuyển đổi số tự nhiên từ hệ DEC ra các hệ đếm khác

Biết số P ở hệ DEC sang hệ đếm cơ số x, chẳng hạn có dạng
ax3 + bx2 + cx + d. Hãy tính các hệ số a, b, c và d.

Theo Horner, ta có: P = ((ax + b)x + c)x + d.

P chia cho x được ((ax + b)x + c) dư d. Đặt P = (ax + b)x + c.
P chia cho x được (ax + b) dư c. Đặt P mới là ax + b.
P chia cho x được a dư b. Đặt P mới là a.
P chia cho x được 0 dư a. Hết việc!
(Chú ý: a, b, c, d đều phải bé hơn x).

Ta lần lượt thu được d, c, b và a theo trình tự thời gian.
Nhưng cần viết ngược lại để được kết quả.... OK


Đổi DEC sang BIN
13 chia cho 2 được 6 dư 1.
6 chia cho 2 được 3 dư 0.
3 chia cho 2 được 1 dư 1.
1 chia cho 2 được 0 dư 1.
Kết quả là 11012. (Viết từ dưới lên!).
Đổi DEC sang HEX
BIN sang HEX và ngược lại
Đặc biệt chuyển đổi giữa BIN và HEX còn có
thể làm như sau:
Coi mỗi chữ số của hệ HEX như dãy 4 bít, thì việc chuyển đổi này dễ dàng thực hiện được.

0000 = 0, 0001 = 1, 0010 = 2, 0011 = 3,
0100 = 4, 0101 = 5, 0110 = 6, 0111 = 7,
1000 = 8, 1001 = 9, 1010 = A, 1011 = B,
1100 = C, 1101 = D, 1110 = E, 1111 = F.
Ví dụ chuyển đổi
BIN sang HEX
1F16 = 000111112
ABC1216 = 101010111100000100102
10010010111101010112 = ?
Giải:
Dãy 10010010111101010112 được chia thành các nhóm 4 bít, từ phải sang trái và thêm số 0 bên trái cho số bít chia hết cho 4.
010010010111101010112 = 497AB16
2.3.2. Mã hóa thông tin
Số tự nhiên
Số tự nhiên nhỏ (cỡ 8 bit, kiểu unsigned char) từ 00000000 đến 11111111 tức là giá trị là 0 đến 255.

Số tự nhiên trung bình (cỡ 16 bit, unsigned int),
từ 0000000000000000 đến 1111111111111111
tức là từ 0 đến 65535.

Số tự nhiên lớn (cỡ 32 bit, kiểu unsigned long) từ 32 bít 0 đến 32 bít 1, tức là từ 0 đến 4294967295.
Số nguyên
Số nguyên ngắn (cỡ 8 bit, kiểu char), bit đầu là bít dấu (0 là +, 1 là -), 7 bít sau là số.
Giá trị từ 10000000 đến 01111111, là -128 đến 127.

Số nguyên trung bình (cỡ 16 bit, kiểu int), bit đầu là bít dấu (0 là +, 1 là -), 15 bít sau là số.
Giá trị từ 100..0 (15 bit 0) đến 011..1 (15 bit 1)
tức là từ -32768 đến 32767.

Số nguyên dài (32 bit, kiểu long int), bit đầu là bít dấu (0 là +, 1 là -), 31 bít sau là số.
Giá trị từ -2147483648 đến 2147483647
Cảnh giác
Kết quả nhận được có thể sai khi người lập trình không chú ý đến cỡ/kiểu dữ liệu.
Ví dụ: Làm phép cộng a + b = c.
Bước 1. Xin cấp phát 3 ô nhớ a, b, c kiểu số tự nhiên cỡ 1 Byte.
Bước 2. Nhập a, b vào các ô nhớ đã có.
Bước 3. Lấy các ô nhớ a + b được kết quả
đưa vào ô nhớ c.
Bước 4. In kết quả ra màn hình.
Kết quả sai ở đâu?
Phân tích lỗi, qua ví dụ sau
Nhập a = 255 và b = 1.
Vào ô nhớ a = 11111111, b = 00000001.
Máy cộng 11111111
00000001
thành 100000000, thừa bit 1.
Đưa vào ô nhớ c chỉ có 8 bít 0 thôi
Xuất ra màn hình 255 + 1 = 0.
Vậy, muốn kết quả đúng phải xin cấp
phát cho c kiểu dữ liệu 16 bit.
Mã hóa số âm như thế nào?
Có người tưởng muốn mã hóa số nguyên âm thì chỉ cần đảo bít (0 thành 1 và 1 thành 0) hay còn gọi là bù 1. Kết quả sai.
Ví dụ: Có người đổi như sau: -13 = 11110010.
Khi đó 00001101+11110010=11111111.
Sai!
Có người khác đổi -13 thành 10001101.
Cũng sai!
Ngoài đời = 0, trong máy bằng 255 khác 0.
Công thức mã hóa số âm
-Z = not(Z) + 1
Bước 1. Đảo bit, tức là not(z).
Bước 2. Thêm 1, tức not(z) + 1.
Ví dụ: Mã hóa -13 thành dạng cỡ 8 bit.
Bước 1. 13 = 00001101  11110010
Bước 2. -13 = 11110010 + 1 = 11110011.
Máy tính làm: 00001101 + 11110011 = 100000000 = 0. (1 bị tràn)
Chú ý: Các cỡ khác cũng làm tương tự
Ví dụ mã hóa số âm cỡ 16 bit
Mã hóa -65 thành dạng 16 bít.
Bước 1. 65 = 0000 0000 0100 0001,
bù 1 thành 1111 1111 1011 1110.
Bước 2. Bù 2, tức cộng thêm 1
thành 1111 1111 1011 1111.
Vậy kết quả mã hóa là:
- 65 = 1111 1111 1011 1111
Giải mã dữ liệu
Có mã nhị phân máy giải mã ra thông tin theo yêu cầu của phần mềm!
Ví dụ. Trong C++ có đoạn mã nguồn:
printf(“Nhap so tu nhiên d = “); //viết dòng chữ
scanf(“%d”,&n); //nhập số vào địa chỉ ô nhớ n
printf(“Xuat ket qua ra:\n”); //Viet dòng chữ
printf(“So tu nhien = %d”,n); //Xuất ra số
printf(“Kí tu = %c”,n); //Xuất ra kí tự
getch(); //Chờ gõ một phím
Khi chạy chương trình
Nhap so tu nhiên d = 65 (User gõ)
Xuat ket qua ra:
So tu nhien n = 65 (Máy xuất ra)
Kí tu = A (Máy xuất ra)
(Máy chờ User gõ một phím rồi kết thúc)

Ví dụ giải mã cụ thể
Ví dụ 1.
Dữ liệu = 0100 0001
Ra số = 65. Phải là số tự nhiên!
Ra chữ = A
Ví dụ 2.
Dữ liệu = 1100 0001
Ra số tự nhiên = 193.
Ra số nguyên = - 63. Ra được số âm!
Ra chữ =  . Hãy xem Bảng kí tự.
Bí quyết giải mã ra số âm
Ví dụ cần giải mã 1000 1111 ra số âm. Ra số âm được vì bít bên trái nhất là 1, tức số âm.
Cách 1. Giả sử 10001111 = z = -n, n > 0.
Suy ra n = -z = not(10001111) + 1 = 01110000 + 1 = 01110001 = 113.
Vậy z = -n = -113.
Cách 2. Đổi 10001111 ra DEC được = 143.
Rồi lấy 256 – 143 = 113.
Từ đây => Đáp án z = -113
Số thực

Số thực (gọi là kiểu Real hay float) viết thành:
1/- Dạng dấu phẩy tĩnh (dạng thông thường),
ví dụ: 345.7645. Trước/Sau dấu chấm là số nguyên.
2/- Dạng dấu phẩy động (dạng khoa học),
ví dụ: 345.7645 = 0. 3457645 *103 .
Cách viết dưới dạng khoa học chuẩn là gồm:
 0. *10.
Gọi là động vì có thể dịch dấu phẩy sang trái hoặc sang phải và thay đổi số mũ của 10
Do vậy muốn mã hóa chỉ cần mã hõa các số tự nhiên và số nguyên đó.
Ví dụ đổi số lẻ DEC -> BIN
Ví dụ: Đổi 12.34 -> BIN lấy 5 bit sau dấu phẩy.
12.34 = 11002 + 0.34, vì 12 -> 1100.
Còn 0.34 = b1*2-1 + b2*2-2 + b3*2-3 + .....
0.34 * 2 = 0.68 = b1 + b2*2-1 + b3*2-2 , b1 = 0.
0.68 * 2 = 1.36 = b2 + b3*2-1 + b4*2-2 , b2 = 1.
0.36 * 2 = 0.72 = b3 + b4*2-1 + b5*2-2 , b3= 0.
0.72 * 2 = 1.44 = b4 + b5*2-1 + b5*2-2 , b4= 0.
0.44 * 2 = 0.88 = b4 + b5*2-1 + b6*2-2 , b5= 0.
Đáp án = 1100.01000
Ví dụ đổi số lẻ BIN -> DEC
Ví dụ. Đổi 11.10112 -> ? Ở DEC.
Giải:
Ở BIN, đem 11.1011 nhân với 104, tương đương với ở DEC nhân 16.
Ta được 111011 -> 59. Bây giờ phải trả lại giá trị đúng bằng cách chia cho 16, được:
59/16 = 3.6875. Vậy
Đáp án = 3.8675
Nhận xét
Cứ thông tin nào biểu diễn được qua các số thì dễ dàng mã hóa và sau lại giải mã được.
Ví dụ:
Số phức z = a + bi, a và b là số thực, vậy cũng sẽ mã hóa được.
Nốt nhạc biểu diễn được qua Tần số (số tự nhiên) và Thời gian (đo bằng mili giây, cũng là số tự nhiên), nên không khó khăn gì để mã hóa chúng!
Các dạng bài tập tự luyện
Dạng 1. Đổi một số tự nhiên từ hệ đếm này sang hệ đếm khác trong ba hệ sau:
DEC – BIN – HEX.
Dạng 2. Thực hiện các phép tính cộng, trừ, nhân ở hệ BIN.
Dạng 3. Mã hóa một số tự nhiên, số nguyên tang dạng dữ liệu cỡ 8 bít, 16 bít.
Dạng 4. Giải mã một dữ liệu bít ra thông tin!

Kí tự

Quy tắc mã hóa nhị phân của các kí tự là:

Mã hóa thập phân (DEC) rổi chuyển sang nhị phân, bổ sung cho đủ 8 bít.

Ví dụ:
Kí tự ‘A’ = kí tụ số 65 -> 01000001.
Kí tự ‘a’ = kí tụ số 97 -> 01100001.
Kí tự ‘0’ = kí tụ số 48 -> 00110000.
Kí tự Esc = kí tụ số 27 -> 00011011.
Xâu kí tự
Xâu kí tự là dãy các kí tự nên cũng mã hóa được thành dãy các số tự nhiên, rồi thành dãy các bit.
Và khi giải mã thì theo chiều ngược lại.
Ví dụ:
‘TIN’  84-73-78  01010100-01001001-01001110
‘2010’  50-48-49-48  00110010-00110000-00110001-00110000.
Viết dấu trừ cho dễ nhìn thôi nhé!
Unicode
Bảng mã Unicode gồm 65536 kí tự.

Mỗi kí tự có số thứ tự từ 0 đến 65535 (gọi là mã thập phân). Ta dùng 16 bit (2B) để mã hóa kí tự (gọi là mã nhị phân) của nó.

Bảng mã này đáp ứng được mọi nhu cầu về font chữ các nước trên toàn thế giới.
Mầu sắc
Có 16 mầu cơ bản, nên dùng hệ đếm HEX để mã hóa ($H) hay DEC tương ứng.



= 15 trắng white
Mầu trong DOS
Trong hệ điều hành phiên bản thấp: Màn hình là màn hình văn bản, thường là 80 cột x 25 dòng,

Giao của mỗi cột và mỗi hàng là một kí tự.

Mầu nền và mầu chữ của kí tự ghép lại với nhau để mô tả thuộc tính (attribut) của kí tự, theo quy định sau:

Thuộc tính = $XY, ($X = mầu nền, $Y = mầu chữ). ở đây X, Y là các chữ số của hệ HEX.

Số $XY chạy từ $00 đến $FF, chiếm 1 Byte.
Thực hành Mầu trong DOS
Nhấp vào nút Start > Gõ cmd . Cửa sổ màn hình DOS hiện ra:



Ta thấy dấu nhắc hệ thống mời chờ lệnh.
Ta gõ lệnh color 1F. Màn hình DOS chuyển mầu xanh, chữ trắng. Ở đây, ta không cần gõ $ hay #, máy vẫn hiểu.
Câu lệnh tổng quát = color XY 

Chữ ‘A’ nền xanh chữ trắng có
mã = 65, thuộc tính = $1F,
Mã nhị phân = 0100000100011111
Chữ ‘b’ với thuộc tính $4E có mã = 98, mầu nền đỏ, chữ vàng,
mã nhị phân = 0110001001001110
Kí tự có mã 49, thuộc tính $CF là chữ số ‘1’ mầu nền là đỏ, mầu chữ trắng.
Ví dụ kí tự và mầu trong DOS
Tính toán mầu trong DOS
Ví dụ. Cho mã kí tự và thuộc tính là
0100000101111100
Hỏi đây là kí tự gì mầu nền, mầu chữ là gì?
Giải:
01000001 là mã của kí tự ‘A’.
0111 = #7 là mầu nền, ghi.
1100 = 12 = #C, mầu chữ là đỏ.
ĐA = A, #7, #C
Mầu trong Windows
Sau này ở hệ điều hành Windows, giao của cột và hàng là một điểm ảnh (pixel), mỗi điểm ảnh mang thông tin về mầu

Hiện nay ít nhất cũng phải là 65536 mầu. Mầu có mã thập phân từ 0 đến 65535, tức là mã nhị phân

Chất lượng mầu (Color Quality) thể hiện bằng số bít 16 bit, 24b và 32b.
Cùng với mầu còn có Độ phân giải (Resolution),
ví dụ 1024 x 768 là màn hình có 1024 cột và 768 hàng.

Bài tập liên quan: Cho một bức ảnh có kích thước Width x Height thì tính được số lượng pixels, cỡ (size) của file ảnh
và thời gian (time) tải khi biết tốc độ của modem…
Ví dụ: Mầu trong WIN
Một bức ảnh kích thước 200 x 300, với chất lượng mầu 16b và Modem tốc độ 56kbps.
a/- Hỏi cỡ bức ảnh bằng bao nhieu KB?
b/- Thời gian tải bằng bao nhiêu giây?
Giải: a/- 200*300 = 60000pxl, chất lượng mầu = 2B, nên Size = 120000B/1024B  117.1875 KB.
b/- Số bít = 60000*16 = 960000/56000  0.171s
Mầu trong Internet
Trong Internet, người ta dùng thống nhất là 24 bít.
Quy định mã hóa mầu là #RRGGBB, ở đây R, G, B là các chữ số HEX, trong đó:
#RR là độ đậm của mầu đỏ (Red),
#GG của mầu lá (Green),
#BB của mầu xanh (Blue).
Ví dụ 1. #102A1F là mã hóa của mầu hòa trộn Đỏ, Lá và Xanh
- Mầu đỏ với độ đâm = #10/#FF = 16/255 = 6.27%.
- Mầu lá với độ đâm = #2A/#FF = 16/255 = 16.47%.
- Mầu xanh với độ đâm = #1F/#FF = 16/255 = 12.16%.
Ví du 2. #FF0000 là mầu đỏ 100%, #0000FF là blue 100%,
#FF00FF là trộn của đỏ và xanh cho mầu tím 100%, #000000 là mầu đen, #FFFFFF là mầu trắng,…
Mã nguồn của một web đơn giản



Chao cac ban!




Viết ra màn hình dòng chữ “Chao cac ban” có cỡ là 7, font kiểu Arial và mầu là tím.

Hãy thử mã mầu khác, lưu mã nguồn dưới tên có đuôi là .htm, và Open bằng một trình duyệt quen biết xem như thế nào!
Ví dụ mầu trong Internet
1/- Tính số phần trăm của các mầu Đỏ, Lá và Xanh trong mầu #A89A64, lấy tròn 2 chữ số thập phân.
Giải:
Red = #A8/#FF = 168/255  65,88%
Green = #9A/#FF = 154/255  60,39%
Blue = #64/#FF = 100/255  39,22%
2/- Để có mã mầu của mầu trên ảnh ta làm gì?
https://photoshopmienphi.com/laymamau/
2.3.3. Các phép toán logic và mạch điện tử
Mệnh đề toán học là mệnh đề chí có thể nói là đúng (1) hoặc sai (0).

Ví dụ:
Mệnh đề “Ai đi đâu đấy, hới ai?’, “Ôi, Hà Nội!’, “anh Minh ơi” chỉ là những mệnh đề văn học.
Các mệnh đề như Mặt trăng sáng hơn mặt trời, 3 > 2,… là nhưng mệnh đề toán học.
Mệnh đề x > 3 tuy chưa biết đúng sai nhưng khi thay x cụ thể vào sẽ biết được kết quả.

Cũng như trong đại số, mệnh đề phụ thuộc vào một biến số gọi là một hàm mệnh đề f(x).
Các phép toán mệnh đề
Cho 2 mệnh đề a và b ta có:
a AND b chỉ đúng khi a và b đều đúng.
Kí hiệu a  b.
a OR b chỉ sai khi a và b đều sai.
Kí hiệu a  b.
a XOR b (hoặc loại trừ) chỉ đúng khi a và b không cùng giá trị.
Kí hiệu a V b.
IF a THEN b chỉ sai khi a đúng và b sai.
Kí hiệu a  b.
Not(a) lấy giá trị ngược. kí hiệu a.