合式公式

合式公式

符号串
命題公式是由命題常項、命題變項、聯結詞、括号等組成的符号串,但不是由這些符号任意組成的符号串都是命題公式。因此,必須給出命題公式的嚴格定義。今後我們将合式公式稱為命題公式,或簡稱為公式。在公式的定義中,引進了A,B等符号,它們代表任意的命題公式,稱它們為元語言符号。[1]例用定義說明是公式。
  • 中文名:合式公式
  • 外文名:well-formed formula
  • 别名:謂詞公式
  • 要求:給出命題公式的嚴格定義
  • 組成:命題常項、命題變項
  • 簡稱:公式
  • 定義:按一定規則構成的表達式

基本内容

若用,…表示真值确定的簡單命題,則稱,…為命題常項,命題常項的真值是确定不變的,不是為1,就是為0。

若用,…泛指簡單的陳述句,則稱,…為命題變項,此時,…是變量,它們的取值為1或0。

定義1.6

(1)單個命題常項或變項是合式公式;

(2)如果A是合式公式,則也是合式公式;

(3)如果A,B是合式公式,則,,,也是合式公式;

(4)隻有有限次地應用(1)~(3)組成的符号串才是合式公式。

為方便起見,規定,等的外層括号可以省去。

根據定義,,,等都是命題公式,但等都不是命題公式。

所謂元語言,是用來說明對象語言的語言,而對象語言是指用來描述所研究的對象(指數理邏輯)的語言。

相關知識

為了使一階邏輯中命題符号化更準确和規範,以便正确進行謂詞演算和推理,引進一階邏輯中合式公式的概念.nn在形式化中,将使用以下四類符号。nn(1)常量符号:,當論域D給出時,它可以是D中的某個元素;nn(2)變量符号:,當論域D給出時,它可以是D中的任何一個元素;nn(3)函數符号::,當論域D給出時,n元函數符号可以是到的任意一個映射;nn(4)謂詞符号:,當論域D給出時,n元謂詞符号可以是到{1,0}的任意一個謂詞。nn定義1一階邏輯中的項(item),被遞歸定義如下:nn(1)常量符号是項;nn(2)變量符号是項;nn(3)若是n元函數符号,是項,則是項;nn(4)隻有有限次地使用(1)、(2)、(3)所生成的符号串才是項。nn例如a,b,x,y是項,,是項,也是項。nn定義2設是n元謂詞,是項,則稱為原子公式,或簡稱原子。

約束變量和自由變量

在一個謂詞公式中.變量的出現是約束的(bound),當且僅當它出現在使用這個變量的量詞作用範圍(稱為作用域)之内;變量的出現是自由的(free),當且僅當它的出現不是約束的;至少有一次約束出現的變量稱為約束變量(bound variable),至少有一次自由出現的變量稱為自由變量(free variable)。

為了避免公式中有些變量既可以約束出現,又可自由出現的情形,我們可采用以下兩條規則。nn改名規則:将謂詞公式中出現的約束變量改為另一個約束變量,這種改名必須在量詞作用域内各處以及該量詞符号中進行,并且改成的新約束變量要有别于改名區域中的所有其他變量。

基本分類

設G是一個謂詞公式,nn(1)如果存在解釋,使在下為真(簡稱滿足),則稱是可滿足的;nn(2)如果所有解釋均不滿足,(簡稱弄假),則稱為恒假的,或不可滿足的;nn(3)如果的所有解釋都滿足,則稱為恒真的。nn如果一階邏輯中的恒真(恒假)公式,要求所有解釋均滿足(弄假)該公式,而解釋依賴一個非空個體集合D,又集合D可以是無窮集合,而集合D的“數目”也可以有無窮多個,因此,所謂公式的“所有”解釋,實際上是很難考慮的,這就使得一階邏輯中公式的恒真、恒假性的判定異常困難。Church和Turing分别于1936年獨立地證明了:對于一階邏輯,判定問題是不可解的,即不存在一個統一的算法A,該算法與謂詞公式無關,使得對一階邏輯中的任何謂詞公式G,A能夠在有限步内判定公式G的類型。nn但是,一階邏輯是半可判定的,即如果謂詞公式G是恒真的,有算法在有限步内檢驗出G的恒真性。

相關詞條

相關搜索

其它詞條