15-251: Great Theoretical Ideas in Computer Science Lecture 3

Logic
Logic:

Logic
a formal game played with symbols which turns out to be useful for modeling mathematical reasoning. a formal game played with symbols which turns out to be useful for modeling the world.

Math:

Propositional (0th order) Logic

A model for a simple subset of mathematical reasoning

Propositional (0th order) Logic

Not And Or Implies If And Only If

Propositional (0th order) Logic

An English statement that can be true or false Potassium is observed. Hydrogen is observed. Pixel 29 is black. Its raining. Propositional variable: a symbol (letter) representing it k h p29 r

Compound sentence
Potassium is not observed. At least one of hydrogen and potassium is observed. If potassium is observed then hydrogen is also observed.
If Im not playing tennis then Im watching tennis, and if Im not watching tennis then Im reading about tennis.

Propositional formula k (hk)

(kh)

((pw)(wr))

Formally, formulas are strings made up of:

Well-formed formula (WFF)

= A string which is syntactically legitimate. WFF x1 ((x1(x3x2))x1) ((x10x11)(x2x5)) not a WFF x1 ))x2 ((x1(x3x2))x1)

( ) x1 , x2 , x 3 ,

(punctuation) (punctuation) (not) (and) (or) (implies) (if and only if) (variable symbols)

Well-formed formula (WFF)

Formally, WFFs have an inductive definition: Base case: Single variables are WFFs.

Inductive rules: If A is a WFF, so is A . If A, B are WFFs, so are (AB) , (AB) , (AB) , (AB) .

Lets talk about TRUTH.

If potassium is observed then carbon and hydrogen are also observed. (k(ch))

If potassium is observed then carbon and hydrogen are also observed. (k(ch)) Whether this statement/formula is true/false depends on whether the variables are true/false (state of the world). If k is T, c is T, h is F If k is F, c is F, h is T the formula is False. the formula is True.

Q: Is this statement true? A: The question does not make sense.

Truth assignment V : assigns T or F to each variable

Extends to give a truth value V [S] for any formula S by applying these rules:
A F F T T B F T F T A T T F F (AB) (AB) (AB) (AB) F F T T F T T F F T F F T T T T

Truth assignment example

S = (x1(x2x3)) V: x1 = T x2 = T x3 = F

V [S] = (T(TF)) V [S] = (TF) V [S] = F

Satisfiability
satisfies S: V [S] = T S is satisfiable: there exists V such that V [S] = T S is unsatisfiable: V [S] = F for all V S is a tautology: V [S] = T for all V

All well-formed formulas

unsatisfiable (kk) satisfiable (k(ch)) tautology (hh)
Potassium is observed and potassium is not observed. If potassium is observed then carbon and hydrogen are observed. If hydrogen is observed then hydrogen is observed.

S = ((x(yz))((xy)z))
Tautology: automatically true, for purely logical reasons Truth table
x
F F F F T T T T

Unsatisfiable: automatically false, for purely logical reasons

Satisfiable (but not a tautology): truth value depends on the state of the world

y
F F T T F F T T

z
F T F T F T F T

((x(yz))((xy)z))

S = ((x(yz))((xy)z))
Truth table
x
F F F F T T T T

S = ((x(yz))((xy)z))
Truth table
x
F F F F T T T T

y
F F T T F F T T

z
F T F T F T F T

((x(yz))((xy)z))
T

y
F F T T F F T T

z
F T F T F T F T

((x(yz))((xy)z))
T T T T T T T T

S is satisfiable!

S is a tautology!

Deciding Satisfiability / Tautology

Truth table method:
Pro: Always works Con: If S has n variables, takes 2n time

Another open problem about truth tables: who invented them?

Conjectures:
There is no polynomial time algorithm that works for every formula. There is no O(1.999n) time algorithm that works for every formula.

Russell?

Wittgenstein?

Post?

Peirce?

ukasiewicz?

Jevons?

LaddFranklin?

Logical Equivalence
Definition: Formulas S and T are equivalent, written S T, if V[S] = V[T] for all truth-assignments V. I.e., their truth tables are exactly the same.

Example equivalences
(xy) (xy) (AB) (AB) AB (AB) AB ((AB)(BA)) A A (AB) (BA) ((AB)C) (A(BC)) remark: so its okay to write (ABC) AA A ((AB)C) ((AC)(BC)) etc.

Problem: Show (((xy)x)y) is a tautology. Solution 1: Truth-table method Solution 2: Use equivalences: = (((xy)x)y) (using AB AB ((xy)x)y (using (AB) AB ((xy)x)y (using (AB)C A(BC) (xy)(xy) (using AB AB (xy)(xy) SS, where S = (xy).

Logical entailment
Is S a tautology? moderately interesting
) ) ) )

