  !"
1
#$%&'()*+,*,*-
TÊN ĐỀ TÀI:
MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ LOGIC MỆNH ĐỀ,
LOGIC VỊ TỪ VÀ LOGIC MỜ.
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

BÀI TIỂU LUẬN MÔN
TOÁN HỌC CHO KHOA HỌC MÁY TÍNH
Giảng viên hướng dẫn: PGS. TS. Nguyễn Phi Khứ
Họ tên học viên: Đặng Thị Mỹ Hạnh
Mã số học viên: CH1301012
  !"
CHƯƠNG I
MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ LOGIC MỆNH ĐỀ, LOGIC VỊ TỪ VÀ
LOGIC MỜ
I. LOGIC MỆNH ĐỀ
1. Khái niệm mệnh đề
Mệnh đề là một phát biểu có thể khẳng định tính ./ hoặc 0.
Mệnh đề sơ cấp là mệnh đề không thể tách nhỏ hơn, nói cách khác nếu ta bỏ đi một
phần của nó thì không còn là mệnh đề nữa.
Ví dụ: "123045" là một mệnh đề sơ cấp nhận giá trị "./" hay nói mệnh
đề sơ cấp này có giá trị chân lý là *.
"604789:;.<=0476:=" là một mệnh đề sơ cấp
nhận giá trị "./" hay giá trị *.
">?@A'>24 " không phải là một mệnh đề.
"-,,,23045>2B*, " không phải là một mệnh đề sơ cấp, vì nó
có thể tách thành hai mệnh đề đơn giản hơn.
2. Các kí hiệu

định của nó.
L
A
, *
* ,
Ví dụ:
A = “M=<” khi đó
A
sẽ là “M=<”
N= “>7O9P#')Q0C8CJ>R”,
B
= “>7O9P#')Q0C8CJ>R”
3.2. Phép “hoặc” hay còn gọi là phép cộng logic
Cho L và N là hai mệnh đề, liên kết L $ B là một mệnh đề S nhận giá trị 0
nếu cả hai mệnh đề đã cho cùng 0, kí hiệu L
∨
N.
LN
L
∨
N
,, ,
*, *
,* *
** *
Ví dụ:
A= “23045”, B= “2304B+”
A∨B = “23045hoặcB+”
Khi đó với TU mệnh đề trên đúng, TV mệnh đề trên đúng, T1 mệnh đề trên
đúng, TW mệnh đề trên sai.

,, ,
*, *
,* *
** ,
Ví dụ:
L= “23045”, N= “2304[”, trong trường hợp này ta có thể định
nghĩa L
⊕
N = “\23045”
Khi đó với T+ , TU mệnh đề trên sai; TU;T1 mệnh đề trên đúng, TW;T+
mệnh đề trên đúng, TU;T+ mệnh đề trên sai.
Phép toán ⊕ thường được sử dụng để kiểm tra tính chẵn lẻ.
3.5. Phép kéo theo
Cho L và N là hai mệnh đề, liên kết L ?A N (còn được phát biểu dạng BL
] N) là một mệnh đề S nhận giá trị 0 nếu L ./, N 0, kí hiệu L
→
N.
4
#$%&'()*+,*,*-
  !"
LN
L
→
N
,, *
*, ,
,* *
** *
Ví dụ:
1. L= “23045”, N= “2304B-”,

LN
BA BA ∧∨
LN
BA BA ∨∧
** ,, ** ,,
*, ,, *, **
,* ,, ,* **
,, ** ,, **
5
#$%&'()*+,*,*-
  !"
