RƯỜN

I HỌC SƯ PH M TP. HỒ CHÍ MINH

KHOA CƠNG NGHỆ THƠNG TIN
CAO HỌC NGÀNH: KHOA HỌC MÁY TÍNH
KHỐ: 28


MƠN HỌ : PHƯƠN

PH P

N R N

N HỌC

Ề TÀI CUỐI KÌ:
TÌM HIỂU BÀI TOÁN 3-CNF SAT

Giảng viên hướng dẫn : TS. Huỳnh ăn ức
Sinh viên thực hiện

: Nguyễn Thanh Thuỷ

Lớp

: Khoa Học Máy Tính – Khố 28

MSSV

: KHMT – 2017 - 010

TP. Hồ Chí Minh,tháng 8 năm 2018


A.

M CL C
Giới thiệu ............................................................................................................. 3

B.

Cơ sở lý thuyết .................................................................................................... 3
1.

Tổng quan về thuật toán ........................................................................ 3
1.1 Định nghĩa: ....................................................................................... 3
1.2 Phân tích thuật tốn và đánh giá thời gian thực hiện thuật tốn ....... 3
1.2.1 Phân tích thuật tốn ................................................................... 3
1.2.2 Tại sao lại cần có thuật tốn hiệu quả? ...................................... 3

2.

Lý thuyết độ phức tạp............................................................................ 3
2.1 Máy tính Turing ................................................................................ 3
2.2 Các khái niệm về độ phức tạp của thuật toán ................................... 4
2.2.1 Độ phức tạp trong trường hợp xấu nhất..................................... 4
2.2.2 Độ phức tạp trung bình .............................................................. 4
2.2.3 Độ phức tạp tiệm cận ................................................................. 4
2.2.4 Độ phức tạp đa thức (Polynomial)............................................. 5

2.2.5 Thuật toán đa thức ..................................................................... 5
2.3 Cách tính độ phức tạp ....................................................................... 5
2.3.1 Các quy tắc cơ bản ..................................................................... 5
2.3.1.1 Quy tắc cộng: ...................................................................... 5
2.3.1.2 Lệnh Quy tắc nhân: ............................................................. 5
2.4 Lớp P, NP và mối quan hệ giữa lớp P và lớp NP ............................. 5
2.4.1 Lớp P .......................................................................................... 6
2.4.2 Lớp NP ....................................................................................... 6
2.4.3 Mối quan hệ giữa lớp P và lớp NP ............................................ 7

2.4.4 Lớp bài tốn NP - khó (NP - hard) và NP - đầy đủ (NP –
Complate) 7
2.4.4.1 Các bài toán quyết định ...................................................... 7
2.4.4.2 Bài tốn NP – Khó (NP – Hard) ......................................... 8
2.4.4.3 Bài toán lớp NPC ................................................................ 8
2.4.4.4 Mối quan hệ giữa P, NP và NPC được biểu diễn như hình
sau:
……………………………………………………………8
2.4.5 Một số bài tốn NPC.................................................................. 9
- Bài tốn Vertex – Cover ............................................................... 9
3.

Lơgic mệnh đề ....................................................................................... 9
3.1 Công thức Lôgic mệnh đề................................................................. 9
1


3.2 Chuẩn tắc hội CNF ......................................................................... 10
3.3 Giải quyết các bài toán chứng minh logic ...................................... 10
3.3.1 Bài toán chứng mình logic:...................................................... 10

3.3.2 Cách giải quyết ........................................................................ 10
C.

Nội dung ............................................................................................................ 11
1.

Bài toán SAT ....................................................................................... 11
1.1 Lịch sử phát triển của SAT: ............................................................ 11
1.2 Bài toán SAT .................................................................................. 11
1.3 Bài toán CNF-SAT ......................................................................... 12
1.4 Bài toán chứng minh thỏa mãn (SAT):........................................... 12
1.5 Giải quyết bài toán SAT ................................................................. 12
1.5.1 Phương pháp Backtracking ...................................................... 12

1.5.2 Các phương pháp tối ưu hoá lặp (Iterative optimization
methods)
………………………………………………………………..13
2.

Bài toán 3-CNF SAT. .......................................................................... 13
2.1 Định nghĩa....................................................................................... 13
2.2 Ứng dụng bài toán 3 - SAT............................................................. 14
2.3 Thuật toán DPLL giải quyết các bài toán SAT .............................. 15
2.3.1 Lịch sử ..................................................................................... 15
2.3.2 Giải thuật DPLL....................................................................... 15

D.

2.3.3 Cài đặt giải thuật ...................................................................... 16
Kết luận ............................................................................................................. 16


E.

Tài liệu tham khảo ............................................................................................. 16

2


