Goals of the week
- By the end of this week you will be able to explain what logic studies and name the main milestones of its history.
- By the end of this week you will be able to translate a short whodunit puzzle into statements and solve it both in the style of a formal proof and by a truth-value table.
- By the end of this week you will be able to explain informally what a decision procedure is and why truth tables give one for propositional logic.
- By the end of this week you will be able to decide whether a sentence is a statement and whether an argument is valid.
- By the end of this week you will be able to match a natural-language sentence to the weakest logical system that can express it.
- By the end of this week you will be able to recognize common formal and informal fallacies and explain why they fail.
Day 1 — What logic studies, where it came from, and one puzzle solved two ways
Today's topic in one sentence: logic is the study of correct reasoning, and we will see, on a small detective puzzle, that correctness can be checked, not just felt.
1.1 The subject of logic
Every day you draw conclusions: from a timetable you conclude when to leave home; from two witness reports you conclude that one of them is wrong. Logic does not ask whether the individual claims are true. That is the job of observation, measurement, or the sciences. Logic asks a different question: if the given claims are true, does the conclusion have to be true as well? In other words, logic studies which conclusions follow from which assumptions.
The most famous argument in logic textbooks:
Premise 1: All humans are mortal.
Premise 2: Socrates is a human.
Conclusion: Therefore, Socrates is mortal.
Logic is not interested in whether Socrates really existed. It is interested in the connection: in any situation where both premises are true, the conclusion is forced to be true. That connection is what we will learn to define precisely and to check mechanically.
1.2 A very short history
Logic as a systematic subject begins with Aristotle (4th century BCE). He catalogued valid patterns of reasoning built from sentences like "All A are B" and "Some A are B"; this is called syllogistic or term logic. A little later, the Stoic school, above all Chrysippus, studied reasoning built from whole sentences joined by "and", "or", and "if … then" — the ancestor of what we now call propositional logic.
For about two thousand years these tools changed little. In the 17th century Leibniz imagined a "calculus of reasoning": disagreements would be settled by computing, like an arithmetic problem. The idea became real in the 19th century. Boole (1847) turned the logic of "and/or/not" into algebra, and Frege (1879) invented quantifiers ("for all", "there exists"), creating modern predicate logic. In the 20th century, work by Russell, Gödel, and Turing revealed both the power and the limits of formal systems — and led directly to the theory of computation. The processor in your phone is, at bottom, Boolean logic implemented in circuits.
1.3 A game: who is guilty?
We now play a small detective game. The whole point of the game is that it can be won by pure reasoning, and in more than one way.
A laptop was stolen from an office. There are three suspects: Alice, Bob, and Carol. Two facts are known for certain:
Fact 1: Exactly one of the three is guilty.
Fact 2: Exactly one of the three statements below is false; the other two are true.
The suspects say:
Alice: "Bob did it."
Bob: "I did not do it."
Carol: "Alice did it."
Who is guilty?
We solve the puzzle step by step, and we write down the reason for every step. In Section 1.4 we will see that this style, once every allowed rule is fixed in advance, is what logicians call a formal proof.
Step 1. Alice's statement ("Bob did it") and Bob's statement ("I did not do it") say opposite things about the same fact. So they cannot both be true, and they cannot both be false. Reason: a statement and its denial always have opposite truth values.
Step 2. Therefore exactly one of the two statements by Alice and Bob is false. Reason: Step 1.
Step 3. Fact 2 says there is exactly one false statement in total. That single false statement is already located among Alice's and Bob's statements by Step 2. So Carol's statement must be true. Reason: if Carol's statement were also false, there would be at least two false statements, contradicting Fact 2.
Step 4. Carol says "Alice did it," and by Step 3 this is true. So Alice is guilty.
Step 5 (verification). Suppose Alice is guilty. Then Alice's statement is false, Bob's is true, Carol's is true: exactly one false statement, and exactly one guilty person. Both facts hold, so the answer is consistent.
The second method does not search for clever steps. It simply lists every possible case and computes truth values. By Fact 1 there are only three cases: the guilty person is Alice, Bob, or Carol. In each case we compute whether each statement is true (T) or false (F), and count the false ones.
| Case | Alice: "Bob did it" | Bob: "I did not do it" | Carol: "Alice did it" | False statements |
|---|---|---|---|---|
| Alice guilty | F | T | T | 1 |
| Bob guilty | T | F | F | 2 |
| Carol guilty | F | T | F | 2 |
Fact 2 requires exactly one false statement. Only the first row satisfies this, so Alice is guilty — the same answer as before. Each cell is a small computation: for example, in the row "Bob guilty", Carol's statement "Alice did it" is false because in that case Bob, not Alice, did it.
1.4 Two methods, one guarantee
Both solutions probably feel right to you. The important point of today is that this is not merely a feeling. Each method carries its own public, checkable guarantee:
In the truth-value method, we listed all cases and computed each cell. Anyone who disagrees with the answer must point at a specific cell and show the computation is wrong — and then we can recompute that cell together. Nothing is left to taste or authority.
In the proof method (Example 1.2), every step came with a reason, and each reason is a small rule that preserves truth (for example: "a statement and its denial have opposite truth values"). If every step preserves truth and the starting facts are true, the final conclusion must be true. Again, a critic must point at a specific step.
Logicians have made this second idea fully precise. A formal proof (also called a derivation) is a finite list of statements in which every line is either a given assumption or follows from earlier lines by one rule taken from a fixed, finite list of rules. There are different classical designs for such proof systems. In Hilbert-style systems, one starts from a small stock of axioms and uses very few rules. In Gentzen-style systems (natural deduction and the sequent calculus), there are no axioms of that kind; instead there are more rules, each one modelling a single natural step of everyday reasoning. Example 1.2 is an informal ancestor of such a derivation: replace its English reasons with official rules, and it becomes a formal proof. Later in the course we will work inside one of these systems.
Here is a related classic you can try on friends. On a certain island every inhabitant is either a knight, who always tells the truth, or a knave, who always lies. You meet two inhabitants, A and B. A says: "We are both knaves."
What are A and B?
Solution by cases. There are four cases. In each, we check whether A's statement is consistent with A's type: a knight's statement must come out true, a knave's must come out false.
| A | B | "We are both knaves" | Consistent with A's type? |
|---|---|---|---|
| knight | knight | F | No — a knight cannot say a false thing |
| knight | knave | F | No — same reason |
| knave | knight | F | Yes — a knave says a false thing |
| knave | knave | T | No — a knave cannot say a true thing |
Only one case survives: A is a knave and B is a knight. The proof-style shortcut: a knight can never claim to be a knave, so A is a knave; then A's statement is a lie, so they are not both knaves, so B is a knight. Two methods, one answer, again.
Day 2 — Statements, validity, and a map of logical systems
Today's topic in one sentence: we decide which sentences logic works with, define what makes an argument valid, and see why several logical systems exist side by side.
2.1 Which sentences enter logic?
Logic works with sentences that can carry a truth value. Not every sentence can.
(a) "17 is a prime number." — A statement. It is true.
(b) "The Nile is longer than the Danube." — A statement. It is true.
(c) "There are infinitely many twin primes." — A statement. Nobody knows today whether it is true or false, but it is one of the two. Unknown truth value is not the same as no truth value.
(d) "Close the window." — Not a statement. A command is neither true nor false.
(e) "Is logic difficult?" — Not a statement. A question has no truth value.
(f) "x + 2 = 5" — Not a statement as it stands. Its truth depends on what x is. Such open sentences become statements only when x is fixed or quantified ("for every x …", "there is an x …"). We will use them heavily later in the course.
2.2 Valid and invalid arguments
Recall from Day 1 that an argument is a list of premises plus a conclusion. Now we say precisely what it means for the conclusion to follow.
All humans are mortal. Socrates is a human. Therefore Socrates is mortal.
Valid: any situation making both premises true forces the conclusion. There is no way to place Socrates inside the humans, and the humans inside the mortals, while keeping Socrates outside the mortals.
Two consequences of the definition often surprise beginners. First, validity says nothing about whether the premises are actually true. Second, an argument whose sentences are all true can still be invalid, because truth by coincidence is not the same as truth by connection.
All cats can fly. Tom is a cat. Therefore Tom can fly.
The first premise is false. But the argument is valid: in any imaginary world where all cats fly and Tom is a cat, Tom flies. A valid argument with all premises actually true is called sound. This argument is valid but not sound.
Dogs are mammals. Therefore dogs bark.
Premise true, conclusion true — yet the argument is invalid. To show invalidity we describe a counterexample situation: a conceivable world where the premise is true and the conclusion false. Imagine a world in which dogs are mammals but are mute. The premise holds, the conclusion fails. So the conclusion does not follow from the premise; both just happen to be true in our world.
Decide validity:
(a) Some students like tea. Some students like coffee. Therefore some students like both.
(b) No fish are birds. All salmon are fish. Therefore no salmon are birds.
Solution.
(a) Invalid. Counterexample situation: a class with exactly two students, one who likes only tea and one who likes only coffee. Both premises are true, the conclusion is false.
(b) Valid. In any situation, every salmon is a fish (premise 2), and no fish is a bird (premise 1); so no salmon can be a bird. No counterexample situation is possible.
2.3 A map of logical systems
Different sentences hide different amounts of internal structure, and a logical system can only certify the arguments whose structure it can see. Historically, each new system was created when natural-language arguments that are clearly correct could not be expressed in the old one. Here is the map we will follow this semester.
Syllogistic logic (Aristotle) sees sentences of four fixed shapes: "All S are P", "No S are P", "Some S are P", "Some S are not P". It handles Example 2.2 perfectly. Figure 2 shows the picture behind it.
But syllogistic logic cannot see the structure of "If the server is down and the backup fails, then the site is offline." That sentence is not about categories; it is whole sentences glued together.
Propositional logic treats whole statements as unanalyzed atoms \(p, q, r\) and studies the glue: \(\neg p\) (not), \(p \land q\) (and), \(p \lor q\) (or), \(p \to q\) (if … then). The server sentence becomes \((d \land b) \to o\). The truth-table method of Day 1 lives here. The price: propositional logic cannot look inside an atom. It sees the Socrates argument as three unrelated letters \(p, q, r\) and cannot certify it.
Predicate logic (also called first-order logic) opens the atoms. It has names for objects, predicates for properties, relation symbols for relations between objects, and the quantifiers \(\forall\) ("for all") and \(\exists\) ("there exists"). The fragment built on relations is sometimes called relational logic. Now "Every student read at least one book" gets a precise skeleton: \(\forall x\,(S(x) \to \exists y\,(B(y) \land R(x,y)))\). Predicate logic can express everything syllogistic logic can — "All humans are mortal" becomes \(\forall x\,(H(x) \to M(x))\) — and far more, such as sentences about relations between several objects, which syllogistic logic cannot touch at all.
Modal logic adds operators for modes of truth: \(\Box p\) ("necessarily p", "p must hold") and \(\Diamond p\) ("possibly p", "p may hold"). "It is possible that the flight is delayed" is not captured by any of the previous systems: it does not claim the flight is delayed, and dropping the word "possible" changes the meaning. Variants of modal logic express time ("eventually", "always from now on"), knowledge ("agent A knows that …"), and obligation ("it is required that …"); these are heavily used in computer science for verifying programs and protocols.
For each sentence, name the weakest system on the ladder that expresses its relevant structure.
(a) "No reptiles are warm-blooded."
(b) "If the power fails, the alarm rings and the doors lock."
(c) "Every guest greeted at least one host."
(d) "The meeting must take place, but it may be short."
Solution.
(a) Syllogistic: it has exactly the shape "No S are P".
(b) Propositional: three whole statements glued by "if … then" and "and": \(f \to (a \land d)\). No quantifiers over objects are involved.
(c) Predicate: "every" and "at least one" quantify over people, and "greeted" is a relation between two people. Syllogistic logic has no way to relate two quantified variables.
(d) Modal: "must" and "may" are the operators \(\Box\) and \(\Diamond\); no weaker system on the ladder expresses them.
Day 3 — Fallacies: reasoning that looks right but is not
Today's topic in one sentence: a fallacy is a common pattern of bad reasoning; formal fallacies break the form of an argument, informal fallacies break its content or context, and spotting both is a skill you will use far beyond this course.
"If it rained, the ground is wet. The ground is wet. Therefore it rained." — The mistake is in the form; replace rain and wet ground by anything and it stays broken (formal fallacy).
"He failed his driving test, so his opinion on the budget is worthless." — The form is not the problem; the premise is simply irrelevant to the conclusion (informal fallacy).
3.1 Formal fallacies
Most classic formal fallacies involve a conditional statement \(p \to q\) ("if p then q"). One fact about conditionals drives everything below: \(p \to q\) promises that whenever \(p\) holds, \(q\) holds. It promises nothing about what happens when \(p\) fails, and it does not promise the converse direction from \(q\) back to \(p\).
| Name | Form | Status | Example |
|---|---|---|---|
| Modus ponens | \(p \to q\); \(p\); therefore \(q\) | valid | If it rained, the ground is wet. It rained. So the ground is wet. |
| Modus tollens | \(p \to q\); \(\neg q\); therefore \(\neg p\) | valid | If it rained, the ground is wet. The ground is not wet. So it did not rain. |
| Affirming the consequent | \(p \to q\); \(q\); therefore \(p\) | invalid | If it rained, the ground is wet. The ground is wet. So it rained. |
| Denying the antecedent | \(p \to q\); \(\neg p\); therefore \(\neg q\) | invalid | If it rained, the ground is wet. It did not rain. So the ground is not wet. |
Why are the last two invalid? Use the counterexample test from the definition of validity: describe a situation with true premises and a false conclusion. For both fallacies the same situation works: it did not rain, but a sprinkler soaked the ground. Then "if it rained, the ground is wet" is true (the promise is never tested), "the ground is wet" is true, "it did not rain" is true — yet "it rained" is false and "the ground is not wet" is false. The wet ground has another possible cause; the conditional never excluded one.
Denying the antecedent: from \(p \to q\) and \(\neg p\), concluding \(\neg q\).
Both are invalid argument forms.
"Successful startups all have confident founders. Deniz is a confident founder, so her startup will succeed."
Analysis. The first sentence is a conditional: if a startup is successful, its founder is confident (\(s \to c\)). The second premise affirms \(c\), and the conclusion is \(s\). This is affirming the consequent. Counterexample situation: a world full of confident founders whose startups fail; both premises can hold there while the conclusion fails. Note that the conclusion may still happen to come true — the point is that these premises give it no support.
Formal fallacies are not special to conditional reasoning. Syllogistic logic, the oldest system on our Day 2 map, has its own classic mistakes. The most famous is the undistributed middle. In a syllogism, the middle term is the term that appears in both premises but not in the conclusion; its job is to link the other two terms together.
All \(A\) are \(B\).
All \(C\) are \(B\).
Therefore all \(A\) are \(C\).
(a) "All cats are mammals. All dogs are mammals. Therefore all cats are dogs."
Analysis. The middle term is "mammals". Both premises are true in the actual world and the conclusion is false, so by the counterexample test of Day 2 the form is invalid; no imagined situation is even needed. In an Euler picture (compare Figure 2), cats and dogs are two circles inside the mammal circle, and nothing forces the two inner circles to overlap.
(b) "All strong candidates give confident interviews. Emre gave a confident interview. Therefore Emre is a strong candidate."
Analysis. The middle term is "people who give confident interviews". Both premises only place things inside that class; neither covers all of it, so the link fails. Notice the family resemblance to affirming the consequent in Example 3.2: read the first premise as "if someone is a strong candidate, they interview confidently" and this is the same mistake in conditional clothing.
3.2 Informal fallacies
Informal fallacies cannot be caught by inspecting symbols; you must look at what the premises actually say and whether they are relevant, fair, and sufficient. The following twelve cover most of what you will meet in news, advertising, and arguments online. For each: the mechanism of the failure, then a short example.
| Fallacy | Mechanism of failure | Example |
|---|---|---|
| Ad hominem | Attacks the person instead of the argument; the attacker's premise is irrelevant to the claim. | "Dr. Kim argues the bridge is unsafe, but she is chronically late to meetings, so ignore her report." |
| Straw man | Refutes a distorted, weaker version of the opponent's position, not the actual one. | "You want fewer meetings? So you think teams should never communicate. Absurd." |
| False dilemma | Presents two options as the only ones when more exist, then eliminates one. | "Either we cancel the project or the company goes bankrupt." |
| Slippery slope | Claims, without justification, that one step will inevitably trigger a chain ending in disaster. | "If we allow one late submission, soon nobody will meet any deadline ever." |
| Circular reasoning | The conclusion is smuggled into the premises; the argument assumes what it must prove. | "This author is trustworthy because she never writes anything untrue." |
| Hasty generalization | Draws a general rule from a sample that is too small or unrepresentative. | "Both taxis I took in this city were late; taxis here are unreliable." |
| Post hoc ergo propter hoc | Infers causation from mere temporal order: B came after A, so A caused B. | "I wore my green shirt and we won; the shirt brought the win." |
| Appeal to popularity | Treats widespread belief or use as evidence of truth or quality. | "Millions follow this diet, so it must be healthy." |
| Appeal to inappropriate authority | Cites an authority outside their field of competence. | "A famous actor endorses this investment, so it is safe." |
| Red herring | Diverts to an irrelevant topic so the original question is never addressed. | "You ask about the missing funds? Let me tell you about our record-breaking sales." |
| Equivocation | Uses one word in two different senses and lets the argument slide between them. | "A feather is light. What is light cannot be dark. So a feather cannot be dark." |
| Appeal to emotion | Substitutes fear, pity, or pride for evidence. | "Think of how disappointed everyone will be if you vote against this." |
1. The fallacy fallacy. Showing that an argument for a claim is fallacious shows that this argument fails. It does not show the claim is false. The claim might be supported by a better argument.
2. Name plus mechanism. In this course, identifying a fallacy always means two things: the name, and a short explanation of why the premises fail to support the conclusion in this particular case. A label alone is not an analysis.
"Our competitor claims their app is more secure. But their CEO dropped out of university, so the claim is baseless. And really, either you trust our app completely or you might as well stop using the internet."
Analysis. Two fallacies. First, ad hominem: the CEO's education is irrelevant to whether the app is secure; the security claim is dismissed by attacking a person. Second, false dilemma: "trust us completely" and "stop using the internet" are presented as the only options, while obvious middle options (use the app cautiously, compare independent audits) are hidden.
"Everyone in my family takes vitamin C in winter, so it prevents colds."
Analysis. This is an appeal to popularity (and, depending on reading, a hasty generalization): family habit is not evidence of medical effect. But notice what we have not shown: we have not shown that vitamin C fails to prevent colds. That question is settled by clinical evidence, not by this analysis. We have only shown that this particular argument gives no support.
Homework — Week 1 Total: 100 points
Show your reasoning in every question; an answer without justification receives no credit. When you are done, click "Save homework as PDF" below and upload the PDF to Canvas. Your answers are saved automatically in this browser only; if you open this file on a different computer, they will not appear there. Estimated workload: 2–3 hours.
Question 1 20 points
A phone was stolen. Suspects: Petra, Quinn, and Rosa. Exactly one of them is guilty, and exactly two of the three statements below are true.
Petra: "Rosa did it."
Quinn: "I did not do it."
Rosa: "Quinn did it."
(a) Solve the puzzle in the style of a formal proof: numbered steps, with the reason for every step written down (as in Example 1.2).
(b) Solve the puzzle again with a case table (as in Example 1.3). Fill every cell with T or F, count the true statements in each row, and state which row satisfies the conditions.
| Case | Petra's statement | Quinn's statement | Rosa's statement | Number true |
|---|---|---|---|---|
| Petra guilty | ||||
| Quinn guilty | ||||
| Rosa guilty |
(c) State your verdict in one sentence and confirm that the two methods agree.
Question 2 15 points
For each sentence, state whether it is a statement, and justify your decision in one sentence (3 points each).
(a) "Shut the door."
(b) "The Pacific is the largest ocean on Earth."
(c) "Every even number greater than 2 is the sum of two primes."
(d) "n is divisible by 3."
(e) "Did you finish the reading?"
Question 3 20 points
For each argument, state whether it is valid or invalid (5 points each). If invalid, describe a counterexample situation in which all premises are true and the conclusion is false. If valid, explain why no such situation can exist. Comment where relevant on the difference between validity and the actual truth of the premises.
(a) All birds can fly. Penguins are birds. Therefore penguins can fly.
(b) If the file was corrupted, the program crashes on start. The program crashed on start. Therefore the file was corrupted.
(c) If the alarm was set, it rang. The alarm did not ring. Therefore the alarm was not set.
(d) Some apps are free. Some apps are secure. Therefore some apps are both free and secure.
Question 4 15 points
For each sentence, name the weakest system on the ladder of Day 2 (syllogistic, propositional, predicate, modal) that expresses its relevant structure, and justify your choice in one or two sentences (3 points each).
(a) "Some metals are not magnetic."
(b) "If the server is down, then email fails and backups stop."
(c) "Every student solved at least one problem."
(d) "It is possible that the meeting will be postponed."
(e) "Some horse is faster than every donkey."
Question 5 30 points
For each passage, name the fallacy (formal or informal) and explain in two or three sentences why the premises fail to support the conclusion in this particular case (6 points each). Remember the warning from Day 3: a label alone is not an analysis, and identifying a fallacy does not show the conclusion is false.
(a) "If the team trained well, they won the match. They won the match. So they trained well."
(b) "Professor Lee, a famous mathematician, says this stock will rise. So it will surely rise."
(c) "You are either fully behind our proposal, or you are against progress itself."
(d) "My neighbor's two cats are unfriendly. Cats are clearly unfriendly animals."
(e) "If we allow calculators in this exam, students will next demand laptops, then phones with internet, and before long exams will mean nothing at all."