Đại học quốc gia thành phố Hồ Chí Minh
Đại học Công Nghệ Thông Tin
Khoa Khoa Học Máy Tính

PHƯƠNG PHÁP TOÁN TRONG TIN HỌC
TÌM HIỂU LOGIC & ỨNG
DỤNG
GVHD: PGS.TS. Nguyễn Phi Khứ
Học Viên : HỒ DUY NHẬT LINH – CH1301028
Lớp: CH08-01
TP.HCM 12-2013
Mục lục
Trang 2
I. Tổng quan:
A. Giới thiệu chung:
Từ “logic” có nguồn gốc từ Hy Lạp “Logos”, có rất nhiều nghĩa, trong đó
hai nghĩa ngày nay được dùng nhiều nhất như sau. Thứ nhất, nó được dùng để
chỉ tính quy luật của sự tồn tại và phát triển của thế giới khách quan. Thứ hai, từ
“logic” dùng để chỉ những quy luật đặc thù của tư duy. Khi ta nói “Logic của sự
vật là như vậy”, ta đã sử dụng nghĩa thứ nhất. Còn khi nói “Anh ấy suy luận hợp
logic lắm”, ta dùng nghĩa thứ hai của từ logic.
Theo quan điểm phổ biến nhất hiện nay thì logic học là khoa học về các
hình thức, các quy luật của tư duy. Nhưng khác với các khoa học khác cũng
nghiên cứu về tư duy như tâm lý học, sinh lý học thần kinh, , logic học nghiên
cứu các hình thức và quy luật của tư duy để đảm bảo suy ra các kết luận chân
thực từ các tiền đề, kiến thức đã có, và đưa ra các phương pháp để có được
các suy luận đúng đắn. Để hiểu cặn kẽ hơn về đối tượng của logic học, ta phải
tìm hiểu các đặc điểm của giai đoạn nhận thức lý tính và trả lời cho câu hỏi thế
nào là hình thức và quy luật của tư duy.
B. Lịch sử phát triển:
Với tư cách là một khoa học, logic học ra đời vào thế kỷ IV trước công

nguyên. Người sáng lập ra logic học là nhà triết học Hy Lạp vĩ đại Aristote (384 -
322 tr. CN). Mặc dù trước Aristote đã có nhiều nhà triết học - chẳng hạn
Pythagor, Democrite, Socrate, Platon - sử dụng và nghiên cứu một số kiểu suy
luận, một số kiểu phán đoán, nhưng chính Aristote mới là người khai sinh ra
logic học như là một khoa học. Aristote được coi là người khai sinh ra logic học
“không phải vì ông là người đầu tiên đã hệ thống hoá được các thao tác suy luận
vốn trước ông chỉ tồn tại riêng rẽ, chưa rõ ràng, mà chính là vì ông là người đầu
tiên đã làm cho các thao tác đó trở thành đối tượng nghiên cứu, làm thành đối
tượng nghiên cứu chính các thao tác suy luận đó, với tư cách là các chỉnh thể,
chứ không chỉ là thành tố này hay thành tố khác của suy luận” [5]. Nghĩa là ở
Aristote các thao tác suy luận đã là các đối tượng nghiên cứu độc lập, chứ
không chỉ được nghiên cứu trong mối quan hệ với các suy luận. Ông đã nghiên
cứu một cách hệ thống về khái niệm, phán đoán, phép chứng minh và bác bỏ,
ông đã nêu lên ba quy luật cơ bản của tư duy. Ông đã xây dựng hoàn chỉnh lý
thuyết tam đoạn luận. Ông cũng là người đầu tiên phân loại các sai lầm logic.
Vấn đề trung tâm trong logic học của Aristote là vấn đề suy luận diễn dịch, trong
đó có các phép chứng minh, được xây dựng như thế nào. Các vấn đề khác xoay
quanh vấn đề này. Các công trình của ông về logic học về sau được tập hợp lại
trong bộ Organon.
Trang 3
Ở thời cổ đại, logic học của Aristote được các học trò của ông tiếp tục phát
triển sau khi ông mất. Nhưng người ta chỉ nêu ra thêm một số quy tắc suy luận
với tiền đề là phán đoán điều kiện và phán đoán lựa chọn nghiêm ngặt mà thôi.
Các nhà triết học thuộc trường phái Megat và trường phái Khắc kỷ, đặc biệt là
Chrysippus (279-206 tr. CN) - người cho rằng các mệnh đề chỉ có thể đúng hoặc
sai và là người đã nghiên cứu các quy tắc xác định tính đúng sai của mệnh đề
phức dựa vào tính đúng sai của các mệnh đề thành phần tạo nên nó -, đi xa
hơn. Họ đã nghiên cứu quan hệ suy diễn, nghĩa là quan hệgiữa các tiền đề và
kết luận của suy luận. Để nghiên cứu vấn đề này, họ đưa ra khái niệm bao hàm
(implication). Họ đã đưa ra hình thức đầu tiên của định lý diễn dịch - định lý làm

