離散數學筆記（1）命題邏輯

文章目錄

• • 1.命題符号化及聯結詞
  • • 基本概念
    • 本節題型
  • 2.命題公式及分類
  • • 基本概念
    • 本節題型

1.命題符号化及聯結詞

基本概念

命題的定義：能夠判斷真假的陳述句稱為命題。

備注：感歎句、疑問句、祈使句和類似于x+y>5之類真值不唯一的句子都不是命題。

真值的真假性：判斷正确的命題的真值為真，被稱為真命題；判斷錯誤的命題的真值為假，被稱為假命題。是以又可以說命題是具有唯一真值的陳述句。常用1表示真命題，0表示假命題。

備注：命題的真假性可能目前是不确定的，但是一定存在且唯一。

簡單命題（原子命題）：不能分解成更簡單的句子的命題被稱為簡單命題。由于簡單命題的真值是确定的，是以也被稱為命題常項或命題常元。

命題符号化：用小寫的英文字母表示簡單命題，被稱為命題符号化。

命題變元：真值可以變化的簡單陳述句被稱為命題變項或命題變元。注意命題變元不是命題。

複合命題：由簡單命題用聯結詞聯結而成的命題被稱為複合命題。

聯結詞：

• 否定聯結詞：設p為任一命題。複合命題“非p”稱為p的否定式，記作 ┐p。 ┐為否定聯結詞。
• 合取聯結詞：設p、q為兩個命題。複合命題“p并且q”稱作p和q的合取式，記作p∧q。p∧q為真當且僅當p和q都為真。
• 析取聯結詞：設p、q為兩個命題。複合命題“p或q”稱為p與q的析取式，記作p∨q。∨被稱為析取聯結詞。p∨q為真當且僅當p與q中至少有一個為真。

備注：析取表示的是一種相容性的或運算，并非非此即彼。需要注意在使用排斥或時不能直接用析取式。

• 蘊含聯結詞：設p、q為兩個命題。複合命題“如果p，則q”稱作p與q的蘊含式，記作p→q，稱p為蘊含式的前件，q為蘊含式的後件。→稱作蘊含聯結詞。p→q為假當且僅當p為真且q為假。

p蘊含q的基本邏輯關系是：q是p的必要條件，或p是q的充分條件。

• 等價聯結詞：設p、q為兩個命題。複合命題“p當且僅當q”稱作p和q的等價式，記作p↔q。↔稱為等價聯結詞。p↔為真當且僅當p和q真值相同。

聯結詞的運算優先級：否定＞合取＞析取＞蘊含＞等價。如果有括号需要先計算括号裡的。

本節題型

• 判斷一個句子是否是命題；
• 判斷一個命題屬于簡單命題還是複合命題；
• 将命題符号化（帶有各種聯結詞）；
• 判斷一個命題的真假性（帶有各種聯結關系）；

2.命題公式及分類

基本概念

合項公式（命題公式/公式）的定義：

• 單個命題變項：單個命題變項是合式公式。
• 聯結詞短語：對一個或多個合式公式使用聯結詞進行聯結，所得到的也是合式公式。要求聯結的次數是有限次。
• 1和0：把1看作某個恒取1的公式的縮寫，把0看作某個恒取0的公式的縮寫。

命題公式的層次的定義：

• 若A是單個命題變項，則稱A是0層公式。
• 當B是n層公式，且A=┐B時，A是n+1層公式。
• 當B、C分别是i層和j層公式，且max(i,j)=n。如果A=B∧C或A=B∨C或A=B→C或A=B↔C，則A是n+1層公式。

命題公式的真值：命題公式的真值往往是不确定的，隻有對它的每個命題變項用指定的命題常項代替後，命題公式才會成為命題，其真值此時也會唯一确定。

命題公式的指派：設A是一個命題公式，p1p2…pn為出現在A中的所有的命題變項，給p1,p2…pn指定一組真值，稱為對A的一個指派或解釋。如果指定的一組值使A的值為真，則稱這組值為A的成真複制；若使A的值為假，則稱這組值為A的成假指派。

真值表的概念：将某個命題公式的所有指派情況下的取值列成表，稱為該命題公式的真值表。

構造真值表的步驟：

1. 找出命題公式中所含的所有命題變項p1,p2…pn（如果無下角标就按照字典順序給出）；
2. 按照從低到高的順序寫出各個層次；
3. 列出所有可能的指派。從00…0（n位）開始，每次加一，直到11…1為止。
4. 對應每個指派，計算命題公式各個層次的值，直到最後計算出命題公式的值。

命題公式的分類：

• 重言式（永真式）：在所有指派下取值都為真的命題公式。
• 沖突式（永假式）：在所有指派下取值都為假的命題公式。
• 可滿足式：至少存在一組成真指派的命題公式。

真值函數的概念：一個n(n≥1)階笛卡爾積到{0,1}的函數被稱為一個n元真值函數。

本節題型

• 命題公式的真值判斷；
• 命題公式的類型判斷；