A. Giới thiệu
Trong Tốn học có rất nhiều dạng tốn và bài tốn khác nhau, có bài tốn là
tiền đề hoặc là kết quả của bài toán khác. Nhiều bài toán vẫn chưa được giải nhưng
là khởi nguồn để con người tìm hiểu và tìm tịi.
Tốn học đang được áp dụng rộng rãi trong các lĩnh vực trong cuộc sống.
Phương pháp Toán là cơ sở quan trọng trong nhiều ngành khoa học cũng như ngành
Khoa học máy tính, trong đó có các bài tốn tìm thỏa mãn SAT (Satisfiability).
Ở bài báo cáo này tơi xin trình bày bài tốn 3SAT nhưng trước đó tơi sẽ trình
bày một số cơ sở lý thuyết của bài toán ở phần thứ đầu sau đó mới đi vào bài tốn.
B.

ơ sở lý thuyết

1.

Tổng quan về thuật toán

ịnh nghĩa:
Thuật toán là một dãy hữu hạn các bước, mỗi bước mơ tả chính xác các phép
tốn hoặc hành động cần thực hiện…để cho ta lời giải của bài toán.
Các đặc trung của thuật toán
- Input

- Output
- Tính xác định
- Tính khả thi
- Tính dừng
- Tính đơn vị
- Tính tổng qt
1.1

1.2

Phân tích thuật tốn và đánh giá thời gian thực hiện thuật tốn

1.2.1

Phân tích thuật tốn
Phân tích thuật tốn là q trình tìm ra những đánh giá về thời gian và dung
lượng bộ nhớ cần thực hiện thuật tốn.
Hầu hết các bài tốn đều có rất nhiều thuật toán khác nhau để giải quyết
chúng và nhiệm vụ của chúng ta là phải tìm thuật tốn tốt nhất để thực hiện bài toán
đã đặt ra
1.2.2

Tại sao lại cần có thuật tốn hiệu quả?
Kỹ thuật máy tính ngày càng tiến bộ rất nhanh, các máy tính lớn có thể đạt
hàng trăm triệu phép tốn mỗi giây. Tuy nhiên có những thuật toán mà độ phức tạp
về thời gian là rất lớn mà các máy tính hiện đại này cũng tốn rất nhiều thời gian. Khi
đó thì việc phân tích thuật tốn để tìm ra những thuật tốn hiệu quả là cần thiết.
2.
2.1


Lý thuyết độ phức tạp

Máy tính Turing
Máy tính Turing là một máy tính tốn trừu tượng, vừa có khả năng của máy
tính thực sự , vừa cho phép định nghĩa về mặt tốn học về những gì có thể tính tốn
được.
3


Một máy Turing là một bộ T = (, Q, , , q0, b ,F)
Trong đó :
 Q là một tập hữu hạn các trạng thái,
 Γ là bộ chữ trên băng (bộ chữ dùng trên băng),
 b∈là ký hiệu trống (ký hiệu duy nhất cho phép xuất hiện một cách
vô hạn trên băng ở bất kỳ bước nào trong q trình tính tốn),
 ⊆Γ là bộ chữ vào (bộ chữ dùng cho xâu vào),
 : Q x Γ  Q x Γx {L, R} là một hàm bộ phận, hay còn gọi là hàm
dịch chuyển (là hàm định nghĩa các việc dịch chuyển trạng thái của
máy Turing hoặc máy trạng thái), trong đó L và R được hiểu là trái
(Left) và phải (Right)),
 q0∈Q là trạng thái đầu (trạng thái khởi tạo),
 F⊆Q là tập các trạng thái thừa nhận – accepting state (hoặc trạng
thái cuối).
Nhận xét: Máy Turing có cấu tạo cực kì đơn giản nhưng lại làm được mọi việc liên
quan tới tính tốn các phép tính. Từ mơ hình này có thể định nghĩa ra phép cộng
(mã hóa dạng nhị phân) bằng cách dịch chuyển đầu đọc 0, 1 và từ đó định nghĩa ra
các phép tính khác.
Có hai loại:
 Máy tính Turing tất định
 Máy tính Turing khơng tất định

2.2
2.2.1

2.2.2

Các khái niệm về độ phức tạp của thuật toán
ộ phức tạp trong trường hợp xấu nhất
Cho một thuật toán A với đầu vào n, khi đó:
- Độ phức tạp về bộ nhớ trong trường hợp xấu nhất được định nghĩa là:
LA(n) = max{lA(e)║│e│≤n}
Tức là chi phí lớn nhất về bộ nhớ.
Trong ví dụ trên: Dữ liệu vào: n+1, ra:1, phụ:1 nên LA(e)=n+3.
- Độ phức tạp thời gian trong trường hợp xấu nhất được định nghĩa là :
TA(n) = max{tA(e)║│e│≤n}
Tức là chi phí lớn nhất về thời gian.
Trong ví dụ trên TA(n) =1+2(n-1) = 2n-1.
ộ phức tạp trung bình
Là tổng số các độ phức tạp khác nhau ứng với các bộ dữ liệu chia cho tổng số.

