Course Description

The material covers all of first-order logic, except the use of functions is only mentioned at the end. The content of the course focuses on showing how logic can be useful for understanding communication, expecially by logical implication and conversational implicature.

Logic Notes

My notes for introductory formal logic.

Truth Table Problems

Practice your ability to do truth tables by doing the following homework problems with answers. Let me know if you spot any errors.

Practice Exams

Practice quizzes on informal validity: Q1, Q2, Q3, with answer keys Q1, Q2, Q3.

Practice Exams on Propositional Logic with Truth Tables: A1, A2, A3, A4, with answer keys A1, A2, A3, A4.

Practice Exams on Propositional Logic with Truth Trees: B1, B2, B3, with answer keys B1, B2, B3.

Practice Exams on Predicate Logic: C1, C2, C3, C4, with answer keys C1, C2, C3, C4.

Practice Exams on Relational Logic with Equality: D1, D2, D3, D4, with answer keys D1, D2, D3, D4.

Practice Final Exams: E1, E2, E3, with answers E1, E2, E3.

Translation Problems

Practice your translations of propositional logic by doing the following homework problem sets in order: ST1, ST2, ST3, ST4, ST5, ST6, ST7 with answers ST1, ST2, ST3, ST4, ST5, ST6, ST7. Let me know if you spot any errors.

Quantifier Translation Practice Problems

I have prepared practice problems for translating sentences with quantifiers QT1, QT2, QT3, and the corresponding answer keys QT1, QT2, QT3.

Sentential Truth Trees

Practice a bunch of them and then check your answers.

Note that you can have a correct answer that doesn't match the one I have provided because there is no single correct order for discharging the complex formulas.

Predicate Truth Tree Practice Problems

Next week, you should practice truth tree problems and check your answers.

Program Announcement

For your general entertainment and edification, I heartily recommend subscribing to the "In Our Time" podcast. It's a BBC program where the host guides 3 professors through a given topic in 40 minutes. The topic during the week of October 21, 2010, was the history of logic.

Further Reading

If you are interested in learning about the history of how logic relates to the foundations of mathematics, have a look at Giaquinto's The Search for Certainty.

Further Reading

Ian pointed out a poem that may help you to remember the proof for the unsolvability of the halting problem.

Grading Scale

The scale for translating your final numerical grade into a letter is as follows: First, round off your grade to the nearest whole number.

85+ A
75+ B
60+ C, Pass

Also note that in the syllabus, it says there are three quizzes and one homework each worth 6%. But the abacus homework is counting for one of the quizzes.

Abacus Computer Program Homework

Here are my answers to the homework problems:

Abacus Computer Programs

Here are my answers to the problems in the textbook. Let me know if you spot any errors.

This program takes the first register n and second register m and puts the product mn into the third register.

This program takes the first register n and second register m and puts the exponential m^n into the third register. The exit arrow with "Function is undefined" could be supplemented to add a pebble to some register. to signify that zero to the zero power is not a well-defined quantity.

This program takes the first register n and second register m and puts the super-exponential m^^n into the third register.

Extra Abacus Computer Practice Programs

Consider the following programming tasks for calculating functions of rational numbers. Let us represent the rational number p/(q+1) in a pair of registers as [p, q]. (The reason I put in the +1 was to ensure that any inputted pair [p, q] would count as a legitimate rational number. Otherwise, a program would need to verify that the denominator is not zero.)

The answers are posted at the bottom of this page.

Problem 1. Program an abacus computer to multiply two rational numbers while preserving the inputs. For example, an input of

[2, 2, 5, 6, 0, 0]

should result in

[2, 2, 5, 6, 10, 20] to represent that 2/3 x 5/7 = 10/21.

Problem 2. Program an abacus computer to add two rational numbers while preserving the inputs. For example, an input of

[2, 2, 5, 6, 0, 0]

should result in

[2, 2, 5, 6, 29, 20] to represent that 2/3 + 5/7 = 29/21.

Problem 3. Program an abacus computer to calculate the remainder when p is divided by q+1 while preserving the inputs. For example, an input of

[5, 2, 0, ...]

should result in

[5, 2, 2, ...].

Homework Assignment

Turn in this assignment by Tuesday, November 23.

Problem 1: Program an abacus machine to calculate n! where n is the number of pebbles in register one at the start of the program and where the ! function is the factorial function. 0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, etc. In general, (n+1)! = (n+1)n!

