Assignment description

Solutions need to be submitted via Crowdmark. If provided with a textbox, please submit a short text answer: your TAs will not be able to provide comments if you upload images or pdfs.

Before You Begin (Not to be Handed In)

We will encounter many definitions and useful propositions during the semester. These will be used cumulatively. Make a list of the definitions you've encountered in this course (lecture, textbook, assignments). For each definition record the following:

Where did that definition appear (lecture date, page number, etc.)? This will be useful if you need to find the discussion to clarify a detail the was not initially clear, or that you have since forgotten.
Is there a real world version of the thing this definition is meant to represent?
Do you understand the definition? Are all of the parts of the definition required, or could some of them be left out without changing the meaning? If you do not understand the definition now, how do you plan to improve your understanding?
Are there any significant differences between the way the definition appears in the text and in lecture?

Make a similar list of theorems and results. Add to your lists as you do your assigned reading, and revisit them as the term progresses.

Pre-reading

We will be covering Chapter 1 of the textbook at a fairly rapid pace, with the expectation that we will finish with the Chapter by the middle of the third week. Questions on this assignment will only involve up to the end of section 1.5, but we may begin to address ideas from section 1.6 before the end of Thursday's lecture. Here are some of the key points to pay attention to in each section.

Section 1.1 (Propositional Logic). Propositional logic forms the basis for how we will interact with ideas throughout this course. It is foundational material, and absolutely essential to understand.
- 1.1.3 (Conditional Statements). One of the elements of the key sources of confusion when trying to communicate logical ideas, is that the English language does not do a good job of distinguishing between the words we use to describe conditional and bi-conditional situations. You should learn what the difference is between a conditional statement and a biconditional statement, and begin to recognize the use of inverse, converse, and contrapositive formulations.
- Section 1.1.4 (Truth Tables of Compound Propositions). We will discuss how truth tables can be used to definitively disambiguate what is meant by compound propositions, but also mention some of the limitations of this approach, especially in terms of scalability.
Section 1.2 (Applications of Propositional Logic). The idea of translating between propositional logic and English sentences will be a recurring theme throughout the course. We will not directly discuss this section in class, but will use its results implicitly. Section 1.2.6 (Logic Circuits) provides a justification for why we spend so much time talking about ∨∨, ∧∧, and ¬¬, and is at the heart of many problems in digital design.
Section 1.3 (Propositional Equivalence). Recognize the difference between a tautology, a contradiction, and a contingency. Why do we need special names for these three kinds of compound propositions? The tables in section 1.3.2 summarize a large number of equivalences. We will definitely talk about De Morgan's Laws, but you should pick one or two other equivalences from Tables 6, 7, and 8 to work through in detail. You will eventually need to understand the entire tables.
Section 1.4 (Predicates and Quantifiers). Predicates introduce variables into logical statements, so that we can make many related statements at once. Quantifiers (section 1.2.3) remove variables, so we can construct propositions from predicates. We will primarily be interested in the universal quantifier (∀∀), and the existential quantifier (∃∃). Variations of these quantifiers can make writing logical statements simpler, but make rules of logic correspondingly more complicated. Section 1.4.4 emphasizes that ∃∃ and ∀∀ are parallel to ∧∧ and ∨∨. Pay particular attention to table 2 of section 1.4.9 describing De Morgan's Laws for Quantifiers. Compare these laws with De Morgan's Laws from table 6 of section 1.3. We will see De Morgan's Laws again in section 2.2.2, applied to sets. \item Section 1.5 (Nested Quantifiers) is a fairly direct continuation of Section 1.4. The main observation is that we must be careful about the order of quantifiers when there is a combination of ∃∃ and ∀∀ involved. With multiple copies of the same quantifier, this in not a problem (compare this to the associative laws in table 6 of section 1.3.2 that let us drop parentheses in expressions involving only ∨∨ or only ∧∧). Sections 1.5.3 and 1.5.7 present the primary mathematical content of this chapter.
Section 1.6 (Rules of Inference). A logical \emph{argument} is valid when the conclusion is a consequence of the premises. Verifying that an argument is valid often amounts to checking that a particular implication is a \emph{tautology}. Pay particular attention to Definition 1 and the remark immediately following it. The named rules of inference from Table 1 of section 1.6.3 and Table 2 of section 1.6.7 will all be used extensively throughout the course. Learn how you could verify that each tautology in table 1 is in fact a tautology, and how you can turn each tautology into a rule of inference.
- Section 1.6.6 (Fallacies). Why might someone believe that a particular fallacy is a valid argument form? In many cases there is a language ambiguity at play. Each of the fallacy of affirming the conclusion and the fallacy of denying the hypothesis, involves a compound proposition that is not a tautology but is closely related (in English) to a compound proposition that is.

Submit your assignmentHelp