2.2.3
ộ phức tạp tiệm cận
Thuật toán A với đầu vào n gọi là có độ phức tạp O(f(n)) nếu  hằng số C, N0:
TA(n)  C.f(n) ,  n  N0. Tức là TA(n) có tốc độ tăng là O(f(n))

4


2.2.4

ộ phức tạp đa thức (Polynomial)

Thuật toán được gọi là có độ phức tạp đa thức nếu tồn tại đa thức P(n) mà

TA(n)  C.P(n) ,  n  N0.
Thuật toán đa thức
Thuật toán được gọi là đa thức nếu độ phức tạp về thời gian trong trường
hợp xấu nhất của nó là đa thức.
Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức
tạp. Vì vậy người ta thường quan tâm đến việc đấnh giá độ phức tạp thời gian
trong trường hợp xấu nhất của bài toán.

2.2.5

Một số đơn vị đo tốc độ tăng:
- O(1): Hầu hết các chỉ thị của chương trình đều được thực hiện một lần hay
nhiều nhất chỉ một vài lần⇒Thời gian chạy của chương trình là hằng số.
- O(logN): Thời gian chạy của chương trình là logarit, tức là thời gian chạy của
chương trình tiến chậm khi N lớn dần.
- O(N):Thời gian chạy là tuyến tính. Đây là tình huống tối ưu cho một thuật
tốn phải xử lý N dữ liệu nhập.
- O(NlogN): Thời gian chạy tăng dần lên cho các thuật toán mà giải một bài
toán bằng cách tách nó thành các bài tốn con nhỏ hơn, sau đó tổ hợp các lời giải.
- O(N2): Thời gian chạy là bậc 2, trường hợp này chỉ có ý nghĩa thực tế cho
các bài toán tương đối nhỏ. Thời gian bình phương thường tăng dần trong các thuật
tốn phải xử lý tất cả các cặp phần tử dữ liệu (2 vịng lặp lồng nhau).
- O(N3): Thuật tốn xử lý các bộ ba của các phần tử dữ liệu (3 vịng lặp lồng
nhau)⇒ ý nghĩa với các bài tốn nhỏ.
- O(2n) , O(n!), O(nn): Thời gian thực hiện thuật toán là rất lớn do tốc độ tăng
của các hàm mũ.
2.3
2.3.1


Cách tính độ phức tạp
Các quy tắc cơ bản

2.3.1.1 Quy tắc cộng:
Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1, P2 và
T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn 2 chương trình đó nối
tiếp nhau là T(n)=O(max(f(n),g(n))
2.3.1.2 Lệnh Quy tắc nhân:
Nếu T1(n) và T2(n) là thời gian thực hiện 2 đoạn chương trình P1, P2 và
T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của 2 đoạn chương trình đó
lồng nhau là T(n)=O(f(n).g(n)).
2.4

Lớp P, NP và mối quan hệ giữa lớp P và lớp NP
Thuật tốn khơng đơn định đa thức(Nodeterministic Polynomial NP)

5


Với nhiều bài toán tối ưu tổ hợp vẫn chưa tìm được các thuật tốn đơn định
chạy trong thời gian đa thức, trong khi đó nếu cho phép dùng thuật tốn khơng đơn
định thì lại dễ dàng chỉ ra các thuật toán chạy trong thời gian đa thức.
Sự phân lớp các bài tốn.
Với một bài tốn cho trước có 2 khả năng xảy ra:
 Không giải được hoặc
 Giải được bằng thuật toán.
- Trường hợp bài toán giải được bằng thuật toán cũng chia làm 2 loại:
 Thực tế giải được: Được hiểu là thuật toán xử lý trong thời gian đủ
nhanh, thực tế cho phép, đó là thuật tốn có độ phức tạp thời gian là đa

thức.
 Thực tế khó giải: Được hiểu là thuật tốn xử lý trong nhiều thời gian,
thực tế khó chấp nhận, đó là thuật tốn có độ phức tạp thời gian là trên
đa thức (hàm mũ).
Do đó, ta có sự phân lớp các bài toán do 2 tác giả Cook và Karp đề xuất năm
1970-1971 như sau:
2.4.1

Lớp P
Thuật toán đơn định (Deterministic algorithm): là thuật tốn có kết quả thực
hiện mỗi phép tốn được xác định duy nhất.
Định nghĩa: Lớp P bao gồm tất cả các bài toán giải được bởi thuật toán đơn
định trong thời gian đa thức (tức là tồn tại thuật tốn giải quyết nó với thời gian
chạy đa thức)
Thuật tốn có độ phức tạp O(nk), k là hằng số.
Những bài tốn có độ phức tạp dạng O(k), O(log(n)), O(n), O(nlog(n)), nk đều
là những bài tốn thuộc lớp P.
Ví dụ: Thuật tốn Ơclide tìm Ước chung lớn nhất (UCLN) của hai số là thuật
toán giải trong thời gian đa thức. Do đó bài tốn tìm UCLN của hai số m và n thuộc
lớp P.
Chú ý:
 Khơng phải mọi bài tốn thuộc lớp P đã có thuật tốn hiệu quả.
 Nếu bài tốn khơng thuộc lớp P thì đều phải trả giá rất đắt về thời gian
hoặc thậm chí khơng giải được nó trong thực tế.
2.4.2

Lớp NP

 Thuật tốn khơng đơn định (nondeterministic algorithm): là thuật tốn có kết
quả khơng phải là một giá trị duy nhất mà là một tập hợp hữu hạn các giá trị.

 Định nghĩa Là lớp các bài tốn có thể giải được bằng thuật tốn khơng đơn
định trong thời gian đa thức. Hay, là lớp các bài tốn mà mọi nghiệm giả định đều
có thể được kiểm chứng trong thời gian đa thức (Nondeterministic polynomial).
Ví dụ: Bài tốn HC (Hamilton cycle)
- Intance: Cho đồ thị vơ hướng G = (V,E)
- Question: Hỏi đồ thị vô hướng G = (V,E) có chu trình Hamilton hay
khơng?
6


P
Sắp xếp
Cây khung bé nhất
Nhân ma trận
Tìm kiếm tuần tự
Đường đi ngắn nhất

2.4.3

NP
Bài tốn cái túi
Bài tốn ba lơ
Bài tốn người du lịch

Mối quan hệ giữa lớp P và lớp NP

Ta có thể thấy một cách trực quan là P  NP. Tuy vậy, cho đến nay người ta
vẫn chưa tìm được một bài tốn thuộc lớp NP nhưng khơng thuộc lớp P. Có nghĩa là
câu hỏi " P = NP?" chưa có lời giải. Mặc dù vậy, nhiều nhà khoa học cho rằng P ≠
NP .

Có lẽ lý do hấp dẫn lý giải tại sao các nhà khoa học ln tin rằng P ≠ NP, đó là
sự tồn tại của một lớp các bài toán trong NP\P được gọi là lớp NP -đầy đủ
NPComplete hay gọn hơn NPC). Lớp này có tính chất gây kinh ngạc rằng, nếu một
bài tốn trong lớp này có thể giải được bởi một thuật tốn đơn định thời gian đa
thức, thì mọi bài toán trong lớp NP cũng giải được bởi một thuật toán đơn định thời
gian tương tự, nghĩa là P = NP (!)
Việc xem xét quan hệ giữa P và NP dẫn đến chúng ta đi đến nghiên cứu lớp
NPC

