[SOLVED] CS TT 22

9/17/2013 CHAPTER 2 SECTION 1
Chapter Two
Sentential Logic with and, or, if-and-only-if
1 SYMBOLIC NOTATION

Copyright By Assignmentchef assignmentchef

In this chapter we expand our formal notation by adding three two-place connectives, corresponding roughly to the English words and, or and if and only if:
if and only if
Conjunction: The first of these, , is the conjunction sign; it has the same logical import as and. It goes between two sentences to form a complex sentence which is true if both of the parts (called conjuncts) are true, and is otherwise false:
() TTT TFF FTF FFF
Disjunction: The disjunction sign, , makes a sentence that is true in every case except when its parts (its disjuncts) are both false. This corresponds to one use (the inclusive use) of or in English:
( ) TTT TFT FTT FFF
Biconditional: The biconditional sign, , states that both of the parts making it up (its constituents) are the same in truth value. It works like this:
( ) TTT TFF FTF FFT
Each of these new connectives behaves syntactically just like the conditional sign, : you make a bigger sentence out of two sentences plus a pair of parentheses:
() ( ) ( )
Our expanded definition of a sentence in official notation is now:
Chapter Two SYMBOLIC SENTENCES
Any capital letter between P and Z is a symbolic sentence. (Numerical subscripts may also be used, as P3, Q24.)
If is a symbolic sentence, so is ~
If and are symbolic sentences, so are (), (), ( ), and ( ).
Nothing is a symbolic sentence for purposes of chapter 2 unless it can be generated by the clauses given above.
Copyrighted material Chapter 2 1 Version of Aug 2013

9/17/2013 CHAPTER 2 SECTION 1
As before, we allow ourselves informally to omit the outer parentheses when the sentence occurs alone on a line. It is also customary (and convenient) to omit parentheses around conjunctions or disjunctions when they are combined with a conditional or biconditional sign. The sentence:
is to be considered to be an informally worded conditional whose antecedent is a conjunction:
If we want to make a conjunction whose second conjunct is a conditional, we must use parentheses
around the parts of the conditional: P (QR)
Likewise, this sentence: P QR
is an informally written biconditional whose second constituent is a disjunction: P (QR)
If we wish to write a disjunction whose first disjunct is a biconditional, we need to use parentheses around the biconditional:
(PQ) R.
Finally, we may use two or more conjunction signs or disjunction signs (but not a mix of conjunctions with disjunctions) as abbreviations for what you get by restoring the parentheses by grouping the left parts together, so that: P Q R is an abbreviation for (PQ) R.
Informal Conventions
Outermost parentheses may be omitted.
Conjunction signs or disjunction signs may be used with conditional signs or biconditional signs with the understanding that this is short for a conditional or biconditional which has a conjunction or disjunction as a part. For example:
PQ R is informal notation for (PQ) R P QR is informal notation for P (QR)
Repeated conjuncts or disjuncts without parentheses are short for the result of putting parentheses around the part to the left of the last conjunction or disjunction sign. For example:
P Q R is informal notation for (PQ) R P Q R is informal notation for (PQ) R
Sentences with the new connectives may be parsed as we did in the previous chapter: PQ R P QR
PQ R P QR 22
Copyrighted material Chapter 2 2 Version of Aug 2013

9/17/2013 CHAPTER 2 SECTION 1
~(PQ) (R PQ) ~~(R (P ~Q)) 2|
~(PQ) R PR ~(R (P ~Q)) |2|
PQ R PR R (P ~Q) 222
P Q P R R P~Q 2
Determining Truth Values Using such parsings, there is a mechanical way to determine whether any given sentence is true or false if you know the truth values of the sentence letters making it up. First, make a parse tree as above by taking the sentences on any given line and writing their immediate parts below them. A parse tree for (PQ) (PR) is:
(P Q) (P R) 2
(P Q) (P R) 22
Then write the truth values of the sentence letters below them. For example, if P and Q are both true but R false, you would have:
(P Q) (P R) 2
(P Q) (P R) 22
Then go up the parse tree, placing a truth value under the major connective of each sentence based on the truth values of its parts given below. For example, the truth value under (P Q) would be T because it is a conjunction, and both of its parts are T:
(P Q) (P R) 2
(P Q) (P R) T
Filling in the remaining parts gives you a truth value for the whole sentence at the top:
Copyrighted material Chapter 2 3 Version of Aug 2013

