Transcription
Math 42, Discrete MathematicsFall 2018Richard P. KubelkaSan Jose State Universitylast updated 09/20/2018 at 17:00:17For use by students in this class only; all rights reserved.Note: some prose & some tables are taken directly from Kenneth R. Rosen, DiscreteMathematics and Its Applications, 8th Ed., the o cial text adopted for this course.c
Maximize Your Chance of Success in this CourseMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityIGet enough sleep! Studies have shown that sleepquantity and sleep quality equal or outrank such popularPreliminariesPropositionalLogicstudent grades and a student's chances of graduating."Applications ofPropositionalLogicSee An Underappreciated Key to College Success:PropositionalEquivalencescampus concerns as alcohol and drug use in predictingPredicates &Quanti ersSleep," New York Times, August 14, dQuanti p.Rules ofhtmlInferenceIntroduction toProofsc R. P. Kubelka
Maximize Your Chance of Success in this CourseITurn o your smartphone when you come to class.IIIRecent research has shown that use of smartphones orlaptops in the classroom for purposes unrelated to thecurrent class e.g., not for taking notes or photos ofthe whiteboard lead to signi cantly lower performanceon the course nal exam.Moreover, this e ect is seen not just for the studentswho are using such devices, but for all the students inthe class presumably because such devices constitute adistraction for everyone.Furthermore, the adverse e ect on academicperformance seems to be greater for weaker students,students who don't need any additional obstacles tolearning.Moral of the story:Facebook, Twitter, and sportsscores can wait till after class!c R. P. KubelkaMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs
Maximize Your Chance of Success in this CourseI Arnold L. Glass & Mengxue Kang (2018): Dividingattention in the classroom reduces exam performance,"Educational Psychology, 0.1080/01443410.2018.1489046I Louis-Philippe Beland & Richard Murphy (2015): IIICommunication: Technology, Distraction & StudentPerformance," CEP Discussion Paper No 1350, Centrefor Economic Performance, London School of Economicsand Political dfI Brian Heaton (2015): Increased Smartphone UseEquals Lower GPA Among College Students," Center forDigital EducationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction tmlc R. P. Kubelka
A Tip on Reading a Math BookMath 42,DiscreteMathematicsThe most important things to look for are the de nitions.I De nitions are key in understanding and using theunderlying mathematicsI You can't prove that something is a glorp if you don'tRichard P.KubelkaSan Jose StateUniversityPreliminariesPropositionalLogicknow what a glorp is.Applications ofPropositionalLogicDe nitions may appear explicitly like:De nitionA yeti is a legendary large, hairy, humanoid creature said toinhabit the Himalayas. It is also referred to as an AbominablePropositionalEquivalencesPredicates &Quanti ersSnowman.NestedQuanti ersOr they may be implicit or embedded, like:Rules ofInferenceWhen stalking Big Foot, also known by its NativeAmerican nameSasquatch, you should avoid usinginsect repellent, as Big Foot has a keen sense ofsmell.[Note that the boldface term is de ned bythe sentence containing it.]c R. P. KubelkaIntroduction toProofs
Math 42,DiscreteMathematicsDe nitionA proposition is a declarative sentence i.e., a sentence thatdeclares a fact that is either true or false, but not both.Thetruth value of a true proposition is true, denoted by T;The truth value of a false proposition is false, denoted by F.Examples100 C."PreliminariesPropositionalLogicApplications ofPropositionalLogicPropositionalEquivalences1. I was born in California." Truth value T.2. Water boils atRichard P.KubelkaSan Jose StateUniversityPredicates &Quanti ersTruth value T.3. I am enrolled in Math 42." Truth value F.NestedQuanti ers4. I have travelled to all 50 states." Truth value F.Rules ofInference5. All humans are mortal." Truth value T.Introduction toProofsc R. P. Kubelka
Math 42,DiscreteMathematicsRemarksI We should take care in stating propositions anddetermining their truth values. Some propositions areabsolutely true or false, e.g., I was born in California."But the truth value of some propositions may depend ontime or other conditions, e.g., I am enrolled in Math42," Water boils at100 C,"or My blood pressure istoo high."I We should also be as precise as possible when stating propositions. Water boils at 150 C" is anotherproposition with truth value T, since water will boil at any temperature greater than 100 C, its boiling point.A more precise statement than Example 2 above wouldbe The boiling point of water is100 C."c R. P. KubelkaRichard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs
Math 42,DiscreteMathematicsExamples (Declarative Sentences But Not Propositions)1. Colorless green ideas sleep furiously."Preliminaries2. The police were ordered to stop drinking afterPropositionalLogicmidnight."Applications ofPropositionalLogic3. I am lying."4.Richard P.KubelkaSan Jose StateUniversityx2 y2 z2 .PropositionalEquivalencesThe rst three of these statements are famous examplesillustrating various problems we can encounter whenPredicates &Quanti ersexamining declarative sentences, e.g., lack of meaning,NestedQuanti ersambiguity, paradox.Rules ofInferenceIntroduction toProofsc R. P. Kubelka
Math 42,DiscreteMathematicsTo simplify matters, we will denote speci c propositions byusingpropositional variables such as p, q, r, s, etc.This isespecially useful when we modify or combine propositionsintocompound propositions.De nitionLetpbe a proposition. Thenegation of p, denoted by p,is the statement It is not the case thatThe proposition pis read nottruth value from that ofp"p."and it has the oppositep.Richard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
NegationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityRemarkWe usually use more conventional English to express thenegation of a proposition than simply adding It is not thePropositionalLogicApplications ofPropositionalLogiccase that" to the front.Examples1. I wasn't born in California" instead of It is not the case2. I haven't travelled to all 50 states." instead of It is notthe case that I have travelled to all 50 states."100 C" instead at 100 C."3. Water doesn't boil atPropositionalEquivalencesPredicates &Quanti ersthat I was born in California."case that water boilsPreliminariesof It is not thec R. P. KubelkaNestedQuanti ersRules ofInferenceIntroduction toProofs
Math 42,DiscreteMathematicsBut some negations of propositions can be problematical:ExampleIf we try to negate the statementPreliminariesp, I got eight hours ofsleep last night," by saying I didn't get eight hours of sleeplast night" that gives the impression that I got less thaneight hours of sleep. But maybe I actually got nine hours ofsleep. If that were the case, then pwould actually be true.This kind of situation is very important in a part of statisticscalledRichard P.KubelkaSan Jose StateUniversityhypothesis testing.PropositionalLogicApplications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Truth TablesMath 42,DiscreteMathematicsIn dealing with compound propositions, we will often employtruth tables, tables that show the truth values of modi edor compound propositions relative to the truth values of thePreliminariescomponent propositions.Table 1: Truth Table for the Negation of a Propositionp pTFFTApplications ofPropositionalLogicPredicates &Quanti ersNestedQuanti erspis a proposition, then pis aproposition. So that means we can form the proposition ( rkAs we've just seen, ifRichard P.KubelkaSan Jose StateUniversityusually written p. It is not the case that it is notthe case that . . . " As we will see when we discussequivalence of propositions, pis equivalent top.c R. P. KubelkaRules ofInferenceIntroduction toProofs
ConjunctionMath 42,DiscreteMathematicsDe nitionq be propositions. The conjunction of p and q,p q, is the proposition p and q." Theconjunction p q is true when both p and q are true andLetpandRichard P.KubelkaSan Jose StateUniversitydenoted byPreliminariesfalse otherwise.Applications ofPropositionalLogicTable 2: Truth Table for the Conjunction of Two encesPredicates &Quanti erspqp qTTTTFFRules ofInferenceFTFFFFIntroduction toProofsNestedQuanti ersc R. P. Kubelka
ConjunctionMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityExamples1.2.p, I was born in California," q, Water boils at 100 C,"p q: I was born in California, and water boils at100 C." p q has truth value T.p, I was born in California,"50 states,"p r:r, I have travelled to all I was born in California, and I havetravelled to all 50 states."p rhas truth value F, sinceI haven't travelled to all 50 states.3. My brother played football in high school, but I ranPreliminariesPropositionalLogicApplications cates &Quanti ersNestedQuanti erstrack and cross-country." (Note that but" functions asRules ofInference and" here.)Introduction toProofsc R. P. Kubelka
DisjunctionMath 42,DiscreteMathematicsDe nitionq be propositions. The disjunction of p and q,denoted by p q, is the proposition p or q." Thedisjunction p q is false when both p and q are false andLetpandRichard P.KubelkaSan Jose ications ofPropositionalLogictrue otherwise.Table 3: Truth Table for the Disjunction of Two Propositionspqp qTTTTFTFTTFFFPropositionalEquivalencesPredicates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
DisjunctionMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityPreliminariesExamples1.2.p, I was born in California," q, Water boils at 100 C,"p q: I was born in California, or water boils at100 C." p q has truth value T.p, I was born in California,"50 states,"p r:r, I have travelled to all I was born in California, or I havetravelled to all 50 states."p rhas truth value T, sinceI was born in California.PropositionalLogicApplications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Disjunction, Exclusive OrMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityRemarksI Note that disjunction ismeans p, orq,inclusive in that p q reallyor bothpandq."That's why Example1 above has truth value T.I Sometimes we want Or to be explicitly exclusive, i.e., wemean Eitherris true orcase we de ne aSo forr,sis true but not both." In thisconnective called the exclusive or. I will go to the Quakes game tonight,"s, Iwill stay home and do my Math 42 homework tonight,"r s: I will either go to the Quakes game or stay homeand do my Math 42 homework tonight (but not both)."c R. P. KubelkaPreliminariesPropositionalLogicApplications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs
Conjunction vs. DisjunctionMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityFigure 1: Conjunction vs. ions cates &Quanti ersNestedQuanti ersRules ofInferencep qp qIntroduction toProofsc R. P. Kubelka
Exclusive OrMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityTable 4: Truth Table for the Exclusive Or of Two Propositionspqp ations cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
ImplicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityDe nitionp and q be propositions. The conditional statementp q is the proposition If p, then q." The conditionalstatement p q is false when p is true and q is false, andtrue otherwise. In the conditional statement p q, p iscalled the hypothesis (or premise or antecedent) and q isLetcalled theconclusion (or consequence).PropositionalLogicApplications cates &Quanti ersNestedQuanti ersRemarkI The statementPreliminariesp qis called a conditional statementbecause it doesn't assert the truth ofrather only on the condition thatpqabsolutely, butis true.c R. P. KubelkaRules ofInferenceIntroduction toProofs
ImplicationMath 42,DiscreteMathematicsAn implication can be stated in many forms other than thestandard Ifp,thenq."Here are some others:Richard P.KubelkaSan Jose ications cates &Quanti ersOne of the trickiest of these alternative ways of statingp qp q as (Thetruth of ) p implies (the truth of ) q." Hence if p is true, qcannot be false. In other words, (the truth of ) p (ispossible) only if q (is true)."is p only ifq."We can reformulatec R. P. KubelkaNestedQuanti ersRules ofInferenceIntroduction toProofs
ImplicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityExample To get a PhD in math you must have studied math for manyyears."p: You have a PhD in math."math for many years."p q:q: You have studied If you have a PhD in math,then you have studied math for many years." A necessary condition for having a PhD in math is havingstudied math for many years." Note that many years of studyis not enough to get you a PhD in math, i.e., it's not aPreliminariesPropositionalLogicApplications cates &Quanti erssu cient condition for having a PhD in math.NestedQuanti ers A su cient condition for having studied math for manyRules ofInferenceyears is having a PhD in math." Note that having a PhD inmath is not a necessary condition for having studied math formany years. (You could have studied math for many yearswithout having a PhD in math.)c R. P. KubelkaIntroduction toProofs
ImplicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityPreliminariesTable 5: Truth Table for the Implication p qpqp qTTTTFFFTTFFTPropositionalLogicApplications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
ImplicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityPreliminariesPropositionalLogicFor given propositionstranslatep qp, q ,etc., we will need to be able tointo ordinary English. On the other hand,we will need to be able to translate certain compoundpropositions given verbally into symbolic implications.Applications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Math 42,DiscreteMathematicsExamples1.p, I study hard," q, I get a goodp q, If I study hard, then I getgrade in this class":a good grade in thisclass." Or, in less stilted English, If I study hard, I'll geta good grade in this class."2. Nobody is despised who can manage a crocodile." If weletsrbe the proposition I can manage a crocodile," andbe the proposition I am despised," then we canr s. But notetranslate this as s r.translate the given sentence as:we could also plausiblythat3. If I travelled to all 50 states before January 1, 2016, amysterious stranger gave me 1 million." This statementis true because the hypothesis is false.4. If a salesperson says, If you need any help, my name isSasha," what is her name if you don't need any help?c R. P. KubelkaRichard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs
ImplicationMath 42,DiscreteMathematicsFor each implicationp qRichard P.KubelkaSan Jose StateUniversitythere are several relatedimplications. To illustrate these we will use Example 2Preliminariesabove.PropositionalLogicDe nitionI The propositionE.g.,q p:q pis called theconverse of p q. If I have studied math for many years,then I have a PhD in math."I The propositionofp q.E.g., q p is called the contrapositive q p: If I haven't studied mathfor many years, then I don't have a PhD in math." p q is called the inverse of p q: If I don't have a PhD in math,I The propositionp q.E.g.,then I haven't studied math for many years."c R. P. KubelkaApplications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs
Implication, Converse, Contrapositive, InverseMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityPreliminariesPropositionalLogicNote that the contrapositive of the converse is the inverse,and, if we believe that ris equivalent tor,theApplications apositive of the inverse is the converse!Predicates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Implication, Converse, Contrapositive, InverseExampleTranslate the following proposition into symbolic implicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityform, then give its converse, contrapositive, and inverse:Preliminaries Everyone who is sane can do logic."PropositionalLogicI Letpbe the statement You are sane" and letqbe thestatement You can do logic." Then the givenproposition can be translated into the implicationp q:I If you are sane, then you can do logic."Converse (q p): If you can do logic, then you areContrapositive ( q p): If you can't do logic,then you are not sane." (Or, You're insane if you can'tdo logic.")IInverse ( p q):PropositionalEquivalencesPredicates &Quanti ersNestedQuanti erssane."IApplications ofPropositionalLogic If you're not sane, then you can'tdo logic." (Or, Insane people can't do logic.")c R. P. KubelkaRules ofInferenceIntroduction toProofs
Implication, Converse, Contrapositive, InverseExampleTranslate the following proposition into symbolic implicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityform, then give its converse, contrapositive, and inverse: NoPreliminariesone can remember the battle of Waterloo, unless he is veryPropositionalLogicold."I Let r be the statement You are very old" and let s bethe statement You can remember the battle ofWaterloo." Then the given proposition can be translatedinto the implications r: If you can remember thebattle of Waterloo, then you are very old."IIConverse (r s): If you are very old, then you canPropositionalEquivalencesPredicates &Quanti ersNestedQuanti ersremember the battle of Waterloo."Rules ofInferenceContrapositive ( r s):Introduction toProofs If you aren't very old,then you can't remember the battle of Waterloo."IApplications ofPropositionalLogicInverse ( s r): If you can't remember the battleof Waterloo, then you aren't very old."c R. P. Kubelka
Implication, Converse, Contrapositive, InverseMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityTable 6: Truth Table for p q and its Converse, Contrapositive,& Inversepqp qq p q p p lLogicApplications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Math 42,DiscreteMathematicsDe nitionTwo compound propositions with the same componentpropositions are calledequivalent if their truth tables are thesame.Richard P.KubelkaSan Jose ication is equivalent to its contrapositive.Applications ofPropositionalLogicThis fact is what allowed us to translate Example 2 above inPropositionalEquivalencesWe can see from this de nition and Table 5 that anyPredicates &Quanti erstwo di erent but equivalent ways.Since any implication is equivalent to its contrapositive, weconclude that the inverse of an implication is equivalent tothe converse of that implication. (Of course we could havenoted this directly by looking at the table.)c R. P. KubelkaNestedQuanti ersRules ofInferenceIntroduction toProofs
ImplicationMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityThe implication p q.p qis equivalent to the disjunctionWe see this by examining their truth tables:Table 7: Equivalence of p q and p qPreliminariesPropositionalLogicApplications ofPropositionalLogicpqp q p qPropositionalEquivalencesTTTTPredicates &Quanti ersTFFFFTTTNestedQuanti ersFFTTRules ofInferenceIntroduction toProofsc R. P. Kubelka
BiconditionalMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityDe nitionp and q be propositions. The biconditional statementp q is the proposition p if and only if q." Thebiconditional statement p q is true when p and q haveLetthe same truth values, and false otherwise.PropositionalLogicApplications ksp q is equivalent(p only if q)," i.e.,I The biconditional statementconjunction (p ifq)(q p) (p q).ANDI Some other ways of expressing the biconditionalinclude p i Preliminariesq," ifpq, andfor q."thenis necessary and su cientconversely,"to thep qand pc R. P. KubelkaPredicates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs
BiconditionalMath 42,DiscreteMathematicsTable 8: Truth Table for the Biconditional p qpqp qq pp q(q p) (p alLogicApplications cates &Quanti ersExampleConsider the statement A real numberRichard P.KubelkaSan Jose StateUniversityxhas a square root ifx 0." This is a conjunction of the twostatements If x has a square root, then x 0" andx 0, then x has a square root."and only if IfOr: A necessary and su cient condition for a real number tohave a square root is for that number to be nonnegative."c R. P. KubelkaNestedQuanti ersRules ofInferenceIntroduction toProofs
Precedence of Logical OperationsMath 42,DiscreteMathematicsSince a compound proposition might easily involve a numberof logical operators like negation, conjunction, disjunction,etc., it is important to use parentheses to avoid anyambiguity as to which operators apply to which operands. If,however, parentheses are missing, we use the following tableto determine which operators take precedence over others.Table 9: Precedence of Logical OperatorsOperatorPrecedence 1Richard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersRules ofInference23Introduction toProofs45c R. P. Kubelka
Logic & Bit OperationsMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityIn computer science, abit is a symbol with two possiblevalues, viz., 0 (zero) and 1 (one). (Does this sound familiar?)As you probably know, most of computer science comesdown to storing and manipulating bits, i.e., 0's and 1's.Well, if we interpret True as 1 and False as 0, we cantranslate most everything we've done so far withpropositions, connectives and truth tables intooperations and their lications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Logic & Bit OperationsMath 42,DiscreteMathematicsIf we replace T and F by 1 and 0 in the truth table forconjunction ( ) see Table 2 above we get the following:Table 10: Digital Conjunction Table 11: Binary Multiplicationpqp q111100010000 01000101Richard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersNow compare Table 10 with Table 11, the multiplicationtable for binary arithmetic.We see that, except for formatting, the tables are identical.c R. P. KubelkaRules ofInferenceIntroduction toProofs
Logic & Bit OperationsMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityPreliminariesSo conjunction which is called the AND operator instead of in computer science can be used to perform binarymultiplication.Similarly, the exclusive or called XOR instead ofPropositionalLogicApplications ofPropositionalLogicPropositionalEquivalences incomputer science can be used to perform binary addition.Predicates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Logic & Bit OperationsMath 42,DiscreteMathematicsFirst replace T and F by 1 and 0 in the truth table forexclusive or ( ) see Table 4 above to get the following:Table 12: Digital Exclusive Or Table 13: Binary Additionpqp q110101011000 01001110Richard P.KubelkaSan Jose ications cates &Quanti ersNestedQuanti ersNow compare Table 12 with Table 13, the addition table forRules ofInferenceIntroduction toProofsbinary arithmetic.Once again, we see that, except for formatting, the tables areidentical.c R. P. Kubelka
System Speci cationsMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityExamplePreliminariesAre the following system speci cations consistent?1. The system is in multiuser state if and only if it isoperating normally.2. If the system is operating normally, the kernel isPropositionalLogicApplications ioning.3. The kernel is not functioning or the system is ininterrupt mode.4. If the system is not in multiuser state, then it is ininterrupt mode.Predicates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofs5. The system is not in interrupt mode.c R. P. Kubelka
System Speci cationsMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityFirst give names to simple propositions:m: The system is in multiuser state."Preliminariesn: The system is operating normally."PropositionalLogick: The kernel is functioning."Applications ofPropositionalLogici: The system is in interrupt mode."Then translate the system speci cations into compoundPropositionalEquivalencesPredicates &Quanti erspropositions:1.m nNestedQuanti ers2.n kRules ofInference3. k i4. m iIntroduction toProofs5. ic R. P. Kubelka
System Speci cationsMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityConstruct the truth table:Table 14: System Speci cations iPreliminariesPropositionalLogicnki k nti ersFFTFFTTFFFFTTFTTRules ofInferenceFFFFTTTFn k m iApplications icates &Quanti ersIntroduction toProofsc R. P. Kubelka
System Speci cationsMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityNow note that the absolute statements i.e., the statementsthat are not conditional must be true. These are thestatements k iand i,and they are marked in green.But there are only two lines in the truth table for which both k iand iare true so we may disregard all the otherlines. And the truth table tells us that in the rst of theselines the statementstatement m in kmust be false and in the other themust be false. That shows that under noconditions is it possible for all of our speci cations to be truesimultaneously. Thus the system of speci cations ications cates &Quanti ersNestedQuanti ersRules ofInferenceIntroduction toProofsc R. P. Kubelka
Logic PuzzlesMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityPreliminariesExampleSuppose we're given the following assumptions. What can weconclude?1. Every object that is to the right of all the blue objects isabove all the triangles.2. If an object is a circle, then it is to the right of all thePropositionalLogicApplications cates &Quanti ersNestedQuanti ersblue objects.3. If an object is not a circle, then it is not gray.Rules ofInferenceIntroduction toProofsc R. P. Kubelka
Logic PuzzlesMath 42,DiscreteMathematicsRichard P.KubelkaSan Jose StateUniversityFirst give names to simple propositions:r: The object is to the right of all the blue objects."t: The object is above all the triangles."Preliminariesc: The object is a circle."PropositionalLogicApplications ofPropositionalLogicg: The object is gray."PropositionalEquivalencesThen translate the three assumptions into compoundpropositions:1.2.3.Predicates &Quanti ersNestedQuanti ersr tc r c gNote that sinceRules ofInfe
San Jose State University Preliminaries Propositional Logic Applications of Propositional Logic Propositional Equivalences Predicates & Quanti ers Nested Quanti ers Rules of Inference Introduction to Proofs c R. .P Kubelka Disjunction Examples 1. p, I was born in California," q, Water boils at 100 C,"