Hình 2: Minh họa giả thuyết về mối quan hệ giữa các lớp P, NP và NP-đầy đủ
2.4.4

Lớp bài toán NP - khó (NP - hard) và NP - đầy đủ (NP – Complate)

2.4.4.1 Các bài toán quyết định
Định nghĩa: Bài toán quyết định là bài toán mà câu trả lời của nó chỉ là “yes”
hoặc “no” (tương ứng với true/1 hay false/0)
Về ngun tắc mọi bài tốn đều có thể biểu diễn dưới dạng bài tốn quyết
định tương ứng.
Ví dụ về bài tốn quyết định
Ví dụ 1: Bài tốn kiểm tra số nguyên tố
7


- Instance: Cho một số nguyên n>2
- Question: n có phải là số ngun tố hay khơng?
Ví dụ 2: Bài tốn HC (Hamilton cycle)
- Intance: Cho đồ thị vơ hướng G = (V,E)
- Question: Hỏi đồ thị vô hướng G = (V,E) có chu trình Hamilton hay
khơng?

2.4.4.2 Bài tốn NP – Khó (NP – Hard)
Bài tốn A được gọi là NP- khó nếu như tồn tại thuật tốn đa thức để giải bài
tốn A thì kéo theo sự tồn tại thuật toán đa thức để giải mọi bài toán trong NP.
Hay: A là NP – Khó nếu như B  A, với mọi bài toán B  NP
2.4.4.3 Bài toán lớp NPC
2.4.4.3.1 Phép dẫn với thời gian đa thức
Định nghĩa: Cho hai bài toán 1 và 2
1 là lớp các Instance ứng với Yes , 1 =
2 là lớp các Instance ứng với No, 2 =
Phép dẫn thời gian đa thức f biến đổi mỗi dữ kiện 1 thành dữ kiện 2 thoã
mãn:
1. Phép dẫn f được thực hiện trong thời gian đa thức bởi máy Turing
2. f( ) 
f( ) 
Ký hiệu : 1 ∞ 2
Ví dụ:
Instance: n, các thành phố: C = {c1, c2,…cm}, khoảng cách giữa ci, cj là
d(ci, cj)  Z+, B  Z+
Question: Tồn tại hay thỏa : C (1) ,C (2) ,...,C (m) thoã:
∑ (

( )

(

))

(

( )


( ))