cơ sở cho các phép chứng minh trong các hệ thống hình thức hóa: một suy luận
là hợp logic khi và chỉ khi công thức biểu thị nó là một công thức hằng đúng.
Công thức biểu thị một suy luận có được khi ta liên kết các tiền đề của nó với
nhau thành phần tiền đề bằng các dấu toán hội, rồi liên kết phần tiền đềvới kết
luận bằng dấu toán kéo theo (dấu implication).
Các thành tựu quan trọng nhất của logic học ở thời La Mã cổ đại là: hệ
thống các thuật ngữ logic được sử dụng đến ngày nay; hình vuông logic (sau
này được Boethius hoàn thiện); lý thuyết về tam đoạn luận phức hợp và tam
đoạn luận với tiền đề là phán đoán quan hệ.
Ở thời trung cổ, logic học của Aristote được nghiên cứu phát triển bởi các
nhà triết học kinh viện. Các thành quả thời kỳ này chủyếu là các nghiên cứu về
khái niệm và ngữ nghĩa học. Các nhà logic học có đóng góp lớn nhất ở thời kỳ
này là P. Abelard (1079-1142) - người đã xây dựng lại logic Aristote, đã phân biệt
các suy luận đúng về hình thức và đúng về nội dung và cho rằng chỉ các suy
luận đúng về hình thức mới là loại suy luận có giá trị thật sự-, và W. Occam
(1285-1349) - người dành một sự quan tâm lớn đến logic hình thái, xây dựng
học thuyết về siêu ngôn ngữ (metalanguage), nghiên cứu toàn diện về tam đoạn
luận đơn của Aristote, phân định các kiểu đúng và không đúng.
Vào thời Phục hưng logic học truyền thống bị chỉ trích mạnh mẽ. Một số
nhà tư tưởng tiến bộ của thời kỳ này buộc tội logic học là chỗ dựa cho tư tưởng
kinh viện.
Nhà triết học người Anh F. Bacon (1561-1626) cho rằng tam đoạn luận của
Aristote hoàn toàn vô ích, vì nó không cho phép tìm ra các thông tin mới từ các
tiền đề đã có, vậy nên khoa học sử dụng nó không thể phát hiện được các quy
luật mới thông qua việc nghiên cứu các sự kiện thực nghiệm đã biết. Ông xây
dựng nên logic quy nạp. Logic này về sau được một nhà triết học và logic học
Anh khác là S. Mill (1806 - 1873) phát triển.
Trang 4
Về phần logic diễn dịch thì phải đến thếkỷ XVII nó mới được nhà toán học
và triết học như R. Descates (1596 - 1650) người Pháp thanh minh và bảo vệ.

Ông muốn xây dựng nó thành phương pháp nhận thức tổng hợp. Công lao rất
lớn trong việc phát triển logic diễn dịch thuộc về nhà triết học, toán học và logic
học người Đức Leibniz (1646 - 1716). Ông được coi là người đầu tiên đặt nền
tảng cho logic ký hiệu. Ông đưa ra tư tưởng sử dụng các ký hiệu và phương
pháp toán học vào logic học. Ông chỉ ra rằng khi sử dụng các ký hiệu thay cho
lời nói, không những chúng ta làm cho tưtưởng được trởnên rõ ràng hơn và
chính xác hơn, mà còn làm cho tư tưởng trở nên đơn giản hơn. Ông muốn xây
dựng logic học thành phép tính (calculus rationator) - ngôn ngữ nhân tạo tổng
quát, trong đó các suy luận được hình thức hóa giống như các phép tính được
hình thức hóa trong đại sốvậy. Thậm chí ông còn mơ đến một ngày kia nếu các
nhà triết học bất đồng ý kiến với nhau thì họ không cần phải tranh cãi nữa, mà
chỉ cần sử dụng một hệ thống logic như vậy mà tính toán xem ai đúng, ai sai. Tư
tưởng của Leibniz về sau được các nhà toán học và logic học J. Boole (1815 -
1864) người Anh, và De Moorgan phát triển. Họ đã xây dựng các hệ đại sốlogic.
Sự phát triển của logic hình thức trong thời hiện đại gắn liền với tên tuổi
của các nhà bác học lớn như G. Frege (1848 - 1925), Peano (1858 - 1932), B.
Russell (1872 - 1970), Marcov, Peirce … . Quá trình phát triển của logic học kể
từ Leibnitz, và đặc biệt là từ Russel trở về sau, liên quan rất chặt chẽ với toán
học. Sự liên quan chặt chẽ đó giữa hai ngành logic học và toán học được Russel
khắc họa như sau trong cuốn Nhập môn về triết học của toán học của ông: “Toán
học và logic học, về mặt lịch sử là hai ngành khác nhau, nhưng trong quá trình
phát triển, chúng sát lại gần nhau: logic học đã “toán hóa” hơn, và toán học đã
“logic hóa” hơn. Ngày nay khó mà vạch ra một đường ranh dứt khoát phân chia
logic học và toán học. Trên thực tế ngày nay chúng gần như là một. Bằng chứng
về sự đồng nhất của chúng thể hiện trong những chi tiết: xuất phát từ các tiền đề
và các phương pháp suy luận, ta đã đứng trên mảng đất của logic; nhưng khi đi
đến những kết quả bằng phương pháp suy diễn ta đã đứng trên mảng đất của
toán”[6]. Trong cuốn sách nổi tiếng Principia Mathematica của mình, các tác giả
A. Whitehead (1861 - 1947) và B. Russell đã cho rằng có thể quy giản toàn bộ
toán học lý thuyết về logic học, nói cách khác, coi toán học là một phần của logic

