66e27538b7187.pdf

MA8351 - DISCRETE MATHEMATICS  BOOKS Discrete Mathematics and Its Applications By Kenneth H. Rosen Discrete Mathematics By T.Veerarajan Discrete Mathematics By P.Sivaramakrishna Das & C.Vijayakumari  TOPICS LOGIC AND PROOFS...

MA8351 - DISCRETE MATHEMATICS  BOOKS Discrete Mathematics and Its Applications By Kenneth H. Rosen Discrete Mathematics By T.Veerarajan Discrete Mathematics By P.Sivaramakrishna Das & C.Vijayakumari  TOPICS LOGIC AND PROOFS COMBINATORICS GRAPHS ALGEBRAIC STRUCTURES LATTICES AND BOOLEAN ALGEBRA  OBJECTIVES To extend student‘s logical and mathematical maturity and ability to deal with abstraction. To introduce most of the basic terminologies used in computer science courses and application of ideas to solve practical problems. To understand the basic concepts of combinatorics and graph theory. To familiarize the applications of algebraic structures. To understand the concepts and significance of lattices and boolean algebra which are widely used in computer science and engineering. UNIT-I LOGIC AND PROOFS Propositional logic Propositional equivalences Rules of inference Predicates and quantifiers Nested quantifiers Introduction to proofs Proof methods and strategy.  Introduction Logic is the discipline that deals with the methods of reasoning. It provides rules and techniques for determining whether a given argument is valid or not.  Logical reasoning is used  In mathematics to prove theorems.  In computer science to verify the correctness of program.  In physical sciences to prove theorems.  To solve multitude problems in our every day life.  Logic is concerned with studying arguments and conclusions. There are two main components of logic Propositional Logic. Predicate Logic.  Propositional Logic The study of propositional logic consist of syntax (grammar), sematics (meaning), inference rules and derivation. Propositional logic can be considered as a language of human reasoning. It consists of  Propositional Variables denoted by 𝐩, 𝐪, 𝐫, 𝐬, …. (which are simple statements).  Propositional constants denoted by T and F (True or False)  Connectives or basic logical operators denoted by ∧, ∨, ∼, → , ↔.  Propositions (Statements) A declarative sentence which is true or false, but not both, is called a proposition or statement. Sentences which are exclamatory, interrogative or imperative in nature are not propositions. Examples: 1. New Delhi is the capital city of India. 2. How beautiful is rose? 3. 2 + 3 = 3. 4. What time is it? 5. 𝑥 + 𝑦 = 𝑧. 6. Take a cup of coffee. In the given statements (2), (4) and (6) are not propositions as they are not declarative in nature. Statements (1) and (3) are propositions but (5) is not since (1) is true, (3) is false and (5) is neither true nor false as the values of 𝑥, 𝑦 𝑎𝑛𝑑 𝑧 are not assigned.  If a proposition is true, we say that the truth value of that proposition is true, denoted by T or 1. If a proposition is false, we say that the truth value of that proposition is false, denoted by F or 0. Primitive Proposition: A proposition is primitive or primary or atomic, if it cannot be broken into simpler propositions. In otherwords, primitive propositions do not contain logical connectives.  Compound Proposition: A proposition obtained by combining two or more propositions by means of logical connectives is called a compound proposition or compound statement or molecular statement. Truth Table: A table displaying the truth values of a compound statement in terms of its component parts is called the truth table. Logical Connectives or Logical Operators: In logic, the letters 𝑝, 𝑞, 𝑟, 𝑠, …. denote propositional variables. Variables can be replaced by propositions. Example : p : 2+3=5. q : It is raining. Negation(¬), Disjunction(∨), Conjunction(∨) are called logical connectives or logical operators to form a new propositions.  NEGATION (¬)[𝑵𝑶𝑻] If p is a proposition , then the negation of p is the proposition not p and it is denoted by ¬𝐩 or ∼ 𝐩. For example: let p: Today is Monday ¬p : Today is not Monday The Truth table is given by T F F T  DISJUNCTION (∨)[OR] If p and q are two propositions then the disjunction of p and q is the compound proposition p or q and is denoted by 𝒑 ∨ 𝒒.  The compound statement 𝒑 ∨ 𝒒 is false if both of p and q is false.  𝑝 ∨ 𝑞 is true if atleast one of p and q is true. (i.e) Rule : F F implies F otherwise T. TRUTH TABLE FOR DISJUNCTION (∨) [OR] T T T T F T F T T F F F (i.e) Rule : F F implies F otherwise T.  CONJUNCTION (∧)[AND] If p and q are two propositions then the conjunction of p and q is the compound proposition p and q and is denoted by 𝒑 ∧ 𝒒.  The compound statement 𝒑 ∧ 𝒒 is true if both of p and q is true.  𝑝 ∧ 𝑞 is false if atleast one of p and q is false (i.e) Rule : T T implies T otherwise F.  TRUTH TABLE FOR CONJUNCTION (∧) [AND] T T T T F F F T F F F F (i.e) Rule : T T implies T otherwise F.  Conditional statement:(→)[If…then] If p and q are propositions the compound statement ‘if p, then q’ is called a conditional statement or implication and is denoted by 𝒑 → 𝒒.  In this implication p is called the Hypothesis and q is called the conclusion.  𝒑 → 𝒒 is false if p is true and q is false.  In other cases 𝒑 → 𝒒 is true. (i.e) Rule : T F implies F otherwise T.  NOTE: The conditional statement 𝒑 → 𝒒 is read as “ p implies q ” or “ p only if q ” or “ p is sufficient for q ” or “ q if p ”  TRUTH TABLE FOR CONDITIONAL STATEMENT (𝒑 → 𝒒) [𝑰𝒇 … 𝒕𝒉𝒆𝒏] T T T T F F F T T F F T (i.e) Rule : T F implies F otherwise T  VARIATIONS IN CONDITIONAL STATEMENTS If 𝒑 → 𝒒 is the conditional statement, then (i) 𝐪 → 𝐩 is called the Converse of 𝒑 → 𝒒 (ii) ∼ 𝐩 →∼ 𝐪 is called the Inverse of 𝒑 → 𝒒 (iii) ∼ 𝐪 →∼ 𝒑 is called the Contrapositive of 𝒑 → 𝒒.  Example(2) Write down the contrapositive , converse and inverse of the implication “ If it is raining then I get wet”. Solution: Let p : It is raining and q: I get wet The given implication is p → q Contrapositive : ¬q → ¬p “If do not get wet then it is not raining”. Converse : q → p is “If I get wet then it is raining”. Inverse : ¬p → ¬q is “ If it is not raining then I do not get wet”. Biconditional Statement (↔) [if and only if] If p and q are propositions the compound statement ‘ p if and only if q’ is called a biconditional statement and is denoted by 𝒑 ↔ 𝒒.  𝒑 ↔ 𝒒 is true whenever p and q have the same truth values and false otherwise. (i.e) Rule: T T T otherwise F F F Truth Table for Biconditional Statement (↔) T T T T F F F T F F F T  p ↔ q can also be expressed as “ p iff q” Or “ p is the necessary and sufficient condition for q” Construct truth table for 𝑷 ∨ 𝑸 → 𝑷 ∧ 𝑸. Solution: Let 𝑆 = 𝑷 ∨ 𝑸 → 𝑷 ∧ 𝑸 T T T T T T F T F F F T T F F F F F F T  Construct truth table for 𝒑 → 𝒒 → 𝒒 → 𝒑. Solution : Let 𝑆 = 𝒑 → 𝒒 → 𝒒 → 𝒑. T T T T T T F F T T F T T F F F F T T T Construct the truth table for ¬(𝑷 ∨ 𝑸) ∧ (𝑷 ∨ 𝑹) Solution: Let S = ¬(𝑷 ∨ 𝑸) ∧ (𝑷 ∨ 𝑹) T T T T F T F T T F T F T F T F T T F T F T F F T F T F F T T T F T F F T F T F F F F F T F T T T F F F F T F F  WELL FORMED FORMULAS The statement formula in which the order of finding the truth values are indicated by using parenthesis is called a well formed formulas. For example: (i) ¬ 𝑃 ∨ 𝑄 is a well formed formula (wff). (ii) 𝑃 → 𝑄 ∧ 𝑅 is not a Wff, but 𝑷 → (𝑸 ∧ 𝑹) is a Wff. (Or) (𝑷 → 𝑸) ∧ 𝑹 is also a Wff.  Order of precedence of logical connectives  Negation ¬ precedes all other operators.  Conjunction ∧ precedes disjunction ∨  The implications → and ↔ have lower precedence. But among these two → precedes ↔. Tautology and Contradiction  A statement formula which is always true irrespective of the truth values of the individual variables is called Tautology.  A statement formula which is always false is called a Contradiction.  A statement which is neither a Tautology nor a contradiction is called a contingency (or) satisfiable. Show that the statement given below is Tautology 𝑸 ∨ (𝑷 ∧ ¬𝑸) ∨ (¬𝑷 ∧ ¬𝑸) Solution: Let 𝑺 = 𝑸 ∨ (𝑷 ∧ ¬𝑸) ∨ (¬𝑷 ∧ ¬𝑸) T T F F F F T T F F T T F T F T T F F F T F F T T F T T This is a Tautology. Verify whether the following statement are Tautology or Contradiction or contingency ¬(𝒒 → 𝒓) ∧ 𝒓 ∧ (𝒑 → 𝒒). Solution : Let t=¬ 𝒒 → 𝒓 ∧𝒓, 𝑆 = ¬(𝒒 → 𝒓) ∧ 𝒓 ∧ (𝒑 → 𝒒) T T T T T F F F T T F T F T F F T F T F T F F F T F F F T F F F F T T T T F F F F T F T F T F F F F T T T F F F F F F T T F F F This is a contradiction. Verify whether the following statement are Tautology or Contradiction or contingency (𝑷 ∨ 𝑸) → 𝑷. Solution: Let S = (P ∨ Q) → P T T T T T F T T F T T F F F F T This is a Contingency.  Logical Equivalence  Two propositions P and Q are said to be logically equivalent if P ↔ Q is a Tautology.  We denoted this by 𝐏 ≡ 𝐐 (Or ) 𝑷 ⇔ 𝑸  Note:  The symbol ⇔ is sometimes used instead of ≡ to denote logical equivalence.  𝑷 ≡ 𝑸 if and only if P and Q have the same truth values.  Logical Implication let P and Q be two compound propositions, if 𝑃 → 𝑄 is a Tautology, then “P is said to be logically imply Q” and it is denoted by 𝑷 ⇒ 𝑸. It is read as “ P implies Q” We also say that “Q logically follows from P”. Note: The symbols → and ⟹ are different. → is logical connective (Or) logical operator. ⟹ is not a logical connective (Or) logical operator. Show that 𝑷 → 𝑸 and ¬𝑷 ∨ 𝑸 are logically equivalent. Method : I W.K.T, Two propositions P and Q are said to be logically equivalent if 𝑷 ↔ 𝑸 is a Tautology. To show : (𝑃 → 𝑄) ↔ (¬𝑃 ∨ 𝑄) ≡ 𝑇 Let 𝑺 = (𝑷 → 𝑸) ↔ (¬𝑷 ∨ 𝑸) T T F T T T T F F F F T F T T T T T F F T T T T Hence the given statements are logically equivalent. Method : II W.K.T, 𝑃 ≡ 𝑄 if and only if P and Q have the same truth values. Given Statements are 𝑃 → 𝑄 and ¬𝑃 ∨ 𝑄 (1) (2) (3) (4) (5) T T F T T T F F F F F T T T T F F T T T From column (4) and (5) they are logically equivalent. Show that 𝒑 → (𝒒 → 𝒓) ⇒ (𝒑 ⟶ 𝒒) → (𝒑 → 𝒓) Solution: Let s: p → (q → r) and t: (p →q) → (p → r) To prove : s → t is a Tautology. T T T T T T T T T T T F T F F F F T T F T F T T T T T T F F F F T T T T F T T T T T T T T F T F T T F T T T F F T T T T T T T F F F T T T T T T 1.Write the following statement in symbolic form : If Avinash is not in good mood or he is not busy, then he will go to New Delhi. Solution: Let 𝒑: Avinash is not in good mood. 𝒒 ∶ He is not busy. 𝒓 ∶ He will go to New Delhi. The symbolic form of the given statement is (𝒑 ∨ 𝒒) → 𝒓. 2. Negate the statement: “ John is playing football” in two different forms. Solution : Form 1 : John is not playing football. Form 2 : It is not the case that John is playing football.  3.State the truth value of “ If tigers have wings then the earth travels round the sun” Solution: Let 𝒑 ∶ Tigers have wings which is a false statement. 𝒒 ∶ Earth travels round the sun which is a true statement. We have 𝒑 → 𝒒 So we have a combination of 𝑭 → 𝑻 which is True (T) So the truth value of the given statement is T.  Duality Law The dual of a compound proposition that contains only the logical operators ∨, ∧ and ¬ is the proposition obtained by replacing each ∨ by ∧, each ∧ by ∨, each 𝑻 by 𝑭 and each 𝑭 by 𝐓, where 𝑻 and 𝑭 are special variables representing compound propositions that are tautologies and contradictions respectively.  Laws of Propositional Logic Name of the Primal Form Dual Form Law Idempotent Law Identity Law Dominant Law Complement F Law Associative Law Commutative Law  Laws of Propositional Logic Name of Primal Form Dual Form the Law Distributive Law Absorption Law Demorgan’ s Law Negation Law Equivalences Involving Conditionals 1 2 (Contrapositive) 3 4 5 6 Equivalences Involving Conditionals 1 2 3 4  1.Without using truth table , prove that ¬𝑷 ⟶ 𝑸 ⟶ 𝑹 ≡ 𝑸 ⟶ 𝑷 ∨ 𝑹 Solution : ¬𝑷 ⟶ 𝑸 ⟶ 𝑹 ≡ ¬𝑷 ⟶ ¬𝑸 ∨ 𝑹 (By 𝑷 → 𝑸 ≡ ¬𝑷 ∨ 𝑸) ≡ ¬(¬𝑷) ∨ (¬𝑸 ∨ 𝑹) (By 𝑷 → 𝑸 ≡ ¬𝑷 ∨ 𝑸) ≡ 𝑷 ∨ (¬𝑸 ∨ 𝑹) (By ¬(¬𝑷) ≡ 𝑷) ≡ (𝑷 ∨ ¬𝑸) ∨ 𝑹 (By Associative law) ≡ (¬𝑸 ∨ 𝑷) ∨ 𝑹 (By Commutative law) ≡ ¬𝑸 ∨ (𝑷 ∨ 𝑹) (By Associative law) ≡ 𝑸 ⟶ (𝑷 ∨ 𝑹) (By ¬𝑷 ∨ 𝑸 ≡ 𝑷 ⟶ 𝑸)  2. Without using truth table, show that ∼ 𝑷 ∧ ∼ 𝑸 ∧ 𝑹 ∨ 𝑸 ∧ 𝑹 ∨ 𝑷 ∧ 𝑹 ⇔ 𝑹. : Solution ∼𝑷∧ ∼𝑸∧𝑹 ∨ 𝑸∧𝑹 ∨ 𝑷∧𝑹 ⇔ (∼ 𝑷 ∧ ∼ 𝑸 ∧ 𝑹 ) ∨ ( 𝑸 ∧ 𝑹 ∨ 𝑷 ∧ 𝑹 ) (By Asso Law) ⇔ (∼ 𝑷 ∧ ∼ 𝑸 ∧ 𝑹 ) ∨ ((𝑸 ∨ 𝑷) ∧ 𝑹) (By Dis Law) ⇔ ∼ 𝑷 ∧∼ 𝑸 ∧ 𝑹 ∨ 𝑷∨𝑸 ∧𝑹 (By Asso & Comm Law) ⇔ (∼ (𝑷 ∨ 𝑸) ∧ 𝑹) ∨ ((𝑷 ∨ 𝑸) ∧ 𝑹) (By Demorgan’s Law) ⇔ (∼ 𝑷 ∨ 𝑸 ∨ 𝑷 ∨ 𝑸 ) ∧ 𝑹 (By Dis law) ⇔𝑻∧𝑹 (By Complement law, 𝒑 ∨∼ 𝒑 ≡T) ⇔𝑹 (By Identity law, 𝑷 ∧ 𝑻 ≡ 𝑷)  3. Show that (𝑃 ∨ 𝑄) ∧ ¬(¬𝑃 ∧ ¬𝑄 ∨ ¬𝑅 ) ∨ (¬𝑃 ∧ ¬𝑄) ∨ (¬𝑃 ∧ ¬𝑅) is a tautology by using equivalences. : Solution (𝑷 ∨ 𝑸) ∧ ¬(¬𝑷 ∧ ¬𝑸 ∨ ¬𝑹 ) ∨ (¬𝑷 ∧ ¬𝑸) ∨ (¬𝑷 ∧ ¬𝑹) ⇔ ( 𝑷 ∨ 𝑸 ∧ ¬ ¬𝑷 ∧ ¬𝑸 ∨ ¬𝑹 ) ∨ ( ¬𝑷 ∧ ¬𝑸 ∨ ¬𝑷 ∧ ¬𝑹 ) (By Associative law) ⇔ ( 𝑷 ∨ 𝑸 ∧ 𝑷 ∨ ¬ ¬𝑸 ∨ ¬𝑹 ) ∨ (¬𝑷 ∧ ¬𝑸 ∨ ¬𝑹 ) (By Demorgan’ s & Distributive law) ⇔ ( 𝑷 ∨ 𝑸 ∧ 𝑷 ∨ 𝑸 ∧ 𝑹 ) ∨ (¬𝑷 ∧ ¬ 𝑸 ∧ 𝑹 ) (By Demorgan’s law) ⇔ (𝑷 ∨ (𝑸 ∧ 𝑸 ∧ 𝑹 ) ∨ ¬(𝑷 ∨ 𝑸 ∧ 𝑹 ) (By Distributive law & Demorgan’ law) ⇔ (𝐏 ∨ 𝐐 ∧ 𝐐 ∧ 𝐑 ) ∨ ¬(𝐏 ∨ 𝐐 ∧ 𝐑 ) (By Associative law) ⇔ (𝑷 ∨ 𝑸 ∧ 𝑹 ) ∨ ¬(𝑷 ∨ 𝑸 ∧ 𝑹 ) (By Idempotent law, 𝑷 ∧ 𝑷 ≡ 𝑷) ⇔𝑻 (By Complement law, 𝑷 ∨ ¬𝑷 ≡ 𝑻) Hence the given proposition is a tautology.  4. Prove that (𝑷 → 𝑸) ∧ (𝑸 → 𝑹) ⟹ (𝑷 → 𝑹). Solution: To prove (𝑷 → 𝑸) ∧ (𝑸 → 𝑹) ⟹ (𝑷 → 𝑹), we have to prove that ((𝑷 → 𝑸) ∧ (𝑸 → 𝑹)) → (𝑷 → 𝑹) is a tautology. 𝑷→𝑸 ∧ 𝑸→𝑹 → 𝑷→𝑹 ≡ ( ¬𝑷 ∨ 𝑸 ∧ ¬𝑸 ∨ 𝑹 ) → (¬𝑷 ∨ 𝑹) (By 𝑷 → 𝑸 ≡ ¬𝑷 ∨ 𝑸) ≡ ¬( ¬𝑷 ∨ 𝑸 ∧ ¬𝑸 ∨ 𝑹 ) ∨ (¬𝑷 ∨ 𝑹) (By 𝑷 → 𝑸 ≡ ¬𝑷 ∨ 𝑸) ≡ (¬ ¬𝑷 ∨ 𝑸 ∨ ¬ ¬𝑸 ∨ 𝑹 ) ∨ (¬𝑷 ∨ 𝑹) (By Demorgan’s law) ≡ ( 𝑷 ∧ ¬𝑸 ∨ 𝑸 ∧ ¬𝑹 ) ∨ (¬𝑷 ∨ 𝑹) (By Demorgan’s law) ≡ 𝑷 ∧ ¬𝑸 ∨ ( 𝑸 ∧ ¬𝑹 ∨ (¬𝑷 ∨ 𝑹)) (By Associative law) ≡ 𝑷 ∧ ¬𝑸 ∨ ( 𝑸 ∨ ¬𝑷 ∨ 𝑹 ∧ (¬𝑹 ∨ ¬𝑷 ∨ 𝑹)) (By Distributive law) ≡ 𝑷 ∧ ¬𝑸 ∨ ( ¬𝑷 ∨ 𝑸 ∨ 𝑹 ∧ ((¬𝑹 ∨ 𝑹) ∨ ¬𝑷)) (By Associative law) ≡ 𝑷 ∧ ¬𝑸 ∨ ( ¬𝑷 ∨ 𝑸 ∨ 𝑹 ∧ (𝑻 ∨ ¬𝑷)) (By Complement law, 𝒑 ∨∼ 𝒑 ≡ 𝑻) ≡ 𝑷 ∧ ¬𝑸 ∨ ( ¬𝑷 ∨ 𝑸 ∨ 𝑹 ∧ 𝑻) (By Dominant law, 𝒑 ∨ 𝑻 ≡ 𝑻) ≡ 𝑷 ∧ ¬𝑸 ∨ ¬𝑷 ∨ 𝑸 ∨ 𝑹 (By Identity law, 𝒑 ∧ 𝑻 ≡ 𝒑) ≡ 𝑷 ∨ ¬𝑷 ∨ 𝑸 ∨ 𝑹 ∧ ¬𝑸 ∨ ¬𝑷 ∨ 𝑸 ∨ 𝑹 (By Distributive law) ≡ ( 𝑷 ∨ ¬𝑷) ∨ (𝑸 ∨ 𝑹 ) ∧ ¬𝑷 ∨ (¬𝑸 ∨ 𝑸) ∨ 𝑹 (By Associative law) ≡ 𝑻 ∨ (𝑸 ∨ 𝑹 ) ∧ (¬𝑷 ∨ 𝑹) ∨ 𝑻 (By Complement law, 𝒑 ∨∼ 𝒑 ≡ 𝑻) ≡𝑻∧𝑻 (By Dominant law, 𝒑 ∨ 𝑻 ≡ 𝑻) ≡𝑻 (By Idempotent law, 𝒑 ∧ 𝒑 ≡ 𝒑) Hence, (𝑷 → 𝑸) ∧ (𝑸 → 𝑹) ⟹ (𝑷 → 𝑹).  Normal Forms Elementary Product : A product of the variables and their negations in a formula is called an elementary product. Examples: 𝑃, ¬𝑃 ∧ 𝑄, ¬𝑄 ∧ 𝑃 ∧ ¬𝑃, 𝑃 ∧ ¬𝑃 𝑎𝑛𝑑 𝑄 ∧ ¬𝑄 are some examples of elementary products.  Elementary Sum: A sum of the variables and their negations in a formula is called an elementary sum. Examples: 𝑃, ¬𝑃 ∨∧ 𝑄, ¬𝑄 ∨ 𝑃 ∨ ¬𝑃, 𝑃 ∨ ¬𝑃 𝑎𝑛𝑑 𝑄 ∨ ¬𝑄 are some examples of elementary sum.  Disjunctive Normal Form Sum of elementary products is called disjunctive normal form. Example : 𝑷 ∨ 𝑷 ∧𝑸 ∨ (𝑷 ∧ ¬𝑸).  Conjunctive Normal Form Product of elementary sums is called Conjunctive normal form. Example : 𝑷 ∧ 𝑷 ∨𝑸 ∧ (𝑷 ∨ ¬𝑸).  Minterms : Given a number of variables, the products in which each variable or its negation but not both, occurs only once are called minterms. For two variables 𝑃 𝑎𝑛𝑑 𝑄, the minterms are 𝑷 ∧ 𝑸, 𝑷 ∧ ¬𝑸, ¬𝑷 ∧ 𝑸 𝒂𝒏𝒅 ¬𝑷 ∧ ¬𝑸. For three variables 𝑃, 𝑄 𝑎𝑛𝑑 𝑅, the minterms are 𝑷 ∧ 𝑸 ∧ 𝑹, ¬𝑷 ∧ 𝑸 ∧ 𝑹, 𝑷 ∧ ¬𝑸 ∧ 𝑹, 𝑷 ∧ 𝑸 ∧ ¬𝑹, ¬𝑷 ∧ ¬𝑸 ∧ 𝑹, ¬𝑷 ∧ 𝑸 ∧ ¬𝑹, 𝑷 ∧ ¬𝑸 ∧ ¬𝑹 and ¬𝑷 ∧ ¬𝑸 ∧ ¬𝑹.  Maxterms : Given a number of variables, the sums in which each variable or its negation but not both, occurs only once are called maxterms. For two variables 𝑃 𝑎𝑛𝑑 𝑄, the maxterms are 𝑷 ∨ 𝑸, 𝑷 ∨ ¬𝑸, ¬𝑷 ∨ 𝑸 𝒂𝒏𝒅 ¬𝑷 ∨ ¬𝑸. For three variables 𝑃, 𝑄 𝑎𝑛𝑑 𝑅, the maxterms are 𝑷 ∨ 𝑸 ∨ 𝑹, ¬𝑷 ∨ 𝑸 ∨ 𝑹, 𝑷 ∨ ¬𝑸 ∨ 𝑹, 𝑷 ∨ 𝑸 ∨ ¬𝑹, ¬𝑷 ∨ ¬𝑸 ∨ 𝑹, ¬𝑷 ∨ 𝑸 ∨ ¬𝑹, 𝑷 ∨ ¬𝑸 ∨ ¬𝑹 and ¬𝑷 ∨ ¬𝑸 ∨ ¬𝑹.  Principal Disjunctive Normal Form (PDNF) A formula consisting of disjunctions of minterms in the variable only is known as its principal disjunctive normal form. Example : (𝑷 ∧ 𝑸) ∨ (¬𝑷 ∧ ¬𝑸).  Principal Conjunctive Normal Form (PCNF) A formula consisting of conjunctions of maxterms in the variable only is known as its principal conjunctive normal form. Example : (𝑷 ∨ 𝑸) ∧ (¬𝑷 ∨ ¬𝑸). Steps involved in finding PDNF:  First obtain DNF of the formula.  To get the minterms in the disjunctions, the missing factors are introduced through the complement law, 𝑃 ∨ ¬𝑃 ≡ 𝑇.  Then apply distributive law.  Identical minterms appearing in the disjunctions are then deleted as 𝑃 ∨ 𝑃 ≡P.  Steps involved in finding PCNF:  First find PDNF of the given formula 𝐴.  To find PCNF, we use the fact that 𝐴 ≡ ∼ ∼𝐴.  Apply Demorgan’s law to the PDNF of ∼ 𝐴 repeatedly. Note: If the PDNF of a formula 𝐴 is known, the PDNF of ∼ 𝐴 will consist of the disjunctions of the remaining minterms which are not included in the PDNF of 𝐴. Find PDNF of 𝑷 ∧ 𝑸 ∨ ¬𝑷 ∧ 𝑹 ∨ 𝑸 ∧ 𝑹. Also find PCNF. Solution: Given 𝑷 ∧ 𝑸 ∨ ¬𝑷 ∧ 𝑹 ∨ 𝑸 ∧ 𝑹 ≡ 𝑃∧𝑄 ∧𝑇 ∨ ¬𝑃 ∧ 𝑅 ∧ 𝑇 ∨ ( 𝑄 ∧ 𝑅 ∧ 𝑇) (By 𝑷 ∧ 𝑻 ≡ 𝑷) ≡ 𝑃 ∧ 𝑄 ∧ 𝑅 ∨ ¬𝑅 ∨ ¬𝑃 ∧ 𝑅 ∧ 𝑄 ∨ ¬𝑄 ∨ ( 𝑄 ∧ 𝑅 ∧ 𝑃 ∨ ¬𝑃 ) (By 𝑷 ∨ ¬𝑷 ≡ 𝑻)  ≡ (𝑃 ∧ 𝑄 ∧ 𝑅) ∨ (𝑃 ∧ 𝑄 ∧ ¬𝑅) ∨ (¬𝑃 ∧ 𝑄 ∧ 𝑅) ∨ (¬𝑃 ∧ ¬𝑄 ∧ 𝑅) ∨ (𝑃 ∧ 𝑄 ∧ 𝑅) ∨ (¬𝑃 ∧ 𝑄 ∧ 𝑅) (By distributive law) ≡ (𝑃 ∧ 𝑄 ∧ 𝑅) ∨ (𝑃 ∧ 𝑄 ∧ ¬𝑅) ∨ (¬𝑃 ∧ 𝑄 ∧ 𝑅) ∨ (¬𝑃 ∧ ¬𝑄 ∧ 𝑅) (By 𝑷 ∨ 𝑷 ≡ 𝑷) which is disjunction of minterms.(PDNF) PCNF ≡ ¬(𝒅𝒊𝒔𝒋𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒐𝒇 𝒓𝒆𝒎𝒂𝒊𝒏𝒊𝒏𝒈 𝒎𝒊𝒏𝒕𝒆𝒓𝒎𝒔) ≡ ¬[(𝑃 ∧ ¬𝑄 ∧ 𝑅) ∨ (¬𝑃 ∧ 𝑄 ∧ ¬𝑅) ∨ (𝑃 ∧ ¬𝑄 ∧ ¬𝑅) ∨ (¬𝑃 ∧ ¬𝑄 ∧ ¬𝑅)] ≡ ¬(𝑃 ∧ ¬𝑄 ∧ 𝑅) ∧ ¬(¬𝑃 ∧ 𝑄 ∧ ¬𝑅) ∧ ¬(𝑃 ∧ ¬𝑄 ∧ ¬𝑅) ∧ ¬(¬𝑃 ∧ ¬𝑄 ∧ ¬𝑅) (By Demorgan’s law) ≡ (¬𝑃 ∨ 𝑄 ∨ ¬𝑅) ∧ (𝑃 ∨ ¬𝑄 ∨ 𝑅) ∧ (¬𝑃 ∨ 𝑄 ∨ 𝑅) ∧ (𝑃 ∨ 𝑄 ∨ 𝑅). (By Demorgan’s law) which is conjunction of maxterms. Obtain PDNF of ¬𝑷 → 𝑹 ∧ 𝑸 ↔ 𝑷. Also find PCNF. Solution: Given ¬𝑷 → 𝑹 ∧ 𝑸 ↔ 𝑷 ≡ ¬(¬𝐏) ∨ 𝐑 ∧ ¬𝐐 ∨ 𝐏 ∧ ¬𝐏 ∨ 𝐐 ) (By 𝐏 → 𝐐 ≡ ¬𝐏 ∨ 𝐐 𝐚𝐧𝐝 𝐏 ↔ 𝐐 ≡ (¬𝐏 ∨ 𝐐) ∧ (¬𝐐 ∨ 𝐏)) ≡ 𝐏 ∨ 𝐑 ∧ (𝐏 ∨ ¬𝐐) ∧ (¬𝐏 ∨ 𝐐) (By double negation & commutative law) ≡ 𝑃∨𝑅 ∨𝐹 ∧ 𝑃 ∨ ¬𝑄 ∨ 𝐹 ∧ ( ¬𝑃 ∨ 𝑄 ∨ 𝐹) (By 𝑷 ∨ 𝑭 ≡ 𝑷)  ≡ 𝑃 ∨ 𝑅 ∨ (𝑄 ∧ ¬𝑄 ∧ 𝑃 ∨ ¬𝑄 ∨ (𝑅 ∧ ¬𝑅 ∧ ( ¬𝑃 ∨ 𝑄 ∨ (𝑅 ∧ ¬𝑅)) (By 𝑷 ∧ ¬𝑷 ≡ 𝑭) ≡ (P ∨ 𝑄 ∨ 𝑅) ∧ (𝑃 ∨ ¬𝑄 ∨ 𝑅) ∧ (𝑃 ∨ ¬𝑄 ∨ 𝑅) ∧ (P ∨ ¬𝑄 ∨ ¬𝑅) ∧ (¬𝑃 ∨ 𝑄 ∨ 𝑅) ∧ (¬𝑃 ∨ 𝑄 ∨ ¬𝑅) (By distributive law) ≡ P ∨ 𝑄 ∨ 𝑅 ∧ 𝑃 ∨ ¬𝑄 ∨ 𝑅 ∧ P ∨ ¬𝑄 ∨ ¬𝑅 ∧ (¬𝑃 ∨ 𝑄 ∨ 𝑅) ∧ (¬𝑃 ∨ 𝑄 ∨ ¬𝑅) (By 𝑷 ∧ 𝑷 ≡ 𝑷) which is conjunction of maxterms. (PCNF) PDNF ≡ ¬(𝐜𝐨𝐧𝒋𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒐𝒇 𝒓𝒆𝒎𝒂𝒊𝒏𝒊𝒏𝒈 𝒎𝒂𝒙𝒕𝒆𝒓𝒎𝒔) ≡ ¬[(𝑃 ∨ 𝑄 ∨ ¬𝑅) ∧ (¬𝑃 ∨ ¬𝑄 ∨ 𝑅) ∧ (¬𝑃 ∨ ¬𝑄 ∨ ¬𝑅)] ≡ ¬(𝑃 ∨ 𝑄 ∨ ¬𝑅) ∨ ¬(¬𝑃 ∨ ¬𝑄 ∨ 𝑅) ∨ ¬(¬𝑃 ∨ ¬𝑄 ∨ ¬𝑅) (By Demorgan’s law) ≡ (¬𝑃 ∧ ¬𝑄 ∧ 𝑅) ∨ (𝑃 ∧ 𝑄 ∧ ¬𝑅) ∨ (𝑃 ∧ 𝑄 ∧ 𝑅). (By Demorgan’s law) which is disjunction of minterms. Note : The 𝐏𝐃𝐍𝐅 and 𝐏𝐂𝐍𝐅 can be obtained by constructing truth tables by finding minterms corresponding to 𝐓 and maxterms corresponding to 𝐅 respectively. 3.Find PDNF and PCNF of (𝑷 ∧ 𝑸) ∨ ¬𝑷 ∧ 𝑹 using truth table. Solution : T T T F T F T T T F F T F T T F T F F F F T F F F F F F F T T T F T T F T F T F F F F F T T F T T F F F T F F F 𝐏𝐃𝐍𝐅 ≡ 𝐏 ∧ 𝐐 ∧ 𝐑 ∨ 𝐏 ∧ 𝐐 ∧ ¬𝐑 ∨ ¬𝐏 ∧ 𝐐 ∧ 𝐑 ∨ (¬𝐏 ∧ ¬𝐐 ∧ 𝐑). 𝐏𝐂𝐍𝐅 ≡ ¬𝐏 ∨ 𝐐 ∨ ¬𝐑 ∧ ¬𝐏 ∨ 𝐐 ∨ 𝐑 ∧ 𝐏 ∨ ¬𝐐 ∨ 𝐑 ∧ 𝐏 ∨ 𝐐 ∨ 𝐑.  Inference Theory Inference theory is concerned with the inferring of a conclusion from certain hypothesis or basic assumptions, called premises, by applying certain principles of reasoning, called rules of inference. Note : Suppose that an implication of the form 𝒑𝟏 ∧ 𝒑𝟐 ∧ 𝒑𝟑 ∧ ⋯ ∧ 𝒑𝒏 ⟶ 𝒒 is a tautology, then we say that 𝒒 logically follows from 𝒑𝟏 , 𝒑𝟐 , … , 𝒑𝒏. The 𝒑𝒊 ’s are called the hypotheses or premises and 𝒒 is called the conclusion.  RULES OF INFERENCE When a conclusion is derived from a set of premises by using rules of reasoning, then such a process of derivation is called a deduction or a formal proof and the argument is called a valid argument.  We state two basic rules of inference called rules 𝐏 and 𝐓. RULE 𝐏 : A premise may be introduced at any step in the derivation. RULE 𝐓 :A formula may be introduced in the derivation, if 𝑺 is tautologically implied by one or more preceding formulas in the derivation.  RULES OF INFERENCE RULE IN TAUTOLOGICAL NAME OF THE RULE FORM SIMPLIFICATION q ADDITION CONJUNCTION MODUS PONENS MODUS TOLLENS HYPOTHETICAL SYLLOGISM DISJUNCTIVE SYLLOGISM 1.Show that 𝑺 is a valid inference from the premises 𝑷 →∼ 𝑸, 𝑸 ∨ 𝑹, ∼ 𝑺 → 𝑷 and ∼ 𝑹. Solution: Step No Statement Reason 1 Rule P 2 Rule P 3 Rule T 1,2 Disjunctive Syllogism. 4 Rule P 5 Rule T 3,4 Modus Tollens 6 Rule P Rule T 5,6 Modus Tollens and 7 double negation. 2.Show that 𝑹 ∧ (𝑷 ∨ 𝑸) is a valid conclusion from the premises 𝑷 ∨ 𝑸, 𝑸 → 𝑹, 𝑷 → 𝑴, ¬𝑴. : Solution Step No Statement Reason 1 Rule P 2 Rule P 3 Rule T 1.2 Modus Tollens 4 Rule P 5 Rule T 3,4 Disjunctive Syllogism 6 Rule P 7 Rule T 5,6 Modus Ponens 8 Rule T 7,4 Conjunction. 3.Show that (𝑷 → 𝑸) ∧ (𝑹 → 𝑺), 𝑸 → 𝑴 ∧ 𝑺 → 𝑵 , ¬(𝑴 ∧ 𝑵) and 𝑷 → 𝑹 ⟹ ¬𝑷. SOLUTION : Step No. Statement Reason 1 Rule P 2 Rule T, 1 Simplification 3 Rule T, 1 Simplification 4 Rule P 5 Rule T, 4 Simplification 6 Rule T, 4 Simplification Step No Statement Reason 7 Rule T 2,5 Hypothetical Syllogism 8 Rule T 3,6 Hypothetical Syllogism 9 Rule P 10 Rule T 9,8 Hypothetical Syllogism Rule T 7,10 11 12 Rule P 13 Rule T 11,12 Modus Tollens 4.Using rules of inference, show that 𝑺 ∨ 𝑹 is tautologically implied by (𝑷 ∨ 𝑸) ∧ (𝑷 → 𝑹) ∧ (𝑸 → 𝑺) Solution: Step No Statement Reason 1 Rule P 2 Rule T 1, 3 Rule T 2, 4 Rule P 5 Rule T 3,4 Hypothetical Syllogism 6 Rule T 5, 7 Rule T 6, 8 Rule P 9 Rule T 7,8 Hypothetical Syllogism 10 Rule T 9, 11 Rule T 10, RULE CP OR RULE OF CONDITIONAL PROOF In addition to the two basic rules of inference 𝑷 and 𝑻, we have one more basic rule called Rule CP, which is stated below: RULE CP : If a formula 𝑆 can be derived from another formula 𝑟 and a set of premises, then the statement 𝑟 → 𝑠 can be derived from the set of premises alone. NOTE : If the conclusion is of the form 𝒓 → 𝒔, we will take 𝒓 as an additional premise and derive 𝒔 using the given premises and 𝒓. 5.Show that 𝑹 → 𝑺 can be derived from the premises 𝑷 → 𝑸 → 𝑺 , ¬𝑹 ∨ 𝑷 and 𝑸. Solution: Step No Statement Reason 1 Rule P 2 Rule P 3 Rule T 1.2 Disjunctive Syllogism 4 Rule P 5 Rule T 3,4 Modus Ponens 6 Rule P 7 Rule T 5,6 Modus Ponens 8 S Rule CP. 6.Prove that 𝑨 → ¬𝑫 is a conclusion from the premises 𝑨 → (𝑩 ∨ 𝑪), 𝑩 → ¬𝑨 and 𝐃 → ¬C by using conditional proof. Solution : Step No Statement Reason 1 Rule P (Additional Premise) 2 Rule P 3 Rule T 1,2 Modus Ponens 4 Rule P 5 B Rule T 1,4 Modus Tollens 6 Rule T 5,3 Disjunctive Syllogism 7 Rule P 8 Rule T 6,7 Modus Tollens 9 D Rule CP  INCONSISTENT PREMISES A set of premises 𝑯𝟏 , 𝑯𝟐 , … … …. , 𝑯𝒏 is said to be inconsistent, if their conjunctions implies a contradiction. (i.e) 𝑯𝟏 ∧ 𝑯𝟐 ∧ ⋯ ∧ 𝑯𝒏 ⇒ 𝑹 ∧ ¬𝑹, for some formula 𝑹. A set of premises is said to be consistent if it is not inconsistent. 7. Show that the premises 𝑷 → 𝑸, 𝑷 → 𝑹, 𝑸 → ¬𝑹, 𝑷 are inconsistent. Solution: Step Statement Reason 1 Rule P 2 Rule P 3 Rule T 1,2 Modus Ponens 4 Rule P 5 Rule T 3,4 Modus Ponens 6 Rule P 7 Rule T 5,6 Modus Tollens 8 Rule T 1,7 Conjunction. Hence the given premises are inconsistent. 8. Show that the premises 𝒂 → (𝒃 → 𝒄), 𝒅 → (𝒃 ∧ ¬𝒄) and (𝒂 ∧ 𝒅) are inconsistent. Solution: Step Statement Reason 1 Rule P 2 Rule T 1, Simplification 3 Rule T 1, Simplification 4 Rule P 5 Rule T 2,4 Modus Ponens  Step Statement Reason 6 Rule P 7 Rule T 3,6 Modus Ponens 8 Rule T 7, Simplification 9 Rule T 7, Simplification 10 Rule T 8,5 Modus Ponens 11 Rule T 10,9 Conjunction Hence the given premises are inconsistent.  INDIRECT METHOD OF PROOF The notion of inconsistency is used to derive a proof at times. This procedure is called the indirect method of proof or proof by contradiction or reduction.  The technique used in indirect method:  Introduce the negation of the desired conclusion as a new premise.  From the new premise, together with the given premises derive a contradiction. 9. Use indirect method of proof to derive 𝑷 → ¬𝑺 from the premises 𝑷 → (𝑸 ∨ 𝑹), 𝑸 → ¬𝑷, 𝑺 → ¬𝑹 and 𝑷. Solution: By indirect method of proof , first we find negation of the conclusion and take it as additional premise. ¬(𝑷 → ¬𝑺) ≡ ¬(¬𝑷 ∨ ¬𝑺) (By 𝑷 → 𝑸 ≡ ¬𝑷 ∨ 𝑸) ≡𝑷∧𝑺 (By Demorgan’s law) Step Statement Reason 1 Rule P (Additional Premise) 2 Rule T 1, Simplification 3 Rule T 1, Simplification 4 Rule P 5 Rule T 2,4 Modus Ponens Step Statement Reason 6 Rule P 7 Rule T 3,6 Modus Ponens 8 Rule T 5,7 Disjunctive Syllogism 9 Rule P 10 Rule P 11 Rule T 9,10 Modus Tollens 12 Rule T 8,11 Conjunction 10. Using indirect method, show that 𝑹 → ¬𝑸, 𝑹 ∨ 𝑺 𝑺 → ¬𝑸, 𝑷 → 𝑸 ⇒ ¬𝑷. Solution: By inditect method of proof, first we find negation of the conclusion and take it as additional premise. ¬(¬𝑷) ≡ 𝑷 Step Statement Reason 1 Rule P (Additional Premise) 2 Rule P 3 Rule T 1,2 Modus Ponens Step Statement Reason 4 Rule P 5 Rule T 3,4 Modus Tollens 6 Rule P 7 Rule T 5,6 Disjunctive Syllogism 8 Rule P 9 Rule T 7,8 Modus Ponens 10 Rule T 3,9 Conjunction 1. Find the validity of the following argument: If the prices of fuel increases then the prices of commodities increase. If the prices of fuel increases then oil companies make profit. If the prices of commodities increase then oil companies do not make profit. Hence the price of fuel does not increase. : Solution Let P : The prices of fuel increases. Q : The prices of commodities increase. R : Oil companies make profit. The premises are 𝑷 → 𝑸, 𝑷 → 𝑹, 𝑸 → ¬𝑹 ⇒ ¬𝑷.  Step Statement Reason 1 Rule P 2 Rule P 3 Rule T 1,2 Hypothetical Syllogism 4 Rule T 3, 5 Rule T 4, 6 Rule P 7 Rule T 6,5 Hypothetical Syllogism 8 Rule T 7, 9 Rule T 8, Hence the given argument is valid. 2.Show that “It rained” is a conclusion obtained from the statements. “If it does not rain or if there is no traffic dislocation, then the sports day will be held and the cultural programme will go on”. “If the sports day is held , the trophy will be awarded” and “the trophy was not awarded”. : Solution Let P : It rains Q : There is traffic dislocation R : Sports day will be held S : Cultural programme will go on T : Trophy will be awarded. The premises are (¬𝑷 ∨ ¬𝑸) → (𝑹 ∧ 𝑺), 𝑹 → 𝑻, ¬𝑻 ⇒ 𝑷 Step Statement Reason 1 Rule P 2 Rule P 3 Rule T 1,2 Modus Tollens 4 Rule T 3, Addition 5 Rule T 4, Demorgan’s law 6 Rule P 7 Rule T 6, Demorgan’s law 8 Rule T 5,7 Modus Tollens 9 Rule T 8, 10 Rule T 9, Simplification  Predicate Calculus Sometimes it was not possible to express the fact that any two atomic statements have some features in common. In order to investigate questions of this nature, we introduce the concept of a predicate in an atomic statement. The logic based upon the analysis of predicate in any statement is called predicate calculus. Example 1: 1) John is a Bachelor. 2) Smith is a Bachelor. Here “is a Bachelor” is called predicate. Denote the predicate by 𝑩, John by 𝒋 and Smith by 𝒔. Therefore, the two statements (1) and (2) can be written as 𝑩(𝒋) and 𝑩(𝒔).  In general any statement of the type 𝑷 is 𝑸 where is 𝑸 is a predicate and 𝒑 is the subject can be denoted by 𝑸(𝒑). Example 2: “John is a Bachelor and this painting is red”. This can be written in symbolic form as 𝑩(𝒋) ∧ 𝑹(𝒑) where 𝑩 is a Bachelor, 𝒋 denote John, 𝑹 denotes red and 𝒑 denotes painting.  Universe of Discourse The domain (universe of discourse or simply universe) of a predicate variable is the set of all possible values that may be substituted in place of the variable. The statement 𝒙 < 𝟓 can be denote by 𝑷(𝒙), where 𝑷 is the predicate “is less than 5” and 𝒙 is the variable.  When a particular value is assigned to 𝒙, 𝐏(𝒙) is a proposition and has a truth value. Example: 1) 𝐏(𝟐) is 𝟐 < 𝟓, which is true. 2) 𝐏(𝟔) is 𝟔 < 𝟓, which is false. The statement 𝒙 − 𝒚 = 𝟏 can be denoted by 𝑷(𝒙, 𝒚), where 𝑷 is the predicate and 𝒙, 𝒚 are the variables. When particular values are assigned to 𝒙 and 𝒚, 𝑷(𝒙, 𝒚) is a proposition and has a truth value.  There is another way to get propositions or statements from predicates which is known as quantification. There are two types of quantifiers 1. Universal quantifier. 2. Existential quantifier.  Universal Quantifier Let 𝑷(𝒙) be a proposition function with universe 𝑨. The statement “for every 𝒙 ∈ 𝑨, 𝑷(𝒙) is true” is the universal quantification of 𝑷(𝒙). It is denoted by ∀𝒙 ∈ 𝑨, 𝑷(𝒙) or ∀𝒙 𝑷(𝒙). Note : The phrases “for every 𝒙”, “for all 𝒙”, “for each 𝒙” have the same meaning and all these can be denoted by (𝒙) or ∀𝒙.  ∀𝒙 𝑷(𝒙) has a truth value and it is assigned as below ∀𝒙 𝑷(𝒙) is true if it is true for every 𝒙 ∈ 𝑨. ∀𝒙 𝑷(𝒙) is false iff 𝑷(𝒙) is false for atleast one 𝒙 in 𝑨. Example: Let 𝑷(𝒙) be the statement "𝒙 < 𝟓“. What is the truth value of the quantification ∀𝒙 𝑷(𝒙), where the universe of discourse is 𝑹 (the set of all real numbers). Solution: Clearly 𝑷 𝒙 is not true for all 𝒙 , since 𝑷 𝟔 : 𝟔 < 𝟓 is false. Therefore, ∀𝒙 𝑷(𝒙) is false.  Existential Quantifier Let 𝑷(𝒙) be a propositional function with universe 𝑨, if there exists an 𝒙 in 𝑨 such that 𝑷(𝒙) is true, then we write it as ∃𝒙 𝑷(𝒙) or ∃𝒙 ∈ 𝑨 𝑷(𝒙). The quantifier “∃𝒙“ is called the existential quantifier and it denotes the phrase “there exists”. Note : The phrases “there is a 𝒙”, “there is some 𝒙”, “there is atleast one 𝒙”, have the same meaning as “there exists an 𝒙” and all these can be denoted by ∃𝐱. Example: Let 𝑷(𝒙) : 𝒙 + 𝟐 < 𝟓 The existential quantification of 𝑷(𝒙), ∃𝒙 𝑷(𝒙) is a true statement because 𝑷 𝟐 : 𝟐 + 𝟐 < 𝟓 is a true statement.  Free and Bound Variables Given a formula containing a part of the form 𝒙 𝑷(𝒙) or ∃𝒙 𝑷(𝒙), such a part is called an 𝒙-bound part of the formula. Any occurrence of 𝒙 in an 𝒙-bound part of a formula is called a bound occurrence of 𝒙, while any occurrence of 𝒙 or of any variable that is not a bound occurrence is called a free occurrence.  Further the formula 𝑷(𝒙) either in 𝒙 𝑷(𝒙) or in ∃𝒙 𝑷(𝒙) is described as the scope of the quantifier. Example : 1) 𝐱 𝐏(𝐱, 𝐲). 𝑷(𝒙, 𝒚) is the scope of the quantifier and all occurences of 𝒙 are bound occurences, while the occurrence of 𝒚 is a free occurrence. 2) 𝐱 𝐏 𝐱 →𝐐 𝐱. Scope of the universal quantifier is 𝐏 𝒙 → 𝐐 𝒙 and all occurences of 𝒙 are bound. 3) (𝐱)(𝐏 𝐱 → ∃𝐲 𝐑 𝐱, 𝐲 ) The scope of (𝒙) is 𝑷(𝒙) → ∃𝒚 𝑹(𝒙, 𝒚) while the scope of (∃𝒚) is 𝑹(𝒙, 𝒚). All occurrences of 𝒙 and 𝒚 are bound occurences. 1. Give the symbolic form of “Some men are giants”. Solution : Let 𝑴 𝒙 : 𝒙 is a man. 𝑮 𝒙 ∶ 𝒙 is a giant. The symbolic form is ∃𝐱 𝐌 𝐱 ∧ 𝐆 𝐱. 2. Give the symbolic form of “All cats have tails” and “No cats have tail”. Solution : Let 𝐂 𝐱 ∶ 𝐱 is a cat. 𝐓 𝐱 ∶ 𝐱 has a tail. The symbolic form of (1) is ∀𝐱 𝐂 𝐱 →𝐓 𝐱. The symbolic form of (2) is ∀𝒙 𝑪 𝒙 → ¬𝑻 𝒙. 3.Negate the statement : “ Every student in this class is intelligent” in two different ways. Solution : Form 1 : There is a student in this class who is not intelligent. Form 2 : It is not the case that every student in this class is intelligent. 4. Find the truth value of ∀𝒙 𝒙𝟐 ≥ 𝒙 if the universe of discourse consists of all real numbers. Also write the negation of the given statement. Solution : The truth value of the given statement is False. For example for the real number 𝒙 = 𝟎. 𝟓, 𝒙𝟐 = 𝟎. 𝟐𝟓 < 𝒙 = 𝟎. 𝟓 Negation of the given statement is ¬ ∀𝒙 𝒙𝟐 ≥ 𝒙 = ∃𝒙 ¬ 𝒙𝟐 ≥ 𝒙 = ∃𝒙 𝒙𝟐 < 𝒙.  Inference Theory for Predicate Calculus In addition to rules of inference for propositions, we shall now consider some important rules of inference for quantified statements. During the course of derivation it may be necessary to eliminate the quantifiers. This is done by rules of specification 𝐔𝐒 and 𝐄𝐒.  Once the quantifiers are eliminated, we proceed as in propositional calculus to reach the conclusion. Sometimes we may require to reach the conclusion in quantified form. This is done by rules of generalization 𝐔𝐆 and 𝐄𝐆.  Rule 𝐔𝐒 : Universal specification is the rule of inference which says that we can conclude 𝐏(𝐜) is true for an arbitrary element 𝐜 of the universe of discourse if ∀𝐱 𝐏(𝐱) is true. ∀𝐱 𝐏 𝐱 ⇒ 𝐏(𝐜) for some 𝐜.  Rule 𝐄𝐒 : Existential specification is the rule of inference which says that there is an element 𝐜 in the universe of discourse for which 𝐏(𝐜) is true if ∃𝐱 𝐏 𝒙 is true. ∃𝒙 𝐏 𝒙 ⇒ 𝐏(𝐜) for particular 𝐜.  Rule 𝐔𝐆 : Universal generalization is the rule of inference which says that ∀𝐱 𝐏(𝐱) is true if 𝐏(𝐜) is true for an arbitrary element 𝒄 of the universe of discourse. 𝐏 𝐜 ⇒ ∀𝐱 𝐏(𝐱) for an arbitrary 𝐜.  Rule 𝐄𝐆 : Existential generalization is the rule of inference which says that for a particular element 𝐜 of the universe of discourse if 𝐏(𝐜) is true then ∃𝐱 𝐏(𝐱) is true. 𝐏 𝐜 ⇒ ∃𝐱 𝐏(𝐱) for some 𝐜.  1.Prove that ∀𝐱 𝑷 𝒙 → 𝑸 𝒙 , ∀𝒙 𝑹 𝒙 → ¬𝑸 𝒙 ⇒ ∀𝒙 𝑹 𝒙 → ¬𝑷 𝒙. Solution : Step Statement Reason 1 Rule P 2 Rule US, 1 3 Rule P 4 Rule US, 3 5 Rule T 2, Contrapositive 6 Rule T 4,5 Hypothetical Syllogism 7 Rule UG, 6  2. Use indirect method to prove that the conclusion ∃𝐳 𝐐(𝐳) follows from the premises ∀𝒙 𝑷 𝒙 → 𝑸 𝒙 and ∃𝒚 𝑷(𝒚). Solution : By using indirect method, we take ¬ ∃𝐳 𝐐(𝐳) as additional premise. Step Statement Reason 1 Rule P (Additional Premise) 2 Rule T 1, Demorgan’s law 3 Rule US, 2 Step Statement Reason 4 Rule P 5 Rule US, 4 6 Rule P 7 Rule ES, 6 8 a) Rule T 7,5 Modus Ponens 9 Rule T 8,3 Conjunction 10 Contradiction  3. Use indirect method of proof to prove that ∀𝐱 𝑷 𝒙 ∨ 𝑸 𝒙 ⇒ ∀𝐱 𝐏 𝐱 ∨ ∃𝐱 𝐐(𝐱). Solution : By using indirect method, we take ¬ ∀𝐱 𝐏 𝐱 ∨ ∃𝐱 𝐐 𝐱 as additional premise. Step Statement Reason 1 Rule P (Additional Premise) 2 Rule T 1, Demorgan’s law 3 Rule T 2, Simplification 4 Rule T 2, Smplification Step Statement Reason 5 Rule T 3, 6 Rule T 4, 7 Rule ES, 5 8 Rule US, 6 9 Rule P 10 Rule US, 9 11 Rule T 10,7 Disjunctive Syllogism 13 Rule T 11,8 Conjunction 14 F Contradiction  4. Prove that ∀𝒙 𝑷 𝒙 → 𝑸 𝒚 ∧𝑹 𝒙 , ∃𝒙 𝑷 𝒙 ⇒ 𝑸 𝒚 ∧ ∃𝒙 𝑷 𝒙 ∧ 𝑹 𝒙. Solution : Step Statement Reason 1 Rule P 2 Rule US, 1 3 Rule P 4 Rule ES, 3 5 Rule T 4,2 Modus Ponens 6 Rule T 5, Simplification 7 Rule T 5, Simplification 8 Rule T 4,7 Conjunction 9 Rule EG, 8 10 Rule T 6,9 Conjunction 1.Establish the validity of the following argument All men are mortal. Socrates is a man. Therefore Socrates is mortal. Solution : Let 𝑯 𝒙 ∶ 𝒙 is a man. 𝑴 𝒙 ∶ 𝒙 is a mortal. The premises are 𝒙 𝑯 𝒙 →𝑴 𝒙 , 𝑯 𝒔 ⇒𝑴 𝒔. Step Statement Reason 1 Rule P 2 Rule US, 1 3 Rule P 4 Rule T 3,2 Modus Ponens Hence, the given argument is valid. 2. Use of rule of inference to prove that the premises “ A student in this class has not read the book” and “ Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book”. Solution : Let 𝐂 𝐱 ∶ 𝐱 is in this class. 𝐁 𝐱 ∶ 𝐱 has read the book. 𝐏 𝐱 ∶ 𝐱 passed the exam. The premises are ∃𝐱 𝐂 𝐱 ∧ ¬𝐁 𝐱 , ∀𝐱 𝐂 𝐱 → 𝐏 𝐱 ⇒ ∃𝒙 𝑷 𝒙 ∧ ¬𝑩 𝒙. Step Statement Reason 1 Rule P 2 Rule ES, 1 3 Rule T 2, Simplification 4 Rule T 2, Simplification 5 Rule P 6 Rule US, 5 7 Rule T 3,6 Modus Ponens 8 Rule T 7,4 Conjunction 9 Rule EG, 8 3. Verify the validity of the following argument. Every living thing is a plant or an animal. John’s gold fish is alive and it is not a plant. All animals have hearts. Therefore, John’s gold fish has a heart. Solution : Universe of discourse : Set of all living things. 𝑷 𝒙 ∶ 𝒙 is a plant. 𝑨 𝒙 ∶ 𝒙 is an animal. 𝑯 𝒙 ∶ 𝒙 has a heart. 𝒈 ∶ John’s gold fish. The premises are 𝒙 𝑷 𝒙 ∨𝑨 𝒙 , ¬𝑷 𝒈 , 𝒙 𝑨 𝒙 →𝑯 𝒙 ⇒𝑯 𝒈. Step Statement Reason 1 Rule P 2 Rule US, 1 3 Rule P 4 Rule T 3,2 Disjunctive Syllogism 5 Rule P 6 Rule US, 5 7 Rule T 4,6 Modus Ponens Hence the given argument is valid.  Nested Quantifier When we consider propositional functions containing two or more variables it is possible, quantifiers occur in combinations with respect to the variable. Nested quantifiers are quantifiers that occur within the scope of other quantifiers. Example: ∀𝒙 ∃𝒚 𝒙 + 𝒚 = 𝟎. This means that for every real number 𝒙 there exists a real number 𝒚 such that 𝒙 + 𝒚 = 𝟎. 1.Express the statement ‘For every ‘𝒙’ there exists a ‘𝒚’ such that 𝒙𝟐 + 𝒚𝟐 ≥ 𝟏𝟎𝟎” in symbolic form. Solution : Let 𝑮 𝒙 , 𝒚 : 𝒙𝟐 + 𝒚𝟐 ≥ 𝟏𝟎𝟎 The symbolic form is 𝒙 ∃ 𝒚 𝑮 𝒙 ,𝒚. 2. Let 𝐐 𝒙, 𝒚, 𝒛 denote the statement "𝒙 + 𝒚 = 𝒛" defined on the universe of discourse 𝒁 , the set of all integers. What are the truth values of the propositions 𝑸 𝟏, 𝟏, 𝟏 and 𝑸 𝟏, 𝟏, 𝟐. Solution : 𝑸 𝟏, 𝟏, 𝟏 ∶ 𝟏 + 𝟏 = 𝟏 which is False. 𝑸 𝟏, 𝟏, 𝟐 ∶ 𝟏 + 𝟏 = 𝟐 which is True. 3. Symbolize the following statement with and without using the set of positive integers as the universe of discourse “ Given any positive integer, there is a greater positive integer”. Solution : (1) Universe of discourse : Set of positive integers. Let 𝑮 𝒙, 𝒚 ∶ 𝒙 is greater than 𝒚. The symbolic form is 𝒙 ∃𝒚 𝑮 𝒙 , 𝒚. (2) Universe of discourse : Set of integers. Let 𝑷 𝒙 ∶ 𝒙 is a positive integer. 𝑮 𝒙, 𝒚 ∶ 𝒙 is greater than 𝒚. The symbolic form is 𝒙 𝑷 𝒙 → ∃𝒚 𝑷 𝒚 ∧ 𝑮 𝒙 , 𝒚.  3.Show that ¬ 𝑷 𝒂, 𝒃 follows logically from 𝒙 𝒚 𝑷 𝒙, 𝒚 → 𝑾 𝒙, 𝒚 and ¬ 𝑾 𝒂, 𝒃. Solution : Step Statement Reason 1 Rule P 2 Rule US, 1 3 Rule US, 2 4 Rule P 5 Rule T 4,3 Modus Tollens  Methods of Proof Proofs play an important role in the development of mathematics because they guarantee the correctness of mathematical results. Mathematical results or computer algorithms are accepted only when they are proved by using the various rules of inference. Usually, we use two methods of proof in mathematics. (1) Direct Proof and (2) Indirect Proof.  A theorem in mathematics is a true proposition. Many theorems are implications of the form 𝑯 → 𝑪, where 𝑯 ≡ 𝑯𝟏 ∧ 𝑯𝟐 ∧ ⋯ ∧ 𝑯𝒏 is a conjunction of hypotheses and 𝑪 is the conclusion. Proving a theorem means verifying 𝑯 → 𝑪 is a tautology. 1. Direct Proof : In direct proof we assume the hypothesis 𝑯𝟏 , 𝑯𝟐 , … , 𝑯𝒏 are true and using the rules of inference and known facts we prove that 𝑪 is true. Thus we prove 𝑯 → 𝑪 is true. 2. There are two types of indirect proof : (a) Proof by contraposition. (b) Proof by contradiction. (a) Proof by contraposition : Proof by contraposition is a very useful and powerful method. It uses the contrapositive equivalence 𝑯 → 𝑪 ≡ ¬𝑪 → ¬𝑯. In this method, we assume the conclusion 𝑪 is false, then using the rules of inference and known facts we prove some hypothesis 𝑯𝟏 is also false and hence 𝑯 is false. This means that indirectly the conclusion is true. (b) Proof by contradiction : Proof by contradiction is based on the law of reduction and 𝒑 → 𝒒 ≡ 𝒑 ∧ ¬𝒒 → 𝑭. ie. 𝑯 → 𝑪 ≡ 𝑯 ∧ ¬𝑪 → 𝑭, where 𝑯 ≡ 𝑯𝟏 ∧ 𝑯𝟐 ∧ ⋯ ∧ 𝑯𝒏. In this method, we assume the conclusion 𝑪 is false and all 𝑯𝒊 are true( ie 𝑯 is true). Then by using the rules of inference we reach a contradiction 𝑭. This implies that our assumption 𝑪 is false is wrong. Thus, indirectly we prove 𝑯 → 𝑪. 1. Give an indirect proof of the theorem “ If 𝟑𝒏 + 𝟐 is odd then 𝒏 is odd”. Solution : If n is even, then 𝟑𝒏 is also even. When an even number 𝟐 is added, 𝟑𝒏 + 𝟐 is also an even number. Hence the theorem. 2.Prove that 𝟐 is irrational by giving a proof using contradiction. Solution : Let 𝑷 be the proposition “ 𝟐 is irrational”. Suppose that ∼ 𝑷 is true. Then 𝟐 is rational. 𝒂 So, 𝟐 = 𝒃 , where 𝒂 and 𝒃 have no common factors. 𝒂 𝒂𝟐 𝟐= ⇒ 𝟐= 𝒃 𝒃𝟐 Hence 𝒂𝟐 = 𝟐 𝒃𝟐. This means that 𝒂𝟐 is even, implying that 𝒂 is even. Furthermore, 𝒂 = 𝟐𝒄 for some integer 𝒄. Therefore, 𝟐𝒄 𝟐 = 𝟐 𝒃𝟐 𝟒 𝒄𝟐 = 𝟐 𝒃𝟐 ⇒ 𝒃𝟐 = 𝟐 𝒄𝟐 This means that 𝒃𝟐 is also even and hence 𝒃 is even. Therefore, 𝐛 = 𝟐𝒌 for some integer 𝒌. Thus 𝒂 and 𝒃 are even. Hence they have a common factor 𝟐. This contradicts the assumption 𝒂 and 𝒃 have no common factors. Thus our assumption 𝟐 is rational is wrong. Hence, 𝟐 is irrational.