2.4.4.3.2 Bài toán lớp NPC
Định nghĩa: Một bài toán thuộc lớp NP mà mọi bài toán thuộc lớp NP khác
đều dẫn được về nó với thời gian đa thức được gọi là bài toán NPC
2.4.4.4

Mối quan hệ giữa P, NP và NP được biểu diễn như hình sau:

8


2.4.5

Một số bài toán NPC
- Bài toán SAT
- Bài toán 3-SAT
- Bài toán Vertex – Cover
- Bài toán Clique
- Bài toán Subset – Sum
- Bài toán Knapsack
- Bài toán Traveling Salesman
- …..

Hình 2.4.4(1) Sơ đồ chứng minh một số bài tốn NPC
Ở nội dung bài này, tơi sẽ trình bày bài tốn 3-CNF SAT
Lơgic mệnh đề
Đầu vào của bài tốn SAT là một công thức Lôgic mệnh đề thường
được biểu diễn dưới dạng chuẩn tắc hội (CNF) hoặc chuẩn tắc tuyển (DNF). Dưới

đây sẽ định nghĩa một công thức Lôgic mệnh đề và các dạng chuẩn tắc tương ứng.
3.

Công thức Lôgic mệnh đề
Một công thức Lôgic mệnh đề được xây dựng từ các biến và các phép
tốn lơgic bao gồm: AND (phép hội), OR (phép tuyển), NOT (phủ định),
IMPLICATION (phép kéo theo). Dưới đây là các khái niệm cơ bản [1]:
 Mệnh đề: Mỗi câu được phát biểu là đúng hay sai được gọi là một mệnh đề.
 Các phép toán trên mệnh đề bao gồm:
 Phép phủ định (  )
 Phép tuyển ( )
 Phép hội ( )
 Phép XOR ()
 Phép kéo theo (  )
 Phép tương đương (  )
 Bảng chân trị đối với các phép toán mệnh đề:
 Bảng giá trị các phép toán mệnh đề
3.1

A
0
0
1

B
0
1
0

AB

0
1
1

AB
0
0
0

AB
0
1
1

9

A B
1
1
0

A B
1
0
0

̅

1
1

0


1

1

1

1

0

1

1

0

3.2

Chuẩn tắc hội CNF
CNF là một tuyển sơ cấp hay hội của hai hay nhiều tuyển sơ cấp. Dạng chuẩn
tắc hội CNF có dạng như sau:
TSC1  …  TSCn
Trong đó TSCi ≡ (P1  …  Pm) với n, m  1 và Pi là các biến Lôgic mệnh đề.
Bất kỳ một công thức Lôgic mệnh đề nào cũng có thể được chuyển đổi thành
cơng thức dạng CNF nhờ các phép biến đổi tương đương như: Luật De Morgan, các
luật phân phối, các phép giao hoán, ….
Dưới đây là một số phép biến đổi tương đương:

* Luật De Morgan
¬(A  B)  ¬A  ¬B
¬(A  B)  ¬A  ¬B
* Tính chất giao hốn của các phép Lơgic
AB
 BA
AB
 BA
* Tính chất kết hợp của các phép Lơgic
(A  B)  C  A  ( B  C)
(A  B)  C  A  ( B  C)
* Tính chất phân phối
A  (B  C)  (A  B )  (A  C)
A  (B  C)  (A  B )  (A  C)
* Biểu diễn phép kéo theo qua các phép Lơgic khác
A  B  ¬A  B
A  B  ¬(¬A  B)
A  B  ¬ B  ¬A
* Biểu diễn phép tương đương qua các phép Lôgic khác
A  B  (A  B)  (B  A)
A B   A  B
3.3

Giải quyết các bài tốn chứng minh logic

3.3.1

Bài tốn chứng mình logic:

3.3.2


Cách giải quyết

Với một cơ sở tri thức (một tập các mệnh đề) KB và một mệnh đề  cần
chứng minh (gọi là một định lý)
Câu hỏi được đặt ra là liệu có tồn tại một thủ tục (suy diễn) có thể giải quyết
được bài toán chứng minh logic, trong một số hữu hạn bước.
Có 3 phương pháp (chứng minh) phổ biến:
 Sử dụng bảng chân lý (Truth-table)
 Áp dụng các luật suy diễn (Inference rules)
 Chuyển về bài tốn chứng minh thỗ mãn (SAT)
10


o Phương
pháp
chứng
(Resolution/Refutation)

minh

bằng

phản

chứng

C. Nội dung
1.


Bài toán SAT

1.1

