**LOGIC**

**Spring
2017**

**Homework Assignments **

**January 18**

**Covered slides:**** **0.a
– 2.5

**Textbook reading:**** **Parts
of Introduction, Chapters 1-2.

**Electronic submissions:**** **Exercises
1.2, 1.3, 1.5, 2.15, 2.17, 2.21.

**Possible quiz questions: **Exercises
2.4, 2.22, 2.23.

**January 25**

**Covered slides:**** **3.0
– 4.6.b

**Textbook reading:**** **Chapters
3-4 (except Section 3.8).

**Electronic submissions:**** **Exercises
3.21, 4.2, 4.17, 4.24, 4.27, 4.39.

**Possible quiz questions: **

· State DeMorgan’s laws (Slide
3.5).

· Definitions of "*logically possible*", "*logically
necessary*", "*tautology*"
(Slide 4.1.a), "*logically equivalent*", "*tautologically equivalent*" (Slide
4.2), "*logical consequence*",
"*tautological consequence*"
(Slide 4.3).

· You should be able to construct a truth table for any
given sentence and tell if it is a tautology.

· Using truth tables, you should be able to tell, for
any two sentences, whether they are tautologically equivalent.

· Using truth tables, you should be able to tell, for
any two sentences, whether one is a tautological consequence of the other.

· Write two sentences ** A** and

· State the laws of commutativity, idempotence,
associativity (Slide 4.5.b), distribution (Slide 4.6.b).

**February 1**

**Covered slides:**** **5.0
– 6.6

**Textbook reading:**** **Chapters
5-6

**Electronic
submissions:**** **Exercises 6.5,
6.6, 6.7, 6.8, 6.20, 6.40[2pt].

**Possible quiz questions: **

·
Exercises 5.1-5.6,
5.7, 5.12, 5.13

·
Give an informal
proof of the fact that Ö2 is irrational (page 138).

·
Give an informal
proof of the following fact: There are irrational numbers b,c such that b^{c}
is rational (pages 132-133).

**February 8**

**Covered slides:**** **7.1
– 8.3.b

**Textbook reading:**** **Sections 7.0-7.4,
8.0-8.4

**Electronic submissions:**** **Exercises 6.33, 7.6, 7.25, 8.26, 8.27, 8.28

**Possible
quiz questions: **

· Exercise
7.22

· Applying
the method explained in Section 7.4, you should be able to express any truth
function using only negation, disjunction and conjunction. Specifically, a
truth function (a new connective, that is) will be given to you through a truth
table, and you should write an equivalent formula only containing negation,
disjunction and conjunction.

· Remember
that **F _{T}** is the version of

a) What does the soundness of **F _{T}** exactly
mean here? Provide a clear, definition-style answer. It should be short and to
the point.

b) What does the completeness of **F _{T}** exactly
mean here?

**February 15**

**Covered slides:**** **9.1
– 10.2.a

**Textbook reading:**** **Sections 9.1-9.6,
10.0-10.2

**Electronic submissions:**** **Exercises 9.6, 9.9, 9.16, 9.17, 6.3, 6.9.

**Possible
quiz questions: **

·
The four
Aristotelian forms and their translations.

·
Exercise 10.1.

·
Explain the meanings of “FO valid”, “FO
consequence” and “FO equivalence”.

**February 22**

**Covered slides:**** **10.2.b
– 11.5

**Textbook reading:**** **Sections 10.2-10.4,
11.1-11.5

**Electronic submissions:**** **Exercises 10.22, 10.23, 10.24, 10.27, 11.2,
11.4, 11.11.

**Possible
quiz questions: **

· Exercises
10.10, 10.20, 11.27, 11.28

**March 1**

**Covered slides:**** **12.1
– 13.4

**Textbook reading:**** **Sections 12.1-12.4,
13.1-13.4

**Electronic submissions:**** **Exercises 11.17, 13.3, 13.8,
13.13, 13.24, 13.28, 13.29

**Possible
quiz questions: **

·
Exercises 12.1, 12.2, 12.3, 12.13, 12.14

· Give an informal proof of Euclid’s Theorem
(Slide 12.4.c)

**March 15**

**Covered slides:**** **15.1.a
– 15.4.c

**Textbook reading:**** **Sections 15.1-15.10

**Electronic submissions:**** **Exercises 15.2, 15.13, 15.14, 15.15, 15.18 [2 points], 15.21 [2 points]

**Possible
quiz questions: **