- Một số công thức biến đổi tương đương của các mệnh đề được cho dưới đây:
¬(¬P) P
(P∨Q) (¬P ⇒Q)
Luật tương phản: (P ⇒Q) (¬Q ⇒ ¬P)
Luật De Morgan: ¬(P ∨Q) (¬P ∧ ¬Q), và
¬(P ∧Q) (¬P ∨ ¬Q)
Luật giao hoán: (P ∧Q) (Q ∧P), và (P∨Q) (Q∨P)
Luật kết hợp: ((P ∧Q) ∧R) (P ∧(Q ∧R)),
((P ∨Q) ∨R) (P ∨(Q ∨R))
Luật phân phối: P ∨(Q ∧R) (P ∨Q) ∧(P ∨R),
P ∧(Q ∨R) (P ∧Q) ∨(P ∧R)
N∧⇔→ A BA
L
↔
N_L
→
N`
∧
_N

- Ký hiệu chân lý: true, false
- Hằng: dùng để chỉ một đối tượng/thuộc tính trong thế giới. Hằng được ký hiệu bắt
đầu bằng chữ thường: helen, yellow, rain, …
- Biến: dùng để chỉ một lớp tổng quát các đối tượng/thuộc tính. Biến được ký hiệu
bắt đầu bằng chữ hoa: X, People, Students, …
- Hàm: dùng để chỉ một hàm trên các đối tượng. Hàm được ký hiệu bắt đầu bằng
chữ thường: father, plus, …
Mỗi ký hiệu hàm có một ngôi n, chỉ số lượng các đối số của hàm.
- Vị từ: dùng để định nghĩa một mối quan hệ giữa không hoặc nhiều đối tượng. Vị
từ được ký hiệu bắt đầu bằng chữ thường: likes, equals, part_of, …
3.1. Biểu thức hàm: là một ký hiệu hàm theo sau bởi n đối số.
Ví dụ: father(david) price(bananas) like(tom, football)
3.2. Mục (term) là một hằng, một biến hay một biểu thức hàm
3.3. Câu sơ cấp: là một hằng vị từ với n ngôi theo sau bởi n thành phần nằm trong
cặp dấu ( ), cách nhau bởi dấu ‘,’, và kết thúc với dấu ‘.’
- Trị chân lý true, false là các câu sơ cấp.
- Câu sơ cấp còn được gọi là: biểu thức nguyên tử, nguyên tử hay mệnh đề
Ví dụ: friends(helen, marry), Likes (hellen, mary), likes (helen, sister(mary)), likes
(X, ice-cream).
Ký hiệu vị từ trong các câu này là friends, likes.
Câu: được tạo ra bằng cách kết hợp các câu sơ cấp sử dụng:
- Các phép kết nối logic: ¬, ∧, ∨, ⇒, =
7
#$%&'()*+,*,*-
  !"
- Các lượng tử biến:
+ Lượng tử phổ biến ∀: dùng để chỉ một câu là đúng với mọi giá trị của biến lượng
giá. Ví dụ: ∀X likes(X, ice-cream).
+ Lượng tử tồn tại ∃: dùng để chỉ một câu là đúng với một số giá trị nào đó của biến
lượng giá. Ví dụ: ∃Y friends(Y,tom).

5. Phép tính vị từ bậc nhất (First – order predicate calculus)
Phép tính vị từ bậc nhất cho phép các biến lượng giá tham chiếu đến các đối tượng
trong miền của vấn đề đang đề cập nhưng không được tham chiếu đến các vị từ và hàm.
Thí dụ 1: Ví dụ không hợp lệ: ∀(Likes) Likes(helen, ice-cream)
Ví dụ hợp lệ:
Nếu ngày mai trời không mưa, Tom sẽ đi biển.
¬weather(rain, tomorrow) ⇒go(tom, sea)
Tất cả các cầu thủ bóng rổ đều cao.
∀X (basketball_player(X) ⇒tall(X) )
Có người thích coca-cola.
∃X person(X) ∧likes(X, coca-cola)
Không ai thích thuế.
¬ ∃X likes(X, taxes)
Hầu hết bất kỳ câu đúng ngữ pháp nào cũng có thể biểu diễn trong phép tính vị từ
bậc nhất bằng cách sử dụng các ký hiệu, các phép kết nối và ký hiệu biến.
6. Các luật suy diễn
Ngữ nghĩa của phép tính vị từ cung cấp một cơ sở cho lý thuyết hình thức về suy
diễn logic. Khả năng suy ra những biểu thức đúng mới từ một tập hợp các khẳng định
đúng là một đặc trưng quan trọng của phép tính vị từ. Logic vị từ dùng các luật suy diễn
sau :
6.1. Luật Modus Ponens (MP):
P
P ⇒Q
Q
Ví dụ: Nếu ta có quan sát sau đây “nếu trời mưa thì sân ướt” (P ⇒Q) và “trời đang
mưa” (P) thì ta dễ dàng suy ra được “sân ướt” (Q).
6.2. Luật Modus Tollens (MT):
P ⇒Q
¬Q
¬P

Hoặc: Nữ an ninh thì rất cao => như thế nào là rất cao?
10
#$%&'()*+,*,*-
  !"
- Vì vậy, logic truyền thống không thể hỗ trợ cho những suy luận trên những thông
tin mang tính mơ hồ, thiếu chính xác như vậy.
1. Khái niệm logic mờ
Để khắc phục khuyết điểm của logic truyền thống, Lotfi Zadeh đã đưa ra lý thuyết
mới về logic gọi là logic mờ (fuzzy logic).
Lý thuyết của Zadeh biểu diễn tính mờ hay tính thiếu chính xác trong các phát biểu
(như đã đề cập ở trên) theo cách định lượng bằng cách đưa ra một hàm tư cách thành viên
tập hợp (set membership function) nhận giá trị thực giữa 0 và 1.
1.1. Định nghĩa tập mờ
Tập mờ L được xác định trên không gian nền kinh điển X là một tập mà mỗi phần tử
của nó là một cặp
))x(,x(
A
µ
trong đó @
∈
X và
)x(
A
µ
là ánh xạ
[ ]
1,0X:
A
→
µ

phần tử @nào đó có ba cách: Tính trực tiếp (nếu
)x(
A
µ
cho trước dưới dạng công thức
tường minh) hoặc:
11
#$%&'()*+,*,*-
  !"
- Tra bảng (nếu
)x(
A
µ
dưới dạng bảng)
- Tìm các giá trị tương ứng trên đồ thị (nếu
)x(
A
µ
được biểu diễn dạng đồ thị )
Trong nhiều tài liệu để biểu diễn tập mờ người ta cũng thường dùng ký hiệu sau:
∑
=
=






++++=

µµ

Cho các tập hữu hạn và
∫
=
@
@
L
L
)(
µ
cho tập vô hạn.
Phép cộng (+) được hiểu là phép hợp.
Ví dụ: Đồ thị hàm liên thuộc của tập mờ
1
m1 m2 m3 m4
)x(
A
µ
]#E%273eaP
Các hàm liên thuộc
)x(
A
µ
có dạng “trơn” như ở hình vẽ được gọi là hàm liên
thuộc kiểu S. Đối với hàm liên thuộc kiểu S do các công thức biểu diễn có độ phức tạp
lớn nên thời gian tính độ phụ thuộc cho một phần tử lâu. Bởi vậy trong kỹ thuật điều
khiển mờ thông thường các hàm liên thuộc kiển S hay được thay gần đúng bằng một hàm
tuyến tính từng đoạn.
Một hàm liên thuộc có dạng tuyến tính từng đoạn được gọi là hàm liên thuộc có

A
µ
=



∉
∈
A x nÕu 0
A x nÕu 1
Ví dụ . LTg@
∈
Zh-i@i1j
Hình sau mô tả hàm thuộc của tập L :
-1
1.3. Một số khái niệm liên quan của tập mờ
Trong những ví dụ trên các hàm liên thuộc đều có độ cao bằng *. Điều đó nói rằng
các tập mờ đó đều có ít nhất một phần tử với độ phụ thuộc bằng *.
Trong thực tế không phải tập mờ nào cũng có phần tử có độ phụ thuộc bằng *.
Tương ứng với điều đó thì không phải mọi hàm liên thuộc đều có độ cao là *.
Định nghĩa 1: Độ cao của một tập mờ L trên không gian nền X là giá trị
)x(h
sup
Xx
µ
∈
=
.
Ký hiệu:
)x(

Định nghĩa 3: Miền tin cậy của tập mờ tập mờ L trên không gian nền Xđược ký
hiệu bởi  là tập con của X thoả mãn
}1)x(/Xx{T
A
=∈=
µ
Định nghĩa 4
: Miền biên của tập mờ tập mờ L trên không gian nền Xđược ký hiệu
bởi k là tập con của X thoả mãn
}1)x(0/Xx{U
A
<<∈=
µ

]<eaP
Định nghĩa 5: Tập cắt α (α∈ [0,1]) của tập mờ tập mờ L trên không gian nền X
được ký hiệu bởi L
α
là tập con của X thoả mãn
L
α

=g@h
µ
L
_@`
≤

