Propositions - Math Study Guide

PROPOSITIONS Definition. A proposition is a declarative sentence that is either true or false, but not both. EXAMPLES OF PROPOSITIONS Examples. The following sentences are propositions. 1. Houston is located in Harris County. 2. San Antonio is the capital of Texas. 3. 2  2  4. 4. 2  1  5. Propositions 1 and 3 are true, while 2 and 4 are false. NOT ALL SENTENCES ARE PROPOSITIONS Examples.The following sentences are not propositions. 1. Is the sun shining? 2. Work Problems 4 and 5 at the end of Section 3. 3. Turn in your paper now! 4. x  2  7. Interrogative, imperative and exclamatory sentences are not propositions. As it stands, Sentence 4 is not a proposition. It becomes a proposition if the value of x is known. Of course it is true if x  5, otherwise it is false. TRUTH VALUE Definition. True propositions are said to have truth value TRUE, denoted by T. False propositions are said to have truth value FALSE, denoted by F. EXAMPLE PROBLEM Problem. Which of the following sentences are propositions? What is the truth value of those that are propositions? 1. Stop at the stop sign. 2. When will class be over? 3. 3  x  7. 4. If x  1 then x  1  5. 5. If x  z then x  y  z  y. COMPOUND PROPOSITIONS Propositions that are simple declarative sentences are called elementary or atomic propositions. Logical operators are used to from compound propositions out of elementary ones. The study of these compounds and how their truth value is determined by the truth values of their constituent parts is known as propositional calculus or propositional logic. NEGATION Definition. The operation of negation is defined as follows: When p is a proposition, the negation of p is denoted by p and is read literally, ”It is not the case that p” or briefly, ”not p. ” The negation of p has the opposite truth value from p. If p is true, then p is false. If p is false, then p is true. The negation of p is also denoted by  p. EXAMPLES Examples of negation. Proposition: The earth is round. Negation: It is not the case that the earth is round. Negation in simple English: The earth is not round. Proposition: A square has five sides. Negation: It is not the case that a square has five sides. Negation in simple English: A square does not have five sides. EXAMPLES Examples of negation. Proposition: Every student in the class made 100% on the exam. Negation: It is not the case that every student in the class made 100% on the exam. Negation in simple English: Some student in the class did not make 100% on the exam. Notice that ’Every’ goes over to ’Some’ in the negation. Proposition: John’s time for the race was less than  seven seconds. Negation: It is not the case that John’s time for the race was less than  seven seconds. Negation in simple English: John’s time for the race was seven or more  seconds. Note that ’was less than’ goes over to  was or was greater than’ in the negation. TRUTH TABLE A truth table for a compound proposition shows its truth value for each choice of truth values for its atomic constituents. TRUTH TABLE FOR NEGATION Truth Table for Negation (NOT p) p p T F F T CONJUNCTION Definition. The operation of conjunction is defined as follows: When each of p and q is a proposition, the conjunction of p and q is denoted by p  q and is read, ”p and q.  The conjunction of p and q is true only when each of p and q is true. TRUTH TABLE FOR CONJUNCTION Truth Table for Conjunction (p AND q) p q pq T T T T F F F T F F F F EXAMPLE Suppose that p is, ”The earth is round," and q is, ”3  5  7. ” Then p  q is, ”The earth is round and 3  5  7.” Here p true and q is false so p  q is false. THE WORD ’OR’ IN ENGLISH Note. In English the word ’or’ is used in two different ways. When used in the inclusive sense, A or B means A or B or both. When used in the exclusive sense, A or B means A or B but not both. Example. Saying that the prerequisite is Calculus I or Computer Science I is an example of the inclusive or. Example. Saying that you should wear a white shirt or a blue shirt is an example or the exclusive or. Note. In mathematics, or is the inclusive or unless it is qualified by ’but not both.’ DISJUNCTION Definition. The operation of disjunction is defined as follows: When each of p and q is a proposition, the disjunction of p and q is denoted by p  q and is read ”p or q.” It means p or q or both, so this is the inclusive or. p  q is true unless each of p and q is false, in which case p  q is false. TRUTH TABLE FOR DISJUNCTION Truth Table for Disjunction (p OR q) p q pq T T T T F T F T T F F F THE EXCLUSIVE OR Although used less frequently, there is a symbol for the exclusive or. When each of p and q is a proposition, the exclusive or of p and q is denoted by p  q and is read ”p or q but not both.” It is true when only one of p and q is true. Otherwise, it is false. TRUTH TABLE FOR THE EXCLUSIVE OR Truth Table for the Exclusive Or (p OR q BUT NOT BOTH) p q pq T T F T F T F T T F F F THE CONDITIONAL Definition. When each of p and q is a proposition, the conditional with hypothesis p and conclusion q is denoted by p  q and is read “p implies q” or “if p then q. ” By definition, the conditional statement p  q is false when p is true and q is false. Otherwise, p  q is true. TRUTH TABLE FOR THE CONDITIONAL Truth Table for the Conditional Statement p  q p q pq T T T T F F F T T F F T Note. The truth or falsity of a p  q statement is determined by the truth table - not by your intuition. Note that p  q is always true when p is false. Note. Unlike in common English usage, in propositional logic, there need not be any connection between the hypothesis and conclusion in a conditional statement. EXAMPLES Example. “If 2  3  5, then the sky is blue.” is a true conditional statement. The hypothesis is true and the conclusion is true. Example. “If 2  3  6, then the sky is green.” is a true conditional statement. The hypothesis is false and the conclusion is false. Example.“If 2  3  5, then the sky is green.” is a false conditional statement. The hypothesis is true and the conclusion is false. Example. “If 2  3  6, then the sky is blue.” is a true conditional statement. The hypothesis is false and the conclusion is true. OTHER WAYS TO EXPRESS THE CONDITIONAL Note. In addition to “if p, then q  and “p implies q  , here are some other ways to express p  q. “if p, q” “p only if q” “p is sufficient for q” “a sufficient condition for q is p” “q if p” “q whenever p” “q when p” “q is necessary for p” “a necessary condition for p is q” “q follows from p  “q unless p” “q provided that p” See pages 7, 8, and 9, of the text for additional remarks about the conditional in propositional logic and usage in the English language and in programming languages. CONVERSE, INVERSE, AND CONTRAPOSITIVE Definition. Related to the conditional statement p  q is its converse, q  p, its inverse, p  q, and its contrapositive, q  p. Example. For the conditional statement “If the sun is shining, then he wears a hat.” the converse is “If he wears a hat, then the sun is shining.” the inverse is “If the sun is not shining, then he does not wear a hat.” and the contrapositive is “If he does not wear a hat, then the sun is not shining.” CONVERSE, INVERSE, CONTRAPOSITIVE, AND PROPOSITIONAL EQUIVALENCE Definition. Saying that two propositions are logically equivalent means that they have the same truth value for each possible assignment of truth values to their elementary constituents. Note. Here are the truth tables for p  q and q  p. p q pq p q q p q  p T T T T T F F T T F F T F T F F F T T F T F T T F F T F F T T T As you can see from the last columns in the two tables, p  q and q  p are logically equivalent. CONVERSE, INVERSE, CONTRAPOSITIVE, AND PROPOSITIONAL EQUIVALENCE Note. Here are the truth tables for q  p and p  q. p q qp p q p q p  q T T T T T F F T T F T T F F T T F T F F T T F F F F T F F T T T As you can see from the last columns in the two tables, q  p and p  q are logically equivalent. CONVERSE, INVERSE, CONTRAPOSITIVE, AND PROPOSITIONAL EQUIVALENCE Note. Here are the truth tables for p  q and q  p. p q pq p q qp T T T T T T T F F T F T F T T F T F F F T F F T As you can see from the last columns in the two tables, p  q and q  p are NOT logically equivalent. It is a common error to confuse a conditional statement with its converse. THE BICONDITIONAL Definition. When each of p and q is a proposition, the biconditional between p and q is denoted by p  q and is read “p if and only if q. ” The biconditional is also read “p is necessary and sufficient for q.  By definition, p  q is true when p and q have the same truth value and false when they have opposite truth values. TRUTH TABLE FOR THE BICONDITIONAL Truth Table for the Biconditional Statement p  q p q pq T T T T F F F T F F F T THE BICONDITIONAL .As we will see in Section 1.3, p  q is logically equivalent to p  q  q  p. In English, the “if and only if ” construction is sometimes expressed by an “if, then” or an “only if” construction with the other part being implied but not stated explicitly. In the statement “If you finish your meal, then you can have desert.” the intent is “You can have desert if and only if you finish your meal.” In propositional logic and in mathematics, we will always distinguish between the implication and the biconditional. We have the symbolism and terminology that makes this easy to do. TRUTH TABLES As noted earlier, a truth table for a compound proposition shows its truth value for each choice of truth values for its atomic constituents. For sake of consistency, construct the truth table in the following way. If there are only two atomic propositions, p and q, let the first two columns be: p q T T T F . F T F F TRUTH TABLES If there are only three atomic propositions, p, q, and r, let the first three columns be: p q r T T T T T F T F T T F F F T T F T F F F T F F F If there are exactly n atomic propositions, the truth table will have 2 n rows. The first column will have 2 n1 T’s followed by 2 n1 F’s. The second column will have 2 n2 T’s followed by 2 n2 F’s followed by 2 n2 T’s followed by 2 n2 F’s, et cetera. The n-th column will have 2 n1 copies of T followed by F. TRUTH TABLES Truth values for the given compound proposition are usually placed in the last column. Columns for intermediate compounds, if any, are placed between those for the elementary atomic propositions and the last column. TRUTH TABLE EXAMPLE Example Problem. Construct a truth table for p  q  p  q. Solution. There are only two elementary atomic propositions p, and q so there will be 2 2  4 rows. The first column will be headed by p, the second by q, and the last by p  q  p  q. Looking at p  q  p  q, we see that we will need a column for p  q and a column for p  q. Looking at p  q we see that we will need a column for q. Thus the framework for the table is as follows. p q q p  q p  q p  q  p  q TRUTH TABLE EXAMPLE As noted earlier, we begin with p q q p  q p  q p  q  p  q T T . T F F T F F TRUTH TABLE EXAMPLE Continuing,we have p q q p  q p  q p  q  p  q T T F T T T T F T F T T F T F F F T F F T F T T .. The compound proposition p  q  p  q is always true. It is an example of a tautology . There will be more about this and related concepts in Section 1.3. PRECEDENCE OF LOGICAL OPERATORS The precedence of the logical operators which have been defined is given in the following table. Operator Precedence  1  2  3  4  5 PRECEDENCE OF LOGICAL OPERATORS Unless directed otherwise by parentheses, operators with higher precedence are applied before operators with lower precedence Examples. p  q means r  q where r is p while p  q means r where r is p  q. p  q  r means s  r where s is p  q while p  q  r means p  s where s is q  r. PRECEDENCE OF LOGICAL OPERATORS Note. Parentheses may be used for clarity even when they are not required by the rules of precedence Example. p  q  r  s is easier to understand if it is written p  q  r  s. BITS Note. In some applications, 1 is used for the truth value of a true proposition and 0 for a false one. This is the case in some computer programing and Boolean Algebra.