- State
the Axiom of Extensionality (write it as a formula), and then explain its
meaning using naturally-sounding English.
- Do the
same for the Axiom of Comprehension.
- Write a
formula saying that
is a subset of*a*, without using the "subset" symbol, which is not in the official language of set theory (remember that the latter only has two predicate symbols:*b***=**and**Î**). - Write a
formula in the official language of set theory saying that
is the singleton set of*a*.*x* - Write a
formula saying that
*c*and*a*, without using the "intersection" symbol, which is not in the official language of set theory.*b* - Do the
same for union.
- Exercises 15.19, 15.20, 15.22, 15.24

**March 22**

**Covered slides:**** **15.5.a
– 15.9.b

**Textbook reading:**** **Sections 15.5-15.9

**Electronic submissions:**** **Exercises
15.34, 15.35, 15.36, 15.37, 15.38, 15.53 [2 points],
15.66

**Possible
quiz questions: **

- Do what Slide 15.5.a asks you to do.
- Write
the set through which we would model the ordered 4-tuple
*<a,b,c,d>**.* - Exercises 15.27,
15.28, 15.40, 15.59-15.65
- The
definitions of the six properties (transitivity, reflexivity, etc.) given
on Slide 15.6.a
- The
definitions of "equivalence relation", "equivalence
class", “inverse”.

- The
definition of "power set", "Russell set" and
"universal set".
- Propositions
13 and 12 with proofs.
- Prove
that naive set theory is inconsistent (Russell's paradox).

**March 29**

**Covered slides:**** **15.10.a
– 16.4.a

**Textbook reading:**** **Sections 15.10-16.4

**Electronic
submissions:**** **Exercises 13.40, 13.41, 13.42, 13.43, 13.44, 13.46, 13.47, 13.48

**Possible
quiz questions: **

· Exercises 15.71

· Let ** S** and

· What kinds
of sets are said to be countable?

· Give an
example of an infinite but countable set different from those given on Slides
15.10.d-15.10.e

· Prove that
the set of all real numbers from the interval ** [0,1)**
(

· Prove the
same about the set of ALL real numbers.

· State
Cantor’s theorem.

· Exercises
16.1, 16.2, 16.7

· By
induction, prove that, for every natural number ** n**,
the sum of the first

· Express, using the formal language of Peano Arithmetic (given on Slide 16.4.a), the
following: (1) "** x**
is even''; (2) "

· What does Godel's Incompleteness Theorem say?

**April 5**

**Covered slides:**** **16.4.b
– 16.7

**Textbook reading:**** **Sections 16.4-16.7

**Electronic submissions:**** **Exercises 16.29, 16.30, 16.31, 16.32[2 points], 16.33, 16.34,
16.35

**Possible
quiz questions: **

·
What does Godel's first
Incompleteness Theorem say?

·
What does Godel's second
Incompleteness Theorem say?

·
What is a total strict ordering?

·
State the strong induction principle (either as a
formula/axiom or as a rule of inference).

**April 12**

**Covered slides:**** **17.1.a
– 17.2.e

**Textbook reading:**** **Sections 17.1 –
17.2

**Electronic submissions:**** **Exercises 16.36[3pt], 16.37[3pt], 16.38, 16.39. NOTE: Now and later, in
some exercises, you may want to use the *Lemma*
mechanism. How it works is explained in Section 10.6.

**Possible quiz questions: **

·
All definitions from Slides 17.1.a - 17.1.b.

·
The definitions of formal consistency and formal
completeness.

·
Exercises 17.5, 17.6.

·
Prove Proposition 1.

· Prove Lemma
2.

· Proofs of
Proposition 4 and Lemma 5. These proofs, if complete, have to
deal with several cases (conjunction, disjunction, negation, implication,
biconditional). You should be able to handle just two or three cases, so that
you can demonstrate your overall understanding of the method of induction used
here.

**April 19**

**Covered slides:**** **17.2.f
– 17.4.i

**Textbook reading:**** **Sections 17.2 – 17.4

**Electronic submissions:**** **Exercises 16.40, 16.41, 16.42, 16.43, 16.44, 16.45, 16.46,
16.47

**Possible quiz questions: **

·
Prove Proposition 6.

·
The (first) proof
from "Putting things together" (p. 492-493).

·
State the Compactness Theorem for propositional logic and
prove it.

·
Exercises 17.7 (without the electronic submission part),
17.8.

·
You should be able to apply the satisfaction algorithm (Slide
17.3.e, formerly 17.3.c) to any Horn sentence to determine whether it is satisfiable or not.

·
Exercises 17.33, 17.35, 17.36, 17.42, 17.43