học. Ngược lại, một số nhà toán học khác lại coi logic là một ngành của toán
học.
Sự phát triển của logic học kể từ Leibniz đã bước sang một giai đoạn mới
hẳn về chất. Nếu như trong suốt cả ngàn năm trước đó logic học chỉ xác định
được một số lượng rất hạn chế - tính được bằng hàng chục - các dạng thức suy
luận đúng, và các dạng thức suy luận này tìm được chủ yếu nhờ phương pháp
kinh nghiệm, thì bây giờ, trong một khoảng thời gian tương đối ngắn, logic học
Trang 5
đã xác lập được một khối lượng dạng thức đúng nhiều hơn rất nhiều lần, và
nhiều phương pháp hiện đại, như phương pháp tiên đề, phương pháp hình thức
hóa, … được áp dụng thay cho kinh nghiệm.
Ngày nay logic học hình thức bao gồm rất nhiều nhánh khác nhau như
logic cổ điển, logic tình thái, logic thời gian, logic kiến thiết, logic relevant, logic
không đơn điệu, logic mờ, logic xác suất, logic quy nạp, logic lượng tử, logic đa
trị,…
Cuối thế kỷ XVIII, đầu thế kỷ thứ XIX nhà triết học người Đức Hegel xây
dựng nên logic biện chứng. Logic biện chứng cũng nghiên cứu các hình thức và
quy luật của tư duy, tuy nhiên, khác với logic hình thức, - là khoa học nghiên cứu
các hình thức và quy luật của tư duy khi tư duy phản ánh trạng thái xác định, ổn
định của sự vật và hiện tượng -, logic biện chứng nghiên cứu tư duy khi nó phản
ánh sự vật và hiện tượng trong sự vận động và phát triển của chúng, trong mối
liên hệ của chúng với các sự vật và hiện tượng khác. Logic hình thức nghiên
cứu các hình thức phản ánh lý tưởng hóa trong tư duy. Các hình thức phản ánh
hiện thực khách quan trong tư duy mà logic biện chứng nghiên cứu không lý
tưởng hóa như vậy. Logic biện chứng của Hegel là logic duy tâm. C. Mác và Ph.
Ăngghen đã xây dựng lại logic biện chứng của Hegel trên cơ sở duy vật. V. I.
Lênin và các nhà triết học mác-xít đã nghiên cứu phát triển sâu thêm logic học
biện chứng. Ngày nay logic biện chứng vừa là cơ sở phương pháp luận, vừa là
công cụ nhận thức, công cụ phát hiện quy luật mới, tri thức mới của các khoa
học.

C. Ứng dụng của Logic học:
Tư duy của con người bao giờ cũng diễn ra trong các hình thức nhất định
và phải tuân theo các quy luật logic, dù cho chủ thể tư duy có biết điều đó hay
không. Thế nhưng không phải bẩm sinh con người đã biết về các hình thức và
quy luật đó. Muốn biết, và quan trọng hơn, muốn sử dụng chính xác và sáng tạo
các hình thức và quy luật này thì phải nghiên cứu và ứng dụng thường xuyên.
Con đường ngắn nhất để thực hiện điều đó là nghiên cứu logic học. Nghiên cứu
logic học giúp cho sự hình thành, củng cố và hoàn thiện tư duy logic. Nó giúp
hình thành thói quen lập luận tuân theo các quy luật, sử dụng khái niệm và phạm
trù một cách chuẩn xác, giúp tránh được các sai lầm trong tư duy của bản thân
và phát hiện nhanh chóng sai lầm trong lập luận của người khác. Nghiên cứu
logic học là bỏ ra một khoảng thời gian tương đối nhỏ mà có thể nâng cao được
trình độ tư duy. Nhà logic nổi tiếng S. Mill nói: “Sau khi thấy rõ lý thuyết suy luận
đơn giản đến thế nào, thấy được khoảng thời gian cần thiết để có được tri thức
hoàn chỉnh về các nguyên lý, quy tắc cơ bản của nó và thậm chí còn có được
những kinh nghiệm đáng kể trong việc sử dụng chúng nhỏ đến thế nào thì tôi
Trang 6
thấy chẳng có một lý do nào để biện hộ cho những người muốn hoạt động tri
thức có kết quả mà lại không nghiên cứu logic. Logic học là người truy đuổi vĩ
đại đối với tư duy nhầm lẫn và đen tối; nó làm tan sương mù bao phủ sự kém
hiểu biết của chúng ta, làm cho chúng ta nghĩ rằng mình hiểu đối tượng trong khi
thật ra không hiểu. Tôi tin rằng trong giáo dục hiện đại không gì có thể mang lại
nhiều lợi ích hơn cho sự hình thành các tư tưởng chính xác, những tư tưởng sử
dụng chính xác ý nghĩa của câu chữ và chống lại các thuật ngữ không chính xác,
nhiều nghĩa như là logic học.”[7]
Cùng với sự phát triển của khoa học và công nghệ, logic học ngày càng
được ứng dụng rộng rãi. Người ta sử dụng logic học để giúp giải quyết các vấn
đề nan giải của toán học, của điều khiển học, của các khoa học máy tính, …
Người ta sử dụng logic vị từ để làm các ngôn ngữ lập trình cho trí tuệ nhân tạo
(ví dụ ngôn ngữ lập trình PROLOG - PROgraming in LOGic); ứng dụng logic mờ

