# DARTMOUTH COSC 030 - 03logic (9 pages)

Previewing pages 1, 2, 3 of 9 page document
View Full Document

## 03logic

Previewing pages 1, 2, 3 of actual document.

View Full Document
View Full Document

## 03logic

52 views

Pages:
9
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Unformatted text preview:

Proposition A declarative sentence that is either true or false but not both Examples CS 30 Discrete Mathematics Amit Chakrabarti Logic and Logical Notation Compound Proposition One that can be broken down into more primitive propositions E g If it is sunny outside then I walk to work otherwise I drive and if it is raining then I carry my umbrella This consists of several primitive propositions p It is sunny outside r I drive t I carry my umbrella q I walk to work s It is raining Connectives if then otherwise and CS 30 is a required course for the CS major The population of New York City is more than 8 000 000 Pigs can Jly Non examples What a beautiful evening Do your homework Compound Proposition If it is sunny outside then I walk to work otherwise I drive and if it is raining then I carry my umbrella p It is sunny outside r I drive t I carry my umbrella q I walk to work s It is raining If p then q otherwise r and if s then t If p then q and if not p then r and if s then t p implies q and not p implies r and s implies t Logical Connectives Compound Proposition in Symbols Used to form compound propositions from primitive ones English name Math name Symbol C C Java and conjuction or disjunction not negation or but not both xor none if then implication none if only if equivalence none If it is sunny outside then I walk to work otherwise I drive and if it is raining then I carry my umbrella p It is sunny outside r I drive t I carry my umbrella q I walk to work s It is raining p implies q and not p implies r and s implies t p q p r s t Defining a Logical Connective How to deJine p q Consider the four possibilities p is true q is true p is true q is false p is false q is true p is false q is false In each case specify the truth value of p q p q p q true true true true false false false true false false false false Truth Table Pondering Implication p q p q T T T T F F F T F F F F s It is raining t I carry my umbrella s t Think of the implication as a promise or a contract if s then I guarantee that t In which of the following situations can I say that I have stood by my contract Situation 1 It was raining and I carried my umbrella s is true t is true Pondering Implication Pondering Implication s It is raining t I carry my umbrella s t Think of the implication as a promise or a contract if s then I guarantee that t In which of the following situations can I say that I have stood by my contract s It is raining t I carry my umbrella s t Think of the implication as a promise or a contract if s then I guarantee that t In which of the following situations can I say that I have stood by my contract Situation 2 It was raining and I didn t carry my umbrella s is true t is false Situation 3 It was not raining and I carried my umbrella s is false t is true Pondering Implication Truth Table for Implication s It is raining t I carry my umbrella s t Think of the implication as a promise or a contract if s then I guarantee that t In which of the following situations can I say that I have stood by my contract Situation 4 It was not raining and I didn t carry my umbrella s is false t is false More Truth Tables p q p q T T T T F F F T T F F T Using Logical Notation p q p q p q p q T T T T T T F F T F F T F T F F F F F T We can rewrite some of our earlier deJinitions and theorems If A B and B A then A B A B B A A B Precedence before We can also say if A B then A B and B A A B A B B A We can combine the two statements above A B B A A B Verifying Logical Equivalence Predicate I claim that the following two propositions are equivalent no matter what p and q represent p q and q p How to verify this Declarative statement with variable s unknown s x is a perfect square where x represents an integer x is even where x represents an integer p q p q p p q T T F T T T F F F F F T T T T F F T T T Predicate Pictorial 1 2 3 4 5 3x y 5 where x and y represent real numbers s has height less than 6 feet where s represents a student in this class To determine truth need value of variable s Predicate Pictorial 1 true false 6 The predicate x is a perfect square on the set 1 2 3 4 5 6 2 3 4 5 true false 6 The predicate x is even on the set 1 2 3 4 5 6 Predicate Definition Given set S a predicate on S is a function P S true false In our earlier examples P1 x x is a perfect square was a predicate on Z P2 s s has height less than 6 feet was a predicate on the set of students in this class P3 x y 3x y 5 was a predicate on Predicates to Propositions Take P x x is a perfect square Plugging in a value for x gives a proposition P 5 5 is a perfect square Two other ways to make propositions from P Is P always true x is a perfect square is that always true for all integers x Is P ever true x is a perfect square is that ever true for any integer x Digression Functions with Multiple Inputs If function f takes two integers as input and produces an integer output then use f Z Z Z Thus f x y really means f x y Recall P3 x y 3x y 5 Thus P3 is a predicate on R R Quantifiers Such propositions come up all the time in mathematics and computer science so we have special notation for them for all there exists These symbols are called quantiJiers These are the two most important symbols to learn in this course Using Quantifiers Let P be a predicate on Z given by P x x is a perfect square P is always true is written as x P x Pronounced for all x P x is called the universal quantiJier P is sometimes true is written as x P x …

View Full Document

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...