α
j

_
λ
@
*
\_*l
λ
`@
-
`
≥
g
µ
L
_@
*
`;
µ
L
_@
-
`jmvới
∀
@
*
;@
-
∈
X;
∀


+ Bảo 35 tuổi => μTre(Bảo) = 0.3 và μTrung niên(Bảo) = 0.8
15
#$%&'()*+,*,*-
1
10 15 17 20
0.5
0.3
  !"
+ Châu 23 tuổi => μTre(Châu) = 1.0
- Ta gọi các con số 0.8, 0.2, 1.0 là các giá trị mờ (fuzzy values). Vậy từ các giá trị
chính xác hay giá trị‘giòn’ (sốtuổi: 28, 35, 23…), ta đã suy ra các giá trị mờ tương ứng.
Thao tác này gọi là mờ hóa (fuzzification) các giá trị giòn.
1.5. Các ví dụ về tập mờ
Ví dụ: Tập đánh giá nhiệt độ của thời tiết
Lạnh =





>
≤≤+−
<<
20x nÕu 0
20x10 nÕu 210/x
10x45- nÕu 1
Ví dụ trên có thể được hiểu như sau:
- Nếu nhiệt độ thấp hơn *,

) ( lUpi@i*, ) tất cả mọi người đều đánh giá mức độ





