Transcript Formal Theories, Part 1

Formal Theories
SIE 550 Lecture
Matt Dube
Doctoral Student - Spatial
Recap of Friday and Monday
• Formal Languages
– Terminal and Non-terminal Symbols
– Well Formed Formulas
• First Order Languages
– Pathway to Computer Logic
– Backus-Naur Operators
– Predicates, Constants, Variables
mother( linda , X )
predicate
constant
variable
Today’s Class
•
•
•
•
•
•
•
Formal Theories
Logical Outputs
Boolean Operators and Modifiers
Truth Tables
Mathematical Laws
Logical Relations
Axioms and Theorems
Formal Theory
• Language for association
• Built on a foundation of primary assertions
– Assumed to be true
– father(henry,susan)
Translation: Henry is Susan’s father
• Rules imposed to infer information
– Mechanisms for inference
– pgrandfather(X,A)=father(X,Z)father(Z,A)
• Statements to prove
– pgrandfather(steve,susan)?
Logical Outputs
• Binary Output
– TRUE
– FALSE
Black and white form
• Multi-valued Output
– TRUE
– FALSE
– MAYBE
More human form
• Fuzzy Logic
– % of truth
Statistical form
Boolean Algebra
• AND
Today is Monday and I am in class.
– All terms are true
• OR
I am here or I am not here.
– At least one term is true
• NOT
– Term is false
Statement
Negated
• =
I am an open set = My complement is a closed set.
– Both terms have the same truth value
• IMPLIES
If I am in Orono then I am in Maine.
– Both true, or first statement false
If I am in Ohio then I am in Maine.
Truth Tables
•
•
•
•
Status of terms
Status under the operators
Can be simple or complex
Equivalent logical results are equivalent
statements
• If all values in a truth column are TRUE,
this is a tautology
• If all values are FALSE, this is a
contradiction.
Truth Table for NOT
P
Not P
TRUE
FALSE
opposite
FALSE
TRUE
Only true if condition is false
Truth Table for AND
P
Q
P AND Q
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
FALSE
TRUE
FALSE
FALSE
FALSE
FALSE
Only true if both conditions are true
Truth Table for OR
P
Q
P OR Q
TRUE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
TRUE
FALSE
FALSE
FALSE
True if at least one condition is true
Truth Table for = (If and only if)
P
Q
P=Q
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
FALSE
TRUE
FALSE
FALSE
FALSE
TRUE
Only true if both conditions are the same
Truth Table for If P, then Q
(IMPLIES)
P
Q
If P, then Q
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
FALSE
TRUE
The uncertainty table: anything can happen
Boolean Modifiers
• Two more relevant terms
–∀
• For All
–∃
• There Exists
Laws
•
•
•
•
•
•
•
•
•
•
•
Idempotent Laws – Intersection and Union
Identity Laws – Equality
Complement Laws – Opposites
Commutative Laws – Reversal
Associative Laws – Arbitrary Grouping
Distributive Laws – Multiplication
Absorption Laws
DeMorgan’s Rules – Distributing Not
Modus Ponens
Modus Tollens
Modus Barbara
Modus Ponens
• Latin
– Mode that affirms by affirming
• Affirming the Antecedent
• Law of Detachment
• Example:
– If today is Monday, then I have class.
– Today is Monday
– Therefore I have class.
Modus Tollens
• Latin
– The way that denies by denying
• Denying the consequent
• Example:
– If I am an archer, then I own a bow.
– I don’t own a bow.
– Therefore I am not an archer.
Modus Barbara
• Latin
– To measure barbarously
• Coming to a conclusion based on successive
implications and then strip the middle
information
• Example:
–
–
–
–
If I learn more, then I know more.
If I know more, then I forget more.
If I forget more, then I know less.
Therefore:
• if I learn more, then I know less.
Logical Relations
• Converse
– Q implies P
• Inverse
– not P implies not Q
• Contrapositive
– not Q implies not P
Components of Formal Theories
• Axioms
– Base level facts – needs no proof
– father(henry,susan)
• Association Rules
– grandfather(X,Y)=father(X,Z)father(Z,Y)
• Theorems
– father(X,susan) -> who is susan’s father
– father(X,A) -> all fathers of all children
Types of axioms
• Logical Axioms
– Association Rules
• Non-logical Axioms
– All other axioms
• Ground Axioms
– Non-logical Axioms that contain all constants
Example
•
•
•
•
•
father(john,suzy)
father(geoff,larry)
father(robert,john)
father(geoff,robert)
grandfather(X,Y)::=father(X,Z)father(Z,Y)
• ggrandfather(X,Y)::=father(X,W)father(W,Z)father(Z,Y)
grandfather(geoff,john)?
THEOREM