Assuming axioms A1, , Am, is S a logical consequence (theorem)?

And a formula of the form SS is always a tautology.

more typical kind of thing to be interested in

Logical entailment
Definition: Formulas A1, , Am entail formula S, written A1, , Am S, if every truth-assignment V which makes A1, , Am equal T also makes S equal T. S is a logical consequence of A1, , Am.

Entailment examples
x, y (xy) A, B (AB) for any BA (AB) for any B A, AB B AB, BC AC Ax, Bx AB etc. fact: iff A1, , Am S (A1Am)S is a tautology

Any questions about propositional logic?

1st order logic

A model for pretty much all mathematical reasoning

Not, And, Or, Implies, If And Only If Plus: For All (), There Exists (), Equals (=) constants, relations, functions Variables like x now represent objects, not truth-values.

Alex is smarter than everyone: x IsSmarter(a,x) variable: stands for an object (person)

constant name: stands for a particular object relation name: stands for a mapping, object(s) T/F

Alex is smarter than everyone: x IsSmarter(a,x) Alex is smarter than everyone else: x ((x=a)IsSmarter(a,x))

Alex is smarter than everyone: x IsSmarter(a,x) Alex is smarter than everyone else: x ((x=a)IsSmarter(a,x)) Alexs father is smarter than everyone elses father: x ((x=a)IsSmarter(Father(a),Father(x))) function name: stands for a mapping, object(s) object

propositional logic, as usual equality (of objects)

Vocabulary: A collection of constant-names, function-names, relation-names. Vocabulary from the previous slide: one constant-name: one function-name: one relation-name: a Father() IsSmarter(, )

Vocabulary: A collection of constant-names, function-names, relation-names. Another example of a vocabulary: one constant-name: two function-names: one relation-name: a Next(), Combine(, ) IsPrior(, )

Example (well-formed) sentences: x (Next(x)=a) x y (IsPrior(x,Combine(a,y)) (Next(x)=y)) (x IsPrior(x,Next(x))) (Next(a)=Next(a))

x (Next(x)=Combine(a,a))
Q: Is this sentence true? A: The question does not make sense.

Lets talk about TRUTH.

Whether or not this sentence is true depends on the interpretation of the vocabulary. Interpretation: Informally, says what objects are and what the vocabulary means.

x (Next(x)=Combine(a,a))
Q: Is this sentence true? A: The question does not make sense. Whether or not this sentence is true depends on the interpretation of the vocabulary. Interpretation: Specifies a nonempty set (universe) of objects. Maps each constant-name to a specific object. Maps each relation-name to an actual relation. Maps each function-name to an actual function.

x (Next(x)=Combine(a,a))
Interpretation #1:
Universe = all strings of 0s and 1s a = 1001 Next(x) = x0 Combine(x,y) = xy IsPrior(x,y) = True iff x is a prefix of y

For this interpretation, the sentence is

False

x (Next(x)=Combine(a,a))
Interpretation #2:
Universe = integers a=0 Next(x) = x+1 Combine(x,y) = x+y IsPrior(x,y) = True iff x < y

x (Next(x)=Combine(a,a))
Interpretation #2:
Universe = natural numbers a=0 Next(x) = x+1 Combine(x,y) = x+y IsPrior(x,y) = True iff x < y

For this interpretation, the sentence is

True

For this interpretation, the sentence is

False

Satisfiability / Tautology
Interpretation I satisfies sentence S: I [S] = T S is satisfiable: there exists I such that I [S] = T S is unsatisfiable: I [S] = F for all I S is a tautology: I [S] = T for all I

All sentences in a given vocabulary

unsatisfiable x (Next(x)=Next(x))

satisfiable

x (Next(x)=Combine(a,a)) tautology (x(x=a))(Next(a)=a)

Tautology: automatically true, for purely logical reasons Unsatisfiable: automatically false, for purely logical reasons Satisfiable (but not a tautology): truth value depends on the interpretation of the vocabulary

(y x (x=Next(y))) (w z (w=z))
Problem 1: Show this is satisfiable. Lets pick this interpretation: Universe = integers, Next(y) = y+1. Now (y x (x=Next(y))) means theres an integer y such that every integer = y+1. Thats False! So the whole sentence becomes True. Hence the sentence is satisfiable.

(y x (x=Next(y))) (w z (w=z))
Problem 2: Is it a tautology?

(y x (x=Next(y))) (w z (w=z))
Problem 2: Is it a tautology? Solution: Yes, it is a tautology!

There is no truth table method. You cant enumerate all possible interpretations! It seems like you have to use some cleverness

