Благодарю за контрольную по логике)
Информация о работе
Подробнее о работе
Логика на английском / Logic in English
- 5 страниц
- 2019 год
- 0 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Нету.
Сделаны номера 2.2, 2.4, 2.5, 2.6, 2.7, 2.8, 2.10.
Math 481: Fall 2019
Second Homework Set: Due Friday, October 4
Exercise 2.1 (Philosophical Question). In our set-theoretic development of the natural numbers, we defined the number 3 to be the set
3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}.
Is this really what the number 3 is, in a philosophical sense (whatever that means)? To what
extent is the question of “what the number 3 really is” relevant to the task of representing
natural numbers as sets?
Exercise 2.2 (Philosophical Question). Should we be worried about the fact that, according
to our formal set-theoretic development of the natural and rational numbers, N is not actually
a subset of Q? Is there any way we can make sense of the (intuitively true) fact that N ⊆ Q
in the formal theory? It might be relevant to consider whether “the natural number 3” is the
same object as “the rational number 3,” both in our formal mathematical development and
philosophically.
Exercise 2.3. Identify two sentential connectives in ordinary natural English that are not
extensional, and for each find examples of sentences that illustrate the fact that they are not
extensional. (Find examples other than “necessarily,” which was given in lecture as an example).
Exercise 2.4. Give an example of formulas ϕ and ψ of SL and strings γ and δ over the alphabet
ASL such that (ϕ ∧ ψ) = (γ ∧ δ) but ϕ 6= γ.
Exercise 2.5. (a) Determine whether or not
(A → (A → B)) → B
is a tautology; if it is not, give a truth assignment that falsifies it.
(b) Determine whether or not
(¬A → (A → ¬B)) → ¬(B → A)
is satisfiable; if it is, give a truth assignment that satisfies it.
(c) If ϕ and ψ are the sentences from (a) and (b), determine whether or not
{ϕ, ψ} |= A → B.
Exercise 2.6. (a) Prove by induction on n that for all n ∈ N and A, B1, . . . , Bn ∈ Symb,
A ∨ (B1 ∧ · · · ∧ Bn) =||= (A ∨ B1) ∧ · · · ∧ (A ∨ Bn).
(b) Is it true that for all n ∈ N and A, B1, . . . , Bn ∈ Symb,
A ∧ (B1 ∨ · · · ∨ Bn) =||= (A ∧ B1) ∨ · · · ∨ (A ∧ Bn)?
Briefly explain.
Exercise 2.7. Let ϕ and ψ be sentences and Σ a set of sentences of SL. Prove or refute each of
the following assertions:
(a) If either Σ |= ϕ or Σ |= ψ, then Σ |= (ϕ ∨ ψ).
(b) If Σ |= (ϕ ∨ ψ), then either Σ |= ϕ or Σ |= ψ.
Exercise 2.8. Let ϕ = (¬A → (A → ¬B)) → ¬(B → A) be the formula from 2.5(b).
(a) Find a formula in Disjunctive Normal Form that is tautologically equivalent to ϕ.
(b) Find a formula in Conjunctive Normal Form that is tautologically equivalent to ϕ.
Exercise 2.9. On the island of knights and knaves, knights always make true statements and
knaves always make false statements, and everyone on the island is either a knight or a knave
and not both. A census taker on the island arrives at a house inhabited by a couple. The
husband answers the door and says, “If I am a knight, then so is my wife.” Can the census taker
deduce from this whether the man’s wife is a knight or a knave? If so, which is she? Explain.
Exercise 2.10. Suppose ϕ is a sentence of SL that contains each of the sentence symbols
A0, . . . , A99 and no others, and contains a grand total of 216 symbols in it without counting
parentheses. (Here we count all occurrences of symbols, including repeat occurrences of the
same symbol). Notice that with a bit of patience, I could easily write down ϕ on a single sheet
of paper. Now, suppose I ask the most powerful computer in the world, which tops out at a speed
of about 2×1017 computations per second, to compute the truth table for ϕ. (For simplicity let
us say that computing a single symbol in this truth table constitutes a single computation for our
computer, so that for instance computing the truth table for A ∨ B requires 12 computations).
Approximately how long will it take this computer to finish computing a truth table for ϕ?
Отвеченные вопросы приведены в содержании.
Нету.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
