S(1): If P Is TRUE and Q = P, Q Is Also TRUE by the Law of Double Negation

Problem 3-2

Part I:

S(1): If P is TRUE and Q = ~~P, Q is also TRUE by the Law of Double Negation.

In general, let us assume that for an arbitrary number k, if Q = P preceded by 2k ~'s, Q will also be TRUE.

Now all we have to do is to prove that for the next case (k+1), Q will be FALSE and that for (k+2), Q will be true.

Well, if a P preceded by k ~'s is TRUE, P preceded by k+1 ~'s will be FALSE, by the definition of negation. By the same rule, adding another ~ will again flip the truth value, thus making k+2 TRUE.

So, for all cases where Q = P preceded by an even number of ~'s (k, k+2, K+4, …), if P is true, Q will be true as well. And, for all cases where Q = P preceded by an odd number of ~'s, if P is TRUE, Q will be false.

Part II:

Since all whole numbers are even or odd and since all literals (P or ~P, if P is atomic) must be either true or false, the above example exhausts all cases. Thus, no matter how many negation symbols Q has, it will have the same truth value as a literal, namely either the literal P or the literal ~P.

Problem 3-9

1. (A Ù B) Ù A

A Ù B Idempotence of Ù

2. (B Ù (A Ù B Ù C))

A Ù B Ù C Idempotence of Ù

3. (A Ú B) Ú (C Ù D) Ú A

(A Ú B) Ú A Ú (C Ù D) Commutativity of Ú

(A Ú B Ú A) Ú (C Ù D) Associativity of Ú (Unnecessary)

(A Ú B) Ú (C Ù D)

4. (ØA Ú B) Ú (B Ú C)

(ØA Ú B Ú B) Ú C Associativity of Ú (Unnecessary)

ØA Ú B Ú C Idempotence of Ú

5. (A Ù B) Ú C Ú (B Ù A) Ú A

(A Ù B) Ú C Ú (A Ú B) Ú A Commutativity of Ù

(A Ú B) Ú C Ú A Idempotence of Ú

Problem 3-10

1. Ø(Home(Carl) Ù ØHome(Claire))

ØHome(Carl) Ú Home(Claire) DeM

2. Ø[Happy(Max) Ù (ØLikes(Carl,Claire) Ú ØLikes(Claire,Carl))]

ØHappy(Max) Ú Ø(ØLikes(Carl,Claire) Ú ØLikes(Claire,Carl)) DeM

