SE 212 - Logic and Computation
Elements of a Logic
A logic consists of syntax
syntax: a format for inscribing the logic
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 is also called sentential logic, i.e. the logic of sentences. We also refer to it as
propositional calculus, sentential calculus, or boolean logic.
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.
"It is cold but not snowing" can by entered into George with
% it is cold but not snowing
c & !s
% c means "it is cold"
5 s means "it is snowing"
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
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
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
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
3 Proof Theories
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
:((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
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
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.
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