CU-BCA-SEM-I-Mathematics

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. 351 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. 352 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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, 353 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 354 CU IDOL SELF LEARNING MATERIAL (SLM)

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 .) • ∨ 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. 355 CU IDOL SELF LEARNING MATERIAL (SLM)

• 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. • 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. 356 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 357 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 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 358 CU IDOL SELF LEARNING MATERIAL (SLM)

• 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. ___________________________________________________________________________ _______________________________________________________________ 359 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. ___________________________________________________________________________ _________________________________________________________________ 360 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 361 CU IDOL SELF LEARNING MATERIAL (SLM)

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’. 362 CU IDOL SELF LEARNING MATERIAL (SLM)

a. 1 b. 3 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 363 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 364 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. 365 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 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: 366 CU IDOL SELF LEARNING MATERIAL (SLM)

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 367 CU IDOL SELF LEARNING MATERIAL (SLM)

Double nagation 10 (P)  P law 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). 368 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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: 369 CU IDOL SELF LEARNING MATERIAL (SLM)

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 370 CU IDOL SELF LEARNING MATERIAL (SLM)

Example, The conjunction of the propositions p – “Today is Friday” and q – “It is raining today”, 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- 371 CU IDOL SELF LEARNING MATERIAL (SLM)

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 372 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- 373 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 374 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- 375 CU IDOL SELF LEARNING MATERIAL (SLM)

Example, “It is raining today if and only if it is Friday today.” is a proposition which is of the 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: 376 CU IDOL SELF LEARNING MATERIAL (SLM)

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 Hence P (P  Q) is a tautology Example 3: 377 CU IDOL SELF LEARNING MATERIAL (SLM)

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 TF F T T FT T F FF T T 378 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 379 CU IDOL SELF LEARNING MATERIAL (SLM)

T TF 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 F FT F F F TF TF F FF F F F FF TF Example 6: Make a truth table for the statement (P∨Q)→(P∧Q). Solution: 380 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. 381 CU IDOL SELF LEARNING MATERIAL (SLM)

● 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 ● 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. 382 CU IDOL SELF LEARNING MATERIAL (SLM)

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. ___________________________________________________________________________ ___________________________________________________________________________ 383 CU IDOL SELF LEARNING MATERIAL (SLM)

14.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Make a truth table for the statement ¬P→(Q∧R). 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. 384 CU IDOL SELF LEARNING MATERIAL (SLM)

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 385 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 386 CU IDOL SELF LEARNING MATERIAL (SLM)

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 ● 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 387 CU IDOL SELF LEARNING MATERIAL (SLM)

● 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. 388 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. 389 CU IDOL SELF LEARNING MATERIAL (SLM)

● 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: 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: 390 CU IDOL SELF LEARNING MATERIAL (SLM)

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) 391 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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: 392 CU IDOL SELF LEARNING MATERIAL (SLM)

¬(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) I13 :P Q , QR P R (HYPOTHETICAL SYLLOGISM) I14 : PR, PR, QR  R 393 CU IDOL SELF LEARNING MATERIAL (SLM)

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 394 CU IDOL SELF LEARNING MATERIAL (SLM)

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: 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 395 CU IDOL SELF LEARNING MATERIAL (SLM)

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 396 CU IDOL SELF LEARNING MATERIAL (SLM)

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) 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. 397 CU IDOL SELF LEARNING MATERIAL (SLM)

• 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). ___________________________________________________________________________ _____________________________________________________________________ 3. Use known logical equivalences to show that (¬a → b) ∧ (¬b ∨ (¬a ∨ ¬b)) is logically equivalent to ¬(a ↔ b). ___________________________________________________________________________ _____________________________________________________________________ 398 CU IDOL SELF LEARNING MATERIAL (SLM)

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 399 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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) 400 CU IDOL SELF LEARNING MATERIAL (SLM)