PPT《习题2.3》

习题2.

3

2 设S={G1,…,Gn}是命题公式集合.试求出从S出发演绎出的所有命题公式.解: 设G=G1?…?Gn 的主合取范式G'共有 m个极大项:G= G'=Mi1 ?…? Mim 则S出发的演绎出来的所有命题公式正是从这m个极大项中任取k(0≤k≤m)个合取组成,共有2m个,其中包括恒真公式,这里用1表示(S ? 1) . 例. G1=(P∨Q) ∧(?P∨R), G2=( Q∨R) ,则G1∧G2= (P∨Q) ∧( ? P∨R) ∧ ( Q∨R)P∨Q∨R)∧(P∨Q∨?R)?P∨Q∨R)∧(?P∨?Q∨R)逻辑结果: 24个.如:1,(P∨Q ∨R) , (P∨Q ), (P∨Q ) ∧ ( ? P∨Q ∨R), G1 ∧ G2,…

2 设S={G1,…,Gn}是命题公式集合.试求出从S出发演绎出的所有命题公式. (1)设H为由G中若干极大项构成的合取公式.往证:S?H,即G?H.从定义出发,任取 满足G=G1?…?Gn 的解释I ,则必使G的主合取范式G'=Mi1 ?…? Mim也取1值,即,使每一个极大项都取1值.从而使由G中若干极大项合取组成的公式H也取1值,则S?H.故,H为由从S出发演绎出的命题公式.

2 设S={G1,…,Gn}是命题公式集合.试求出从S出发演绎出的所有命题公式. ?(2)设公式H是S的任意一个逻辑结果,即G ?H.将H写成主合取范式.现在要证组成H的极大 项都在G的主合取范式G'中出现.反证法.若不然,假设H中有一个极大项Mk不在G的主合取范式中.则取使Mk为0的解释I,可有解释I使H= Mk ?…取0值.而I使所有不等于Mk的极大项都为1,则有G' =Mi1 ?…? Mim在I下取1值,即G在I下取1值,这与G ? H矛盾. 5.设G1,…,Gn是公式.证明:从{G1,…,Gn}出发可演绎出公式G的充要条件是从{G1,…,Gn,?G}出发可演绎出公式(R??R).其中R为任意公式.证明: 必要性.若从{G1,…,Gn}出发可演绎出公式G,则G1 ? … ? Gn? G,有(G1?…? Gn)?G恒真,即?(G1?…? Gn)?G恒真,对该式取非有G1?…?Gn??G恒假,故(G1?…? Gn??G)?(R??R)恒真,其中R为任意公式,则(G1?…? Gn??G)?(R??R),即从{G1,…,Gn,?G}出发可演绎出公式(R??R).充分性. 若从{G1,…,Gn,?G}出发可演绎出公式(R??R),则G1?…? Gn??G ?(R??R),因(R??R)恒假,故G1?…? Gn??G恒假,即?(G1?…?Gn)?G恒真,亦即(G1?…?Gn)?G恒真,则有(G1?…? Gn)?G,因此从{G1,…,Gn}出发可演绎出公式G . 8.用演绎法证明题注明演绎中的每个公式的列出所使用的规则,如果使用的是规则2,还需要注明该公式是之前哪些公式的逻辑结果.一个行号对应一个公式,不能在一行内写多个公式,共用一个行号. 习题2.3