The Proof Page

by D. A. Kouba

Section 1.1- Propositions and Connectives; Truth Tables



In the study of mathematics, one often must begin with definitions and assumptions (rules of the game), which are assumed to be true. The process of deductive reasoning can then lead to logical conclusions (lemmas, theorems, and corollaries), which need to be proven true. In general, unique or uniform mathematical language and symbols are used to simplify this process. The Proof Page will assist those in the transition from ``how to" mathematics to ``why" mathematics.

$ \underline { \rm DEFINITION } $ : A $ \underline { \rm proposition } $ is a sentence that is either true (T) or false (F).

$ \underline { \rm EXAMPLE } $ : Determine which of the following sentences are propositions. Find solutions HERE .

We will now begin combining propositions using the symbols $ \wedge, \vee,$ and $ \sim$, which are called logical connectives.

$ \underline { \rm DEFINITION } $ : Let $ P $ and $ Q $ be propositions.

1.) The $ \underline { \rm conjunction } $ of $ P $ and $ Q $ is written $ P \wedge Q $ (read ``$ P $ and $ Q $"). The conjunction is true exactly when both $ P $ and $ Q $ are true.

2.) The $ \underline { \rm disjunction } $ of $ P $ and $ Q $ is written $ P \vee Q $ (read ``$ P $ or $ Q $"). The disjunction is true exactly when at least one of $ P $ and $ Q $ is true.

3.) The $ \underline { \rm negation } $ of $ P $ is written $ \sim P $ (read ``not $ P $"). The negation is true exactly when $ P $ is false.

NOTE : The preceding three definitions of logical connectives and their values of true (T) and false (F) are designed to be consistent with standard spoken and written usage of ``and", ``or", and ``not" in the English language.

$ \underline { \rm DEFINITION } $ : A $ \underline { \rm propositional \ form } $ is an expression involving finitely many logical symbols (connectives) and letters (propositions).

$ \underline { \rm EXAMPLE } $ : The expression $ Q \wedge ( P \vee (\sim R) ) $ is a propositional form.

The following truth tables illustrate all possible truth values for the propositional forms $ \sim P $, $ P \wedge Q $, and $ P \vee Q $.

$ P $ $ \sim P $
$ T $ $ F $
$ F $ $ T $


$ P $ $ Q $ $ P \wedge Q $
$ T $ $ T $ $ T $
$ T $ $ F $ $ F $
$ F $ $ T $ $ F $
$ F $ $ F $ $ F $


$ P $ $ Q $ $ P \vee Q $
$ T $ $ T $ $ T $
$ T $ $ F $ $ T $
$ F $ $ T $ $ T $
$ F $ $ F $ $ F $



On The Proof Page, in particular, and in advanced mathematics, in general, we are often concerned with the equivalence of mathematical statements, that is, the equivalence of propositional forms. Equivalent forms give us the opportunity to choose, from among all the equivalent forms, a form which is simplest to use or easiest to understand. Propositional forms are equivalent if they have the same truth tables.

$ \underline { \rm EXAMPLE } $ : Determine if the following propositional forms are equivalent.


NOTE : (ORDER OF OPERATIONS) If parantheses are not used to clearly indicate the use of the connectives, then invoke the connectives in the following order- $ \sim$ , $ \wedge $ , $ \vee $. For example, $ P \vee \sim Q \wedge R $ is equivalent to $ P \vee ( (\sim Q) \wedge R) $ .

$ \underline { \rm EXAMPLE } $ : Provide parantheses to clarify the following ambiguous expressions. Find solutions HERE .



$ \underline { \rm DEFINITION } $ : A $ \underline { \rm tautology } $ is a propositional form for which all of its values are true (T). A $ \underline { \rm contradiction } $ is a propositional form for which all of its values are false.

$ \underline { \rm EXAMPLE } $ : Truth tables can be used to easily verify the following two statements. The form $ P \vee ( \sim P) $ is a tautology. The form $ Q \wedge ( \sim Q) $ is a contradiction.

$ \underline { \rm DEFINITION } $ : A $ \underline { \rm denial } $ of a proposition $ S $ is any proposition which is equivalent to $ \sim S $.

$ \underline { \rm EXAMPLE } $ : Let proposition $ S $ be ``Integer $ n $ is even." Each of the following statements is a denial of $ S $, that is, each statemnt is equivalent to $ \sim S $.

  • 1.) It is not the case that integer $ n $ is even.

  • 2.) Integer $ n $ is not even.

  • 3.) Integer $ n $ is odd.

  • 4.) Integer $ n $ can be written in the form $ 2m+1 $, where $ m $ is some integer.

  • 5.) Integer $ n $ can be written in the form $ 2m-1 $, where $ m $ is some integer.

    $ \underline { \rm EXAMPLE } $ : Write two denials for each proposition. Find solutions HERE .




    RETURN to The Proof Page .


    Please e-mail your comments, questions, or suggestions to D. A. Kouba at kouba@math.ucdavis.edu .


    Next: About this document ...
    Duane Kouba 2002-05-08