复旦大学：《离散数学——代数结构与数理逻辑》PPT课件_24/29

§4-般逻辑系统 定义1817:一个逻L是由下述集合 所组成的系统:元素(称为命题)集P; 函数集v这些函数都是从P到某个值 集W的,称为赋值特别若W>2则称 L为多值逻辑系统);以及对应于P的每 个子集A导出P中元素的有限序列集 (称为由前提A得到的证明)

§4一般逻辑系统 定义18.17:一个逻辑L是由下述集合 所组成的系统：元素(称为命题)集P； 函数集V(这些函数都是从P到某个值 集W的，称为赋值.特别若|W|>2则称 L为多值逻辑系统);以及对应于P的每 个子集A导出P中元素的有限序列集 (称为由前提A得到的证明)

■例如:X上命题演算的逻辑,记为 Prop(X),它是由集合P=P(xX)(X上自由命 题代数),所有的P(X)到Z2同态映射集v 以及满足定义18.13的证明集组成,后者 包含从P(X的每个子集A导出P(X中元素 的有限序列(称为由假设A得到的证明)集

 例如： X 上 命 题 演 算 的 逻 辑 ， 记 为 Prop(X)，它是由集合P=P(X)(X上自由命 题代数)，所有的P(X)到Z2同态映射集V， 以及满足定义18.13的证明集组成，后者 包含从P(X)的每个子集A导出P(X)中元素 的有限序列(称为由假设A得到的证明)集

在逻辑L中,语义蕴含由赋值所定义,记 号APp读成“A语义蕴含p”或称“p是A 的后件”,语法蕴含由证明所定义,记 号Ah读成“A语法蕴含p”或称“p是A的 推导”。若⑦卜p,则称p是的重言式; 若hp,则称p是的定理 定义18.18:如果Ah必有AHp,则称逻辑 工是可靠的( sound)。 定义1819:如果F不是工的定理,则称逻 辑工是协调的( consistent)

 在逻辑L中，语义蕴含由赋值所定义，记 号A╞p读成“A语义蕴含p”或称“ p是A 的后件” ，语法蕴含由证明所定义，记 号A┣p读成“A语法蕴含p”或称“ p是A的 推导” 。若╞p，则称p是L的重言式； 若┣p，则称p是L的定理。  定义18.18:如果A┣p必有A╞p，则称逻辑 L是可靠的(sound)。  定义18.19:如果F不是L的定理，则称逻 辑L是协调的(consistent)

定义1820:如果AF必有AFp,则称逻辑L 是完备的( complete 可缮性和完备性把真值和证明联系起来, 而协调性则是纯语法性质,即任何逻辑都 不会导致矛盾。 ■定义18.21:如果存在一个算法,对逻辑L 的每个命题p,能在有限步内确定p是否为 重言式,则称逻辑L是有效性可判定的。 定义18.22:如果存在一个算法,对逻辑L 的每个命题p,能在有限步内确定p是否为定 理,则称逻辑L是可证明性可判定的

 定义18.20:如果A╞p必有A┣p，则称逻辑L 是完备的(complete)。  可靠性和完备性把真值和证明联系起来， 而协调性则是纯语法性质，即任何逻辑都 不会导致矛盾。  定义18.21:如果存在一个算法，对逻辑L 的每个命题p，能在有限步内确定p是否为 重言式，则称逻辑L是有效性可判定的。  定义18.22:如果存在一个算法，对逻辑L 的每个命题p,能在有限步内确定p是否为定 理，则称逻辑L是可证明性可判定的

95命题演算的性质 定理18.8(可箬性定理):设 ACP(X),PEP(X)。若AFp,则有AFp 简言之:Ded(A)∈con(A)。 证明:设p1pnp是从A推导p的证 明序列,要证明的是p为A的后件。 设v是PX)到2的赋值,且v(A={1}, 施归纳于证明序列长度n n=1,则p=p1,故p∈A∪A,由习题 186知每个公理都是重言式,且 V(A)={1},所以vp)=1

§5 命题演算的性质 定 理 18.8( 可靠性定理 ): 设 AP(X),pP(X)。若A┣p，则有A╞p。 简言之：Ded(A) Con(A)。 证明：设p1 ,…,pn=p是从A推导p的证 明序列，要证明的是p为A的后件。 设v是P(X)到Z2的赋值，且v(A){1}， 施归纳于证明序列长度n。 n=1，则p=p1，故pA∪A，由习题 18.6 知每个公理都是重言式 ， 且 v(A){1}，所以v(p)=1

现假设n>1,且对任何n≤k,若p可从A 用n≤k步证明序列推出,必有AFp 下面就是证明对n=k+1也成立。 pn=p有下述两种情况 n(i)pn∈AUA,因此有v(pn)=1, (对某个jn,有p=P→>Pn,此时 v(p/=v(p1→>pn),由v的同态性质知 v(p=v9)→v(pn),故v(p)=1

 现假设n>1，且对任何nk，若p可从A 用 nk步证明序列推出，必有A╞p。  下面就是证明对n=k+1也成立。  pn=p有下述两种情况:  (i)pnA∪A，因此有v(pn )=1，  (ii)对某个i,j<n，有pi=pj→pn，此时 v(pi )=v(pj→pn )，由v的同态性质知：  v(pi )=v(pj )→v(pn )，故v(pn )=1

推论20.3:(邡调性定理:F不是Prop(X)的 定理

 推论20.3:(协调性定理):F不是Prop(X)的 定理

定义1823:设AcP(X)若F∈Ded(A),则 称A是邡调的。若A是协调的,且对任何 B∈P(X,当B真包含A时,B必定不协调, 则称A是级大协调子集

 定义18.23:设AP(X),若FDed(A)，则 称A是协调的。若A是协调的，且对任何 BP(X)，当B真包含A时，B必定不协调， 则称A是极大协调子集

引理183:设AcP(X),则A是极大协调子 集当且仅当 ()FA,并且 a(i)A=Ded(A),并且 n(i对所有的p∈P(X),或者p∈A或者 p∈A。 证明:(1)A是极大协调子集,则(),(i)和i 成立 (2)若()()和(成立,则A是极大协调子 集

 引理18.3:设AP(X)，则A是极大协调子 集当且仅当  (i)FA，并且  (ii)A=Ded(A)，并且  (iii)对 所有 的 pP(X)， 或 者 pA或者 pA。  证明:(1)A是极大协调子集,则(i),(ii) 和(iii) 成立.  (2) 若(i),(ii)和(iii)成立,则A是极大协调子 集

引理184设A是不协调的,则存在A的有 限子集是不协调的。 引理185:设A是P(X)的协调子集,则A必 被某个极大协调子集所包含。 用构造方法 (1)构造一组协调子集序列Σ和∑ (2)证明∑是协调的 n采用归纳法 (3)证明Σ*是极大协调子集 ■先证Σ*是协调的采用反证法 再证∑*是极大的

 引理18.4:设A是不协调的，则存在A的有 限子集是不协调的。  引理18.5:设A是P(X)的协调子集，则A必 被某个极大协调子集所包含。  用构造方法  (1)构造一组协调子集序列n和*  (2)证明n是协调的  采用归纳法  (3)证明*是极大协调子集  先证*是协调的,采用反证法  再证*是极大的