3B  Connectives

A connective is a word used to combine two statements into one - such as and, or, because, however, etc. In our study of logic we concern ourselves mainly with and and or, the simplest connectives. Connecting statements with and is called conjunction, while connecting statements with or is disjunction. The logic symbol for “and” is “Ù”, while the symbol for “or” is “Ú”. A statement formed by combining two or more statements with connectives is a compound statement.

example 1

	Lunch with Fred

Let p, q, r, and s be the statements

Below are some compound statements constructed from these simple statements with the use of connectives and negations; on the left we write each statement symbolically, and on the right we interpret the symbols into words. Note the strategic use of parentheses in symbolic statements to indicate where parts of sentences are separated by commas.

What do we mean when we connect two statements with the word “and”? For instance, if you say “I met Fred and I had lunch”, what do you want people to understand from this compound statement? Indeed, you intend that listeners accept as true the statement “I met Fred” as well as the statement “I had lunch”; if either of these simpler statements is false then your entire compound statement is false. So when you say “p and q”, you speak truthfully if both p is true and q is true, but you speak falsely if either p is false, q is false, or if both p and q are false. We summarize these observations in the truth table at the left. The first two columns of the table list all possibilities for the truth values of general statements p and q, while the third column gives the corresponding truth value in each case for the conjunction p Ù q.

The analysis of the connective “or” is a little more complicated, because in different circumstances we might interpret this connective in different ways. In everyday usage there are two kinds of “or” - an exclusive or and an inclusive or. Suppose for example that you are eating breakfast at Zippy’s restaurant, and the waitress announces that “you may have rice or hash browns with your eggs.” What she probably means is that, for no extra charge, you may have rice with your eggs or you may have hash browns with your eggs, depending on your preference, but not that you may have both rice and hash browns. In this instance she uses an exclusive or, because one or the other option must be excluded. Now suppose that next the waitress asks, “do you want salt or pepper on your eggs?” What she probably means now is that you may have salt on your eggs, you may have pepper on your eggs, or you may even have both salt and pepper on your eggs. Here she uses an inclusive or, meaning that it is not necessary to exclude one of the options.

In ordinary conversation there is hardly ever much confusion created by the ambiguity of the connective “or”, because most times the appropriate interpretation is clear from the context. However in the study of logic we must be clear in what we mean when we use this connective. To avoid misunderstanding, it is customary to decree that the symbol “Ú” refers always to the inclusive version of “or”, and that when we use the word “or” we mean the inclusive version unless specifically stated otherwise.

What then will be our truth table for “or”? Let us suppose you arrive at a wedding reception, and the doorman asks if you were invited by the bride or groom (obviously using an “inclusive or” in this situation). If you answer, “Yes, I was invited by the bride or I was invited by the groom”, under what circumstances are you telling the truth? If either of the statements

is true, or if even both p and q are true, then your compound statement p Ú q is true. You are lying to the doorman only if both p and q are false. Thus the disjunction p Ú q is false only when both p and q are false, and it is true in all other situations. The accompanying truth table for disjunction summarizes these observations.

Our truth tables for negation, conjunction, and disjunction can be summarized with the following list of “logic equations” :

These formulas have obvious interpretations. For example, ~T = F indicates that the negation of a true statement is a false statement, while T Ù F = F asserts that the conjunction of a true statement and a false statement is a false statement.

We can use the preceding formulas to analyze the truth value of a more complicated compound statement, whenever the truth values of its simpler parts are known.

example 2

Suppose that statement p is true, statement q is false, and statement r is true. We determine the truth value of the compound statements

In each of these expressions we substitute T for both p and r, and substitute F for q; then we simplify:

We conclude that the statements of parts a and c are false,whereas that of part b is true.

example 3

Upon arriving home late, Mr. Kim made the following statement to his wife:

We will use a truth table to determine under what circumstances Mr. Kim is telling the truth. By defining simple statements

we can write Mr. Kim's compound statement as

