CmpE 104: Lesson 9 :The Logic of Compound Statements CmpE 104: Lesson 9


Slide 2:The first great treatises on logic were written by the Greek philosopher Aristotle. They were a collection of rules for deductive reasoning that were intended to serve as a basis for the study of every branch of knowledge. In the seventeenth century, the German philosopher and mathematician Gottfried Leibnitz conceived the idea of using symbols to mechanize the process of deductive reasoning in much the same way that algebraic notation had mechanized the process of reasoning about numbers and their relationships.


Slide 3:Leibnitz’s idea was realized in the nineteenth century by the English mathematicians George Boole and Augustus De Morgan, who founded the modern subject of symbolic logic. Symbolic logic has provided, among other things, the theoretical basis for many years of computer science such as digital logic circuit design, relational database theory, automata theory and computability, and artificial intelligence.


LOGICAL FORM AND LOGICAL EQUIVALANCE :LOGICAL FORM AND LOGICAL EQUIVALANCE The central concept of deductive logic is the concept of argument form. An argument is a sequence of statements aimed at demonstrating the truth of an assertion. To have confidence in the conclusion that you draw from an argument, you must be sure that the statements composing it either are acceptable on their own merits or follow from preceding statements. In logic, the form of an argument is distinguished from its content.


LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. :LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. Logical analysis won’t help you determine the intrinsic merit of an argument’s content, but it will help you analyze an argument’s form to determine whether the truth of the conclusion follows necessarily from the truth of the preceding statements. For this reason logic is sometimes defined as the science of necessary inference or the science of reasoning.


LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. :LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. Consider the following two arguments: If the program syntax is faulty or if program execution results in division by zero, then the computer will generate an error message. Therefore, if the computer does not generate an error message, then the program syntax is correct and program execution does not result in division by zero. If x is real number such that x 2, then x2 > 4. Therefore, if x2 ≤ 4, then x ≥ -2 and x ≤ 2.


LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. :LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. The content of these arguments is very different. Nevertheless, their logic form is the same. To illustrate the logical form we use letters of the alphabet (such as p, q, and r) to represent the component sentences and the expression. Then the common form of both the arguments above is as follows: If p or q, then r. Therefore, if not r, then not p and not q.


LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. :LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. Most of the definitions of formal logic have been developed so that they agree with the natural or intuitive logic used by people. The differences that exist between formal and intuitive logic are necessary to avoid ambiguity and obtain consistency. In any mathematical theory, new terms are defined by using those that have been previously defined. However, this process has to start somewhere. A few initial terms necessarily remain undefined. In logic, the words sentence, true, and false are the initial undefined terms.


DEFINITION :DEFINITION A statement (or proposition) is a sentence that is true or false but not both.


LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. :LOGICAL FORM AND LOGICAL EQUIVALANCE cont…. For example, “Two plus two equals four” and “Two plus two equals five” and both statements. On the other hand, the truth or falsity of “He is a college student” depends on the reference for the pronoun he. For some values of he the sentence is true; for others it is false. However, the sentence is neither true nor false, and so it is not a statement. Similarly “x + y > 0” is not a statement because for some values of x and y the sentence is true, whereas for others it is false.


COMPOUND STATEMENTS :COMPOUND STATEMENTS We now introduce three symbols that are used to build more complicated logical expressions out of simpler ones. The symbol ~ denotes not,  denotes and, and V denotes or. The sentence “~p” is read “not p” and is called the negation of p. The sentence “p  q” is read “p and q” and is called the conjunction of p and q.


COMPOUND STATEMENTS :COMPOUND STATEMENTS The sentence “p V q” is read “p or q” and is called the disjunction of p and q. In expressions that include the symbol ~ as well as  or V, the order of operation is that ~ is performed first. ~p  q = (~p)  q. The order of operations can be overridden through the use of parentheses


COMPOUND STATEMENTS :COMPOUND STATEMENTS The symbols  and V are considered coequal in order of operation. An expression such as p  q V r is considered ambiguous. This expression must be written as either (p  q) V r or p  (q V r) to have meaning.


Translating from English to Symbols: :Translating from English to Symbols: But and Neither-Nor Write each of the following sentences symbolically, letting p = “it is hot” and q = “It is sunny.” a. It is not hot but it is sunny. b. It is neither hot nor sunny.


Translating from English to Symbols: cont… :Translating from English to Symbols: cont… The words but and and mean the same thing. Generally, but is used in place of and. “It is not hot and it is sunny,” which can be written symbolically as ~ p  q. The phrase neither A nor B means the same as not A and not B. The given sentence can be written symbolically as ~p  ~q.


