## Propositions and Truth Sets

As one enters into the realm of advanced technology, one increasingly realizes that a layman's use of terminology and language is too imprecise. Not only does the use of technology require precision, but so does its discussion. Otherwise, it is not possible to establish requirements for a project. Nor is it possible to discover the cause of system problems and thereby get a sense of where to focus one's energies. This subunit gets you thinking along those lines and helps you to understand and avoid the vagueness of common speech.

**3.6.1 Propositions over a Universe**

Consider the sentence "He was a member of the Boston Red Sox". There is no way that we can assign a truth value to this sentence unless "he" is specified. For that reason, we would not consider it a proposition. However, "he" can be considered a variable that holds a place for any name. We might want to restrict the value of "he" to all names in the major-league baseball record books. If that is the case, we say that the sentence is a proposition over the set of major-league baseball players, past and present.

**Definition 3.6.1: Proposition ****ov****er a Universe. **Let *U *be a nonempty set. A proposition over *U *is a sentence that contains a variable that can take on any value in *U *and that has a definite truth value as a result of any such substitution.

**Example 3.6.2: Some propositions ****ov****er a variety of universes.**

- A few propositions over the integers are 4
*x*^{2}*−*3*x*= 0, 0*≤**n**≤*5, and "*k*is a multiple of 3". - A few propositions over the rational numbers are 4
*x*^{2}*−*3*x*= 0,*y*^{2}= 2, and (*s**−*1)(*s*+ 1) =*s*^{2}*−*1. - A few propositions over the subsets of ℙ are (
*A*= ∅) ∨ (*A*= ℙ), 3 ∈*A*, and*A**∩*{1*,*2*,*3} = ∅.

All of the laws of logic that we listed in Section 3.4 are valid for propositions over a universe. For example, if *p *and *q *are propositions over the integers, we can be certain that *p *∧*q *⇒*p*, because (*p *∧*q*) *→ **p *is a tautology and is true no matter what values the variables in *p *and *q *are given. If we specify *p *and *q *to be *p*(*n*) : *n < *4 and *q*(*n*) : *n < *8, we can also say that *p *implies *p *∧*q*. This is not a usual implication, but for the propositions under discussion, it is true. One way of describing this situation, in general, is with truth sets.

**3.6.2 Truth Sets**

**Definition 3.6.3: Truth Set. **If *p *is a proposition over *U*, the truth set of *p *is *T** _{p}*= {

*a*∈

*U*|

*p*(

*a*) is true}.

**Example 3.6.4: Truth ****Set Example. **The truth set of the proposition {1,2}∩ *A*= ∅, taken as a proposition over the power set of {1,2, 3, 4}is {∅,{3},{4},{3,4}}.

**Example 3.6.5: Truth sets depend ****on the universe. **Over the universe ℤ (the integers), the truth set of 4*x*^{2}*− *3*x *= 0 is {0}. If the universe is expanded to the rational numbers, the truth set becomes {0,3/4}. The term *solution set *is often used for the truth set of an equation such as the one in this example.

**Definition 3.6.6: Tautologies ****and Contradictions over a Universe. **A proposition over *U *is a tautology if its truth set is *U *. It is a contradiction if its truth set is empty.

**Example 3.6.7: Tautology, Contradiction ****ov****er ****ℚ****. **(*s **−* 1)(*s *+ 1) = *s*^{2}*−* 1 is a tautology over the rational numbers. *x*^{2}*−* 2 = 0 is a contradiction over the rationals.

The truth sets of compound propositions can be expressed in terms of the truth sets of simple propositions. For example, if *a *∈*T*_{p}_{∧}* _{q}*if and only if

*a*makes

*p*∧

*q*true. This is true if and only if

*a*makes both

*p*and

*q*true, which, in turn, is true if and only if

*a*∈

*T*

_{p}*∩*

*T*

*. This explains why the truth set of the conjunction of two propositions equals the intersection of the truth sets of the two propositions. The following list summarizes the connection between compound and simple truth sets.*

_{q}

**T****able 3.6.8: Truth Sets ****of Compound Statements**

*T*_{p }_{∧ q}= *T*_{p}*∩ **T*_{q}

*T*_{p }_{∨}* _{q}* =

*T*

*∪*

_{p}*T*

_{q}*T*_{¬}* _{p}*=

*T*

_{p}^{c}*T*_{p }_{↔ }* _{q}*= (

*T*

_{p}*∩*

*T*

*) ∪(*

_{q}*T*

_{p}^{c}*∩*

*T*

*)*

_{q}^{c}*T*_{p }_{→ }* _{q}*=

*T*

*∪*

_{p}^{c }*T*

_{q}

**Definition 3.6.9: Equivalence ****of propositions over a universe. **Two propositions, *p *and *q*, are equivalent if *p **↔ **q *is a tautology. In terms of truth sets, this means that *p *and *q *are equivalent if *T** _{p}*=

*T*

*.*

_{q}

**Example 3.6.10: Some ****pairs of equivalent propositions.**

(a) *n *+ 4 = 9 and *n *= 5 are equivalent propositions over the integers.

(b) *A **∩ *{4} = ∅ and 4 ∈ *A *are equivalent propositions over the power set of the natural numbers. □

**Definition 3.6.11: Implication ****for propositions over a universe. **If *p *and *q *are propositions over *U *, *p *implies *q *if *p **→ **q *is a tautology.

Since the truth set of *p **→ **q *is *T*_{p}* ^{c} *∪

*T*

*, the Venn diagram for*

_{q}*T*

_{p }

_{→ }*in Figure 12 shows that*

_{q}*p*⇒

*q*when

*T*

_{p}⊆

*T*

*.*

_{q}**Figure 3.6.12 **Venn Diagram for *T*_{p }_{→ }_{q}

**Example 3.6.13: Examples ****of Implications.**

- Over the natural numbers:
*n*≤ 4 ⇒*n*≤ 8 since {0, 1, 2, 3, 4} ⊆ {0,1, 2, 3, 4, 5, 6, 7, 8} - Over the power set of the integers: |
*A*^{c}| = 1 implies*A*∩ {0, 1} = ∅ - Over the power set of the integers,
*A*⊆ even integers ⇒*A*∩ odd integers = ∅

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.