Formal Systems Flashcards
MIU System
Alphebet system:
M, I, U
Finite and uses typographical symbols
MIU System
Recursive definition of MIU-strings
Base Clauses:
- Empty string is a MIU-string
- Each symbol of the alphabet is a MIU-string
Inductive Clause(s):
(There are three clauses for x = M, I, U)
- If x is a MIU-string, then yx is a MIU string (y is a symbol of the alphabet)
Final Clause:
- Nothing else is a MIU-string
Symbols x and y are meta-variables (Used in a recursive definiiton about other variables)
MIU System
What are the inference rules for the MIU system?
Inference rules are also called production rules
I. xI → xIU
II. Mx →Mxx
III. xIIIy→xUy
IV. xUUy→xy
Where x and y are, possibly empty, MIU-strings
Ex: (I) MI → MIU
MIU System
Axoim of the MIU-system:
MI
MIU System
What are possible derivations for the MIU system?
Derivation is a non-empty sequence of strings, such that each string is either an axoim or obtained from strings that are earlier in the sequences by one of the inference rules
MIU System
Theorems of the MIU System:
MI, MII, MIIII, MUI, MIU, etc.
theorem is the last string in a derivation
MIU System
How to prove that the theorems of the MIU system always starts with M
Proof: Let t be any theorem, Then (by the definition of theorems) it must be the last line in a derivation D in the MIU system. Derivative must be finite so d>/1.
Use complete mathematical induction and proof by cases to show that this holds for all possible cases of the MIU system.
MIU System
How can we decide whether MU is a theorem of the MIU-system?
Possible strategies:
1. Generate all theorems
2. If MU is generated, it is a theorem
3. If MU is never generated, it is not
geq-System
What is a recursive definition for the geq-system?
- (Base clause) Any string of the form ‘-geq- is a well-formed geq-string
- (Inductive clause 1) If ‘xgeqx’ is a well-formed string, so is ‘x-geqx-’; where x is composed of hypens only
- (Inductive clause 2) If ‘xgeqy’ is a well-formed string, so is ‘x-geqy’; where x and y is composed of hypens only
- (Final clause) Nothing else is a well-formed geq-string
geq-System
Well-formed strings of the geq-system:
’–geq-‘, ‘—-geq-‘, ‘-geq–’
How can “use” and “reference” be applied to formal systems?
a) We have assign specific meaning to primitives by means of interpretation, i.e. by specifying particalur referents in the structure
b) Since many different interpretations possible, say the meanings of the primitives are definied implicitly by the relations in which they are assumed to stand according to axoims
Interpretation: Both syntax and semantics
pq-System
Alphabet of the pq-System:
Alphabet: p, q, -
pq-System
Axioms of the pq-System:
Axioms: xp-qx- is an axiom, whenever x is composed only of hyphens
Infinitely many axoims. Not a single axoim but an axoim schema
pq-System
Example axioms of the pq-System
-p-q–, –p-q—, —p-q—-
pq-System
Inference Rules for the pq-System
Inference Rule: If xpyqz is a theorem (where x,y,z are composed only of hyphens), then xpy-qz- is a theorem
pq-System
What is a meaningful interpretation of the system?
geq-System
What are possible interpretations for the geq-system?
pq-system
What are well-formed strings for the pq-system?
pq-strings: Any concatenations of symbols from the p,q,-
Well-formed Strings: Strings in the form xpyqz for x,y,z non-empty strings of dashes
tq-system
How to build a formal system for multiplication:
x * 1 = x
x * (n + 1) = (x * n) + x
tq-system
What is the amiom schema for the tq-system:
xt-qx is an axiom, whenever x is a (non-empty) hypen string
tq-system
Rule of inference for the tq-system:
tq-system
Sample derivations for the tq-system:
C-System
What is the rule of inference of the augmented tq-system?
C-System
What are the theorems and non-theorems of the C-System?
In the C-System, all strings of the form Cx are divided into the C-System into composite (theorems) and primes (non-theorems)
Can we use this to characterize the prime numbers?
C-System
Can we use the theorems and non-theorem schema to characterize prime numbers?
Proposed Rule: Let x be a (non-empty) hyphen string;
If Cx is not a theorem, then Px is a theorem
Note: NOT a typographical rule. We cannot apply it in M-Mode, use I-Mode to determien whether it is applicable or not