(Fuzzy logic) để phát triển công nghệ mờ, …
II. Logic mệnh đề:
A. Khái quát:
Logic mệnh đề là kiểu biểu diễn tri thức đơn giản nhất và gần gũi nhất đối
với chúng ta. Đồng thời nó cũng là môt khái niệm cơ bản của toán học không
được định nghĩa mà chỉ được mô tả. Do đó giá trị của nó chỉ có thể hoặc là đúng
hoặc là sai. Giá trị của mệnh đề không chỉ phụ thuộc vào bản thân mệnh đề đó.
Có những mệnh đề mà giá trị của nó luôn đúng hoặc sai bất chấp thời gian
nhưng cũng có những mệnh đề mà giá trị của nó lại phụ thuộc vào thời gian,
không gian và nhiều yếu tố khách quan khác.
Ví dụ:
• Sáng nay An ăn xôi
• Noel năm nay trời rất lạnh
• Minh chưa làm bài
B. Các phép toán trên mệnh đề:
1. Phép phủ định:
Mệnh đề mà nó đúng khi A sai và nó sai khi A đúng gọi là mệnh đề phù
định ý hiệu hoặc hay
Trang 7
2. Phép hội
Mệnh đề mà chỉ đúng khi cả mệnh đề A và B đều đúng gọi là mệnh đề Hội
(hay hội) của mệnh đề A và B. Ký hiệu hoặc A.B hoặc A&B.
3. Phép tuyển
Mệnh đề mà nó chỉ sai khi cả mệnh đề A và B đều sai được gọi là mệnh
đề tuyển (hay tuyển) của mệnh đề A và B. Ký hiệu hoặc A + B.
4. Phép kéo theo
Mệnh đề mà nó chỉ sai khi mệnh đề A đúng và mệnh đề B sai được gọi là
mệnh đề A kéo theo B. Ký hiệu:
5. Phép tương đương
Mệnh đề mà nó chỉ đúng khi mệnh đề A và mệnh đề B nhận cùng một

giá trị được gọi là A tương đương với B. Ký hiệu: hoặc
C. Các luật logic mệnh đề:














Trang 8






D. Đánh giá:
1. Điểm mạnh:
2. Điểm yếu:
• Không thể hiện được các phát biểu có các biến:
Ví dụ:
x = y + 3 và x > 3.
Bởi vì các biến chưa có giá trị. Tuy nhiên, phát biểu dạng như trên x

uất hiện rất
nhiều.
• Những sự tương đương sau không biểu diễn được bằng logic mệnh
đề:"Không phải tất cả bánh đều ăn được" và "Chỉ một số bánh ăn đ
ược".
• Để suy diễn, mỗi mệnh đề phải được liệt kê riêng lẽ.
Để khắc phục nhược điểm trên của logic mệnh đề người ta đưa ra cách
khắc phục bằng cách liệt kê riêng rẽ mỗi mệnh đề để tiến hành suy diễn.
Ví dụ:
• Phát biểu x > 3 có 2 phần:
- Biến x
- Tính chất của biến x (> 3), được gọi là vị từ (predicate)
Nói cách khác, predicate là vị từ mô tả tính chất của những đối tượng,
hoặc quan hệ giữa chúng. Ký hiệu phát biểu P(x)
⇒ P(2), P(4) là mệnh đề
Trang 9
III. Logic vị từ:
A. Khái quát:
Môn Logic như được nghiên cứu ngày nay rất khác với môn học đã được
nghiên cứu trước đây, và sự khác biệt chính là sự phát minh của logic vị từ.
Trong khi logic tam đoạn luận của Aristote định ra những dạng thức cho những
phần có liên quan với nhau trong mỗi phán đoán, logic vị từ cho phép các câu
được phân tích thành chủ đề và các luận cứ theo nhiều cách khác nhau, do vậy
cho phép logic vị từ giải quyết được vấn đề tổng quát hóa nhiều lần - vấn đề đã
làm bối rối các nhà logic học thời trung cổ. Với logic vị từ, lần đầu tiên, các nhà
logic học đã có khả năng đưa ra các phép lượng hóa (quantifiers) đủ tổng quát
để diễn tả mọi luận cứ có mặt trong ngôn ngữ tự nhiên.
Sự khám phá ra logic vị từ thường được coi là công của Gottlob Frege,
người cũng được xem là một trong những sáng lập viên của ngành triết học
phân tích, nhưng dạng phát biểu có hệ thống thông dụng nhất ngày nay của