≤≤+
≤≤−
≥≤
30x20 nÕu 3x/10-
20x10 nÕu 110/x
30x hoÆc 10x nÕu 0
16
#$%&'()*+,*,*-
1
10 20 30 40
lạnh
mát
ấm
nóng
  !"
Ấm =





≤≤+
<≤−
≥≤
40x30 nÕu 4x/10-
30x20 nÕu 210/x

∩
N , bù L…
được định nghĩa cùng với tập mờ, song sẽ không mâu thuẫn với các phép toán tương tự
của tập hợp kinh điển nếu như chúng thoả mãn những tính chất tổng quát được phát biểu
như “tiên đề” của lý thuyết tập hợp kinh điển. Đó là các “tiên đề” cho phép giao L
∩
N,
phép hợp và phép bù.
2.1 Phép hợp hay toán tử OR
Hợp của hai tập mờ (A∪B) thể hiện mức độ một phần tử thuộc về một trong hai tập
là bao nhiêu.
Công thức: μ
A
∨
B
(x) = max (μA(x) , μB(x) )
Ví dụ: μ
Tre
(An) = 0.8 và μ
Trung niên
(An) = 0.3
=> μ
Tre
∨
Trung Niên
(An) = max( 0.8, 0.3) = 0.8
17
#$%&'()*+,*,*-
  !"
2.2 Phép giao hay toán tử AND

(An) = 1 – 0.8 = 0.2
Nhận xét: Logic mờ không tuân theo các luật về tính bù của logic truyền thống:
μ
¬A
∨
A
(x) ≡1 và μ
¬A
∧
A
(x) ≡0
Ví dụ: μ
¬A
∨
A
(x) = max (0.8, 0.2) = 0.8
μ
¬A
∧
A
(x) = min( 0.8, 0.2) = 0.2
18
#$%&'()*+,*,*-
  !"
3. Suy luận xấp xỉ dựa trên logic mờ
Suy diễn xấp xỉ hay còn gọi là suy luận mờ đó là quá trình suy ra những kết luận
dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, dữ liệu đầu vào cho
trước cũng không hoàn toàn xác định.
Trong công trình của mình Zadeh đưa ra khái niệm lập luận xấp xỉ như sau:
Bảng Suy luận xấp xỉ

\*
AwTN
\*
Kết luận wTN
,
19
#$%&'()*+,*,*-
Input A0
Phương pháp lập luận và suy diễn xấp xỉ
Output B0
  !"
Trong đó L

và N

là các điều kiện mờ, mô hình này mô tả quan hệ phụ thuộc giữa
hai đại lượng L và N. Giá trị XTL
,
được gọi là Input còn wTN
,
gọi là Output.
Phương pháp lập luận xấp xỉ tính wTN
,
gồm các bước sau:
Bước 1: Qxb.<.<b Chúng ta xem các khái niệm mờ L

, N

là
các nhãn của tập mờ biểu thị ngữ nghĩa của L

