Cos4807
Formal Logic 4
,
,Propositional Logic Part 1 of 3
Propositional Formulae:
Instead of p1, p2 subscripts, use different letters such as p, q, r etc
Capital letters are used for arbitrary formulae A, B, C etc
If Parenthesis aren’t serving a purpose, omit it
Alphabet:
An atom is a formula with a single symbol ex p
A literal is a atom or its negation ex p or p
Complementary: One is the formula and the other is
it’s negation
Substitution: A[B/C] in formula A, sub all occurrences of B to C, if none occur it remains unchanged
A, B are Conjuncts
A, B are Disjuncts
A is the antecedent
B is the consequent
Formulae as Trees
principle operator (the root node)
Subformula: B is a subformula of
A iff B is a subtree of A
Propositional Interpretation: A function that assigns a truth value ( T or F) to
propositional sysmbols
p is true for interpretation 1, p is false for interpretation 2.
Truth value: Value associated to a propositional formula
, Definitions:
Validity: True in all interpretations.
Unsatisfiablity: False in all interpretations.
Falsifiability: False in at least one
interpretation.
Equivalence: Two formulae are equivalent
if they have identical truth tables.
Entailment: When A is true then B is true
Truth Tables
We use the interpretation
name I as a subscript and
we have the truth value
function v1. This normally
gets omitted.
Additional columns are
added for subformulae for
convenience.
The truth table above is
satisfiable
Sound: The output is always correct.
Complete: There is output to all input.
Truth value:
Formal Logic 4
,
,Propositional Logic Part 1 of 3
Propositional Formulae:
Instead of p1, p2 subscripts, use different letters such as p, q, r etc
Capital letters are used for arbitrary formulae A, B, C etc
If Parenthesis aren’t serving a purpose, omit it
Alphabet:
An atom is a formula with a single symbol ex p
A literal is a atom or its negation ex p or p
Complementary: One is the formula and the other is
it’s negation
Substitution: A[B/C] in formula A, sub all occurrences of B to C, if none occur it remains unchanged
A, B are Conjuncts
A, B are Disjuncts
A is the antecedent
B is the consequent
Formulae as Trees
principle operator (the root node)
Subformula: B is a subformula of
A iff B is a subtree of A
Propositional Interpretation: A function that assigns a truth value ( T or F) to
propositional sysmbols
p is true for interpretation 1, p is false for interpretation 2.
Truth value: Value associated to a propositional formula
, Definitions:
Validity: True in all interpretations.
Unsatisfiablity: False in all interpretations.
Falsifiability: False in at least one
interpretation.
Equivalence: Two formulae are equivalent
if they have identical truth tables.
Entailment: When A is true then B is true
Truth Tables
We use the interpretation
name I as a subscript and
we have the truth value
function v1. This normally
gets omitted.
Additional columns are
added for subformulae for
convenience.
The truth table above is
satisfiable
Sound: The output is always correct.
Complete: There is output to all input.
Truth value:
