TRƯỜNG CAO ĐẲNG SƯ PHẠM BẾN TRE.
TỔ TIN HỌC

GIÁO TRÌNH TOÁN RỜI RẠC
VÀ ỨNG DỤNG.
Vương Đức Bình.
Tài liệu lưu hành nội bộ.
2003-2004
1
LỜI MỞ
ối với người làm công nghệ thông tin thì ngoại trừ những kỹ năng cần thiết về sử
dụng máy tính như sử dụng những phần mềm, những dòch vụ phổ biến trên Internet
cho công việc thường ngày, còn phải có một hiểu biết khá đầy đủ về những lónh
vực toán học có liên quan nhằm có thể tiếp cận sâu sắc hơn các quá trình xử lí thông tin. Nếu
người sử dụng máy tính thông thường trong các văn phòng, chỉ cần một khoá học “mì ăn
liền” nhằm hoàn thiện kỹ năng sử dụng một số ứng dụng nào đó là tạm đủ cho công việc,
người làm công nghệ thông tin cần có một nền tảng lí luận về thông tin và xử lí thông tin đầy
đủ để có thể chủ động tự đồng bộ được, đối phó được (và góp phần!) với những thay đổi
chóng mặt về phần cứng lẫn phần mềm của ngành công nghệ thông tin. Do đó một hiểu biết
tương đối về những ngành toán học có liên quan đến công nghệ thông tin là không thể thiếu
được.
Đ
Có khá nhiều tài liệu về đề tài này
1
để sinh viên có thể tham khảo nhưng các tài liệu đó hoặc
khó kiếm hoặc nhanh chóng dẫn người mới tìm hiểu vào quá sâu của vấn đề khiến việc tiếp
cận môn học gặp khó khăn. Vì vậy giáo trình này được soạn ra nhằm giúp sinh viên mới tìm
hiểu khoa học này tiếp cận vấn đề dễ dàng và có hệ thống hơn. Mặt khác đây là một tài liệu
dạng hỗ trợ học tập (nên cần phải) hết sức cô đặc vì vậy sinh viên cũng cần phải đọc thêm
các tài liệu khác của thư viện.
Tài liệu này tốt hơn hết là được giảng song song với việc học một ngôn ngữ lập trình để các

phát biểu có thể chứa trong nó đến ba chức ngôn ngữ:
Chức mệnh lệnh
Chức cảm xúc
Chức miêu tả.
Vì vậy phát biểu: “Anh phải đến đó trước 6 giờ!” nếu xét về chức mệnh
lệnh không thể cho phép ta xác đònh tính đúng sai mà đơn thuần chỉ là một
câu ra lệnh, buộc phải thực hiện một yêu cầu! Tương tự, phát biểu “Tình
yêu đẹp như hoa hồng buổi sớm” thuần tuý chỉ mang tính cảm xúc - nó chỉ
đem lại một cảm xúc mơ hồ êm dòu nào đó - không đem lại một giá trò chân
lí đúng hay sai; nhưng phát biểu “5 < 7” hoàn toàn là một miêu tả về quan
hệ giữa hai số, tính đúng sai của nó do lòch sử hoạt động thực tiển của con
người xác nhận
2
. Tính chân lí - do đó - không phụ thuộc vào ngôn ngữ mang
phát biểu. Ví dụ các phát biểu sau:
I am studying logic.
J’ étudie la logique.
Ich studiere Logik.
Tôi học môn lô gích.
Hoc(Tôi, Lôgich)
Là năm phát biểu khác nhau, nhưng chỉ là cùng một mệnh đề.
Môn học nghiên cứu về các quan hệ giữa các mệnh đề gọi là môn logic
mệnh đề (propositional logic).
2
“Hoạt động thực tiển của con người đã làm cho ý thức của con người lập di lập lại hàng
nghìn lần những cách thức lôgích khác nhau đặng làm cho những cách thức này có thể có
những ý nghóa của công lí” – (Lênin).
4
o Các phép toán lô gích và phép toán bit.
Để dễ dàng trong các suy luận chúng ta sẽ kí hiệu các mệnh đề bằng các

1 0
Lưu ý rằng hai mệnh đề P và Q là phủ đònh lẫn nhau nếu P đúng thì Q phải
sai (và ngược lại). Ví dụ : Hai mệnh đề sau đây là phủ đònh lẫn nhau:
P: Năm 2002 là năm nhuận.
Q: Năm 2002 không phải năm nhuận.
Nhưng hai mệnh đề sau đây không phải là hai mệnh đề phủ đònh lẫn nhau:
R: Số hàng tồn kho lớn hơn 300 đơn vò.
S: Số hàng tồn kho bằng đúng 300 đơn vò.
Mà chỉ là hai mệnh đề tương phản (Vì sao? Hãy tự nghó ra thêm một ví dụ
khác!).
5
Trong kỹ thuật các phép toán trên có thể dùng để biểu diễn sơ đồ các mạch
điện:
Hình 1: Mạch điện
hiện thực cho phép
toán logich L = A
AND B với mỗi công
tắc lấy giá trò 1 nếu
công tắc đó đóng và
lấy giá trò 0 nếu công tắc đó mở. Ta thấy đèn L chỉ sáng lên khi cả hai công
tắc A và B đều đóng.
Hình 2: Mạch điện
hiện thực cho phép
toán logich L = A OR
B . Ta thấy đèn L
sáng lên khi một
trong hai công tắc
trong trạng thái đóng.
Có thể thấy rằng các phép toán lôgich AND, OR, XOR, NOT nói trên tác động lên
các mệnh đề để cho kết quả cũng là một mệnh đề. Nói cách khác các phép toán đó