logic vị từ là logic bậc nhất (first-order logic) được trình bày trong cuốn sách Các
nguyên lý về logic lý thuyết (Grundzüge der theoretischen Logik) của David
Hilbert và Wilhelm Ackermann vào năm 1928. Tính tổng quát có tính phân tích
của logic vị từ cho phép hình thức hóa toán học và đẩy mạnh nghiên cứu về lý
thuyết tập hợp, cho phép sự phát triển của cách tiếp cận của Alfred Tarski đối với
lý thuyết mô hình; và không quá lời khi nói rằng nó là nền tảng của logic toán học
hiện đại.
B. Khái niệm:
Cho A là một tập hợp khác rỗng. Giả sử,ứng với mỗi x A ta có một mệnh
đề p(a). Khi đó, ta nói p = p(x) là một vị từ theo một biến (xác định trên A). Nói
cách khác, vị từ có thể xem là một hàm mệnh đề có nhiều biến hoặc không có
biến nào, nó có thể đúng hoặc sai tùy thuộc vào giá trị của biến và lập luận của
vị từ.
• Bản thân P(x) không phải là mệnh đề.
• Nếu thay x bằng những giá trị cụ thể thuộc tập hợp A ta sẽ được một
mệnh đề P(x) nghĩa là khi đó chân trị của P(x) được gọi là các biến tự do
của vị từ.
Ví dụ:
• Các câu có liên quan tới các biến như: “x > 100”, “z - m = 10” rất hay gặp
trong toán học và trong các chương trình của máy tính. Các câu này
không đúng cũng không sai vì các biến chưa được gán giá trị xác định.Nói
cách khác, vị từ có thể được xem là một hàm mệnh đề có nhiều biến hoặc
Trang 10
không có biến nào, nó có thể đúng hoặc sai tùy thuộc vào giá trị của biến
và lập luận của vị từ.
• Câu {n là chẵn} là một vị từ. Nhưng khi cho n là một số cụ thể là chẵn hay
là lẻ ta được một mệnh đề:
- n = 2 :{2 là chẵn}: mệnh đề đúng.
- n = 5 :{5 là chẵn}: mệnh đề sai.
Vị từ { n là chẵn} có 2 phần. Phần thứ nhất là biến x là chủ ngữ của câu.

Phần thứ hai "là chẵn" cũng được gọi là vị từ, nó cho biết tính chất mà chủ
ngữ có thể có.
Ký hiệu: P(n) = {n là chẵn} Tổng quát, người ta nói P(n) là giá trị của hàm
mệnh đề P tại n. Một khi biến n được gán trị thì P(n) là một mệnh đề.
C. Phép toán vị từ:
1. Kí hiệu:
o Các kí hiệu hằng: a, b, c, Hằng, Thạnh, John,
o Các kí hiệu biến: x, y, z,
o Các kí hiệu vị từ: P, Q, R, Thích, Have_color, (viết hoa kí tự đầu).
o Vị từ một biến. Ví dụ: Have_color(red).
o Vị từ nhiều biến. Ví dụ: Thích(Thạnh, kẹo).
o Vị từ không biến: là các mệnh đề P, Q,
o Kí hiệu hàm: f,g,cos,sin,…. Mỗi hàm đều có ít nhất 1 biến.
o Kí hiệu kết nối logic: .
o Kí hiệu lượng tử: ∀ (với mọi/phổ dụng), ∃ (tồn tại).
o Kí hiệu ngăn cách: dấu phẩy, dấu ngoặc mở và dấu ngoặc đóng.
2. Các phép toán trên vị từ 1 biến:
• Phép toán phủ định ký hiệu: ¬ P(x) cũng là một vị từ trên trường M mà khi
thay thế x = a ∈ M ta được mênh đề ¬ P(a) nhận giá trị đúng khi P(a) nhận
giá trị sai và ngược lại.
• Hội hai vị từ P(x) và Q(x) ký hiệu: P(x) ^Q(x) trên trường M mà khi thay thế
x = a ∈ M ta được mệnh đề P(a) ^Q(a) nhận giá trị đúng khi cả P(a) và
Q(a) nhận giá trị đúng, sai trong tất cả các trường hợp còn lại.
• Tuyển hai vị từ P(x) và Q(x) ký hiệu: P(x) v Q(x) trên trường M mà khi thay
thế x = a ∈ M ta được mệnh đề P(a) v Q(a) nhận giá trị sai khi cả P(a) và
Q(x) nhận giá trị sai, đúng trong tất cả các trường hợp còn lại.
• Vị từ P(x) suy ra Q(x) ký hiệu: P(x) -> Q(x) trên trường M mà khi thay thế
x = a ∈ M ta được mệnh đề P(a) -> Q(a) nhận giá trị đúng khi cả P(a) sai
hoặc P(a) đúng, Q(a) đúng, mệnh đề này sai khi giả thuyết là P(a) đúng,
kết luận là Q(a) sai.