Lịch sử phát triển của SAT:
Năm 1960, thuật toán Davis-Putnam đƣợc phát triển bởi Martin Davis và
Hilary Putnam. Năm 1962, thuật toán Davis–Putnam–Logemann–Loveland (DPLL)
đƣợc giới thiệu, đây là thuật toán cả tiến của thuật toán Davis-Putnam trƣớc đó.
Năm 1966, thủ tục DPLL với hàm mũ ràng buộc thấp hơn do Tseitin phát triển.
Năm 1971, bài toán NP đầy đủ do Cook phát triển. Năm 1992, thuật tốn tìm kiếm
địa phương GSAT do Selman, Levesque và Mitchell phát triển. Năm 1993, giải
thuật WalkSAT do Kautz và Selman phát triển. Năm 1994, chuyển pha SAT do
Gent và Walsh phát triển. Năm 1998, phƣơng pháp Lagrangian rời rạc( DLM) do
Shang và Wah phát triển. Từ năm 2002 trở đi, các cuộc thi đấu SAT được tổ chức .
Cuộc thi tập hợp một số kỹ thuật để thi đấu SAT như : learning, unlearning,
backjumping, watched literal, special
heuristics...
1.2

Bài toán SAT
Bài toán SAT là một bài toán trong khoa học máy tính nhằm kiểm tra tính
thỏa mãn (SAT - Satisfiability) hay không thỏa mãn (UNSAT – Unsatisfiability) của
một công thức mệnh đề Logic. Bài toán SAT là bài toán được chứng minh thuộc lớp
NP - đầy đủ (NP - Complete), các bài toán khác muốn chứng minh thuộc lớp NP –
đầy đủ có thể giản lược vấn đề về bài tốn SAT.
SAT (Satisfiability). Cho một biểu thức logic φ(n,m) gồm n biến x1,x2,…,
…,xn có dạng là hội (conjuction) của m mệnh đề (clause) C1,C2,…,Cm,

C1 ∧ C2 ∧ … ∧ Cm


Trong đó mỗi mệnh đề Ci lại là tuyển (disjunction) của các literal. Mỗi literal
là một biến xj hoặc phủ định của nó ̅ j. Một phép gán (assigment) của φ(n,m) là một
cách gán cho mỗi biến xi một giá trị True hoặc False. Giá trị của một phép gán là giá
trị của biểu thức (True hoặc False) khi ta thay giá trị tương ứng của biến vào biểu
thức. Xác định xem có tồn tại hay khơng một phép gán của biểu thức φ(n,m) có giá
trị True.
Một cơng thức Φ là satisfiable (thỏa mãn được )nếu có một phép gán giá trị để
giá trị ra của Φ là 1.
SAT = {<Φ>: Φ là một công thức thỏa mãn được}
Một công thức Lôgic mệnh đề là SAT khi tồn tại một bộ giá trị true hoặc false
trên các biến Lôgic mệnh đề làm cho công thức nhận giá trị true. Ngược lại công
thức đó là UNSAT khi và chỉ khi mọi bộ giá trị true hoặc false của biến Lôgic mệnh
đề luôn làm cho cơng thức có giá trị là false.
Ví dụ 1.1: Ví dụ về cơng thức SAT:
11


Cho công thức Lôgic mệnh đề: F = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x3)
trong đó x1, x2, x3 là các biến Lôgic mệnh đề.
Công thức F là SAT vì với bộ giá trị x1 = true, x2 = false và x3 = true thì
F cho kết quả true.
Ví dụ 1.2: Ví dụ về cơng thức UNSAT:
Cho cơng thức Lơgic mệnh đề: F = (¬x1∨ x1 ∨ ¬x2) ∧ (x1 ∨¬ x3) ∧ (x1 ∨ x2)
trong đó x1, x2, x3 là các biến Lơgic mệnh đề.
Cơng thức F là UNSAT vì với mọi bộ giá trị thì F ln cho kết quả false.
1.3

Bài tốn CNF-SAT
Mơ tả:
- Biến logic nhận một trong hai giá trị: true hoặc false. Kí hiệu a là biến logic,

a là phủ định của a. Nếu a nhận giá trị true thì a nhận giá trị false và ngược lại,
nếu a nhận giá trị false thìa nhận giá trị true. Một tên biến là một biến logic hoặc
phủ định của biến logic (cũng là một biến logic).
- Một mệnh đề là một dãy các tên biến được xen kẽ bới phép toán logic OR (
).
- Một biểu thức logic trong dạng liên kết chuẩn (conjunction nomal form CNF) là một dãy các mệnh đề được kết nối bới phép toán AND ().
ịnh lý Cook:
Bài toán CNF-SAT là NP-đầy đủ
Cần chỉ ra rằng bất kỳ bài toán NP nào (A) cũng dẫn chuyển về CNF-SAT:
- Cần xây dựng ánh xạ T dẫn chuyển input x của bài toán A về một biểu thức
logic.
- Lời giải của bài toán quyết định A trùng với giá trị true hoặc false của CNFSAT.
Bài toán CNF-SAT là NP-đầy đủ

1.4

Bài tốn chứng minh thỏa mãn (SAT):
Mục đích của bài toán chứng minh thỏa mãn (Satisfiability – SAT-Problem)
là xác định biểu thức ở dạng chuẩn kết hợp (CNF) có thể thỏa mãn được hay không?
Tức là chứng minh biểu thức đó đúng hay khơng?
1.5
1.5.1

