Propositional Logic Syllabus Definition, Statements & Notatio, Tables, Well-formed Formulas, Implications, Examples ”, Truth Values, Tautologies, Eng Statement Formulas & Truth lence of Formulas, Duality Law, Tautological Contents 4.1 Logic 42. Statements (or Propositions) 43 Open Statement 44. Truth Value of a Statement 45 Truth Table 4.6 Logical Connectives 47 Tautology 48 Contradiction 4.9 Precedence Rule 4.10 Logical Equivalence 4.11 Normal Forms a9)Proposition) Discrete eee tee ma Logic (or oi is analysis of language, which consists of sig Lo axioms) which we can use to draw valid conclusions: my Statements (or Propositions) Statements are kinds of sentences which we have to use to convey our thoughts b others. A sentence is a statement or proposition if it is possible to say whether wha conveyed by the sentence is true or false. gic is a set of rules pon, A Sentence of which itis meaningful, to 58, whether it is, te or false batty) ‘oth is called a statement or proposition. We denote statements by letters p, q, 1) §- Examples 1. Pune is capital of India 2. Mars is a planet. 3.9 > 13. 4y+8=12 5. 6 € (1, 2, 3, 4} 6.xEA. 7. There are 12 months in a year. Examples (2' and (7) are true statements. Examples‘1', 3:, ©) are false statements. In example 4, if we write 4 in place of y, it becomes a true sentence and if y is not 4 then it is a false sentence. Similarly in \6) we cannot say whether this sentence is true or not unless we are told what are the elements of A. Thus only those sentences are statements about which we can say whether these ar true or false. Definition A statement is a declarative sentence with a definite truth value. Hence (1), (2 ®, @ are statements. > is not a statement since its truth value depends on the value of y- If y is 4 the sentence is true, if y # 4 then the sentence is false. ‘Also@) is not a statement since its truth value depends on set A, if A = fx ¥ #4 then © is true but if A = (1, 2, 3, 4} then ©6/'is false. TECHNICAL PUBLICATIONS” - An up thrust for knowledgeye Mathematics yu “ae = Propositional Logic Open Statement xample @ above if w mee Ine ee ug ae oun va nf = 4, it becomes a true statement, if we take value of yates atements are open statements. Thus if a mathematical sntence is neither true nor false it is called open senten 4 ce. pefinition ‘An open statement is a sentence that contains one or more variables such that when contain values are substituted for the variables, we get statements examples 1xt7=9 2ax+2>8 3.xeA I Truth Value of a Statement Statement has a definite truth value which is either true or false. True values are denoted by (I) and false values are denoted by (F). EI Truth Table ‘A table giving all possible truth values of a statement is called truth table. |Exercise 4.1 | 1. Which of the following statements are true and which are false ? a9<22 ») 2 is a prime number. ) 41 is a composite number. @)2+5=34+9 . What type of the sentence is x+8=17? For what value of x following sentences will become true statements ? a)3x+9=15 b)xt+6=8 ox+1>5 djx+2<8 ¢) Sx 2 25 ff) 5x $25 Which of the following open statement a)x+4=6 whenx=2 c)x+5#8 whenx=3 ) 3x + Sy = 11 when x = 0, = ee TECHNICAL PUBLICATIONS? An up trust for knowledge its are true ? p) x +44 6when x =2 d) 2x + 4y = 14 when x=1y=3 ya2 Set 2, x) when x =5S Define the Sollowing and illustrate each by an example. a) Statement ») Open statement NSWers fe) True b) True ¢) False) False Bee Open, statement. Se a)ixa2 b)x=2 a) x25 Dx<6orx<5 x25 fx<5 a) True b) False) False 4) True e) False) True. na Logical Connectives Every statement must be either true or false but not both. If 3 two or more statements, they can be combined to produce a These statements are called compound statements. To combine statements we use following symbols. Ea Conjunction (‘\' or ‘and') If p and q are Statements, the compound statement ‘pA q' is 'P and q' and is Conjunction q’ or 'p meet q- 4 ‘A’ denotes ‘and’ and is known as conjunction. Examples 1. Let us consider P : Shalaka is in senior KG, 4: Shalaka likes drawing, then p A q is the statement Shalaka is in senior K.G. and likes drawing. Definition NEW: staysnematics i _ agate Mathomne 4-5 Propositional Logic pi3>2 q:9 is an odd number, then p 4 q is the statement 3 >2and 9 is an odd number, p : 28 is divisible by 5. q : Shalaka likes swimming, then p 4 q is the statement 25 is divisible by 5 and Shalaka likes swimming, Remark i, If there is no connection between two statements still we can combine them in logic. ii, ‘But’ and 'while’ are treated as equivalent words to ‘and’. iii, Conjunction is a binary connective as in conjunction we need atleast two statements to combine.] 1. If p is true and q is true then p , q means the resulting statement is true. 2. If p is false and q is false then p » q is false. 3, If pis false and q is true then p a q is false. 4. If p is true and q is false then p A q is false. Truth table for p aq P\qis true only when both are true otherwise false. 145.2] Disjunction ('v’ or ‘or') When two or more statements are combined by the word ‘or’, the compound Statement ig as disenedeah The symbol 'p v q' is read as 'p or q' or ‘p disjunction q' or 'p join q). TECHNICAL PUBLICATIONS? - An up thrust fr knowiedge4-6 Discrete Mathematics Examples Let us consider the statements 1. P: I will purchase a dress 4: Lwill purchase a book, then p v q is the statement he I will purchase a dress or I will purchase 2. P : a is equal to 5. 4: b is equal to 7, then p v q is the statement a is equal to 5 or b is equal to 7. 1. If pis true and q is true, then p v q is true. 2. If p is true and q is false, then p v q is true. 3. If p is false and q is true, then p v q is true. 4. If p is false and q is false, then p v q is false. Truth table for p vq Remark - Freee teas citer & tue or gis tue or bth p and q aw te is false if both p and q are false, ae fi, Disjunction is a binary connective 4H The exclusive disjunction of exclusive ‘OR Propositi 2 Soe Siher pls te or qs tue bat bother Be AP a ta oe uaa ge ) SENrete Mathematics 4-7 Propositional Logic jv, Inclusive disjunction or inclusive ‘OR’ of two propositions p and q is the statement. ‘Either p is true or q is true or both true: ie. pyq truth table for p®q [exclusive ‘OR'] asc ee a ee ao j | P L q Pea | | ee eae F | 2 eee aes a a ree LE eg ee example for exclusive ‘OR’ | shall go for walk or I shall watch TV. Here the connective ‘or’ is used in exclusive sense. ie, Either one or the other is possible at a time but both are not possible. [EGEI Negation (~) Let p be any statement then negation of p is denoted by '~p' (or ) is read as ‘not p'. Ifp is true then ~ p is false. If p is false then ~ p is true. Truth table ~ p is a unary connective as only one statement is required to form negation. Examples 1. If p is the statement ‘Ram is intelligent boy’, then ~ p is the statement. ‘Ram is not intelligent boy.’ or 'It is not the case that Ram is intelligent boy.’ 2. If p is the statement 'I like to read’, then ~ p is the statement. ‘T don't like to read’ or It is not the case that I like to read. TECHNICAL PUBLICATIONS” An up thrust for knowledgeDiscrete Mathematics ERX conditional connectives (if - _Consider the proposition ‘If Akash ge will get admission for engineering course: C in 12" examinati ts 90 % or more ™ then i, We can write this statement as ‘If p then q’ P: Akash gets 90 % or more in 12'" examination. q : Akash will get admission for engineering course. This is an example of implication of q by P- Definition Let p and q be two propositions, then the statement ‘if p then q' is denoted by p — q (p implies q) or 'p is sufficient for q' or 'p only if or 'q if p' or 'q is necessary for p’. P is known as hypothesis or antecedent and q is known as conclusion or consequent, A statement or Proposition of the form p > 4 is called a conditional statement or conditional proposition. Example ‘If a is in S, then a is in € (complex number) the hypothesis is a € % and the conclusion is a €. This can be expressed as ae R > ac 1) If p is true, q is true then P qis true. 2) If p is true, q is false then Pq is false. 3) If p is false, q is true then Pp qis true. 4) If p is false, q is false then Pp qis true. Truth table for p > qpscrete Mathematios 4-9 Propositional Logic a - SS -———++—_+ I F T Sy ae i Seem se | Examples for conditional connectives 1. p: The function is differentiable. q: The function is continuous, If p then q ie pq or p is sufficient for q. 2. p: Weather is good. q: Match will take place. If weather is good then the match will take place. p>q 3p: (E+) isa field. q: G, +, is an integral domain. 1: (R, +,) is a ring. Oe Every field is an integral domain. @i) por Every field is a ring. (i) q>r Every integral domain is a ring. Remark If p, then q qifp P only if q, P is sufficient for q q is necessary for p are all equivalent to the statement. Pq. a TECHNICAL PUBLICATIONS®- Anup thst or IowiedgeProposit Discrete Mathematics 4:10 St Lope Remark 1. Converse of p > q is q — p. 2. Inverse of p + q is ~ p> ~ 4 i valence) EXE Biconditional (or Double Implication or Equiv ) " ‘ alled bi i If p and q are two propositions, then 'p > q' and 'q > P 1S & conditional o, double implication. It is written as eal and it is known as 'p if and only if q’ : awe ‘if and only if is shortened as ‘iff’. © is also known as ‘implies and is implied’, We also say ‘p is necessary and sufficient for q’. P © q is true when truth values of p and q are same, ie. either both true or both false and false otherwise. Truth table for po q Bere) a oP PiLQS @>9A@>p) Ze Biss F F T Example Ina triangle ABC, p:2C=90° q: (AC)? +(BC)? = (AB)? If p then q peoe od aD [By Pythagoras theorem] Also if q then p ieq>p ~ @) [lf (AC)? +(BC)? =(AB)2 then ZC = 904) From equations (1) and (2),Propositional Logic piscrete Mathematics [EI Contrapositive of an Implication ‘The implication ~ q — ~ p is called the contrapositive of the implication p > q- ie. implication p — q and ~ q ~~ p are the contrapositive of each other. Example i) If in a triangle ABC, 2 A = 90° then (AB)? +(AC)? =(BC)?. ii) If in a triangle ABC, (AB)? +(AC)? # (BC)? then 2 A 490°, ‘Above two implications are the contrapositive of each other. 1) If p is true, q is true then p — q is true and ~ q is false, ~ p is false but ~ q> ~ pis true. 2) If p is true and q is false then p — q is false, ~ q is true and ~ p is false but ~q > ~ pis false. 3) If p is false, q is true, then p + q is true, ~ q is false, ~ p is true but ~ q— ~ pis true. 4) If p is false, q is false, then p — q is true, ~ q is true, ~ p is true and ~ q— ~ pis true. The following table gives the truth value of the implications p > q and ~ q > ~ p. Truth table for p > q and ~q >~p4-2 + i) ps: There are many clouds in the a q: It rain. “ PA~q ii) p: I will get first class. q: I study well. 1: Score above 80 in mathematics. “Pe (qa iii) p : Computers are cheap. q : Softwares are costly. = PA iv) p : It is very hot. q: It is very humid. 1: Ramesh is having heart problem. “ @AQvr v) p : In small restaurant food is good. q : Service is poor. “Pad vi) p :I finish my submission before 5.00 pm. q : It is very hot. r: I will go. s : I will play a game of hockey. 2 (pa~q) > (ras) TECINCAL PUBLCATON® Ano at br owscrote Mathematics ° 2 Propositional Logic solution: i) PAq ii) (PAA > p) iii) pO~q iv) (~PA~Q>~r v)~pa~qa~r. GENIE rr te conti, cn : » converse, ini conditional statement given below : werse and negation forms of the ‘if x is rational, then x is real,’ Solution: Let p : x is rational, q: x is real. Symbolic form : p > q Contrapositive : (~ q > ~ p) If x is not real, then x is not rational. Converse : (q > p) If x is real then x is rational. Inverse : (~ p > ~ q) If x is not rational, then x is not real. Negation : ~ (p — q) 22650) «eae sia (EERE) press the conirapostioe, . if3 t Contrapositive : (~ r > ~ (p49) ie. ~r—(~pv~q) ie. it sin % +5 then 326 or 1+1#2 = TECHNICAL PUBLICATIONS” - An up thrust for knowledgePro ee | | Exercise 4.2 ie. if 32bor1+1+#2 then sin Converse : r 5 (p aq) ie. if sin $= then 3 ~ 1 ie (~pv~q)o-r 1. If ’p’ stands for the statement 'I read book’ and ‘q' stands for 'T go for swimming’, trang, the following in words aprq Dpva o~pvq a pa(~q If ‘p’ stands for the statement ‘Ramesh is a player’ and ‘q” stands for ‘Mohan is q strong boy’, translate the following in words : apaq D~paq pat-q) d)~pa-q D-prag fl-~perq pr>~q If ‘p’ stands for ‘I run fast’ and ‘q’ stands for ‘I shall win’, express the following symbolically : a) I do not run fast. 5) If I run fast, I shall win. ©) I run fast or I shall not win. 4) I run fast and 1 shall win. ¢) I neither run fast nor I shall win. f) I shall win if and only if I run fast. 4 If p stands for ‘it is cold’ and q stands for ‘it is raining’ translate the following into symbols : 4) It is cold or it is raining. b) It is cold and it is raining. ©) It is cold but it is not raining. 4) It is not cold but it is raining. 0) If it is not cold then it is not raining. peal ‘fi Sufficient condition for rain is that itis cold. g) A necessary condition for raining is that it be cold Wy A necessary and sufficient condition for raining is that it be cold. wv » TECHNICAL PUBLCATONS. An op mt er nounagepisorote Mathematics 4-15 Propositional Logic ‘Answers 1, a) read book and I go for swimming, b) I read book or I go for swimming, ¢) Either I do not read book or I go for swimming. d) I read book and I do not go for swimming. 2, _ a) Ramesh is a player and Mohan is a strong boy. b) Ramesh is not a player and Mohan is a strong boy. c) Ramesh is a player and Mohan is not a strong boy. d) Neither Ramesh is a player nor Mohan is a strong boy. e) This is not the case that Ramesh is a player and Mohan is a strong boy. £) Ramesh is not a player if and only if Mohan is a strong boy. g) If Ramesh is a player then Mohan is not a strong boy. 3 a)-P Piped pv (~q) dpagq e)~pa-q Nqop 4 apvq DPA ) pa(~q) d) (~p)aq e-~p>-~q fq>p 8)P>4 py need Tautology A tautology is a proposition which is true for all truth values of its sub-propositions. In other words a proposition is a tautology if it is always true for all assignments of truth values. EE] contradiction A proposition is a contradiction if it is always false for all assignments of truth values. Remark : A proposition which is neither a tautology nor a contradiction is called a contingency. carga renee anne GENE sion tne i a feitaleey "TECHNICAL PUBLICATIONS®- An up tus for knowledgeDiscrete Mathematics Solution ; Since in p > p all the truth values are true (T), EEEEOEES Show that p v (~ p) is a tautology. hence p — P is a tautology. Solution : Since in p v (~ p), all the truth values are true (T), hence p v (~ p) ha that ip a (ply a Solution : Hence ~ (p (~ p)) is a tautology. Remark : p » (~ p) is a contradiction as all the truth values are false (F). Tes istey Example 4.8 Hence (p > q) © (~ p) vq isa tautology. TECHNICAL PUBLICATIONS. Anup tua er nowoage peepiserete Mathematics ee sdciaiteee! Construct truth table for (question 1 to question 5) to find if each of the following is a tautology, contradiction or contingency. 10992) 7), Solution : Consider the truth table, q 5 P49) 059 Gon P5q>y PQ >~>) PIG>D> ye @>9>0 >») T (* T tT T Ae T Salers wy a o UF ae) F at D i z T a AE |e F || F 1 sual eiFl Ff len olen! Br ane TOT ry T a T re Flot |e ee ee a a TOF| T T ol iw J Feuer FOF. fe My T tT! ur eae T In the last column all truth values are (T), hence (p> >») > (P > 9) > (P 2) is a tautology. 2)((pvqa~P)>4 Solution: Consider the truth table. Hence ((pvq) ~ p) > q is a tautology. 3) (P39 AG>01 9(P>) Solution: Consider the truth table. TECHNICAL PUBLICATIONS? - An up thrust for knowledgeHence [(p— q) a (q 1)] + (p> 1) is a tautology: 4) (PAg A~(pvag) Solution : Consider the truth table. et See Hence (pq) ~ (pv q) is a contradiction. 5) (p> 9) (qv ~p) Solution : Consider the truth table. E v-p (po@d—> @v~p) (©3906) ie P q P op7a 4 avon) 559) Wee 2 ee F F oe T Hence (p— q) © (qv ~ p) is a tautology. CEERI ve proton p=) i te. Solution : Prise ce Pag ~@aq@ Bek ec Z stew ion Baier apes eR gear eet iwte ole eB, = F F E Hence pv ~ (pq) is a tautology. TECHNICAL PUBLICATIONS. np tus or imowledgoDiscrete Mathematics a: Soild, Propositional Logic (EB) Precedence Rule ee ae ity Operations on numbers, we realize the importance of BODMAS ce ane se a ee ues calculating the value of an arithmetic expression, we lue of the Bracketed part the ati Be dition and subteatieneite ome cee ek apply of, division, multiplication, Similarly while calculating the truth value of compound propositions involving more than one connective, we have a similar convention which tell us which connective to apply first Suppose we did not have an order of preference and want to find the truth of ~ pv q- Some may ‘consider the value of (~p)v q and some may consider ~(pvq). The truth values can be different in these cases. For example : If p and q are both true, then (~ p) vq is true but ~ (pv q) is false. So, for the purpose of unambiguity, we agree to such an order or rule. The rule of precedence : The order of preference in which the connectives are applied in a formula of propositions that has no brackets is i)~ ii) A iii) v and ® iv) > and & Remark : 1. 'v includes ‘exclusive or’ and ‘inclusive or’ both. 2. 'v' and '@' which are both third in order of preference. If both these appear in a statement, we first apply the leftmost one. The same applies to the > and <>. no Logical Equivalence In mathematics, as in ordinary language, there can be several ways of saying the same thing. Definition Two propositions A and B are logically equioalent if and only if they have the same truth value for every choice of truth values of simple propositions involved in them. We denote this fact by A = B. In other words two propositions A and B are logically e Aq Bis a tautology. quivalent if and only if TECHNICAL PUBLICATIONS? - An up thrust fr knowldge'Y equivalent using truth tables Prove that (p vq) \~ p =~ PA: Solution : Consider the truth table. P q ~P Pua iS! eT T F E aad F F Bi F T T T F F T F i From the table, truth values of (p vq) ~ p and ~ pq are same for each choice of P and q. Hence (p v q) 4 ~ p is equivalent to ~ p 0 q- ie (Pvqa~p = ~paq Prove that @>G>n)=(e>99047) Solution : Consider truth table. por pP>24@>) Pa > 59 cae ee F F me ae E T ae [Pees ee Te T Te een a T T T In last two columns, truth values are same for each choice of truth values of p,q and r hence P>@>*) = (P>q>(P>n) or (P>(q>»)) = (Pq) > (pn) Duality Law Two formulas A and AY are said to be the duals of each other if either one can be obtained from the other by replacing 's’ by \V and 'V’ by ‘s’. The connectives ‘a’ and V are also called dual of each other. TECHNICAL PUBLCATONS. An pat owepiscrete Mathematics 4-21 Propositional Logic Logical identities 4, DeMorgan's laws i) ~(pv@ = (~pa~q) ii) ~(PAq) = (~pv~q) [Dual of (i)] 2, Associative laws i) pv(av2) = (pvqyvr ii) PAAD) = (PAQ)ar {Dual of (i)] 3. Commutative laws i) Pyq ™ qvp ii) PAG = qap [Dual of (i)] 4. Idempotent laws i) PVP =p) ii) PAP =P [Dual of ()] 5, Double negation ~ CP) =e 6, Distributive laws i) pv(qax) = (pyg)a (pv2) ii) pA(qvr) = (pAqgv (par) [Dual of ()] 7. Absorption laws i) Pv(PAq) = P i) papva) =P Deal of Logically equivalent TECHNICAL PUBLICATIONS” - An up thrust for knowledgeProposition 4-22 Logie Solution: i) ~ (pvq) = ~pa-a Consider the truth table. ae ~(pv@ Paw From the table, truth values of ~ (pv q) and ~ p’~ q are same for each choice of p and q. Hence ~(pvq) =~pa~q a) ~(PAq) = ~py~q Consider the table. q Ss el pAq ~(PA@ —~Pvaq F a T a From the table, truth values of ~ (pq) and (~ pv ~ q) are same for each choice of pand q. Hence ~(paq) = (~pv~q) Smee Ee ace Solution :. i) pv(paq) =p TECHNICAL PUBLICATIONS. An ptt orionte Mathematics ai 4-23 Propositional Logic Dis p. a PAq ig T T rr F F b FE aa Bane F eae ee From the table, in last two columns, trut truth val each choice of p and q.. Hence values of pv(paq) and p are same for Pv(PAq) = p ii) pa(pya) =p Consider the table. mains From the table, last two columns are identical, hence PA(pvg) = P Note : Proofs of remaining identities are left as an exercise to the students. SERED es - Solution: Consider the table. P 2 — are Es - as tae ee : T Sea ee F tie eee he Hence ~ pv q and p—>q are logically equivalent. TECHNICAL PUBLICATIONS” - An up thrust for knowledgeDiscrete Mathematics “4 ——s = pO & logically equivalent to (p>DAG p) also (P>9) Ag 5) @ logically equivalent to (~ pv q) a(~ 4 P)- Solution : Consider the table. Po 4 ~P ~a psa q rp Po@aca>p) Pod -~PYd “IVP CPvq, Cavp tl afeter| ot T tig) ae T oF al T F T F 3 y z e Fatal et Fe [era F oT ee [Fler oa) T T T T a a T From the table, t_t_______+ Pq = (~pvq)a(-~qvp)=(p> dA > P) Normal Forms In logic, with the help of truth table we can compare if two statements are equivalent. But when more statements or propositions are involved, then this method is not practical. [As if n propositions are involved, its truth values will be 2" ] Hence, it is necessary to apply another method. One method is to transform Sj andS3 to some standard form Sj and $5. Such that a simple comparison of Sj and $3 should establish whether Si = S}. The standard forms are called normal forms or canonical forms. Disjunctive Normal Form [dnf] Disjunctive normal form is a disjunction (V) of fundamental conjunctions (a) . Now fundamental conjunctions (1) are conjunction of simple statements [i.e. joining two statements by 'a]. fe. Pr, PAG ~PAG ~PA~q PA~p, qa~q, pa~q, ~ p are fundamental conjunctions. Hence disjunction of fundamental conjunctions are joining fundamental conjunction by. TECHNICAL PUBLICATIONS. tn up att in Ne ee | aethematics p pero ath 4-25 Propositional Logic examples 1) (PADYPVGA~P) 2) (PAGADY(PAQ’AT) VP’ Agar) 3) (p'AQANV(PAQ) 4) (pagvl) 5) (pag (tag) v(~ rap) Remark qA~ 4 PA~P ate always false. Hence if a fundamental conjunction contains at least one pair of (p and ~ p) or (q 4 ~ q) etc., it will be false. Example 1, Obtain the dnf of the form paip>q) = pa(~ pvq) [as p>q = ~pval = (pA~p)v (Pag) [Using distributive law] = Fv(paq) =(paq) dnf Conjunctive Normal Form (cnf) Conjunctive normal form is a conjunction (A) of fundamental disjunctions (v). Now fundamental disjunctions (v) are disjunction of simple statements. [ie. joining two statements by 'v] Example PYq, PY~q,~PVq, ~PV~ 4, ~ P, ~ % P, q, ete. are fundamental disjunctions. "Hence conjunction of fundamental disjunctions are joining fundamental disjunction by'a Examples 1 (pvg)a (qvx)a (~ py~») 2. pa(~qv~r) 3.(pvqv~1)a (pvg)a (- pvav~) TECHNICAL PUBLICATIONS" - An up thrust for knowledge4-26 Discrete Mathematics eae Truth Table Method to Find dnf v3 pi, P2” Let p be a proposition containing variables P1 To find its dnf from the truth table: Step 1 : Consider the true values (T) from P. Step 2 : Form the conjunction ('4') (Pi Apa A oA Pi Ae ABR A oA Pav where if p; is true consider p; and if py is false consider ~ Px such a term is called minterm. Step 3 : The disjunction of minterms is the anf of the given form. Conjunctive normal forms and disjunctive normal forms (cnf and dnf) Obtain conjunctive normal form of D(-prnaer” i) (RADY PAIAN, Solution : i) (~ p> )a(P> = (~(~p)vgaPvd = (py@a(-pya) ent ii) (paqy (pagan = (pv(~ pagan)a av PAGAD) . (py~p) apy awyn)a(ay-PAav dala) = Tapa aipy) Aav-P)A@AaYD) = (pyv@atpynaqy~p)a@acays) one (QEEEERED Fired conjunctive normal form and disjunctive normal form for the without using truth table. (p>gag>P) Solution: (p>q)A(q>P) = (~pyq@a(-qvp) cnf ©) Pires Pky oe Propositiongy len Pn- [As p> = ~pvq] [As ~ = p=] [Using left distributive law] = ((~p)a(-avp))v(qa~qvp)) [Using distributive law] = (~pa~a)v(~ Pap) v(qa~q)v(qap) = (~pa~q)VFVFv(qap) = (~pa~q)v(qnp) dnt TECHNICAL PUBLICATIONS’ - An up thrust for knowledgepiscrote Mathematics 4-27 Propositional Logic Obtain disjunctive normal form of DPIDAC PaAQ) i) PAP >) 4 Solution: i) (Pp q)A (~ pag) = C PY A png) (p> = ~pval = (PA pag)viqa~ pag) [Using distributive law] =(GPA~p)agviqaqn~p) [By associative and commutative laws] = (~ pq) v(qa~ p) anf [By idempotent law] i) (pap? 9) > 4 = (PAC pyg)3q [p> q=~pval (PA pyg))vq = ~pv(-(~pvq)vq = ~pv(pa~q)vq dnt Obtain the conjunctive normal form fay of the following : dp AG >9) ii) ~ (pv g)o(paq) Solution: i) pa (p> q) = pa(- pvq) enf i) ~(pvq) @ (PAQ) = (pvav@aglal-(pagv~(pvgl Po q=(- pyvga qvp)] = [pva)vpagalc py~ av(~pr~q)] = [Pvavp)A@vav DIAl(- py ~ qv ~ p)a(- pv~qv~ ql = (PYQA(pYMA- pY~ QA PY~ 9) = (pyqa(~pv~q) ent — IPEQvn)>~P — W(~3)>9> 4 Solution: Using truth table method, find dnf, which is logically equivalent a given form. TEGHNIGAL PUBLIGATIONS? - Anup tus fr howeDiscrete Mathematics “ = awe pov? Pe@vns. 4 r - > T D T F T - a a T F F Z 3 eee or Rate TF See E F a T iT T 0 F F T Sa T T F pea, F T on | ot [aseciee | t L t Consider only (I) from last column and choose corresponding ae a from p,q, eg. for marked row (9), corresponding p is true q and r are false, 80 consider (PAQ’Ar) oF (PA~qn~D)- Similarly for other (T) values choose truth values from column of P, q t. Choose p ig P is true otherwise p’ or ~ p if p is false. Hence the logically equivalent form of (POQvn)>~pP = (Pag ar)Vip’ GAY AGATIVP'AD AD) v(p'aq’ar) sane «2 (GAT) A= p9(~ pa~1)) by truth table method. — oe Solution r~po(~pr~n (p> qan) ACP P 4 © -Pp~r qarpoqar~P bat) | fo | | malin fa alalalal Hence the logically equivalent form is (PAGAN AgAr)V(p'Ag’ ar’) TECHNICAL PUBLICATIONS. Anup het or