CU-BCA-SEM-I-Mathematics (1)

11.8 REFERENCES References book ● Kenneth H. Rosen, ”Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw – Hill Pub. Co. Ltd, New Delhi, 2011. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Thomas Koshy, “Elementary Number Theory with Applications”, Elsevier Publications, New Delhi, 2002. ● Tremblay J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011. ● San Ling and Chaoping Xing, “Coding Theory – A first Course”, Cambridge Publications, Cambridge, 2004. 201 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 12: COMBINATIONS 2 STRUCTURE 12.0 Learning Objectives 12.1 Introduction 12.2 Combinations 12.3 Pigeonhole principle 12.4 Summary 12.5 Keywords 12.6 Learning Activity 12.7 Unit End Questions 12.8 References 12.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Explain the likelihood of compound events and solving issues, correctly use permutations and combinations. ● Describe the likelihood of a compound event or solve a problem by calculating permutations and combinations ● Calculate and apply combinations ● Analyse permutations and combinations in applications. 12.1 INTRODUCTION We turn first to counting. While this sounds simple, perhaps too simple to study, it is not. When we speak of counting, it is shorthand for determining the size of a set, or more often, the sizes of many sets, all with something in common, but different sizes depending on one or more parameters. For example: how many outcomes are possible when a die is rolled? Two dice? n dice? As stated, this is ambiguous: what do we mean by “outcome”? Suppose we roll two dice, say a red die and a green die. Is “red two, green three” a different outcome than “red three, green two”? If yes, we are counting the number of possible “physical” outcomes, namely 36. If no, there are 21. We might even be interested simply in the possible totals, in which case there are 11 outcomes. 202 CU IDOL SELF LEARNING MATERIAL (SLM)

Even the quite simple first interpretation relies on some degree of knowledge about counting; we first make two simple facts explicit. In terms of set sizes, suppose we know that set A has size m and set B has size n. What is the size of A and B together, that is, the size of A ∪ B? If we know that A and B have no elements in common, then the size A ∪ B is m + n; if they do have elements in common, we need more information. A simple but typical problem of this type: if we roll two dice, how many ways are there to get either 7 or 11? Since there are 6 ways to get 7 and two ways to get 11, the answer is 6 + 2 = 8. Though this principle is simple, it is easy to forget the requirement that the two sets be 12 Chapter 1 Fundamentals disjoint, and hence to use it when the circumstances are otherwise. This principle is often called the addition principle. This principle can be generalized: if sets A1 through An are pairwise disjoint and have sizes m1, . . . mn, then the size of A1 ∪ · · · ∪An = ∑n i=1 mi . This can be proved by a simple induction argument. Why do we know, without listing them all, that there are 36 outcomes when two dice are rolled? We can view the outcomes as two separate outcomes, that is, the outcome of rolling die number one and the outcome of rolling die number two. For each of 6 outcomes for the first die the second die may have any of 6 outcomes, so the total is 6 + 6 + 6 + 6 + 6 + 6 = 36, or more compactly, 6 · 6 = 36. Note that we are really using the addition principle here: set A1 is all pairs (1, x), set A2 is all pairs (2, x), and so on. This is somewhat more subtle than is first apparent. In this simple example, the outcomes of die number two have nothing to do with the outcomes of die number one. Here’s a slightly more complicated example: how many ways are there to roll two dice so that the two dice don’t match? That is, we rule out 1- 1, 2-2, and so on. Here for each possible value on die number one, there are five possible values for die number two, but they are a different five values for each value on die number one. Still, because all are the same, the result is 5 + 5 + 5 + 5 + 5 + 5 = 30, or 6 · 5 = 30. In general, then, if there are m possibilities for one event, and n for a second event, the number of possible outcomes for both events together is m · n. This is often called the multiplication principle. In general, if n events have mi possible outcomes, for i = 1, . . . , n, where each mi is unaffected by the outcomes of other events, then the number of possible outcomes overall is ∏n i=1 mi . This too can be proved by induction. 203 CU IDOL SELF LEARNING MATERIAL (SLM)

12.2 COMBINATION Definitions: A combination of r objects chosen from among n different objects is a choice of the r objects without regard to order. The number of combinations of r objects chosen from among n different objects is nCr=n!/(n−r)!r! Other notations for nCr are C(n,r) and (rn). You need to know all these notations. Example 1: The order in which the balls ended up important in our previous cases. Order, on the other hand, isn't always important. Consider the following scenario: we have five pool balls and wish to chose four to toss in a bag. How many different ways could the four balls be chosen? Solution: Clearly, the only thing that matters is which balls are chosen, not which sequence they are chosen in. For example, if we choose Ball 2, Ball 3, Ball 1, and then Ball 4, we receive the same outcome as if we choose Ball 1, Ball 2, Ball 3, and then Ball 4. A combination is a choice like this where the order doesn't matter. Example 2: Jerrold possesses a total of five pool balls. How many different ways can he select four balls for a bag? Solution: 5C4=5!4!(5−4)!=5, so there are five ways in which he can choose. Example 3: When a customer orders an entrée, he has the option of selecting three different side dishes. How many different side dish combinations can a consumer make if there are twelve to pick from? Solution: Because the order in which side dishes are ordered does not matter, this is a combinations problem. So there are 12C3=12!/3!(12−3)! =12⋅11⋅10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1/(3⋅2⋅1)(9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1) =12⋅11⋅10/3⋅2⋅1=660 different choices. Example 4: You are deciding which awards you are going to display in your room. You have 8 awards, but you only have room to display 4 awards. Right now you are not worrying about how to 204 CU IDOL SELF LEARNING MATERIAL (SLM)

