E-LESSON-4-5-6

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

B.C.A 2 All right are reserved with CU-IDOL Mathematics Course Code: BCA114 Semester: First SLM UNITS : 4, 5 & 6 e-Lesson No.: 3 www.cuidol.in Unit-4,5,6 (BCA114)

Modern Algebra 1-3 33 OBJECTIVES INTRODUCTION Student will be able to : In this unit we are going to learn about the Define Proposition and Algebra of logic. Proposition. Illustrate the Connectives with suitable example Under this unit you will also understand the and explain Tautology and Contradiction. connectives, Tautology and Contradiction. Describe the term Algebra of Propositions. This Unit will also make us to understand the Algebra of Propositions. www.cuidol.in Unit-4,5,6 (BCA1141)4) INSTITUTE OAFlDl IrSiTgAhNt CaEreArNeDseOrvNeLdINwEiLthEACRUN-INDGOL

TOPICS TO BE COVERED 4 •Propositions •Compound Proposition •Basic Logical Operators •Connectives •Tautologies •Contradiction •Algebra of Propositions •Law of Contrapositive •Laws www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Propositions 5 Definition •A proposition is a declarative statement which is either true or false but not both. Example: 1. 7 × 5 = 30 2. 100 – 25 = 50 3. 3 x 5 =15 The statements 1 and 2 have truth value 0 and 3 have truth value 1. Example: Observe statements “Study well” The Statement is not declarative, hence it is not proposition. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Compound Proposition 6 •Many propositions are composite, i.e, composed of subproposition and various connectives discussed subsequently. Such composite propositions are called compound proposition. •A proposition is said to be primitive if it cannot be broken into simple propositions, i.e, if it is not composite. Example: If it is sunny outside then I walk to work; otherwise I drive, and if it is raining then I carry my umbrella. p = “It is sunny outside” q = “I walk to work” r = “I drive” s = “It is raining” t = “I carry my umbrella” p implies q and ((not p) implies (r and (s implies t))). (p ⇒ q)  (~ p ⇒ (r  ( s ⇒ t))) www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Basic Logical Operators 7 Conjunction •When two or more statements are joined by connective, denoted by the symbol,  , the compound statement formed so is called as conjunction. Let p and q be two statements. •Then p  q forms a statement which is true if and only if both p and q are true and is false if p is false or q is false or both are false. The statement p  q is read as: p and q, and is called the conjunction of p and q. Disjunction •When two or more statements are joined by the connective or denoted by symbol,  , the compound statement formed so is called disjunction of two statements p and q, and is written as p or q or p  q. •It is false only when both the statements are false, otherwise, it is true for all cases. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Basic Logical Operators 8 Conditional Proposition •Given propositions p and q, then p  q represents the conditional proposition “If p, then q.” or “p implies q.” •The proposition p is called the antecedent and the proposition q is called the consequent. Bi-conditional Proposition •Definition: p if and only if q is a biconditional statement and is denoted by p  q and often written as p iff q. •A biconditional is true only when p and q have the same truth value. Negation •If p is statement, then negation (or not) of p, denoted by ~ p is defined to form a statement that is true when p is false and false when p is true. •The negation of statement p is read as ‘not p’. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Connectives 9 NAND •It is negation after ANDing of two statements. •For example, if p and q are two statements, then NANDing of p and q is denoted by p ↑ q is a false statement when both p and q are true, otherwise true for other cases. NOR or Joint Denial •It is the negation after ORing of two statements. For example, if p and q are two statements, then NORing of p and q, denoted by p ↓ q is a true statement when both p and q are false. XOR •If p and q are two statements, then XORing of p and q denoted by p  q is a true statement when either p or q is true but not both and vice versa. •The truth values of p  q are given in truth table. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Tautologies 10 • There are certain compound statements that always are true regardless of truth or falsity of compound statement. Compound statement which have this characteristic are called as tautology. •In other words, tautologies is a compound statement if it is true for all truth value assignments for its compound statements. Truth tables only contain T for tautology. •Example: Show that statement p  ~ p is tautology. Solution: p ~p p~p TF T FT T i.e., either p is true or p is false, there is no middle possibility. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Contradiction 11 • If a compound statement is false for all true values assignment for its component statement, then it is called contradiction. • A compound statement is said to be contradicting its truth value if it is false (F) for all its entries in the truth table. •Example 1: Show that statement p  ~ q is a tautology or contradiction. p ~p p~p T FF F TF All values are false, hence contradiction. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Algebra of Propositions 12 •The mathematical structure (statements,  ,  , ~) has many properties that are used for regulating manipulations on statements which are used in finding out new relations and equivalence among some of them. The propositions have the following properties: Idempotent Law •According to this law, the given statement does not change by conjunction with another statement such as: (a) p  p  p (b) p  p  p •For example, in ordinary algebra, a + b = a and b = 0, i.e., b is additional identity, similarly a.b = a, where b = 1 and is multiplicative identity. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Algebra of Propositions 13 Associate Law •According to this law, a compound statement consists of three statements remaining unchanged with the change in position of three statements with same connectives. (a) p  (q  r)  (p  q)  r (b) p  (q  r)  (p  q)  r Commutative Law •According to this law, order is irrelevant. (a) p  q  q  p (b) p  q  q  p www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Law of Contrapositive 14 •In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive and an associated proof method known as proof by contraposition. •The contrapositive of the statement has its antecedent and consequent inverted and flipped: the contrapositive of P  Q is thus ~Q  ~P. •For instance, the proposition “All cats are mammals” can be restated as the conditional “If something is a cat, then it is a mammal”. •The law of contraposition says that a statement is true if, and only if, its contrapositive (in this case “If something is not a mammal, then it is not a cat”) is true. •Inversion (the inverse), ~P  ~Q •“If something is not a cat, then it is not a mammal.” Unlike the contrapositive, the inverse's truth value is not at all dependent on whether or not the original proposition was true, as evidenced here. •The inverse here is clearly not true. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Law of Contrapositive 15 •Conversion (the converse), Q  P •“If something is a mammal, then it is a cat.” •The converse is actually the contrapositive of the inverse, and so always has the same truth value as the inverse (which as stated earlier does not always share the same truth value as that of the original proposition). •Negation, ~ (P  Q) •“It is not the case that if something is cat, then it is a mammal”, or equivalently, “There exists a cat that is not a mammal.” •If the negation is true, then the original proposition (and by extension the contrapositive) is false. In this example, the negation is false. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

