Boolean LogicQuick surveyBoolean 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 2Slide 14Logical operators: Conditional 3Logical operators: Conditional 4Logical operators: Bi-conditional 1Logical operators: Bi-conditional 2Boolean operators summarySlide 21Precedence of operatorsTranslating English SentencesTranslation Example 2Slide 25Slide 26Translation Example 3Slide 28A bit of humor: Yale vs. HarvardSystem Specifications 1System Specifications 2Slide 32Slide 33Slide 34Boolean SearchesBit Operations 1Bit Operations 2Slide 38&& vs. & in C/C++Slide 40Slide 41Slide 42Today’s demotivators11Boolean LogicBoolean LogicCS/APMA 202, Spring 2005CS/APMA 202, Spring 2005Rosen, section 1.1Rosen, section 1.1Aaron BloomfieldAaron Bloomfield2 Quick surveyQuick surveyHow familiar are you with Boolean How familiar are you with Boolean logic?logic?a)a)A lotA lotb)b)SomeSomec)c)A littleA littled)d)Boolean what?Boolean what?33 A proposition is a statement that can be A proposition is a statement that can be either true or falseeither true or false““The sky is blue”The sky is blue”““I is a English major”I is a English major”““x == y”x == y”Not propositions:Not propositions:““Are you Bob?”Are you Bob?”““x = 7”x = 7”Boolean propositionsBoolean propositions44 We use Boolean variables to refer to We use Boolean variables to refer to propositionspropositionsUsually are lower case letters starting with p Usually are lower case letters starting with p (i.e. (i.e. p, q, r, sp, q, r, s, etc.), etc.)A Boolean variable can have one of two A Boolean variable can have one of two values true (T) or false (F)values true (T) or false (F)A proposition can be…A proposition can be…A single variable: A single variable: ppAn operation of multiple variables: An operation of multiple variables: pp((qqrr))Boolean variablesBoolean variables55 Introduction to Logical OperatorsIntroduction to Logical OperatorsAbout a dozen logical operatorsAbout a dozen logical operatorsSimilar to algebraic operators + * - /Similar to algebraic operators + * - /In the following examples,In the following examples,pp = “Today is Friday” = “Today is Friday”qq = “Today is my birthday” = “Today is my birthday”66 Logical operators: NotLogical operators: NotA not operation switches (negates) the truth valueA not operation switches (negates) the truth valueSymbol: Symbol:  or ~ or ~In C++ and Java, In C++ and Java, the operand is the operand is !!pp = “Today is not Friday” = “Today is not Friday”ppppTTFFFFTT77 Logical operators: AndLogical operators: AndAn and operation is true if both operands are trueAn and operation is true if both operands are trueSymbol: Symbol: It’s like the ‘A’ in AndIt’s like the ‘A’ in AndIn C++ and Java, In C++ and Java, the operand is the operand is &&&&ppqq = “Today is Friday and = “Today is Friday and today is my birthday”today is my birthday”ppqqppqqTTTTTTTTFFFFFFTTFFFFFFFF88 Logical operators: OrLogical operators: OrAn or operation is true if either operands are trueAn or operation is true if either operands are trueSymbol: Symbol: In C++ and Java, In C++ and Java, the operand is the operand is ||||ppqq = “Today is Friday or = “Today is Friday or today is my birthday (or today is my birthday (or possibly both)”possibly both)”ppqqppqqTTTTTTTTFFTTFFTTTTFFFFFF99 Logical operators: Exclusive OrLogical operators: Exclusive OrAn exclusive or operation is true if one of the operands An exclusive or operation is true if one of the operands are true, but false if both are trueare true, but false if both are trueSymbol: Symbol: Often called XOROften called XORppqq  ( (pp  qq) )  ¬( ¬(pp  qq) ) In Java, the operand is In Java, the operand is ^^ (but not in C++)(but not in C++)ppqq = “Today is Friday or today = “Today is Friday or todayis my birthday, but not both”is my birthday, but not both”ppqqppqqTTTTFFTTFFTTFFTTTTFFFFFF1010 Inclusive Or versus Exclusive Inclusive Or versus Exclusive OrOrDo these sentences mean inclusive or Do these sentences mean inclusive or exclusive or?exclusive or?Experience with C++ or Java is requiredExperience with C++ or Java is requiredLunch includes soup or saladLunch includes soup or saladTo enter the country, you need a passport or a To enter the country, you need a passport or a driver’s licensedriver’s licensePublish or perishPublish or perish1111 Logical operators: Nand and NorLogical operators: Nand and NorThe negation of And and Or, respectivelyThe negation of And and Or, respectivelySymbols: | and ↓, respectivelySymbols: | and ↓, respectivelyNand: Nand: pp||qq  ¬( ¬(ppqq))Nor: Nor: pp↓↓qq  ¬( ¬(ppqq))ppqqppqqppqqpp||qqppqqTTTTTTTTFFFFTTFFFFTTTTFFFFTTFFTTTTFFFFFFFFFFTTTT1212 Logical operators: Conditional 1Logical operators: Conditional 1A conditional means “if A conditional means “if pp then then qq””Symbol: Symbol: ppqq = “If today is = “If today is Friday, then today Friday, then today is my birthday”is my birthday”p→q=¬pp→q=¬pqqppqqppqqTTTTTTTTFFFFFFTTTTFFFFTTtheantecedenttheconsequence1313 Logical operators: Conditional 2Logical operators: Conditional 2Let Let pp = “I am elected” and = “I am elected” and qq = “I will lower taxes” = “I will lower taxes”I state: I state: p p  qq = “If I = “If I am elected, then I am elected, then I will lower taxes”will lower taxes”Consider all Consider all possibilitiespossibilitiesNote that if Note that if pp is false, then is false, then the conditional is true regardless of whether the conditional is true regardless of whether qq is is true or falsetrue or falseppqqppqqTTTTTTTTFFFFFFTTTTFFFFTT14 Quick surveyQuick surveyDoes truth table of the conditional Does truth table of the conditional make sense?make sense?a)a)Yes, alreadyYes, alreadyb)b)MostlyMostlyc)c)Not reallyNot