arrange the awards, so the order does not matter. How many ways could you choose the 4 awards to display? Solution: Since order does not matter, this is a combination problem. You start with 8 awards and then choose 4. 8C4=(8, 4)=8!/4!(8−4)! =8⋅7⋅6⋅54⋅3⋅2⋅1=7⋅2⋅5=70 Note that if you try to use the Fundamental Counting Principle with this question, you will need to do an extra step of reasoning. There are 8 options you could choose 1st, then 7 left, then 6, and lastly 5. 8⋅7⋅6⋅5=1,680 Example 5: With three letters and four numerals, how many Oregon licence plates could be made? Solution: The Fundamental Counting Principle with 7 spaces can represent a licence plate with 3 letters and 4 numerals. Because order matters with licence plates, you can employ the Fundamental Counting Principle. The first position is a number, the following three are letters, and the next three are numbers. Repetition is permitted while selecting a licence plate. 10⋅26⋅26⋅26⋅10⋅10⋅10=263⋅104=175,760,000 This number is only approximate because, in reality, certain letter and number combinations are not allowed, some license plates have extra symbols, and some commercial and government license plates have more numbers, fewer letters, or blank spaces. Example 6: A professional NHL team has 20 players, two of whom are goaltenders. What is the maximum number of sets of five skaters and one goalkeeper that can be on the ice at the same time? Solution: 205 CU IDOL SELF LEARNING MATERIAL (SLM)

The question asks for how many on the ice, implying that order does not matter. This is combination problem with 2 combinations. You need to choose 1 goalie out of a possible of 2, and choose 5 skaters out of a possible 18. (21)(185)=2⋅18!/5!⋅13!=17,136 Example 7: How many different ways could you score a 70% on a 10-question test, where each question is weighted equally and is either right or wrong? Solution: The order of the questions you got right does not matter, so this is a combination problem. (107)=10!/7!3!=120 Difference between Permutations and Combinations Both problems involved arrangements of the same set {p, e, n}, taken 2 elements at a time, without allowing repetition. However, in the first problem, the order of the arrangements mattered since pe and ep are two different “words”. In the second problem, the order did not matter since pe and ep represented the same two-man crew. We counted this only once.The first problem was concerned with counting the number of permutations of 3 objects taken 2 at a time. The second problem was concerned with the number of combinations of 3 objects taken 2 at a time. 12.3 THE PIGEONHOLE PRNCIPLE Pigeonhole Principle: Suppose that n+1n+1 (or more) objects are put into nn boxes. Then some box contains at least two objects. Proof: Suppose each box contains at most one object. Then the total number of objects is at most 1+1+⋯+1=n1+1+⋯+1=n, a contradiction. This seemingly simple fact can be used in surprising ways. The key typically is to put objects into boxes according to some rule, so that when two objects end up in the same box it is because they have some desired relationship. For example: Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it, at most 19 pigeons, one per hole, could be accommodated. This illustrates a general 206 CU IDOL SELF LEARNING MATERIAL (SLM)

principle called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it. Example 1: Among any 13 people, at least two share a birth month. Solution: Label 12 boxes with the names of the months. Put each person in the box labeled with his or her birth month. Some box will contain at least two people, who share a birth month. Example 2: Suppose 5 pairs of socks are in a drawer. Picking 6 socks guarantees that at least one pair is chosen. Solution: Label the boxes by \"the pairs'' (e.g., the red pair, the blue pair, the argyle pair, Put the 6 socks into the boxes according to description. Example 3: If (Kn+1) pigeons are kept in n pigeon holes where K is a positive integer, what is the average no. of pigeons per pigeon hole? Solution: Average number of pigeons per hole = (Kn+1)/n = K + 1/n Therefore there will be at least one pigeonhole which will contain at least (K+1) pigeons i.e., [K +1/n] and remaining will contain at most K 207 CU IDOL SELF LEARNING MATERIAL (SLM)

i.e., floor[k+1/n] pigeons. i.e., the minimum number of pigeons required to ensure that at least one pigeon hole contains (K+1) pigeons is (Kn+1) Example 4: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color? Solution: Apply pigeonhole principle. No. of colors (pigeonholes) n = 3 No. of marbles (pigeons) K+1 = 4 Therefore the minimum no. of marbles required = Kn+1 By simplifying we get Kn+1 = 10. Verification: ceil[Average] is [Kn+1/n] = 4 [Kn+1/3] = 4 Kn+1 = 10 i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10 Example 5: In a computer science department, a student club can be formed with either 10 members from first year or 8 members from second year or 6 from third year or 4 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed? Solution: Example 6: Solution: Here in this we cannot blindly apply pigeon principle. 208 CU IDOL SELF LEARNING MATERIAL (SLM)

First, we will see what happens if we apply above formula directly. From the above formula we have get answer 47 because 6 + 8 + 10 + 12 + 15- 5 + 1 = 47 But it is not correct. In order to get the correct answer, we need to include only blue, yellow and white balls because red and green balls are less than 9. But we are picking randomly so we include after we apply pigeon principle. i.e., 9 blue + 9 yellow + 9 white – 3 + 1 = 25 Given we are picking randomly, now we can get all the red and green balls before the above 25 balls. Therefore, we add 6 red + 8 green + 25 = 39 We can conclude that in order to pick 9 balls of same color randomly, one has to pick 39 balls from a box. 12.4 SUMMARY ● The number of possibilities to choose k objects from a total of n objects is called a combination. nCk=(nk)=n!/k!(n−k)! ● If the average number of pigeons per hole is “A,” and A is not an integer, then There are ceil[A] (smallest integer greater than or equal to A) birds in at least one pigeon hole. There are at most floor[A] (biggest integer less than or equal to A) pigeons in the remaining pigeon holes. • Put n items into k boxes. Then There is a box with at least n/k items. There is a box with at most n/k items • The Pigeonhole Principle doesn’t say which pigeons will be in the same hole 12.5 KEYWORD ● Pigeonhole principle: If n+1 or more pigeons occupy n pigeonholes, then at least one pigeonhole is occupied by more than one pigeon. ● Combinations: is a mathematical approach for calculating the number of potential configurations in a group of objects. 12.6 LEARNING ACTIVITY 1. How many four-digit numbers can be formed from the digits 1, 2, 3, 4, 5, 6 (Repetition of digits not allowed)? 209 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ _____________________________________________________________________ 2. A person has 6 friends to be invited for dinner through invitation cards, and he has 3 servants. In how many ways can he extend the invitation card? ___________________________________________________________________________ ____________________________________________________________________ 12.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. A restaurant's special allows you to select three dishes from a 10-item menu. How many different food combos could you come up with? 2. You go to 12 colleges and decide to apply to only four of them. How many different ways might you pick the four to apply to? 3. For the 12 colleges you visited, you want to select your top 5. How many different ways could you rank your top five? 4. How many different words can be formed with the letters of the word MISSISSIPPI? 5. What is pigeonhole principle? Long Questions 1. Explain why the following problem is not strictly a permutation or combination problem: The local ice cream shop has 12 flavours. You decide to buy 2 scoops in a dish. In how many ways could you do this if you are allowed to get 2 of the same scoop? 2. How many 3 digit numbers between 400 and 1000 can be formed with the digits 0, 2, 3, 4, 5, 6 if no digit is repeated? 3. A team of 3 members need to be formed out of 5 men and 2 women. In how many ways team can be formed so as to include at least 1 woman? 4. In how many ways a committee of 5 members can be selected from 6 men and 5 women, consisting of 3 men and 2 women? 5. In a computer science department, a student club can be formed with either 15 members from first year or 9 members from second year or 5 from third year or 4 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed? 210 CU IDOL SELF LEARNING MATERIAL (SLM)