Laws 16 •De Morgan’s Laws •According to this law, a statement remains unchanged if we change and () by or () and or () by and (), provided, universal of constituent statement exists. (a) ~ (p  q)  (~ p)  (~ q) (b) ~ (p  q)  (~ p)  (~ q) •Distributive Laws •According to this law, if connectives or distributes over and from the left, then this is left distributive. •Similarly, if connectives or distributes over and form the right, then this is left distributive. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 1) The proposition is p  (~ p  q) is ________. 17 (a) A tautology (b) A contradiction (c) (a) and (b) (d) None 2) Which of the following propositions is tautology? (a) (p  q) → p (b) p  (q → p) (c) p  (p → q) (d) None 3) Let p and q be propositions. Using only the truth table, decide whether p  q does not imply p → q is ________. (a) True (b) False (c) Otherwise (d) None 4) Is this statement p  ~ (p  q) is tautology? (a) True (b) False (c) (a) or (b) (d) None 5) Law of negation is ________. (a) ~ (~ p)  p (b) (p  q) (c) (p  q) (d) None Answers: 1) (c ) 2) ( c) 3) (b) 4) (a) 5)(a) www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

SUMMARY 18 Let us recapitulate the important concepts discussed in this session: •Logic has variety of applications in each course of day-to-day life and many other engineering applications like designing of electronic circuits, computer and other robotic programming, etc. •Many propositions are composite, i.e, composed of subproposition and various connectives discussed subsequently. Such composite propositions are called compound proposition. •A proposition is said to be primitive if it cannot be broken into simple propositions, i.e, if it is not composite. •We have come across tautologies and contradiction. The final column of truth table of given compound proposition contains both T and F. There are some compositions whose truth values are always T or F. •If a compound statement is false for all true values assignment for its component statement, then it is called contradiction. •A compound statement is said to be contradicting its truth value if it is false (F) for all its entries in the truth table. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 19 Q:1 Define Proposition. Explain the composition of proposition. Ans: A proposition is a declarative statement which is either true or false but not both. composed of subproposition and various connectives discussed subsequently. Such composite propositions are called compound proposition. A proposition is said to be primitive if it cannot be broken into simple propositions, i.e, if it is not composite. For more details refer subject SLM unit 4. Q2: Explain tautology and contradiction. Ans: A tautology is a formula which is \"always true“ that is, it is true for every assignment of truth values to its simple components. You can think of a tautology as a rule of logic. The opposite of a tautology is a contradiction, a formula which is \"always false\". In other words, a contradiction is false for every assignment of truth values to its simple components. For more details refer subject SLM unit 5. Q3. What do you mean by implication? Ans.Thus, the implication can't be false, so (since this is a two-valued logic) it must be true. This explains the last two lines of the table. means that P and Q are equivalent. So the double implication is true if P and Q are both true or if P and Q are both false; otherwise, the double implication is false. For more details refer subject SLM unit 6. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

REFRENCES 20 CU-IDOL’s “Mathematics” SLM. Seymour Lipschutz, Marc Lars Lipson, “Discrete Mathematics”, Publisher: McGraw Hill Education (India) Private Limited.  J.K. Sharma, “Discrete Mathematics”, Publisher: MacMillan India Limited. K. Chandrasekhara Rao, “Discrete Mathematics”, Publisher: Narosa Publishing House. Dr. Abhilasha S. Magar, “Applied Mathematics – I”, Publisher: Himalaya Publishing House. Dr. Abhilasha S. Magar, “Business Mathematics”, Publisher: Himalaya Publishing House. Dr. Abhilasha S. Magar, “Quantitative Methods – II”. Publisher: Himalaya Publishing House. www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL

21 THANK YOU For queries Email: [email protected] www.cuidol.in Unit-4,5,6 (BCA114) All right are reserved with CU-IDOL