Giải quyết bài tốn SAT
Phương pháp acktracking

Áp dụng chiến lược tìm kiếm theo chiều sâu (Depth-first-search)
12



Xét một biến (một định đề đơn), xét các khả năng gán giá trị (True/False) cho
biến đó.
Lặp lại, cho đến khi tất cả các biến được gán giá trị, hoặc việc gán giá trị cho
tập con của tập tất cả các biến làm cho biểu thức là False.
Thuật toán quay lui:
//Thủ tục thử cho xi nhận lần lượt các giá trị mà nó có thể nhận
procedure Try (i: Integer);
begin
for (mọi giá trị V có thể gán cho xi) do
begin
<Thử cho xi := V>;
if (xi là phần tử cuối cùng trong cấu hình) then
<Thơng báo cấu hình tìm được>
else
begin
<Ghi nhận việc cho xi nhận giá trị V (Nếu cần)>;
Try(i + 1);
//Gọi đệ qui để chọn tiếp xi + 1
<Nếu cần, bỏ ghi nhận việc thử xi := V, để thử giá trị khác>;
end;
end;
end;
1.5.2

Các phương pháp tối ưu hoá lặp (Iterative optimization methods)

 Bắt đầu với một phép gán ngẫu nhiên các giá trị True/False cho các ký hiệu
định đề.
 Đổi các giá trị (True thành False/ False thành True) đối với một biến.
 Heuristic: Ưu tiên các phép gán giá trị làm cho nhiều mệnh đề (hơn) đúng

 Sử dụng các phương pháp tìm kiếm cục bộ: Simulated Annealing, WalkSAT
2.

Bài tốn 3-CNF SAT.

ịnh nghĩa
 Phân biệt biến (variables) và literals:
 Mỗi biến xi có 2 literals tương ứng là xi và phủ của nó ̅ .
 Nếu xi được gán giá trị False thì literal xi sẽ có giá trị False cịn literal ̅ . sẽ
có giá trị True.
 Bài tốn 3-CNF SAT được phát biều dưới dạng biểu thức quyết định như
sau:
 Một công thức boolean là một dạng 3-CNF nếu mỗi clause của nó có đúng 3
literal khác nhau.
 3-CNF-SAT={Ф Є 3-CNF và là cơng thức thoả mãn được}
Ví dụ: C = { 
 ,

 ̅̅̅}
2.1

13


Một mệnh đề (clause) của 3-CNF Sat có giá trị True khi và chỉ khi ít nhất 1
literal trong mệnh đề đó có giá trị True, mặc dù tất cả các biến trong mệnh đề đó có
thể nhận giá trị False.
ịnh lý: 3-CNF-SAT Є NP-đầy đủ
Ứng dụng bài toán 3 - SAT
Cho một cơng thức logic có dạng:

( ¬x1 ∨ ¬x3 ∨ ¬x4 ) ∧ ( x2 ∨ x3 ∨ ¬x4 ) ∧ ( x1 ∨ ¬x2 ∨ x4 ) ∧ ( x1 ∨ x3 ∨ x4 ) ∧
( ¬x1 ∨ x2 ∨ ¬x3 )
Với các biến xi là các biến logic ( TRUE or FALSE)
Xác định xem có tồn tại một phép gán các trị logic vào các biến logic sao cho
tồn cơng thức trở thành TRUE.
 Quy ước:
- Mỗi literal logic được biểu diễn dưới dạng một số nguyên dương hoặc âm,
trong đó i và -i tương ứng với xi và ¬ xi , tương ứng.
- Mỗi mệnh đề trong biểu thức được biểu diễn như một bộ mã hóa các ký tự
Ví dụ, (-1, 2, -3) đại diện cho sự phân tách (¬ x 1 ∨ x 2 ∨ ¬ x 3 ).
- Tồn bộ biểu thức kết nghĩa là một danh sách các bộ dữ liệu như vậy.
Ví dụ, biểu thức trên sẽ có mã hóa:
[(-1, -3, -4), (2, 3, -4), (1, -2, 4), (1, 3, 4), (-1, 2, -3)]
Phân tích: Thuật tốn solve_sat
Hàm này sẽ trả về None nếu nó khơng thể tìm thấy một phép gán thỗ mãn.
Đối với mỗi biến logic xi, có một biến cấu trúc biểu diễn cả phần âm và phần
dương xi và ¬ xi
Coi như tổng của nó cho ra kết quả cuối cùng là 1. Mệnh đề là True.
 Cài đặt
2.2

def solve_sat(expression):
if len(expression)==0: return [] # Trivial case. Otherwise count vars.
numvars = max([max([abs(v) for v in clause]) for clause in expression])
lp = glpk.LPX()
# Construct an empty linear program .
glpk.env.term_on = False
# Stop the annoying output.
lp.cols.add(2*numvars)
# As many columns as there are literals.