B. Multiple Choice Questions 1. If nPr = 3024 and nCr = 126 then find n and r. a.9, 4 b.10, 3 c. 12, 4 d.11, 4 2. Find the number of rectangles and squares in an 8 by 8 chess board respectively. a.296, 204 b.1092, 204 c.204, 1092 d.204, 1296 3. There are 20 points in a plane, how many triangles can be formed by these points if 5 are colinear? a.1130 b.550 c.1129 d.1140 4. In how many ways can we select 6 people out of 10, of which a particular person is not included? a. 10C3 b. 9C5 c. 9C6 d. 9C4 5. In a colony, there are 55 members. Every member posts a greeting card to all the members. How many greeting cards were posted by them? a. 990 b. 890 c. 2970 d.1980 211 CU IDOL SELF LEARNING MATERIAL (SLM)

6. Find the number of ways of arranging the letters of the words DANGER, so that no vowel occupies odd place. a.36 b.48 c.144 d.96 7. Find the sum of all four-digit numbers that can be formed by the digits 1, 3, 5, 7, 9 without repetition. a.666700 b. 666600 c. 678860 d. 665500 Answers 1-a, 2-b, 3-a. 4-c, 5-c, 6-c, 7- b. 12.8 REFERENCES References book ● Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw – Hill Pub. Co. Ltd, New Delhi, 2011. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Thomas Koshy, “Elementary Number Theory with Applications”, Elsevier Publications, New Delhi, 2002. ● Tremblay J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011. ● San Ling and Chaoping Xing, “Coding Theory – A first Course”, Cambridge Publications, Cambridge, 2004. 212 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 13: PROPOSITIONAL LOGIC 1 STRUCTURE 13.0 Learning Objectives 13.1 Introduction 13.2 Proposition logic 13.3 Basic logic 13.4 Summary 13.5 Keywords 13.6 Learning Activity 13.7 Unit End Questions 13.8 References 13.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Explain how to solve problems using truth tables and logical operators. ● Translate between narrative and propositional logic arguments. ● Demonstrate logical equivalency, contingency, tautology, and inconsistencies. 13.1 INTRODUCTION Propositional logic, also known as sentential logic and statement logic, is the branch of logic that studies ways of joining and/or modifying entire propositions, statements or sentences to form more complicated propositions, statements or sentences, as well as the logical relationships and properties that are derived It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions. Importance of Mathematical Logic: The rules of logic give precise meaning to mathematical statements. These rules are used to distinguish between valid and invalid mathematical arguments. Apart from its importance in understanding mathematical reasoning, logic has numerous 213 CU IDOL SELF LEARNING MATERIAL (SLM)

applications in Computer Science, varying from design of digital circuits, to the construction of computer programs and verification of correctness of programs. 13.2 PROPOSITION LOGIC The simplest and most abstract logic we can study is called propositional logic. Definition: A proposition is a statement that can be either true or false; it must be one or the other, and it cannot be both. For example, The following are propositions: a. the reactor is on b. the wing-flaps are up c. John Major is prime minister. d. Whereas the following are not e. are you going out somewhere? f. 2+3 It is possible to determine whether any given statement is a proposition by prefixing it with: It is true that and seeing whether the result makes grammatical sense. We now define atomic propositions. Intuitively, these are the set of smallest propositions. Definition: An atomic proposition is one whose truth or falsity does not depend on the truth or falsity of any other proposition. So all the above propositions are atomic. Now, rather than write out propositions in full, we will abbreviate them by using propositional variables. • It is standard practice to use the lower-case roman letters p, q,r, . . . to stand for propositions. • If we do this, we must define what we mean by writing something like: Let p be John Major is prime Minister. • Another alternative is to write something like reactor is on, so that the interpretation of the propositional variable becomes obvious. Now, the study of atomic propositions is pretty boring. We therefore now introduce a number of connectives which will allow us to build up complex propositions. The connectives we introduce are: • ∧ and (& or .) 214 CU IDOL SELF LEARNING MATERIAL (SLM)

• ∨ or (| or +) • ¬ not • (∼) ⇒ implies • (⊃ or →) ⇔ iff 13.3 BASIC LOGIC Any two propositions can be combined to form a third proposition called the conjunction of the original propositions. Definition: If p and q are arbitrary propositions, then the conjunction of p and q is written p ∧ q and will be true iff both p and q are true. We can summaries the operation of ∧ in a truth table. The idea of a truth table for some formula is that it describes the behavior of a formula under all possible interpretations of the primitive propositions they are included in the formula. If there are n different atomic propositions in some formula, then there are 2 n different lines in the truth table for that formula. This is because each proposition can take one 1 of 2 values true or false. • Let us write T for truth and F for falsity. Then the truth table for p ∧ q is: Any two propositions can be combined by the word ‘or’ to form a third proposition called the disjunction of the originals. Definition: If p and q are arbitrary propositions, then the disjunction of p and q is written p ∨ q and will be true iff either p is true, or q is true, or both p and q are true Many statements, particularly in mathematics, are of the form: if p is true then q is true. Another way of saying the same thing is to write: p implies q. • 215 CU IDOL SELF LEARNING MATERIAL (SLM)

