§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( 可靠性定理 ): 设 AP(X),pP(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，故pA∪A，由习题 18.6 知每个公理都是重言式 ， 且 v(A){1}，所以v(p)=1