We construct a truth table for this statement, beginning with columns for p and q on the left, and adding columns until we build up Mr. Kim's statement in the last column. The first two columns require no work - they just list all possibilities for the truth values of p and q - but the remaining columns we fill in using preceding columns and our logic equations for negation, conjunction, and disjunction. Note that the third column negates the first column, the fourth column is the conjunction of the first two columns, and the last column is the disjunction of the third and fourth columns. The truth table shows that Mr. Kim's statement is false only when p is true and q is false; under all other conditions he is telling the truth. Therefore, Mrs. Kim may conclude that either Mr. Kim is telling the truth, or that he is lying and caught the bus and did not work late.

Next we ponder how to negate a conjunction. It will help to look at a concrete example. Let p and q be the statements

and consider the conjunction of these statements,

The negation of p Ù q is that statement whose truth value must be opposite to that of p Ù q, regardless of the circumstances. So suppose p Ù q is false - that is, suppose it is false that the dog is brown and lazy. Then what statement has to be true? The dog must be either “not brown” or “not lazy” - that is, the statement ~p Ú ~q must be true. On the other hand, suppose p Ù q is true, so that the dog is brown and the dog is lazy; then it is false that the dog is not brown or not lazy, so the statement ~p Ú ~q is false. Consequently, as p Ù q and ~p Ú ~q are necessarily opposite in truth value, the negation of p Ù q is

This example illustrates the so-called De Morgan law for the negation of a conjunction,

Again, the symbol “≡” indicates that the two statements are equivalent. We rigorously verify this formula with the truth table below. In the table we include columns for each of the statements ~(p Ù q) and ~p Ú ~q. As the sequence of T's and F's is the same in these two columns, the statements have always the same truth value and thus are logically equivalent.

example 4

On the left appear some conjunctions, and on the right their negations :

Next we examine how to negate a disjunction. Suppose a student is having trouble with her moped, and consider the statements

as well as their disjunction,

If p Ú q is false, then the moped is not out of gas and is not broken, so both ~p and ~q are true - that is, the conjunction ~p Ù ~q is true. On the other hand, if p Ú q is true, then either the moped is out of gas, broken, or perhaps both, so it is false that the moped is not out of gas and is not broken - that is, ~p Ù ~q is false. Therefore, since p Ú q and ~p Ù ~q are always opposite in truth value, the negation of p Ú q is

This example demonstrates the De Morgan law for the negation of a disjunction,

In one of the exercises you are asked to verify this De Morgan law with a truth table - to do so just look at our previous truth table for negating a conjunction, and procede in an analogous way.

example 5

On the left appear some disjunctions, and on the right their negations :

It is of course possible to connect several statements at once with the word “and”, and likewise with the word “or”. Two such examples are

The assumption in the first statement is that all three assertions are true - not just one or two of them. A compound statement of the form p Ù q Ù r is true whenever all three statements p, q, and r are true, and is false under all other conditions. In contrast, the second statement maintains only that at least one of the three assertions is true - not necessarily that two or three of them are true. The compound statement p Ú q Ú r is false whenever all three statements p, q, and r are false, and is true under all other conditions.

We summarize these deliberations in the following truth table for three statements p, q, and r. The left three columns of the table list all possible combinations for the truth values of p, q, and r; there are eight of these, resulting in a table of eight rows. (By convention, the first three columns in a truth table for three statements are completed always exactly in this way.) The last two columns list the corresponding truth values for the conjunction p Ù q Ù r and the disjunction p Ú q Ú r. At the right of the table are the corresponding logic equations asserted by the table.

The formulas for negating conjunctions and disjunctions of three statements are

In the exercises you are asked to verify these formulas with truth tables. As illustration of these formulas, below are two compound statements, each followed by its negation:

Thanks to the richness of our language, in everyday conversation we can say the same thing in many different ways. The conjunction “and”, for example, can appear in several forms. Let p and q be the statements

Here are different ways we can make the logical statement p Ù q :

Probably you can think of other ways.

EXERCISES 3B

1. Let p, q, r, and s be the statements

   p : the horse is gone

   ,

   q : the gate is closed

   ,

   r : the cow lows

   ,

   s : dusk falls .

   Change the symbolic statements below into ordinary sentences:

   		a.	p Ù r		b.	~p Ù q		c.	r Ú s
   		d.	p Ù ~q Ù s		e.	r Ú (p Ù s)		f.	(r Ú p) Ù s
   		g.	~(p Ù ~q)		h.	(s Ù p) Ú ~q		i.	(~r Ú p) Ù ~s
   		j.	(p Ù s) Ú (q Ù ~r)		k.	~q Ú ~p Ú r		l.	q Ù ~(r Ù s)

   
   