Translating from English to Symbols: cont… :Translating from English to Symbols: cont… The notation for inequalities involves and and or statements. x ≤ a means x < a or x = a a ≤ x ≤ b means a ≤ x and x ≤ b


Slide 17:If such sentences are to be statements, however, they must have well-defined truth values-they must be either true or false.


Negations of And and Or: De Morgan’s Laws :Negations of And and Or: De Morgan’s Laws ~(p  q)  ~p V ~q ~(p V q)  ~p  ~q


Inequalities and De Morgan’s Laws :Inequalities and De Morgan’s Laws Use De Morgan’s laws to write the negation of -1 < x ≤ 4.


Inequalities and De Morgan’s Laws cont…. :Inequalities and De Morgan’s Laws cont…. The given statement is equivalent to -1 4


A Cautionary Example :A Cautionary Example The negation of p: Jim is tall and Jim is thin is ~p: Jim is not tall or Jim is not thin Note that statement p can be written more compactly as p/: Jim is tall and thin Another way to negate it is ~(p/): Jim is not tall and thin.


Slide 22:Doesn’t that violate De Morgan’s laws? The reason is that in formal logic the words and and or are allowed only between complete statements, not between sentence fragments.


TAUTOLOGIES AND CONTRADICTIONS :TAUTOLOGIES AND CONTRADICTIONS DEFINITION A tautology is a statement from that is always true regardless of the truth values of the individual statements substituted for its statement variables. A statement whose form is a tautology is called a tautological statement. A contradiction is a statement from that is always false regardless of the truth values of the individual statements substituted for its statement variables. A statement whose form is a contradiction is called a contradictory statement


Tautologies and Contradictions :Tautologies and Contradictions Show that the statement form p V ~p is a tautology and that the statement form p  ~p is a contradiction.


Simplifying Statement Forms :Simplifying Statement Forms Verify the logical equivalence ~(~p  q)  (p V q)  p.


CONDITIONAL STATEMENTS :CONDITIONAL STATEMENTS Let p and q be statements. A sentence of the form “If p then q” is denoted symbolically by “p  q”; p is called the hypothesis and q is called the conclusion. DEFINITION If p and q are statement variables, the conditional of q by p is “If p then q” or “p implies q” and is denoted p  q It is false when p is true and q is false; otherwise it is true.


CONDITIONAL STATEMENTS cont… :CONDITIONAL STATEMENTS cont… In expressions that include  as well as other logical operators such as , V, and ~, the order of operations is that  is performed last, ~ is performed first, then  and V, and finally .


Slide 28:Truth Table for p V ~q  ~p


LOGICAL EQUIVALENCES INVOLVING -> :LOGICAL EQUIVALENCES INVOLVING -> Showing that p V q  r  (p  r)  (q  r)


REPRESENTATION OF IF-THEN AS OR :REPRESENTATION OF IF-THEN AS OR p  q  ~p V q The logical equivalence of “if p then q” and “not p or q” is used only occasionally in everyday speech.


REPRESENTATION OF IF-THEN AS OR cont…. :REPRESENTATION OF IF-THEN AS OR cont…. Rewrite the following statement in if-then form. Either you get to work on time or you are fired.


REPRESENTATION OF IF-THEN AS OR cont…. :REPRESENTATION OF IF-THEN AS OR cont…. Let ~p be You get to work on time. and q be You are fired. Also p is You do not get to work on time. So the equivalent if-then version, p  q, is If you do not get to work on time, then you are fired.


The Negation of a Conditional Statement :The Negation of a Conditional Statement The negation of “if p then q” is logically equivalent to “p and not q.” This can be restated symbolically as follows: ~(p  q)  p  ~q ~(p  q)  ~(~p  q)  ~(~p)  (~q) by De Morgan’s Laws  p  ~q by the double negative law


THE CONTRAPOSITIVE OF A CONDITIONAL STATEMENT :THE CONTRAPOSITIVE OF A CONDITIONAL STATEMENT One of the most fundamental laws of logic is the equivalence between a conditional statement and its contrapositive. Definition: The contrapositive of a conditional statement of the form “If p then q” is If ~q then ~p. Symbolically, The contrapositive of p  q is ~q  ~p.


THE CONTRAPOSITIVE OF A CONDITIONAL STATEMENT :THE CONTRAPOSITIVE OF A CONDITIONAL STATEMENT A conditional statement is logically equivalent to its contrapositive.


Writing the contrapositive :Writing the contrapositive If Howard can swim across the lake, then Howard can swim to the island. If Howard cannot swim to the island, then Howard cannot swim across the lake. When you are trying to solve the certain problems, you may find that the contrapositive form of a conditional statement is easier to work with than the original statement.


