离散证明题集锦.doc

.离散证明题集锦一命题逻辑例：给出(PQ)(PQ)的真值表PQ(PQ) (PQ)00 1 0 1 1 1 101 1 0 1 1 1 010 1 0 1 0 1 111 0 1 1 0 0 0步骤 解：一般说来，n个命题变元组成的命题公式共有2n种真值指派。l 定理1：任何两个重言式的合取或析取，仍然是重言式。 证明：设A、B为两个重言式，则AB和AB的真值分别等于TT和TT。l 定理2：对一个重言式的同一分量都用任何一个命题公式置换，所得命题公式仍为一个重言式。（即代入规则） 证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变。l 定理3：设A、B是两个命题公式，AB当且仅当AB是一个重言式。（前面已证） 证明：若AB，则对于A、B所包含的