Example 2 p represents the proposition Henry VIII had six wives. q represents the proposition The English Civil War took place in the nineteenth century. (a) Connect these two propositions with OR. Is the resulting compound proposition true or false? (b) Now connect them with AND. Is this compound proposition true or false? (c) Is the opposite of p true or false? Answers (a) p ∨ q is Henry VIII had six wives or the English Civil War took place in the nineteenth century This is true. The first part of the compound proposition is true, and this is sufficient to make the whole statement true – if a little odd-sounding! If you think that this example seems very artificial, imagine that youre taking part in a History Quiz; there are two questions left, and you need to get at least one right to win the quiz. You make the two statements above about Henry VIII and the Civil War. Do you win the quiz? Yes, because it is true that either Henry VIII had six wives or the English Civil War took place in the nineteenth century. Note that this is an inclusive OR: in other words, we dont rule out both parts being true. So p ∨ q means Either p is true, or q is true, or both. (b) p \scriptstyle \wedge q is Henry VIII had six wives and the English Civil War took place in the nineteenth century This is false. To be true, both parts would have to be true. This is equivalent to your needing both questions right to win the quiz. You fail, because you got the second one wrong. (c) The opposite of p, which we write as ¬p, is Henry VIII did not have six wives. This is clearly false. And in general, if p is true, then ¬p is false, and vice versa. Example 3 p is The printer is off-line q is The printer is out of paper r is The document has finished printing Write as English sentences, in as natural a way as you can: (a) p ∨ q (b) r \scriptstyle \wedge q (c) q \scriptstyle \wedge ¬r (d) ¬(p ∨ q) Answers (a) The printer is off-line or out of paper. Notice how we often leave words out when were writing or speaking English. This sounds much more natural than The printer is off-line or the printer is out of paper. (b) The document has finished printing and the printer is out of paper. The subject of each part of the sentence is different now, so no words are missing this time. (c) The printer is out of paper and the document has not finished printing. But and And The statement in (c) could be someone reporting a problem, and they might equally well say: (c) The printer is out of paper but the document has not finished printing. So note that, in logic, but and and mean the same thing. Its just that we use but to introduce a note of contrast or surprise. For example, we might well say: The sun is shining brightly, but its freezing cold outside. Logically, we could use and to connect both parts of this sentence, but(!) its more natural to use but. In (d) what does ¬(p ∨ q) mean? Well, p ∨ q means either p is true or q is true (or both). When we place ¬ in front, we negate this. So it means (literally): It is not true that either the printer is off-line or the printer is out of paper. In other words: (d) The printer is neither off-line nor out of paper. Notice that its often convenient to translate ¬ using the phrase It is not true that …. Logic Exercise 1 Click link for Logic Exercise 1. Truth Tables Consider the possible values of the compound proposition p \scriptstyle \wedge q for various combinations of values of p and q. The only combination of values that makes p \scriptstyle \wedge q true is where p and q are both true; any other combination will include a false and this will render the whole compound proposition false. On the other hand, the compound proposition p ∨ q will be true if either p or q (or both) is true; the only time p ∨ q is false is when both p and q are false. We summarise conclusions like these in what is called a Truth Table, the truth table for AND being: p q p \scriptstyle \wedge q T T T T F F F T F F F F The truth table for OR is: p q p ∨ q T T T T F T F T T F F F The order of the Rows in a Truth Table Notice the pattern of Ts and Fs in the first two columns of each of the truth tables above. In the first column (the truth values of p), there are 2 Ts followed by 2 Fs; in the second (the values of q), the Ts and Fs change on each row. We shall adopt this order of the rows throughout this text. Adopting a convention for the order of the rows in a Truth Table has two advantages: It ensures that all combinations of T and F are included. (That may be easy enough with just two propositions and only four rows in the Truth Table; its not so easy with, say, 4 propositions where there will be 16 rows in the table.) It produces a standard, recognisable output pattern of Ts and Fs. So, for example, T, F, F, F is the output pattern (or footprint if you like) of AND (\scriptstyle \wedge), and T, T, T, F is the footprint of OR (∨). The truth table for NOT Each of the two truth tables above had two input columns (one for the values of p and one for q), and one output column. They each needed four rows, of course, because there are four possible combinations of Ts and Fs when two propositions are combined. The truth table for NOT (¬) will be simpler, since ¬ is a unary operation – one that requires a single proposition as input. So it just two columns – an input and an output – and two rows. p ¬p T F F T Drawing up Truth Tables The method for drawing up a truth table for any compound expression is described below, and four examples then follow. It is important to adopt a rigorous approach and to keep your work neat: there are plenty of opportunities for mistakes to creep in, but with care this is a very straightforward process, no matter how complicated the expression is. So: Step 1: Rows Decide how many rows the table will require. One input requires only two rows; two inputs require 4 rows; three require 8, and so on. If there are n propositions in the expression, 2n rows will be needed. Step 2: Blank Table Draw up a blank table, with the appropriate number of input columns and rows, and a single output column wide enough to accommodate comfortably the output expression. If 8 or more rows are needed, youll probably find it helps to rule a horizontal line across the table every four rows, in order to keep your rows straight. Step 3: Input Values Fill in all the input values, using the convention above for the Order of Rows in a Truth Table; that is to say, begin with the right-most input column and fill in the values T and F, alternating on every row. Then move to the next column to the left, and fill in Ts and Fs changing on every second row. And so on for all the remaining columns. The left-most column will then contain Ts in the first half of all the rows in the table, and Fs in the second half. Step 4: Plan your strategy Study carefully the order in which the operations involved in evaluating the expression are carried out, taking note of any brackets there may be. As in conventional algebra, you dont necessarily work from left to right. For example, the expression p ∨ ¬q will involve working out ¬q first, then combining the result with p using ∨. When youve worked out the order in which you need to carry out each of the operations, rule additional columns under the output expression - one for each stage in the evaluation process. Then number each of the columns (at its foot) in the order in which it will be evaluated. The column representing the final output will be the last stage in the evaluation process, and will therefore have the highest number at its foot. Step 5: Work down the columns The final stage is to work down each column in the order that youve written down in Step 4. To do this, youll use the truth tables for AND, OR and NOT above using values from the input columns and any other columns that have already been completed. Remember: work down the columns, not across the rows. That way, youll only need to think about one operation at a time. Youre probably thinking that this all sounds incredibly complicated, but a few examples should make the method clear. Worked examples Example 4 Produce truth tables for: (a) ¬(¬p) (b) p \scriptstyle \wedge (¬q) (c) (p \scriptstyle \wedge q) ∨ (¬p ∨ ¬q) (d) q \scriptstyle \wedge (p ∨ r) Solutions (a) ¬(¬p) is pretty obviously the same as p itself, but well still use the above method in this simple case, to show how it works, before moving on to more complicated examples. So: Step 1: Rows Theres just one input variable here, so we shall need two rows. Step 2: Blank Table So the table is: p ¬(¬p) . . Step 3: Input Values Next, we fill in the input values: just one T and one F in this case: p ¬(¬p) T F Step 4: Plan your strategy As in ordinary algebra we evaluate whatevers in brackets first, so we shall first (1) complete the (¬p) values, followed (2) by the left-hand ¬ symbol, which gives us the final output values of the whole expression. We rule an extra column to separate these two processes, and write the (1) and (2) at the foot of these two columns. Thus: p ¬ (¬p) T F (2) Output (1) Step 5: Work down the columns Finally we insert the values in column (1) – F followed by T – and then use these values to insert the values in column (2). So the completed truth table is: p ¬ (¬p) T T F F F T (2) Output (1) As we said at the beginning of this example, ¬(¬p) is clearly the same as p, so the pattern of the output values, T followed by F, is identical to the pattern of the input values. Although this may seem trivial, the same technique works in much more complex examples, where the results are far from obvious! (b) p \scriptstyle \wedge (¬q) Step 1 There are two input variables, p and q, so we shall need four rows in the table. Steps 2 & 3 In the q column write Ts and Fs alternating on every row; in the p column alternate every two rows. At this stage, the table looks like this: p q p \scriptstyle \wedge (¬q) T T T F F T F F Steps 4 & 5 As Example (a), we begin (1) by evaluating the expression in brackets, (¬q), and then (2) we combine these results with p using the \scriptstyle \wedge operator. So we divide the output section of the table into two columns; then work down column (1) and finally column (2). The completed table is: p q p \scriptstyle \wedge (¬q) T T F F T F T T F T F F F F F T (2) output (1) (c) (p \scriptstyle \wedge q) ∨ (¬p ∨ ¬q) Steps 1 to 3 As in Example (b). Steps 4 & 5 There will be 5 stages in evaluating the expression (p \scriptstyle \wedge q) ∨ (¬p ∨ ¬q). In order, they are: (1) The first bracket: (p \scriptstyle \wedge q) (2) The ¬p in the second bracket (3) The ¬q in the second bracket (4) The ∨ in the second bracket (5) The ∨ between the two brackets. This final stage, then, represents the output of the complete expression. Reminder: Dont work across the rows; work down the columns in order (1) to (5). That way, youll only have to deal with a single operation at a time. The completed table is: p q (p \scriptstyle \wedge q) ∨ (¬p ∨ ¬q) T T T T F F F T F F T F T T F T F T T T F F F F T T T T (1) (5) output (2) (4) (3) Notice that the output consist solely of Ts. This means that (p \scriptstyle \wedge q) ∨ (¬p ∨ ¬q) is always true whatever the values of p and q. It is therefore a tautology (see below). (d) q \scriptstyle \wedge (p ∨ r) This simple expression involves 3 input variables, and therefore requires 23 = 8 rows in its truth table. When drawing this truth table by hand, rule a line below row 4 as an aid to keeping your working neat. It is shown as a double line in this table. The completed table is shown below. p q r q \scriptstyle \wedge (p ∨ r) T T T T T T T F T T T F T F T T F F F T F T T T T F T F F F F F T F T F F F F F (2) output (1) Tautology An expression which always has the value true is called a tautology. In addition, any statement which is redundant, or idempotent, is also referred to as a tautology, and for the same reason previously mentioned. If P is True then we can be sure that P ∨ P is true, and P ∧ P is also true. Logic Exercise 2 Click link for Logic Exercise 2. Order of Precedence In ordinary algebra, the order of precedence in carrying out operations is: 1 brackets 2 exponents (powers) 3 × and ÷ 4 + and - In the algebra of logic, brackets will often be inserted to make clear the order in which operations are to be carried out. To avoid possible ambiguity, the agreed rules of precedence are: 1 brackets 2 NOT (¬) 3 AND (\scriptstyle \wedge) 4 OR (∨) So, for example, p ∨ q \scriptstyle \wedge r means: Evaluate q \scriptstyle \wedge r first. Then combine the result with p ∨. Since it would be easy to misinterpret this, it is recommended that brackets are included, even if they are not strictly necessary. So p ∨ q \scriptstyle \wedge r will often be written p ∨ (q \scriptstyle \wedge r). Logically Equivalent Propositions Look back to your answers to questions 2 and 3 in Exercise 2. In each question, you should have found that the last columns of the truth tables for each pair of propositions were the same. Whenever the final columns of the truth tables for two propositions p and q are the same, we say that p and q are logically equivalent, and we write: p ≡ q Example 5 Construct truth tables for (i) p ∨ (q \scriptstyle \wedge r), and (ii) (p ∨ q) \scriptstyle \wedge (p ∨ r), and hence show that these propositions are logically equivalent. Solution (i) p q r p ∨ (q \scriptstyle \wedge r) T T T T T T T F T F T F T T F T F F T F F T T T T F T F F F F F T F F F F F F F (2) output (1) (ii) p q r (p ∨ q) \scriptstyle \wedge (p ∨ r) T T T T T T T T F T T T T F T T T T T F F T T T F T T T T T F T F T F F F F T F F T F F F F F F (1) (3) output (2) The outputs in each case are T, T, T, T, T, F, F, F. The propositions are therefore logically equivalent. Example 6 Construct the truth table for ¬(¬p ∨ ¬q), and hence find a simpler logically equivalent proposition. Solution p q ¬ (¬p ∨ ¬q) T T T F F F T F F F T T F T F T T F F F F T T T (4) output (1) (3) (2) We recognise the output: T, F, F, F as the footprint of the AND operation. So we can simplify ¬(¬p ∨ ¬q) to p \scriptstyle \wedge q Laws of Logic Like sets, logical propositions form what is called a Boolean Algebra: the laws that apply to sets have corresponding laws that apply to propositions also. Namely: Commutative Laws p \scriptstyle \wedge q ≡ q \scriptstyle \wedge p p ∨ q ≡ q ∨ p Associative Laws (p \scriptstyle \wedge q) \scriptstyle \wedge r ≡ p \scriptstyle \wedge (q \scriptstyle \wedge r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Distributive Laws p \scriptstyle \wedge (q ∨ r) ≡ (p \scriptstyle \wedge q) ∨ (p \scriptstyle \wedge r) p ∨ (q \scriptstyle \wedge r) ≡ (p ∨ q) \scriptstyle \wedge ( p ∨ r) Idempotent Laws p \scriptstyle \wedge p ≡ p p ∨ p ≡ p Identity Laws p \scriptstyle \wedge F ≡ F p ∨ F ≡ p p \scriptstyle \wedge T ≡ p p ∨ T ≡ T Involution Law ¬(¬p) ≡ p De Morgan’s Laws ¬(p ∨ q) ≡ (¬p) \scriptstyle \wedge (¬q) (sometimes written p NOR q) ¬(p \scriptstyle \wedge q) ≡ (¬p) ∨ (¬q) (sometimes written p NAND q) Complement Laws p \scriptstyle \wedge ¬p ≡ F p ∨ ¬p ≡ T ¬T ≡ F ¬F ≡ T Worked Examples Example 7 Propositional functions p, q and r are defined as follows: p is n = 7 q is a > 5 r is x = 0 Write the following expressions in terms of p, q and r, and show that each pair of expressions is logically equivalent. State carefully which of the above laws are used at each stage. (a) ((n = 7) ∨ (a > 5)) \scriptstyle \wedge (x = 0) ((n = 7) \scriptstyle \wedge (x = 0)) ∨ ((a > 5) \scriptstyle \wedge (x = 0)) (b) ¬((n = 7) \scriptstyle \wedge (a ≤ 5)) (n ≠ 7) ∨ (a > 5) (c) (n = 7) ∨ (¬((a ≤ 5) \scriptstyle \wedge (x = 0))) ((n = 7) ∨ (a > 5)) ∨ (x ≠ 0) Solutions (a) (p ∨ q) \scriptstyle \wedge r (p \scriptstyle \wedge r) ∨ (q \scriptstyle \wedge r) (p ∨ q) \scriptstyle \wedge r = r \scriptstyle \wedge (p ∨ q) Commutative Law = (r \scriptstyle \wedge p) ∨ r \scriptstyle \wedge q) Distributive Law = (p \scriptstyle \wedge r) ∨ (q \scriptstyle \wedge r) Commutative Law (twice) (b) First, we note that ¬q is a ≤ 5; and ¬p is n ≠ 7. So the expressions are: ¬(p \scriptstyle \wedge ¬q) ¬p ∨ q ¬(p \scriptstyle \wedge ¬q) = ¬p ∨ ¬(¬q) De Morgans Law = ¬p ∨ q Involution Law (c) First, we note that ¬r is x ≠ 0. So the expressions are: p ∨ (¬(¬q \scriptstyle \wedge r)) (p ∨ q) ∨ ¬r p ∨ (¬(¬q \scriptstyle \wedge r)) = p ∨ (¬(¬q) ∨ ¬r) De Morgans Law = p ∨ (q ∨ ¬r) Involution Law = (p ∨ q) ∨ ¬r Associative Law
Posted on: Tue, 05 Aug 2014 10:00:21 +0000
Trending Topics
Recently Viewed Topics
© 2015