Disjunction (OR)
• p: I am going to town. • q: It is raining. • p q: I am going to town or it is raining. • Inclusive or - only one proposition needs to be true for the disjunction to be true.
College of Computer Science and Technology Zhejiang University
Truth table for conjunction
• p q pq
• • • •
T T F F
T F T F
T F F F
College of Computer Science and Technology Zhejiang University
pq qp
– If I am going to town, it is raining.
College of Computer Science and Technology Zhejiang University
Contrapositive of an Implication
• Implication: pq • Contrapositive: q p • Implication:
College of Computer Science and Technology Zhejiang University
Converse of an Implication
• Implication: • Converse: • Implication: • Converse:
– If it is raining, then I am going to town.
p q r means (p q) r, not p (q r) p q r means (p q) r
College of Computer Science and Technology Zhejiang University
Translating English sentence to logical expressions
College of Computer Science and Technology Zhejiang University
Truth table for disjunction
• • • • • • p q pq __________ T T T T F T F T T F F F
College of Computer Science and Technology Zhejiang University
Logic
Section 1.1
College of Computer Science and Technology Zhejiang University
Logic
• Logic is the study of reasoning. It is concerned with whether reasoning is correct. • Logical methods are used in mathematics to prove theorems and in computer science to prove that programs do what they are alleged to do. • The goal of logic is to teach the students how to understand and how to construct correct mathematical arguments. (many applications)
College of Computer Science and Technology Zhejiang University
Biconditional
• “if and only if”, “iff” • pq • I am going to town if and only if it is raining. • Both p and q must have the same truth value for the assertion to be true.
College of Computer Science and Technology Zhejiang University
Logical operators (connectives)
1. Negation (NOT) • p: I am going to town. • ~p: I am not going to town. • Truth table: p ~p T F F T
College of Computer Science and Technology Zhejiang University
2. Conjunction (AND)
• p: I am going to town. • q: It is raining. • p q: I am going to town and it is going to rain. • Both p and q must be true for the conjunction to be true.
Implication - If .. then
• p: I am going to town. • q: It is raining. • p q: If I am going to town, then it is raining. • The implication is false only when p is true and q is false!
Exclusive OR
• p: I am going to town. • q: It is raining. • p q: Either I am going to town or it is raining. • Only one of p and q are true. (not both)
Inverse of an Implication
• Implication: p q • Inverse: p q • Implication:
– If I am going to town, it is raining.
• Inverse:
– If I am not going to town, then it is not raining.
College of Computer Science and Technology Zhejiang University
Propositions
• Statement that is true or false. • We determine the truth value of a proposition. • The moon is made of green cheese. • Go to town. • What time is it? • x + 1 = 2.
q: You will pass the final exam
College of Computer Science and Technology Zhejiang University
Implication - Equivalent Forms
• • • • • • • • If p, then q p implies q If p, q q if p q whenever p p is a sufficient condition for q q is a necessary condition for p p only if q
College of Computer Science and Technology Zhejiang University
Truth table for Exclusive
• • • • • • p q pq __________ T T F T F T F T T F F F
College of Computer Science and Technology Zhejiang UniverT F T F
College of Computer Science and Technology Zhejiang University
Precedence of Logical Operators
• Parentheses gets the highest precedence • Then • Example:
– If I am going to town, it is raining.
• Contrapositive:
– If it is not raining, then I am not going to town.
College of Computer Science and Technology Zhejiang University
College of Computer Science and Technology Zhejiang University
Truth Table Example
• (p q) r
p
T T T T F F F F
q
T T F F T T F F
r
T F T F T F T F
pq
T T T T T T F F
• Natural language is often ambiguous.
College of Computer Science and Technology Zhejiang University