CHAPTER 2 SECTION 1
( (P Q) (P R) ) T
(P Q) (P R) TT 22
Sometimes not all of the parse tree needs to be filled out; this happens when partial information below a sentence is sufficient to decide its truth value. In the example just given it is not necessary to figure out the truth value of (P Q), since the conditional on the top line is determined to be true based on the information that (P R) is true. So the following parse tree is sufficient to show that the main sentence is true if the sentence letters have the indicated truth values:
(P Q) (P R) T
(P Q) (P R) T
1. For each of the following state whether it is a sentence in official notation, or a sentence in informal notation, or not a sentence at all. If it is a sentence, parse it as indicated above.
e. (PQ) (R~Q) f. P(QR)Q g. PQ (QRQ) h. P (PQR)
i. P (QP)
2. If P and Q are both true and R is false, what are the truth values of the official or informal sentences in 1? (Use the parses that you give in 1 to guide the determination of truth values.)
Copyrighted material
Chapter 2 4
Version of Aug 2013

2 ENGLISH EQUIVALENTS OF THE CONNECTIVES
Conjunctions: The word and is equivalent to the symbol . There are other locutions of English that may also be equivalent to , although they are sometimes used to communicate something additional. For example:
The book is short, and it is interesting
The book is short, but it is interesting
The book is short, although it is interesting The book is short, even though it is interesting The book is short; it is interesting
Some of these sentences suggest that if a book is short, you probably wont find it interesting. But all that they literally say is that it is both short and interesting. If it isnt short, what you have said is false, and if it isnt interesting then what you have said is false, but if it is both short and interesting, what you have said is true, even if possibly misleading.
In certain cases, use of a relative pronoun is logically equivalent to a use of : the sentence Maria, who was late, greeted the vice-counsel is equivalent to Maria was late Maria greeted the vice-counsel.
Disjunctions: The English word or can be taken in two ways: inclusively or exclusively. If you are asked to contribute food or money, you will probably take this as saying that you may contribute either or both; the invitation is inclusive. But if a menu says that you may have soup or salad the normal interpretation is that you may have either, but not both; the offer is exclusive. The difference in logical import appears in the first row here:
( inclusive-or ) ( exclusive-or ) TTTF TFTT FTTT FFFF
If the English or can be read either inclusively or exclusively, we will need to have a convention for how to interpret it when it is used in exercises. Our convention will be that or is always meant inclusively when it is used in problems and examples in this text. That is, it coincides in logical import with our disjunction sign .
A common synonym of or is unless. The sentence Wilma will leave unless there is food is false if there is no food but Wilma doesnt leave; otherwise it is true, just like or when read inclusively.
Biconditionals: We will see below that a biconditional sign is equivalent to two conditionals made from its constituents. The sentence ( ) is equivalent to:
CHAPTER 2 SECTION 2
Conjunctions: and
both and
although although ,
even though even though , ;
Disjunctions: or
either or unless
Copyrighted material Chapter 2 5 Version of Aug 2013

( ) ( )
This can be read in English as if , and only if ; thus it is often pronounced if and only if. The English phrase just in case or exactly in case are sometimes used to state the equivalence of two claims; the biconditional can be used to symbolize them:
The game will be called off just in case it rains:
The game will be played exactly in case it is sunny:
Q R P S
Biconditionals: if and only if
exactly on condition that just in case
CHAPTER 2 SECTION 2
a. Sally will walk or Veronica will give her a ride. b. Exactly on condition that it rains will Sally walk c. Although it will rain, Sally will walk
d. Barbara will come with Quincy or Tom
e. Barbara will come with Quincy; Sally will walk
3. What are the truth values of the sentences in 2 when all of the simple sentences are false?
1. For each of the following sentences say which symbolic sentence it is equivalent to.
a. It will rain, but the game will be played anyway. RP
b. Willa drove or got a ride WR
c. Robert, who didnt get a ride, was tardy ~R T
d. It rained; the sell-a-thon was called off RS
e. The quilting bee will be called off just in case it rains QR
QR QR RQ
2. Symbolize each of the following using this translation scheme:
S Sally will walk
V Veronica will give Sally a ride R It will rain
Q Barbara will come with Barbara will come with material Chapter 2 6
Version of Aug 2013

