---
tags: 資芽
title: 手寫作業9
---
# 姓名:李緒成

## 1
### $(a)$
* $a = 0, b = 1, c = 0$
### $(b)$
* 無解

## 2
### $(a)$
* 令$f = (l_1 ∨ l_2 ∨ ... ∨ l_{m_{1}}) ∧ (l_1 ∨ l_2 ∨ ... ∨ l_{m_{2}}) ∧ ... ∧ (l_1 ∨ l_2 ∧ ... ∨ l_{m_{n}})$
* 則$¬f = (¬l_1 ∧ ¬l_2 ∧ ... ∧ ¬l_{m_{1}}) ∨ (¬l_1 ∧ ¬l_2 ∧ ... ∧ ¬l_{m_{2}}) ∨ ... ∨ (¬l_1 ∧ ¬l_2 ∧ ... ∧ ¬l_{m_{n}})$

### $(b)$

* 存在，驗證其中一個**子句**為T即可

### $(c)$

* 不存在
* 引理$1$ $(Cook-Levin Theorem) \space CNF-SAT ∈ NPC$
* 引理$2$ $(2-a)f ∈ DNF, 則¬f ∈ CNF$
* 由於一個$DNF$算式取反後可變為$CNF$
* 所以$DNF$可在多項式時間內轉換成NP-hard問題
* 故此題不存在多項式解