Trang 11
3. Hạng thức:
Hạng thức là biểu thức thể hiện đối tượng. Hạng thức được định nghĩa đệ
quy như sau:
Kí hiệu hằng và kí hiệu biến là hạng thức: Nếu t1, , tn là hạng thức và f là
một hàm n biến thì f(t1, ,tn) là một hạng thức.
Ví dụ:
Hằng Bình là hạng thức và mother là hàm 1 biến:
=> Bình là một hạng thức.
=> mother(Bình) là một hạng thức.
=> mother(mother(Bình)) cũng là một hạng thức.
D. Không gian của vị từ:
Người ta có thể xem vị từ như là một ánh xạ P, với mỗi phần tử thuộc tập hợp
E ta được một ảnh P(x)
• ∈{ , 1}. Tập hợp E này được gọi là không gian của vị từ. ϕ
• Không gian này sẽ chỉ rõ các giá trị khả dĩ của biến x làm cho P(x) trở
thành mệnh đề đúng hoặc sai.
Trọng lượng của vị từ:
Chúng ta cũng thường gặp những câu có nhiều biến hơn. Vị từ xuất hiện
cũng như một hàm nhiều biến, khi đó số biến được gọi là trọng lượng của vị từ.
Vị từ P(a,b) = {a + b = 5} là một vị từ 2 biến trên không gian N. Ta nói P có
trọng lượng 2
Trong một vị từ P(x1, x2, ,xn) có trọng lượng là n. Nếu gán giá trị xác
định cho một biến trong nhiều biến thì ta được một vị từ mới Q(x1, x2, xn) có
trọng lượng là (n-1). Qui luật này được áp dụng cho đến khi n=1 thì ta
có một mệnh đề. Vậy,thực chất mệnh đề là một vị từ có trọng lượng là . ϕ
IV. Lượng từ:
A. Lượng từ tồn tại (∃)
Câu xác định "Tập hợp những biến x làm cho P(x) là đúng không là tập
hợp rỗng" là một mệnh đề. Hay "Tồn tại ít nhất một phần tử x trong không gian

sao cho P(x) là đúng" là một mệnh đề được gọi là lượng từ tồn tại của P(x). Ký
hiệu: ∃x P(x) .
Ví dụ:
Trang 12
P(x) = ”x > 3”
• Miền giá trị x ∈ R
• Mệnh đề: ∃xP(x) là T
Q(x) = ”x = x + 1”
• Miền giá trị x ∈ R
• Mệnh đề: ∃xQ(x) là F
B. Lượng từ với mọi (∀)
Câu xác định "Tập hơp những x làm cho P(x) đúng là tất cả tập hợp E" là
một mệnh đề. Hay "P(x) đúng với mọi giá trị x trong không gian" cũng là một
mệnh đề được gọi là lượng từ với mọi của P(x). Ký hiệu: ∀xP(x)
Ví dụ:
• Mọi sinh viên máy tính phải học môn logic, thì
o P(x) = "x phải học môn logic"
o Mệnh đề: ∀xP(x)
o S(x) = x là sinh viên máy tín
o P(x) = x phải học môn logic
o Mệnh đề: ∀x(S(x) → P(x))
C. Tầm vực của lượng từ
Ký hiệu bởi [] hoặc (), nếu không có thì tầm vực là công thức nhỏ nhất
ngay sau lượng từ. Biến x là bound nếu:
• Biến x được gán giá trị
• Biến x được lượng từ hóa
• Biến x là free nếu nó không bound
Ví dụ:
• ∀xP(x, y) thì x là bound và y là free
• ∀x(∃yP(x, y)∨Q(x, y)) thì x, y trong P(x, y) là bound, trong khi y trong