2. Let p, q, r, and s be the statements

   p : baby cries

   ,

   q : baby laughs

   ,

   r : baby is hungry

   ,

   s : baby is tired .

   Translate the sentences below into symbolic statements.

   a.	Baby cries and is hungry.
   b.	Baby cries, and is hungry or tired.
   c.	Baby is not hungry, but laughs.
   d.	Baby cries and is tired and hungry.
   e.	Baby is tired or hungry, and does not laugh.
   f.	Baby cries and is hungry, or is tired.
   g.	Baby laughs and is not tired, or is hungry and cries.
   h.	It is not the case that Baby is tired and hungry.
   i.	Baby is hungry or tired, and cries and does not laugh.
   j.	Baby laughs, or Baby is not hungry and is tired and is crying.

   
   
3. Determine whether the “or” in the sentence is inclusive or exclusive:

   		a.	The leaf is from a maple or an elm.
   		b.	I hope to make an A or a B in this class.
   		c.	Tomorrow will be cloudy or rainy.
   		d.	I have always a fruit or a vegetable with lunch.
   		e.	Jim likes movies that are escapist or funny.
   		f.	Give me liberty or give me death.

   
   
4. Suppose statements p and q are true, while r and s are false. Determine the truth value of each of the following compound statements :

   a.	p Ù r		b.	q Ú s		c.	(~p Ù s) Ú q
   d.	(q Ú r) Ù ~s		e.	(q Ú ~s) Ù (r Ú ~p)		f.	~s Ù (p Ú ~q)
   g.	(s Ù p) Ú ~(r Ù q)		h.	(~p Ù s) Ú (p Ù q Ù r)		i.	~(~q Ú r) Ù (s Ú p Ú ~r)

   
   
5. Construct a truth table for each statement :

   a.

   p Ú ~q

   b.

   ~p Ù q

   c.

   p Ù (q Ú ~p)

   
   
6. A politician promised, “I will vote for lower taxes or for fiscal reform, and I will not vote for fiscal reform”. What must the politician do to keep his word? Justify your answer with a truth table.
   
   
7. Use a truth table to verify the De Morgan law for the negation of a disjunction.
   
   
8. Give the negation of each statement :
   1. I will study hard and make an A on the test.
   2. The boy is over 16 or is accompanied by a parent.
   3. Peanut butter is gooey and sticks to the roof of your mouth.
   4. I understand your position and I am not angry.
   5. Jenny will not visit Paris or not visit Rome.
   6. The earth is not flat, nor does it rest on the back of a turtle.
   7. The resident of the apartment is not home or is sleeping.
   8. Mary will win the race or die trying.
   
   
9. Verify each negation formula with a truth table :

   a.

   ~(p Ù q Ù r) ≡ ~p Ú ~q Ú ~r

   b.

   ~(p Ú q Ú r) ≡ ~p Ù ~q Ù ~r

   
   

Give the negation of each statement : The UH basketball team will beat Rice, Fresno, and Tulsa. UH will lose to Nevada or SMU or Boise. The team will practice hard, play smart, and not lose hope. We will win the game - or at least try hard - or the coach will not be pleased. Andy or Ben or Carl or Dan will make the all-conference team. I will enjoy the game, eat popcorn, yell with the cheerleaders, and listen to the band.

11. Let p and q be the statements

    p : Bob will bring food

    ,

    q : Bev will bring drinks .

    Write symbolically the compound statements :
    1. Bob will bring food and Bev will bring drinks.
    2. Bob will bring food but Bev will not bring drinks.
    3. Bob will bring food, whereas Bev will bring drinks.
    4. Bob will not bring food; Bev will not bring drinks.
    5. Bev will bring drinks; additionally, Bob will bring food.
    6. Although Bev will bring drinks, Bob will not bring food.
    7. Despite the fact that Bob will not bring food, nevertheless Bev will bring drinks.
    8. Bev will bring drinks; in the alternative, Bob will bring food.