計算機科學家邏輯/命題邏輯/語義

定義 3 (命題邏輯的語義)

對於我們命題形式語言的語義，我們不參考特定的意圖解釋。此外，我們只對真值感興趣。我們假設對原子公式的真值的初始賦值，並在此基礎上，我們定義更復雜公式的真值。真值的集合是集合$\{true,false\}$. 對於原子公式集$D$，賦值是一個函式

${\mathcal {A}}|D$$\to \{true,false\}$. 設$E$是包含$D$的公式集，即$E\supseteq D$，並且恰好是那些可以根據語法定義從$D$構造的公式。那麼，${\mathcal {A}}$在$E$上的擴充套件，${\mathcal {A}}_{E}|E\to \{true,false\}$，給出如下

• $A\in D$ : ${\mathcal {A}}_{E}(A)={\mathcal {A}}(A)$

• ${\mathcal {A}}_{E}((F\land G))={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=true{\text{ and }}{\mathcal {A}}_{E}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {A}}_{E}((F\lor G))={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=true{\text{ or }}{\mathcal {A}}_{E}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {A}}_{E}(\lnot F)={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=false\\\;\;\,false&otherwise\end{cases}}$

在下文中，我們將省略索引 $E$ 來指示賦值 ${\mathcal {A}}$ 的擴充套件。請注意，這是將型別為 $(F\land G)$ 的公式命名為合取式，將型別為 $(F\lor G)$ 的公式命名為析取式，將型別為 $\lnot F$ 的公式命名為否定式的正確位置。

以下是透過定義${\mathcal {A}}$進行的示例評估：假定給定${\mathcal {A}}(A)=true,{\text{ }}{\mathcal {A}}(B)=true$ 和 ${\mathcal {A}}(C)=false$，那麼

${\mathcal {A}}(\lnot ((A\land B)\lor C))$

${\text{ }}={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {A}}((((A\land B))\lor C))=false\\\;\;\,false&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))\lor C))=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))))=true{\text{ or }}A(C)=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))))=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}(A)=true{\text{ and }}{\mathcal {A}}(B)=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}=false$

定義 4

令 ${\mathcal {A}}$ 是一個賦值，而 $F$ 是一個公式。 ${\mathcal {A}}$ 被稱為 $F$ 的賦值，如果 ${\mathcal {A}}$ 對 $F$ 的每個子公式都有定義。如果 ${\mathcal {A}}$ 是 $F$ 的賦值，並且 ${\mathcal {A}}(F)=true$，我們稱 ${\mathcal {A}}$ 是 $F$ 的模型，並寫成 ${\mathcal {A}}\models F$ 如果 ${\mathcal {A}}$ 是 $F$ 的賦值，並且 ${\mathcal {A}}(F)=false$，我們寫成 ${\mathcal {A}}\nvDash F$.

一個公式 $F$ 被稱為可滿足的，當且僅當存在一個模型 $F$ ，否則 $F$ 被稱為不可滿足的。 $F$ 被稱為有效的（或為重言式）當且僅當對 $F$ 的每一個賦值都是一個模型。我們寫作 $\models F$ 或者 $\nvDash F$ 。

定理 1

一個公式 $F$ 是有效的，當且僅當 $\lnot F$ 是不可滿足的。

證明： $F$ 是一個重言式

當且僅當對 $F$ 的每一個賦值都是一個模型 $F$

當且僅當對 $F$ 的每一個賦值（當然，這也是對 $\lnot F$ 的賦值）不是模型 $\lnot F$

當且僅當 $\lnot F$ 沒有模型

當且僅當 $\lnot F$ 是不可滿足的。

定義 5 (結論)

如果對於公式 $G$ 和 $F_{1},\cdots ,F_{k}$ 的任何賦值 ${\mathcal {A}}$ 都成立：如果 ${\mathcal {A}}$ 是 $F_{1},\cdots ,F_{k}$ 的模型，那麼 ${\mathcal {A}}$ 也是 $G$ 的模型。我們將這種情況記作 $\{F_{1},\cdots ,F_{k}\}\models G$.

以下定理是定義的一個簡單推論。

定理 2

$G$ 被稱為公式 $F_{1},\cdots ,F_{k}$ 的推論，

當且僅當 $((\bigwedge _{i=1}^{k}~F_{i})\to G)$ 是重言式

當且僅當 $((\bigwedge _{i=1}^{k}~F_{i})\land ~\lnot G)$ 是不可滿足的。

很明顯，一個公式的有效性只取決於其原子子公式的賦值：如果 ${\mathcal {A}}$ 和 ${\mathcal {A}}'$ 是 $F$ 的賦值，並且它們對每個出現的原子子公式都產生相同的值，那麼 ${\mathcal {A}}(F)={\mathcal {A}}'(F)$ 成立。因此，我們可以說，為了檢驗一個公式 $F$ 的有效性，只需要檢驗其原子子公式的無限多個賦值。這種檢驗可以用下表的形式輕鬆地描述出來，其中 $F$ 是一個任意的公式，包含 $n$ 個不同的原子公式 ${\mathcal {A}}_{i}$。

	${\mathcal {A}}_{1}$	$\cdots$	${\mathcal {A}}_{n-1}$	${\mathcal {A}}_{n}$	$F$
${\mathcal {A}}_{1}$	false	$\cdots$	false	false	${\mathcal {A}}_{1}(F)$
${\mathcal {A}}_{2}$	false	$\cdots$	false	true	${\mathcal {A}}_{2}(F)$
${\mathcal {A}}_{2}n$	true	$\cdots$	true	true	${\mathcal {A}}_{n}(F)$

在應用此過程時，引入子公式的中間結果可能會有所幫助，如下面的示例所示。

