Formal Language 9/11/2013 11:39:00 AM
The Vocabulary of SL consists of:
Sentence letters of SL: A,B,C,..A1, A2, A3
Connectives of SL: ~(not),&(and),v(or),,
Punctuation marks: (,)
Syntactic formation rules:
o An expression of SL is any string of vocabulary elements.
o A sentences of SL is a string of vocabulary elements
assembled in accord with the following rules:
If P is a sentence of SL, then ~P is a sentence of SL
If P and Q are (not necessarily distinct) sentences of SL,
then (P & Q), (P v Q), (P Q), and (P Q) are
sentences of SL.
Nothing is a sentence of SL unless it can be formed by
repeated applications of rules 1-3.
Informal notational conventions:
o Allows [,] as substitutions for (,).
o Allow omission of outer parentheses.
o If P is a sentence letter of SL then it is an atomic sentence.
o If P contains a connective, then it is a compound sentence.
o ~ is a unary connective.
o &, v, >, and are binary connectives.
o A sentences of the form ~P is a negation. Its main connective
is “~” and its immediate component is P.
o A sentence of the form (P & Q) is a conjunction. It’s main
connective is “&” and P and Q are immedia