=
=
trong đó @ là một trong các công thức mô tả giá trị chân lý của các
phép toán logic hội và tuyển ( chẳng hạn ta có thể chọn các hàm tương ứng là (  và
@). Việc kết nhập như vậy bảo đảm
µ
 
chứa các thông tin được cho bởi các mệnh đề
vA dạng mệnh đề logic mờ.
Bước 3: YaN
,
 Để tính N
,
ta sử dụng công thức N
,
= L
,

µ
, trong đó  là
phép hợp thành của L
,
và
µ
.
Bước 4: !yP Kết quả tính ở bước 3 là một giá trị mờ. Trong nhiều bài toán điều
khiển người ta cần xác định giá trị thực của biến trong w. Phương pháp tính giá trị thực
"tương ứng" với giá trị chân lý của N
,
được gọi là phương pháp khử mờ. Sẽ không có

+ µ
A
(x) là một ánh xạ từ X  [0,1] được gọi là hàm liên thuộc xác định độ thuộc
của x vào tập A
4.1. Miền xác định của tập mờ
Miền xác định của tập mờ A trên không gian nền X là một tập con các phần tử của
X được ký hiệu  thỏa mãn
S= {x∈ X | µ
A
(x) > 0}
4.2. Miền tin cậy của tập mờ
Miền tin cậy của tập mờ A trên không gian nền X là một tập con các phần tử của X
được ký hiệu  thỏa mãn
= {x∈ X | µ
A
(x) = 1}
4.3. Miền biên của tập mờ
Miền biên của tập mờ A trên không gian nền X là một tập con các phần tử của X
được ký hiệu k thỏa mãn
k= {x∈ X | 0< µ
A
(x) <1}
8z Ta định nghĩa young - trẻ. Là tập hợp những người từ 20 tuổi trở xuống,
những người từ 30 tuổi trở lên không còn trẻ nữa, nhưng những người từ 21 đến 30 tuổi
vẫn thuộc tập Young với độ liên thuộc nào đó nhỏ hơn 1.
Ta định nghĩa hàm liên thuộc của tập Young như sau:
30)(
30)(10
20)(
0

chất sau:
- µ
A
là O{A8 (miền tin cậy khác rỗng)
- µ
A
là 0O (mỗi giá trị rõ phải thuộc miền tin cậy)
- µ
A
là đơn điệu tăng trên biên trái và đơn điệu giảm trên biên phải
Trong ngôn ngữ nói, có thể mô tả số mờ với các từ như xấp xỉ, khoảng; gần đến,
5.2. Số mờ dạng tam giác
- Là số mờ được mô tả kiểu "@@Fa@SGH"
- Biểu diễn một khoảng (a-α, a, a+β)
- Hàm thuộc được xác định như sau:
]4P8'









>
≤<
−
−
≤<

#$%&'()*+,*,*-
A_@`
3020
]<G7eaP
)(@
L
µ
1
a
3
a
2
a
1
x0
1
a-
a
b+
b
  !"
A =
AO
GG@
G@
G@
@
@
0
],(1

I. Mô tả bài toán thực tế
Xuất phát từ yêu cầu thực tế tại trường Đại học CSND, tôi có ý tưởng ứng dụng lý
thuyết logic mờ trong công tác trực ban tại trường.
Do đặc thù của lực lượng vũ trang, cán bộ chiến sĩ tại trường phải trực đêm vào các
ngày trong tuần từ 19
h
00 đến 7
h
00. Ngoài nhiệm vụ kiểm tra quân số tại các phòng ở của
sinh viên, và các phòng làm việc của các đơn vị, cán bộ trực ban phải có nhiệm vụ khóa
cổng 1 và cổng 2 vào lúc 22
h
00. Để đi từ cổng 1 đến cổng 2 của trường, cần phải đi qua
các phòng ban và phòng học, do đó cần phải có một con đường ngắn nhất giữa 2 cổng để
giúp cán bộ trực ban hoàn thành nhiệm vụ đúng thời gian đã quy định.
Bài toán này được đưa về dạng bài toán tìm đường đi ngắn nhất biểu diễn cung
đường đi là số mờ dạng khoảng.
II. Phát biểu bài toán
Giả sử xét đồ thị có hướng G=(V,E) mỗi cung (u,v)
∈
E được đặt tương ứng là số mờ
dạng khoảng.
Các bài toán đường đi ngắn nhất được chia thành 3 dạng chính:
].9P.}F|3/E.B3/.
].9P.}F|3/E.BFQ/.
].9P.}F~/GF•
Bài toán được đề cập đến ở đây là bài toán ở dạng thứ nhất: tìm đường đi ngắn nhất
từ một nút nguồn đến một nút đích cho trước.
Input:
a~'.S;a€;/E*_•*`‚/._•-`

ƒ
ƒvƒv
1 1
),(),(
(với i là một đỉnh thông thường trong đồ thị)
Tổng đường đi ra khỏi đỉnh nguồn bằng tổng đường đi vào đỉnh đích
∑ ∑
= =
=

ƒ

ƒ
ƒvƒ0v
1 1
),(),(
III. Mô hình bài toán
Gọi c
ij
là chiều dài cung i,j. Bài toán đường đi ngắn nhất trong đồ thị được phát biểu
như sau:
* Hàm mục tiêu:
Min
∑∑
= =



ƒ
ƒƒ

1
1 1
25
#$%&'()*+,*,*-