北京邮电大学 计算机学院 离散数学 1.1-Propositional logic.ppt

* * College of Computer Science Technology, BUPT Implication（蕴涵） ‘If...then...’: ? Definition: If p and q are statements,the compound statement “if p then q”,denoted p ? q ,is called a conditional statement(条件命题）,or implication. The statement p is called the antecedent (前件）or hypothesis（假设）. The statement q is called the consequent （后件）or conclusion（结论）. The connective if …then is denoted by the symbol ?. Example: P - ‘I am going to town’ Q - ‘It is going to rain’ P ?Q: ‘If I am going to town then it is going to rain.’ * * College of Computer Science Technology, BUPT Implication ‘If...then...’: ? Truth Table: P Q P ? Q 0 0 1 0 1 1 1 0 0 1 1 1 * * College of Computer Science Technology, BUPT Implication ‘If...then...’: ? Equivalent forms: If P, then Q ? P implies Q If P, Q ? P only if Q P is a sufficient condition(充分条件） for Q a sufficient condition for Q is P Q if P ? Q whenever P Q when P ? Q follows from P Q is a necessary condition （必要条件）for P Q unless not P Note: The implication is false only when P is true and Q is false! * * College of Computer Science Technology, BUPT Implication ‘If...then...’: ? There is no causality（因果关系） implied here! ‘If the moon is made of green cheese then I have more money than Bill Gates’ (T) ‘If the moon is made of green cheese then I’m on welfare’ (T) ‘If 1+1=3 then your grandma wears combat boots’ (T) ‘If I’m wealthy then the moon is not made of green cheese.’ (T) ‘If I’m not wealthy then the moon is not made of green cheese.’ (T) * * College of Computer Science Technology, BUPT Terminology P = premise（前提）, hypothesis, antecedent Q = conclusion, consequence More terminology: Q ? P is the CONVERSE（逆） of P ? Q ~Q ? ~P is the CONTRAPOSITIVE （逆反式）of P ? Q ~P ? ~Q is the INVERSE（反式）of P? Q One of these three has the same meaning (same truth table) as p ? q. Can you figure out which? * * College of Computer Science Technology, BUPT How do w