A. 離散數學(謂詞邏輯)
為了研究簡單命題句子內部的邏輯關系,我們需要對簡單命題進行分解,利用個體詞,謂
詞和量詞來描述它們,並研究個體與總體的內在聯系和數量關系,這就是謂詞邏輯或一階邏輯
在原子命題中,可以獨立存在的客體(句子中的主語、賓語等),稱為個體詞。而用以
刻劃客體的性質或客體之間的關系即是謂詞。
個體詞可分為兩種,個體常量和個體變數,均在個體域內取值。
設 D 為非空的個體域,定義
(表示 n 個個體都在個體域 D 上取值) 上取值於{0, 1}上的 n 元
函數,稱為 n 元命題函數或 n 元謂詞,記為P(x1, x2, · · · , xn)。其中,個體變數x1, x2, · · · , xn ∈ D。
1 表示具體性質或關系的謂詞稱為謂詞常量。
2 表示抽象的或泛指的性質或關系的謂詞稱為謂詞變數。
如果王童是一個三好學生,那麼她的學習成績一定很好。
設 S(x):x 是一個三好學生,H(x):x 學習成績好,a:王童,
則該命題符號化為:S(a) → H(a)
李新華是李蘭的父親並且李蘭和張三是同班同學。
設 F(x, y):x 是 y 的父親,M(x, y):x 與 y 是同班同學,b: 李新華,c: 李蘭,d: 張三,
則該命題符號化為:F(b, c) ∧ M(c, d)
全稱量詞 (∀x): 所有的 x;任意的 x;一切的 x;每一個 x;· · ·
存在量詞 (∃x): 有些 x;至少有一個 x;某一些 x;存在 x;· · ·
其中的 x 稱為作用變數。一般將其量詞加在其謂詞之前,記為 (∀x)F(x),(∃x)F(x)。此時,F(x)稱為全稱量詞和存在量詞的轄域。
統一個體域為全總個體域,而對每一個句子中個體變數的變化范圍用一元特性謂詞刻劃之。這種特性謂詞在加入到命題函數中時必定遵循如下原則:
對於全稱量詞 (∀x),刻劃其對應個體域的特性謂詞作為蘊涵式之前件加入。
對於存在量詞 (∃x),刻劃其對應個體域的特性謂詞作為合取式之合取項加入。
若 P(x1, x2, · · · , xn) 是 n 元謂詞,t1,t2, · · · ,tn 是項,則稱 P(t1,t2, · · · ,tn) 為原子謂詞公式,簡稱原子公式。
滿足下列條件的表達式,稱為合式公式(well-formed formulae/wff),簡稱公式。
給定一個合式公式 G,若變元 x 出現在使用變元的量詞的轄域之內,則稱變元 x 的出現為約束出現,此時的變元 x 稱為約束變元。若 x 的出現不是約束出現,則稱它為自由出現,此時的變元 x 稱為自由變元。
設 G 是任意一個公式,若 G 中無自由出現的個體變元,則稱 G 為封閉的合式公式,簡稱閉式。
在命題邏輯里,每一公式都有與之等值的範式,範式是一種統一的表達形式,當研究一個公式的特點 (如永真、永假) 時,範式起著重要作用。對謂詞邏輯的公式來說,也有範式,其中前束範式與原公式是等值的,而其它範式與原公式只有較弱的關系。
B. 離散數學的謂詞是什麼意思
在邏輯學裡面,
通常將一命題里表示思維對象的詞稱為主詞,
將表示對象性質的詞稱為謂詞
C. 離散數學之謂詞邏輯
謂詞邏輯中對命題的解釋更加深入,同時引入謂詞,個體詞,變元等概念,讓命題從靜態化變為動態。
一.謂詞邏輯的基本表示
1.三個基本概念:
個體詞
謂詞
量詞:留意轄域
以函數的觀點看,謂詞決定了映射關系,個體詞與量詞決定了映射對象。
2.命題翻譯:將自然語言用三個部分進行符號化翻譯和它的逆向過程。
3.原子公式與謂詞公式
用聯結詞聯結命題組成的公式。
這時候由於變數增加,我們需要區分好各個變元歸屬的量詞轄區。
公式所有變元的一次實例化稱為解釋。
(命題邏輯中可以通過舉例舉出所有真值,而謂詞邏輯中由於變元的不確定性,有時無法窮舉,需要分析。同時,閉式具有特殊性與更良好的操作性,因為它沒有自由變元)
同時用命題作為變元的實例化得到的是代入實例。
4.等價關系
給出的11個式子主要是在量詞作為參照進行聯結詞的變換。而我們之前在命題邏輯種學過的等價方程依然可以將命題中聯結詞轉化「降維」。
5.範式
前期操作依然與命題邏輯相同,
我們復習一下:
a.消去蘊含與等價聯結詞
b.否定內移
c.內外聯結詞區分
d.特殊*:增加了量詞左移的操作
6.Skolen標准型
在化成前束範式後,我們對每個量詞與其約束的變元分析,逐步消去量詞。
消去規則
a.常量符號(存在量詞,左無全稱量詞)
b.函數符號(存在量詞,左有全稱量詞)
c.變數符號(全稱量詞)
7.引入推理符號
a.引入十一個推理規則式
b.幾個推理過程中消去/增添量詞的規則
US,ES,UG,EG.
c.推導過程逐個變數推導,規則與Skolen標准型化簡過程相似。
8.總結/推導綜合
通過上面的知識,我們可以對一個事實進行詳盡而嚴謹的邏輯推導。
基本都推導規則也是之前知識的靈活運用。這里不再給出一般步驟。
學習知識的過程是螺旋上升的過程,要有找到真理的信心與耐心。這是我學習離散數學的感受,復雜的概念交互下其實是很簡單的邏輯。
2019.3.14