Proof: Let I be any interpretation. If I [y x (x=Next(y))] = F, then the sentence is True. If I [y x (x=Next(y))] = T, then every object equals Next(y). In that case, I [w z (w=z)] = T. So no matter what, I [the sentence] = T.

(y x (x=Next(y))) (w z (w=z))
Problem 2: Is it a tautology?

Checking tautologies

Hmm Its really a shame that theres no truth table method. Is there any mechanical method?? Gottlob Frege

&

invented the idea of Deductive Calculus David Hilbert

A fixed set of rules for deducing new tautologies from known tautologies.

A, E.g.,

A B B

Checking tautologies
Open almost any textbook on logic. Page 1 will have some Deductive Calculus, like: Base Case tautologies / tautology families:
1. AA is a 1st order tautology for any sentence A 2. In fact, given any tautology in propositional logic, you can replace its variables with sentences to get a 1st order tautology 3. x y ((x=ay=b)(Func(x,y)=Func(a,b))) 4. IsR(a)(x IsR(x)) 5. blah blah blah, a bunch more obviously tautological kinds of sentences

Easy claim: anything deducible is indeed a 1st order tautology. Question: is every tautology deducible?

Kurt Gdel

His PhD thesis: Yes! Gdels COMPLETENESS Theorem

Deduction rule:

From A and AB can deduce B

Checking tautologies
Consequence: There is a purely mechanical (algorithmic) way to verify that a given S is a tautology. Just brute-force search for the shortest proof in Deductive Calculus!

Logical entailment
Is S a tautology of 1st order logic? moderately interesting Assuming axioms A1, , Am, is S a logical consequence (theorem)?

more typical kind of thing to be interested in

Logical entailment
Definition: Formulas A1, , Am entail formula S, written A1, , Am S, if every interpretation I which makes A1, , Am equal T also makes S equal T. Equivalently, (A1Am)S is a tautology.

Typical use of 1st order logic in math

1. Think of some universe you want to reason about. 2. Invent an appropriate vocabulary (constants, functions, relations). 3. Start with some axioms which are true under the interpretation you have in mind. 4. See what theorems these axioms entail.
(By Gdels theorem, equivalent to what you can deduce from the axioms in Deductive Calculus.)

Example 1: Euclidean geometry

Euclids Axioms:
1. To draw a straight line from any point to any point. 2. To produce a finite straight line continuously in a straight line. 3. To describe a circle with any center and radius. 4. That all right angles are equal to one another.

Example 1: Euclidean geometry

Euclid

5. If a straight line falling on two straight lines make the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which are the angles less than the two right angles.

Alfred Tarski He did it right. In his interpretation, universe is the points of R2.

Example 1: Euclidean geometry

constant-names, function-names: relation-names: axioms:
x1 x2 IsSameLength(x1,x2,x2,x1) x y z IsSameLength(x,y,z,z)(x=y) x y IsBetween(x,y,x)(y=x) Segment Extension: x1,x2,y1,y2 z IsBetween(x1,x2,z)IsSameLength(x2,z,y1,y2) 7 more

Example 1: Euclidean geometry

Cool fact (proved by Tarski): These 11 axioms are complete for Euclidean geometry. For every true statement S in Euclidean geometry, {A1, , A11} S.

none

IsBetween(x,y,z) IsSameLength(x1,x2,y1,y2)

10

Example 2: Arithmetic of
constant-name: function-names: axioms: 0 Successor(x) Plus(x,y) Times(x,y)

Example 2: Arithmetic of
Question: How complete are those 7 axioms? Answer based on 125 years of experience: Pretty darn complete. Almost all true statements about arithmetic can be deduced from them.
Four-Square Theorem, Prime Number Theorem, FLT (?)

Giuseppe Peano x (Successor(x)=0) x y (Successor(x)=Successor(y))(x=y) x Plus(x,0)=x x y Plus(x,Successor(y))=Successor(Plus(x,y)) x Times(x,0)=0 x y Times(x,Successor(y))=Plus(Times(x,y),x) Induction: For any parameterized formula F(x), (F(0)(x F(x)F(Successor(x)))) x F(x)

We do know one or two tricky theorems which Peanos axioms dont entail (see Lec. 24)

Example 3: Set theory

constant-names, function-names: none relation-name: IsElementOf(x,y) [xy] axioms, catchily known as ZFC: x y ( (z zx zy) x = y ) x y z (xz yz) 7 more axiom/axiom families
Ernst Zermelo++

Example 3: Set theory

Question: How complete are those 9 axioms? Answer based on 100 years of experience: Amazingly complete! Almost all true statements about mathematics can be deduced from them. Including everything well prove in 15-251!

propositional logic: meaning of WFFs truth assignments tautology/satisfiable truth-table method equivalences entailment

Study Guide

1st-order logic: understand examples interpretations tautology/satisfiable

11