This homework covers material from Lecture 1: The Study of Programming Languages and Lecture 2: Classical Logic and Proofs. You will demonstrate comprehension of programming language foundations, formal reasoning, and logical systems.
All questions require written responses. Show your work where applicable, and provide clear justifications for your answers. Partial credit will be awarded based on the quality of your reasoning.
In your own words, define programming language and computation. Your definitions should capture the essential characteristics discussed in lecture.
The lecture introduced four major programming paradigms: imperative, functional, object-oriented, and logic.
Choose two paradigms and for each:
The lecture showed the "sum of even squares" problem implemented in many languages across different decades. Consider this Haskell implementation:
sumOfEvenSquares :: [Int] -> Int
sumOfEvenSquares = sum . map (^ 2) . filter even
Compare this to an imperative approach (like C or Fortran with explicit loops). Identify:
Explain what it means for a language to be:
Give one practical consequence that arises from each category.
Rust's ownership and borrowing system is formalized in its type system to prevent data races at compile time.
Explain:
Compare a language with formal foundations from birth (choose one: ML, Haskell, or Rust) to one formalized after the fact (choose one: JavaScript or C).
For each language, describe one practical consequence (positive or negative) that arose from its approach to formalization, with a specific example.
Python is described as "still being formalized" through its gradual typing system.
Explain:
Classify each of the following as a term, predicate, or formula:
Using the predicates provided below, translate each English sentence into first-order logic:
Available predicates:
Translate:
The description operator
Explain:
Construct a complete truth table for the following compound formula:
Based on your truth table, what can you conclude about the relationship between implication and disjunction?
Many students find it counterintuitive that
Explain:
Consider the following formulas. For each, determine whether it is valid (tautology), satisfiable (but not valid), or unsatisfiable (contradiction). Justify each answer.
De Morgan's Laws state:
Demonstrate the first law using a truth table. Show all columns for
The order of quantifiers matters. Explain the difference in meaning between:
Give a scenario where statement 1 is true but statement 2 is false.
Intuitionistic logic rejects the law of excluded middle (
Explain:
Translate each of the following natural language statements into formal logic using the appropriate modal operators. Identify which modal logic (alethic, deontic, epistemic, doxastic, or temporal) you are using.
In fuzzy logic, the statement "Bob is tall" might have a truth value of 0.7 (Bob is 70% tall).
Given:
Calculate the fuzzy truth values for:
Show your work using the standard fuzzy operators.
The lecture mentioned that predicate logic can sometimes express ideas similar to modal operators. For example:
Explain why this equivalence works. What does "possible worlds" semantics mean in this context?
Natural deduction proofs use introduction and elimination rules to derive conclusions from premises. This question tests your ability to read and understand proofs.
Consider the following natural deduction proof:
1. P ∧ Q (premise)
2. P (∧E₁ from 1)
3. Q (∧E₂ from 1)
4. Q ∧ P (∧I from 3, 2)
Answer the following:
Consider this proof of implication transitivity:
1. [P ⊃ Q] (assumption)
2. [Q ⊃ R] (assumption)
3. [P] (assumption)
4. Q (⊃E from 1, 3)
5. R (⊃E from 2, 4)
6. P ⊃ R (⊃I from 3-5)
7. (Q ⊃ R) ⊃ (P ⊃ R) (⊃I from 2-6)
8. (P ⊃ Q) ⊃ ((Q ⊃ R) ⊃ (P ⊃ R)) (⊃I from 1-7)
Answer the following:
For each of the following logical fallacies, explain what inference rule it superficially resembles and why the fallacy is invalid:
Affirming the Consequent: "If it rains, the ground is wet. The ground is wet. Therefore, it rained."
Denying the Antecedent: "If you study, you'll pass. You didn't study. Therefore, you won't pass."
Appeal to Ignorance: "No one has proven that aliens don't exist, so they must exist."
Define soundness and completeness for a logical system.
For each property:
Godel's Incompleteness Theorems revealed fundamental limits of formal systems.
The Curry-Howard Correspondence reveals that proofs are programs and propositions are types.
| Logic | Programming |
|---|---|
| Proposition | Type |
| Proof | Program |
| Implication | Function type |
| Conjunction | Product type |
Choose one of these correspondences and explain it in detail:
| Section | Question | Points |
|---|---|---|
| Part 1 | Q1: Languages, Paradigms, and History | 15 |
| Q2: Formal Foundations in Practice | 10 | |
| Part 2 | Q3: Building Blocks of Logic | 15 |
| Q4: Logical Operators and Semantics | 15 | |
| Q5: Alternative Logics | 15 | |
| Q6: Reading Natural Deduction Proofs | 15 | |
| Q7: Metalogic and Curry-Howard | 15 | |
| Total | 100 |