信息科学技术学院2003-2004学年第一学期本科生期末考试试卷（数理逻辑）

1.(每题2分,共10分)判断题(若正确,则在题前的括号中打√;否则,打): (a)()若合式公式A是永真式当且仅当合式公式B是永真式,则AB是永真式。 (b)()若合式公式A是可满足的,则~A是不可满足的。 (c)()v((,x)y~(,y)是可满足的 (d)()设P是一个由P系统增加单个合式公式pq作为公理所得到的系统,则P是协调的

Syntax Formation Rules for P The The Axiomatic Structure of P Theorems and Derived Rules

Substitutivity of Equivalence Let A,M and N be wffs and let AMN be the result of replacing M by N at zero or more occurrences (henceforth called designate occurrences) of M in A. 1. AMN is a wff. 2. If |= M ≡ N then |= A ≡ AMN

Axiom Schemata for F Axiom Schema 1 A ∨ A ⊃ A Axiom Schema 2 A ⊃ (B ∨ A) Axiom Schema 3 A ⊃ B ⊃ (C ∨ A ⊃ (B ∨ C)) Axiom Schema 4 ∀xA ⊃ Sxt A where t is a term free for the individual variable x in A Axiom Schema 5 ∀x(A ∨ B) ⊃ (A ∨ ∀xB) provided that x is not free in A

Interpretation An interpretation I of F is , where D is a non-empty set called the domain of individuals. I0 is a mapping defined on the constants of F satisfying 1. If c is an individual constant, then I0(c) ∈ D. 2. If f n is an n-ary function constant, then I0(f n) : Dn → D

Two forms of Completeness Theorem Let Γ be a set of wffs. The following parts are equivalent. If Γ |= A then Γ ` A If Γ is consistent, then Γ is satisfiable

本章是数理逻辑中的最基本内容， 是下一章的基础.本章主要讲述命 题与联结词、命题公式、恒真命 题、等价式、蕴涵式及范式等基 本内容；能将自然语言符号化； 能用等价式、蕴涵式等进行命题 演算和推理；能用逻辑推理的方 法解决一些实际问题

本章是数理逻辑中的最基本内容， 是下一章的基础.本章主要讲述命 题与联结词、命题公式、恒真命 题、等价式、蕴涵式及范式等基 本内容；能将自然语言符号化； 能用等价式、蕴涵式等进行命题 演算和推理；能用逻辑推理的方 法解决一些实际问题

一、 英国人布尔创立 二、 代表着一种因果关系，无所谓大小 三、 0和1的基本逻辑，二进制