CS 30: Discrete MathematicsAmit%Chakrabarti%%Logic%and%Logical%Notation%PropositionA%declarative%sentence%that%is%either%true%or%false,%but%not%both.%Examples:%• 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 PropositionOne%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:%%%%Connectives:%if…%then ,%otherwise ,%and %p%=%It%is%sunny%outside % q%=%I%walk%to%work %r%=%I%drive % s%=%It%is%raining %t%=%I%carry%my%umbrella %Compound PropositionIf%it%is%sunny%outside%then%I%walk%to%work;%otherwise%I%drive,%and%if%it%is%raining%then%I%carry%my%umbrella.%%%%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))).%p%=%It%is%sunny%outside % q%=%I%walk%to%work %r%=%I%drive % s%=%It%is%raining %t%=%I%carry%my%umbrella %Logical ConnectivesUsed%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-%Compound Proposition, in SymbolsIf%it%is%sunny%outside%then%I%walk%to%work;%otherwise%I%drive,%and%if%it%is%raining%then%I%carry%my%umbrella.%%%%p%implies%q%and%((not%p)%implies%(r%and%(s%implies%t))).%(p%⇒%q)%∧%(¬p%⇒%(r%∧%(s%⇒%t)))%p%=%It%is%sunny%outside % q%=%I%walk%to%work %r%=%I%drive % s%=%It%is%raining %t%=%I%carry%my%umbrella %Defining a Logical ConnectiveHow%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% fal se%false% true% false%false% fal se% false%Truth Tablep( q( p(∧(q%T% T% T%T% F% F%F% T% F%F% F% F%Pondering Implications%=%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 1It%was%raining%and%I%carried%my%umbrella.%s%is%true,%t%is%true%Pondering Implications%=%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 2It%was%raining%and%I%didn’t%carry%my%umbrella.%s%is%true,%t%is%false%Pondering Implications%=%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 3It%was%not%raining%and%I%carried%my%umbrella.%s%is%false,%t%is%true%Pondering Implications%=%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 4It%was%not%raining%and%I%didn’t%carry%my%umbrella.%s%is%false,%t%is%false%Truth Table for Implicationp( q( p(⇒(q%T% T% T%T% F% F%F% T% T%F% F% T%More Truth Tablesp% 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%Using Logical NotationWe%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 EquivalenceI%claim%that%the%following%two%propositions%are%equivalent,%no%matter%what%p%and%q%represent:%%p%⇒%q %%%%%%and%%%%%%%q%∨%¬p %How%to%verify%this?%%T%T%T%F%F%T%T%T%T%F%F%F%F%F%T%T%T%F%T%T%p(⇒(q(q(∨(¬p(¬p(q(p(PredicateDeclarative%statement%with%variable(s)/unknown(s)%• “x%is%a%perfect%square”%§ where%x%represents%an%integer%• “x%is%even”%§ where%x%represents%an%integer%• “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: PictorialThe%predicate%“x%is%a%perfect%square”%on%the%set%{1,2,3,4,5,6}%564231false%truePredicate: PictorialThe%predicate%“x%is%even”%on%the%set%{1,2,3,4,5,6}%564231false%truePredicate: DefinitionGiven%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%…%???%Digression: Functions with Multiple InputsIf%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.(Predicates to PropositionsTake:%%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?%%QuantifiersSuch%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 QuantifiersLet%P%be%a%predicate%on%Z,%given%by(P(x)%=%“x%is%a%perfect%square”.%%•