Q(x, y) là free
D. Cách định chân trị
• ∀xP(x) = P(x1) ∧ P(x2) ∧ . . . ∧ P(xn)
• ∃xP(x) = P(x1) ∨ P(x2) ∨ . . . ∨ P(xn)
Trong đó x¬1, x2, . . . , xn là liệt kê các giá trị có thể có của x
Trang 13
Thử tất cả các xi với ∀ để xác định T. Tìm một x
i
với ∃ để xác định T. Thứ
tự của lượng từ là quan trọng, chỉ trừ khi tất cả các lượng từ là "với mọi" hoặc tất
cả là "tồn tại". Đọc từ trái sang phải, áp dụng từ trong ra.
Ví dụ:
• ∀x∀y(x + y = y + x) T với tất cả x, y ∈ R
• ∀x∃y(x + y = 0) là T,trong khi ∃y∀x(x + y = 0) là F
E. Một số định lý lượng từ:
Định lý 1: Cho vị từ P(a, b) có trọng lượng là 2. Khi đó:
• ∀a∀b P(a,b) và ∀b∀a P(a, b) là có cùng chân trị.
o Nghĩa là : ∀a∀b P(a,b) ↔∀b∀a P(a, b)
o Ký hiệu: ∀(a,b) P(a,b)
• ∃a∃b P(a,b) và ∃b∃a P(a, b) là có cùng chân trị.
o Nghĩa là: ∃a∃b P(a,b) ↔ ∃b∃a P(a, b)
o Ký hiệu: ∃(a,b) P(a,b)
• Nếu ∃a∀b P(a,b) là đúng thì ∀b∃a P(a,b) cũng đúng nhưng điều ngược
lại chưa đúng.
Nghĩa là : ∃a∀b P(a,b) → ∀b∃a P(a,b)
Định lý 2:
¬ (∀ x P(x)) và ∃ x (¬ P(x) là có cùng chân trị.
¬ (∃ x P(x)) và ∀ x (¬ P(x) là có cùng chân trị.
Phương pháp ứng dụng.
Để đạt được phủ định của một mệnh đề xây dựng bằng liên kết

của những biến của vi từ với phương tiện định lượng, người ta thay
thế những định lượng ∀ bởi ∃, và ∃ bởi ∀ và sau cùng thay thế vị từ
bằng phủ định của vị từ đó.
Định lý 3: Cho P và Q là hai vị từ có cùng không gian.
• Mệnh đề ∀x (P(x) ∧ Q(x)) và (∀x (P(x) ∧∀x (Q(x)) là có cùng chân
trị.
• Nếu mệnh đề ∃x (P(x) ∧ Q(x)) là đúng thì ta có mệnh đề: (∃x P(x))
∧ (∃xQ(x)) cũng đúng.
• Mệnh đề ∃x (P(x) ∨ Q(x)) và (∃xP(x) ∨∃xQ(x)) là có cùng chân trị.
• Nếu mệnh đề ∀x (P(x) ∨ Q(x)) là đúng thì ta có mệnh đề ∀xP(x)
∨∀xQ(x) là đúng, nhưng điều ngược lại không luôn luôn đúng.
Trang 14
Chú thích:
Nếu P và Q là hai vị từ có cùng không gian E. Ta có :
• Tập họp A⊂ E : Tập hợp những phần tử x thuộc E mà ở chúng thì P(x)
là đúng.
• Tập họp B⊂ E: Tập hợp những phần tử x thuộc E mà ở chúng thì Q(x)
là đúng.
• Khi đó người ta lưu ý rằng, A∧B là tập hợp những x thuộc E mà ở
chúng mệnh đề P(x)∧Q(x) là đúng. Trong khi đó A∨B là tập hợp những
x của E mà ở đó mệnh đề P(x)∨Q(x) là đúng.
F. Công thức tương đương:
A tương đương B nếu và chỉ nếu (A → B) ∧ (B → A)
Ký hiệu:
A ≡ B |= (A → B) ∧ (B → A)
Một số công thức tương đương:
• ~∀x W(x) ≡ ≡ ∃x ~W(x)
• ~ ∃x W(x) ≡ ≡ ∀x ~W(x)
• ∃x (A(x) ∨ B(x)) ≡ ≡ ∃x A(x) ∨ ∃x B(x)
• ∀x(A(x) ∧ B(x)) ≡ ≡ ∀x A(x) ∧ ∀x B(x)

• ∃x (A(x) → B(x)) ≡ ≡ ∀x A(x) → ∃x B(x)
• ∀x∀y W(x,y) ≡ ≡ ∀y∀x W(x,y)
• ∃x ∃y W(x,y) ≡ ≡ ∃y∃x W(x,y)
G. Các phép tương đương có giới hạn:
Các phép tương đương sau đúng khi x không xuất hiện trong biểu thức C:
Disjunction
• ∀x(C ∨ A(x)) ≡ ≡ C ∨ ∀x A(x)
• ∃x(C ∨ A(x)) ≡ ≡ C ∨ ∃x A(x)
Conjunction
• ∀x(C ∧ A(x)) ≡ ≡ C ∧ ∀x A(x)
• ∃x(C ∧ A(x)) ≡ ≡ C ∧ ∃x A(x)
Implication
• ∀x (C → A(x)) ≡ ≡ C → ∀x A(x)
Trang 15
• ∃x (C → A(x)) ≡ ≡ C → ∃x A(x)
• ∀x (A(x) → C) ≡ ≡ ∃x A(x) → C
• ∃x (A(x) → C) ≡ ≡ ∀x A(x) → C
Một vài điều kiện không tương đương:
• ∀x W(x) → ∃x W(x)
• ∀x A(x) ∨ ∀x B(x) → ∀x(A(x) ∨ B(x))
• ∃x(A(x) ∧ B(x)) → ∃x A(x) ∧ ∃x B(x)
• ∀x(A(x) → B(x)) → (∀x A(x) → ∀x B(x))
• ∃y ∀x W(x,y) → ∀x ∃y W(x,y)
H. Dạng chuẩn PRENEX:
F = (Q1 x1) (Qn xn) (M)
M là công thức không chứa lượng từ
Ví dụ:
• F = (∀x)p(x) → (∃y)q(y)
• F = (∃x)¬p(x) ∨ (∃y)q(y)
• F = (∃x)(∃y) (¬p(x) ∨ q(y))

1. Dạng chuẩn Prenex không duy nhất.
Dạng chuẩn Prenex còn tương đương với công thức ban đầu.
a) Chuyển về dạng chuẩn Prenex :
• F = (∀x)(p(x) → (∃x)(∀y)(q(y) ∨ r(x)))
• F = (∀x)(¬p(x) ∨ (∃x)(∀y)(q(y) ∨ r(x)))
b) Đổi tên biến cục bộ.
• F = (∀x)(¬p(x) ∨ (∃z)(∀y)(q(y) ∨ r(z)))
• F = (∀x)(∃z)(∀y)(¬p(x) ∨ (q(y) ∨ r(z))).
2. Qui tắc chuyển 1 công thức về dạng Prenex.
1. Xoá toán tử "→".
2. Chuyển lượng từ ra phía trước.
3. Dạng chuẩn Prenex Hội/Tuyển:
F = (Q
1
x
1
) (Q
n
x
n
) (D
1
∨ … ∨ D
k
)
D
k
là hội của một hoặc nhiều mệnh đề.
Ví dụ :
Trang 16

F = (∀x)(∃z)(∀y)((¬p(x) ∧ q(y)) ∨ (q(y) ∧ r(z))).
a) Chuyển về dạng chuẩn Prenex hội :
F = (Q
1
x
1
) (Q
n
x
n
) (D
1
∧…∧ D
k
)
D
k
là tuyển của một hoặc nhiều mệnh đề.
Ví dụ :
F = (∀x)(∃z)(∀y)((¬p(x) ∨ q(y)) ∧ (q(y) ∨ r(z))).
b) Giải thuật chuyển công thức về dạng chuẩn Prenex
Hội/Tuyển:
1. Đổi tên biến
2. Xóa toán tử "→“ dùng A → D= ~A ∨ B.
3. Di chuyển ¬ (~) về bên trái của mỗi mệnh đề.
4. Chuyển các lượng từ ra bên trái của mỗi mệnh đề.
5. Dùng luật phân bố và kết hợp để chuyển về dạng tương ứng Hội/Tuyển.
Ví dụ:
Cho W= ∀xA(x) ∨∃xB(x) → C(x) ∧ ∃x C(x).
W ≡ ∀yA(y) ∨∃zB(z) → C(x) ∧ ∃tC(t) (Đổi tên biến )