Problem 2: Program an abacus machine to calculate the product of two integers. Represent the first integer x with the number p-q, where p is the number of pebbles in register one and q is the number of pebbles in register two. Represent the second integer y similarly using registers three and four. Output the product xy in the same form using registers five and six.

For example, the input

[ 0, 3, 2, 0, 0, 0, .... ]

Should result in the output

[ 0, 3, 2, 0, 0, 6, ... ]

to represent that -3 times +2 equals -6.

And the input

[ 0, 3, 0, 5, 0, 0, .... ]

Should result in the output

[ 0, 3, 0, 5, 15, 0, ... ]

to represent that -3 times -5 equals +15.

You are not required to preserve the values of the first four registers.

Optional Problem 3: (For bonus credit!) Find r(4), where r(n) is the longest running time of any abacus computer program that has exactly n nodes, starts with all registers empty and eventually halts with all registers empty. Describe briefly how you did it. You do not need to prove to me that your answer is the correct one. Just find the correct answer.

Answers to the Fourth Exam...

are now available. Read Charlie's advice column as well.

Quiz on First Order Logic

Here is what I would have written for an answer:

First order logic is the full quantifier logic with equality and functions. That is, it includes propositions and all the standard truth-functional connectives, constants, variables that range over individuals, predicates/relations of arbitrary adicity, functions of arbitrary adicity, and the equality relation. Unlike second order logic, the variables of first order logic do not range over predicates/relations or functions.

First order logic is complete, which means that there exist proof systems such that all valid arguments have a proof in that system. By contrast, Peano Arithmetic and second order logic are incomplete.

First order logic is undecidable, which means that there is no effective procedure for determining definitively in all cases (in a finite number of computational steps) whether a given argument is valid/invalid or whether a given set of sentences is consistent/inconsistent. By contrast, propositional logic decidable. Also decidable is the monadic (i.e. no relations) predicate logic with equality but without functions.

Unlike second order logic, first order logic is not powerful enough to express the axiom of finitude, which states that only finitely many things exist. Nor can it express the idea that only a countable infinity of things exist.

The most prominent problem that every student had was an inability to state what first order logic was. Everyone left out that it includes an equality symbol and functions.

Also, many students confused first order logic with a proof system. There are many different proof systems for first order logic. Some are natural deduction systems, some are truth tree systems, and there are other kinds of systems as well. The terms 'sound' and 'complete' apply primarily to proof systems, not to first order logic itself. However, we can say that first order logic is complete, by which we mean thatthere exist proof systems for first order logic that are complete.

Clarification of Digression in Class

A discussion in class was whether if you have the axiom ∀xy(Pxy ⊃ Axy), the following two turn out to be equivalent: ∀xyz((Axy & Ayz) ⊃ Axz) and ∀xyz((Pxy & Ayz) ⊃ Axz). We should suspect that they are not because the axiom asserts an asymmetrical dependence. However,

The inference from ∀xy(Pxy ⊃ Axy) & ∀xyz((Axy & Ayz) ⊃ Axz) to ∀xy(Pxy ⊃ Axy) & ∀xyz((Pxy & Ayz) ⊃ Axz) can be seen to be valid by the method of conditional proof:

1. Assume Pxy & Ayz.
2. Use Pxy ⊃ Axy to derive Axy & Ayz.
3. Use (Axy & Ayz) ⊃ Axz to derive Axz.
4. Conclude unconditionally that (Pxy & Ayz) ⊃ Axz.

In the other direction, the inference does not hold. Here is a counterexample:

f ----A-----> g ---A---> h

It has a failure of ancestor transitivity but because it has no parental relations, the set { Pfg ⊃ Afg, (Pfg & Agh) ⊃ Afh, ~((Afg & Agh) ⊃ Afh)} is true. Hence its generalization is a counterexample to the inference being tested.

However, what we intuitively know about ancestors is each of everyone's ancestors is connected by a finite chain of parenthood relations. Thus, if we could get express that Axy implies a finite chain of Px(w1), P(w1)(w2), P(w2)(w3), ..., P(wn)y, then we could derive ∀xy(Pxy ⊃ Axy) & ∀xyz((Axy & Ayz) ⊃ Axz) from ∀xy(Pxy ⊃ Axy) & ∀xyz((Pxy & Ayz) ⊃ Axz).

Practice Exams

The fourth exam will be like the practice exams in that it will include translations that have more complicated translations, including ones with equality. It will include a few problems where you need to identify whether the model is reflexive, symmetric, etc. And the truth trees can include functions and equality and arbitrary complexity in the quantifiers.