In propositional logic, we have a connective that combines two propositions into a new proposition called the conditional, or implication of the originals, that attempts to capture the sense of such a statement. Definition: If p and q are arbitrary propositions, then the conditional of p and q is written p ⇒ q and will be true iff either p is false or q is true. The ⇒ operator is the hardest to understand of the operators we have considered so far, and yet it is extremely important. If you find it difficult to understand, just remember that the p ⇒ q means ‘if p is true, then q is true’. If p is false, then we don’t care about q, and by default, make p ⇒ q evaluate to T in this case. Terminology: If φ is the formula p ⇒ q, then p is the antecedent of φ and q is the consequent. Another common form of statement in maths is: p is true if, and only if, q is true. • The sense of such statements is captured using the biconditional operator. Definition: If p and q are arbitrary propositions, then the biconditional of p and q is written: p ⇔ q and will be true iff either: 1. p and q are either true; or 2. p and q are both false. If p ⇔ q is true, then p and q are said to be logically equivalent. They will be true under exactly the same circumstances. All of the connectives we have considered so far have been binary: they have taken two arguments. • The final connective we consider here is unary. It only takes one argument. • Any proposition can be prefixed by the word ‘not’ to form a second proposition called the negation of the original. Definition: If p is an arbitrary proposition then the negation of p is written ¬p and will be true iff p is false. Tautologies & Consistency Definition: • A formula is a tautology iff it is true under every valuation. • A formula is consistent iff it is true under at least one valuation; • A formula is inconsistent iff it is not made true under any valuation. 216 CU IDOL SELF LEARNING MATERIAL (SLM)

13.4 SUMMARY • Propositional logic, also known as sentential logic, is a type of logic that is used to make statements. • Statement logic is a branch of logic that investigates how to join and/or change whole propositions. • Assertions or sentences, as well as logical links, to build more intricate propositions, statements or sentences • Any two propositions can be combined to form a third proposition called the conjunction of the original propositions. 13.5 KEYWORD • Propositional logic : A proposition is a statement that can be either true or false; it must be one or the other, and it cannot be both • Logical connectives: In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant used to connect two or more formulas. • Negation: the contradiction or denial of something. • Conjunction Logical conjunction is an operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both of its operands are true. • disjunction Disjunction, in logic, relation or connection of terms in a proposition to express the concept “or”; it is a statement of alternatives (sometimes called “alternation”). 13.6 LEARNING ACTIVITY 1. If the statement q ∧ r is true, determine all combinations of truth values for p and s such that the statement (q → [¬p ∨ s]) ∧ [¬s → r] is true. ___________________________________________________________________________ _______________________________________________________________ 2. Find all combinations of truth values for p, q and r for which the statement ¬p ↔ (q ∧ ¬(p → r)) is true. 217 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ _______________________________________________________________ 3. Show that [(p ∨ q) ∧ (r ∨ ¬q)] → (p ∨ r)] is a tautology by making a truth table, and then again by using an argument that considers the two cases “q is true” and “q is false”. ___________________________________________________________________________ _______________________________________________________________ 4. Show that (p → q) ↔ (q → p) is neither a tautology nor a contradiction. What does that tell you about possible relationships between the truth values of a statement and its converse? ___________________________________________________________________________ _______________________________________________________________ 5. Tommy Flanagan was telling you what he ate yesterday afternoon. He tells you, “I had either popcorn or raisins. Also, if I had cucumber sandwiches, then I had soda. But I didn't drink soda or tea.” Of course you know that Tommy is the world’s worst liar, and everything he says is false. What did Tommy eat? Justify your answer by writing all of Tommy's statements using sentence variables (P,Q,R,S,TP,Q,R,S,T), taking their negations, and using these to deduce what Tommy actually ate. ___________________________________________________________________________ _________________________________________________________________ 13.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is proportion with example? 2. What are the 3 types of proportion? 3. What are the applications of propositional logic? 4. What are the four logical connectives? 5. What is propositional logic in math? Long Questions 218 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Suppose that the statement p → ¬q is false. Find all combinations of truth values of r and s for which (¬q → r) ∧ (¬p ∨ s) is true. 2. Is (p → q) → [(p → q) → q] a tautology? Why or why not? 3. Suppose ¬[(p → q) ↔ (q → p)] is false. Can p ↔ q have both possible truth values? Explain. 4. Consider the following popular puzzle. When asked for the ages of her three children, Mrs. Baker says that Alice is her youngest child if Bill is not her youngest child, and that Alice is not her youngest child if Carl is not her youngest child. Write down a knowledge base that describes this riddle and the necessary background knowledge that only one of the three children can be her youngest child. Show with resolution that Bill is her youngest child. 5. Consider two propositions generated by p and :q: ¬(p∧q) and .¬p∨¬q. At first glance, they are different propositions. In form, they are different, but they have the same meaning. One way to see this is to substitute actual propositions for p andq; such as :p: I've been to Toronto; and :q: I've been to Chicago. B. Multiple Choice Questions 1. Which of the following statement is a proposition? a. Get me a glass of milkshake b. God bless you! c. What is the time now? d. The only odd prime number is 2 2. Which of the following option is true? a. If the Sun is a planet, elephants will fly b. 3 +2 = 8 if 5-2 = 7 c. 1 > 3 and 3 is a positive integer d. -2 > 3 or 3 is a negative integer 3. What is the value of x after this statement, assuming the initial value of x is 5? ‘If x equals to one then x=x+2 else x=0’. a. 1 b. 3 219 CU IDOL SELF LEARNING MATERIAL (SLM)

c. 0 d. 2 4. Let P: I am in Bangalore.; Q: I love cricket.; then q -> p(q implies p) is? a. If I love cricket, then I am in Bangalore b. If I am in Bangalore, then I love cricket c. I am not in Bangalore d. I love cricket 5. Let P: If Sahil bowls, Saurabh hits a century.; Q: If Raju bowls, Sahil gets out on first ball. Now if P is true and Q is false then which of the following can be true? a. Raju bowled and Sahil got out on first ball b. Raju did not bowl c. Sahil bowled, and Saurabh hits a century d. Sahil bowled, and Saurabh got out Answers 1-d, 2-a, 3-c. 4-a, 5-c 13.8 REFERENCES References book ● Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw – Hill Pub. Co. Ltd, New Delhi, 2011. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Thomas Koshy, “Elementary Number Theory with Applications”, Elsevier Publications, New Delhi, 2002. ● Tremblay J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011. ● San Ling and Chaoping Xing, “Coding Theory – A first Course”, Cambridge Publications, Cambridge, 2004. 220 CU IDOL SELF LEARNING MATERIAL (SLM)

