G. Japaridze: 5930

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 B such that B is a logical consequence of A but not a tautological consequence of A.

· 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 F (or Fitch) that only includes the rules for introducing and eliminating Boolean connectives (including contradiction), plus reiteration. Section 8.3 of our textbook correctly claims that this system is sound and complete with respect to tautological consequence.

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 a is a subset of b, without using the "subset" symbol, which is not in the official language of set theory (remember that the latter only has two predicate symbols: = and Î).
Write a formula in the official language of set theory saying that a is the singleton set of x.
Write a formula saying that c is the intersection of a and b, without using the "intersection" symbol, which is not in the official language of set theory.
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 T be two sets. When do we say that: (a) |S|£|T|? (b) |S|<|T|? (c) |S|=|T|?

· 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) (0 included, 1 not) is uncountable.

· 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 n natural numbers is n(n-1)/2 (pages 466-467).

· Express, using the formal language of Peano Arithmetic (given on Slide 16.4.a), the following: (1) "x is even''; (2) "x³y"; (3) "x>y"; (4) "x=y³"; (5) "x is composite" (meaning that x is the product of two other numbers, both different from x); (6) "x is prime"; (7) "x is a divisor of y"; (8) "x is a common divisor of y and z"; (9) "x MOD y = z". NOTE: An adequate translation should contain exactly the same free variables as the translated statement.

· 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