Lecture 23

[Music] okay uh let us start so so far we have uh seen that logic is a branch of philosophy as well as mathematics where we study how to reason and we would like to know answers to various questions in mathematics we want to know what is the difference between structure and properties what is the difference between polom polinomial equations solution sets of polinomial polinomial functions those kinds of things what is a theorem what is a theory yeah how a theory differs a theory in mathematics differs from theories in other science areas and um if in order to start that I mean we are going to in this course we are going to look at two different types of Logics the first one is called propositional logic which is the baby version and then we'll study first order logic so the difference between these two Logics is that the propositional logic is logic of connectives so which means you are going to start with some sentences you don't question anything about them except for whether they are true or false and then you construct new sentences out of these existing sentences so these sentences that you begin with you will uh treat them as indestructible atoms yeah I mean atom as an indestructible so you don't go inside that particular sentence you just say whether it is true or false apart from that you don't do anything and in the first order logic however we will try to convey the idea of Truth in a more meaningful way there will be some uh more delicate way of dealing with sentences you will have some quantifiers embedded inside your language right so connectives means and or implies negation those kinds of things simple things and quantifiers means there exist and for all so right now we are not talking about quantifiers we'll only talk about propositional logic which is the logic of connectives so whenever we start with some new area uh be it science or be it mathematics we always have to know what is its terminology right so first of all whenever we are starting with the logic we need to know what is the alphabet so the alphabet of propositional logic consists of two things a language and meta language language is something variable okay it will change according to our I mean in this case we'll say it's a propositional language and meta language on the other hand it is fixed it is coming from The Meta level okay it is fixed and it consists of something simple yeah so this consists of consists of parenthesis yeah parenthesis we don't want to change according to our wish yeah they are always there then conjunction conjunction is a binary connective binary connective means it connects two different things to give one new thing and negation what is the arity of negation as a connective unary one right it's unary connective means uh it just says that this is not true that's our intended meaning so let me write here so binary connective and this one is unary connective actually our language meta language can only consist of these four symbols and we are happy with that however in practice Yeah in practice we will also use these symbols right disjunction then implication and by implication okay let me write down some names so this one is called conjunction then negation then disjunction implication and by implication now you might be wondering that we have seen similar symbols in Boolean algebra okay so what are they called conjunction is meat yeah I mean the same symbol represents meat then negation what do we call it complement very good disjunction what do we call it join implication yeah I mean it's called implication and bi implication those are the same same name now so far what I have not described is the language you understand meta language why it is called meta because we do not want to change yeah so uh for now yeah for a few classes these symbols are not going to be important these two symbols we'll call them basic and these ones we'll call them derived yeah they are derived from the basic symbols can you tell me how disjunction can be derived from Conjunction and negation de demorgan law exactly what is the meaning of uh implication negation A or B correct so that that much you know and what is by implication B plus not plus there is no plus a implies B and B implies a yeah we'll see all these things later but therefore they are derived and we have used this idea once before last week can you tell me where we only talked about conjunction and negation and nothing else hom homomorphisms homomorphisms preserve negation and conjunction and then we never worried about anything else the everything else was automatic okay uh we are not yet done I should add two more symbols t or top and bottom for false okay so this one stands for truth and this stands for false I mean uh true or false yeah I mean those are the symbols because our logic yeah we are not trying to say that uh I am sometimes lazy if that's a statement then that has some sense of quantifier yeah sometimes is a quantifier we do not want to talk about such statements our world will be black and white something is either true or it is false there is nothing in between right so that's why only two symbols I accidentally might write T and F yeah please correct me if I do yeah so truth and false those are the only two symbols okay now what does the language consist of so language is simply a set yeah usually countable and most likely finite okay it is just a set we use letters pqr to denote elements of the language yeah I mean they are called propositional elements of the propositional language and okay so the notation that we use is usually L yeah L stands for language yeah no surprise here latis l poset p well order W yeah language L but it's a curly L yeah we will distinguish it from a lce so L is equal to I mean generally we write something like this P1 P2 and dot dot dot that's our language so these are just placeholders so let me give you a quick example yeah my first statement is that the moon is made of Pi is it sensible don't care about it whether it is sensible or not yeah mice like cheese yeah this is another statement and then I'm saying it is not the case that the moon is made of Pi so if the moon is made of Pi is the statement P I'm saying it is not the case that the moon is made of Pi so what is that statement negation P that's how we are going to work with it don't care about what's inside just care about how things are connected right so uh Did You observe something very specific here I did not say the Moon is not made of Pi I did not touch the sentence that was there I said it is not the case that so I can say that uh person X is a good student okay and X is a fixed Quant uh fixed uh person now if I want to say it's negation what should it be it is not the case that person X is a good student I'm not going to immediately change good to bad yeah there are different Logics which will deal with that kind of situation our logic does not change the internal portions of the sentences understood the moon is made of Pi and the and mice like cheese this is p and q p and I mean in our normal language what does it stand for and this is not well let's also mention those things I will use green color uh or maybe red color yeah this this stands for and this stands for not this stands for or then this stands for if then and this stands for if and only if so there are three different types of languages we are dealing with one is the language of Boolean algebras another is the language of logic meta language of logic and third one is our usual human understanding so prepositional logic will establish one to one correspondence between all of them yeah so in these two lectures we'll go there so you understand what is propos uh what these P1 P2 stand for they are just sentences and then we are going to talk about whether they are true or false we won't worry about what those sentences are are those meaningful how they are constructed nothing they are indestructible understood this part okay so this is our language and so alphabet alphabet what is English language alphabet what does it consist of ab b c d up to zed then there are some meta language symbols also huh punctuation punctuation marks then also space without punctuation marks and space we cannot construct sentences so similarly with a language now we have the alphabet we should construct sentences we'll call them formulas but there are sentences also this distinction will be clear between formulas and sentences once we study first order logic so okay so let's start with that the set of sentences or formulas for a language L I mean sorry for a propositional language L is defined recursively as follows okay I want to make two more comments that first whenever we are talking about logic then your language has to be precise yeah that's one of the most important things to learn about foundations of mathematics I mean your language has to be precise doesn't mean this language I'm saying the way we speak about mathematics that will become more precise if you study logic properly yeah that's one of the major goals of teaching you logic that your language becomes polished okay uh so even like these small propositions like see there are so many common things yeah are propositions for yeah this for a language L formulas for language L yeah now you cannot say formulas of a language everything has to be very precise okay uh okay uh this one I'm going to say SL s is ordinary L is Curly recursively as follows what is the base case each propositional variable is an L formula okay each propositional variable is an L formula we had to start somewhere and the only place we can start with is whatever is given to us and then we can form long sentences with them and then this recursive case so if s and t are r l formulas uh this is my way of writing it shortcut yeah FMLA formulas then so are negation s and s m t and then there is a third Clause yeah so this uh this is neither base case nor recursive case but I mean if I call this 0 1 and two then the most important case uh important clause it reads that's it okay what does this mean that there is nothing else which is a Formula only the things which we can construct using base case or recursive case only those things are formulas nothing else is a Formula right so in every definition we write about formalism this Clause will will be present and it will be the most important Clause so here note something that we are talking about parenthesis negation S without parenthesis it won't work right so you have to be careful about it so let us look at some examples if L is equal to P then some L formulas are obviously P then P conjunction P then negation P then P conjunction negation p then negation of P conjunction p and dot dot dot how many such formulas would there be infinitely many even when you start with a singl ton language yeah there will be infinitely many propositional formulas okay this is one of your tutorial exercises that if your language is countable show that The Collection SL is also countable always countably infinite nonempty count uh if your language is nonempty then it's always countable infinite okay so then these some some L formulas are like this and if L is equal to PQ then what will happen some L formulas are tell me well start with p and Q yeah don't don't jump to something fancy then P negation P negation Q then P conjunction Q anything else negation of P conjunction P yeah and so on right so you can write down infinitely many formulas uh yes let us go back a bit and let me write that we use letters Stu to denote L formulas okay so we are going to use only very specific letters to denote something specific pqr to denote elements of language St to denote formulas yeah this distinction in our mind is very important right so this base case uh and recursive case see this is not our usual type of induction this is called I mean recursion or induction this is called recursion on the complexity of formulas yeah this is not our usual type and um we can also write SL as uh using our usual recursion so alternate definition of SL uhhuh Define s0 L equal to l and s n + 1 L equal to SNL Union negation s comma for all s in SNL Union s conjunction t for all SN T in SNL and then so finally we set SL equal to Union of SNL where n is less than Omega so now tell me how uh like where is P this particular p in which SNL what is the n zero zero this meet p p p conjunction P one negation P this one two now can you easily recognize which SNL it belongs to what do you do number of parenthesis okay very simple idea just just the number of parenthesis will tell you which SNL it belongs to okay now one observation that you might have made so far is that yeah so this is observation but you are supposed to prove it if L and R L blank and R blank denote the number of denote the numbers of left and right parenthesis now respectively then for any s in SL LS is is what is equal to RS how will you prove such a result how will you prove such a result if you want to prove anything about SL SL is recursively constructed so what is the method of proof induction induction oh yeah I earlier said that there are two things to discuss and I only said one the second thing is we try to use very minimal set theory while doing this we only assume existence of finite or atmost countable sets yeah we don't want to do anything more complicated than that so therefore our proof techniques are also going to be limited to I mean at least in the first part this formalism part our proof technique is going to be limited to only induction because that's all we know yeah even though you have studied more set theory than this yeah logic is an independent branch of mathematics and at The Meta level it should not assume too much set the that that will change as the time progresses but for now we don't want to use anything more now uh another observation so we can call this observation one and observation two see if I take any formula and I take its initial subword so for example I can take just this part or I can can take just this part I can take just this part so nonempty initial subword of a formula then the number of left parenthesis and right parenthesis how are they related in that subw left is more than that exactly left is more than that and therefore what can you conclude that no left proper left subvert non-empty proper left sub word can be a propositional formula itself yes it's an observation but again you are supposed to prove it if W is a non-empty proper left subw of s in SL then L of w is bigger than R of w and hence W does not belong to SL right so a formula is a whole on its own yeah you cannot canot break it into two parts two things cannot be formulas and for this reason these parenthesis are really crucial because everything is really based on around parenthesis just counting of parenthesis in practice tell me do we write so many parenthesis it's cumbersome right and also if I just want to say that P implies Q how complicated would it be what is p implies Q yeah I mean this is just an aside I will write it here so P implies Q is a shortcut for negation P or q but negation P or Q we don't even have R right disjunction we don't have so it is negation of negation of negation p and negation q and then this well we don't want to write this H oh what happened have I not written it correctly I missed parenthesis 1 2 3 2 ah okay here thank you there should be one more right ah okay see this is the mess we create if we write all the parenthesis now if we just want to say something like P implies q and we are making so much mess yeah we don't want that so first yeah I mean based on these two observations we will state a theorem which is easy to prove from these two observations and then we will try to add some derived symbols in our Lang language Okay so uh let us go to the next page and say that so this looks boring but it is extremely important unique readability theorem if L is a propositional language and S belongs to SL then s is exactly one of the following forms first one f s belongs to L Second One S is equal to negation t for sum T in SL and Third One S is equal to T conjunction U for sum T and U in SL okay you might think I have just written down the definition again but that's not the case in the definition I said that you start with propositional variables and then you use two rules either negation or conjunction to construct new formulas but I'm saying that if you uh like any formula can be constructed in exactly one of these two ways or it itself is a propositional variable there cannot be anything else you understand that a formula which is negation of something cannot be a conjunction of something right it cannot happen suddenly that negation T is same as Steven conjunction T2 and how do you prove something like this this is just manipulation of symbols yeah there is nothing else how do you prove something like this using those two observations because if something is of the form yeah I mean I'm giving you a hint if something is of the form two then the first symbol must be parenthesis the second symbol must be negation if even if T it itself is a negation yeah in the third form even if T itself is a negation there will be a parenthesis before negation that's how we constructed it right so therefore there cannot be two different construction trees for the same formula construction tree is a term used for this so if I want to construct this uh if I start with p and uh this yeah negation p and q and then negation then how do I start well first of all it is a negation yeah so U I should write this yeah here in the tree I'm applying negation then this is conjunction so it is coming from two different things first one is negation p and the second one is q q and this is the conjunction part and this is p and this is the negation part so basically unique readability theorem says that every single formula has a unique construction tree why is this important all of you know some level of programming yes coding in coding if you write some if you have one uh wrong symbol then your program does not run so therefore every symbol should be in its proper place so there is unique readability to the codes that you write so that is what this says okay you cannot write something with ambiguous meaning okay so again this is easy to prove using those two observations okay at this step this is the right place to use derived connectives we use disjunction implication and this okay okay how do we Define disjunction we already know so s disjunction T is same as negation of negation s conjunction negation T and this then implication is negation s disjunction T right and by implication is implication conjunction another implication so these are in increasing levels of complexity then we do not use so many parenthesis in practice so but we use some conventions okay what are the conventions so negation binds closer than all of the other symbols so for example yeah for example if I write negation p and Q then what does this mean it means negation P first and then conjunction Q it doesn't read as negation of P conjunction Q if I want to say that then I should put parenthesis so the rule is that negation binds closer than any other symbol similarly so conjunction and disjunction they bind closer than implication and bi implication yeah these are the common things which we use yeah whenever you read a formula then you read them using these things so that now we don't have to use so many parenthesis yeah our life will be easy again any questions so far no okay so uh yeah I mean just well perhaps I should give you a a non example of a formula if I just write this is this a formula yeah it's not not obtained from anything then so is not yeah these looks look nonsense and that's the purpose of this last Clause yeah that's it that we do not allow anything else so you understand the formalism we have our alphabet which consists of language and meta language and using that alphabet we construct what are valid formulas oh yes I did not say this I should add yeah some people will call them well formed formulas especially if you read some books and abbreviated as wff however I'm not calling them wellform formula because I never understood when did we Define ill form formulas we never Define them so therefore all the formulas we talk about are well formed so I'm not going to use that terminology okay uh let me go to the second slide now look at these things p p conjunction P then I can also add P conjunction P conjunction p and so on so even with something as simple as P we have infinitely many formulas and most of them look the same yeah to us to our eyes they look the same P conjunction P what will be the short shortcut to write that P then P disjunction P also if we write it should be P but a computer doesn't understand that for a computer everything is a string of symbols we have to write all of them however here enters human semantics because we understand that P conjunction P should be P we have to make sure our understanding is exactly the same way so let me start with this semantics part of our propositional logic so PL L semantics so what is semantics for us it is called a valuation or a model because there is a branch of logic which is called Model Theory nothing to do with fashion industry OKAY model is so in simple sense a group is a model of the theory of groups a ring is a model of the theory of rings so the theory of rings will come first and then a ring is a model of that theory so in the same sense now this is a baby example so let me write that down for a propositional language L A valuation or a model for L is a map map means function V from SL to the Two element set truth and false satisfying the following okay so first one V of negation T is equal to true if and only if V of T is equal to false for all oh sorry uh please add it here for all T and U in SL then I can erase this part and then second condition V of T conjunction U is equal to T if and only if V of T is true and V of U is true okay uh let me add one more if I only here for the first Clause if and only if V of T is not equal to true so uh if you have copied this down let me quickly go back to the first slide see there was something red red stands for and and not and the black stands for uh conjunction and negation now this definition is trying to give a connection between those two read this V of negation T is true if and only if V of T is not true you can see the transform yeah this not is our understanding similarly in the second Clause V of T conjunction U so this is conjunction is equal to true if and only if V of T is equal to T true and and V of U is equal to true so we are converting these symbols into our usual meaning yeah that's how the definition goes okay so can you tell me uh I mean where should we start in order to Define such a valuation it's an arbitrary map which satisfies these two values okay so let me uh give you an example so let's first do that if L is equal to PQ then V of p is equal to true and V of Q is equal to false then V of P conjunction Q is what tell me false because this property is not satisfied the second one V of T is equal to true but V of U is not equal to true so therefore we cannot say that the conjunction has this normally what do we do for such things you already have some truth truth tables very good so now here is where the truth tables enter right so simple thing let's do this so we have truth tables so we have P we have q then suppose we want negation P then we want negation Q then we want p uh conjunction q p disjunction q p implies Q all right so and maybe I'll slip in one thing one more thing over here negation q p by implication Q if both of them are true what will be negation P false negation q p if and only if Q by implication true p and q p or Q I mean disjunction and P implies Q okay how many entries should I fill up for p and Q four entries yes so there will be four rows and in general if I have n variables then 2 to the power n yeah not 2 n 2 to the power n so uh let me fill this up so true and false yeah so negation p is still false this is true then well let me first finish this false and true and false and false negation P will be exactly the opposite thing negation Q will be this p if and only if Q is true if and only if valuation of p is equal to valuation of Q so true true will give me true true false will give me false false true will give me false and true false false will give me true false false will give me false uh true because they are equal yeah it just checks whether they are equal then P conjunction Q is true if and only if both of them are true so the rest of them I should write as false false false and disjunction is true if and only if one of them is true yeah or our meaning of or either p is true or Q is true so I should say true true true and false and P implication Q is true if and only if either either our premises is are wrong or our conclusion is true so therefore it only becomes false in this case yeah let me quickly write that down that V of s implies T is equal to true if and only if I mean sorry I shouldn't write if and only if I'm always going to be careful if and only if V of s is false or V of T is true all of you know how to draw Ro tables right nothing hard about that so tomorrow we will continue our discussion about semantics and then we'll see the notion of logical equivalence between formulas so that P conjunction P becomes logically equivalent to p and then we can treat them as the same thing and these logical equivalence classes there is a word equivalence in there so the logical equivalence classes will form a Boolean algebra whose meet and join and complement they will coincide with our usual logic operations [Music] [Music] [Music]