MAT2004 Complete Notes PDF

Module: 1 Mathematical Logic Propositional Logic Propositions A proposition or statement is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. EXAMPLE All the following declarative sentences are proposi...

Module: 1 Mathematical Logic Propositional Logic Propositions A proposition or statement is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. EXAMPLE All the following declarative sentences are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3. Propositions 1 and 3 are true, whereas 2 and 4 are false. Note: Some sentences that are not propositions that can be simultaneously True or False. Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. x + 1 = 2. 4. x + y = z. Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false. If sentences 3 and 4 can be turned into a proposition if we assign values to the variables. CONNECTIVES Declarative sentences which cannot be further split into simpler sentences are called atomic statements. Many mathematical statements are constructed by combining one or more propositions, new propositions called molecular or compound or compound propositions, are formed from existing propositions using logical operators. The following symbols are used to represent connectives, S.No Symbol used Connective word Logical connectives Symbolic form 1 ¬ Not Negation ¬p 2 ∧ And Conjunction p∧q 3 ∨ Or Disjunction p∨q 4 → If…then Implication p→q (or)conditional 5 ↔ If and only if Equivalence (or) bi- p↔q conditional NOTE: 1. Propositional variables (or statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s,.... 2. The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. NEGATION The negation of a statement is generally formed by introducing a word ‘not’ at a proper place in a statement. If p be a proposition. The negation of p, denoted by ¬p (also denoted by p) and read as “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p. The Truth table for the negation of a proposition: p ¬p T F F T EXAMPLE 1. Find the negation of each of the following proposition a) “Michael’s PC runs Linux” b) “Vandana’s smartphone has at least 32GB of memory” English. Solution: The negation is a) “Michael’s PC does not run Linux.” b) “Vandana’s smartphone does not have at least 32GB of memory” CONJUNCTION Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise. The Truth table for the conjunction of two proposition: p q p∧q T T T T F F F T F F F F Example 1. The conjunction of p: It is raining today. q: There are 20 tables in this room. Solution:  p ∧ q : It is raining today and there are 20 tables in this room. 2. If p: It is snowing, q: I am cold. Solution: p ∧ q : It is snowing and I am cold. DISJUNCTION Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. The Truth table for the disjunction of two proposition: p q p∨q T T T T F T F T T F F F EXAMPLE 1.The disjunction of p: I shall watch the game on T.V q: Go to the stadium. Solution: p ∨ q: I shall watch the game on T.V or go to the stadium. 2.Find the conjunction and disjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.” Solution: The conjunction of these propositions, p ∧ q, is the proposition “Rebecca’s PC has more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1 GHz.” The disjunction of p and q, p ∨ q, is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.” CONDITIONAL STATEMENT Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence) The Truth table for the conditional statement of two proposition: p q p→q T T T T F F F T T F F T NOTE The conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express p → q. You will encounter most if not all of the following ways to express this conditional statement: “if p, then q”; “p implies q” ; “if p, q”; “p only if q” ; “p is sufficient for q” ; “a sufficient condition for q is p”; “q if p”; “q whenever p” ; “q when p” ; “q is necessary for p”; “a necessary condition for p is q” ; “q follows from p”; “q unless ¬p”. EXAMPLE: Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria will find a good job.” Express the statement p → q as a statement in English. Solution: p → q : If Maria learns discrete mathematics, then she will find a good job. BICONDITIONAL STATEMENT Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications. The Truth table for the biconditional statement of two proposition: p q p↔q T T T T F F F T F F F T EXAMPLE Let p be the statement “You can take the flight,” and let q be the statement “You buy a ticket.” Then p ↔ q is the statement Solution: p ↔ q : You can take the flight if and only if you buy a ticket. PROBLEMS 1. Which of these are propositions? What are the truth values of those that are propositions? a. Do not pass go. b. What time is it? c. 4 + x = 5. d. The moon is made of green cheese. e. 2n ≥ 100.  Solution: a) This is not a proposition; it’s a command. b) This is not a proposition; it’s a question. c) This is not a proposition; it’s truth value depends on the value of x. d) This is a proposition that is false. e) This is not a proposition; it’s truth value depends on the value of n. 2. Let p and q be the propositions “Swimming at the New Jersey shore is allowed” and “Sharks have been spotted near the shore,” respectively. Express each of these compound propositions as an English sentence. a) ¬q e) ¬q → p b) p ∧ q f ) ¬p → ¬q c) ¬p ∨ q g) p ↔ ¬q d) p → ¬q h) ¬p ∧ (p ∨ ¬q) Solution: a) Sharks have not been spotted near the shore. b) Swimming at the New Jersey shore is allowed and sharks have been spotted near the shore. c) Swimming at the New Jersey shore is not allowed or sharks have been spotted near the shore. d) If Swimming at the New Jersey shore is allowed, then sharks have not been spotted near the shore. e) If sharks have not been spotted near the shore, then swimming at the New Jersey shore is allowed. f) If Swimming at the New Jersey shore is not allowed, then sharks have not been spotted near the shore. g) Swimming at the New Jersey shore is allowed if and only if sharks have not been spotted near the shore. h) Swimming at the New Jersey shore is not allowed and, either swimming at the New Jersey shore is allowed or sharks have not been spotted near the shore. 3. Let p and q be the propositions p : You drive over 65 miles per hour. q : You get a speeding ticket. Write these propositions using p and q and logical connectives (including negations). a. You do not drive over 65 miles per hour. b. You drive over 65 miles per hour, but you do not get a speeding ticket. c. You will get a speeding ticket if you drive over 65 miles per hour. d. If you do not drive over 65 miles per hour, then you will not get a speeding ticket. e. Driving over 65 miles per hour is sufficient for getting a speeding ticket. f. You get a speeding ticket, but you do not drive over 65 miles per hour. Solution: a. This is just the negation of p, so we write ¬p. b. This is a conjunction ("but" means "and"): p ∧ ¬q. c. The position of the word "if" tells us which is the antecedent and which is the consequence: p → q. d.¬ p → ¬q e. The sufficient condition is the antecedent: p → q.  f. q ∧ ¬p. PRACTICE PROBLEMS 1. Let p and q denote the statements: p : You drive over 70 km per hour. q : You get a speeding ticket. Write the following statements into symbolic forms. i. You will get a speeding ticket if you drive over 70 km per hour. ii. Driving over 70 km per hour is sufficient for getting a speeding ticket. iii. If you do not drive over 70 km per hour then you will not get a speeding ticket. iv. Whenever you get a speeding ticket, you drive over 70 km per hour. 2. Write the negation of the following statements. a) Jan will take a job in industry or go to graduate school. b) If the processor is fast then the printer is slow. WELL FORMED FORMULAS A statement formula is an expression denoted by a string consisting of variables, parentheses and connective symbols. EXAMPLE 1. ¬ (p ∧ q) 2. ¬ (p ∨ q) 3. (p → (p ∨ q)) 4. (p → (q →r)) TRUTH TABLE The truth value of a proposition is either true (denoted as T) or false (denoted as F). A truth table is a table that shows the truth value of a compound proposition for all possible cases. PROBLEMS 1. Construct the truth table for ¬p∧ q. Solution: p q ¬p ¬p ∧ q T T F F T F F F F T T T F F T F 2. Construct the truth table for (p∨ q) ∨¬p. Solution: p q p ∨q ¬p (p∨ q) ∨¬p T T T F T T F T F T F T T T T F F F T T  3. Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q) Solution: p q ¬q p ∨ ¬q p∧q (p ∨ ¬q) → (p ∧ q) T T F T T T T F T T F F F T F F F T F F T T F F 4. Construct a truth table for (p ↔ q) ↔ (r ↔ s). Solution: Practice Problems: 1. Construct the truth table for the following formulas (i) ¬ (¬p ∨ ¬q) (iii) p → (¬q ∨ r) (ii) ¬ (¬p ∧ ¬q) Duality Law Two formulas A and A* are said to be duals of each other if either one can be obtained from the other by replacing ∧ by ∨ and ∨ by ∧. The connectives ∨ and ∧ are called duals of each other. If the formula A contains the special variable T or F , then A* , its dual is obtained by replacing T by F and F by T in addition to the above mentioned interchanges. Example: Write the dual of the following formulas: (i). (p ∨ q) ∧ r (ii). (p ∧ q) ∨ T (iii). (p ∧ q) ∨ (p ∨ ¬(q ∧ ¬ s)) Solution: The duals of the formulas may be written as (i). (p ∧ q) ∨ r (ii). (p ∨ q) ∧ F (iii). (p ∨ q) ∧ (p ∧ ¬(q ∨ ¬s)) NOTE : The negation of the formula is equivalent to its dual in which every variable is replaced by its negation. We can prove ¬A ( p1 , p 2 ,..., p n ) ⇔ A (p1 , p 2 ,..., p n ) CONVERSE, CONTRAPOSITIVE, AND INVERSE If p → q is a conditional statement, then (1).q → p is called its converse (2). ¬p → ¬q is called its inverse (3). ¬q → ¬p is called its contrapositive. EXAMPLE What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?” Solution: Because “q whenever p” is one of the ways to express the conditional statement p → q, the original statement can be rewritten as “If it is raining, then the home team wins.” Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win. LOGIC AND BIT OPERATIONS Computers represent information using bits. A bit has two possible values, namely 0 and 1. We will use a 1 bit to represent true and a 0 bit to represent false. Truth value Bit T 1 F 0 EXAMPLE Find the bitwise OR and bitwise AND of the bit strings 01 1011 0110 and 11 0001 1101. (Here, bit strings will be split into blocks of four bits to make them easier to read.) Solution: The bitwise OR and bitwise AND of these strings are obtained by taking the OR and AND, of the corresponding bits, respectively. This gives us  01 1011 0110 11 0001 1101 11 1011 1111 bitwise OR 01 0001 0100 bitwise AND Propositional Logic Equivalences TAUTOLOGY A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. EXAMPLE: p ∨ ¬p CONTRADICTION A compound proposition that is always false is called a contradiction. EXAMPLE: p ∧ ¬p CONTINGENCY A compound proposition that is neither a tautology nor a contradiction is called a contingency. LOGICALLY EQUIVALENT The compound propositions p and q are called logically equivalent if p ↔ q is a tautology. The notation p ≡ q or p ⇔ q denotes that p and q are logically equivalent. Method I. Truth Table Method: One method to determine whether any two statement formulas are equivalent is to construct their truth tables. PROBLEMS 1. Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent by using truth table. Solution: Truth Tables for ¬(p ∨ q) and ¬p ∧ ¬q. ∴ ¬ (p ∨ q) ≡ ¬p ∧ ¬q 2. Show that p → q and ¬p ∨ q are logically equivalent by using truth table. Solution:  ∴ p → q ≡ ¬p ∨ q 3. Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent. Solution: ∴ p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r). 4. Show that the proposition (p ∨ q) ↔ (q ∨ p) is tautology. Solution: p q p∨q q∨p (p ∨ q) ↔ (q ∨ p) T T T T T T F T T T F T T T T F F F F T The last column entries are T. ∴ (p ∨ q) ↔ (q ∨ p) is tautology. 5. Show the truth table for (( ¬ q ∧ p) ∧ q). Solution: p q ¬q ¬q ∧ p (( ¬q ∧ p) ∧ q) T T F F F T F T T F F T F F F F F T F F The last column entries are F. ∴ (( ¬q ∧ p) ∧ q) is contradiction. Table Logic equivalences Table logical equivalences invoving conditionals Table logical equivalences involving biconditionals. Method II. Replacement Process: Consider a formula A : p → (q → r). The formula q → r is a part of the formula A. If we replace q → r by an equivalent formula ¬ q ∨ r in A, we get another formula B : p → (¬ q ∨ r). One can easily verify that the formulas A and B are equivalent to each other. This process of obtaining B from A as the replacement process. PROBLEMS 1. Show that ¬(p → q) and p ∧ ¬q are logically equivalent. Solution: ¬(p → q) ≡ ¬(¬p ∨ q) (by logical equivalences invoving condition) ≡ ¬(¬p) ∧ ¬q (by De Morgan law) ≡ p ∧ ¬q (by double negation law) 2. Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences Solution: ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q) (by De Morgan law ) ≡ ¬p ∧ [¬(¬p) ∨ ¬q] (by De Morgan law ) ≡ ¬p ∧ (p ∨ ¬q) (by double negation law ) ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) (by distributive law ) ≡ F ∨ (¬p ∧ ¬q) ( because ¬p ∧ p ≡ F ) ≡ (¬p ∧ ¬q) ∨ F ( by the commutative law for disjunction ) ≡ ¬p ∧ ¬q (by the identity law for F ) 3. Show that (p ∧ q) → (p ∨ q) is a tautology. Solution: (p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q) (by logical equivalences invoving condition) ≡ (¬p ∨ ¬q) ∨ (p ∨ q) (by De Morgan law ) ≡ (¬p ∨ p) ∨ (¬q ∨ q) (by the associative and commutative laws for disjunction ) ≡T∨T (by Negation law and the commutative law for disjunction) ≡T (by the domination law) 4. Show that (p → r) ∨ (q → r) and (p ∧ q) → r are logically equivalent. Solution: (p → r) ∨ (q → r) ≡( ¬p ∨ r) ∨ (¬q ∨ r) (by logical equivalences invoving condition ≡ (¬p ∨ ¬q ) ∨ (r ∨ r) (by the associative and commutative laws for disjunction) ≡ ¬ (p ∧ q) ∨ r (by De Morgan law and idempotent law) ≡ (p ∧ q) → r (by logical equivalences invoving condition) PRACTICE PROBLEMS 1. Show ((p ∨ q) ∧ ¬(¬p ∧ (¬q ∨ ¬r))) ∨ (¬p ∧ ¬q) ∨ (¬p ∧ ¬r) is tautology, by using truth table and replacement process. 2. Prove that (p → q) ∧ (r → q) ⇔ (p ∨ r) → q, by using truth table and replacement process. 3. Prove that (¬p ∧ (¬q ∧ r)) ∨ (q ∧ r) ∨ (p ∧ r) ⇔ r, by using truth table and replacement process. 4. Prove that conditional and contrapositive are equivalent. Normal forms ELEMENTARY PRODUCT A conjunction of the variables and their negations is called an elementary product. EXAMPLE: Let p, q be any two atomic variables. Then ¬p ∧ q, ¬q ∧ p, ¬q ∧ p∧¬ p, ¬p ∧ p, ¬p ∧ ¬ q are some examples of elementary products. ELEMENTARY SUM A disjunction of the variables and their negations is called an elementary sum. EXAMPLE Let p, q be any two atomic variables. Then ¬p ∨ q, ¬q ∨ p, ¬q ∨ p ∨ ¬ p, ¬p ∨ p, ¬p ∨¬ q are some examples of elementary sum. FACTOR Any part of an elementary product or elementary sum, which is itself an elementary product or sum is a factor of the product or sum. EXAMPLE q ∨ p is a factor of ¬q ∨ q ∨ p DISJUNCTIVE NORMAL FORM (DNF) A formula which is equivalent to a given formula and which consists of a sum of elementary products is called a disjunctive normal form of the given formula. EXAMPLE 1. Obtain DNF of p ∧ ( p → q) Solution: p ∧ ( p → q)) ≡ p ∧ (¬p ∨ q) (by logical equivalences invoving condition) ≡ (p ∧ ¬p) ∨(p ∧ q) ( by Distributive ) Which is the required DNF. 2. Obtain the DNF p → [( p → q) ∧ ¬(¬q ∨ ¬p)] Solution: ≡ ¬p ∨ [(¬ p ∨ q) ∧ ¬(¬q ∨ ¬p)] (by logical equivalences invoving condition) ≡ ¬p ∨ [(¬ p ∨ q) ∧ (q ∧ p)] (by double negation law) ≡ ¬p ∨ [(¬ p ∧ q ∧ p)∨ (q ∧ q ∧ p)] (distributive law) ≡ ¬p ∨ [(F ∧ q) ∨ (q ∧ p)] (negation law, idempotent law) ≡ ¬p ∨ [(F ∨ (q ∧ p)] (domination law) ≡ ¬p ∨ (q ∧ p) (identity law) Which is the required DNF. 3. Obtain DNF of ¬ ( p → ( q ∧ r)). Solution:  ¬ ( p → ( q ∧ r)) ≡ ¬[¬ p ∨ (q ∧ r)] (by logical equivalences invoving condition) ≡ p ∧ (¬q ∨ ¬ r) ( De Morgan law) ≡ ( p ∧ ¬q) ∨ ( p ∧¬ r) (Distributive law) Conjunctive Normal Forms(CNF) A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of a given formula. Example 1. Obtain the conjunctive normal form for the following (a) p  (p q) (b) ¬ (p  q) (c) ¬ (p ↔ q) Solution: (a) p  (p q) ≡ p  (¬p  q). (by logical equivalences invoving condition) (b) ¬ (p  q) ≡ ¬ p  ¬q. (De Morgan’s law) (c) ¬ (p ↔ q) ≡ ¬ ((p q)  (q p)) (by logical equivalences invoving Bi- condition)  ≡ ¬ ((¬p  q)  (¬q  p)) (by logical equivalences invoving condition) ≡ ¬(¬p  q)  ¬ (¬q  p) (De Morgan’s law) ≡ (p  ¬q)  (q  ¬p) (De Morgan’s law) ≡ (p  q)  (q  ¬q)  (p  ¬ p)  (¬ p  ¬q) (Distributive law) Principal Disjunctive Normal Form(PDNF) Minterm For a given number of variables, the minterm consists of conjunctions in which each statement variable or its negation, but not both, appears only once. Let p and q be the two statement variables. Then there are 2 2 minterms given by p ∧ q, p ∧ ¬q, ¬p ∧ q, and ¬p ∧ ¬q. Minterms for three variables p , q and r are p ∧ q ∧ r, p ∧ q ∧ ¬r, p ∧ ¬q ∧ r, p∧ ¬q ∧ ¬r, ¬p ∧ q ∧ r, ¬p ∧ q ∧ ¬r, ¬p ∧ ¬q ∧ r and ¬p ∧ ¬q ∧ ¬r. Definition For a given formula, an equivalent formula consisting of disjunctions of minterms only is called the Principal disjunctive normal form of the formula. The principle disjunctive normal formula is also called the sum-of-products canonical form. Methods to obtain PDNF of a given formula (a). By Truth table: (i). Construct a truth table of the given formula. (ii). For every truth value T in the truth table of the given formula, select the minterm which also has the value T for the same combination of the truth values of p and q. (iii). The disjunction of these minterms will then be equivalent to the given formula. Example: 1. Obtain the PDNF of p → q. Solution: From the truth table of p → q P q p→q Minterm T T T p∧q T F F p ∧ ¬q F T T ¬p ∧ q F F T ¬p ∧ ¬q The PDNF of p → q is (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q). ∴ p → q ≡ (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q). 2. Obtain the PDNF for (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ r). Solution: p Q r Minterm p∧q ¬p ∧ r q∧r (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ r) T T T p∧q∧r T F T T T T F p ∧ q ∧ ¬r T F F T T F T p ∧ ¬q ∧ r F F F F T F F p ∧ ¬q ∧¬ r F F F F F T T ¬p ∧ q ∧ r F T T T F T F ¬p ∧ q ∧ ¬r F F F F F F T ¬p ∧ ¬q ∧ r F T F T F F F ¬p ∧ ¬q ∧ ¬r F F F F The PDNF of (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ r)is  (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r). (b). Without constructing the truth table: In order to obtain the principal disjunctive normal form of a given formula is constructed as follows: (1). First replace →, by their equivalent formula containing only ∧, ∨ and ¬. (2). Next, negations are applied to the variables by De Morgan‘s laws followed by the application of distributive laws. (3). Any elementarily product which is a contradiction is dropped. Minterms are ob-tained in the disjunctions by introducing the missing factors. Identical minterms appearing in the disjunctions are deleted. Example 1. Obtain the principal disjunctive normal form of (i) (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ r). (ii) p ∨ (p ∧ q) ≡ p (iii) p ∨ (¬p ∧ q) ≡ p ∨ q Solution: (i) (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ r) ≡ (p ∧ q ∧ T ) ∨ (¬p ∧ r ∧ T ) ∨ (q ∧ r ∧ T ) ≡ (p ∧ q ∧ (r ∨ ¬r)) ∨ (¬p ∧ r ∧ (q ∨ ¬q)) ∨ (q ∧ r ∧ (p ∨ ¬p )) ≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ r ∧ q) ∨ (¬p ∧ r ∧ ¬q) ∨ (q ∧ r ∧ p )∨ (q ∧ r ∧ ¬p ) ≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r) which is the required PDNF. (ii) p ∨ (p ∧ q) ≡ (p ∧ T ) ∨ (p ∧ q) [∵ P ∧ Q ≡ P ] ≡ (p ∧ (q ∨ ¬q)) ∨ (p ∧ q) [∵ P ∨ ¬P ≡ T ] ≡ ((p ∧ q) ∨ (p ∧ ¬q)) ∨ (p ∧ q) [by distributive laws] ≡ (p ∧ q) ∨ (p ∧ ¬q) [∵ P ∨ P ≡ P ] which is the required PDNF. Now, p≡ p ∧ T ≡ p ∧ (q ∨ ¬q) ≡ (p ∧ q) ∨ (p ∧ ¬q) which is the required PDNF. Hence, p ∨ (p ∧ q) ≡ p (iii) p ∨ (¬p ∧ q) ≡ (p ∧ T ) ∨ (¬p ∧ q) ≡ (p ∧ (q ∨ ¬q)) ∨ (¬p ∧ q) ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) which is the required PDNF. Now, p ∨ q ≡ (p ∧ T ) ∨ (q ∧ T ) ≡ (p ∧ (q ∨ ¬q)) ∨ (q ∧ (p ∨ ¬p )) ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (q ∧ p ) ∨ (q ∧ ¬p ) ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) which is the required PDNF. Hence, p ∨ (¬p ∧ q) ≡ p ∨ q. Principal Conjunctive Normal Form(PCNF) The dual of a minterm is called a Maxterm. For a given number of variables, the maxterm consists of disjunctions in which each variable or its negation, but not both, appears only once. Each of the maxterm has the truth value F for exactly one combination of the truth values of the variables. Now we define the principal conjunctive normal form. For a given formula, an equivalent formula consisting of conjunctions of the max-terms only is known as its principle conjunctive normal form. This normal form is also called the product-of-sums canonical form. The method for obtaining the PCNF for a given formula is similar to the one described previously for PDNF. Example: Obtain the principal conjunctive normal form of the formula (¬p → r) ∧ (q ↔ p) Solution: (¬p → r) ∧ (q ↔ p ) ≡ [¬(¬p ) ∨ r] ∧ [(q → p ) ∧ (p → q)] ≡ (p ∨ r) ∧ [(¬q ∨ p ) ∧ (¬p ∨ q)] ≡ (p ∨ r ∨ F ) ∧ [(¬q ∨ p ∨ F ) ∧ (¬p ∨ q ∨ F )] ≡ [(p ∨ r) ∨ (q ∧ ¬q)] ∧ [¬q ∨ p ) ∨ (r ∧ ¬r)] ∧ [(¬p ∨ q) ∨ (r ∧ ¬r)] ≡ (p ∨ r ∨ q) ∧ (p ∨ r ∨ ¬q) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ≡ (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) which is required principal conjunctive normal form PRACTICE PROBLEM 1. Find the PDNF form PCNF of S : p ∨ (¬p → (q ∨ (¬q → r))). 2. Obtain CNF for ((p → q) ∧ ¬q)→ ¬p. 3. Obtain DNF for (p  r)  (q  r) 4. Find the PDNF form PCNF for (p ↔ q) ANSWER: 1. p ∨ q ∨ r which is the PCNF. PDNF of S: (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ ( p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ q ∧ r). PCNF of S: (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) 2.( p ∨ ¬q)  (¬q ∨ p) 3. (p  q  r) V (p  q  ¬r) V (p  ¬q  r) V (¬p  q  ¬r) 4. PDNF : (¬ p  q) ( ¬q p)  PCNF : (¬ p  ¬q) (q  ¬q) (p ¬ p)  (qp) Rules of Inference ARGUMENT A set of propositions p1 , p 2 ,..., p n and q is said to be an argument if ( p1  p 2 ...  p n )  q. In other words ( p1  p 2 ...  p n ) q should be a tautology. Here p1 , p 2 ,..., p n are called Premises of the argument and q is called a conclusion of the argument. p1 p2... pn ∴q An argument with premises p1 , p 2 ,..., p n and conclusion q is said to valid if whenever each of premises p1 , p 2 ,..., p n is true, then conclusion q is also true. Otherwise the argument is invalid. RULES OF INFERENCE PROBLEMS 1.State which rule of inference is the basis of the following argument: “It is below freezing now. Therefore, it is either below freezing or raining now.”  Solution: Let p be the proposition “It is below freezing now” and q the proposition “It is raining now.” Then this argument is of the form This is an argument that uses the addition rule. 2. State which rule of inference is the basis of the following argument: “It is below freezing and raining now. Therefore, it is below freezing now.” Solution: Let p be the proposition “It is below freezing now,” and let q be the proposition “It is raining now.” This argument is of the form This argument uses the simplification rule. 3. State which rule of inference is used in the argument: If it rains today, then we will not have a barbecue today. If we do not have a barbecue today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a barbecue tomorrow. Solution: Let p be the proposition “It is raining today,” let q be the proposition “We will not have a barbecue today,” and let r be the proposition “We will have a barbecue tomorrow.” Then this argument is of the form Hence, this argument is a hypothetical syllogism. 4. Show that the premises “It is not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.” Solution: Let p : “It is sunny this afternoon,” q : “It is colder than yesterday,” r : “We will go swimming,” s: “We will take a canoe trip,” and t : “We will be home by sunset.” Then the premises become ¬p ∧ q, r → p, ¬r → s, and s → t. The conclusion is simply t. We construct an argument to show that our premises lead to the desired conclusion as follows.  Hence the result. 5. Show that the premises “If you send me an e-mail message, then I will finish writing the program,” “If you do not send me an e-mail message, then I will go to sleep early,” and “If I go to sleep early, then I will wake up feeling refreshed” lead to the conclusion “If I do not finish writing the program, then I will wake up feeling refreshed.” Solution: Let p : “You send me an e-mail message,” q : “I will finish writing the program,” r : “I will go to sleep early,” and s : “I will wake up feeling refreshed.” Then the premises are p → q, ¬p → r, and r → s. The desired conclusion is ¬ q → s. This argument form shows that the premises lead to the desired conclusion. Hence the result. 6. Show that r ∨ s follows logically from the premises c ∨d, (c ∨d) → ¬h, ¬h → (a ∧ ¬b), and (a ∧ ¬b) → (r ∨ s). Solution: Step Reason (1) (c ∨ d) → ¬h Premise (2) ¬h → (a ∧ ¬b) Premise (3) (c ∨ d) → (a ∧ ¬b) Hypothetical syllogism using (1) and (2) (4) (a ∧ ¬b) → (r ∨ s) Premise (5) (c ∨ d) → (r ∨ s) Hypothetical syllogism using (3) and (4) (6) c ∨ d Premise (7) r ∨ s Modus ponens using (5) and (6) Hence the result. 7. Show that s ∨ r is tautologically implied by (p ∨ q) ∧ ( p → r) ∧ (q → s). Solution: Step Reason (1) p ∨ q Premise (2) ¬p → q p → q ⇔ ¬ p ∨ q (1) (3) q → s Premise (4) ¬p → s Hypothetical syllogism using (2) and (3) (5) ¬s → p p → q ⇔ ¬ q → ¬ p (4) (6) p → r Premise (7) ¬s → r Hypothetical syllogism using (5) and (6) (8) s ∨ r p → q ⇔ ¬ p ∨ q (7) Hence the result. Consistency of Premises A set of formulas H 1 , H 2 ,..., H m is said to be consistent if their conjunction has the truth value T for some assignment of the truth values to the atomic variables appearing in H 1 , H 2 ,..., H m. If, for every assignment of the truth values to the atomic variables, at least one of the formulas H 1 , H 2 ,..., H m is false, so that their conjunction is identically false, then the formulas H 1 , H 2 ,..., H m are called inconsistent. Alternatively, a set of formulas H 1 , H 2 ,..., H m is inconsistent if their conjunction implies a contradiction, that is, H 1 , H 2 ,..., H m ⇒ r ∧ ¬r where r is any formula. PROBLEMS 1. Show that the following premises are inconsistent: (1). If Jack misses many classes through illness, then he fails high school. (2). If Jack fails high school, then he is uneducated. (3). If Jack reads a lot of books, then he is not uneducated. (4). Jack misses many classes through illness and reads a lot of books. Solution: Let us indicate the statements as follows: e: Jack misses many classes through illness. s: Jack fails high school. a: Jack reads a lot of books. h: Jack is uneducated. The premises are e → s, s → h, a → ¬h, and e ∧ a. Step Reason (1) e → s Premise (2) s → h Premise (3) e → h Hypothetical syllogism using (1) and (2) (4) a → ¬h Premise (5) h → ¬a p → q ⇔ ¬q → ¬p (4) (6) e → ¬a Hypothetical syllogism using (3) and (5) (7) ¬e ∨ ¬a p → q ⇔ ¬p ∨ q (6) (8) ¬(e ∧ a) ¬(p ∧ q) ⇔ ¬p ∨ ¬q (7) (9) e ∧ a Premise (10) ¬(e ∧ a) ∧ (e ∧ a) Conjunction (8), (9)  Thus, the given set of premises leads to a contradiction and hence it is inconsistent. 2. Show that the following set of premises is inconsistent: “If the contract is valid, then John is liable for penalty. If John is liable for penalty, he will go bankrupt. If the bank will loan him money, he will not go bankrupt. As a matter of fact, the contract is valid, and the bank will loan him money.” Solution: Let us indicate the statements as follows: v : The contract is valid. l: John is liable for penalty. m: Bank will loan him money. b: John will go bankrupt. Step Reason (1) v → l Premise (2) l → b Premise (3) v → b Hypothetical syllogism using (1) and (2) (4) m → ¬b Premise (5) b → ¬m p → q ⇔ ¬q → ¬p (4) (6) v → ¬m Hypothetical syllogism using (3) and (5) (7) ¬v ∨ ¬m p → q ⇔ ¬p ∨ q (6) (8) ¬(v ∧ m) ¬(p ∧ q) ⇔ ¬p ∨ ¬q (7) (9) v ∧ m Premise (10) ¬(v ∧ m) ∧ (v ∧ m) Conjunction (8), (9) Thus, the given set of premises leads to a contradiction and hence it is inconsistent. Indirect Method of Proof The method of using the rule of conditional proof and the notion of an inconsistent set of premises is called the indirect method of proof or proof by contradiction. In order to show that a conclusion C follows logically from the premises H 1 , H 2 ,..., H m , we assume that C is false and consider ¬C as an additional premise. If the new set of premises is inconsistent, so that they imply a contradiction. Therefore, the assumption that ¬C is true does not hold. Hence, C is true whenever H 1 , H 2 ,..., H m are true. Thus, C follows logically from the premises. H 1 , H 2 ,..., H m. PROBLEMS 1.Show that ¬(p ∧ q) follows from ¬p ∧ ¬q. Solution: We introduce ¬ ¬(p ∧q) as additional premise and show that this additional premise leads to a contradiction. Step Reason (1) ¬ ¬ (p ∧ q) Premise (assumed) (2) p ∧ q ¬ ¬P ⇔ P (1) (3) p Simplification, (2),  (4) ¬p ∧ ¬q Premise (5) ¬p Simplification, (4) (6) p ∧ ¬p Conjunction, (3), (5) Hence, our assumption is wrong. Thus, ¬(p ∧ q) follows from ¬p ∧ ¬q. 2.Using the indirect method of proof, show that p → q, q → r, p ∨ r ⇒ r. Solution: We include ¬R as an additional premise. Then we show that this leads to a contradiction. Step Reason (1) p → q Premise (2) q → r Premise (3) p → r Hypothetical syllogism using (1), (2) (4) ¬r Premise (assumed) (5) ¬p Modus Tollens, (4) (6) p ∨ r Premise (7) r Disjunctive syllogism, (5), (6) (8) r ∧ ¬r Conjunction, (4), (7) Hence, our assumption is wrong PRACTICE PROBLEMS 1.Show that r ∧ (p ∨ q) is a valid conclusion from the premises p ∨ q, q → r, p → m, and ¬m. 2.Show that p → s can be derived from the premises ¬p ∨ q, ¬q ∨ r, and r → s. 3.“If there was a ball game, then traveling was difficult. If they arrived on time, then traveling was not difficult. They arrived on time. Therefore, there was no ball game‘. Show that these statements constitute a valid argument. [Hint: p → q , r → ¬q, and r. The conclusion is ¬p ] 4.By using the method of derivation, show that following statements constitute a valid argument: “If A works hard, then either B or C will enjoy. If B enjoys, then A will not work hard. If D enjoys, then C will not. Therefore, if A works hard, D will not enjoy. [Hint: a → (b ∨ c), b → ¬a , and d → ¬c. The conclusion is a → ¬d] Predicate Calculus Predicate A part of a declarative sentence describing the properties of an object is called a predicate. The logic based upon the analysis of predicate in any statement is called predicate logic. Consider two statements: John is a bachelor Smith is a bachelor. In each statement “is a bachelor” is a predicate. Both John and Smith have the same property of being a bachelor. In the statement logic, we require two different symbols to express them and these symbols do not reveal the common property of these statements. In predicate calculus these statements can be replaced by a single statement “x is a bachelor”. A predicate is symbolized by a capital letters which is followed by the list of variables. The list of variables is enclosed in parenthesis. If P stands for the predicate “is a bachelor”, then P (x) stands for ”x is a bachelor”, where x is a predicate variable. `The domain for P (x) : x is a bachelor, can be taken as the set of all human names. Note that P (x) is not a statement, but just an expression. Once a value is assigned to x, P (x) becomes a statement and has the truth value. If x is Ram, then P (x) stands for “ Ram is a bachelor” is a statement and its truth value is true. Examples: 1. Let P (x) denote the statement “x > 3.” What are the truth values of P (4) and P (2)? Sol: We obtain the statement P (4) by setting x = 4 in the statement “x > 3.” Hence, P (4), which is the statement “4 > 3,” is true. However, P (2), which is the statement “2 > 3,” is false. 2. Let A(x) denote the statement “Computer x is under attack by an intruder.” Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)? Sol: We obtain the statement A(CS1) by setting x = CS1 in the statement “Computer x is under attack by an intruder.” Because CS1 is not on the list of computers currently under attack, we conclude that A(CS1) is false. Similarly, because CS2 and MATH1 are on the list of computers under attack, we know that A(CS2) and A(MATH1) are true. NOTE: The statement P(x) is also said to be the value of the propositional function P at x. One place predicate If there is only one name (variable) associated with the predicate, then it is called as one place predicate. Example: P (x): x is a bachelor, where ‘x’ is a variable and “ is a bachelor” is predicate. Two place predicate If there are 2 names (variables) of objects associated with a predicate, then it is known as two- place predicate. Example consider the statement “x = y + 3.” We can denote this statement by Q(x, y), where x and y are variables and Q is the predicate. When values are assigned to the variables x and y, the statement Q(x, y) has a truth value. Problem: Q: What are the truth values of the propositions Q(1, 2) and Q(3, 0)? Solution: To obtain Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y). Hence, Q(1, 2) is the statement “1 = 2 + 3,” which is false. The statement Q(3, 0) is the proposition “3 = 0 + 3,” which is true Note: 1. Mr.X sits between Mr.Y and Mr.Z , here 3 name associated with predicate so it is called as 3 place predicate and it is dented by S(x, y, z). 2. Green and Miller played bridge against Johnson and Smith, here 4 name associated with predicate so it is called as 4 place predicate and it is dented by P(g, m, j, s). 3. In general an n-place predicate is a predicate requiring n name of objects where n>0. COMPUND STATEMENT FUNCTION Compound statement function is obtained by combining one or more simple statement functions using logical connective. EXAMPLE: Let M(x): x is a man; C(y): y is clever, be the simple statement functions then M(x) ∨ C(y) M(x) ∧ C(y) M(x) → C(y) M(x) ↔ C(y) Quantifiers Quantifiers are words that are refer to quantities such as ‘some‘ or ‘all‘. i.e they quantify the scope of variables involved in statement function. Universal Quantifier The universal quantification of P (x) is the statement “P (x) for all values of x in the domain.” The notation ∀x P(x) or (x)P(x) denotes the universal quantification of P (x). Here ∀ is called the universal. An element for which P (x) is false is called a counterexample of ∀x P(x). The Universal Quantifier is equivalent to each of the following phrases. 1. For every x, 2.For each x, 3. For all x, 4. Everything x is such that, 5. Each thing x is such that. EXAMPLE 1.Let P (x) be the statement “x + 1 > x.” What is the truth value of the quantification (∀x) P (x), where the domain consists of all real numbers? Solution: Because P (x) is true for all real numbers x, the quantification (∀x) P (x) is true. 2. What is the truth value of (∀x) P (x), where P (x) is the statement “ x 2 < 10” and the domain consists of the positive integers not exceeding 4? Solution: The statement (∀x) P (x) is the same as the conjunction P (1) ∧ P (2) ∧ P (3) ∧ P (4), because the domain consists of the integers 1, 2, 3, and 4. Because P (4), which is the statement “ 4 2 < 10,” is false, it follows that ∀x P (x) is false. 3.Consider the sentence “All human beings are mortal”. Solution: Let P (x) denote ‘x is a mortal‘. Then, the above sentence can be written as (∀x) P (x) Existential Quantifier The existential quantification of P (x) is the proposition “There exists an element x in the domain such that P (x).” We use the notation ∃x P (x) for the existential quantification of P (x). Here ∃ is called the existential quantifier. The Existential Quantifier is equivalent to each of the following phrases. 1. There exists an x, 2. There is an x, 3. For some x, 4. There is at least one x. 5. Some x such that EXAMPLE 1. Let P (x) denote the statement “x > 3.” What is the truth value of the quantification (∃x) P (x), where the domain consists of all real numbers? Solution: Because “x > 3” is sometimes true—for instance, when x = 4—the existential quantification of P (x), which is (∃x) P(x), is true. 2. What is the truth value of (∃x) P(x), where P(x) is the statement “ x 2 > 10” and the universe of discourse consists of the positive integers not exceeding 4? Solution: Because the domain is {1, 2, 3, 4}, the proposition (∃x) P(x) is the same as the disjunction P (1) ∨ P (2) ∨ P (3) ∨ P (4). Because P (4), which is the statement “ 4 2 > 10,” is true, it follows that (∃x) P(x) is true. 3. Consider the sentence “There exists x such that x 2 = 5”. Solution: This sentence can be written as (∃x) P(x), where P (x) : x 2 = 5. Problems 1. Write the following statements in symbolic form: (i). Something is good (ii). Everything is good (iii). Nothing is good  (iv). Something is not good. Solution: The above statement can be restated as follows and if G(x): x is good, then Statement (i) “There is atleast one x such that, x is good”. The symbolic form is (∃x) G(x) Statement (ii) “Forall x, x is good”. The symbolic form is (∀x) G(x) Statement (iii) “Forall x, x is not good”. The symbolic form is (∀x) ¬G(x) Statement (iv) “There is atleast one x such that, x is not good”. The symbolic form is (∃x)¬G(x) 2. Let K(x) : x is a man, L(x) : x is mortal , M(x) : x is an integer, N(x) : x either positive or negative. Express the following using quantifiers:  All men are mortal  Any integer is either positive or negative. Solution: (a) The given statement can be written as For all x, if x is a man, then x is mortal and this can be expressed as (x)(K(x) → L(x)). (b) The given statement can be written as For all x, if x is an integer, then x is either positive or negative and this can be expressed as (x)(M(x) → N(x)). Free and Bound Variables Given a formula containing a part of the form (x) P(x) or (∃x) P(x), such a part is called an x-bound part of the formula. Any occurrence of x in an x-bound part of the formula is called a bound occurrence of x, while any occurrence of x or of any variable that is not a bound occurrence is called a free occurrence. The smallest formula immediately following (∀x) or (∃x) is called the scope of the quantifier. Consider the following formulas:  (x)P (x, y)  (x) (P (x) → Q(x))  (x) (P (x) → (∃y)R(x, y))  (x) (P (x) → R(x)) ∨ (x)(R(x) → Q(x))  (∃x) (P (x) ∧ Q(x))  (∃x) P (x) ∧ Q(x). In (1), P (x, y) is the scope of the quantifier, and occurrence of x is bound occurrence, while the occurrence of y is free occurrence. In (2), the scope of the universal quantifier is P (x) → Q(x), and all concrescences of x are bound. In (3), the scope of (x) is P (x) → (∃y) R(x, y), while the scope of (∃y) is R(x, y). All occurrences of both x and y are bound occurrences. In (4), the scope of the first quantifier is P (x) → R(x) and the scope of the second is R(x) → Q(x). All occurrences of x are bound occurrences. In (5), the scope (∃x) is P (x) ∧ Q(x). In (6), the scope of (∃x) is P (x) and the last of occurrence of x in Q(x) is free.  Negations of Quantified Statements The following rule are used for negating statement s with one quantifier. (i) ¬((x) P(x)) ≡ (∃x) ¬P (x) (ii) ¬((∃x) P(x)) ≡ (x)(¬P (x)) (iii) ¬((x) ¬P (x)) ≡ (∃x) P(x) (iv) ¬((∃x) ¬ P(x)) ≡ (x) (P (x)) Inference Theory of the Predicate Calculus To understand the inference theory of predicate calculus, it is important to be familiar with the following rules: Rule US: Universal specification or instantiation (x)A(x) ⇒ A(y) From (x)A(x), one can conclude A(y). Rule ES: Existential specification (∃x)A(x) ⇒ A(y) From (∃x)A(x), one can conclude A(y). Rule EG: Existential generalization A(x) ⇒ (∃y)A(y) From A(x), one can conclude (∃y)A(y). Rule UG: Universal generalization A(x) ⇒ (y)A(y) From A(x), one can conclude (y)A(y). PROBLEMS 1.Verify the validity of the following arguments: “All men are mortal. Socrates is a man. Therefore, Socrates is mortal”. (or) Show that (x)[H(x) → M(x)] , H(s) ⇒ M(s). Solution: Let us represent the statements as follows: H(x) : x is a man M(x) : x is a mortal s : Socrates Thus, we have to show that (x)[H(x) → M(x)] , H(s) ⇒ M(s). Steps Reason (1) (x)[H(x) → M(x)] Premises (2) H(s) → M(s) Rule US, (1) (3) H(s) Premises  (4) M(s) Modus ponens using (2), (3) Hence, the given statement is valid. 2. Establish the validity of the following argument:”All integers are rational numbers. Some integers are powers of 2. Therefore, some rational numbers are powers of 2”. Solution: Let P (x) : x is an integer R(x) : x is rational number S(x) : x is a power of 2 Hence, the given statements become (x)(P (x) → R(x)), (∃x)(P (x) ∧ S(x)) ⇒ (∃x)(R(x) ∧ S(x)) Steps Reason (1) (∃x)(P (x) ∧ S(x)) Premises (2) P (y) ∧ S(y) Rule ES, (1) (3) P (y) P ∧ Q ⇒ P (2) (4) S(y) P ∧ Q ⇒ Q (2) (5) (x)(P (x) → R(x)) Premises (6) P (y) → R(y) Rule US, (5) (7) R(y) P, P → Q ⇒ Q (3), (6) (8) R(y) ∧ S(y) P, Q ⇒ P ∧ Q (4), (7) (9) (∃x)(R(x) ∧ S(x)) Rule EG, (8) Hence, the given statement is valid. 3.Show that (x)(P (x) → Q(x)) ∧ (x)(Q(x) → R(x)) ⇒ (x)(P (x) → R(x)). Solution: Steps Reason (1) (x)(P (x) → Q(x)) Premises (2) P (y) → Q(y) Rule US, (1) (3) (x)(Q(x) → R(x)) Premises (4) Q(y) → R(y) Rule US, (3) (5) P (y) → R(y) Hypothetical syllogism using (2), (4) (6) (x)(P (x) → R(x)) Rule UG, (5) Hence, the given statement is valid. 4. Show that (∃x)M(x) follows logically from the premises (x)(H(x) → M(x)) and (∃x)H(x). Solution: Steps Reason (1) (∃x)H(x) Premises (2) H(y) Rule ES, (1) (3) (x)(H(x) → M(x)) Premises (4) H(y) → M(y) Rule US, (3) (5) M(y) Modus Ponens using (2), (4) (6) (∃x)M(x) Rule EG, (5) Hence, the result. 5.Show that from (∃x)[F (x) ∧S(x)] → (y)[M(y) → W (y)] and (∃y)[M(y) ∧ ¬W (y)] the conclusion (x)[F (x) → ¬S(x)] follows. Solution: Steps Reason (1) (∃y)[M(y) ∧ ¬W (y)] Premises (2) [M(z) ∧ ¬W (z)] Rule ES, (1) (3) ¬[M(z) → W (z)] ¬(P → Q) ⇔ P ∧ ¬Q (2) (4) (∃y)¬[M(y) → W (y)] Rule EG, (3) (5) ¬(y)[M(y) → W (y)] ¬(x)A(x) ⇔ (∃x)¬A(x) (4) (6) (∃x)[F (x) ∧ S(x)] → (y)[M(y) → W (y) ] Premises (7) ¬(∃x)[F (x) ∧ S(x)] Modus Tollens (5), (6) (8) (x)¬[F (x)∧S(x)] ¬(x)A(x) ⇔ (∃x)¬A(x) (7) (9) ¬[F (z) ∧ S(z)] Rule US, (8) (10) ¬F (z) ∨ ¬S(z) De Morgan‘s laws (9) (11) F (z) → ¬S(z) P → Q ⇔ ¬P ∨ Q (10) (12) (x)(F (x) → ¬S(x)) Rule UG, (11) Hence, the result. PRACTICE PROBLEMS 1. Show that (∃x)[P (x) ∧ Q(x)] ⇒ (∃x)P (x) ∧ (∃x)Q(x) and also verify the converse is true. 2. Show that (x)(P (x) ∨ Q(x)) ⇒ (x)P (x) ∨ (∃x)Q(x). 3. Using predicate logic, prove the validity of the following argument: “Every husband argues with his wife. x is a husband. Therefore, x argues with his wife”. 4. Prove using rules of inference Duke is a Labrador retriever. All Labrador retriever like to swim. Therefore, Duke likes to swim.  MODULE: 2 ALGEBRAIC STRUCTURES SETS DEFINITION A set is an unordered collection of objects. DEFINITION The objects in a set are called elements or members of the set. A set is said to contain its elements. We write a  A to denote that a is an element of the set A. The notation a  A denotes that a is not an element of the set A. NOTE Sets to be denoted using uppercase letters. Lowercase letters are usually used to denote elements of sets. EXAMPLE 1.The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}. 2. The set O of odd positive integers less than 10 can be expressed by O = {1, 3, 5, 7, 9}. 3. Although sets are usually used to group together elements with common properties, there is nothing that prevents a set from having seemingly unrelated elements. For instance, {a, 2, Fred, New Jersey} is the set containing the four elements a, 2, Fred, and New Jersey. 4. The set {N, Z, Q, R} is a set containing four elements, each of which is a set. The four elements of this set are N, the set of natural numbers; Z, the set of integers; Q, the set of rational numbers; and R, the set of real numbers. EQUAL SETS Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if ∀x (x ∈ A ↔ x ∈ B). We write A = B if A and B are equal sets. EMPTY SET There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by ∅. The empty set can also be denoted by { }. NOTE 1.It does not matter if an element of a set is listed more than once, so {1, 3, 3, 3, 5, 5, 5, 5} is the same as the set {1, 3, 5} because they have the same elements. 2. A set with one element is called a singleton set. SUBSET The set A is a subset of B if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B. Showing that A is a Subset of B, To show that A ⊆ B, show that if x belongs to A then x also belongs to B. EXAMPLE 1.The set of all odd positive integers less than 10 is a subset of the set of all positive integers less than 10. 2.The set of rational numbers is a subset of the set of real numbers. PROPER SUBSET A set A is called proper subset of the set B. If (i) A is subset of B and (ii) B is not a subset A i.e., A is said to be a proper subset of B if every element of A belongs to the set B, but there is atleast one element of B, which is not in A. If A is a proper subset of B, then we denote it by A  B. cardinality Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by |S|. EXAMPLE 1.Let A be the set of odd positive integers less than 10. Then |A| = 5. 2. Let S be the set of letters in the English alphabet. Then |S| = 26. 3.The null set has no elements, it follows that |∅| = 0. INFINITE A set is said to be infinite if it is not finite. EXAMPLE The set of positive integers is infinite. UNIVERSAL SET The universal set U, which contains all the objects under consideration. POWER SET Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S). If a set has n elements, then its power set has 2 n elements. EXAMPLE: 1.What is the power set of the set {0, 1, 2}? Solution: The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence, P({0, 1, 2}) = {∅,{0},{1},{2},{0, 1},{0, 2},{1, 2},{0, 1, 2}}. Note that the empty set and the set itself are members of this set of subsets. 2. What is the power set of the empty set? What is the power set of the set {∅}? Solution: The empty set has exactly one subset, namely, itself. Consequently, P(∅) = {∅}. The set {∅} has exactly two subsets, namely, ∅ and the set {∅} itself. Therefore, P({∅}) = {∅,{∅}}. CARTESIAN PRODUCT Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence, A × B = {(a, b) | a ∈ A ∧ b ∈ B}. EXAMPLE 1.What is the Cartesian product of A = {1, 2} and B = {a, b, c}? Solution: The Cartesian product A × B is A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. 2. Let A represent the set of all students at a university, and let B represent the set of all courses offered at the university. What is the Cartesian product A × B and how can it be used? Solution: The Cartesian product A × B consists of all the ordered pairs of the form (a, b), where a is a student at the university and b is a course offered at the university. One way to use the set A × B is to represent all possible enrollments of students in courses at the university. 3. What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2} ? Solution: The Cartesian product A × B × C consists of all ordered triples (a, b, c), where a ∈ A, b ∈ B, and c ∈ C. Hence, A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1),(1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)} PRACTICE PROBLEMS 1. List the members of these sets. a) {x | x is a real number such that x 2 = 1} b) {x | x is a positive integer less than 12} c) {x | x is the square of an integer and x < 100} 2. Use set builder notation to give a description of each of these sets. a) {0, 3, 6, 9, 12} b) {−3, −2, −1, 0, 1, 2, 3} 3. What is the cardinality of each of these sets? a) ∅ b) {∅} c) {∅,{∅}} d) {∅,{∅},{∅,{∅}}} 4. Find the power set of each of these sets, where a and b are distinct elements. a) {a} b) {a, b} c) {∅,{∅}} 5. Find A2 if a) A = {0, 1, 3}. b) A = {1, 2, a, b} Answer 1. a) {1,-1}; b) {1,2,3,4,5,6,7,8,9,10,11}; c) {0, 1, 4, 9, 16, 25, 36, 49, 64, 81} 2. a){3n / n = 0, 1, 2, 3, 4}; b) { x /  3  x  3}  3. a)0; b)1; c)2; d)3 4. a) {∅,{a}} ; b) {∅, {a}, {b}, {a,b}}; c) {∅,{0},{{0}},{0,{0}}} 5. a) {(0,0), (0,1),(0,3),(1,0), (1,1),(1,3), (3,0),(3,1),(3,3)} b) {(1,1),(1,2),(1,a),(1,b),(2,1), (2,2),(2,a),(2,b),(a,1),( (a,2),(a,a),(a,b),(b,1), (b,2), (b,a),(b,b)} SET OPERATIONS EXAMPLE Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}. Because A ∩ B = ∅, A and B are disjoint. UNION Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set that contains those elements that are either in A or in B, or in both. It is denoted by A ∪ B = {x | x ∈ A ∨ x ∈ B}. EXAMPLE 1.The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5}; that is, {1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}. 2. The union of the set of all computer science majors at your school and the set of all mathematics majors at your school is the set of students at your school who are majoring either in mathematics or in computer science (or in both) INTERSECTION Let A and B be sets. The intersection of the sets A and B, denoted by A ∩ B, is the set containing those elements in both A and B. It is denoted by A ∩ B = {x | x ∈ A ∧ x ∈ B}. EXAMPLE 1. The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3}; that is, {1, 3, 5} ∩ {1, 2, 3} = {1, 3}. 2. The intersection of the set of all computer science majors at your school and the set of all mathematics majors is the set of all students who are joint majors in mathematics and computer science. DIFFERENCE OF SETS Let A and B be sets. The difference of A and B, denoted by A − B, is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A. It is denoted by A – B thus: A – B = {x | x ∈ A and x  B}. EXAMPLE The difference of {1, 3, 5} and {1, 2, 3} is the set {5}; that is, {1, 3, 5} − {1, 2, 3} = {5}. This is different from the difference of {1, 2, 3} and {1, 3, 5}, which is the set {2} COMPLEMENT OF A SET Let U be the universal set. The complement of the set A, denoted by A , is the complement of A with respect to U. Therefore, the complement of the set A is U – A. It is denoted by A thus A {x U / x  A}. EXAMPLE 1.Let A = {a, e, i, o, u} (where the universal set is the set of letters of the English alphabet). Then A = {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y,z}. 2. Let A be the set of positive integers greater than 10 (with universal set the set of all positive integers). Then A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. DISJOINT SETS Two sets are called disjoint if their intersection is the empty set. VENN DIAGRAM A venn diagram is a pictorial representation of the set. The universal set U is normally represented by a rectangle and its subsets as circles inside it. Venn diagram are useful in understanding relations among sets and operations on set. PRACTICE PROBLEMS 1. Let A = {a, b, c, d, e} and B = {a, b, c, d, e, f, g, h}. Find a) A ∪ B; b) A ∩ B; c) A – B; d) B − A. 2. Let A and B be sets. Prove the commutative laws A ∪ B = B ∪ A 3. Let A = {0, 2, 4, 6, 8, 10}, B = {0, 1, 2, 3, 4, 5, 6}, and C = {4, 5, 6, 7, 8, 9, 10}. Find a) A ∩ B ∩ C. b) A ∪ B ∪ C. c) (A ∪ B) ∩ C. d) (A ∩ B) ∪ C ANSWER 2. A ∪ B = {x | x ∈ A ∨ x ∈ B} = {x | x ∈ B ∨ x ∈ A} = B U A 3. a) { 4, 6}; b) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; c) { 4, 5, 6, 8, 10}; d) {0, 2, 4, 5, 6, 7, 8, 9, 10}. FUNCTIONS DEFINITION Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f (a) = b if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write f : A → B. NOTE Functions are sometimes also called mappings or transformations. EXAMPLE Let X = {1, 2, 3}, Y = {p, q, r} and f = {(1, q), (2, p), (3, r)} then f(1) = q, f(2) = p, f(3) = r. Clearly f is a function from X to Y. DEFINITION If f is a function from A to B, we say that A is the domain of f and B is the codomain of f. If f (a) = b, we say that b is the image of a and a is a preimage of b. The range, or image, of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that f maps A to B. EXAMPLE 1. If the function f is defined by f(x) = x 2 + 1 on the set {−2, −1, 0, 1, 2}, find the range of f. Solution: f(−2) = (2)2 + 1 = 5 f(−1) = (1) 2 + 1 = 2 f(0) = 0 + 1 = 1 f(1) = 1 + 1 = 2 f(2) = 4 + 1 = 5 Therefore, the range of f = {1, 2, 5} 2. Let R be the relation with ordered pairs (Abdul, 22), (Brenda, 24), (Carla, 21), (Desire, 22), (Eddie, 24), and (Felicia, 22). Here each pair consists of a graduate student and this student’s age. Specify a function determined by this relation. Solution: If f is a function specified by R, then f (Abdul) = 22, f (Brenda) = 24, f (Carla) = 21, f (Desire) = 22, f (Eddie) = 24, and f (Felicia) = 22. (Here, f (x) is the age of x, where x is a student.) For the domain, we take the set {Abdul, Brenda, Carla, Desire, Eddie, Felicia}. The range of the function we have specified is the set of different ages of these students, which is the set {21, 22, 24}. ONE-TO-ONE (INJECTIVE) A function f is said to be one-to-one, or an injective, if and only if f (a) = f (b)implies that a = b for all a and b in the domain of f. i.e distinct elements should have distinct images A function is said to be injection if it is one-to-one. EXAMPLE Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f (a) = 4, f (b) = 5, f (c) = 1, and f (d) = 3 is one-to-one. Solution: The function f is one-to-one because f takes on different values at the four elements of its domain. 2.Determine whether f : Z → Z given by f(x) = x 2 , x ∈ Z is a one-to-One function. Solution: The function f : Z → Z given by f(x) = x 2 , x ∈ Z is not a one-to-one function. This is because both 3 and -3 have 9 as their image, which is against the definition of a one-to-one function. 3. Determine whether the function f (x) = x + 1 from the set of real numbers to itself is one-to- one. Solution: The function f (x) = x + 1 is a one-to-one function. To demonstrate this, note that x + 1  y + 1 when x  y. ONTO(Surjective) A function f from A to B is called onto, or a surjective, if and only if for every element b ∈ B there is an element a ∈ A with f (a) = b. A function f is called surjection if it is onto. EXAMPLE 1. Let f be the function from {a, b, c, d} to {1, 2, 3} defined by f (a) = 3, f (b) = 2, f (c) = 1, and f (d) = 3. Is f an onto function? Solution: All three elements of the codomain are images of elements in the domain, we see that f is onto. 2. Is the function f (x) = x + 1 from the set of integers to the set of integers onto? Solution: This function is onto, because for every integer y there is an integer x such that f (x) = y. To see this, note that f (x) = y if and only if x + 1 = y, which holds if and only if x = y − 1. BIJECTIVE The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective. EXAMPLE 1.Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c) = 1, and f (d) = 3. Is f a bijection? Solution: The function f is one-to-one and onto. It is one-to-one because no two values in the domain are assigned the same function value. It is onto because all four elements of the codomain are images of elements in the domain. Hence, f is a bijection. 2.Show that a mapping f : R → R defined by f(x) = 2x + 1 for x ∈ R is a bijective map from R to R. Solution: Let f : R → R defined by f(x) = 2x + 1 for x ∈ R. We need to prove that f is a bijective map, i.e., it is enough to prove that f is one-one and onto. Proof of f being one-to-one: Let x and y be any two elements in R such that ⇒f(x) = f(y) ⇒ 2x + 1 = 2y + 1 ⇒x=y Thus, f(x) = f(y) ⇒ x = y This implies that f is one-to-one. Proof of f being onto: Let y be any element in the codomain R ⇒ f(x) = y ⇒ 2x + 1 = y ⇒ x = (y-1)/2 Clearly, x = (y-1)/2∈ R Thus, every element in the codomain has pre-image in the domain. This implies that f is onto. Hence, f is a bijective map. INVERSE FUNCTION Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that f (a) = b. The inverse function of f is denoted by f 1. Hence, f 1 (b) = a when f (a) = b. NOTE: A one-to-one correspondence is called invertible because we can define an inverse of this function. A function is not invertible if it is not a one-to-one correspondence, because the inverse of such a function does not exist. EXAMPLE 1. Let f be the function from {a, b, c} to {1, 2, 3} such that f (a) = 2, f (b) = 3, and f (c) = 1. Is f invertible, and if it is, what is its inverse? Solution: The function f is invertible because it is a one-to-one correspondence. The inverse function f 1 reverses the correspondence given by f , so f 1(1)  c, f 1(2)  a and f 1 (3)  b. 2. Let f be the function from R to R with f (x) = x 2. Is f invertible? Solution: Because f (−2) = f (2) = 4, f is not one-to-one. If an inverse function were defined, it would have to assign two elements to 4. Hence, f is not invertible. (Note we can also show that f is not invertible because it is not onto.) 3. f : R → R is defined by f(x) = ax + b, for a, b ∈ R and a  0. Show that f is invertible and find the inverse of f. Solution (i) First we shall show that f is one-to-one  Let x 1 , x 2 ∈ R such that f( x 1 ) = f( x 2 ) ⇒ a x1 + b = a x 2 + b ⇒ a x1 = a x 2 ⇒ x1 = x 2 ∴ f is one-to-one. (ii) To show that f is onto. Let y ∈ R(codomain) such that y = f(x) for some x ∈ R. ⇒ y = ax + b ⇒ ax = y − b ⇒ x = (y-b)/a Given y ∈ R(codomain), there exists an element x = (y-b)/a ∈ R such that f(x) = y. ∴ f is onto xb ⇒ f is invertible and f 1  x   a IDENTITY FUNCTION Let X be any set and f be a function such that f : X → X is defined by f(x) = x for all x ∈ X. Then, f is called the identity function or identity transformation on X. It can be denoted by I or IX. Note: The identity function is both one-to-one and onto. Let I X ( x )  I X ( y ) ⇒x=y ⇒ I X is one-to-one IX is onto since x  I X ( x ) for all x. COMPOSITION OF FUNCTIONS Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted for all a ∈ A by f ◦ g, is defined by (f ◦ g)(a) = f (g(a)). EXAMPLE 1.Let g be the function from the set {a, b, c} to itself such that g(a) = b, g(b) = c, and g(c) = a. Let f be the function from the set {a, b, c} to the set {1, 2, 3} such that f (a) = 3, f (b) = 2, and f (c) = 1. What is the composition of f and g, and what is the composition of g and f ? Solution: The composition f ◦ g is defined by (f ◦ g)(a) = f (g(a)) = f (b) = 2, (f ◦ g) (b) = f (g(b)) = f (c) = 1, and (f ◦ g)(c) = f (g(c)) = f (a) = 3. g ◦ f is not defined, because the range of f is not a subset of the domain of g. 2.Let f and g be the functions from the set of integers to the set of integers defined by f (x) = 2x + 3 and g(x) = 3x + 2. What is the composition of f and g? What is the composition of g and f ? Solution: Both the compositions f ◦ g and g ◦ f are defined. Moreover, (f ◦ g)(x) = f (g(x)) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7 and (g ◦ f )(x) = g(f (x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11. 3.Let f(x) = x + 2, g(x) = x − 2 and h(x) = 3x for x ∈ R, where R is the set of real numbers. Find g ◦ f; f ◦ g; f ◦ f; g ◦ g; f ◦ h; h ◦ g; h ◦ f; and f ◦ h ◦ g. Solution: f : R → R is defined by f(x) = x + 2 g: R → R is defined by g(x) = x – 2 h : R → R is defined by h(x) = 3x  g ◦ f : R → R Let x ∈ R. Thus, we can write (g ◦ f)(x) = g(f(x)) = g(x + 2) = x + 2 − 2 = x ∴ (g ◦ f)(x) = {(x, x)| x ∈ R}  (f ◦ g)(x) = f(g(x)) = f(x − 2) = (x − 2) + 2 = x ∴ f ◦ g = {(x, x)| x ∈ R}  (f ◦ f)(x) = f(f(x)) = f(x + 2) = x + 2 + 2 = x + 4 ∴ f ◦ f = {(x, x + 4)| x ∈ R}  (g ◦ g)(x) = g(g(x)) = g(x − 2) = x − 2 − 2 = x − 4 ∴ g ◦ g = {(x, x − 4)| x ∈ R}  (f ◦ h)(x) = f(h(x)) = f(3x) = 3x + 2 ∴ f ◦ h = {(x, 3x + 2)| x ∈ R}  (h ◦ g)(x) = h(g(x)) = h(x − 2) = 3(x − 2) = 3x – 6 ∴ h ◦ g = {(x, 3x − 6)| x ∈ R}  (h ◦ f)(x) = h(f(x)) = h(x + 2) = 3(x + 2) = 3x + 6 ∴h ◦ f = {(x, 3x + 6)| x ∈ R}  (f ◦ h ◦ g)(x) = [f ◦ (h ◦ g)](x) f(h ◦ g(x)) = f(3x − 6) = 3x − 6 + 2 = 3x – 4 ∴ f ◦ h ◦ g = {(x, 3x − 4)| x ∈ R}. 4. Let f and g be functions from the positive real numbers to positive real numbers defined by f(x) = [2x], g(x) = x 2. Calculate f ◦ g and g ◦ f. Solution: f ◦ g(x) = f(g(x)) =f( x 2 )=[2 x 2 ] g ◦ f(x) = g(f(x))=g([2x])= 2x 2 FLOOR AND CEILING FUNCTIONS Let x be a real number, then the least integer that is not less than x is called the CEILING of x. The CEILING of x is denoted by ⌈x⌉. EXAMPLES ⌈2.15⌉ = 3, ⌈ √ 5⌉ = 3, ⌈ −7.4⌉ = −7, ⌈−2⌉ = −2 Let x be any real number, then the greatest integer that does not exceed x is called the Floor of x. The FLOOR of x is denoted by ⌊x⌋. EXAMPLES ⌊5.14⌋ = 5, ⌊ √5⌋ = 2,⌊ −7.6⌋ = −8,⌊6⌋ = 6,⌊ −3⌋ = −3 RELATIONS AND THEIR PROPERTIES Let A and B be sets. A binary relation from A to B is a subset of A × B. In other words, a binary relation from A to B is a set R of ordered pairs where the first element of each ordered pair comes from A and the second element comes from B. We use the notation aRb to denote that (a, b) ∈ R and aRb to denote that (a, b)  R. Moreover, when (a, b) belongs to R, a is said to be related to b by R. EXAMPLE: Let A = {0, 1, 2} and B = {a, b}. Then {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. This means, for instance, that 0 R a, but that 1R  b. Relations can be represented graphically or by using table. DEFINITION A relation on a set A is a relation from A to A. In other words, a relation on a set A is a subset of A × A. EXAMPLE: 1.Define a relation between two sets A = {5, 6, 7} and B = {x, y}. Solution: If A = {5, 6, 7} and B = {x, y}, then the subset R = {(5, x), (5, y), (6, x), (6, y)} is a relation from A to B. 2. Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) | a divides b}? Solution: Because (a, b) is in R if and only if a and b are positive integers not exceeding 4 such that a divides b, we see that R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}. 3.How many relations are there on a set with n elements? Solution: A relation on a set A is a subset of A × A. Because A × A has n 2 elements when A has n elements, and a set with m elements has 2m subsets, there are 2 n subsets of A × A. Thus, 2 there are 2 n relations on a set with n elements. For example, there are 2 3 = 2 9 = 512 relations 2 2 on the set {a, b, c}. PROPERTIES OF RELATIONS A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A. A relation R on a set A is called symmetric if(b, a) ∈ R whenever(a, b) ∈ R, for all a, b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric. A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A. EXAMPLE 1.Consider the following relations on {1, 2, 3, 4}: R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}, R2 = {(1, 1), (1, 2), (2, 1)}, R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}, R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}, R6 = {(3, 4)}. Which of these relations are reflexive, symmetric, antisymmetric and transitive? Solution: The relations R3 and R5 are reflexive because they both contain all pairs of the form (a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4). The other relations are not reflexive because they do not contain all of these ordered pairs. In particular, R 1 , R 2 , R 4 and R6 are not reflexive because (3, 3) is not in any of these relations. The relations R 2 and R3 are symmetric, because in each case (b, a) belongs to the relation whenever (a, b) does. For R 2 , the only thing to check is that both (2, 1) and (1, 2) are in the relation. For R3 , it is necessary to check that both (1, 2) and (2, 1) belong to the relation, and (1, 4) and (4, 1) belong to the relation. R4 , R5 , and R6 are all antisymmetric. For each of these relations there is no pair of elements a and b with a  b such that both (a, b) and (b, a) belong to the relation. R4 , R5 , and R6 are transitive. For each of these relations, we can show that it is transitive by verifying that if (a, b) and (b, c) belong to this relation, then (a, c) also does. For instance, R 4 is transitive, because (3, 2) and (2, 1), (4, 2) and (2, 1), (4, 3) and (3, 1), and (4, 3) and (3, 2) are the only such sets of pairs, and (3, 1), (4, 1), and (4, 2) belong to R4. PRACTICE PROBLEMS 1. List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3}, where (a, b) ∈ R if and only if a) a = b. b) a + b = 4. c) a>b. d) a | b. 2. For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive. a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} c) {(2, 4), (4, 2)} 3. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive, where (x, y) ∈ R if and only if a) x  y. b) xy ≥ 1. ANSWER 1.a) {(0,0), (1, 1), (2,2), (3,3)} b) {(1,3),(2,2),(3, 1), (4,0)} c) {(1,0), (2,0), (2, 1),(3,0), (3,1),(3,2),(4,0), (4, 1), (4,2), (4,3)} d) Recall that a I b means that b is a multiple of a (a is not allowed to be 0). Thus the answer is { (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 2), (3, 0), (3, 3), (4, O)}. 2.a) not reflexive, not symmetric, not antisymmetric, transitive. b) reflexive, symmetric, not antisymmetric, transitive.  c) not reflexive, symmetric, not antisymmetric, not transitive. 3.a) not reflexive, symmetric, not antisymmetric, not transitive. b) not reflexive, symmetric, not antisymmetric, transitive. Relation Matrix: A relation R from a finite set X to a finite set Y can be represented by a matrix is called the relation matrix of R. Let A  a1, a2 ,...,am and B  b1, b2 ,...,bn be finite sets containing m and n elements, respectively, and R be the relation from A to B. Then R can   be represented by an m × n matrix M R  mij , which is defined as follows 1 if (ai , b j )  R, mij   0 if (ai , b j )  R. EXAMPLE 1.Suppose that A = {1, 2, 3} and B = {1, 2}. Let R be the relation from A to B containing (a, b) if a ∈ A, b ∈ B, and a>b. What is the matrix representing R if a 1  1, a 2  2 and a3  3 and b1  1 and b 2  2 ? Solution: Because R = {(2, 1), (3, 1), (3, 2)}, the matrix for R is 0 0 M R  1 0 1 1 The 1s in M R show that the pairs (2, 1), (3, 1), and (3, 2) belong to R. The 0s show that no other pairs belong to R. 2. Let A a1, a2 , a3 and B  b1, b2 , b3 , b4 , b5. Which ordered pairs are in the relation R 0 1 0 0 0    represented by the matrix M R  1 0 1 1 0 ? 1 0 1 0 1 Solution:   Because R consists of those ordered pairs ai , b j with mij  1, it follows that R  a1,b2 , a2 ,b1 , a2 ,b3 , a2 ,b4 , a3 ,b1 , a3 ,b3 , a3 ,b5  3.Suppose that the relation R on a set is represented by the matrix 1 1 0  M R  1 1 1 . Is R reflexive, symmetric, and/or antisymmetric? 0 1 1  Solution:  Because all the diagonal elements of this matrix are equal to 1, R is reflexive. Moreover, because M R is symmetric, it follows that R is symmetric. It is also easy to see that R is not antisymmetric. 4. Find the matrix representing the relation R 2 , where the matrix representing R is 0 1 0  M R  0 1 1. 1 0 0 0 1 1 [ 2]   Solution: The matrix for R 2 is M R 2  M R  1 1 1. 0 1 0 5. Let R = {(1, 2), (3, 4), (2, 2)} and S = {(4, 2), (2, 5), (3, 1), (1, 3)}. Find R ◦ S, S ◦ R, R ◦ (S ◦ R), (R ◦ S) ◦ R, R ◦ R, S ◦ S, and (R ◦ R) ◦ R. Solution: Given R = {(1, 2), (3, 4), (2, 2)} and S = {(4, 2), (2, 5), (3, 1), (1, 3)}. R ◦ S = {(1, 5), (3, 2), (2, 5)} S ◦ R = {(4, 2), (3, 2), (1, 4)} R ◦( S ◦ R) = {(3, 2)} = (R ◦ S) ◦ R R ◦ R = {(1, 2), (2, 2)} S ◦ S = {(4, 5), (3, 3), (1,1)} (R ◦ R) ◦ R = {(1, 2), (2, 2)} Example: Let A = {a, b, c}, and R and S be relations on A whose matrices are as given below: 1 0 1 1 0 0 M R  1 1 1 and M S  0 1 1   0 1 0 1 0 1 Find the composite relations R ◦ S, S ◦ R, R ◦ R, S ◦ S and their matrices. Solution: R = {(a, a), (a, c), (b, a), (b, b), (b, c), (c, b)} S= {(a, a), (b, b), (b, c), (c, a), (c, c)}. From these, we find that R ◦ S = {(a, a), (a, c), (b, a), (b, b), (b, c), (c, b), (c, c)} S ◦ R = {(a, a), (a, c), (b, b), (b, a), (b, c), (c, a), (c, b), (c, c)} R ◦ R = R 2 = {(a, a), (a, c), (a, b), (b, a), (b, c), (b, b), (c, a), (c, b), (c, c)} S ◦ S = S 2 = {(a, a), (b, b), (b, c), (b, a), (c, a), (c, c)} The matrices of the above composite relations are as given below:  1 0 1 1 0 1 1 1 1 M R S  1 1 1 ; M S  R  1 1 1 ; M R R  1 1 1 and     0 1 1 1 1 1 1 1 1 1 0 0 M S S  1 1 1  1 0 1  DIRECTED GRAPH A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge NOTE: An edge of the form (a, a) is represented using an arc from the vertex a back to itself. Such an edge is called a loop. EXAMPLE: 1. The directed graph with vertices a, b, c, and d, and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) 2. The directed graph of the relation R = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)} on the set {1, 2, 3, 4} is shown in 3. What are the ordered pairs in the relation R represented by the directed graph shown in  Solution: The ordered pairs (x, y) in the relation are R = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3)}. Each of these pairs corresponds to an edge of the directed graph, with (2, 2) and (3, 3) corresponding to loops. PRACTICE PROBLEMS 1. Represent each of these relations on {1, 2, 3, 4} with a matrix (with the elements of this set listed in increasing order). a) {(1, 2),(1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} b) {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)} 2. List the ordered pairs in the relations on {1, 2, 3} corresponding to these matrices (where the rows and columns correspond to the integers listed in increasing order). 1 0 1  0 1 0     a) 0 1 0  b) 0 1 0 1 0 1  0 1 0 0 1 0    3. Let R be the relation represented by the matrix M R  0 0 1. Find the matrices that 1 1 0 represent a) R 2 b) R 3 CLOSURES OF RELATION Let R be a relation on a set A. R may or may not have some property P, such as reflexivity, symmetry, or transitivity. If there is a relation S with property P containing R such that S is a subset of every relation with property P containing R, then S is called the closure. Reflexive Closure: Given a relation R on a set A, the smallest relation containing R and which is reflexive is its reflexive closure. we may form the reflexive closure of R by adding: Rr = R ∪ ∆, where ∆ = {(a, a) | a ∈ A} is the diagonal relation on A. Symmetric Closure: Given a relation R on a set A, the smallest relation containing R and which is symmetric is its symmetric closure. we may form the symmetric closure of R, Rs , by taking the union of R with R−1 : Rs = R ∪ R−1 = R ∪ {(b, a) | (a, b) ∈ R}.  Transitive Closure: Let A be a set and R a relation on A. The transitive closure of R is the smallest relation containing R and which is transitive. The transitive closure relation Rt on A that satisfies the following three properties: 1. Rt is transitive. 2. R ⊆ Rt. 3. If S is any other transitive relation that contains R, then Rt ⊆ S. EXAMPLE: 1.What is the reflexive closure of the relation R = {(a, b) | a < b} on the set of integers? Solution: The reflexive closure of R is R ∪ ∆ = {(a, b) | a < b} ∪ {(a, a) | a ∈  } = {(a, b)| a  b}. 2.What is the symmetric closure of the relation R = {(a, b) | a>b} on the set of positive integers? Solution: The symmetric closure of R is the relation R ∪ R  1 = {(a, b) | a>b}∪{(b, a) | a>b}={(a, b) | a  b}. This last equality follows because R contains all ordered pairs of positive integers where the first element is greater than the second element and R  1 contains all ordered pairs of positive integers where the first element is less than the second. EQUIVALENCE RELATIONS A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. Two elements a and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation. EXAMPLE 1.Let R be the relation on the set of real numbers such that aRb if and only if a − b is an integer. Is R an equivalence relation? Solution: (i)Because a − a = 0 is an integer for all real numbers a, aRa for all real numbers a. Hence, R is reflexive. (ii)Now suppose that aRb. Then a − b is an integer, so b − a is also an integer. Hence, bRa. It follows that R is symmetric. (iii)If aRb and bRc, then a − b and b − c are integers. Therefore, a − c = (a − b) + (b − c) is also an integer. Hence, aRc. Thus, R is transitive. Consequently, R is an equivalence relation. 2.Let X = {1, 2, 3,..., 7} and R ={(x, y)| x − y is divisible by 3}. Show that R is an equivalence relation. Solution: (i). For any x ∈ X, x − x = 0 is divisible by 3. ∴ xRx ⇒ R is reflexive. (ii). For any x, y ∈ X, if xRy, then x − y is divisible by 3. ⇒ −(x − y) is divisible by 3. ⇒ y − x is divisible by 3. ⇒ yRx Thus, the relation R is symmetric. (iii). For any x, y, z ∈ X, let xRy and yRz. ⇒ (x − y) + (y − z) is divisible by 3 ⇒ x − z is divisible by 3 ⇒ xRz Hence, the relation R is transitive. Thus, the relation R is an equivalence relation. 3.Suppose that R is the relation on the set of strings of English letters such that aRb if and only if l(a) = l(b), where l(x) is the length of the string x. Is R an equivalence relation? Solution: (i) Because l(a) = l(a), it follows that aRa whenever a is a string, so that R is reflexive. (ii)Next, suppose that aRb, so that l(a) = l(b). Then bRa, because l(b) = l(a). Hence, R is symmetric. (iii)Finally, suppose that aRb and bRc. Then l(a) = l(b) and l(b) = l(c). Hence, l(a) = l(c), so aRc. Consequently, R is transitive. Because R is reflexive, symmetric, and transitive, it is an equivalence relation. CONGRUENCE RELATION Let I denote the set of all positive integers, and let m be a positive integer. For x ∈ I and y ∈ I, define R as R = {(x, y)| x − y is divisible by m }. The statement “x − y is divisible by m” is equivalent to the statement that both x and y have the same remainder when each is divided by m. In this case, denote R by ≡ and to write xRy as x ≡ y (mod m), which is read as “x equals to y modulo m”. The relation ≡ is called a congruence relation. Example: 83 ≡ 13(mod 5), since 83-13=70 is divisible by 5. EXAMPLE 1.Prove that the relation “congruence modulo m” over the set of positive integers is an equivalence relation. Solution: Let N be the set of all positive integers and m be a positive integer. We define the relation “congruence modulo m” on N as follows: Let x, y ∈ N. x ≡ y (mod m) if and only if x − y is divisible by m. Let x, y, z ∈ N. Then (i). x − x = 0 is divisible by m ⇒ x ≡ x (mod m) for all x ∈ N (ii). Let x ≡ y (mod m). Then, x − y is divisible by m. ⇒ −(x − y) = y − x is divisible by m. i.e., y ≡ x (mod m) ∴ The relation ≡ is symmetric. ⇒ x − y and y − z are divisible by m. Now (x − y) + (y − z) is divisible by m. i.e., x − z is divisible by m. ⇒ x ≡ z (mod m) ∴ The relation ≡ is transitive. Since the relation ≡ is reflexive, symmetric and transitive, the relation congruence modulo m is an equivalence relation. 2.Let R denote a relation on the set of ordered pairs of positive integers such that (x,y)R(u, v) iff xv = yu. Show that R is an equivalence relation. Solution: Let R denote a relation on the set of ordered pairs of positive integers. Let x, y, u and v be positive integers. Given (x, y)R(u, v) if and only if xv = yu. (i). Since xy = yx is true for all positive integers ⇒ (x, y)R(x, y), for all ordered pairs (x, y) of positive integers. ∴ The relation R is reflexive. (ii). Let (x, y)R(u, v) ⇒ xv = yu ⇒ yu = xv ⇒ uy = vx ⇒ (u, v)R(x, y) ∴ The relation R is symmetric. (iii). Let x, y, u, v, m and n be positive integers Let (x, y)R(u, v) and (u, v)R(m, n) ⇒ xv = yu and un = vm ⇒ xvun = yuvm ⇒ xn = ym, by canceling uv ⇒ (x, y)R(m, n) ∴ The relation R is transitive. Since R is reflexive, symmetric and transitive, hence the relation R is an equivalence relation. EQUIVALENCE CLASSES Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. The equivalence class of a with respect to R is denoted by aR. When only one relation is under consideration, we can delete the subscript R and write [a] for this equivalence class. EXAMPLE 1.What are the equivalence classes of 0 and 1 for congruence modulo 4? Solution: The equivalence class of 0 contains all integers a such that a ≡ 0 (mod 4). The integers in this class are those divisible by 4. Hence, the equivalence class of 0 for this relation is = {..., −8, −4, 0, 4, 8,...}. The equivalence class of 1 contains all the integers a such that a ≡ 1 (mod 4). The integers in this class are those that have a remainder of 1 when divided by 4. Hence, the equivalence class of 1 for this relation