221 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 14: PROPOSITIONAL LOGIC 2 STRUCTURE 14.0 Learning Objectives 14.1 Introduction 14.2 Logical connectives 14.3 Truth tables 14.4 Summary 14.5 Keywords 14.6 Learning Activity 14.7 Unit End Questions 14.8 References 14.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Explain the concepts relating to Logical connectives ● Describe the concepts relating to truth tables. ● Construct the common logical connectives or operators. They are considered common logical connectives because they are very popular, useful and always taught together. 14.1 INTRODUCTION In logic, a logical connective is a logical constant used to connect two or more formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and rendering the complex formula . Common connectives include negation, disjunction, conjunction, and implication. In standard systems of classical logic, these connectives are interpreted as truth functions, though they receive a variety of alternative interpretations in nonclassical logics. Their classical interpretations are similar to the meanings of natural language expressions such as English \"not\", \"or\", \"and\", and \"if\", but not identical. In math logic, a truth table is a chart of rows and columns showing the truth value (either “T” for True or “F” for False) of every possible combination of the given statements (usually represented by uppercase letters P, Q, and R) as operated by logical connectives. 222 CU IDOL SELF LEARNING MATERIAL (SLM)

14.2 LOGICAL CONNECTIVES Definition: A logical connective is a word usually written as a symbol that carries a particular instruction of logic on how to operate a statement or compound statement. Logical connectives can also be used to join or combine two or more statements to form a new statement. Laws Of Logic: S.No Name of the law Primal form Dual form 1 PPP 2 Idempotent law PPP PT  P 3 PF  F 4 Identity law PF  P PP F 5 PQ  QP 6 Dominant law PT  T (PQ) R  (PQ)R (PQ) R  7 Compliment law PP T (PQ) (PR) P(PQ)  P 8 Commutative law PQ  QP (PQ) PQ Assosciative law (PQ) R  P(QR) Distributive law (PQ) R  (PQ)(PR) Absorption law P(PQ)  P 9 De morgan’s law  (PQ) PQ Double nagation 10 (P)  P law 223 CU IDOL SELF LEARNING MATERIAL (SLM)

14.3 TRUTH TABLES Definition: A statement is a sentence or mathematical expression that is either definitely true or definitely false but not both. It is usually denoted by an uppercase letter or variable. The common ones are P, Q, R and S. A proposition is the basic building block of logic. It is defined as a declarative sentence that is either true or false, but not both. The Truth Value of a proposition is True(denoted as T) if it is a true statement, and False(denoted as F) if it is a false statement. For Example, a. The sun rises in the East and sets in the West. b. 1 + 1 = 2 c. 'b' is a vowel. All of the above sentences are propositions, where the first two are Valid(True) and the third one is Invalid (False). Some sentences that do not have a truth value or may have more than one truth value are not propositions. For Example, a. What time is it? b. Go out and play. c. x + 1 = 2. The above sentences are not propositions as the first two do not have a truth value, and the third one may be true or false. To represent propositions, propositional variables are used. By Convention, these variables are represented by small alphabets such as p, q, r, s. The area of logic which deals with propositions is called propositional calculus or propositional logic. It also includes producing new propositions using existing ones. Propositions constructed using one or more propositions are called compound propositions. The propositions are combined together using Logical Connectives or Logical Operators. Truth Table Since we need to know the truth value of a proposition in all possible scenarios, we consider all the possible combinations of the propositions which are joined together by Logical 224 CU IDOL SELF LEARNING MATERIAL (SLM)

Connectives to form the given compound proposition. This compilation of all possible scenarios in a tabular format is called a truth table. Most Common Logical Connectives: 1. Negation: If p is a proposition, then the negation of p is denoted by , which when translated to simple English means “It is not the case that “p” or simply “not p”. The truth value of is the opposite of the truth value of p. The truth table of is- Example, The negation of “It is raining today”, is “It is not the case that is raining today” or simply “It is not raining today”. 2. Conjunction: For any two propositions p and q, their conjunction is denoted by , which means “p and q”. The conjuction is True when both p and q are True, otherwise False. The truth table of is Example, The conjunction of the propositions p – “Today is Friday” and q – “It is raining today”, 225 CU IDOL SELF LEARNING MATERIAL (SLM)

is “Today is Friday and it is raining today”. This proposition is true only on rainy Fridays and is false on any other rainy day or on Fridays when it does not rain. 3. Disjunction: For any two propositions p and q, their disjunction is denoted by , which means “p or q”. The disjunction is True when either p or q is True, otherwise False. The truth table of is- Example, The disjunction of the propositions p – “Today is Friday” and q – “It is raining today”, is “Today is Friday or it is raining today”. This proposition is true on any day that is a Friday or a rainy day(including rainy Fridays) and is false on any day other than Friday when it also does not rain. 4. Exclusive Or: For any two propositions p and q, their exclusive or is denoted by , which means “either p or q but not both”. The exclusive or is True when either p or q is True, and False when both are true or both are false. The truth table of is 226 CU IDOL SELF LEARNING MATERIAL (SLM)

Example, The exclusive or of the propositions p – “Today is Friday” and q – “It is raining today”, is “Either today is Friday or it is raining today, but not both”. This proposition is true on any day that is a Friday or a rainy day(not including rainy Fridays) and is false on any day other than Friday when it does not rain or rainy Fridays. 5. Implication: For any two propositions p and q, the statement “if p then q” is called an implication and it is denoted by . In the implication , is called the hypothesis or antecedent or premise and q is called the conclusion or consequence. The implication is is also called a conditional statement. The implication is false when p is true and q is false otherwise it is true. The truth table of is- You might wonder that why is true when p is false. This is because the implication guarantees that when p and q are true then the implication is true. But the implication does not guarantee anything when the premise p is false. There is no way of knowing whether or not the implication is false since p did not happen. Conditional statements play a very important role in mathematical reasoning, thus a variety of terminology is used to express , some of which are listed below. 227 CU IDOL SELF LEARNING MATERIAL (SLM)