3 COMPLEX SENTENCES
Complex sentences of English generally translate into complex sentences of the logical notation. As usual, it is important to be clear about the grouping of clauses in the English sentence.
The following sentence is a simple conjunction:
Polk and Quincy were presidents P Q
The following sentence is also a conjunction, one of whose conjuncts is a negation:
Polk, but not Quincy, was a president.
This is a negation of a conjunction:
Not both Polk and Quincy were presidents.
This is a simple disjunction:
Either Polk or Quincy was president.
P ~Q ~(P Q)
This is a complex sentence, with at least two different but equivalent symbolizations.
Neither Polk nor Quincy was president.
One symbolization is the negation of Either Polk or Quincy was president; in this symbolization neither means not either: ~(P Q). An equivalent symbolization is a conjunction of negations; neither P nor Q is equivalent to not P and not Q: ~P ~Q
The fundamental principles for our new connectives are:
CHAPTER 2 SECTION 3
and, or, if and only if
When any of these expressions occurs between sentences, it gives rise to a conjunction, disjunction, or biconditional. The constituents of the conjunction, disjunction, or biconditional are symbolizations of sentences immediately to the left and to the right of and, or, or if and only if.
When either occurs with or, the symbolization of the expression enclosed between either and or is a disjunct. Likewise, When both occurs with and, the symbolization of the expression enclosed between both and and is a conjunct.
neither nor is equivalent to not (either or ).
As in chapter 1, these principles do not eliminate all ambiguity. The sentence Wilma will leave and Steve will stay or Tom will dance is ambiguous between these two symbolizations:
The use of either will sometimes disambiguate; the only symbolization of Wilma will leave and either
Steve will stay or Tom will dance is: W & (ST)
This is because either and or exactly enclose Steve will stay, and so S must be a disjunct. But it is not a disjunct in (W&S) T.
Commas play their usual role of grouping items on each side. The sentence Wilma will leave and Steve will stay, or Tom will dance has only the symbolization:
Copyrighted material Chapter 2 7 Version of Aug 2013

Conjunction and disjunction signs inside of sentences: Sometimes and and or occur within
sentences, as in:
Wilma sang and danced Tom or Sam left
In such cases you need to fill in a missing part to get a sentence that we already know how to symbolize.
These are some examples:
Wilma sang and danced Wilma sang and [Wilma] danced Tom or Sam left Tom [left] or Sam left
If there is a both or an either, it ends up on the front:
There may also be a not after the compound subject, or before a compound predicate. If the negation is after a compound subject, it forms part of the predicate, and it is filled in with that predicate:
Wilma or Veronica didnt sing Wilma [didnt sing] or Veronica didnt sing.
If the negation is before a compound predicate, it yields a negation sign that applies to the whole compound:
Wilma didnt sing or dance ~ (Wilma sang or danced) Wilma didnt sing and dance ~ (Wilma sang and danced)
The parts inside the parentheses are then expanded as usual:
Wilma didnt sing or dance ~ (Wilma sang or [Wilma] danced)
Wilma didnt sing and dance ~ (Wilma sang and [Wilma] danced) Compounds within simple sentences affect how sentences are grouped after symbolization:
When connectives occur inside otherwise simple sentences, the symbolizations of the sentences form a unit.
For example, the sentence Ruth tap-dances or sings and she plays the clarinet must be grouped like this: (T S) & P
This is because the disjunction with T and S must be a unit. In Ruth tap-dances or she sings and plays the clarinet the opposite happens; you must have:
T (S & P)
because the conjunction with S and P must form a unit.
CHAPTER 2 SECTION 3
Sometimes and or or occurs inside a simple sentence, where only the subject is conjoined or disjoined, and there is a single predicate, or only the predicate is conjoined or disjoined, and there is a single subject. If you fill in a copy of the shared part, you will get a synonymous sentence that we already know how to symbolize.
Both Tom and Sam left Either Tom or Sam left
Wilma both sang and danced Wilma either sang or danced
Both Tom [left] and Sam left Either Tom [left] or Sam left
Both Wilma sang and [Wilma] danced Either Wilma sang or [Wilma] danced.
Copyrighted material Chapter 2 8 Version of Aug 2013