THE CONVERSE AND INVERSE OF A CONDITIONAL STATEMENT :THE CONVERSE AND INVERSE OF A CONDITIONAL STATEMENT Two other variants of a conditional statement are not logically equivalent to the statement.


THE CONVERSE AND INVERSE OF A CONDITIONAL STATEMENT :THE CONVERSE AND INVERSE OF A CONDITIONAL STATEMENT Definition: Suppose a conditional statement of the form “If p then q” is given. 1. The converse is “If q then p.” 2. The inverse is “If ~p then ~q.” Symbolically, The converse of p  q is q  p. and The inverse of p  q is ~ p  ~q.


Writing the Converse and the Inverse :Writing the Converse and the Inverse If Howard can swim across the lake, then Howard can swim to the island. converse: If Howard can swim to the island, then Howard can swim across the lake. inverse: If Howard cannot swim across the lake, then Howard cannot swim to the island. If a conditional statement is true, then its converse and inverse may or may not be true.


The converse and inverse of a conditional statement :The converse and inverse of a conditional statement 1. A conditional statement and its converse are not logically equivalent. 2. A conditional statement and its inverse are not logically equivalent. 3. The converse and the inverse of a conditional statement are logically equivalent to each other.


ONLY IF AND THE BICONDITIONAL :ONLY IF AND THE BICONDITIONAL To say “p only if q” means that p can take place only if q takes place also. Another way to say this is that if p occurs, then q must also occur (by the logical equivalence between a statement and its contrapositive).


ONLY IF AND THE BICONDITIONAL :ONLY IF AND THE BICONDITIONAL Definition: If p and q are statements, p only if q means “if not q then not p,” or, equivalently, “if p then q.”


Order of Operations :Order of Operations ~ , V , 


If and Only If :If and Only If Rewrite the following statement as a conjunction of two if-then statements: This computer program is correct if, and only if, it produces the current answer for all possible sets of input data


If and Only If :If and Only If If this program is correct, then it produces the correct answers for all possible sets of input data; and if this program produces the correct answers for all possible sets of input data, then it is correct. p  q  (~p V q)  (~q V p)


NECESSARY AND SUFFICIENT CONDITIONS :NECESSARY AND SUFFICIENT CONDITIONS DEFINITION If r and s are statements: r is a sufficient condition for s means “if r then s” r is a necessary condition for s means “if not r then not s.”


NECESSARY AND SUFFICIENT CONDITIONS cont…. :NECESSARY AND SUFFICIENT CONDITIONS cont…. r is a necessary condition for s also means “if s then r.” r is a necessary and sufficient condition for s means “r if, and only if, s.”


Interpreting Necessary and Sufficient Conditions :Interpreting Necessary and Sufficient Conditions Consider the statement “If John is eligible to vote, then he is at least 18 years old.” The truth of the condition “John is eligible to vote” is sufficient to ensure the truth of the condition “John is at least 18 years old.” In addition, the condition “John is at least 18 years old” is necessary for the condition “John is eligible to vote” to be true. If John were younger than 18, then he would not be eligible to vote.


VALID AND INVALID ARGUMENTS :VALID AND INVALID ARGUMENTS In mathematics and logic an argument is not a dispute. It is a sequence of statements ending in a conclusion. In this section we show how to determine whether an argument is valid, that is, to determine whether the conclusion follows necessarily from the preceding statements.


VALID AND INVALID ARGUMENTS cont…. :VALID AND INVALID ARGUMENTS cont…. DEFINITION An argument is a sequence of statements. All statements but the final one are called premises (or assumptions or hypotheses). The final statement is called the conclusion. The symbol , read “therefore,” is normally placed just before the conclusion.


VALID AND INVALID ARGUMENTS cont…. :VALID AND INVALID ARGUMENTS cont…. If Socrates is a human being, then Socrates is mortal; Socrates is a human being;  Socrates is mortal; has the abstract form If p then q; p;  q.


VALID AND INVALID ARGUMENTS cont…. :VALID AND INVALID ARGUMENTS cont…. DEFINITION To say that an argument form is valid means that no matter what particular statements are substituted for the statement variables in the premises, if the resulting premises are all true, then the conclusion is also true. To say that an argument is valid means that its form is valid.


A Valid Argument Form :A Valid Argument Form Show that the following argument form is valid: p V (q V r) ~r  p V q


An Invalid Argument Form :An Invalid Argument Form Show that the following argument form is invalid. p  q V ~r q  p  r p  r


MODUS PONENS AND MODUS TOLLENS :MODUS PONENS AND MODUS TOLLENS Consider the following argument form: If p then q. p q Here is an argument of this form. If the last digit of this number is a 0, then this number is divisible by 10. The last digit of this number is a 0. This number is divisible by 10.