$A$	$B$	$\lnot A$	$A{\text{ }}\to {\text{ }}B$	($\lnot {\text{ }}A{\text{ }}\to {\text{ }}(A{\text{ }}\to {\text{ }}B$ ))
false	false	true	true	true
false	true	true	true	true
true	false	false	false	true
true	true	false	true	true

請注意，我們只是描述了檢查公式有效性的演算法。假設公式包含 $n$ 個原子子公式，那麼我們剛剛構建的表格將包含 $2^{n}$ 行。為了估計這種指數級演算法的成本，假設計算一行需要 1 微秒。如果 $F$ 僅包含 100 個原子子公式，則計算表格將需要 $2^{100}$ 微秒。

真值表

命題公式是否可滿足的問題稱為 SAT，相應的重言式問題稱為 TAUT。

SAT 是一個 NP 完全問題，因此目前尚不清楚 SAT 是否是易處理的。TAUT 是否屬於 NP 仍然是一個開放問題。對於 TAUT，我們知道，它屬於 NP 當且僅當 NP 在補運算下是封閉的。SAT 和 TAUT 都在複雜性理論研究中發揮著重要作用，特別是在關於 $P=NP$ 的問題方面。

問題

問題 1（命題）

計算以下公式的真值表。確定每個公式是否有效（重言式）、可滿足或不可滿足。

1. $(A\land B)\land (B\to C)$
2. $(A\land B)\leftrightarrow (\lnot A\lor \lnot B)$
3. $(\lnot A\lor \lnot (\lnot B\lor A))\lor A$
4. $(A\to (B\land C))\leftrightarrow ((A\to B)\land (A\to C))$
5. $(A\lor (B\land A))\land ((C\lor \lnot C)\to \lnot A)$
6. $((C\lor B)\land (C\lor \lnot B))\land \lnot C$
7. $\lnot (\lnot A\lor \lnot (\lnot B\lor \lnot A))$
8. $(A\to (B\to A))$
9. $(A\lor (B\land A))\land ((C\lor \lnot C)\to \lnot A)$
10. $((A\lor \lnot B)\lor ((\lnot A\land \lnot C)\land B))\leftrightarrow ((A\lor \lnot C)\lor \lnot B)$
11. $\lnot (A\land \lnot (B\land \lnot C))$

問題 2（命題邏輯）

“你長壽的秘訣是什麼？”有人問一位百歲老人。他回答道：“我嚴格遵守以下飲食規則：如果我晚餐不喝酒，我就總是吃魚。每當我晚餐吃魚和酒，都是不放蒜的。如果我吃蒜或喝酒，我就會避免吃魚”。

1. 用命題邏輯的形式化這些規則。
2. 嘗試簡化這位百歲老人的建議。

問題 3（命題邏輯）

透過對命題公式的構造進行歸納，遞迴地定義以下函式

1. $\alpha (F)$: $F$ 中的原子公式集
2. $\beta (F)$: $F$ 中的二元連線詞 $\land$ 和 $\lor$ 的數量

注意：對於

$F$ = $(\lnot (A\lor B)\lor C)$ $\land$ $((\lnot A\lor B)\land C)$

$\alpha (F)=\{A,B,C\}$ 並且 $\beta (F)=5$ 成立。

問題 4（命題邏輯）

給定公式 $F_{n}$= $A_{1}$ ${\stackrel {\cdot }{\vee }}\cdots {\stackrel {\cdot }{\vee }}A_{n}$, 其中 $A_{1},\dots ,A_{n}$ 是原子公式（$n\geq 1$）其中 ${\stackrel {\cdot }{\vee }}$ 表示異或。證明對於所有的 $n\in \mathbb {N}$: 一個合適的賦值 ${\mathcal {A}}$ 對於 $F_{n}$ 是 $F_{n}$ 的模型（即 ${\mathcal {A}}\models F_{n}$）當且僅當 ${\mathcal {A}}(A_{i})=1$ 對奇數個 ${\mathcal {A}}_{i}$ 成立（$1\leq i\leq n$）。

問題 5（命題邏輯）

在下面，我們研究只包含原子 $A_{1},\dots ,A_{n}$ 的公式。

1. 最多有多少個具有不同真值表的公式？
2. 對於每一個真值表，是否存在一個對應的公式？如果存在，請給出構造方法！

問題 6（命題邏輯）

如果上校在謀殺案發生時不在房間裡，那麼他就無法知道兇手的武器。管家在撒謊，或者他知道兇手是誰。如果巴恩特里夫人是兇手，那麼上校在謀殺案發生時就在房間裡，或者管家在撒謊。管家知道兇手是誰，或者上校在謀殺案發生時不在房間裡。警察得出結論，巴恩特里夫人是兇手。為論證中的每個語句賦予命題變數。將論證寫成一組命題公式，其中包含前提和結論作為命題公式 $F$.

問題 7（命題）

將以下表達式形式化，然後簡化相應的公式和口頭命題。

1. 他的母親不是英國人，而他的父親也不是法國人，這是不正確的。
2. 他正在學習物理，但沒有學習數學，這是不正確的。
3. 工資在下降，而價格在上漲，這是不正確的。
4. 既不冷也不下雨，這是不正確的。

問題 8（命題）

教授建議為大學餐廳的午餐制定一個新的方案。

1. 如果沒有甜點，每頓午餐都必須有面包。
2. 如果供應麵包和甜點，則不供應湯。
3. 如果供應湯，則沒有面包。

幫助管理層滿足教授的願望。為此，

1. 將三個命題形式化（作為蘊含式、析取式/合取式），並將它們組合成一個邏輯公式。
2. 為該邏輯公式提供真值表。該公式是否有模型？
3. 為該任務提供一個口語化的表達。