≡ ~(∀yA(y) ∨∃zB(z)) ∨ (C(x) ∧∃t C(t)) (Xóa “→”)
≡ (~∀yA(y) ∧ ~∃zB(z)) ∨ (C(x) ∧∃t C(t)) (Di chuyển” ~”)
≡ (∃y~A(y) ∧ ∀z~B(z)) ∨ (C(x) ∧∃t C(t))
≡ ∃y∀z∃t((~A(y) ∧ ~B(z)) ∨ (C(x) ∧C(t)))
Đây là dạng chuẩn Prenex.
V. Ứng dụng:

Ví dụ 1: Biểu diễn câu:
(1) "Có kỹ sư trong tập đoàn đã tham quan trụ sở Microsoft"
(2) "Mọi kỹ sư trong tập đoàn đã tham quan trụ sở Facebook hoặc Google
"
thành một biểu thức logic.
Nếu ta đặt câu:
C(x): x đã thăm trụ sở Microsft
D(x): x đã thăm Facebook
E(x): x đã thăm Google
Ta có:
Trang 17
(1): ∃xC(x)
(2): ∀x(D(x) ∨ E(x))
VI. Tài liệu tham khảo:
[1] Ebook "Logic Vị từ", Nguyễn Quang Châu, khoa CNTT ĐHCN
Tp.HCM.
[2] GS. Nguyễn Hữu Anh, “Toán rời rạc 2 ” , Nhà xuất bản lao động xã
hội,2001.
[3] Trần Ngọc Danh, “Toán rời rạc nâng cao ”, Nhà Xuất Bản ĐHQG TP
HCM, 2001.
[4] PGS Đỗ Văn Nhơn, “ Giáo trình toán rời rạc ”, Nhà Xuất Bản ĐHQG
TP HCM, 2006.
[5] Z. N. Mikeladze, “Cơ sở của logic Aristote”, trong sách Aristote toàn

tập, Moskva, 1979, tr. 5 (tiếng Nga).
[6] Dẫn theo: Phan Thanh Quang, Giai thoại toán học, tập 2, NXB Giáo
dục, Hà Nội 1995, tr. 31.
[7] Dẫn theo: Iu. V. Ivlev, Bài giảng logic học, Moskva 1988, tr. 4-5
(tiếng Nga).
Trang 18