Propositional Logic | Discrete Mathematical Structures - Lecture 1

[00:00:05][Music] [Music] [Music] [Music] this course is about discrete mathematical structures it is a theoretical course intended for we take our B students in computer science in the second semester and what are the things we are going to study in this subject so first of all what is discrete mathematics and what are the topics which are to be covered here discrete mathematics is study of discrete structures which are abstract mathematical models dealing with discrete objects and the relationship between them the district's objects could be likes it's permutations graphs FSA etc we'll see in a minute what are the topics which are to be covered here and why do you want to study discrete mathematics and why should one study the subject the reason is in many fields in computer science basic mathematical concepts will be used and in any books on them when such a concept is introduced they will not explain it in detail but briefly mentioned a few lines about it better for a student to understand the subject completely that may not be enough at the same time only not going to depth in these subjects also one shouldn't not lenore or need not learn these subjects as a mathematics student would learn algebra or analysis you want to know something about its topic to a decent depth and that will help to understand the other subjects in computer science in a better way the aim of this course is not only make people learn about these topics but also develop the habit of thinking mathematically the student should develop to think in a mathematical manner that is the aim of this course what are the applications are the what are the fields in which this these concepts will be used they are plenty in fact in each and every subject in computer science somewhere or other these concepts will be used for example when you want to study programming after writing a program you would like that it is correct you want to prove it so proving programs correct is a topic which will be studied in this course it will help you to write correct programs and in artificial intelligence a lot of ideas about logic will be used Prolog it's a logic programming language where there a solution principle is used and we will learn about this in this subject and in computer networks lot of concepts about graph theory and finite state automata are used so that will be very useful that in fact you can find that in any field you will have a few concepts from discrete mathematics which will help you to understand the subject in a better manner in compilers you learnt the finest rater automatic concepts will be used grammar concepts will be used hash functions will be used and these are studied in this subject and now what are the topics which will be covered in the subject we'll be studying about logic sets relations then functions graphs combinatoric s-- recurrence relations algebras and FSA the level of the subject will be like this first nine lectures will be devoted to logic and it's applications then three lectures will be on sets actually this subject does not presuppose any prior knowledge from this road and accept a reasonable mathematical maturity expected of a high school student that is the only thing we assume and proceed with this subject in fact after learning this subject the student should be able to think more mathematically and also should have acquired a basic knowledge about these topics then we go on to relations in relations first we have lecture 13 then afterwards we shift two graphs from lecture 14 to 17 then again come back to more properties of relations from 18 to 23 then the last lecture will be about lattices it is also about partially ordered sets we will learn about certain basic facts about graphs in lecture 14 to 17 then we learn about the functions in lecture 24 to 26 then a few lectures on combinatoric where we will be studying about pigeonhole principle permutation and combination and generating functions the recurrence relation is a another topic it is of importance especially in algorithmic analysis we spent three lectures on them then algebras we'll study a little bit there we study about groups semigroups rings etc and about financial Tata my time we have two lectures where we study only the basic principles of finite state automata we shall give some reference books for the subject some of them are new some of them are old but there have been recent additions of them elements of discrete mathematics by CL lu and the second one is discrete mathematical structures with applications to computer science by Tremblay Manohar these are standard books discrete mathematics in computer science by Stinnett and Mike Lister is another book discrete mathematics and its application by Rosen logic and discrete mathematics by grassman and Tremblay this has come some concepts about Prolog and application of logic to that introductory combinatorics by bro Rd for topics on combinatorics this book can be used modern applied algebra may be covered with but it's a world book but it has got some good concepts about lattices final state automata mathematical theory of computation by mana this book will be useful for proving programs corrected introduction to combinatorial mathematics by Leo this is an old book but still it has got some very good topics permutation combination generating functions recurrence relations etcetera then for automata theory this book can be used introduction to automata theory languages and computation by hop craft motwani and will these are only a few books there are so many other books any student using studying the subject can use the prescribed book by the respective university our College now we shall go on to the first topic logic logic is a very useful topic every student in computer science should learn this topic because it is applied in proving programs correct in databases where you study about relational algebra and relational calculus and also in artificial and intelligence about reasoning and things like that so first coming to logic there will be nine lectures on logic they are divided like this the first two lectures will be devoted to propositional logic then we go on to predicate logic then logical inference then the solution principle then methods of proofs normal forms and one topic on one lecture on proving programs correct so let us start first with logic and proposition what is proportion logic so for that first we have to start with what is a proposition in English language we talk about sentences we talk about assertions we talk about orders questions and so on what is a proposition first of all it should be an assertion an assertion is a statement it is different from asking a question or giving an order a proposition is an assertion which is either true or false but not both so you must be able to associate a truth value with an assertion truth value the truth value will be false are true usually you denote it by false by 0 and true by 1 so any sentence any assertion to which you can associate a truth value is called a proposition consider the following examples the following are propositions for this is a prime number it is an assertion but it is a false statement so the truth value associated with 4 is a prime number is false then take the next sentence 3 plus 3 is equal to 6 again it is an assertion and it is a correct statement so the truth value associated with that is true the moon is made of green cheese or the moon is made of cheese this is again an assertion and a wrong statement so the truth value associated with that is false let us see what are not propositions consider the statement X plus y greater than 4 is it true or false it depends on what value you are going to give for X and value if you give X the value 2y is the value 2 then 2 plus 2 is greater than 4 is not correct or if I give the value X is equal to 3 y is equal to 4 then it takes the value 3 plus 4 is greater than 4 that is 7 is greater than 4 which is correct so depending on the value you give for x and y the statement takes a true or a false value it does not have a unique value it depends on the value are going to give for the variables x and y x and y are called individual variables so you cannot associate a unique truth value to this next take the sentence x is equal to 3 here you find that you cannot associate a truth value to this if you give the value 3 to X it will be true if you give some other value to X it will not be true so again this is not a proposition take the next one are you leaving this is not an assertion a proposition should be an assertion all you're leaving is a question and it is not an assertion so it is not a proposition take the next one by 4 books this again is not an assertion is no order go and buy 3 books this is an order and not an assertion so it cannot be a proposition so whenever something is not an assertion to the question not an order it cannot be a proposition but in special cases there can be assertions which are not propositions for example they consider this sentence this statement is false this is an assertion is it the proposition it is not a proposition because you cannot associate their truth value to this if it is true it is false if it is false it is true so you cannot associate a true or a false value with this statement this is called a paradox this is called actually a liar paradox is called the layer pannel ox and such a statement even though it is an assertion is not a proposition because you are not able to associate the truth value with that this as you have variables individual variables x and y 2 which we associated numbers you can talk about a preposition variables a propositional variable denotes an arbitrary proportion with unspecified truth value P Q R there are propositional variables and you can assign a proposition to them P is just a variable propositional variable just as we assigned the value 4 to X you can assign the value of a proposition to their variable P similarly you can denote this as propositional variables and you can assign propositions as values to them then when you have proper share variables are actual propositions also you can connect them with logical connective there are several connectives first we shall study 3 of them and our and not consider the proposition john is six feet tall and the proposition q there are four curves in the model then the compound statement P and Q is John is six feet tall and there are four cows in the bottle when is this true P and Q will be true when both P is true and Q is true so we have a truth table for them so and is denoted by this symbol and the truth table for that will be P Q P and Q the possibilities are both can be false or P can be false and Q can be true this can be true and this can be false and both can be these are the possibilities and both are false the compound statement will be false when one is false also the compound statement will be false but when both are true the compound statement will be true usually we denote false by 0 and true by 1 so the truth table will be like this P Q P and zero zero zero one one deal one one and in these three cases it is zero it is this one in this case so the compound statement P and Q will be true only when both P is true and Q is true in all the other cases it will be false what about the connective are PR q If P denotes this sentence and Q denotes this sentence PR q will denote the sentence John is 6 feet tall are there are four curves in the bomb when can you say that this is true when one of them is true the compound statement will be true or when both of them are true also the compar segment will be this is called in to see our inclusive r and the truth table for that will be like this PQ p RQ 0 0 0 1 1 0 1 1 0 denotes false and 1 denotes true and when both of them are false this is false when one of them are both of them are true this will be true this is the truth table this is called a truth table for us and for the unary operator not P and not P when P is false not P will be true and P is true not P will be false so what is the statement not be John is not 6 feet up that will be the statement for not P so we are studying the operators and are not there is one more operator called the exclusive are an assertion which contains at least one proposition variable is called a proportional form so when you connect to propositional variables by and R it is a proffesional form we can also use the exclusive or operator exclusive R means the truth table for that will be like this zero one one zero one one in the exclusive our case it is true only when one of them is true and other is false if both of them are true or both of them are false it is false so when you say something like that John is six feet tall there are four cows in the barn both can be both statements can be true and the compound statement can be true but in some cases like say Sudha is wearing a sari and Sudha is wearing a blue churidhar something and if I say Sudha is wearing a sari our Sudha is wearing a blue churidhar both of them cannot be true at the same time only one can be true the other will be false so in such cases you use exclusive are usually when you say either this our that that means exclusive or when you just say our it means inclusive our but you have to be very careful in sometimes they are used in a slightly ambiguous way so when you want to transform an English sentence into logical notation or transform some logical formula into English sentence you have to be very careful whether you are using inclusive or exclusive are usually exclude exclusive or means you must say either are inclusive are you save just are without that either and any propositional form it is connecting variables it is called a well formed formula well formed formula of proportional logic well-formed formula it is denoted by W PFF usually call s wff so P and Q is a well-formed formula p RQ is a well-formed Butler we exclusive RQ is a well-formed formula so P exclusive R will be denoted like P exclusive are apart from these operators there are two more operators which are used in logic one is called the implication and another is called the equivalence what is implication let us look at this P implies Q it is denoted like P implies Q in some books it may be written like this and some in some books they rarely use this sort of an arrow for P implies Q so when you take a book you must be clear what sort of a notation they are using similarly not P is usually denoted like this sometimes it is also denoted like this so when you see a book you must be careful what notation they are using so in this case B is called the premise hypothesis our antecedent and Q is called the conclusion or consequence and what is the truth table for P implies Q P implies Q you have 0 0 0 1 1 0 1 1 then when both are false it is true when P is false and Q is true it is true when P is true and Q is false it is false when both of them are true it is true there is a slight problem here it is not a problem but you must feel convinced about this truth table usually when we say logic or what we study is Greek logic which was formulated by Aristotle Socrates and Greek philosophers in such logic this is the truth table for implication the antecedent and the consequent need not be related at all they may be quite unrelated statements like if the moon is made of cheese then earth is not found it could be something like that there is no relationship between the antecedent and the consequence but the compound statement is true because this is of the form false implies false and for that in the truth table the first line of the truth table tells you if P is 0 and Q is 0 P implies Q will be true Greek logic allows that usually in Indian logic you look at Bay Area but our buskerud exploration inaudible does work such things are not allowed usually as antecedent and the consequence will be related for example something like this this you can very easily see if I fall into the lake I will get red obviously the premise and the conclusion are the consequence are related and you can see the correspondence between them but generally in the truth table you must also give a valid the compound statement even though the president promised and the antecedent are not related so the implication this you must remember very well the implication is true when the premise are the antecedent is false are the consequence is true it is false on in the case when premise is true and the conclusion is false or the antecedent is true and the consequences was only only in that case it will be false either three cases it is taken to be true this can be read in several ways you can read it this if P then Q P only if Q P is a sufficient condition for Q q is a necessary condition for P Q Y of P Q follows from P Q provided P Q is a logical consequence of P Q whenever people these are different ways of saying this and you would have said it about sufficient conditions and necessary conditions in high school level and any many theorems where the statement will be in the form if then for example you decided the Pythagoras theorem if ABC is a triangle right angled at B then AC square is equal to a B square plus BC square so the statement of the theorem is of the form if something then something and sometimes you talk about the converse of a theorem sometimes the theorem will be proved in a slightly different manner when we study methods of proof we'll go into that in depth but generally the converse of a theorem is denoted as Q implies P P implies Q is a comp a statement and the converse is Q implies P is the converse and not Q implies not P is called the contrapositive so you have this P implies Q Q implies P is the converse not Q implies not P is the contrapositive so suppose Pythagoras theorem is if ABC is a triangle right angle at B then AC square is a B square plus BC square what would be the converse of the theorem Conners also you would have studied in school if in a triangle the AC square is a B square plus BC square then the triangle is right angled at B so there is a Congress in this case is it so happens that both the theorem and the converse are true but several situations may arise where the theorem may be true but the converse need not be true because P implies Q it does not mean Q implies P is two whereas the contrapositive not Q implies not P will be true whenever P implies Q is true let us draw the truth table and see this so you have P you have P Q P implies Q not P not Q not Q implies not P so consider this table you have the possibilities 0 0 0 1 1 0 another thing is you must note before going into that let us see that if there are variables say P Q R yes like that in the truth table there will be one column for each one of the variables and there will be one row for each assignment of the variable each variable can be assigned the value true or false that is 0 or 1 so if there are four variables they'll be two into two into two into two 16 possibilities so there will be 16 rows in the truth table in general when you deal with in proportion variables and you want to study the truth table involving them about foreign expression involving them there will be n columns first n columns will be first n columns will be 4 very this and their turn there will be more columns here there are two variables two columns are for the variables and here you consider every assignment every possible assignment for the variables so there will be two power n possible assignments possible assignments of truth values to the variables and so there will be 2 power n rows and if you look at them carefully they are representing binary numbers 0 1 2 3 so they will represent binary numbers from 0 to 2 power n minus 1 now coming to this this is not Q implies not P is the contrapositive P implies Q is true here it is false here what about not P not P will be true if P is false it will be false when P is true what about not you if Q is false this would be true if Q is true this will be false and when is the implication false when the premise is true and the conclusion is false so in this case it will be false 1 and 0 in the if the premise is false the conclusion will be true I mean the result implication will be true if the ant if the consequence is true then also it is true here both are 1 so it will be 1 or 2 1 represents true so you see that these two columns are identical and so P implies Q is the same as saying not Q implies not P many terms you will make use of such statements for example if a prime number is not a perfect number so you may say it is a if X is a prime is it is not a perfect number are you may also say a perfect number is not a prime it is saying the other way around in the contrapositive manner okay so next thing is equivalence you also have a logical connective equivalence which is denoted by a double arrow with arrow like this this is called equivalence this is read as P is equivalent to Q R P if and only if Q R P is a necessary and sufficient condition for Q then the Li you read is SP is equivalent to R P if and only if Q this is also correct P is a necessary and sufficient condition for Q when is this compound statement true this compound statement is true when both P and who have the same values when both of them are false are when both of them are true the compound statement takes a value two if one of them is false and the other is true then it takes the value false so this is the truth table for equivalence those who have learnt a little bit about boolean algebra you will see the similarity between professional logic and boolean algebra in boolean algebra you also study about two operators an end and not that we will not study in logic instead in logic we study equivalence and implicit now let us take some examples constrict the truth tables for Q and not P implies P and P and Q or not R is equivalent to P so I say I mentioned to you earlier when you have K variables there will be K columns for each of the variable then some more columns but there will be 2 power K rows representing the assignments and they will be representing binary numbers from 0 to 2 power K minus 1 now let us draw the truth tables for these two expressions Q and Q and not P implies P there are two variables P and Q so there will be two columns for them and you will give the value 0 0 1 0 0 0 1 1 0 1 1 for them then not P Q and not B then the whole expression Q and not P in place now when is not be true when P is false not P is true and when P is true not P will be false and the ending of that when you end when both of them are true this is true in other cases it will be false now this is the premise and this is the consequence when is the implication true when the premise is false the implication will be and in this case the premise is true and the conclusion or that consequence is false so in that case you know that it is what's so this is the truth table but you can not be in place P now let us take the other one P and Q or not R in is equivalent to P there are three variables P Q R so there will be three columns for them and there will be all possible assignments for them that will be 0 0 0 usually that you write them in this order so that they are representing number 0 1 2 3 etcetera 1 0 1 1 1 0 1 1 1 now what is a statement the statement is this I will write here P and Q or not R is equivalent to P so next you must have a column for P and Q you must have a column for not R so when s P and Q true when both of them are true when one of them is false it will be false so you get this for P and Q when is not of are true when R is false and it is false when R is true so you get 1 0 1 0 1 0 1 0 now you have the expression for P and Q are not apar you are owning this and this when you are when one of them is true that the so it is true so when one of them is true it is true and both of them are false it is false when one of them is true it is true when both of them are false it is false in these cases in this case it will be true in this case it will be false true and true then the last column is like this P and Q or not R this is equivalent to P when not true expression is equivalent when they take the same value 0 0 or 1 so you have to compare this and this when they are the same it is true here 0 0 it is true but here it is 0 and 1 so it is false 0 & 1 it is false 0 & 0 it is true 1 and 1 it is true 0 & 1 it is false 1 & 1 1 and 1 so this is the truth table for P and Q or not R is equivalent to P so for e given any expression you can draw the to table and find out when the whole expression will be true and when the whole expression will be false and so on now a tautology is a propositional form whose truth value is true for all possible values of its propositional variables sometimes an expression may be such that always it takes the truth value true for example PR not be considered this expression PR not P there are two possibilities we can be true RP can be false when P is true this compound expression is true because one of the component is true when P is false not P will be true so this compound expression will be true because one of the components is true so whether you give the value of zero or one our faults are true to P this compound expression is always true such an expression is called a tautology a tautology is a proportional form whose truth value is true for all possible values of its propositional variables now the way around a contradiction or an absurdity is a propositional form which is always false take this expression P and not P there are two possibilities P is true or P is false if P is true not P is false so this expression will be fast because and will be true only when both of them are true it is not fun possible for P and not P to be both true either one of them will be true in any case one of them will be true the other will be false the possibility is this is true this is false or this is false this is true in any case this compound expression P and not P will always be false such an expression is called a contradiction a proposition form which is neither a tautology now or a contradiction is called a contingency these examples which we consider Q and not P is equal to the in place P and Q and P are not R is equivalent to P these two are examples of contingencies some cases they are true some cases they're false so they are examples of contingency given that propositional from it is always possible to find out whether it is a tautology or not because you can't always draw the truth table and if the last column is always 1 1 1 then it is a tautology the last column is always 0 0 0 it is a contradiction sometimes it is 0 and sometimes it is 1 then it is a contingency then we have lot of logical identities this logical identities can be used in simplifying logical expressions look at this one bow and let us see one by one P is equivalent to say PR people when you say PR P it is not necessary to say it price is enough to say once this is called the idempotence of r then if you have P and P it's not necessary to write like this it is enough to say like this so P is equivalent to P and P this is called idempotence offhand so whenever is an expression you get something like P and P can replace it by P then you have the commutative laws it's equivalent to saying Q or P is equivalent to saying PR q you can interchange the variables doesn't affect the meaning either this or that ARB is BRE so PR Q is same as Q or P this is called commutativity of similarly you have commutativity for any P and Q is equivalent to saying Q and P and you have associative loss p RQ then R that is first you are PR Q then you take R and combine that is equivalent to having P R Q or R and P and Q and R is equivalent to saying P and Q and R this is called associativity ah and in general we are try to whenever you write an expression you try to use parentheses there is no priority but generally not has higher priority then and then if you use only these three of them not has higher priority than end then not because you can write not P and Q this is not P and Q that is equivalent to saying not P and Q you can write without that parenthesis it is not not P and this is different if you want to write like this you must put the parenthesis in a proper way so we see that but P and Q and R you can write without parenthesis because of associated that we group this first R group this first is immaterial when both the operators around without any problem you can write like this that is what is meant by associated to your tough and similarly for all whereas you can realize that P implies Q in place if you want to write like that P implies Q implies R this is different from saying P implies Q implies up you cannot say something like this P implies Q implies R because you do not know whether you mean this R that you can draw the truth table and verify that this has got a different value this has got a different one they are not the same so you cannot write something like this you have to put parentheses wherever his either you mean this are you mean that so implication is not associated then there are de Morgan's laws which are very common and very useful also not of PRQ you can bring the not inside and that will mean not P and not Q you can again draw the truth table for this and for this and see that they will be identical the columns representing them will be identical so when you bring the not inside are become centered similarly not of P and Q will be not of P or not of Q so even you bring the not inside and becomes R R becomes and these are called the Morgan's plus then you have distributive laws and distributes over R that is P and Q R R is equivalent to saying P and Q or P R R so you can distribute and over R and write like this sometimes you can use the distributive laws in the reverse direction also another thing is are distributes over and P R PR q and r is the same as saying P R Q and P R I again here also the distributive law sometimes you can apply in the reverse then you have these rules in playing when one of the operands is true or false P R 1 is always 1 so this is a compound statement but when one of the operands is true the compound statement is always true this we know so even when one of them is true this is true and now we have taken one operand that's true only so this is 1 P and 1 if P is true this will be true if P is false this will be false so P and 1 has the same us P similarly for our PR 0 if P is true this will be true if P is false this will be false so P our zeroes take the same value as speak and when you end with a 0 P and 0 because one of the operands is false the compound statement will be false so you will have P and 0 is the same as 0 or false PR not P is always 1 always true this is called a tautology this is what we have seen earlier P and not P is called a contradiction or AB absurdity it always takes the value 0 and you have double negation saying P is equivalent to not of not of P so if you use negative 1 negative in price it is equivalent to the original statement there are some more statements like this we shall briefly look into them we shall look into them in more detail in the next lecture but just we have a brief look at them P implies Q you can write it as not P R Q this is equivalent to saying P implies Q and similarly P is equivalent to Q you can equivalent we say it s P implies Q and Q implies P this rule is also true P and Q implies R is equivalent to saying P implies Q implies R and P implies Q and P implies not Q is equal into saying not V this is called absurdity and this is used in proof by contradiction this is the most commonly used this we have seen earlier P implies Q is equivalent to saying not Q implies not P which is the contrapositive so on so to this class we have learnt a few logical connectives and how to write the truth table and so on we shall continue with this concepts in the next lecture [Music]