Logic 1 Statements In any mathematical theory new terms are defined by using those that have been previously defined However this process has to start somewhere In logic the words statements true and false are the initial undefined terms Definition A statement or proposition is a sentence that is true or false but not both 5 Compound Statements We now introduce three symbols that are used to build more complicated logical expressions out of simpler ones denotes not Given a statement p the sentence p is read not p or It is not the case that p and is called the negation of p denotes and Given another statement q the sentence p q is read p and q and is called the conjunction of p and q denotes or The sentence p q is read p or q and is called the disjunction of p and q 6 Compound Statements In expressions that include the symbol as well as or the order of operations specifies that is performed first In other words has higher precedence than and For instance p q p q 7 Compound Statements In logical expressions as in ordinary algebraic expressions the order of operations can be overridden through the use of parentheses Thus p q represents the negation of the conjunction of p and q In this as in most treatments of logic the symbols and are considered coequal in order of operation and an expression such as p q r is considered ambiguous This expression must be written as either p q r or p q r to have meaning 8 Example 2 Translating from English to Symbols But and Neither Nor Write each of the following sentences symbolically letting h It is hot and s It is sunny a It is not hot but it is sunny b It is neither hot nor sunny Solution a The given sentence is equivalent to It is not hot and it is sunny which can be written symbolically as h s b To say it is neither hot nor sunny means that it is not hot and it is not sunny Therefore the given sentence can be written symbolically as h s 9 Statement Form Statement Form an expression made up of abstract statement variables p q r etc and logical connectives etc Statement Form p q Statement It is not hot and it is sunny Statement p q where p It is hot and q It is sunny Truth table for statement forms all combinations of truth values for statement variables 11 Truth Table Truth Table for p Truth Table for p q Truth Table for p q 12 Example 4 Truth Table for Exclusive Or Construct the truth table for the statement form p q p q Note that when or is used in its exclusive sense the statement p or q means p or q but not both or p or q and not both p and q which translates into symbols as p q p q This is sometimes abbreviated 13 Logical Equivalence 16 Logical Equivalence The statements 6 is greater than 2 and 2 is less than 6 are two different ways of saying the same thing Why Because of the definition of the phrases greater than and less than By contrast although the statements 1 Dogs bark and cats meow and 2 Cats meow and dogs bark are also two different ways of saying the same thing the reason has nothing to do with the definition of the words 17 Logical Equivalence It has to do with the logical form of the statements Any two statements whose logical forms are related in the same way as 1 and 2 would either both be true or both be false You can see this by examining the following truth table where the statement variables p and q are substituted for the component statements Dogs bark and Cats meow respectively 18 Logical Equivalence The table shows that for each combination of truth values for p and q p q is true when and only when q p is true In such a case the statement forms are called logically equivalent and we say that 1 and 2 are logically equivalent statements 19 Logical Equivalence Testing Whether Two Statement Forms P and Q Are Logically Equivalent 1 Construct a truth table with one column for the truth values of P and another column for the truth values of Q 20 Logical Equivalence 2 Check each combination of truth values of the statement variables to see whether the truth value of P is the same as the truth value of Q a If in each row the truth value of P is the same as the truth value of Q then P and Q are logically equivalent b If in some row P has a different truth value from Q then P and Q are not logically equivalent 21 p Example 6 Double Negative Property p Construct a truth table to show that the negation of the negation of a statement is logically equivalent to the statement annotating the table with a sentence of explanation Solution 22 Logical Equivalence There are two ways to show that statement forms P and Q are not logically equivalent 1 Use a truth table to find rows for which their truth values differ 2 Find concrete statements for each of the two forms one of which is true and the other of which is false The next example illustrates both of these ways 23 Example 7 Showing Nonequivalence Show that the statement forms p q and p q are not logically equivalent Solution a This method uses a truth table annotated with a sentence of explanation 24 Example 7 Solution cont d b This method uses an example to show that p q and p q are not logically equivalent Let p be the statement 0 1 and let q be the statement 1 0 Then which is true On the other hand which is false 25 Example 7 Solution cont d This example shows that there are concrete statements you can substitute for p and q to make one of the statement forms true and the other false Therefore the statement forms are not logically equivalent 26 Logical Equivalence The following two logical equivalences are known as De Morgan s laws 27 Example 9 Applying De Morgan s Laws Write negations for each of the following statements a John is 6 feet tall and he weighs at least 200 pounds b The bus was late or Tom s watch was slow Solution a John is not 6 feet tall or he weighs less than 200 pounds b The bus was not late and Tom s watch was not slow Since the statement neither p nor q means the same as p and q an alternative answer for b is Neither was the bus late nor was Tom s watch slow 28 Example 11 A Cautionary Example According to De Morgan s laws the negation of p Jim is tall and Jim is thin is p Jim is not tall or Jim is not thin because the negation of …
View Full Document