For the exam, I will let you use the relaxed rules so that if you have multiple disjuncts or conjuncts, you don't need to use any internal parentheses. You still need to use parentheses everywhere it makes a difference to the meaning of the statement.

Answers to the Third Exam...

are now available. Read Charlie's advice column as well. Be aware that because I made an error typing the formula for problem 19, the tree in my answer closes. Your tree for 19 should be open because your first formula included a Py instead of an Fy.

Check your answers to verify that your exam was scored correctly. If you think your translation answer is logically equivalent to the one in the answer key, mark that problem and resubmit your exam to Charlie for reappraisal. Because there is an infinite number of statements that are logically equivalent to the correct answer, it is easy for us to miss a correct but roundabout answer.

Practice Exams on Relational Logic with Equality: D1, D2, D3, D4, with answer keys D1, D2, D3, D4.

Ontological Argument Assignment

The assignment is to prove the claims in the Anselm and Actuality paper that the arguments using 3b and 3d are invalid, the one using 3a is valid, and that 3c implies 3a.

Remember to include the auxiliary premise, Wa, which states that the actual world is a world.

Here are the relaxation of the rules.

(I) You may write nested conjunctions or discjunctions without parentheses and discharge them as a single unit.

For example,
1. A & ~B & C & (D ∨ E) & F
2. A 1, &
3. ~B 1,&
4. C 1,&
5. D ∨ E 1,&
6. F 1,&

For another example,
1. A ∨ ~B ∨ (E & D)
. . | . . | . . . . \
2. A . . ~B . . (E & D) 1, ∨

The dots in the above only exist in order to allow the spacing to be displayed properly.

(II) You may instantiate multiple variables in a single step.

For example,
1. ∀xyz((x=z & y=z) ⊃ x=y)
2. ((a=b & c=b) ⊃ a=c) 1,∀

For another example,
1. ∃x∃y(Fxy & x≠y)
2. Fab & a≠b 1,∃

Remember that using the ∃ rule requires you to introduce new constants for all the variables you are instantiating, and they must differ from each other as well.

Review Notes

A few clarifications.

The exam only covers quantifier translation and quantifier truth trees, including problems that involve both. I also expect you to know how to evaluate logical equivalience using truth trees as in sample test C4.

In your truth trees, I prefer that you use QE to mark your use of the quantifier exchange rules instead of ~∃ and ~∀, but I will accept either of these last two. You may feel free to use QE to move a negation sign through multiple quantifiers.

The expression ∀xyHxy is shorthand for ∀x∀yHxy. If you like, when you have multiple quantifiers of the same type, you can instantiate them all in a single step. For example, you may do the following.

1. ∀x∀y∃zHxyz
2. ∃zHabz _ _ _ 1, ∀

Do not attempt to instantiate multiple variables when the quantifiers are different or if they are not all together in the outermost scope.

On every truth tree that ends up open, you need to use every universal quantifier at least once before you call it quits on the constructing the tree.

Probability Logic Problems

For each argument below, figure out whether it is valid. If it is invalid, draw a diagram that serves as a probabilistic counterexample. If it is valid, draw a diagram that illustrates why it is valid, providing an explanation in your own words for why it does not have any counterexamples.

1. ~(A & B)
    Thus, A=>~B

2. A=>B
   (A&B)=>C
   Thus, A=>C

3. A=>(BvC)
    A=>B
    Thus, A=>~C

4. A
    Thus, AvB

5. B
    Thus, A=>B

6. ~A
    Thus, A=>B

Here are the answers.

Second Exam

Check your exam against the answers, and verify that your score has been added correctly.

A Few Tips to Use When Translating...

Anytime you see 'only if', just scratch it out and replace with a ⊃. That way, you won't accidently treat what follows it as an antecedent.

In order to get the direction of the conditionals correct, mark what follows any 'if' as an antecedent. The antecedent is the iffy clause. It is easy to confuse A if B and If A, B.

When translating an argument that you will then do the truth table for, triple check your translation. You do not want to redo a truth table. Takes too much time.

If your hand writing is bad, you can use + instead of &, and use O's for true and X's for false.

Quiz Answers...

are now available.

Extra Abacus Computer Practice Programs

Here are the answers to the problems listed above.

Problem 1. Program an abacus computer to multiply two rational numbers while preserving the inputs.

Problem 2. Program an abacus computer to add two rational numbers while preserving the inputs.

Problem 3. Program an abacus computer to calculate the remainder when p is divided by q+1 while preserving the inputs.