Tutorial : Week 07

[Music] okay let's start so uh today we are going to look at some problems based on propositional logic very basic problems essentially so the first problem is if L is countable then SL is countably infinite what's the answer how do you show that bounded above using string bound below us L bounded below using l l okay yeah I mean uh well I should say uh is non empty yeah that that thing needs to to be added yes so we need to show that this is countably infinite so it is bounded below so suppose P belongs to L then negation p negation of negation P negation of uh negation of negation p and so on they are elements of are L formulas so how many are there like this there are countably infinitely many such formulas right so therefore therefore Alf not is a lower Bound for SL okay because these are all formulas they are all distinct yes so therefore this is a lower bound and upper Bound for for the upper bound you you have to notice that every formula is a finite string of symbols yes so which symbols can we use anything in L and what other symbols can we use conjunction negation and parenthesis so there are so any L formula is a finite string string as in like we are writing a word word or string finite string of symbols from L and these symbols so if L is countable then what can you say about this set that is also countable yeah so uh which is a countable set therefore SL is contained inside the set of finite strings with countable alphabet see I'm saying contained is it equal can it be equal can I just write open parenthesis is that a formula no so therefore it is contained properly contained but uh finite strings with countable alphabet how can you write that set we can write it as a countable Union countable Union of strings of length n where n varies correct so let a n denote the set of finite uh sorry length and strings with alphabet L Union okay this one you know so what can you say about the cardinality of a n come on N is countable n is countable how for each place we can choose one symbol from a so therefore a n is actually a finite power the power n this language cross language cross I mean this alphabet cross alphabet cross alphabet taken n times so therefore a n is since finite product you all should be prepared for the exam and instead you are not saying anything this is something we did in week two yeah since finite product of countable sets is countable a n is countable and hence so is Union of a n n belongs to Omega correct I mean if we need we can use axum of choice yeah countable axm of choice and this Union a n is precisely the right hand side here so therefore we are done so we showed that Alf KN is a lower bound Alf not is an upper bound and therefore we get what we need any questions this is perhaps the simplest possible question let's go to the next question suppose s is a is an L formula and let LS and rs denote the number of left and right parenthesis in s then can you show that LS is equal to RS what kind of formulas are there there are three different types of formulas the first formula is a propositional variable how many left brackets are there in a propositional variable zero and for right bracket so LS is equal to RS what is the other form yeah so every formula let me write that each s in SL is of one of the following forms one of the three forms the first one is that s belongs to L and here LS is equal to 0 is equal to RS second s is equal to negation t then what what can we say I mean what kind of proof should we use proof by induction very good so s is equal to this uh so I mean let's say this is our base case yeah maybe I should change the order I should say that this is my base case and then inductive case one of the three forms uh so here I will write we will use induction uh on N what is n here induction on N so s belongs to s0 l that is what we were doing earlier so here um belongs to SN + 1 L and we wanted where T belongs to SNL so what can you say about t the number of left parenthesis in t so then L of s is equal to 1 + L of T but L of T is equal to so this is by induction hypothesis this is equal to 1 + r of T and this is equal to R of s similarly so inductive case has two steps s is equal to T conjunction U where T and U are in SNL so the result holds and then L of s is equal to 1 + L of t plus L of U correct so this is equal to by induction hypothesis 1 + r of t + r of U is equal to R of s so we are done very simple and boring proof but let us see if you can use the same logic over here suppose W is a nonempty proper left subw of a propositional formula non-empty proper left subword so basically I mean I'll give you an example first suppose I'm writing this then I can have this word just one parenthesis then I can have this word two parenthesis 3 4 yeah any of those left subword and what do we need to show that L of w is bigger than R of w what is our method of proof induction there can't be anything else so once again there is base case yeah I will perhaps not write the entire proof you can formalize it the base case is that s belongs to s0 L then can there exist a non-empty proper left subword it just has length one yeah so either the subword is empty or it is everything so there is nothing to prove here yeah so base case nothing to prove then what about the inductive case in inductive case you can either have S is equal to negation t or you can have S is equal to this so let us consider this case Okay uh then what will happen if yeah I mean I'm just going to write this if s is equal to negation T then nonm proper left subw of s has one of the following forms well it can be just this parenthesis it can be that parenthesis followed by negation or it can be T Prime yeah uh sorry I mean maybe I should call it uh W Dash where w-h is a left subword of t or finally it can be just this okay these are the only possible four forms now what will you do in the first case if it is just a parenthesis then how many left parenthesis are there one right zero second one also same one and zero third one what will you do if it is a proper left subword of T w- is a proper left subword of t then by induction hypothesis you already know that L of w- is bigger than R of w- and then what is L of w 1 + L of w Dash and therefore you can prove the result and in the last case well T is T is a Formula so therefore l L of T and R of T are equal and therefore 1 + L of T is equal to l of s and that is strictly greater than R of T done okay can you do the second part as well if s is equal to oops T conjunction U then what are the forms either it can be just this parenthesis open parenthesis or it can be open parenthesis followed by some subw left subw of T in which case we know what to do then or it can include an entire T and then just this in which case also this open parenthesis is extra or it can contain some left subw of youu it can go until some left sub word of you in which case you can use the result for you induction hypothesis for you yeah so this is again very boring and straightforward proof I'm not going to finish this however we need this result the result is interesting but the proof is boring that's what I'm saying we need this result to prove the unique readability theorem so we know that every single formula can be written as one of the three forms either it is in the language or it is negation of something or it is conjunction of two formulas the question is can we write a single formula using two such different forms any ideas on how to prove this if I say that the length is one length of this formula is one then what can it be it only can be propositional variable and that propositional variable is uniquely determined so without loss we can assume that the length is bigger than one which means we have taken care of s0 basically okay now the question is can it be of form two and form three simultaneously can it be a form two and form three simultaneously by yes if necessary do you have any idea in mind how to count count and then prove it so for the second form would be only the form l l of t plus and on which sub word are you applying that you had to tell me which sub word is that the whole formula the whole formula the whole formula L is always equal L and R are equal in both these cases right we proved that even if it is of second form or third form it doesn't matter L and R are always going to be equal so are the same L one should be equal to l yes L of one should be equal to l of the other can prove and how will you prove that that's what my question is is not proposition variable then we would have at least one uh you do you mean u u is not a propos is one then it will have at least one um we don't have to go that way just look at the strings how they start okay so um what can t be in in Formula 3 what can t be T can either be a propositional variable or a formula which is not not a variable so either T can be a variable or the first syllable the first letter in t can be a parenthesis or proposition a propositional variable whereas look at formul form two in form two what is the second letter it's negation so therefore they can never be equal to each other yeah so uh it is enough to argue when s is not in L if s is equal to negation t for some t oh perhaps I will make a slight change yeah um we are facing problems because I'm using the same notation over here I I'm going to convert this into U1 and U2 okay if s is equal to negation t for some T inl then the second syllable uh second letter is negation however if s is equal to U1 conjunction U2 then the second syllable or letter syllable and letter are the same thing we'll use syllable very properly next time uh so maybe I should use letter uh second letter is either an open parenthesis or a prepositional variable therefore no formula no formula no l formula can be written as both form two and form three because their strings are different the second symbol is different okay now now yes suppose un is also negation of something even if it is negation after negation we put a parenthesis so don't forget that yeah but that then the third letter will be negation third letter will be negation but the second letter in that case will always be open parenthesis whereas in that negation in second form it will be negation so therefore they are going to be different any other questions yes sir uh is it necessary to for every formula to have a unique Str I mean uh you just don't want to solve this question so uh I mean all of you know coding yeah so in coding don't you have to be precise otherwise there are bugs so why does a code work because it has unique readability whatever you write should have a unique meaning if you mess up one symbol will it accept your program will it run no so you can be precise there then why are you asking why I mean this is the logic behind coding but we can't put as many you can put as many brackets because uh even in coding can you put as few brackets as possible yeah I mean if you miss out on some parenthesis will your code still work parenthesis curly brackets square brackets whatever you are doing if you mess them up then it doesn't work one of the rules of coding is also what we wrote here the left and right parenthesis should always match the number matches but the number matches but the number can vary yeah yes the number can vary but it again has unique readability so U There Are Rules like what binds closer we also had those rules yeah that negation binds closer than conjunction and disjunction which themselves bind closer than implication and bi implication so there are some rules yeah but they are taught to a machine yeah it's not automatic everything has to be taught computer programming works on the principle of turing machine yeah it only reads one symbol at a time so that's that string of symbols every program is a finite string of symbols so that string of symbols must be uniquely readable similarly in logic also if we are doing something formally then it should be uniquely readable and uh in fact yesterday we showed an application do you have any other question are you happy with this yes okay so uh okay so no l formula can be written as form two and form three both that much is clear now if I have two formulas of I mean the same formula can it be written at in two different ways using form two so the next question is if s is equal to negation T and S is equal to negation T Das for T and T Dash in SL then can you conclude that t is equal to T Das Lally no no no not logically equivalent there is no logical equivalence here yet yeah this is we are talking about plain syntax see how do you recover T from this s you remove the first two and you remove the last letter then you can obtain T similarly if you remove the first two and last letter then you can obtain T Prime then clearly T is equal to T Prime so there is no question whatsoever okay so therefore there is no problem here however we need to do some work if s is equal to U1 conjunction U2 and S is equal to U1 Das conjunction U2 dash for U1 U2 U1 Dash U2 Dash in SL then then we have to do some work yes so first we said that oh I mean uh it was propositional variable just length one so there is nothing to check it can only be a form one then we showed that two and three simult ously cannot occur then we said that two and two cannot occur simultaneously now only remaining Cas is three and three now what will happen in this case well if U1 and U1 Dash are equal then we are done yeah so if they are not equal then what will happen I'm going to write this string yeah so this is U1 so without loss we can assume that this is the length yeah if if U1 is not equal to U1 Dash then without loss of generality assume that U1 is a proper left subword of U Dash I'm beginning to read in two different ways yeah so the first way is that I start with U1 and then I hit this conjunction symbol but now there is another way where I have to go a bit further to hit the conjunction symbol then without loss of generality one of them has smaller length because we are talking about length length is in integers and it's a linear order so trotto yeah we are using Troy here so if U1 is a proper left subw of U1 Dash and U1 is of course a formula so it is non empty so then what will happen U Dash is a formula and it is a proper left sub word so therefore the number of left parenthesis in U1 has to be greater than number of right parenthesis which is a contradiction a contradiction to U1 in s cell because if un is a Formula then the number of left and right parenthesis must be equal yes because it's the same string yeah both of them are s like that a and like C uhhuh A and C are not same uh A and C are not same like are you thinking of a and C as letters or they are formulas they formulas if they are formulas then one of so either their lengths are equal or their lengths are different if their lengths are equal then we are done right if their lengths are equal then you go only that much length the formula is still same see this is s this is s formula is still same so therefore if the lens are equal then U1 is equal to U2 the next symbol is conjunction and therefore U2 is also equal to U2 Prime U1 is equal to U1 Prime and U2 is equal to U2 Prime so we are done if their lengths are different then what can you say one of them is longer than the other contain in the same the in the same they I mean they are not necessarily so I said without loss of generality it can be that U1 is longer than U1 Prime is composed form uh it that both of formas in the same in the same order yes then will be able to say I mean what order are you talking about strings to be sa the string is there is only one string there is only one string namely s talking about u andu a string human as a string can you give me an example that what is the point of this proving this we know that and Prime will have the things in the same order to some extent to some extent but exactly same extent that's the point of proof proving this I mean are uh all of you questioning why we need unique readability is that the point unil see uh let us give take an example so negation P conjunction negation Q is this good enough for you oh maybe U maybe I will I'll take two things maybe I'll take conjunction Q conjunction negation Q This is a valid formula yes so now can I write it in two different ways what's your point now which which one can be U1 what can be U Prime uh negation P join Q uh meet sorry negation P conjunction Q is U1 yeah that's unique but see I cannot give you an example where un and un Prime are different because that's what we are proving it's not possible so what q and then conjunction yes okay that's a good question that if we are doing U1 conjunction U2 and then you do U2 conjunction U1 then they are different strings we are not talking about formulas up to logical equivalence here the this conjunction is commutative up to logical equivalence but it's not the same string see otherwise what's the point yeah we said that P is a Formula P conjunction p is a Formula then P conjunction P conjunction p is a formula and there are infinitely many formulas all of them I mean all but the first one is useless up to logical equivalence but actually as strings of symbols they are different so therefore U conjunction U2 and U2 conjunction U1 even if they are logically equivalent we think of them as the same they are actually different if U1 and U2 are different then they are different yeah so therefore we still need to prove this result any problems in the proof okay then we have shown unique readability now let's go ahead okay draw the Hass diagram for this Boolean algebra so how many atoms are there in this Boolean algebra four atoms so how many elements are there 16 can you tell me the atoms let us start with uh the bottommost element what is it contradiction which contradiction should I choose I should always talk about the class of a formula equivalence class of P conjunction negation P very good then tell me some atom P conjunction Q is an atom okay good any other atem P conjunction negation Q okay then other atoms negation P conjunction q and negation P conjunction negation Q okay good now we can if we are allowed to use all the symbols then can you tell me what is the top one contradiction top one is contrad tooy huh how do you write toyjun P disjunction negation P okay what are the co- atoms Co atoms are precisely the atoms of the inverted Boolean algebra negation negations of all of these yeah can you have some nice forms for them p p disjunction Q yes okay then P disjunction negation P disjunction negation Qs uhhuh then P disjunction negation P disjunction q and negation P disjunction negation Q okay so in the truth table for a contradiction yeah I mean it is a column it is the column in the truth table how many truths are there zero how many truths are there in the column for atoms yeah so one how many for tautology and how many for Co atems 4 minus 1 yeah okay what are the middle formulas now okay PQ thenation negation pation negation q p p q Pou implies Q very good negation p double implies Q okay good and you can connect yeah I'm not going to do this networking so there are precisely two truths in the column corresponding to all these formulas and how many can there be it's a column of length four and there are precisely two truths so four choose two six so there are six so 14 641 okay uh I hope I don't have to teach you how to convert from one set of connectives to another set of connectives if I ask you to write this uh P if and only if Q yeah I mean p by implication Q only using conjunction you can write it only using disjunction and negation you can write it yeah I mean negation will always be there but only using certain connectors that you can do any problem so far okay then let us look at some examples of logical equivalences and relations so what about double negation p is logically equivalent to P is that true how will you show that truth table okay so perhaps this is Simple Truth tables you can all draw but there are some interesting questions there yeah so U perhaps this you can do but p dis disjunction negation P and R implies Q implies R they are also logically equivalent and yesterday I used a comment that there is no functional relation functionality just depends on this that this contains p and this contains q and R so there is no causal cause and effect what happens is that this is a toogy and that side is also a toogy because see if R is false then the whole implication is true but if R is true then Q implies R is also true because R is true right right so therefore true implies true so everything is true always yeah it's very easy to check this so therefore both of them are tautologies now uh we can ask similar questions yeah so for example if I write down some other formula let's say I write down uh P disjunction q and then I ask whether this equivalence class is less equal the class for p if and only negation Q if I ask this how will you solve this problem implication yeah I mean you take this formula then you take implies the other formula and then you show try to show that it is a tooy if it is a tooy then then this this less equal happens and if it is not true then the implic the L equal relation does not hold however yeah I mean uh is there a quicker way of doing this see in general I'm asking you this how to check this if there exists yeah so uh sorry the answer is no if there is a valuation v such that V of s is true but V of T is false so basically when I'm saying that this implies this is is a tautology what does that mean that whenever the column in the truth table for this formula has t then the same Row in the column for this formula must have t yeah if it doesn't happen then there is some T here but F I mean false there in that case we don't do anything so you can um solve all the problems related to this okay I think uh the congruence relation question we have already done and yesterday I tried to show this yeah I mean in the atomless Boolean algebra case I tried to show this uh maybe I should write on the next slide so truth less than so some non uh non-contradiction formula was given and then I was trying to show this so this is given that s is not a contradiction so therefore this is less than so because this is less than we obtain some valuation for which VSS is true vs is true and we needed to find something in between and how did we find that something in between if our language is countably infinite then s being a finite string of symbols it can only use finitely many propositional variables so there is a new variable which does not appear in the formula s and I choose that V I will call that variable p and then I can put here I can either put here s conjunction p or I can put here s conjunction negation P now I know that there is a valuation V which makes s true now that valuation is either going to make p true or P false if it makes p true then s conjunction p is true okay so s conjunction p is true so therefore we have witnessed that s conjunction p is not a contradiction understood on the other hand if V makes p false then s conjunction negation p is no oh sorry s conjunction uh p is FAL false so therefore we have witness this less than and then we construct another valuation which only differs from V in the value of p and then you can simultaneously witness this or that yeah so that's how you have to show both these less than yeah just showing one of them is not sufficient both have to be shown [Music] [Music] [Music]