MODUS PONENS AND MODUS TOLLENS cont…. :MODUS PONENS AND MODUS TOLLENS cont…. The fact that this argument form is valid is called modus ponens. The term modus ponens is Latin meaning “methos of affirming” Now consider this argument form: If p then q. ~q  ~p


MODUS PONENS AND MODUS TOLLENS cont…. :MODUS PONENS AND MODUS TOLLENS cont…. If Zeus is human, then Zeus is mortal. Zeus is not mortal. Zeus is not human. The fact that this argument form is valid is called modus tollens. Modus tollens is Latin meaning “methos of denying” (since the conclusion is a denial).


ADDITIONAL VALID ARGUMENT FORMS :ADDITIONAL VALID ARGUMENT FORMS Disjunctive Addition The following argument forms are valid: a. p b. q p V q p V q These argument forms are used for making generalizations. For instance, according to the first, if p is true, then, more generally, “p or q”


Conjunctive Simplification :Conjunctive Simplification The following argument forms are valid: a. p  q b. p  q p q These argument forms are used for particularizing. For instance, the first says that if both p and q are true, then, in particular, p is true.


Disjunctive Syllogism :Disjunctive Syllogism The following argument forms are valid: a. p V q b. p V q ~q ~p p q These argument forms say that when you have only two possibilities and you can rule one out.


Hypothetical Syllogism :Hypothetical Syllogism The following argument form is valid: p  q q  r p  r


Slide 62:The logic of Quantifies Statements


Slide 63:In Chapter 1 we discussed the logic analysis of compound statements – those made of simple statements joined by the connectives ~, , V, , and . It cannot be used to determine validity in the majority of everyday and mathematical situations. For example, the argument All human beings are mortal Socrates is a human being  Socrates is mortal is intuitively perceived as correct. Yet its validity cannot be derived using the methods outlined


Slide 64:To determine validity in examples like this, it is necessary to separate the statements into parts in much the same way that you separate declarative sentences into subjects and predicates. And you must analyze and understand the special role played by words that denote quantities such as “all” or “some.” The symbolic analysis of predicates and quantified statements is called the predicate calculus.


Slide 65:The symbolic analysis of ordinary compound statements (as outlined in Sections 1.1-1.3) is called the statement calculus (or the propositional calculus).


PREDICATES AND QUANTIFIED STATEMENTS I :PREDICATES AND QUANTIFIED STATEMENTS I The sentence “He is a college student” is not a statement because it may be either true or false depending on the value of the pronoun he. In grammar, the word predicate refers to the part of a sentence that gives information about the subject. In the sentence “James is a student at Bedford College,” the word James is the subject and the phrase is a student at Bedford College is the predicate. In logic, predicates can be obtained by removing any nouns from a statement.


PREDICATES AND QUANTIFIED STATEMENTS I :PREDICATES AND QUANTIFIED STATEMENTS I For instance, let P stand for the words “is a student at Bedford College” and let Q stand for the words “is a student at.” Then both P and Q are predicate symbols. The sentences “x is a student at Bedford College” and “x is a student at y” are symbolized as P(x) and as Q(x,y) respectively, where x and y are predicate variables that take values in appropriate sets. When concrete values are substituted in place of predicate variables, a statement results.


DEFINITION :DEFINITION A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable.


DEFINITION :DEFINITION If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements of D that make P(x) true when substituted for x. the truth set of P(x) is denoted {x  D | P(x)} the set of all such that which is read “the set of all x in D such that P(x).”


NOTATION :NOTATION Let P(x) and Q(x) be predicates and suppose the common domain of x is D. the notion P(x)  Q(x) means that every element in the truth set of P(x) is in the truth set of Q(x). The notion P(x)  Q(x) means that P(x) and Q(x) have identical truth sets.


QUANTIFIERS:  and  :QUANTIFIERS:  and  The formal concept of quantifier was introduced into symbolic logic in the late nineteenth century by the American philosopher, logician, and engineer Charles Sanders Peirce and, independently, by the German logician Gottlob Frege. The symbol  denotes “for all” and is called the universal quantifier.  human beings x, x is mortal, or, more formally,  x  S, x is mortal.


QUANTIFIERS:  and  cont… :QUANTIFIERS:  and  cont… Some other expressions that can be used instead of for all are for every, for arbitrary, for any, for each, and given any.


DEFINITION :DEFINITION Let Q(x) be a predicate and D the domain of x. A universal statement is a statement of the form “x  D,Q(x).” It is defined to be true if, and only if Q(x) is true for every x in D. It is defined to be false if, and only if, Q(x) is false for at least one x in D. A value for x for which Q(x) is false is called a counterexample to the universal statement.