for col in lp.cols:
# Literal must be between false and true.
col.bounds = 0.0, 1.0
def lit2col(lit):
# Function to compute column index.
return [2*(-lit)-1,2*lit-2][lit>0]
for i in xrange(1, numvars+1):
# Ensure "oppositeness" of literals.
lp.rows.add(1)
lp.rows[-1].matrix = [(lit2col(i), 1.0), (lit2col(-i), 1.0)]
lp.rows[-1].bounds = 1.0
# Must sum to exactly 1.
for clause in expression:
# Ensure "trueness" of each clause.
lp.rows.add(1)
lp.rows[-1].matrix = [(lit2col(lit), 1.0) for lit in clause]
lp.rows[-1].bounds = 1, None # At least one literal must be true.
retval = lp.simplex()
# Try to solve the relaxed problem.
assert retval == None
# Should not fail in this fashion.
if lp.status!='opt': return None # If no relaxed solution, no exact sol.
for col in lp.cols:

14


col.kind = int
retval = lp.integer()
# Try to solve this integer problem.

assert retval == None
# Should not fail in this fashion.
if lp.status != 'opt': return None
return [col.value > 0.99 for col in lp.cols[::2]]

 Ví dụ chạy
Vì vậy, làm thế nào để làm việc này? Hãy nhớ lại công thức CNF của chúng:
(¬ x 1 ∨ ¬ x 3 ∨ ¬ x 4 ) ∧ ( x 2 ∨ x 3 ∨ ¬ x 4 ) ∧ ( x 1 ∨ ¬ x 2 ∨ x 4 ) ∧ ( x 1 ∨ x 3 ∨ x 4 ) ∧
(¬x1∨x2∨¬x3)
Điều này có mã hóa [(-1, -3, -4), (2, 3, -4), (1, -2, 4), (1, 3, 4), (-1, 2, -3)]
Giả sử chúng ta chạy điều này trong trình Python của chúng ta.
exp = [(-1, -3, -4), (2, 3, -4), (1, -2, 4), (1, 3, 4), (-1, 2, -3)]
print resolve_sat (exp)

Kết quả được xuất ra: [True, True, False, False]
Vì vậy, x1 = T, x2 = T, x3 = F và x4 = F.
Kiểm tra lại ta có mệnh đề đầu tiên và thứ hai là đúng vì ¬ x 4 . Các mệnh đề thứ
ba và thứ tư là đúng vì x 1 . Mệnh đề thứ năm (cuối cùng) là đúng vì x2 .
2.3
2.3.1

Thuật toán DPLL giải quyết các bài toán SAT
Lịch sử

DPLL = Davis-Putnam-Logemann-Loveland.
Bài báo đầu tiên (Davis và Putnam) năm 1960: memory problems – vấn đề về
bộ nhớ
Bài báo thứ hai (Davis, Logemann và Loveland) vào năm 1962: Depth-firstsearch with backtracking – duyệt theo chiều sâu
Những cải tiến của những năm 90 và đầu những năm 90 làm cho DPLL hiệu
quả.


Thuật tốn được chính thức đưa vào làm việc trong GRASP. SATO và hệ
thống Relsat, những cải tiến
2.3.2

Giải thuật DPLL

Kiểm tra tính thoả được của cơng thức Logic ở dạng chuẩn CNF
Liệt kê mơ hình với một số Heuristics:
i. Kết thức sớm:
Mệnh đề đúng nếu có bất kì literal là đúng
Mệnh đề sai nếu tất cả các literal là sai
ii. Mệnh đề nhất quán: luôn xuất hiện cũng dấu trong mọi mệnh đề
15


Ví dụ: (A  B), (B  C), (C  A), A và B là nhất quán, C là không nhất
quán.
Cho mệnh đề nhất quán bằng True
iii. Câu đơn vị:
Câu đơn vị: câu chỉ có một literal
Literal trong câu đó phải bằng True
2.3.3

ài đặt giải thuật

D. Kết luận
Có rằng nhiều cách khác nhau tồn tại để giải quyết 3-CNF SAT. Từ tìm kiếm khơng
gian của định giá, để xây dựng toàn bộ giải pháp thiết lập để chứng minh thỏa mãn
bằng cách thao tác công thức. Ở phạm vi của bài này tơi chỉ giới thiệu bài tốn 3 CNF

SAT và thuật toán DPLL.
E. Tài liệu tham khảo
1. Bài tập lớn phân tích và thiết kế thuật giải _ Thái Trung Tín _ Trường ĐH
Tơn Đức Thắng _ 2017
/>2.
3. A new algorithm for Solving 3-CNF-SAT problem, Belal Qasemi, University of
Bonab, Bonab, Iran.
4. A Polynomial Algorithm for 3-sat, M Angela Weiss - Draft Version,
, Universidade de S˜ao Paulo, S˜ao Paulo - Brasil

16