Example, “If it is Friday then it is raining today” is a proposition which is of the form . The above proposition is true if it is not Friday(premise is false) or if it is Friday and it is raining, and it is false when it is Friday, but it is not raining. 6. Biconditional or Double Implication: For any two propositions p and q, the statement “p if and only if(iff) q” is called a biconditional and it is denoted by . The statement is also called a biimplication. has the same truth value as . The implication is true when p and q have same truth values, and is false otherwise. The truth table of is- Some other common ways of expressing are- Example, “It is raining today if and only if it is Friday today.” is a proposition which is of the 228 CU IDOL SELF LEARNING MATERIAL (SLM)

form . The above proposition is true if it is not Friday and it is not raining or if it is Friday and it is raining, and it is false when it is not Friday or it is not raining. Example 1: Construct a truth table for the compound proposition (pq) (qp). Solution: pq p→q q→p (pq)(qp) TT T TT TF F TT FT T FF FF T TT Definition: Tautology: A statement formula which is true always for the truth values of the components is called tautology. Therefore, the last column of the truth table of the given formula has truth value ‘T’ only. Example: PP is a tautology Example 2: Prove that P (P  Q) is a tautology Solution: PQ P∨ Q P →(P ∨ Q) TT T T TF T T FT T T FF F T 229 CU IDOL SELF LEARNING MATERIAL (SLM)

Hence P (P  Q) is a tautology Example 3: Show that (,) is not functionally complete Solution: Consider the statement P. P Cannot be expressed using the connections (,). Therefore (,) is not functionally complete. Example 4: Show that the conclusion C:P follows from the premises H1:P  Q and H2:Q Solution: To prove (P  Q)QP H1 H2 C P P Q P→Q ¬Q F F TT T F T T TF F T FT T F FF T T 230 CU IDOL SELF LEARNING MATERIAL (SLM)

From the fourth row, if the hypothesis is true, then the conclusion is true. Therefore, follows from the premises H1 and H2. Example 5: Construct the truth table for the formula  (P(QR))  ((PQ)(PR)) Solution: P QR QR P(QR) PQ A= B= PR  AB (PQ)(PR) (P(QR)) TTT T T T TT FF TTF F T T TT FF TFT F T T TT FF TFF F T T TT FF F TT T T T TT FF F TF F F T FF TF FFT F F F TF TF FFF F F F FF TF Example 6: Make a truth table for the statement (P∨Q)→(P∧Q). Solution: 231 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 7: Make a truth table for the statement ¬P∧(Q→P).¬P∧(Q→P). What can you conclude about PP and QQ if you know the statement is true? Solution: 14.4 SUMMARY ● A logical connective is a symbol that is used to connect two or more propositional or predicate logics in such a way that the resultant logic is only dependent on the input logics and the connective's meaning. ● A truth table is a table with statements in the columns and probable scenarios in the rows, and it contains every possible scenario as well as the truth values that might occur. ● One of the most basic truth tables is one that keeps track of the truth values for a statement and its negation. 14.5 KEYWORD ● Truth table: A table showing the relationship between truth values of simple statements and the truth values of compound statements formed by using these simple statements is called truth table ● Hypothesis : to denote the antecedent of a proposition ● Implication, in logic, a relationship between two propositions in which the second is a logical consequence of the first 232 CU IDOL SELF LEARNING MATERIAL (SLM)

● Conditional statement: Conditional statements are those statements where a hypothesis is followed by a conclusion. ● Biconditional statement Conditional statements are those statements where a hypothesis is followed by a conclusion. 14.6 LEARNING ACTIVITY 1. Consider the following statements: P: Good mobile phones are not cheap. Q: Cheap mobile phones are not good. L: P implies Q M: Q implies P N: P is equivalent to Q Which one of the following about L, M, and N is CORRECT Only L is TRUE. Only M is TRUE. Only N is TRUE. L, M and N are TRUE. ___________________________________________________________________________ __________________________________________________________________________ 2. Which of the following is the contrapositive of ‘if two triangles are identical, then these are similar’? If two triangles are not similar, then they are not identical. If two triangles are not identical, then these are not similar. If two triangles are not identical, then these are similar. If two triangles are not similar, then these are identical. ___________________________________________________________________________ ___________________________________________________________________________ 14.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Make a truth table for the statement ¬P→(Q∧R). 233 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Determine whether the following two statements are logically equivalent: ¬(P→Q)¬(P→Q) and P∧¬Q.P∧¬Q. Explain how you know you are correct. 3. Are the statements P→(Q∨R)P→(Q∨R) and (P→Q)∨(P→R)(P→Q)∨(P→R) logically equivalent? 4. Write the truth table of (¬P∨¬Q)→¬(¬Q∧R).(¬P∨¬Q)→¬(¬Q∧R). 5. Write the truth table of ¬((P→¬Q)∨¬(R∧¬R)). Long Questions 1. Simplify the statements (so that negation only appears right before variables). ¬(P→¬Q).¬(P→¬Q). 2. Prove that (¬p ∨ q) ∧ ¬(¬p ∨ q) is a contradiction. 3. Show that the two statements (p ∧ q) → r and (p → r) ∧ (q → r) are not logically equivalent. 4. Use any method to show that ¬(p → q) ↔ (p ∧ ¬q) is a tautology. 5. Use known logical equivalences to show that ¬(p ↔ q) ⇔ (p ∨ q) ∧ (¬p ∨ ¬q). B. Multiple Choice Questions 1. Let P: I am in Delhi; Q: Delhi is clean; then q ^ p(q and p) is? a. Delhi is clean, and I am in Delhi b. Delhi is not clean, or I am in Delhi c. I am in Delhi and Delhi is not clean d. Delhi is clean, but I am in Mumbai 2. Let P: This is a great website, Q: You should not come back here. Then ‘This is a great website, and you should come back here.’ is best represented by? a. ~P V ~Q b. P ∧ ~Q c. P V Q d. P ∧ Q 3. Let P: We should be honest, Q: We should be dedicated, R: We should be overconfident. Then ‘We should be honest or dedicated but not overconfident.’ is best represented by? a. ~P V ~Q V R b. P ∧ ~Q ∧ R 234 CU IDOL SELF LEARNING MATERIAL (SLM)

