Today:
ECS 20 — Lecture 3 — Fall 2013 —3 Oct 2013
Phil Rogaway
o Review of propositional logic: Boolean values, circuits and their efficiency, design problems, satisfiable and tautological formulas.
Propositional Logic “Propositional Logic” = “Sentential Logic” = “Sentential Calculus”
Universe of two points: 0 (F) and 1 (T).
Give some basic examples.
Truth tables.
Definitions of conditional and biconditionals.
Def: A well-formed formula (WFF) of the propositional logic over a set of variables P (finite or countably
infinite) (the variables may not contain any of: ( ) F T // we may alternatively use 0 and 1 for F and T
F and T are WFF
If P P then P is a WFF
If x and y are WFFs then so are: (x), (x y), (x y),
// stop here: let’s treat (xy), (x y) as “syntactic sugar”
Nothing else is a WFF.
This is an example of a recursive definition.
Formulas are just strings: sequences of symbols from an alphabet. AtruthassignmenttonPisamapt: P{F,T}.
A t.a. is also called a model.
A t.a. gives a formula a truth value (T or F) in the natural way; formally, we extend t to a t.a. on WFFs by asserting that
t(T)=T
t(F)=F
t((x y)) = t(x)t(y) t((x y)) = t(x)t(y) t((x)) = t(x)
A recursive definition.
Don’t confuse strings of symbols with their semantics (eg, the wedge in the third formula has a very different
meaning in the third formula); there is a big difference between a formal symbol and a logical operation.
In common usage we use a precedence order and omit many “unnecessary” parenthesis, adopting a convention:
(or some would put at same level as )
and right-to-left within a level (or some would say left-to-right; or some would say ill-defined).
1
Design something, say a majority circuit – returns 1 if a majority of its inputs are on. Do for 3 gates. How would you do it for 100 gates?
Describe the class NC.
Describe Disjunctive Normal Form (DNF).
Proposition: Each WFF is equivalent to one in DNF.
Give a proof, and give an upper bound on the number of two-input gates to realize any n-input functionality.
Define: a set of operators being logically complete.
Show that the following sets of operators are logically complete: {
{
{write NAND as a wedge with a bar over it).
A formula is satisfiable if some t.a. makes it true.
A set of formula is satisfiable if some t.a. makes them all true.
A formula of propositional logic is tautological (or valid) if it is true for every t.a. ⊨ (It is satisfiable if it is true under some t.a.)
Formulas and are logically equivalent , written , if a tautology.
Prop: There is an algorithm (=a precisely-describable procedure, mechanism, recipe) that, given a WFF of sentential logic, decides
– if it is a tautology.
– if it is a satisfiable.
– if it equivalent to some given, second formula.
Proof: “Truth-table algorithm” Example:
Contrapositive: ⊨ (PQ) (QP)
DeMorgan’s law:
Discuss the inefficiency of the truth-table algorithm.
Remarkable claim: no efficient means are known for any of these problems.
(We only got to about here; teaching slowly today, I guess)
2
Some simple tautologies Velleman, List from How to Prove It, p. 21, 23, 47, 49 . You can check any of these with a truth table.
Associative: P (Q R) (P Q) R P (Q R) (P Q) R
DeMorgan’s: (P Q) P Q (P Q) P Q
Idempotent: P and P P P P P
Contradiction P Q P Q P Q (P Q)
Formal Proofs
//Mention the similarities to arithmetic //laws with corresponding to addition //and corresponding to multiplication
Discuss conventional proofs vs. formal proofs.
I now discuss formal proofs, although what mathematicians – and you – will mostly be producing conventional (informal) ones.
Following from Wikipedia, Propositional Calculus. Following 14 rules
Axiom List W
A (B A)
(A (B C)) ( (A B) (AC)) A B A, A BB
A (B (A B))
A (A B), B (A B)
(A B) ((C B) ( A C B)) (A B) ((A B) C)
A (A B)
A A
(A B) (A B),
(A B) ((B A) (A B))
implication introduction
distribute hypothesis over implication conjunction elimination
conjunction introduction disjunction introduction disjunction elimination introduce negation eliminate negation
law of excluded middle eliminate equivalence introduce equivalence
(A B) (B A)
One of the reasons to have axioms like the list just given is to develop a notion of “what is provable””
We will write X ⊢Y if statement Y follows from X. Read: Y is provable from X. Turnstyle is the name of the symbol.
Formal proofs are quite different from conventional proofs, but a thesis in mathematics is that conventional proofs can be recast as formal ones. What are formal proof? They are syntactic objects in some formalized system. There are many choices one has in how to do the formulation, but here is what we would typically have: that a formal proof is a sequence of formula: 1, …, n where each i is either
– an assumption or
– an axiom (it appear on a list like Axiom List W) or
– it follows from a previous set of lines in the proof by one of
a number of enumerated rules – indeed we can make do with one rule, modes ponens, i) (A B)
… j) A
…
3
k) B
Example:
⊢ (PQ)(P R S)(SQ T) T
1. PQ assumption 2. PRS assumption 3. SQ T assumption
modes ponens
4. P
5. Q
6. P R 7. S
8. SQ
9. T
“conjunction elimination” (P Q P) applied to (1) “conjunction elimination” (P QQ) applied to (1)
“disjunction introduction” (P R P) applied to (5)
modus ponens (AB A gives B) applied to (2) and (6) “conjunction introduction” (S, Q SQ) applied to (7) and (5)
modus ponens applied to (3) and (8)
therefore
⊢ (PQ)(P R S)(SQ T) T //The given statement is provable
⊢can derive (prove) (from the — no assumptions) ⊢ can derive from
Some theorem and terms: Completeness, Soundness, and Compactness of Predicate Calculus
SOUNDNESS: ⊢ ⊨ COMPLETENESS ⊨ ⊢
COMPACTNESS: Let be a set of WFFs.
Suppose that every finite subset of is satisfiable. Then is satisfiable.
(contrapositive:
Let be a set of WFFs.
If is unsatisfiable then some finite subset of is too)
Don’t prove — want to use this in a computer-science example.
Application: TILING (Dominos)
Can you tile the with tiles of specified types (adjacent edges of the same color)
Eg:
4
Make an example where the plane is and is not tileable. Indicate that, in ecs120, common to prove that the TILING decision question is undecidable. But not our interest here. We are interested in whether the tileability of the plane for a given set of tile types is FALSIFIABLE — is there a proof of untileability? There will be if the following is true:
If the plane is untellable, it is already untileable on some finite subset of the plane.
Not an obvious claim — a priori possible that plane is untileable even though every finite rectangle of it is tileable.
To prove from compactness: Introduce a variable
P[i,j,k]: there is a tile of type k at position (i, j )
Write a boolean formula to capture
– One and only one tile per cell: P[i,j,k] P[i,j,k’] for all i,j and all k k’.
– Adjoining tiles are of compatible types. P[i,j,k] (k’P[i+1,j,k’] for all i, j, if a tile of type k’ can be put
atop a tile of type k; and so on (three more sets of rules)
Now: connect it to compactness theorem. The set is all the formulas above. If it is unsatisfiable, then some finite subset of is unsatisfiable. Let n be the largest index used by a variable in . Then the [-n..n] [-n..n] subset of the plane is already untileable.
Gamma is satisfiable iff every the plane can be tiled with tiles of the given types.
In the language you will learn in ecs120, TILING is co-RE Adding quantifiers — First order logic
“All apples are bad”
(x) (A(x) B(x)) // universe of discourse? “Some apples are bad”
(x) (A(x) B(x)) // universe of discourse?
“BILLY has beat up every boy at the Caesar-Chavez elementary school”
(x) ((Student(x) Boy(x) (xBILLY) HasBeatenUp(BILLY, x)) // universe of discourse?
Universe of discourse = what quantifiers range over. Always important to know the universe of discourse; it’s implicit or explicit in any discussion of logical formulas involving quantifiers.
All lions are fierce (x) (L(x) F(x))
Some lions do not drink coffee ( x) (L(x) C(x)) Some fierce creatures do not drink coffee (x) (F(x) C(x))
“Nobody likes a sore loser”
5
universe of discourse = human beings (is this really unambiguous?) L(x,y) – predicate – true iff person x likes y (is this really unambiguous?) S(x) – person x is a sore loser
(x) (S(x) (y) L(y, x))
(apparently, a sore loser doesn’t like even himself)
If anyone in the dorm has a friend who has the measles, then EVERYONE in the dorm will have to be quarantined.
universe of discourse – people
D(x) – person x lives in some (unspecified but understood) dorm Q(x) – person x must be quarantines
F(x,y) – person x is friends with person y
M(x) – person x has the measles (oh no!)
(x)(D(x) (y)(F(x,y) M(y))) (x)(D(x) Q(x))
Discuss the mismatch / absurdity of trying to translate English into logical formulas
People like to speak of the variables as corresponding to declarative claims in English, either true or false, and they like to speak of our WFFs as modelling English-language sentences built around if, or, and, not. If it disingenuous. We don’t use language in similar ways in math and in every-day language.
For lunch, do you want Indian or Thai?
If the US is storing and analyzing virtually everything you say on the phone or do on the
internet, then democracy is over.
The first sentence is not to be answered yes, unless you are trying to be cute. The second sentence is expressing a causal or foundational matter; it cannot be replaced by
If is irrational then democracy is over. or
is irrational
and preserve its meaning.
Don’t take seriously any claim of a meaningful relationship between logic and natural language communications.
Negating Quantified Boolean Expressions
PUSHING QUANTIFIERS
(x ) (x) () (x ) (x) ()
negate this:
(x)( y) (y>x z (z2 + 5z = y))
(x)(y) (y>x z (z2 + 5z = y)) (x) (y) (y>x z (z2 + 5z = y)) (x) (y) (y>x z (z2 + 5z = y))
(A B) (A B) (A B)
6
(x) (y) (y>x z (z2 + 5z = y))m (x) (y) (y>x z (z2 + 5z = y)) (x) (y) (y>x z(z2 + 5z y))
Example: negligible functions
A function f: N R is negligible if it vanishes faster than the inverse of any polynomial:
(c>0) (N) (n N) f (n) nc shorthand for (c)(N)(n)( c>0nNf(n)nc)
“eventually, you’re less than n-c for ANY c. Negate it:
“there is a c s.t., infinitely often, you’re bigger than n-c” Even grad students and researchers get confused about this!
= = = =
(c)(N)(n) ( c>0nNf(n)nc) (c)(N)(n) ( c>0nNf(n)nc) (c)(N)(n)( c>0nNf(n)nc) (c)(N)(n)( c>0nNf(n)nc) (c)(N)(n)( c>0nN f(n)nc)
Infinitely often, you are bigger than nc
Formalizing First-Order Logic
Below, not a formal treatment, but a formal treatment can be found in any standard logic book, eg., Enderton. In general:
vocabulary consists of:
LOGICAL SYMBOLS
1. Parenthesis ( , )
2. Sentential connectives
3. Variables v1, v2, … (name points in the universe) 4. Equality symbol: = (usually)
PARAMETERS:
1. ,
2. predicate symbols // functions from the universe U to {T, F}
3. constant symbols 4. function symbols
Important Examples
Number Theory
1. constant symbol: 0 2. predicate symbol: < 3. function symbol: S
// each names a point in the universe U
// maps a tuple of points in the universe U to a point in U
+ * E
(2-ary) (2-ary) (2-ary)
(1-ary) (successor function)
7
"Any number other than 0 is the successor of some number"
( x) ( (x=0) (y) (S(y)=x)) "2+2=4”
SS 0 = SSSS 0
Set Theory
predicate symbols: 2-ary function symbol:
Note "syntactic sugar" -- write a A instead of (a,A). But that doesn't change that is a 2-ary predicate.
"For any pair of sets, x and y, there a set x y that contains all of the elements of x and y"
(x)(y)(z) (u) (uz (ux) (u y)) Seems very spare, just \in.
What are other operators on sets, and how would we define them? A B: (another 2-ary predicate)
aA = (aA) AB = (xAxB) AB = (xBxA)
8