SE 212 Fall 2013 Course Notes

18 Pages
Unlock Document

University of Waterloo
Software Engineering
SE 212
Nancy Day

SE 212 - Logic and Computation Kevin James Fall 2013 Elements of a Logic A logic consists of syntax syntax: a format for inscribing the logic semantics semantics: the de▯nition of validity within the logic and proof theories proof theories: methods of determining validity The syntax de▯nes a "well-formed formula" (w▯). The semantics tells us which of these w▯s are true or valid. Valid formulas are given the symbol ‘, and non-valid formulas are marked as 6‘. When we describe a formula as being proven by theory, we use "▯"; if this is a natural deduction,NDe.use ▯ Proof theories do mechanical manipulations on strings or symbols. It does not make use of the meanings of characters, but simply uses them as strings of characters. Semantics and proof theories are related by soundness and completeness. A proof theory is sound if there is a way to prove it that ensures its validity, ie ▯ =) ‘. A proof theory is complete if there is only a way to prove it if it is actually valid, e.g. ‘ =) ▯. Propositional Logic Propositional Logic is also called sentential logic, i.e. the logic of sentences. We also refer to it as propositional calculus, sentential calculus, or boolean logic. Syntax A formula in propositional logic consists of ▯ two constant symbols: true and false ▯ propositional letters: any single lower- or upper-case letters 1 ▯ propositional connectives: :;^;_; =) ;(= (in that order of operations) ▯ brackets: these always have the highest precedence All binary logical connectives are right associative. Example: a ^ b ^ c means a ^ (b ^ c). With ands, the constants are conjuncts; with ors, they are disjuncts. Not that disjuncts are inclusive, and thus we must formulate exclusive ors by (p _ q) ^ :(p ^ q). By implication, we have the premise or antecedant or hypothesis leading to the consequent or conclusion. The contrapositive or a =) b is :b =) :a. Prime propositions are declarative sentences which can be either true or false. The primeness is based on the lack of connectives. Propositions with connectives are called compound propositions. Sentences that are interogative (questions) or imperative (commands) are not propositions. Logic is concerned with the structure of an argument, particularly valid ones. We encode sentences in symbols to give us a better understanding of the structure. Avoid using t or f, since those tend to confuse us with true and false . Our goal is to formalize all the details found in an English sentence while matching the form of the sentence as closely as possible. We do this by selecting the smallest statements without connectives about which we can can determine validity. Using propositional letters to stand for each of these sentences, we construct our statement by connecting them with connectives. George "It is cold but not snowing" can by entered into George with #u kevin #a 01 #q 01a % it is cold but not snowing #check PROP c & !s % where % c means "it is cold" 5 s means "it is snowing" Ambiguity The English language is notorious for ambiguity. When formalizing sentences, we must be sure to reduce the ambiguity as much as possible. The use of logical connectives, particularly, is often incorrect in English. For example, "and" in English is not always commutative and must be sometimes treated temporally. 2 Semantics Semantics are about giving our propositions meaning by relating words. They provide the interpretation of expressions in one world in terms of values in another world. The often act as a fucntion which converts between the two. The semantics de▯ne the limits of how a proof theory can transform a logical formula. The syntax of our logic is the domain of the semantic function. Classical logic is two-valued: true and false are the only possibilities for truth values. These are not a part of the syntax of propositional logic. The range of a logic is the set of its truth values. The semantics are described using boolean valuations boolean valuations: a function in propositional logic which maps from the set of formulas to the range We can de▯ne these boolean valuations with truth tables. For example, we can map true^false to false. The truth value of a formula is uniquely determined by the truth values of the prime propositions. When describing a boolean function, we must only describe the relation of truth values. For example: (p =) q) ^ r where v(p) = true;v(q) = false;v(r) = false gives v((p =) q) ^ r) = v(p =) q) ^ v(r) = (v(p) =) v(q)) ^ v(r) = (true =) false) ^ false = false ^ false = false We de▯ne a function as satis▯able if there is some combination of input values which will make the outcome true . If the formula is true for all possible input values, that formula is valid and can be referred to as a tautology. A tautology is written as ‘ p ^ :p. A formula p logically implies another formula q if and only if for all possible boolean value v(p) ‘ v(q). This can be represented as a tautology with ‘ p =) q. Note that we sometimes use V We can also generalize this over a set of functions with p ;p ;:::p ‘ q. 0 1 n A formula is a contradiction or falsehood if it is false for all possible input values. If a formula is neither tautology nor contradiction, then it is a contingent formula. Two formulas are logically equivalent if they have the same truth values. For example p_q $ q _p. A material equivalence uses the symbol ,, which expresses the "if and only if" idea. Though any formula can be proven with truth tables, these can sometimes be ungainly. A more concise method of determining whether a formula is a tautology is to use a proof theory (so long as the theory is sound). 3 Proof Theories Transformational Proof Transformational Proof is the act of using substitutions to prove a formula. For example (p ^ q) ^ :q WV false p ^ (q ^ :q) WV false p ^ false WV false false WV false Common transformations include commutativity, associativity, distributivity, contradiction, the law of the excluded middle, double negation, simpli▯cation, DeMorgan’s law, contrapositives, equivalence, implications, and idempotents (p ^ p =) p). We implicitely use the rule of substitution rule of substitution: substituting equivalent formulas for sub-formulas and the rule of transistivity rule of transistivity: all lines are equivalent, not just the closest two Examples: :((p ^ q) =) p) WV false :(:(p ^ q) _ p) WV false :(:p _ :q _ p) WV false (p ^ q) ^ :p WV false (p ^ :p) ^ q WV false false ^ q WV false false WV false x WV x ^ (y =) x) x WV x ^ (:y _ x) x WV x :true WV false :(p _ :p) WV false :p ^ p WV false false WV false Natural Deduction An argument is a collection of formulas beginning with a premise or multiple premises and ending with a conclusion which is justi▯ed by the remaining formulas. 4 If the conclusion of an argument is completely justi▯ed by the premises, it is a deductive argument. Inductive arguments conclude more general knowledge from a small number of particular facts or observations. In this course, we will be studying deductive arguments. Later on, we will study mathematical induction. Natural deduction is a collection of rules (inference rules), each of which allws us to infer new formulas from given ones. It is a forward proof, which begins from the premises and deduces new formulas which logically follow. We continue this until we have deduced the conclusion. An inference rule is a primitive valid argument form. Each one enables the introduction or elimination of some logical connection. We use a horizontal line to divide our premises from our conclusion, and write the name of the rule used on each line to the right of the preceeding line. These names may reference previous lines (including premises) by line number. The order of our premises does not matter. Normal Forms A literal is a proposition letter or its negation. A formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals or a single literal. A formula is in disjunctive normal form if it is a disjunction of clauses, where a clause is a conjunction of literals or a single literal. There are no repeated literals in a clause and no clause contains true or false . No two clauses should contain the same literals. Note that true and false by themselves are in CNF and DNF. Every formula has an equivalent formula in CNF and DNF. We can convert our formula to CNF with the following methodology: 1. Remove all ! and =) using implication and equivalence laws 2. Use the negation law or DeMorgan’s theorem to remove any negated compound subformulas 3. Use distributivity to reduce the scope 4. Simplify so there are no repeated literals in a clause and no clause contains true or false Subproofs Some natural deduction rules use subordinate proofs, which are enclosed by f and g, are indented, and involve and assumption and the conclusion it leads to. Once we’ve proven a subproof, we refer to it as closed. We must close all subproofs to complete the proof. The active formulas at any stage of a proof are those which do NOT occur in a subproof. 5 Predicate Logic Predicate logic is a method of formalizing an English sentence. A sentence expressed in predicate logic looks like the following: "Rich actors collect some valuables" becomes 8x▯rich(x)^actor(x) =) 9y▯collects(x;y)^valuable(y). "Not everyone in Louisiana speaks French, but everyone in Louisiana knows someone in Louisiana who speaks French" becomes :(8x ▯ inL(x) =) speaks(x;French)) ^ (8c ▯ inL(x) =) 9y ▯ knows(x;y) ^ inL(speaks(y;French))). Types A type is a set of objects describing the possible values of a variable. We assume types to be non-empty. Any unary predicates are interchangeable with the type of the object they describe. Quanti▯ers For a universally quali▯ed variable, the formula must be true for all sbstituions of an object int he domain for the quanti▯ed variable. For an existentially quali▯ed variable, the formula must be true for some substitution. We can eliminate 8 by simply selecting a possiblity, i.e. 8x =g x . The opposite of this would be to introduce an 9, i.e. x=) 9x. g We can also introduce 8 terms; informally: if a formula is true for an arbitrary value, it is true for all values. For example: for every g { ... ... P[g/x] } A x * P We can similarly eliminate 9 terms with E x * P for some u P[u/x] { ... q } q Interpretations Interpretations are sets of rules our equation must follow. An interpretation must contain a domain (x 2 f0;1;2▯▯▯g) and a The environment is the mapping between variables and objects within the domain. 6 For example: 8d 2 D : I[x => something(x;y)];e[x d]. Terms A predicate formula satis▯es a logic if it is true in that interpretation and environment. If there exists any interpretation and environment for which it is true, that formula is satis▯able. It is a tautology (valid) if every environment and interpretation satis▯es the formula. It is a contradiction if it is not satis▯able in any interpretation or environment. A logic is closed if it contains no free occurances of a variable. In this case, environments have no e▯ect (e.g. it is satis▯able dependant only on the interpretatation, not also the environment). Predicate logic is valid if there exists some interpretation with both valid premises and conclusions. It is invalid if and only if there exists some interpretation such that the premises are true but a conclusion is false. Types of Variables A genuine variable is a free variable such that the universal quanti▯cation of it yields a true formula. For example: 8x ▯ x + x = 2x. We tend to represent these with x ;g ,getc. A universal variable requires an existential quaniti▯cation to be rendered true; it represents a speci▯c but unknown value. Example: 9x ▯ x + 1 = 2. We represent these as x ;y , etc. u u Induction There are two branches in the philosophical study of logic: ▯ Deduction is showing a conclusion follows from the stated premises using rules of inference. ▯ Philosophical induction is the process of deriving general principles from particular observa- tions. ▯ Mathematical induction deals with generalizations, but does not allow exceptions since we are dealing with an ordered domain. We have Peano’s axioms of arithmetic: 1. 8n ▯ :(suc(n) = 0) 2. 8x;y ▯ (suc(x) == suc(y)) =) (x == y) 3. 8m ▯ m + 0 == m, 8m ▯ 0 + m == m 4. 8m;n ▯ m + suc(n) == suc(m + n) 5. 8n ▯ n ▯ 0 == 0 6. 8m;n ▯ m ▯ suc(n) == m ▯ n + m 7. (P(0) ^ (8k ▯ P(k) =) P(suc(k)))) =) 8n ▯ P(n) Note that the seventh axiom is the basis for mathematical induction. 7 Set Theory A set is a collection of elements or numbers. They have no order and may or may not be in▯nite. All elements are distinct, i.e. no set contains more than one of the same element. We de▯ne x as being a member of S with x 2 S and its converse with x 62 S. Note that x 62 S $ :(x 2 S). In addition to de▯ning exactly which members are in a set, we can use set construction notation as follows ▯ S = f2x ▯ x : N▯ (5 < x) ^ (x < 10)g for the set of all even numbers between ▯ve and ten. We can refer to the size of set A as #A or jAj, where the size is equal to the number of elements in A. A singleton set is any set with a size of one. Set Comprehension We have two axioms for dealing with set comprehension: ▯ ▯ x 2 fy : S ▯ P(y)g () x 2 S ^ P(x) ▯ ▯ x 2 ff(y) ▯ y : S▯ P(y)g () 9y ▯ y 2 S ^ P(y) ^ x == f(y) Special Sets The empty set, which contains no elements, is written as ;. This can be de▯ned as 8x ▯ :(x 2 ;). The universal set contains all objects of concern (e.g. all countries in the world, all people...). This set is denoted U. ▯ The power set of A is the set of all sets such that PA = fB ▯B ▯ Ag. For any ▯nite set, #PA = 2 #A . We have the following axiom for power sets: S 2 PQ () (8x ▯ x 2 S =) x 2 Q). Set Comparisons Sets are equal if and only if they contain exactly the same elements. The corresponding axiom is A == B () (8x ▯ x 2 A () x 2 B) We de▯ne A to be a subset of B if all elements of A are contained in B. Note that this includes the case where A == B. The subset axiom is A ▯ B () (8x ▯ x 2 A =) x 2 B). If A is a subset of B and the two sets are not equal, we refer to A as a proper subset of B. A ▯ B () A ▯ B ^ :(A == B). 8 Derived Laws We can derive a few laws in set theory: ▯ The empty set is a subset of every set ‘ ; ▯ A ▯ Every set is a subset of itself ‘ A ▯ A ▯ Subsets are transitive ‘ A ▯ B ^ B ▯ C =) A ▯ C ▯ Equal sets can be shown as subsets ‘ A == B () A ▯ B ^ B ▯ A Set Functions We can perform unions and intersections of sets as follows: ▯ ▯ Set Union: A [ B = fx ▯x 2 A _ x 2 Bg ▯ ▯ Set Intersection: A \ B = fx ▯x 2 A ^ x 2 Bg. Two sets A and B are disjoint if their intersection is empty (i.e. A \ B = ;). Note: #(A [ B) = #A + #B#(A \ B)
More Less

Related notes for SE 212

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.