Boolean LogicAdministratriviaApplications of Boolean logicBoolean propositionsBoolean variablesIntroduction to Logical OperatorsLogical operators: NotLogical operators: AndLogical operators: OrLogical operators: Exclusive OrInclusive Or versus Exclusive OrLogical operators: Nand and NorLogical operators: Conditional 1Logical operators: Conditional 2Logical operators: Conditional 3Logical operators: Conditional 4Logical operators: Bi-conditional 1Logical operators: Bi-conditional 2Boolean operators summaryPrecedence of operatorsTranslating English SentencesTranslation Example 1Slide 23Slide 24Translation Example 2Slide 26Boolean SearchesBit Operations 1Bit Operations 2&& vs. & in C/C++Slide 32Tautology and ContradictionLogical EquivalenceLogical Equivalences of AndSlide 36Slide 37Logical Equivalences of OrCorollary of the Associative LawLogical Equivalences of NotDeMorgan’s LawYet more equivalencesHow to prove two propositions are equivalent?Using Truth TablesUsing Logical EquivalencesLogical ThinkingCan all of their statements be true?Are all of their statements true? Show values for s, b, and f such that the equation is trueWhat if it weren’t possible to assign such values to s, b, and f?Functional completenessFunctional completeness of NANDSlide 521Boolean LogicCS 202, Spring 2007Epp, sections 1.1 and 1.2Aaron Bloomfield2Administratrivia•HW 1: due next Friday–Section 1.1 # 49, 52–Section 1.2 # 34, 44, 46•Today’s lecture will be somewhat of a review•Next week we will see applications of logic3Applications of Boolean logic•Computer programs•And computer addition•Logic problems•Sudoku4•A proposition is a statement that can be either true or false–“The sky is blue”–“I is a Engineering major”–“x == y”•Not propositions:–“Are you Bob?”–“x := 7”Boolean propositions5•We use Boolean variables to refer to propositions–Usually are lower case letters starting with p (i.e. p, q, r, s, etc.)–A Boolean variable can have one of two values true (T) or false (F)•A proposition can be…–A single variable: p–An operation of multiple variables: p(qr)Boolean variables6Introduction to Logical Operators•About a dozen logical operators–Similar to algebraic operators + * - /•In the following examples,–p = “Today is Friday”–q = “Today is my birthday”7Logical operators: Not•A not operation switches (negates) the truth value•Symbol:  or ~•In C++ and Java, the operand is !p = “Today is not Friday”ppT FF T8Logical operators: And•An and operation is true if both operands are true•Symbol: –It’s like the ‘A’ in And•In C++ and Java, the operand is &&•pq = “Today is Friday and today is my birthday”p qpqT T TT F FF T FF F F9Logical operators: Or•An or operation is true if either operands are true•Symbol: •In C++ and Java, the operand is ||•pq = “Today is Friday or today is my birthday (or possibly both)”p qpqT T TT F TF T TF F F10Logical operators: Exclusive Or•An exclusive or operation is true if one of the operands are true, but false if both are true•Symbol: •Often called XOR•pq  (p  q)  ¬(p  q) •In Java, the operand is ^ (but not in C++)•pq = “Today is Friday or todayis my birthday, but not both”p qpqT T FT F TF T TF F F11Inclusive Or versus Exclusive Or•Do these sentences mean inclusive or exclusive or?–Experience with C++ or Java is required–Lunch includes soup or salad–To enter the country, you need a passport or a driver’s license–Publish or perish12Logical operators: Nand and Nor•The negation of And and Or, respectively•Symbols: | and ↓, respectively–Nand: p|q  ¬(pq)–Nor: p↓q  ¬(pq)p qpq pqp|qpqT T T T F FT F F T T FF T F T T FF F F F T T13Logical operators: Conditional 1•A conditional means “if p then q”•Symbol: •pq = “If today is Friday, then today is my birthday”•p→q  ¬pqp qpq ¬pqT T T TT F F FF T T TF F T Ttheantecedenttheconsequence14Logical operators: Conditional 2•Let p = “I am elected” and q = “I will lower taxes”•I state: p  q = “If I am elected, then I will lower taxes”•Consider all possibilities•Note that if p is false, then the conditional is true regardless of whether q is true or falsep qpqT T TT F FF T TF F T15Logical operators: Conditional 3Conditional Inverse Converse Contra-positivep qp q pq pq qp qpT T F F T T T TT F F T F T T FF T T F T F F TF F T T T T T T16Logical operators: Conditional 4•Alternate ways of stating a conditional:–p implies q–If p, q–p is sufficient for q–q if p–q whenever p–q is necessary for p–p only if qI don’t like this one17Logical operators: Bi-conditional 1•A bi-conditional means “p if and only if q”•Symbol: •Alternatively, it means “(if p then q) and (if q then p)”•pq  pq  qp•Note that a bi-conditional has the opposite truth values of the exclusive orp qpqT T TT F FF T FF F T18Logical operators: Bi-conditional 2•Let p = “You take this class” and q = “You get a grade”•Then pq means “You take this class if and only if you get a grade”•Alternatively, it means “If you take this class, then you get a grade and if you get a grade then you take (took) this class”p qpqT T TT F FF T FF F T19Boolean operators summary•Learn what they mean, don’t just memorize the table!not not and or xor nand nor conditional bi-conditionalp qp  q pq pq pqp|qpq pq pqT T F F T T F F F T TT F F T F T T T F F FF T T F F T T T F T FF F T T F F F T T T T20Precedence of operators•Just as in algebra, operators have precedence–4+3*2 = 4+(3*2), not (4+3)*2•Precedence order (from highest to lowest): ¬   → ↔–The first three are the most important•This means that p  q  ¬r → s ↔ t yields: (p  (q  (¬r))) ↔ (s → t)•Not is always performed before any other operation21Translating English Sentences•Problem:–p = “It is below freezing”–q = “It is snowing”•It is below freezing and it is snowing•It is below freezing but not snowing•It is not below freezing and it is not snowing•It is either snowing or below freezing (or both)•If it is below freezing, it is also snowing•It is either below freezing or