ØHappy(Max) Ú (Likes(Carl,Claire Ù Likes(Claire,Carl)) DeM

3. ØØØ[(Home(Max) Ú Home(Carl)) Ù (Happy(Max) Ú Happy(Carl))]

Ø[(Home(Max) Ú Home(Carl)) Ù (Happy(Max) Ú Happy(Carl))] DN

Ø(Home(Max) Ú Home(Carl)) Ú Ø(Happy(Max) Ú Happy(Carl)) DeM

ØHome(Max) Ù ØHome(Carl) Ù ØHappy(Max) Ù ØHappy(Carl) DeM

Problem 3-15

1. Max is a student, not a disk.

Student(Max) Ù ØDisk(Max)

2. Claire erased Folly at 2pm and then gave it to Max.

Erased(Claire, Folly, 2:00) Ù Gave(Claire, Folly, Max, 2:00 < t)

Note that this problem is rather bogus (as is the solution) since we don't have any way of specifying an unspecified time that is later than another time. A function symbol would do the trick, but we don't have one. It would be nice if they had provided Later(t), for "a time later than t".

Given what we have to work with, this might be a good translation, despite the fact that it has more precision than the sentence we're given:

Erased(Claire, Folly, 2:00) Ù Gave(Claire, Folly, Max, 2:01)

3. Folly belonged to either Max or Claire at 2:05 pm.

Owned(Max, Folly, 2:05) Ú Owned(Claire, Folly, 2:05)

4. Neither Max nor Claire erased Folly at 2 pm or at 2:05 pm.

ØErased(Max, Folly, 2:00) Ù ØErased(Max, Folly, 2:05) Ù ØErased(Claire, Folly, 2:00) Ù ØErased(Claire, Folly, 2:05)

5. 2:00 pm is between 1:55 pm and 2:05 pm.

(1:55 < 2:00) Ù (2:00 < 2:05)

6. When Max gave Folly to Claire at 2pm , it wasn't blank, but it was five minutes later.

Gave(Max, Folly, Claire, 2:00) Ù ØBlank(Folly, 2:00) Ù Blank(Folly, 2:05)

Problem 3-16

1. Student(Claire) Ù ØStudent(Max)

Claire is a student, but Max is not.

2. Disk(Silly) Ù ØOwned(Max, Silly, 2:00)

Silly is a disk but Max didn't own it at 2:00 pm.

3. Owned(Claire, Silly, 2:00) Ú Owned(Claire, Folly, 2:00)

Claire owned either Silly or Folly at 2:00 pm.

4. Ø(Erased(Max, Silly, 2:00) Ù Erased(Max, Folly, 2:00)

Max erased neither Silly nor Folly at 2:00pm.

5. ((Gave(Max, Silly, Claire, 2:00) Ù Blank(Silly, 2:00)) Ú

(Gave(Max, Folly, Claire, 2:00) Ù Blank(Folly, 2:00))) Ù

Angry(Claire, 2:05)

Either Max gave Silly to Claire at 2:00pm and it was blank at 2:00pm or Max gave Folly to Claire at 2:00pm and it was blank at 2:00pm, and Claire was Angry at 2:05pm.

Problem 3-17

English / FOL
The disease known as AIDS / AIDS (Name)
The disease known as influenza / Flu (Name)
X is less contagious than y / LessContagious(x, y) (Predicate)
X is more deadly than y / MoreDeadly(x, y) (Predicate)

LessContagious(AIDS, Flu) Ù MoreDeadly(AIDS, Flu)

English / FOL
Abe / Abe (Name)
Stephen / Stephen (Name)
Monday / Monday (Name)
Sunday / Sunday (Name)
X Fooled y on d (a day) / Fooled(x, y, d)

Fooled(Abe, Stephen, Sunday) Ù ØFooled(Abe, Stephen, Monday)

English / FOL
Dan / Dan (Name)
George / George (Name)
Al / Al (Name)
Bill / Bill (Name)
X Admires y and z / Admires(x, y, z) (Predicate)

Admires(Dan, Al, Bill) Ú Admires(George, Al, Bill)

English / FOL
Daisy / Daisy (Name)
Dee / Dee (Name)
X is a river / River(x) (Predicate)
X is a jolly miller / JollyMiller(x) (Predicate)
X lives on y (a place) / Lives(x, y) (Predicate)

JollyMiller(Daisy) Ù Lives(Daisy, River(Dee))

3-18

1. (A Ù B) Ú (ØA Ú ØB)

Since, by DeMorgan's theorem, (ØA Ú ØB) is Ø(A Ù B), we have

(A Ù B) Ú Ø(A Ù B)

This is a tautology since it is of the form P Ú ØP, and whenever P (A Ù B) is true, ØP (Ø(A Ù B)) must be false. Because a disjunction is true whenever one side is true and because one side is always true, this statement is always true. Therefore it is a tautology.

2. (A Ù B) Ú (A Ù ØB)

This is not a tautology because of lines 3 & 4.

( A / Ù / B ) / Ú / ( A / Ù / Ø B )
T / T / T / T / T / F / F
T / F / F / T / T / T / T
F / F / T / F / F / F / F
F / F / F / F / F / F / T

3. Ø(A Ù B) Ú C

This is not a tautology because of line 2.

Ø / ( A / Ù / B ) / Ú / C
F / T / T / T / T / T
F / T / T / T / F / F
T / T / F / F / T / T
T / T / F / F / T / F
T / F / F / T / T / T
T / F / F / T / T / F
T / F / F / F / T / T
T / F / F / F / T / F

4. (A Ú B) Ú Ø(A Ú (B Ù C))

This is not a tautology because of lines 3-6.

( A / Ú / B ) / Ú / Ø / ( A / Ú / ( B / Ù / C )
T / T / T / T / F / T / T / T / T / T
T / T / T / T / F / T / T / T / F / F
T / F / F / F / F / T / T / F / F / T
T / F / F / F / F / T / T / F / F / F
F / F / T / F / F / F / T / T / T / T
F / F / T / T / T / F / F / T / F / F
F / F / F / T / T / F / F / F / F / T
F / F / F / T / T / F / F / F / F / F

3-19

We do this problem by deciding whether any of the lines in the truth table are spurious. What this means is that if a given statement is necessarily true, assigning the value to false to it would be bogus. So, what we do is blank out the rows that contain spurious values and then assess the remaining rows. (I'll shade the spurious rows)

1-1

(A Ù B) Ú (ØA Ú ØB)

( A / Ù / B ) / Ú / ( ØA / Ú / ØB )
T / T / T / T / F / F / F
T / F / F / T / F / T / T
F / F / T / T / T / T / F
F / F / F / T / T / T / T

Because this was a tautology anyway, eliminating the spurious rows doesn't make any difference. It's still a tautology, which means that is logically true

1-2

( A / Ù / B ) / Ú / ( A / Ù / Ø B )
T / T / T / T / T / F / F
T / F / F / T / T / T / T
F / F / T / F / F / F / F
F / F / F / F / F / F / T

Because only T's are left under the major connective, this turns out to be logically true.

1-3

This turns out to be satisfiable (not logically true) because of the F in row 2.

This turns out to be satisfiable (not logically true) because of the F's in rows 3 & 4.

2-1

( A / Ù / B ) / Ú / ( ØA / Ú / ØB )
T / T / T / T / F / F / F
T / F / F / T / F / T / T
F / F / T / T / T / T / F
F / F / F / T / T / T / T

This is still logically true because it was a tautology.

2-2

( A / Ù / B ) / Ú / ( A / Ù / Ø B )
T / T / T / T / T / F / F
T / F / F / T / T / T / T
F / F / T / F / F / F / F
F / F / F / F / F / F / T

This turns out to be satisfiable if a is necessarily false.

2-3

This turns out to be logically true because after eliminating the first 4 rows because they are spurious if A is necessarily false, all we have left are T's.

2-4

This turns out to be satisfiable.

3-1

Since there is no C, the condition does not apply.

3-2

Since there is no C, the condition does not apply.

3-3

This turns out to be logically true, because when we eliminate row 2 (when A and B are true, C must be true), we are left with all T's.

3-4

This continues to be satisfiable, even when A and B imply C.

Problem 20

1. Every satisfiable sentence is tt-satisfiable because in order to be satisfiable, at least one row must be true, which is the definition of tt-satisfiable.

2. Cube(a) Ù Tet(a)

This sentence is not satisfiable because a can't be a cube and a tetrahedron at the same time. It is tt-satisfiable because it there is at least one row in its truth table (though spurious), which has the truth value of T.

3. Every tt-satisfiable sentence is satisfiable if the atomic sentences of the langauge are logically independent because logical independence is a condition of all logically true statements being taugologies. That is, if all statements of the language are logically independent, the only truth tables that will be logically true are tautologies.

4. S is tt-satisfiable IFF ØS is not a tautology because if ØS were a tautology, S would be unsatisfiable. In order to be tt-satisfiable, a sentence must be satisfiable.

Problem 21

(The spurious rows will be grayed out.)

1. A Û b = b