PASCAL - việc bỏ bớt các toán tử () như trong biểu thức (**) là không được
phép mà phải viết tường minh như biểu thức (*)
Trong trình bày trên, thay vì ghi các giá trò TRUE hoặc FALSE trong bảng chân trò
chúng ta đã dùng các kí hiêu 1 hoặc 0 để thay thế, điều này cho phép nghó đến các
phép toán logich NOT, AND,OR, XOR có thể được mở rộng trên tập hợp các số
được biểu diễn trong hệ nhò phân (các phép toán bit). Để đảm bảo tính hệ thống của
giáo trình, đề nghò sinh viên tham khảo về vấn đề này trong chương II (phần số
nguyên)
o Tương đương lô gích.
Hai biểu thức logich f(X,Y,Z,...) và g(X,Y,Z,...) gọi là tương đương lôgich nếu chúng
nhận được cùng một giá trò ứng với mỗi bộ giá trò có thể có của (X,Y,Z,...).
Ví dụ 1: Xét hai biểu thức lôgich:
f(A,B,C)=A AND (B OR C) (1)
g(A,B,C)=(A AND B) OR (A AND C). (2)
Việc chứng minh f và g là tương đương lôgich có thể được thực hiện “thô”
nhờ vào việc thiết lập bảng chân trò như sau:
A B C B OR C
A AND (B OR C)
A AND B A AND C
(A AND B) OR (A AND C)
0 0 0 0
0
0 0
0
0 0 1 1
0
0 0
0
0 1 0 1
0

g(X,Y): Y OR (NOT X)
Cùng với cách làm như trên ta có thể kiểm chứng f(X,Y) và g(X,Y) là tương
đương lôgich.
Kí hiệu:
Khi hai biểu thức lôgich f và g là tương đương ta ghi: f
≈
g
Khái niệm tương đương lôgich là rất quan trọng trong kỹ thuật máy tính vì nó liên
quan đến việc tối ưu hoá chương trình máy tính (phần mềm) cũng như đơn giản hoá
các mạch điện tử (phần cứng). Trong ví dụ 1 biểu thức (1) rõ ràng là đơn giản hơn
biểu thức (2) còn trong ví dụ 2 sự tương đương lôgích cho phép chúng ta thay mọi
biểu thức chứa toán tử
⇒
thành biểu thức chỉ chứa hai toán tử OR và NOT, nghóa
là giảm bớt được một dạng toán tử. Chúng ta còn cần xây dựng những công cụ
mạnh hơn để thực hiện các quá trình đơn giản các biểu thức lôgich này và sẽ được
trình bày trong các chương sau.
o Vò ngữ và lượng từ.
Trong lôgich mệnh đề chúng ta xây dựng nên các biểu thức lôgich bằng những
mệnh đề. Các phép toán mệnh đề xử lí các mệnh đề như những “nguyên tử” và bỏ
qua cấu trúc toàn thể của quá trình suy luận. Tuy nhiên, có nhiều trường hợp việc
diễn đạt các ý tưởng không thể thực hiện một cách đơn giản như vậy. Ví dụ diễn đạt
sau đây:
P: Mọi người đều chết.
Q: Socrate là người.
R: Socrate phải chết.
Tính đúng sai của mệnh đề R chỉ có thể được xác lập trong khung quan hệ cấu trúc
với hai mệnh đề được phát biểu trước đó. Trong ví dụ này tính đúng đắn của R được
dẫn xuất từ tính đúng đắn của P và Q và bản thân cấu trúc của suy luận.
Xét ví dụ vui trong chuyện dân gian:

Vậy:
Phát biểu: “Ai cũng chết” có thể được viết lại:
∀
x, P(x) trong đó P(x) là “x phải chết”
Phát biểu: “Có ít nhất một trường hợp a bằng 7” có thể được viết lại:
∃
a, Q(a) trong đó Q(a) là “a=7”.
Một khi vò từ đi kèm theo lượng tử nó trở thành một mệnh đề nên có thể áp
dụng các phép toán mệnh đề như vừa nghiên cứu trên. Tuy nhiên phủ đònh
của sự phổ biến một tính chất nào đó chính là sự tồn tại ít nhất một trường
hợp ngược lại. Và phủ đònh của sự tồn tại ít nhất một trường hợp có tính
chất nào đó chính là sự phổ biến của trường hợp ngược lại.
Từ đó ta có hai tương đương logic sau:
NOT (
∀
x, P(x)) tương đương với (
∃
x,NOT P(x))
NOT (
∃
x,P(x)) tương đương với (
∀
x, NOT P(x))
3
Về khái niệm hàm xin xem tiếp trong phần II của chương này.
9