Synonyms of and, or, and if and only it are subject to the conditions described above.
Here are some illustrations:
If neither Wilma nor Sally attends, either Robert or Peter will be bored.
If neither Wilma [attends] nor Sally attends, either Robert [will be bored] or Peter will be bored. If neither W nor S, either R or P
~(WS) (RP)
The neither and the either made units, and the comma was redundant.
A slightly more complex case:
If neither Wilma nor Sally attends, either Robert or Peter, but not Tom, will be bored.
If neither Wilma [attends] nor Sally attends, either Robert [will be bored] or Peter [will be bored], but Tom will not be bored.
If neither W nor S, either R or P, but not T ~(WS) (RP) & ~T
Here the either made a unit, so the but could not take Peter would be bored as its left conjunct. That is, the symbolization could not be this:
~(WS) (R (P&~T))
Likewise, the original phrase either Robert or Peter, but not Tom, will be bored consists of three simple
sentences all sharing the will be bored, so it could not be pulled apart, as in: (~(WS) (RP)) & ~T
Some additional examples:
Either Robert or Tom will attend, but not both
Either Robert [will attend] or Tom will attend, but not both [will attend] Either R or T, but not R and T
(RT) ~(RT)
Robert will attend if Sally does, but she wont attend if neither Tom nor Wilma attend.
Robert will attend if Sally does [attend], but she wont attend if neither Tom [attends] nor Wilma attends.
R if S, but not S if neither T nor W
(SR) (~(TW) ~S)
Neither Sally nor Robert will run, but if either Tom or Quincy run, Veronica will win. Neither S nor R, but if either T or Q, V
~(SR) (TQ V).
Given that Sally and Robert wont both run, Tom will run exactly if Q does. Given that not both S and R, T exactly if Q.
~(SR) (TQ)
A variety of English expressions that we have not mentioned affect how a sentence is to be symbolized. Examples:
Quincy will whistle if Reggie sings without Susan singing or Susan sings without Reggie, but he wont whistle if they both sing
CHAPTER 2 SECTION 3
Copyrighted material Chapter 2 9 Version of Aug 2013

Q if R and not S or S and not R, but not Q if S and R ((R~S) (S~R) Q) (SR ~Q)
Here Reggie sings without Susan singing means that Reggie sings and Susan doesnt sing. If Sally runs, Rob will run, in which case Theodore will leave
(SR) (RT)
Here in which case means if Rob runs.
If a symbolization of a sentence is a correct one, then it and the English sentence being symbolized must agree in truth value no matter what truth values the simple sentences have. If they agree for every assignment of truth values, then the symbolization is correct. If not, it is incorrect. (To tell whether an English sentence is true or false given a specification of truth values for its simple parts you must rely on your understanding of English. To tell whether a symbolic sentence is true or false given the truth values of its sentential letters, you parse it and figure out its truth value as in section 1.)
CHAPTER 2 SECTION 3
1. If P is true and both Q and R are false, what are the truth values of the following? (In answering, give a parse tree for the sentence.)
a. ~(P(QR))
b. ~P(QR)
c. ~(PR)~PR
d. ~Q(P(QR))
e. P(~Q(~RQ))
For questions 2 and 3, use this translation scheme: V Veronica will leave
W William will leave Y Yolanda will leave
2. For each of the following say which of the proposed translations is correct.
a. Veronica wont leave if and only if William wont leave ~(V ~W)
~V ~W V ~~W
b. William and Veronica will both leave if Yolanda does, provided that Veronica doesnt Y~V WV
(YWV) ~V ~V (YWV)
c. Unless Yolanda leaves, Veronica or William will leave Y (W V)
Y (W V) YWV
d. Either Yolanda leaves and Veronica doesnt, or Veronica leaves and William doesnt (Y ~V) (V ~W)
(Y ~V) (V ~W) Y ~V V ~W
Copyrighted material Chapter 2 10 Version of Aug 2013

CHAPTER 2 SECTION 3
3. For each of the following produce a correct symbolization
a. Sally will run and win unless she quits
b. Sally will win exactly in case she runs without quitting c. Sally, who will run, will win if she doesnt quit
d. Sally will run and quit, but she will win anyway
a. Only if Veronica doesnt leave will William leave, or Veronica and William and Yolanda will all leave
b. If neither William nor Veronica leaves, Yolanda wont either
c. If William will leave if Veronica leaves, then he will surely leave if Yolanda leaves d. Neither William nor Veronica nor Yolanda will leave
4. What are the truth values of 3a-d if Veronica leaves but neither William nor Yolanda leaves?
For question 5 use this translation scheme:
R Sally will run W Sally will win Q Sally will quit
5. For each of the following produce a correct symbolization
Copyrighted material Chapter 2 11 Version of Aug 2013

Each new connective comes with two new rules. As earlier, it should be obvious from the truth-table descriptions of each connective that instances of these rules are formally valid arguments.

CS: assignmentchef QQ: 1823890830 Email: [email protected]