Introduction to Logical Terminology, Notation, and Proof Structure

    Mark Barsamian, Ohio University

    I: Statements, Predicates, Logical Equivalence

    A statement \( S \) is a sentence that can be true or false

    • For example, the sentence "March has 31 days" is a true statement.
    • For example, the sentence "June has 31 days" is a false statement.

    A predicate \( P(x) \) is a sentence that contains a variable \( x \) that can be chosen from some domain set \( D \) such that once a value of \( x \) is chosen, \( P(x) \) becomes a statement that is either true or false.

    • For example, the sentence "\( x \) has 31 days" is a predicate with domain \( D \) the set of months. This predicate could be denoted \( P(x) \). It is neither true nor false, because we don't know the value of \( x \). Observe that \( P(March) \) is a true statement, while \( P(June) \) is a false statement.

    Often, two predicates can look different but actually have same truth value. That is the idea of logical equivalence . Here is the definition:

    Definition of logical equivalence

    • symbol: \( P(x) \equiv Q(x) \)
    • spoken: \( P(x) \) is logically equivalent to \( Q(x) \)
    • usage: \( P(x) \) and \( Q(x) \) are predicates with variable \( x \) and domain \( D \)
    • meaning: \( P(x) \) and \( Q(x) \) have the same truth value for every particular choice of value for \( x \) from domain \( D \).

    II: Building New Statements and Predicates from Old

      The simplest way to build a new statement from an old one is by using the negation

      Definition of the negation

      • symbol: \( NOT(S) \)
      • usage: \( S \) is some statement
      • meaning: \( NOT(S) \) is a new statement whose truth value is defined to be the opposite of the truth value of \( S \). That is, the truth \( NOT(S) \) is defined by the following truth table .
        truth of \( S \) truth of \( NOT(S) \)
        true false
        false true
      • generalization: The symbol \( NOT( P(x) ) \), where \( P(x) \) is a predicate , is a new predicate that is defined in the obvious way.

      A common way of building a new statement from two old ones is by using the conjunction , which is also known as the AND operation.

      Definition of the conjunction

      • symbol: \( A \; AN\!D \; B \)
      • alternate symbol: \( A \wedge B \) (spoken "\( A \) wedge \( B \)".)
      • usage: \( A \),\( B \) are statements
      • meaning: \( A \; AN\!D \; B \) is a new statement whose truth value is defined by the following truth table. (From now on, the column headings in truth tables will just give the symbol for the statement, rather than saying truth of statement .)
        \( A \) \( B \) \( A \; AN\!D \; B \)
        T
        		T T
        T
        		F F
        F
        		T F
        F
        		F F
      • generalization: The symbol \( A(x) \; AN\!D \; B(x) \), where \( A(x) \) and \( B(x) \) are both predicates , is a new predicate that is defined in the obvious way.

      Another common way of building a new statement from two old ones is by using the disjunction , which is also known as the OR operation.

      Definition of the disjunction

      • symbol: \( A \; OR \; B \)
      • alternate symbol: \( A \vee B \) (spoken "\( A \) vee \( B \)".)
      • usage: \( A \),\( B \) are statements
      • meaning: \( A \; OR \; B \) is a new statement whose truth value is defined by the following truth table.
        \( A \) \( B \) \( A \; OR \; B \)
        T
        		T T
        T
        		F T
        F
        		T T
        F
        		F F
      • Remark: Notice that the logical OR operation is what is sometimes referred to as the inclusive or in regular English. That is, \( A \) OR \( B \) is true not just when one of \( A \) or \( B \) is true, but also when they are both true.
      • generalization: The symbol \( A(x) \; OR \; B(x) \), where \( A(x) \) and \( B(x) \) are both predicates , is a new predicate that is defined in the obvious way.

      Our third way of building a new statement from two old ones is by building a conditional statement , which is also known as an IF-THEN statement.

      Definition of the conditional statement

      • sentence: \(I\!f \; A \; then \; B \)
      • alternate sentence: \( A \; implies \; B \)
      • symbol: \( A \rightarrow B \)
      • usage: \( A \),\( B \) are statements
      • meaning: \( A \rightarrow B \) is a new statement whose truth value is defined by the following truth table.
        \( A \) \( B \) \( A \rightarrow B \)
        T
        		T T
        T
        		F F
        F
        		T T
        F
        		F T
      • generalization: The symbol \( A(x) \rightarrow B(x) \), where \( A(x) \) and \( B(x) \) are both predicates , is a new predicate that is defined in the obvious way.
    • Negate AND and OR statements using deMorgan's Laws
      • \( NOT ( A \wedge B ) \equiv NOT(A) \vee NOT(B) \)
      • \( NOT ( A \vee B ) \equiv NOT(A) \wedge NOT(B) \)
    • Negate the conditional statement in this surprising way:
      • \( NOT ( A \rightarrow B ) \equiv A \wedge NOT(B) \)
      In words: \( NOT ( I\!f \; A \; then \; B ) \equiv A \; AND \; NOT(B) \)

    III: Related Conditional Statements

    Introducing the converse , the inverse , and the contrapositive

    Recall the truth table for the conditional statement \( I\!f \; A \; then \; B \):

    \( A \) \( B \) \( A \rightarrow B \)
    T
    		T T
    T
    		F F
    F
    		T T
    F
    		F T

    We let \( S \) stand for the original conditional statement \( I\!f \; A \; then \; B \). There are three conditional statements that are related to \( S \):

    • The converse of \( S \) is the statement \( I\!f \; B \; then \; A \).
    • The inverse of \( S \) is the statement \( I\!f \; NOT(A) \; then \; NOT(B) \).
    • The contrapositive of \( S \) is the statement \( I\!f \; NOT(B) \; then \; NOT(A) \).

    Truth of the Related Conditional Statements

    For an original statement \( S \) of the form \( I\!f \; A \; then \; B \), the truth of the related conditional statements can be determined by making truth tables for them.

    Truth table for the converse of \( S\):

      \( A \) \( B \) \( A \) \( B \rightarrow A \)
      T
      		T T T
      T
      		F T T
      F
      		T F F
      F
      		F F T

    Observe that the converse of \( S\) is not logically equivalent to \( S \) because \( S\) and the converse of \( S\) have different truth tables.

    Truth table for the inverse of \( S\):

      \( A \) \( B \) \( NOT(A) \) \( NOT(B) \) \( NOT(A) \rightarrow NOT(B) \)
      T
      		T F F T
      T
      		F F T T
      F
      		T T F F
      F
      		F T T T

    Observe that the inverse of \( S\) is not logically equivalent to \( S \) because they have different truth tables.

    But notice that the inverse of \( S\) is logically equivalent to the converse of \( S\) because they have the same truth tables.

    Truth table for the contrapositive of \( S\):

      \( A \) \( B \) \( NOT(B) \) \( NOT(A) \) \( NOT(B) \rightarrow NOT(B) \)
      T
      		T F F T
      T
      		F T F F
      F
      		T F T T
      F
      		F T T T

    Observe that the contrapositive of \( S\) is logically equivalent to \( S \) because they have the same truth tables. Knowing how to exploit this fact will be incredibly useful in this course and in all future math that you do.

    IV: Quantified Statements

    Definition of the existential quantifier

    • symbol: \( \exists x \in D \left( P(x) \right) \)
    • usage: \( P(x) \) is some predicate containing the variable x with domain D
    • meaning: There exists some \( x \) in \( D \) such that \( P(x) \) is true.
    • more terminology: The symbol \( \exists \) is called the existential quantifier ; The whole sentence "\( \exists x \in D \left( P(x) \right) \)" is called an existentially quantified statement
    • example:
      • Let \( D \) be the set of cars in the Morton Hall parking lot.
      • Let \( x \) be a variable with domain \( D \).
      • Let \( Silver(x) \) be a the predicate "\( x \) is silver."
      • Let \( A \) be the statement \( \exists x \in D \left( Silver(x) \right) \)
      • Then Statement \( A \) means "There exists a car in the Morton Hall lot that is silver."

    Definition of the universal quantifier

    • symbol: \( \forall x \in D \left( P(x) \right) \)
    • usage: \( P(x) \) is some predicate containing the variable x with domain D
    • meaning: For every \( x \) in \( D \), \( P(x) \) is true.
    • more terminology: The symbol \( \forall \) is called the universal quantifier ; The whole sentence "\( \forall x \in D \left( P(x) \right) \)" is called a universally quantified statement
    • example:
      • Same domain \( D \), variable \( x \) and predicate \( Silver(x) \) as in the previous example
      • Let \( B \) be the statement \( \forall x \in D \left( Silver(x) \right) \)
      • Then Statement \( B \) means "Every car in the Morton Hall lot is silver."

    What is the subject of predicates and quantified statements ?

    Consider the predicate "\( x \) is red." Clearly the predicate is a sentence about car \( x \). In general, a predicate is a sentence about the variable \( x \). Once an actual value for \( x \), an actual car, is chosen and substituted into \( Red(x) \), the predicate becomes a statement about that particular car, a statement that is either true or false. For exampe. The symbol \( Red( \) Mark's car \( ) \) denotes the statement "Mark's car is red . This is a statement about Mark's car. (It is a false statement.)

    Now consider two sets:

    • Let \( V \) be the set of cars in the Village Bakery parking lot.
    • Let \( C \) be the set of cars in the Columbus Airport parking lots (all of the lots).
    and consider two extistential statements built using those sets as domains and using the earier predicate \( Red(x) \).
    • Let \( A \) be the statement \( \exists x \in V \left( Red(x) \right) \). Statement \( A \) means "There exists a car in the Village Bakery parking lot that is red."
    • Let \( B \) be the statement \( \exists x \in C \left( Red(x) \right) \). Statement \( B \) means "There exists a car in the Columbus Airport parking lots that is red."
    What are statements \( A \) and \( B \) about ? They are really statements about the domains . That is, statement \( A \) is a statement about the set of cars in the Village Bakery Parking Lot. (At the time of this writing, it was a false statement. That is, statement \( B \) is a statement about the set of cars in the Columbus Airport parking lot. (It is safe to say that it is a true statement.)

    Negating Quantified Statements

    Negating Universal Statements

    Return to an earlier example of a universal statement \( B \):

  • "Every car in the Morton Hall lot is silver."

    • The negation of this statement would be the following

  • "There exists a car in the Morton Hall lot that is not silver."

    • Notice that the original statement \( B \) is a false statement, while its negation is a true statement. That makes sense.

    Expressinging our observations about statement \( B \) in symbols, we have

  • \( NOT(B) \equiv NOT \left( \forall x \in M (Silver(x)) \right) \equiv \exists x \in M \left(NOT(Silver(x)) \right) \)

    • Generalizing to other universal statements, we would write

  • \( NOT \left( \forall x \in D ( P(x) ) \right) \equiv \exists x \in D \left(NOT(P(x)) \right) \)

    • Notice that the negation of a universal statement will be an existential statement .

    Negating Existential Statements

    Return to an earlier example of an existential statement \( a \):

  • "There exists a car in the Morton Hall lot that is silver."

    • The negation of this statement would be the following

  • "Every car in the Morton Hall lot is not silver."

    • Notice that the original statement \( A \) is a true statement, while its negation is a false statement. That makes sense.

    Expressing our observations about statement \( A \) in symbols, we have

  • \( NOT(B) \equiv NOT \left( \exists x \in M (Silver(x)) \right) \equiv \forall x \in M \left(NOT(Silver(x)) \right) \)

    • Generalizing to other existential statements, we would write

  • \( NOT \left( \exists x \in D ( P(x) ) \right) \equiv \forall x \in D \left(NOT(P(x)) \right) \)

    • Notice that the negation of an existential statement will be a universal statement .

    V: Quantified Conditional Statements

    Introducing Quantified Conditional Statements

    An existentially quantified conditional statement would be just what it sounds like: a statement of the following form:

    • \( \exists x \in D \left( I\!f \; A(x) \; then \; B(x) \right) \)
    • \( \exists x \in D \left( A(x) \; implies \; B(x) \right) \)
    • \( \exists x \in D \left( A(x) \rightarrow B(x) \right) \)

    A universally quantified conditional statement would be just what it sounds like: a statement of the following form:

    • \( \forall x \in D \left( I\!f \; A(x) \; then \; B(x) \right) \)
    • \( \forall x \in D \left( A(x) \; implies \; B(x) \right) \)
    • \( \forall x \in D \left( A(x) \rightarrow B(x) \right) \)

    Negating Quantified Conditional Statements

    The simplest way to negate a statement or a predicate is to simply put the statement or predicate in parentheses and put the word \( NOT \) in front. The resulting sentence could be read as "Not statement" , or "It is not true that statement." This applies, in particular to quantified conditional statements .

    For example

    • Let \( C \) be the set of cars in the Columbus Airport parking lots (all of the lots).
    • Let \( x \) be a variable with domain \( C \).
    • Let \( Toyota(x) \) be the predicate " \( x \) is a Toyota."
    • Let \( blue(x) \) be the predicate " \( x \) is blue."
    • Let \( S \) be the statement \( \forall x \in C \left( I\!f \; A(x) \; then \; B(x) \right) \). Statement \( S \) means "For every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."
    • The simplest way to negate \( S \) would be to write
      • \( NOT(S) \)
      • \( NOT \left( \forall x \in C \left( I\!f \; A(x) \; then \; B(x) \right) \right) \)
      • "It is not true that for every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."

    But while that long sentence is technically the the negation of \( S \), the long sentence is rather confusing. What does it really mean to say that that all of that stuff is not true? What does the phrase it is not true that do to all of the stuff that follows to its right in the sentence?

    When writing sentences using the word not , or the phrase it is not true that , clarity is often improved if the sentence can be rewritten with word not moved as far to the right in the sentence as possible. The reason is that then there are not many words to the right of the word not in the sentence, so it won't be as hard to figure out what the word not does to all the stuff that follows to its right in the sentence.

    So our goal in writing sentences containing the word not will be to figure out how to rewrite them so that the not is as far to the right as possible while retaining the same meaning as the original sentence. This goal can be easier to achieve if we convert our sentences to logical notation, and then do the rewriting in logical notation, and then convert the final logical notation to a sentence.

    Here is an example of that process at work, using the above example.

    Original Sentence: We start with the statement \( NOT(S) \)

    • in symbols: \( NOT \left( \forall x \in C \left( I\!f \; A(x) \; then \; B(x) \right) \right) \)
    • in words: " It is not true that for every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."

    Move the NOT one place to the right : This moves the NOT past the quantifier, which changes the quantifier from \( \forall \) to \( \exists \)

    • in symbols: \( \exists x \in C \left( NOT \left( I\!f \; A(x) \; then \; B(x) \right) \right) \)
    • in words: "There exists a car in the Columbus Airport parking lots such that it is not true that if the car is a Toyota, then the car is blue."

    Move the NOT further to the right : This can only be done by negating the conditional statement. Note that the result will be an AND statement.

    • in symbols: \( \exists x \in C \left( A(x) \; AND \; NOT(B(x)) \right) \)
    • in words: "There exists a car in the Columbus Airport parking lots such that the car is a Toyota and the car is not blue."

    Realize that we have now written three sentences in words that all mean the same thing. They are all \( NOT(S) \). Most people would find the third version to be the easiest to understand.

    There is a practical reason for wanting to rewrite our sentences in the way just described, so that they are easier to understand. Remember the original statement \( S \)

    • \( S \) is the statement: "For every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."
    We have a sense that \( S \) is not true. How would we prove that \( S \) is not true? We would have to prove that \( NOT(S) \) is true. Now consider the three versions of \( NOT(S) \) that we have seen:
    • " It is not true that for every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."
    • "There exists a car in the Columbus Airport parking lots such that it is not true that if the car is a Toyota, then the car is blue."
    • "There exists a car in the Columbus Airport parking lots such that the car is a Toyota and the car is not blue."
    All three of these sentences mean the same thing. But the third version makes it easiest to see what we would need to do to prove that \( NOT(S) \) is true: We would need to find an example of a car in the Columbus Airport parking lots such that the car is a Toyota and the car is not blue.

    This same sort of thing will happen in our course. That is, it will happen that we will need to prove a statement that contains the word not . It will be be much simpler to figure out how to prove the statement if the statement is written in a form that has the word not appearing as far to the right as possible. That is the practical reason referred to above.

    In summary, when writing the negation of a logical statement, whether in words or in symbols, we will always strive to rewrite the negation in an equivalent form that has the word NOT appearing as far to the right as possible.

    VI: Proving Statements

    Proving Conditional Statements

    To prove a statement of the form \( I\!f \; A \; then \; B \), one builds a proof frame as follows:

    Proof that \( A \rightarrow B \)

    • Suppose that \( A \) is true.
    • Some statement (with some justification)
    • Some statement (with some justification)
    • Some statement (with some justification)
    • Some statement (with some justification)
    • Therefore, \( B \) is true (with some justification)

    End of proof

    Disproving Conditional Statements

    To disprove a conditional statement, one must prove that the negation of the conditional statement is true . Remember that the negation of the conditional statement \( I\!f \; A \; then \; B \) is not another conditional statement. Rather, the negation is an \( AND \) Statement: \( NOT ( I\!f \; A \; then \; B ) \equiv A \; AND \; NOT(B) \)

    Proof that \( NOT(A \rightarrow B) \). That is, Proof that \( A \; AND \; NOT(B) \)

    • Some statement (with some justification)
    • Some statement (with some justification)
    • Some statement (with some justification)
    • \( A \) is true. (with some justification)
    • Some statement (with some justification)
    • Some statement (with some justification)
    • Some statement (with some justification)
    • \( B \) is false. (with some justification)

    End of proof

    Proving Existential Statements

    Prove an existential statement by giving an example of an element \( x \) in the domain \( D \) that makes \( P(x) \) true.

    Proving Universal Statements

    • If domain is a \( D \) finite set, then one can check all of the \( x \) in the domain \( D \) to find their corresponding values of \( P(x) \). This is called the method of exhaustion . For example, consider the universally-quantified statement \( W \): "Every car in the Morton Lot has all its windows up." To prove this statement, one would have to go through the parking lot and check every car.
    • If domain is a \( D \) an infinite set, then one can't possibly do the method of exhaustion. Must do a general proof .
      • Suppose \( x \) is a generic (unkown) particular element of the domain \( D \).
      • Show that \( P(x) \) is true.
      • By the principle of generalizing from generic particular example (GFGPE) , conclude that \( P(x) \) is true for all \( x \) in \( D \).
    (page maintained by Mark Barsamian , last updated Jan, 2022)
    View Site in Mobile | Classic
    Share by: