Theoretical/Discrete Mathematics - Propositional Phrases and Logical Equivalences
Theoretical/Discrete Mathematics - Propositional Phrases and Logical Equivalences
Popular in Department
This 29 page Class Notes was uploaded by Ishtyaq Ponir on Tuesday September 8, 2015. The Class Notes belongs to at Georgia State University taught by in Summer 2015. Since its upload, it has received 96 views.
Reviews for Theoretical/Discrete Mathematics - Propositional Phrases and Logical Equivalences
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
f Tberoetjczzl Foundations of Computer Science 1 13 Discrete Mathematics and its Applications Ishtyaq Ponir Dr Artsiomenka Quick Little Disclaimer Before We Start Hi how is it going I know you39re not typically used to your notes talking to you when you study but here me out before you decide to get right too it As the author I believe that the best way to learn is by means of interaction and communication so I designed these notes to feel like you were studying with a friend We made sure simplify the notes so it reads in ENGLISH not whatever language our professor is speaking I tried my best to make the notes very straight forward and not intimidating How could it be when my font is Happy Monkey seriously no jokes Just relax and together we can get through this and later go about our lives But for now let39s get started 11 The Basics of Propositional Logic Making sense of 1 s and 0 s Hello again today we will be looking at logic What is logic 0 Essentially it is trying to make sense of something 0 It means to make meaning from mathematical statements in the context of this class 0 When you make up a Li39ect mathematical argument it is called a proof 0 When a mathematical statement is proven to be true it is called a theorem o In computer science the use of logic relates to the construction of circuits computer programs and software systems In the course we39re in we39re looking at logic as it to relates to propositions o A proposition is any statement that can be True 1 or False O The O and 1 are known as truth values Note the methods used for propositions was elaborated by George Boole in the hit classic The Laws of Thought in 1854 just in case this appears on a test Note propositional language is an artificial language we only parallel English to make it easy to use and remember 0 They take the form of a declarative statement a sentence that declares of fact or lack thereof 0 They are the basic building blocks of logic 0 Propositions can be identified using variables such as P Q R or S These are known as propositional variables or statement variables They do to propositions what letters do to denote numerical variables in a mathematic expression basic algebra people When constructing a truth table it is known as a standard to put the variables in order alphabetically which why we did so above The idea of the calculus of propositions basically means creating new propositions from old ones using what are known as logical operators These operators form what are called compound propositions which are taking the old propositions and using logical operators on them It makes them transform into something new 0 Logical operators or basically symbols used to relate one or more statements 0 We use truth tables to chart the propositions that are in question and see their answers when we use a logical operator you39ll be seeing a handful of them as we continue on When constructing a truth table make sure that the number of rows of the truth table corresponds to the number of propositional variables 11 0 Then make the number rows equal to 2 o The operator you use to connect two propositions is known as a connective We say one or more because logical operators are split into two different categories unary and binary o Unary operators or operator are pretty simple because well there s only one of them 0 Unary means quotone value so unary expressions only apply to changing the value of proposition o The only unary operator is P t P called the negation which is denoted by You can thing of I as a negative sign that s because I means the opposite of the truth value you are given for a certain proposition or variable as you ve seen above Next we have the more complex of operators the binary operators 0 The first operator we will P Q 39 3 look at is the conjunction denoted by the symbol tquot tquot This literally translates bquot H bquot to English as and 0 Sometimes quotbutquot is used to signify a conjunction These statements truth values are determined by the two propositions in this case P and Q In order for the resulting compound proposition to be true both the truth values have to be true This is so because of the syntax of the theorem of o Thequotandquot denotes that both have to be true in order for the expression to be true 0 Think of it like thEHH 0 You have a pennyin each hand and your friend which could be me asks you if you have a penny in each hand You can pretend each of your hands with the penny in it is a propositional variable with a certain truth value a penny in the hand for 1 and no penny in your hand for O see what I did there 1 cent vs 0 cents oh forget it It can39t be true if you don39t have any penny in your hand or if you just have one on one TTi Ii Ii d tEI ZEIHJJ hand and one on the other o It can only be true if you have pennies on both hands and in no other case if you are asked if you have pennies in both hands The second operator on our list is called a disjunction otherwise known as the incusIe orj denoted by v The incusIe part of the statement basically means that either one of the truth values in you compound proposition have to be true in order for the result to be true 0 Let39s go back to the penny example 0 Let39s say your friend told youifyou had a pennyin yourhand o The same logic applies if you don39t have any pennies in your hand but if you had a penny in either hand or pennies in both hand it would still be true 0 So even if there is one penny in one hand you still would have 1 cents or 1 True so inherently TJ TJHH U TJH TJHQ meanJED the whole statement would be true 0 The next operator is a different beast the o dreaded exclusive Or denoted by the a or 0 what I like to call the quotJesus Circlequot This statement is called exclusive because you only consider the whole to be true if you have only the truth values to be true to make the whole proposition true 0 Back to the penny example or you know what let39s make it dollars because you deserve a pay upgrade for all your hard work 0 You have one dollar in one hand and nothing in the other 0 This is the only case that an expression with the eXCusfle or can be true you have to have only one truth value that is true anything else is false 0 The next operator is an implication noted by an arrow sign 9 These are also known mma l1nj Ti Z39TEi IiC39 a a rra l a s condl39z l39ona statements This normally follows the syntax quotIf thenquot o It is important to note the same syntax used here applies to coding as well 0 You only execute a program if the initial conditions are true and don39t if they are false This one39s a tough one to understand so after your done reading it take a quick break get a snack maybe rest a little and then continue on my prescription not suggestion The implication basically shows a scenario where you assume something and what the statement will end up being when the truth is compared to it I can39t use pennies or dollars if you were tagging along so I ll use the whether a slight step up from currency 0 Let39s say that it is raining today and yesterday you made an assumption of the weather 0 For the first case let39s pretend it didn t rain and you said it didn t rain you39d be right and so the proposition would be right Let39s say it did rain and you said it would you39d be right so the same logic from the previous assumption applies Let39s say you said it wouldn39t rain and it did It really doesn39t matter what you said it39s still raining and you didn39t hurt anyone with your assumption that it was going to rain Sure there is a logical error but in the world of logic it39s not the end of the world if you said something was nothing was going to happen and it did The next case however does matter If you said it was going to rain and it didn39t then you would be stifled by your piers for being false Unlike the other case where expressed it might not rain so people didn t really pay attention in this case you made a prediction and it was false making your whole argument false 0 Take a minute to sink that in before you go on again my prescription not suggestion o The next subject we have to discuss is terminology This is basically looking at an implication as a premise P as a precedence to the consequence Q P is considered the hypothesis and Q is called the conclusion This dives deeper into why the operator is called a conditional because Q is true in the condition that P holds 0 In an implication Q9P is the CONVERSE of P90 0 Just literally flip them around I don39t know what else to say 0 In an implication Q9P is the CONTRAPOSITIVE of P90 Here you both change the sign of each propositional variable and flip them around Etcl l t 39TEi I39TEi IECII i ZTTDI39lf o In an implication PQ the INVERSE of PQ 0 Remember when two compound propositions always have the same truth value they are equivalent I Remember this for the next section 0 All of these propositions and their inverse contrapositive and converse are equivalent Last but not least is the biconditional denoted with a two headed arrow it might be called something else I don t know lt gt o This is the quotIf and only if or iff for you savvy texters 0 They express that two propositions have the same truth values I PQAQ P o This is why they are known as quot Diimplicationsquot o This basically means what you say you39ll do you39ll do it think of someone who says they39ll do what they said 0 This means that the only way you can be right is if you do what you say If you say you39ll do something and you do it your right I The same for if you say you won39t do something and you don39t do it you re right but shame If you said you won39t do something and you do it you39re wrong because you lied before The same goes for if you say you39d do something and you don39t you still lied so it doesn39t make it true this is a double shame for false hopes The rule regarding the order you quotsolvequot compound propositions is called precedence o It basically goes We39ll be working out truth table with compound propositions in the practice section which will be posted later this week That pretty much covers all the operators now let39s move on to something a little more complex 12 Propositional Equivalence A Fancy Way of Saying Equal Now we will go further in our discussion of propositions specifically how to determine their equivalences The first thing to note are the various definitions for different special cases of propositions They include o Tautology This is a proposition that is always true Take a look at the example 0 o This is a proposition that will always be trie because for the inclusive Or case it doesn39t matter if the two propositions are different truth values they will still be true 0 Contradiction This is a proposition that will always be false Take a look at the example 0 o Contingency o This is a proposition that will always be falj because the only case for the conjunction to be true is if they both of true for each proposition and in this case it will be impossible because the second proposition your considering will always be the opposite of the other one Note IP is considered an entirely different variable than P because of the different truth value that it has and the different nomenclature used to de neit This is a proposition which neither is a tautology or a contradiction Let39s take a look at the example shall we 0 PVQ IR o In this case the possibility of it being true and it being false is entirely possible based on the possibilities for its values o If PVQ is true and IR is false then it will always be false but if PVQ is any other truth value which does not pair up with R being false and is not true it will always be true due to the fact that implications can only be false if the hypothesis is true and the conclusion is false Okay now that we got that out of the way we can talk about logical equivalence 0 Two propositions are logically equivalent if P Q is a tautology is always true 0 We denote logical equivalence with the ltgt symbol 0 All you have to know for logical equivalence is that we use already established laws like DeMorgan39s and Associativity to simplify reduce and rearrange propositions so they equal quotthe other sidequot of the expression This means you replace a statement with another statement with the same truth value Here is a chart with all the quotfamousquot logical equivalences L eal Equit39alenees Equit39 leuee p TEp vaEp puTET pnFEF ptpEp p pip t mEp pvqiqvp p qiq p vmvr3pvmv w rip m pvm iwvm wv p mv 5 v tw mitpvtq twv itp q pvm mip p wvmip par 3915 E T pint 391 EF U E U 3 U E U U 3 U E U 3 U E U H U E Name Identity laws Domination laws Idemp otent laws Double negation law C ommutative laws Associative laws Distributive laws DE Morgan39s laws Absorption laws Negation laws Note equivalent expressions can always be substituted for each other in a more complex expression its wordy but true They still retain the same truth value 0 Also Note stay tuned for the practice when we will actually attempt to work some of these out wish me luck I ve made sure to add Universal and Existential Propositions next week just in case you needed some time to read through these if you needed a break from physics or if you just don t want to read my notes anymore Anyways Thank you for taking the opportunity to better yourself and to study with me o I hope you stick by me we have a lot more ground to cover 0 Until next time stay classy
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'