Mathematics for Computer Science

2.4. Factoring into Primes 33 Problem 2.7. In Chapter 2, the Well Ordering was used to show that all positive rational numbers c ...

...

3 Logical Formulas It is amazing that people manage to cope with all the ambiguities in the English language. Here are some sent ...

Chapter 3 Logical Formulas36 3.1 Propositions from Propositions In English, we can modify, combine, and relate propositions with ...

3.1. Propositions from Propositions 37 According to this table, the proposition “PANDQ” is true only whenPandQare both true. Thi ...

Chapter 3 Logical Formulas38 real numberx”. Since the conclusion is definitely true, we’re on either line (tt) or line (ft) of t ...

3.2. Propositional Logic in Computer Programs 39 3.2 Propositional Logic in Computer Programs Propositions and logical connectiv ...

Chapter 3 Logical Formulas40 Now we have the values needed to fill in theANDcolumn: A B A OR .NOT.A/ AND B/ AORB T T F F T T F F ...

3.2. Propositional Logic in Computer Programs 41 easier to read and understand, and can also make it faster since fewer operatio ...

Chapter 3 Logical Formulas42 3.3 Equivalence and Validity 3.3.1 Implications and Contrapositives Do these two sentences say the ...

3.3. Equivalence and Validity 43 If I am grumpy then I am hungry, and if I am hungry then I am grumpy. are equivalent to the sin ...

Chapter 3 Logical Formulas44 the system designer is to come up with a system that follows all the specs. This means that theANDo ...

3.4. The Algebra of Propositions 45 The expression (3.5) is a disjunctive form where eachAND-term is anANDof every oneof the var ...

Chapter 3 Logical Formulas46 that look like the familiar ones for multiplication of numbers: AANDB! BANDA commutativity ofAND (3 ...

3.4. The Algebra of Propositions 47 into disjunctive normal form. We start by applying DeMorgan’s Law forORto (3.20) in order to ...

Chapter 3 Logical Formulas48 Doing the same thing to the otherAND-terms in (3.22) finally gives a disjunctive normal form for (3 ...

3.5. The SAT Problem 49 you: it’s important to realize that using the strategy we gave for applying the ax- ioms involves essent ...

Chapter 3 Logical Formulas50 “Pvs. NP” problem.^1 It is the outstanding unanswered question in theoretical computer science. It ...

3.6. Predicate Formulas 51 Always True For allx 2 D,P.x/is true. For allx 2 R,x^2  0. P.x/is true for everyxin the set,D. x^2  ...

Chapter 3 Logical Formulas52 Let’s write this out in more detail to be precise about the quantification: For every even integern ...