c. P V Q ∧ R d. P V Q ∧ ~R 4. The compound propositions p and q are called logically equivalent if ________ is a tautology. a. p ↔ q b. p → q c. ¬ (p ∨ q) d. ¬p ∨ ¬q 5. p → q is logically equivalent to ________ a. ¬p ∨ ¬q b. p ∨ ¬q c. ¬p ∨ q d. ¬p ∧ q 6. (p → r) ∨ (q → r) is logically equivalent to ________ a. (p ∧ q) ∨ r b. (p ∨ q) → r c. (p ∧ q) → r d. (p → q) → r 7. ¬ (p ↔ q) is logically equivalent to ________ a. p ↔ ¬q b. ¬p ↔ q c. ¬p ↔ ¬q d. ¬q ↔ ¬p Answers 1-a, 2-b, 3-d. 4-a, 5-c, 6-c, 7-a 14.8 REFERENCES References book 235 CU IDOL SELF LEARNING MATERIAL (SLM)

● Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw – Hill Pub. Co. Ltd, New Delhi, 2011. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Thomas Koshy, “Elementary Number Theory with Applications”, Elsevier Publications, New Delhi, 2002. ● Tremblay J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011. ● San Ling and Chaoping Xing, “Coding Theory – A first Course”, Cambridge Publications, Cambridge, 2004. 236 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 15: PROPOSITIONAL LOGIC 3 STRUCTURE 15.0 Learning Objectives 15.1 Introduction 15.2 Equivalence Laws of logic 15.3 Implication laws of logic 15.4 Summary 15.5 Keywords 15.6 Learning Activity 15.7 Unit End Questions 15.8 References 15.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Determine whether two statements and their consequences are logically identical. ● Create a value table for compound propositions. ● Using truth values, describe the logical equivalence. ● Implicit statements and operations, as well as their inverses, inverses, and negations. ● Demonstrate logical statement equivalence using truth tables and derivations. ● Define tautologies, contradictions, and equivalences that are commonly encountered. 15.1 INTRODUCTION Two logical expressions are said to be equivalent if they have the same truth value in all cases. Sometimes this fact helps in proving a mathematical result by replacing one expression with another equivalent expression, without changing the truth value of the original compound proposition. Implication Introduction is a rule of inference that allows us to deduce an implication from a sub proof. If, by assuming φ, we can derive ψ, then we can derive (φ ⇒ ψ). 15.2 EQUIVALENCE LAWS OF LOGIC Logical Equivalence: 237 CU IDOL SELF LEARNING MATERIAL (SLM)

Two statements P and Q are logically equivalent provided P is true precisely when Q is true. That is, P and Q have the same truth value under any assignment of truth values to their atomic parts. To verify that two statements are logically equivalent, you can make a truth table for each and check whether the columns for the two statements are identical. For example, you might have noticed that the final column in the truth table from ¬P∨ Q¬P∨ Q is identical to the final column in the truth table for P→Q: His says that no matter what PP and QQ are, the statements ¬P∨ Q¬P∨ Q and P→QP→Q either both true or both false. We therefore say these statements are logically equivalent. Example: Let s be “The sun is shining” and t be “It is raining.” Join these into the compound statement: (¬s ∧ t) ∨ ¬t. EQUIVALENCES E1 : PQ PQ(CONDITIONAL AS DISJUNCTION) E2 : (PQ)  PQ E3 :PQ QP(CONTRAPOSITIVE LAW) E4 : P(QR)  (PQ)R E5 :  (PQ)  P (Q) E6 : PQ  (PQ)(QP) (BICONDITIONAL AS DISJUNCTION) E7 : PQ  (PQ)(PQ) E8 : (PQ)(RQ)  (PR)Q E9 : P(QR)(PQ)(PR) E10 : (PQ)(PR)  P(QR) E11 : PQ PQ E12 : PQ (PQ) 238 CU IDOL SELF LEARNING MATERIAL (SLM)

E13 : (PR)(QR)  (PQ)R E14 : (PQ) (PR)  P(QR) E15 : (PR)(QR)  (PQ)R E16 : PQ PQ 15.3 IMPLICATION LAWS OF LOGIC Logical implication is expressible using only two of the operators introduced in the last slide. Implication captures the notion of an action depending upon the success (or failure) of another action. Unlike primitive connectors, implication is directional! Example: If it rains, then Richard brings an umbrella. A well-known and often-used pair of laws based upon the distributive and the negation properties from your text: Definition: De Morgan’s Laws state that for any statements p and q: ¬(p ∨ q) ≡ ¬p ∧ ¬q and ¬(p ∧ q) ≡ ¬p ∨ ¬q. De Morgan’s laws simplify computer programs. De Morgan’s laws simplify circuit designs. IMPLICATIONS: I1 : PQ  P I2 : PQ  Q I3 : P PQ I4 : Q PQ I5 : P P Q I6 : Q P Q I7 : (P Q)P I8 :  (P Q)Q I9 : P,QPQ I10 : P, PQQ(DISJUNVTIVE SYLLOGISM) Q, PQ P I11 : P , P QQ(MODUS PONENS) I12 :Q, PQP(MODUS TOLLENS) 239 CU IDOL SELF LEARNING MATERIAL (SLM)

I13 :P Q , QR P R (HYPOTHETICAL SYLLOGISM) I14 : PR, PR, QR  R Example 1: Determine whether the following compound preposition is a tautology or not ((P∨ Q)∧ (P→R)∧ (Q→R))→R without using truth table. Solution: Consider (PR)(QR (PR)(QR) Reasons (PR)(QR) (PR)(QR) Conditional as disjunction Distributive law  (PQ) R Demorgan’s law  (PQ) R Conditional as disjunction  (PQ)R Now (PQ)(PR)(QR)(PQ)((PQ)R)) R (Absorption law) Thus ((PQ)(PR)(QR))R is tautology. [Since RRRR T] Example 2: Show that (P→Q)∧ (R→Q) and (P∨ R)→Q are equivalent formula Solution: To Prove : (PQ)  (RQ)  (PR) Q (PQ)  (RQ)  (PQ) (RQ) (Conditional as disjunction)  (PR)Q (Commutative law)  (PR)Q (Demorgan’s law)  (PR)Q (Conditional as disjunction) Example 3: Without using truth table prove the equivalence: P→ (Q∨ R)≡ (P→ Q)∧ (P→R) Solution: 240 CU IDOL SELF LEARNING MATERIAL (SLM)

