SE 212 Fall 2013 1/2 Course Notes

10 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 a
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.