Understanding Propositional Logic and Mathematical Logic in Computer Science
Study the development of formal logic in computer science, focusing on propositional logic and mathematical logic. Learn about propositions, logical operators, and ways of combining statements to derive conclusions. Explore examples and understand how to determine the validity of arguments using logic.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Mathematical Logic The development of formal logic and its implementation is essential in computer science. It is mainly used for deriving a conclusion based on what one already knows. Logic is the study of correct reasoning. It provides rules to determine whether a given argument is valid or not. Proposition A proposition is a statement that can be either true or false . Examples: 1) It rained yesterday. 2) India is a state. 3) Himachal Pradesh is a country.
Proposition It is possible to determine whether any given sentence is a proposition by prefixing it with: It is true that Or It is false that and check whether the result makes any grammatical sense. Check whether the following sentences are propositions or not 1) New Delhi is the capital of Sri Lanka. 2) 1 + 1 = 10. 3) Two is less than five. 4) Man will reach Mars by 2050. 5) Close the door.
Proposition 6) This is true. 7) What time is it? 8) 6+5 9) x is greater than 5. 10) What a beautiful day! Propositional Logic It is the study of propositions (true or false statements) and ways of combining them (logical operators) to get new propositions. It is effectively algebra of propositions. In this algebra, the variables stand for propositions and the operators (connectives) are and, or, not, implies(if then), and if and only if.
Propositional Logic Example (p and q are simple statements) p q p q p or ~p p q Connective Symbol or ~ p and q p or q not p Implies (if then ) if and only if (iff) p q Consider a statement Raju will eat fruit-salad if the fruit- salad contains mangoes in it . The statement is equivalent to the statement If the fruit-salad contains mangoes, then Raju will eat it . The statement is a complex statement constructed from two simple statements say p and q, where
Propositional Logic p: Fruit-slalad contains mangoes. q: Raju will eat fruit-salad containing mangoes. If p then q, when p and q are propositions can be written as p q. The above sentence (p q) states only that Raju will eat fruit- salad containing mangoes. It does not, however, rule out the possibility that Raju will eat fruit-salad containing apples. Whenever there is a statement p meaning is different from the previous one. This is equivalent to the statement If the fruit-salad contains mangoes, then Raju will eat it AND If Raju is eating fruit-salad, then it must be containing mangoes . q (if and only if),its
Propositional Logic The values of the complex statement varies according to the values of its constituent propositions. (p q) p q p q p q p q (q p) F F T T F T F T F F F T F T T T T T F T T F F T Converse and Contrapositive For a proposition p q, the proposition q p is called its converse and the proposition q p is called contrapositive.
Propositional Logic Truth table for converse and contrapositive q p p q q p p q F F T T T F T T F T F T F F T T T T T T
Propositional Logic Some of the logically equivalent propositions are listed below. They are also called identities. The symbol equivalence. shows the logical 1. p (p p) ( idempotence of ) 2. p (p p) ( idempotence of ) 3. (p q) (q p) ( commutativity of ) 4. (p q) (q p) ( commutativity of ) 5. (p q) r p (q r) (associativity of ) 6. (p q) r p (q r) (associativity of ) 7. (p q) ( p q) (DeMorgan's Law) 8. (p q) ( p q) (DeMorgan's Law)
Propositional Logic 9. p (q r) (p q) (p r) (Distributive) 10. p (q r) (p q) (p r) (Distributive) 11. (p True) True 12. (p False) p 13. (p True) p 14. (p False) False 15. (p p) True 16. (p p) False 17. p ( p) 18. (p q) ( p q) 19. (p q) [(p q) (q p)] 20. (p q) ( q p)
Propositional Logic Q1)Using the following statements p:Raju is tall. q:Raju is strong. What is the symbolic form of the following statement? Raju is tall but week. Answer: The statement given is equivalent to Raju is tall and Raju is not strong . So the corresponding symbolic representation is (p q). Q2) Using p and q of the previousquestion, what is the symbolic representation of the following statement? It is false that Raju is short or strong .
Propositional Logic Answer: The statement given is equivalent to the negation of Raju is not tall or Raju is strong . So it is the negation of ( p q). That is ( p q). Q3) Prove that (p p) (p (q q)) is equivalent to p q Answer: (p p) (p (q q)) p (p q) p ( p q) (p p) ( p q) F ( p q) (p q) Q4)p (q r) (p q) r
Propositional Logic Answer: Let us explore the L.H.S first p (q r) p ( q r) ( p q) r (p q) r (p q) r Q5) Prove that (p q) (p r) p (q r)
Propositional Logic Dual of a Proposition Let X be a proposition involving and as connectives, and X* be a proposition obtained from X by replacing with , with , T with F and F with T. Then X* is called the dual of X. Eg: The dual of [( p q) r] is [( p q) r] If two propositions X and Y are equivalent, then their duals X* and Y* are also equivalent. Tautology & Contradiction A proposition whose truth value is always true is called a tautology and one whose truth value is always false is called a contradiction. The negation of a tautology is a contradiction and that of a contradiction is a tautology.
Propositional Logic Q1) Which of the following is true about the proposition p ( p q) ? a)Tautology b)Contradiction c)Logically equivalent to p q d)None of these Answer: The proposition can be written as (p p) (p q) F (p q) (p q).So the answer is (c) Q2) What is the dual value of (p q) T ? Answer: The dual value of any expression is created by replacing with , with , T with F and F with T . Thus the dual value of the given expression is (p q) F.
Propositional Logic 1) Which of the following proposition is a tautology? a)(p q) p b) p (q p) c) p (p q) d) p (p q) Answer: There are two ways to solve the problem. The first method is by drawing the Truth-table for each option given and thereby finding the tautology. This approach sometimes becomes a time and space consuming approach. The second approach is by making the given expression of the form T (an expression). Where T is a known tautology (like p p , q q etc..)
Propositional Logic Option (a) can be written as (p q) p.(There is no tautology). Option (b) can be written as: p ( q p) (p q) (p p) (p q) p (there is no tautology present in this also) Option (c) can be written as: p (p q) p ( p q) (p p) (p q) T (expression) So the truth value of the statement is always true. So it is a tautology.
Propositional Logic 2) Let X denotes (p q) r and Y denotes (p r) (q r). Which of the following is a tautology? a) X Y b) X Y c) Y X d) Y X Answer: We need to draw truth tables for all the options given. p q p q F F F F F T T T T F T T F T T F r F T T T F F F T p r T T T T q r X T T T T F F T T Y T T T T T F T T Y F F F F F T F F X Y Y X Y X T T T T T T T T T F T T T F T T F F T T T T T T T T T T F F F T T T T T T F T T F F T T
Propositional Logic 3) Let a, b, c and d be propositions. Assume that equivalences a (b b) and b c hold. What is the truth value of the formula (a b) ((a c) d) ? Answer: The first equivalence a tautology as (b b)is a tautology. b c shows that b is false when c is false and b is true when c is true. (a b) ((a c) d) (T b) ((T c) d) b (c d) b (c d) ( b c) d T d This is in the form of (Tautology (any expression)).So the truth value is always true. (b b) shows that a is a
Propositional Function (Predicates) A propositional function defined on a set A is an expression p(x),which has the property that p(a) is true or false for each (a A).The set A is called the domain of p(x). The set containing elements of A for which p(a) is true is called the truth set Tp. Tp={x: x A, where p(x) is true}. Eg: Consider a propositional function p(x) defined on the set of positive numbers N. 1. Let p(x) be (2 + x > 9),its truth set is {8,9, } 2. Let p(x) be (x < 0),its truth set is { }.
Propositional Function (Predicates) Quantifiers Quantifiers are symbols used with propositional functions. There are two types of quantifiers as shown in the table below. Name Universal Quantifier Existential Quantifier Symbol Meaning for all there exists at least one Eg: If N is a set of all positive numbers, then the following statements are true. x N, (x + 3 > 2). x N, (x + 2 < 7).
Propositional Function (Predicates) Negation of Quantified Statements Consider the statement All cities are clean . Its negation can be written in two ways. 1.It is not the case that all cities are clean. 2.There exists at least one city which is not clean. Symbolically we can write, ( x M)(x is clean) ( x M)(x is not clean) or ( x M) p(x) ( x M) p(x) Where M is the set of all cities. According to Demorgan, 1) ( x A) p(x) 2) ( x A) p(x) ( x A) p(x) ( x A) p(x)
Propositional Function (Predicates) Propositional Functions with more than one variable A propositional function with more than one variable can be written as p(x1,x2, xn) over a product set A1 A2 An. Eg: Let A={1,2,3,4} and p(x,y) denotes x + y = 5. So we can write a true statement as x y p(x,y). But if we change the order of the quantifiers the statement becomes false. i.e. if we write y x p(x,y) the meaning of the statement becomes There exists a y such that for all x we have x+y=5 .(We know that no such y exists.) Negating Quantified Statements When we negate statement with more than one variable, each will be replaced by a and each will be changed to . Eg: ( x y z p(x,y,z)) x y z p(x,y,z)
Propositional Function (Predicates) Q1) What is the predicate calculus statement equivalent to the following? Every teacher is liked by some student a) x [ teacher(x) y[student(y) likes(y,x)]] b) x [ teacher(x) y[student(y) likes(y,x)]] c) y x[ teacher(x) [student(y) likes(y,x)]] d) x [ teacher(x) y[student(y) likes(y,x)]] Answer: The statement given can also be written as For all x, if x is a teacher, then there exists a student y who loves x , which can also be represented using the quantifiers as follows. x [ teacher(x) y[student(y) likes(y,x)]]. It is important to note that implication ( ) is almost used in conjunction with the quantifier . Mostly the quantifier is associated with .
Propositional Function (Predicates) Q2) P(x): x is a human being. F(x, y): x is father of y. M(x, y): x is mother of y. Write the predicate corresponding to x is the father of the mother of y Answer: If we try to interpret the predicate using three variables x, y, z we can write z is a human being and x is the father of z and z is the mother of y . This can be represented as ( z)(P(z) F(x,z) M(z,y)).
Propositional Function (Predicates) Normal Forms Some important points to remember here are, 1.An atomic proposition is a proposition containing no logical connectives. Eg: p, q, r etc. 2.A literal is either an atomic proposition or a negation of an atomic proposition. Eg: p, q, r etc. 3.A conjunctive clause is a proposition that contains only literals and the connective . Eg: ( p q r). 4. A disjunctive clause is a proposition that contains only literals and the connective . Eg: ( p q r) The problem of finding whether a given statement is a tautology or contradiction in a finite number of steps is called a decision problem. Constructing truth tables is not a practical way.
Propositional Function (Predicates) We can therefore consider alternate procedure known as reduction to normal forms. Two such normal forms are: 1.Disjunctive Normal form(DNF) 2.Conjunctive Normal form(CNF) 1.Disjunctive Normal form(DNF) A proposition in said to be in disjunctive normal form (DNF) if it is a disjunction of conjunctive clauses and literals. Eg: ( p q r) q (q r). A proposition in said to be in principal disjunctive normal form if it is a disjunction of conjunctive clauses only. Eg: ( p q r) (q r).
Propositional Function (Predicates) 2.Conjunctive Normal form(CNF) A proposition in said to be in conjunctive normal form (CNF) if it is a conjunction of disjunctive clauses and literals. Eg: ( p q r) r (q r). A proposition in said to be in principal conjunctive normal form if it is a conjunction of disjunctive clauses only. Eg: ( p q r) (q r). Q1) What is the disjunctive normal form of p (p q) ? Answer: (p p) (p q) Q2) What is the principal disjunctive normal form of p q?
Propositional Function (Predicates) Answer: A proposition in said to be in principal disjunctive normal form if it is a disjunction of conjunctive clauses only. We can write, p q ( p T) (q T) ( p (q q)) (q (p p)) ( p q) ( p q) (p q) ( p q) ( p q) ( p q) (p q)
Mathematical Reasoning We need mathematical reasoning to determine whether a mathematical argument is correct or incorrect Mathematical reasoning is important for artificial intelligence systems to reach a conclusion from knowledge and facts. We can use a proof to demonstrate that a particular statement is true. A proof consists of a sequence of statements that form an argument. Rules of Inference: Inference is the act or process of deriving a conclusion based solely on what one already knows. It uses hypotheses, axioms, definitions etc. to reach a conclusion.
Mathematical Reasoning The general form of a rule of inference is: Where p1, p2,.., pnare known as the hypotheses and q is known as the conclusion and means therefore . The rule states that if p1and p2 and andpn are all true, then q is true as well. Some valid arguments:
Mathematical Reasoning We say that an argument is valid, if whenever all its hypotheses are true, its conclusion is also true. Q1) check whether the following argument is valid or not. If it rains today, then we will not have a barbeque today. If we do not have a barbeque today, then we will have a barbeque tomorrow. Therefore, if it rains today, then we will have a barbeque tomorrow. p: It is raining today. q: We will not have a barbeque today. r: We will have a barbeque tomorrow. So the argument is of the following form:
Mathematical Reasoning Q2) check whether the following argument is valid or not. Gary is either intelligent or a good actor. If Gary is intelligent, then he can count from 1 to 10. Gary can only count from 1 to 3. Therefore, Gary is a good actor. Answer: Yes i: Gary is intelligent. a: Gary is a good actor. c: Gary can count from 1 to 10. Step 1: c Step 2: i c Step 3: i Step 4: a i Step 5: a Conclusion: a ( Gary is a good actor. )
Proving Theorems Direct proof: An implication p then q is also true. q can be proved by showing that if p is true, Example:Prove that If n is odd, then n2is odd. Assume that n is odd. Then it can be written as n = 2k + 1, where k is an integer. Consequently, n2 = (2k + 1)2. = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 Since n2 can be written in this form, it is odd Q1) Prove that If n is even, then n2 is even.
Proving Theorems Indirect proof: An implication p q is equivalent to its contra-positive q p. Therefore, we can prove p q by showing that whenever q is false, then p is also false. Q2) Give an indirect proof of the theorem If 3n + 2 is odd, then n is odd . Assume that n is even. Then n = 2k, where k is an integer. It follows that 3n + 2 = 3(2k) + 2 Therefore, 3n + 2 is even. We have shown that the contrapositive of the implication is true, so the implication itself is also true (If 3n + 2 is odd, then n is odd). = 6k + 2 = 2(3k + 1)
Mathematical Induction If we have a propositional function P(n), and we want to prove that P(n) is true for any natural number n, we do the following: Show that P(0) is true. (basis step) Show that if P(n) true then P(n + 1) is also true for any n N. (inductive step) Then P(n) must be true for any n N. (conclusion) Example: Show that n < 2n for all positive integers n. Let P(n) be the proposition n < 2n. 1. Show that P(1) is true. (basis step) P(1) is true, because 1 < 21 = 2.
Mathematical Induction 2. (inductive step) Assume that n < 2n is true. We need to show that P(n + 1) is true, i.e. n + 1 < 2n+1 We start from n < 2n: n + 1 < 2n + 1 (2n + 2n = 2n+1) Therefore, if n < 2n then n + 1 < 2n+1 Show that if P(n) is true, then P(n + 1) is true. 3. Then P(n) must be true for any positive integer. (conclusion) n < 2n is true for any positive integer. End of proof.
Mathematical Induction Q1) Using mathematical induction, prove that 1 + 2 + + n = n (n + 1)/2 Answer: Show that P(0) is true. (basis step) For n = 0 we get 0 = 0. True. Show that if P(n) then P(n + 1) (inductive step) 1 + 2 + + n = n (n + 1)/2 1 + 2 + + n + (n + 1) = n (n + 1)/2 + (n + 1) = (2n + 2 + n (n + 1))/2 = (2n + 2 + n2 + n)/2 = (2 + 3n + n2 )/2 = (n + 1) (n + 2)/2 = (n + 1) ((n + 1) + 1)/2