P (QR)P (QR) (Conditional as disjunction)  (PP) (QR) (Idempotent law)  (PQ) (PR) (Commutative law)  (PQ) (PR) (Conditional as disjunction) 15.4 SUMMARY ● If two logical propositions always produce the same truth value, they are logically identical. As a result, saying p≡q is a tautology is equivalent to saying p⇔q is a tautology. ● EQUIVALENCES E1 : P→Q ≡¬P∨ Q(CONDITIONAL AS DISJUNCTION) E2 ¬(P→Q) ≡ P∨ ¬Q E3 :P→Q ≡¬Q→¬P(CONTRAPOSITIVE LAW) E4 : P→(Q→R) ≡ (P∧ Q)→R E5 : ¬ (P↔Q) ≡ P↔ (¬Q) E6 : P↔Q ≡ (P→Q)∧ (Q→P) (BICONDITIONAL AS DISJUNCTION) E7 : P↔Q ≡ (P∧ Q)∨ (¬P∧ ¬Q) E8 : (P→Q)∧ (R→Q) ≡ (P∨ R)→Q E9 : P→(Q∨ R)≡(P→Q)∨ (P→R) E10 : (P→Q)∧ (P→R) ≡ P→(Q∨ R) E11 : P∨ Q ≡¬P→Q E12 : P∧ Q ≡¬(P→¬Q) E13 : (P→R)∧ (Q→R) ≡ (P∨ Q)→R E14 : (P→Q)∨ (P→R) ≡ P→(Q∨ R) E15 : (P→R)∧ (Q→R) ≡ (P∧ Q)→R E16 : P↔Q ≡¬P↔¬Q • DeMorgan’s Laws implications I1 : PQ  P I2 : PQ  Q I3 : P PQ I4 : Q PQ 241 CU IDOL SELF LEARNING MATERIAL (SLM)

I5 : P P Q I6 : Q P Q I7 : (P Q)P I8 :  (P Q)Q I9 : P,QPQ I10 : P, PQQ(DISJUNVTIVE SYLLOGISM) Q, PQ P I11 : P , P QQ(MODUS PONENS) I12 :Q, PQP(MODUS TOLLENS) I13 :P Q , QR P R (HYPOTHETICAL SYLLOGISM) I14 : PR, PR, QR  R 15.5 KEYWORD • Tautology: A tautology is a compound statement which is true for every value of the individual statements. • Contradiction: A compound proposition that is always false is called a contradiction. • Contrapositive: a proposition or theorem formed by contradicting both the subject and predicate or both the hypothesis and conclusion of a given proposition • Contingency: A statement which is neither a tautology nor a contradiction is called contingency • Equivalence: Any two compound statements A and B are said to be logically equivalent or simply equivalent if the columns corresponding to A and B in the truth table have identical truth value 15.6 LEARNING ACTIVITY 1. Show p → (q ∨ r) ⇔ (p ∧ ¬q) → r. ___________________________________________________________________________ _____________________________________________________________________ 2. Show ¬(p ∨ q) ∨ (¬p ∧ q) ∨ ¬(¬p ∨ ¬q) ⇔ ¬(p ∧ ¬q). ___________________________________________________________________________ _____________________________________________________________________ 242 CU IDOL SELF LEARNING MATERIAL (SLM)

3. Use known logical equivalences to show that (¬a → b) ∧ (¬b ∨ (¬a ∨ ¬b)) is logically equivalent to ¬(a ↔ b). ___________________________________________________________________________ _____________________________________________________________________ 15.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Show that ∼ (p ∧ q) and ∼ p∧ ∼ q are not logically equivalent 2. Show that ∼ (p ∨ q) ≡∼ p∧ ∼ q. 3. Prove that ∼ (p ∧ q) and ∼ p∨ ∼ q are logically equivalent. 4. Show that p → (q → r) is logically equivalent to (p ∧ q) → r. 5. Define the logical connective “nand” (not and) by p ∧ q ⇔ ¬(p ∧ q). Long Questions 1. Show that (a ∨ b −→ c) =⇒ (a ∧ b −→ c) 2. Let p, q, r denote primitive statements. Use truth tables to prove the following logical equivalences. p → (q ∧ r) ⇐⇒ (p → q) ∧ (p → r) [(p ∨ q) → r] ⇐⇒ [(p → r) ∧ (q → r)] 3. Let p, q, r denote primitive statements. Use the laws of logic to show that [p −→ (q ∨ r)] ⇐⇒ [(p ∧ ¬q) −→ r]. 4. Show that ((a ∧ b) −→ c) ⇐⇒ ((a −→ c) ∨ (b −→ c)). 5. Simplify (p ∧ (¬r ∨ q ∨ ¬q)) ∨ ((r ∨ t ∨ ¬r) ∧ ¬q). B. Multiple Choice Questions 1. p ∨ q is logically equivalent to ________ a. ¬q → ¬p b. q → p c. ¬p → ¬q d. ¬p → q 2. ¬ (p ↔ q) is logically equivalent to ________ a. q↔p 243 CU IDOL SELF LEARNING MATERIAL (SLM)

b. p↔¬q c. ¬p↔¬q d. ¬q↔¬p 3. p ∧ q is logically equivalent to ________ a. ¬ (p → ¬q) b. (p → ¬q) c. (¬p → ¬q) d. (¬p → q) 4. Which of the following statement is correct? a. p ∨ q ≡ q ∨ p b. ¬(p ∧ q) ≡ ¬p ∨ ¬q c. (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) d. All of these 5. p ↔ q is logically equivalent to ________ a. (p → q) → (q → p) b (p → q) ∨ (q → p) c. (p → q) ∧ (q → p) d. (p ∧ q) → (q ∧ p) 6. (p → q) ∧ (p → r) is logically equivalent to ________ a. p → (q ∧ r) b. p → (q ∨ r) c. p ∧ (q ∨ r) d. p ∨ (q ∧ r) Answers 1-d, 2-b, 3-a. 4-d, 5-c, 6-a 15.8 REFERENCES References book 244 CU IDOL SELF LEARNING MATERIAL (SLM)

● Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw – Hill Pub. Co. Ltd, New Delhi, 2011. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Thomas Koshy, “Elementary Number Theory with Applications”, Elsevier ● Publications, New Delhi, 2002. ● Tremblay J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011. 245 CU IDOL SELF LEARNING MATERIAL (SLM)