# SE 212 Fall 2013 Course Notes

Unlock Document

University of Waterloo

Software Engineering

SE 212

Nancy Day

Fall

Description

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