LECTURE NOTES ON LOGIC COURSE OUTLINE (a) Symbolic logic (b) Special symbols in symbolic logic (©) Conjunction, negation and disjunction (d) Distribution (e) Equivalence and conditional statements (f) Laws of thoughts {g) The methods of deduction using rules of inferences and the bi conditional qualification theory. AIM AND OBJECTIVE Encourage or enhance his/her critical thinking and reasoning, Student power of persuasive arguments and level of understanding rational discussions and controversies are expected to be significantly raised by this course. SYMBOLIC LOGIC: INTRODUCTION and “ratio”. Of course, these translations are not enough to help us understand the more specialized meaning of logic as is used today. The term logic came from the Greek word logos, which is sometimes translated as “sentence”, “reasons” Definition: Logic can best be defined as the science of good reasoning. Reasoning is a kind of thinking that oims at conclusion. In other words, logic Is the study of arguments. More speeifiealy, logic Is the study of the criteria for distinguishing good argument from bad argument. Part of logic which enables us to reduce reasoning to an algebra which has fixed and simple rules will be considered for discussion. Example: Consider, for example, the following argument or statements (a) All Mathematicians wear sandals. (b} Anyone who wears sandals is an algebraist. (c) Therefore, all Mathematicians are algebraist. Proposition A proposition is a statement that is either true or false, but cannot be both. These statements may be “verbal or written, When a propesition is true, @truth value T.is assigned to it and a truth value F whon it is false, A statement that cannot be assigned T or F value is not a proposition in logic.The following are examples of propositions {a) All women are beautiful (b) A pastor is man of God (c} All men are born by a woman (d) Accra is not in Ghana (e) Obama is the president of Kuwait (f} Earth is the only planet in the universe that has life The following are not examples of propositions: (a) Who are you? (b) When is the party taking place? {c) twas wonderful! (d) Leave now! (e) What a pretty woman Generally, 2 proposition is typically expressed as a declarative sentence (as opposed t0 2 question, ccclamation, commands and any expression of feelings that cannat be assigned a truth value T or F}. Propositions are the basic building blocks of any theory of logic. Compound proposition ‘A proposition consisting of only a single propositional ‘an atomic proposition or simply proposition that is they cannot be further subdivided, A proposition obtained from the combination of two or more propositions by meens of logical operators oF or more propositions or by negating a single proposition is referred to as compound variable or a single propositional constant is called connectives of tw! proposition Connectives ‘The words and phrases (or symbols) used to form compound propositions are called connectives. There are five bosic connectives called negation, conjunction, 2 or bi-conditional. The following symbols ae used to represent connectives. disjunction, implication or conditional and eequivatenc Connectivesin | Nature ofthe compound Symbolic form | Negation word statement formed by the connective | negation ad (rp) = 2 conjunction Pag (cp) v (a) disjunction Pva [els ea) implieationfor conditional) | P —a pArQ) Equivalence or bi- Ped Teall ta (“Pl conditional alNegation If p is any proposition, the negation of p, denoted by ~p and read as “not p”, is a proposition which is false when p is true and true when pis false. E.g. P: turkey is in Japan, the negation of this statement is ~p: Turkey is not in Japan. Strictly speaking, not is not a connective, since it does not joint two statorents and not p (~p) is not a compound statement, However, ~p is a statement If p is considered a statement. Conjunction If p and q are two statements, then the conjunction of p and q is @ compound statement denoted by p* qand read asp and q’. The compound statement p and q is true when both p and q are true, otherwise itis false. ‘The truth values of p and q (p4.q) are given in the table below ptalerg tT[t] 1 T{FLF F(t] F Feel F : In logic, we may combine any two statements to form conjunction; there is no requirement that the two sentences be related in content or subject matter. Disjun If p and q are two compound statements, the disjunction of p and q is the compound statement _ denoted by pY @and read "p or a’. The statement p Y qs true if at least one of p or ais true, is alse wuhen both p and q are false. E.g. the required candidate for the office must be someone that knows how to speak English or Hausa. Certainly, we cannot reject a candidate if he knows both languages. The truth table of p ¥ qis given in the table below. fal eva TIT 7 T{Fl_t : e[t] FFL e ‘The truth value of a compound statement depend: only on the truth values of the statements being tomibined and on the type of connectives being used. Truth tables are especially valuable in detezmination of the truth values of a proposition constructed frem simpler propositicns Bxample Construct truth table for each compound proposition (i) (“a a) (i) ~ (oY a) ¥ (~p.Aa) Solution {i) Make columns labeled p, a logical combinations of T's and F's as can be seen below. mq, (4 a) DA Ca¥ gh fil the p and q columns with the poss? =F a[al=|ala a}n|a|n (ii) This is left as an exercise to the reader. Example Verify whether or not the two compound propositions are equal. (i) “p ¥ ~q and ~ {p *.q) (ii) ~P A ~a and ~ (pV q), this is an exercise for the reader. Conditional proposition Conditional Proposition or implication and the connective is the conditional connective. The proposition » is called the antecedent or hypothesis, and the proposition q is called the consequent or conclusion. The conditional proposition p > q is true unless p is true and q is false! In other words, it means that a true ststement cannot imply a falge statement. The truth value of the conditional statement p — q Is given in the table below. a|>]5]5)5 a]a) >|] 5 afaln}al] ‘As can be seen from the table above, the only situation under which the implication p —+ qs false is only when p Is true and q is false, To understand better, implication can be looked at as @ conditianal promise. If the promise is broken, the implication is false otherwise it is true. For this reason, the only circumstance under which the implication p — qs false is when p is true and q is false. Example Which of the following propositions are true and which are false? is round, then the earth travels round the sun. ‘raha Bell invented telephone, then'tigers have wings (iif the earth (iif Alexander (i) IF Tigers have wings, then X-ray is dangercus solutions: sinis ound, ¢: the earth travels ound the sun. Here pf true and is tru, hence the (i) bet a: the cart 1 true (i) Let p: Alexander Graham Bell invented telephone, q: tigers have conational piercer false, hence the conditional proposition is false(il)Let p: tigers have ings. Hore pis tus an0 8 hence the conditional proposition is tue. ancray is dangerous isf pis false and qis true,Example Compute the truth table for (a)p¥~q—>p —(b) [~ (pa) V1 ~P Solution Let the compound statement be as given below [a [-alovna| Yn TITIEF T T TIFT T T FUL TIE F T FUL FIT T F (2) Let the truth table of the compound statement be as shown below ~(pAq) | “(pra)¥r |i (pAqg)¥ 1 >~p F F = [> ]=]=]]]5] 4] ey ofa] a|ala]a)a]]5 -n|n]-n]-]m]x |] a] a}a|]a}4|n]4 a] a]a}a]n]x]s a]a|-]-]4)4|> Example Using the truth table, show that p —> ="p¥q Solution ‘The truth table of pq and ~p Y qs as shown in the table below Pla] Pa [~p] ~P¥a Tit] 7 [F T TIF FF F Flt| t | T F[F[ 7 [7 T Looking at the truth table above, the logical equivalence is established by the third and fifth columns which are identical, This means that the logical statements p qanci~p ¥ q are equivalence. Bi-conditional statements Hf p and q are statements, then the compound statement p if and only if q, denoted by p ++ q is called a bi-conditional statement ‘and the connective if and only if is the bi-conditiofial connective. The 2: conditional statement p r+ q can also be stated as “p implies q and q implies p". The truth value of the bi-conditional pq satisfies the following properties,1) Fp and q have the same truth value, then p = q is true (ii) fp and q have opposite truth values, then p + qis false. V / The truth table of p © qis given in the table below. t pla[Poaq T|T| T TIF[ F Fit[ Flel T The above table is called the truth table for the bi-conditional statement p + q. Example Show that (p= q) A(a— p)=p++q Solution To show that these two expressions are logically equivalent, we use the truth table below. pla] poag [Poa] ap] >a A—p) TT T T T T Tle F F T E FLT F T F F F[lF[ tT T T T Since the columns corresponding to the given two expressions have the same truth values, we conclude that (pq) 4(q— p)=poa. Example Show that p+ q=(p¥ a) > (Pa) Solution Using the truth table below, the logical equivalent or otherwise can be obtained. pla] Peal P¥q | PAq {p¥ q) = (pAq) Titi t T T 7 | a T F F ae T F F PLE F F T hue columns corresponding to the given two expressions have identical ruth values, we conclude Since the colun 8 that p+ a= (p> (PAD Exerei peevg (i)perastpcra tiple pa) (pr) (yr {p4dconverse, contra positive and inverse plication q — p, the contra positive of p If pqs an implication, then the converse of p a is the im p+ ~q. The truth table of the four = q is the implication ~q — ~p and the inverse ofp q propositions follows as: CP Tq | Conditional | converse | Inverse Contra positive proposition | q—p | *P—7™4 “q>"p Pog T{T T T T T TLE E T T E FT T E E T FIF T T T T Consider the following statements: P: it rains, q:the crops will grow. The implication p + q states that , then the crops will grow. The converse of this implica: riamely q— p states that st if the crops grow, then there’ has been rain. The contra positive of implication p — q, namely ~q — ~p states that: if the crops do not grow, then there has been no rain The inverse of this implication, p —+ q, namely ~p —» ~q states that u: if it does not rain, then the crops will not grow. on, the Note Notice that @ conditional proposition and its inverse or conversa Is not logically equivalent. On the other hand, a conditional proposition and its contra positive are logically equivalent. Example: Show that a conditional proposition and its contra positive are logically equivalent. That is~4—- ~p = p 4 Solution The truth table of ~q— ~p and p — q are shown below and the logical equivalence is shown by the last twe columns whic are seen to be identical. pa |p |-a tite {F TlFl[e# {t F[t|7]/F Flre| tt Since the column orresponding to the given two expressions have identical truth values, we conclude pa that ~qal equivalence 'F two propositions P(p, 9, ..) and Q(p, q, .) where p, g, .. ae propositional variables having the same truth values in every possible case, the propositions are called logically equivalent or simply equivalent and denoted by P(p, 4, ..) = Op, q, w) Itis always permissible, and sometimes desirable to replace a given Proposition by an equivalent one. To test whether two propositions P and Q are logically equivalent, the following steps are followed. (2) Construct the truth table for P and Q () Check each combination of the truth values of the propositional variables to see whether the value of P Is the same as the truth value of Q. If In each raw the truth value of P Is the same as. the truth value of Q, then P and Q are logically equivalent, Exercise Use the truth table to verify the following pall) ~p Y q=~q— “plill) (2 ¥q) Ye PY(G* liv) (PAG) AT=pA(GAry) pY(qa AIRY GAIA) (vi) “(pV qh=panq Negation of compound statements: Negation of conjunction A conjunction of p and q (p 4 q) consists of two sub-statements p and q both of which exists simultaneously. The negation of a conjunction of p and q (p A q)s the disjunction of the negation of p and the negation of q. equivalently, we write ~ (p 4 q) =~p ¥ ~q as can be seen from the truth table below. Fle SSince the two corresponding columns to the given two expressions have identical truth values, we conclude that ~ (p 4q)=~pY “a, ation of a disjunction ar lunction of p and q (p ¥ q) is consisting of two sub statements p and q which are such that either p ora both exists. The negation of p or q [~ (p ¥ q)] is the conjunction of the negation of p and q. or gor ats. ‘equivalently, ~{p ¥ 4) =p 4 "a as can be seea in the truth table below. p [a [eval 9 [a] ~pva@l | -pAva Tht>t [FlFl - F The) + ]Fi[tl © F : : F[t>t[tiFl - F rile] * [tt Tcal truth value.) & since the two corresnonding columns to the given conclude that ~(p¥ a) =p 4~q. ‘Associative law \fp, q and s are three propositions, then (i) p ¥ (q¥s) =(p ¥ q) Y sand (ii) p (qs) = (9 Aq) As. These can be seen as in the truth table below. pals favs[Pvavs) [P¥a] (pvalvs t[t|[+[ Tt T T T tT[tlF[ tT T T T Tle l[t[ 1 T T T Tel FF T T T F[t{[t| 1 T T T e[tiel 7 T T T Fle[t|[ Tt T F T Fle{rel el Ff F_ F cance the two corresponding columns to the given two expressions have identical truth values, we conclude that p ¥ (qYs)=(p Yq) Ys and (i) pA(q45)=(p Aq) &5is as shown in the truth table below. S| PAtaAs) [P T g| (pAajAs +] >] =]=]]5]/o {|= |-n]]5]o aln]a]>[a]=]a]6 an|-n]-a]-n]-n]--] 5] >| -n|-n]-n]-n]-n]]-] > Fle[rl F F E Since the two corresponding columns to the given two expressions have Identical truth values, we conclude that p 4 (q 4s) = (pq) s proving the associative laws. Distributive law 34245) 2 642) a (ars) if p, qand sare three propositions, then, p¥ (qs) =(pY q) 4 (ps) and pA (q¥s)= (pq) (ys). The establishments of these facts are left to the reader as exercise. Tautology Ordinarily, when we write a compound proposition, we cannot be certain of the outcome of the iruth of the proposition unless we know the truth or falsity of the component propositions. But that is true regardless of the truth values of its components can be constructed. Proposi are called tautology. a propasition tions of this kindDefinition ‘A compound proposition that is always true for all possibl words contain only T in the last column of its truth tabl: Example Propositions like: (a) The professor is either a woman or a man Je truth values of its variables or, in other called a tautology. (0) People either like watching TV's or they don’t are always true and are called tautology. Example Prove that the following propositions are tautology. (a) PY~p (b)~(pAa)Ya (c)/p—(p¥a) Solutions: {2)The truth table of the given proposition is as shown below. p [=p PY¥“p Tle| 7 F[t|_ 7 Since the truth value is true for all possible values of the propositional variables which can be seen in the last column of the table, hence the given proposition is a tautology. (b) We construct the table for the expression in question. It ¢ Gf p and q, the expression ~ (p 4 q) ¥ q's true, which establist -an be seen that for any possible assignment fies that itis a tautology. pla] Pa] Prag | ~PAaa T/T T F T TULF F T T F[T F T T FILE F T T (c) We construct the table of the given expression as shown below. [palevay Paiva) T/T T T TIF T T FLT T T Cele fF T it can 1 be seen from the last column of the truth table tha it the expression is true for all possible assignments of p and q. hence the proposition is a tautology: 10contradiction A compound propositic i neomponr Ie is son that Is always false for all possible values of its variables or, in other words y 'e last column of its truth table is called 2 contradiction Example Verify whether or not the proposition p A (qA~p) is a contradiction. Solution We construct the truth table for the given expression as shown below. pla]? [aa] PNat~p) TIT F FE F TLe FE FE E FT T T F Cele lt F F It can be seen from the last column of the ‘trathy table that the expression is true for all possible assignments of p and q, the given proposition Is false, which establishes that It |s a contradiction. Universal and Existential quantifiers Given 2 set A, @ propositional function on a set A is an expression denoted by p(x) which has the property that pla) is true or false for each a ¢ A The phrase “for all” (denoted by ¥ ) is called the universal quantifier. Example consider the sentence “All human sing are mortal”, This santenco can be written as: (HxeS): p(x) oF ae: p(), where s denotes the set ofall human beings. x represent each of the following phrases since they have essentially the same meaning: For all x, for every x or for each x The statement (#-xeS): P@) oF P: p(x) s called a universal statement, The expression p(x) by itselfis ‘an open sentence and therefore has n” truth value, However, Px:p(2) does have a truth value and is aesigned truth values 2s follows:-Hx: pC) is ue if plx) is true for every x in U.-Fx: p(x) is false, If and only if, plx) i false for at least one xin U specifically, 5 = (41x05, pC), then Has PG) 8 tus otherwise, Has?) 8 false, A value for which p(x) is false Is called a counter example to the universal statement: Existential quantifier The phrase “there exists” denoted by }s called the existential quantifier. 1Example Consider the sentence, “there exists x such that x = 5 eee z This sentence can be written using the coxistential quantifier as: QxeR)p (x) or }ep(x) where pz)" 2 = 5", Ja represents each ofthe following phrases, There exists an x There is an X. . For some x. There is at least one x. The statement ( : re a ee he statement (xeR)p(S) or Jxp(e) is called an existential statement Jxp(x) has the following truth values. (a) 4xp(x) is true if p(x) is true for at least one x inU. (b) }xp(x) is false, if p(x) is false for every x in U. Wh , ; , on the quantifiers are used, one should specify the universe of discourse: ifthe universe of discourse is changed, the truth value may change. (2) Letz, the set of integers, be the universe of discourse and consider the statements (xe2) 6° (Jxe2}, x x find the truth values of each of the statements. Solution: Let ple) be proposition x= x, then ¥xp() is false beccuse, 1p(3) that is 3? = 3is false. And}xp(x) is true, because at least one proposition p(x) is true. In fact, exactly twoof them are true, namely p(0) and p(1) (2) Let B= (2, 2, 3,4, 9} Determined the truth value of each of the following statements. (a) (uxeD), x#4< 15. (o}¥xeD), x45 10 (c(ixeD), x + 4= 10 (d)(ixeD), x+4 > 15 solution: (a) True, because for every qumber x ind, x+4<15 1s satisfied. (p) True, because there exists east one number x= 6inD, in which x 4= 101s satisfied (c) False, because for some numbers ifiD, x +4> 20, namely, X= 7,8, and 9 (dj Fatse, because there exists ne number xin D that satisfies x + 4>15- 12