Logic is the rules and principles of reasoning we use every day.
Logic can also mean the study of our reasoning.
Formal logical systems/logical systems: a model we create to study our reasoning.
1.2: Active Learning
Humans learn best by doing.
Tabula rasa vs constructivism
Constructivism: Students must actively build their understanding of the material..
1.3: Logic and Form
We study the form/structure of reasoning an dinferences.
Structure is a repeatable pattern.
Replacing words with symbols allows us to reveal forms.
Reasoning depends on form.
1.4: Entailment = Validity
In logic, we want to know when some logic guarantees something is true.
Deductive logical entailment/entailment.
A set of premises entails a conclusion if whenever the premises are true, the conclusion is also true.
A valid argument: the premises entail the conclusion.
1.5: Deductive vs Inductive Logic
Inductive logic: probability and likelihood.
Deductive logic: guarantee and certainty.
Principle of Charity: give people the benefit of the doubt and interpret their arguments in a reasonable way, if possible.
Chapter 2: Weird Cases of Validity
2.1: First Weird Case of Validity
Circular reasoning: the prmeise and conclusion are the same.
All circular reasoning is valid: if the premise is true, so is the conclusion.
Circular reasoning is any case of assuming what you are trying to prove.
Fallacy: a tempting but flawed form of reasoning.
Whether circular reasoning is good or bad depends on the circumstances one is in.
2.2: Second Weird Case of Validity
Reasoning from a contradiction is valid.
Contradiction - occurs when two sentneces say the opposite of each other.
Contradiction - a logical falsehood, a sentence that is necessarily false.
Contradictory set - a group of sentences that can’t be true at once.
Any argument with contradictory premises is valid.
Validity says that whenever all premises are true, the conclusion must be true. Contradictory premises satisfy this definition trivially because the premises can never be true.
The only way to show that an argument is invalid is to find a way to make the premises true but the conclusion false.
2.3: Third Weird Case of Validity
A set of premises can be empty. We can still use the definition of validity to assess the argument.
If there are no premises, the conclusion must always be true.
We can cehck the validity of an argument with an empty set of premises by checking if the conclusion is necessarily true.
Logical turth -a sentence that is necessarily true because of the laws of logic.
An argument with a logically true conclusion is always valid.
2.4: Necessary vs. Contingent
Some statements are neither necessarily true or necessarily false.
The opposite of necessary is contingent - something that may or may not be true.
Necessary truths may manifest in a wide variety of laws and backgrounds.
2.5: Augmentation
Augmentation: to add one or more premises to make an argument a new argument.
When we augment a valid argument, the new premise may add relevant or irrelevant information. It may also contradict existing premises - but the argument will always remain valid.
Induction - a set of premises may support or confirm a conclusion.
Validity is a tipping point. once information guarantees the conclusion is true, you cannot destroy validity by adding information - only by taking the information away.
Chapter 3: Argument Herooics
3.1: Identifying Arguments
Identifying arguments can be surprisingly difficult.
Argument: premises and conclusion.
Premise signals: words that indicate a premise. “Because”, “since”, “for”, “given”.
Conclusion signals: words that indicate a conclusion. “Thus”, “so”, “hence”, “therefore”.
3.2: Sentences
Anything that can carry information can be studied with logic.
Sentences can be short in pithy; some ask questions; some make comma ds.
We care interested in assertions or statements: sentences that make cleaims.
Sentences int he context of logic have truth values.
3.3: Soundness and Premise Truth
Validity doesn’t care about actual truth values; it is a hypothetical/conditional property.
Truth concerns the relationship between premises and the world.
3.4: Bivalence
Truth and falsity: truth values.
In logical systems studied in this course, there are only two possible truth values (True and False).
These are bivalent logics.
Chapter 4: Meet the Boolean Connectives
4.1: And here is the conjunction &
BOOL: a logical system, short for Boolean logic.
& is only allowed to connect two entences together; we technically shouldn’t say P&Q&R but we can infer an order of operations.
If English groups sentences clearly, we need to also group them in bool.
& - conjunction, ampersand, and
Sentences are atomic sentences/atoms - they are the building blocks of BOOL.
Complex sentences are combinations of atomic sentneces.
4.2: Or Is it Disjunction v
Disjunction, wedge, or: v.
Disjunction is connective; we can use long strings of disjunctions.
Conjuncts and disjuncts
4.3: Not to Neglect Negation ~
The third connective is ~: negation, tilde, not.
These three connectives are the Boolean connectives.
Preserve as much structure whne translating into BOOL as possible.
Negation always applies to the smallest possible scope of sentence.
Scope - how much of a sentence a connective governs.
Default: negation has a narrow scope.
4.4: Lost in Translation
Some bits are lost in translation.
BOOl helps us study how we reason.
When we translate a complex sentence into BOOL, we need to capture logical commitmnets.
Chapter 5: Features of Connectives
5.1: Scope
Scope is the extent of a connective - how much of a sentence it governs.
Each occurrence of a connective has its own scope.
Main connective - the connective with wide scope, governs the whole sentence
5.2: Arity
Arity: the number of inputs a connective takes.
If a connective takes only one input, it is unary. If it takes two inputs, it is binary.
5.3: Advanced Boolean Translations
‘Neither Pia nor Quinn is guilty’. ~P&~Q or ~(PvQ)
You can translate neither/not in two ways.
When connectives are the same time, we can allow chaining because any way of grouping yields the same result. (P&Q)&R = P&(Q&R).
This property does not hold for mixed connectives.
When you have mixed binary connectives and English doesn’t group them, you must give both translations until you know which is correct.
Ambiguity - when a word or sentence has two different but possible meanings.
Chapter 6: Semantics for BOOL - Truth Tables
Truth tables: charts showing every possible way a sentence could be true or false.
Truth table for an atomic sentence \(P\):
P
T
F
Truth functionality: the truth value of any complex sentence is dependent on the truth values of the atomic sentences it is comprised of.
P
~P
T
F
F
T
Canonical form: reference columns are alphabetical; the patterns of Ts and Fs are awlays the same.
P
Q
P&Q
T
T
T
T
F
F
F
T
F
F
F
F
P
Q
PvQ
T
T
T
T
F
T
F
T
T
F
F
F
6.2: Computing Truth Functions
BOOL has only three connectives; all are truth functional.
P
Q
~Pv(Q&P)
T
T
?
T
F
?
F
T
?
F
F
?
We begin by computing the inputs to the disjunction, which is the main connective.
P
Q
~P
Q&P
~Pv(Q&P)
T
T
F
T
?
T
F
F
F
?
F
T
T
F
?
F
F
T
F
?
Now, we can fill in the disjunction.
P
Q
~P
Q&P
~Pv(Q&P)
T
T
F
T
T
T
F
F
F
F
F
T
T
F
T
F
F
T
F
T
The number of rows in any table is \(2^n\), where \(n\) is the number of atomic sentences.
Solving Knights and Knaves problems via proof by cases.
x is a knight or knave, or y is a knight or knave. Temporarily assuming x is a knight/knave, what holds true?
Chapter 13: Reductio
13.1: Reductio ad absurdum
~Intro is paired with an informal proof method that pairs it. Proof by contradiction, reductio ad absurdom, reductio.
~Intro and Reductio: how to reason to a negation, formally and informally.
If you can make a temporary assumption and show that a contradiction results, then you know that ~assumption is true.
Constructing reductio proofs:
Start with “proof by contradiction/reductio.”
Write “assume for reductio …, we want to show a contradiction results.”
Demonstrate how a contradiction results.
Write “hence we know … by reductio. Done.”
13.2: Contradiction Principle
Tautological contradiction: # or ⊥, always F/0.
# is a sentence, not a connective. It can appear in complex sentences: P&# or ~#.
Disjoining with a tautological falsity returns the same truth sentence as the original sentence.
A contradiction entails anything.
P&~P ⇒ R
Q&~Q ⇒ R
# ⇒ R
P&~P ⇒ P&~P
Q&~Q ⇒ Q&~Q
# ⇒ #
P&~P ⇒ Q&~Q
P&~P ⇒ #
# ⇒ P&~P
Contradiction principle: only a contradiction can entail a contradiction.
TO prove an argument by reductio, we assume ~ conclusion and show that the premises and conclusions \(\to \bot\).
1. If Q, then P
2. ~P
Thus,
3. ~Q
13.3: #Intro and #Elim
Only a contradiction can entail #, any contradiction can entail #.
1. P Premise
2. ~P Premise
3. # #Intro;1,2
To introduce a tautological falsity, establish a sentence and its negation. These sentences do not necessarily need to be atomic.
#Elim: how to use a symbol that you already have. A contradiction entails anything. If you have a #, you can write anything you want and cite #Elim. (Easiest rule ever.)
We can ask metalogical questions about whether truth-tables and formal proofs always deliver the same result.
Well-designed logical systems should satisfy this above property.
We want to prove two properties:
Soundness. If we can give a formal proof of an argument, it is valid by the truth-table method.
Completeness. If an argument is valid (by the truth table method), then we can give a formal proof for it.
20.2: Proving Soundness
Any argument we can give a formal proof of in bool is valid.
Soundness is a conditional claim.
1-step soundness: if a conclusion can be proven in BOOL with a one-step formal proof, then that conclusion really is a logical consequence of the premises.
vElim and ~Intro cannot be used to justify the conclusion because they take more than one line.
20.3: Truth-Functional Completeness
TFC: the ability to express any possible truth function.
TFC concerns the expressive power of aysstem.
All sentences of BOOL are finitely long.
Classical logics: logical systems created with standard properties like bivalence and finitely long sentences.
TFC algorithm: creating a sentence of BOOL expressing a truth function, regardless of the truth function.
Disjoin the exact conditions for each truth value.
20.4: More TFC
We can prove that PROP is truth functionally complete.
Something can be TFC with ‘less’ than BOOL.
We only need two connectives, either negation or disjunction and negation.
\({\to, ~}\) is TFC
\({\iff, ~}\) is not TFC
None of the connectives alone is TFC
20.5: Nor and Nand
\(\downarrow = ~v\); NOR - not or, FFFT truth table.
| = ~&; NAND - not and, FTTT truth table.
NAND and NOR can express conjunction and negation. NAND and NOR are therefore TFC alone.
Chapter 21: Welcome to FOL
21.1: Terms - Constants and Variables
FOL: First-order Logic.
Quantifiers in the logic range over sets of objects in the domain, rather than sets of sets of objects.
IN BOOl and PROP, the smallest units of language are atomic sentences.
Atomic sentences can have parts.
Terms - objects.
Constants (names)
Variables
Names in FOL - constants; pick out the same thing.
Variables can refer to different things.
21.2: Predicates - Properties and Relations
Predicates - how we say things about objects.
Predicates must start with a capital letter.
Argument places - gaps in the predicate where we insert terms.
Number of argument places - arity.
Order of the argument places matters
Properties - predicates with one argument place.
Relations - predictes with two or more argument places.
21.3: The Identity Predicate
Identity - =.
infix - go in the middle of terms.
prefix - go before terms
Identity has three important properties - reflexible, symmetric, transitive
21.4: Atomic Sentences
The correct number of names depends on the arity of the predicate
Chapter 22: Meet the Quantifiers
22.1: All (A) and Exists (E)
Quantifier - a part of language for referring to a quantity of things
Logical symbol for all - \(\forall\)
All objects are fish - \(\forall \text{xFish(x)}\)
\(\exists\) - Existential Quantifier. Makes a claim of existence.
22.2: Variables, Free and Bound
Constants refer to the same object
Variables aren’t assigned a specific interpretation.
Examples:
Something is a dog. \(\exists \text{Dog}(x)\)
Everything is a dog. \(\forall \text{Dog}(x)\)
Some cat likes some dog. \(\exists x \exists y (\text{Cat}(x) & \text{Dog}(y) & \text{Likes}(x, y))\)
When a quantifier connects with a variable, it binds the variable.
When a variable is not bound it is free.
22.3: Well-Formed Formulas (WFFs) vs Sentences
FOL is bivalent; every sentence has exactly one truth value.
New grammatical category - an open formula, a formula with a free variable in it.
If a formula has no free variable, then it is a closed formula (i.e. a sentence).
Well-formed formulas (WFF): open and closed formulas
Chapter 23: Semantics of FOL
23.1: Names and Objects
Rule of names - each name represents one object.
Each name does not need to pick out a different object.
23.2: The Domain
Domain - the set of objects a quantifier ranges over
If you have multiple quantifiers in a sentence or multiple sentences in an argument, thye must all operate on the same domain. If this prerequisite is not met, fallacious reasoning is allowed.
23.3: Predicates and Intended Interpretations
Identity predicate = - only predicate that gets its own logical symbols.
Logical symbols are fixed parts of the system.
Intended Interpretation
Chapter 24: Aristotelian Forms
24.1: Four Aristotelian Forms
Aristotelian form - “All Ps are Q”
All dogs are running.
Ax(D(x)->R(x))
Aristotelian form - “Some Ps are Q”
Some dogs are running.
Ex(D(x)&R(x))
Boolean Definition of Conditional (BDC): Ex(~P(x)vQ(x))
Does not say some Ps are Q
Abdominable form: never translate anything with \(\exists x\) around \(\to\).
Aristotelian form: “No Ps are Q”
No dogs are running.
~Ex(D(x)&R(x))
Ax(D(x)->~R(x))
All forms:
All Ps are Q: Ax(P(x)->Q(x))
Some Ps are Q: Ex(P(x)&Q(x))
No Ps are Q: Ax(P(x)->~Q(x)) or ~Ex(P(x)&Q(x))
Some Ps are not Q: Ex(P(x)&~Q(x))
24.2: Advanced Forms
All happy dogs are running.
Ax((D(x)&H(x))->R(x))
When translating complex forms, formulas can be messy.
Drop parentheses when you can.
24.3: Vacuous Generalizations
When there are no \(P\)s, then “All \(P\)s are \(Q\)” is vacuously true.
24.4: Pairs of Contradictories
Contradictories - sentences that say the opposite of each other.
Chapter 25: FOL Equivalences
25.1: Demorgan’s for Quantifiers
~AxP(x) ⇔ Ex~P(x)
~ExP(x) ⇔ Ax~P(x)
25.2: Null Quantification
If a quantifier doesn’t bind to any variables in the formula, it is null on it.
If a quantifier is null on a formula, the quantifier is always put on wide scope.
P&AxQ(x) ⇔ Ax(P&Q(x))
25.3: Variable Switch
Variable Switch: you can uniformly substitute one variable for another.
AxP(x) ⇔ AyP(y)
ExP(x) ⇔ EyP(y)
Restrictions
All occurrences of the variable connected to the quantifier must be switched
You must have independent quantifiers binding a variable
You cannot switch a variable with scope overlap
25.4: Distribution for Quantifiers
Sometimes quantifiers distribute, sometimes not
Universal quantifier distributes over &, but Existential does not.
25.5: Prenex Normal Form and Chain of Equivalences
All quantifiers are stacked out up front in widest possible form.
25.6: Quantifier Reorder
When you have multiple stacked quantifiers of the same type, order doesn’t matter.
This text occupies the 1000th line in the markdown file used to generate this page. Woot woot!
Chapter 26: FO Necessities
26.1: FO Validities
FO validites are logical truths of FOL.
FO validites are necessary truths of First-Order Logic.
FO validities: \(a = a, ~\forall x P(x) \to \exists x ~P(x)\)
For tautologies, there is always a mechanical procedure we can use to show a tautological property. We cannot always do the same with FOL because quantifiers are not truth functional.
26.2: FO Falsities
FO falsities are necessary falsities of FOL.
We can obtain an FO falsity by negating an FO validity.
Anything in the scope of a quantifier depends on the quantifier
26.3: Truth-Functional Form Algorithm
TFFA: a tool to show which components in a sentence are ‘doing the work’ - connectives or quantifiers
Replace quantifiers with atomics, using the same atomics for the same quantifiers.
If the TFF of a sentence is a tautology, so is the original sentence.
If the quantifiers aren’t doing the work, then it can be a tautology.
26.4: The Chart
We can represent tautologies, FO validites, and logical truths in an Euler diagram.
Chapter 27: Counterexamples in FOL
27.1: Counterexamples in FOL
Because FOL is not truth functional, we assign meanings to a predicate and names.
Chapter 28: Multiple Quantifiers
28.1: Same Quantifiers
Things become more complicated when quantifiers are related to each other and have overlapping scope with multiple binding variables.
Somebody likes somebody: \(\exists x \exists y L(x, y)\)
Quantifier reorder (QRe): order doesn’t matter.
Different quantifiers and variables don’t necessarily pick out different objects
Distinctness clauses: \(~(x=y)\)
28.2: Mixed Quantifiers
Rule: pick objects for quantifiers from left to right.
A sentence is stronger than another if it entails the other, but not vice versa.
Chapter 29: Numerical Quantification
29.1: At Least
You need \(n\) existential quantifiers and enough distinctness clauses.
The number of distinctness clauses follows the progression of triangular numbers - 1, 3, 6, 10, etc.
“There are at least two dogs”: \(\exists x \exists y (D(x)&D(y)&~(x=y))\)
29.2: At Most
At most \(n\) means \(n\) or fewer, maybe none.
At most \(n\) takes \(n + 1\) universal quantifiers.
\[\forall x \forall y \forall z ((D(x) & D(y) & D(z)) \to (x=y \lor x=z \lor y=z))\]
The number of equalities is triangular.
29.3: Exactly
There are two ways to translate ‘exactly’ into FOL.
There are exactly two dogs:
\[\exists x \exists y (D(x) & D(y) & ~x = y) & \forall x \forall y \forall z ((D(x) & D(y) & D9z)) \to (x = y \lor x = z \lor y = z))\] \[\exists x \exists y (D(x) & D(y) & ~x = y & \forall z (D(z) \to (x = z \lor y = z)))\]
Short way - ‘exactly \(n\)’ can be translated as \(n\) existential quantifiers and 1 universal.
29.4: Definite Descriptions - ‘The’
Definite descriptions imply uniqueness - only one thing can fit the description.
Bertrand Russell - logical analysis of definite descriptions to solve the law of the excluded middle.
Chapter 30: Proofs in FOL - 2 Easy Ruels
30.1: Simple Informal Proofs
How do steps with qquantifiers work?
Universal Instantiation - instantiate general claim in the quantiifer for a specific claim about a particular object.
Existential Generalization - how we reason to an existential.
All these sets have the same cardinality as the natural numbers.
35.2: The Rational Numbers Q
\(\mathbb{Q}\) - rational numbers - expressed as fractions of whole numbers.
Density - between any two numbers, there exists another number.
\[\forall x \forall y \exists z (~(x=y) \to ((x < z & z < y) v (y < z & z < x)))\]
Density: means that no two rational numbers are adjacent to each other.
We can pair \(\mathbb{Q}\) with \(\mathbb{N}\) as follows: write a table where each column is the numerator and each row is the denominator, then take a snake-coil pattern for the line through the table. Every cell of the table will eventually be covered by the line.
\[\| \mathbb{N} \| = \| \mathbb{Q} \|\]
35.3: The Real Numbers R
The reals include the rationals and the irrationals.
There are different sizes of infinity - we can prove via reductio that there is no 1-to-1 correspondence between \(\mathbb{R}\) and \(\mathbb{N}\).
