Transcript Introduction.

Mathematical Logic
An Introduction
Copyright © 2006-2010 - Curt Hill
History
• Classical logic is based on natural
language and may be closer to
philosophy
• Symbolic logic is based on
mathematics
• What is the difference?
Copyright © 2006-2010 - Curt Hill
Difference
• Classical logic is greatly influenced
between the connection between the
statements and underlying facts
– Lawyers and debaters are main users
– Two lawyers can reason from the same facts
to two different conclusions
– They do this by emphasizing different sets of
facts and reasoning
• Symbolic logic is mostly concerned with
values that are removed from their
underlying propositions
– The proofs generated here are
incontrovertible
Copyright © 2006-2010 - Curt Hill
Statements
• Def: A statement is a sentence that is
either true or false. It cannot be both.
– Statement is in natural language
– It should state a fact even if that fact is not
true
– AKA proposition
• Examples:
– Bill Clinton was president in 1999.
– VCSU graduated 10,000 students in 2000.
– There are exactly 10 million dust particles in
this room at this time.
Copyright © 2006-2010 - Curt Hill
Non-examples:
• What time is it?
– Does not state a fact
• All generalities including this one
are false.
– Is this true or false?
• 12 + x = 5
– Neither true nor false until a value is
given for x
Copyright © 2006-2010 - Curt Hill
Proposition
• A statement is also known as a
proposition
– We usually assign a lower case letter to
such statements of fact, starting with p
so that they may be variables as well
• Why are we doing this?
– There are numerous examples of faulty
logic
– Everyone who ever died of cancer ate
mushrooms, thus mushrooms cause
cancer.
Copyright © 2006-2010 - Curt Hill
The Goal
• To be able to mathematically treat
such a set of statements and
determine if they are valid or not
• How will we do this?
• Three steps:
– Translate into symbolic form
– Simplify the symbolic form
– Optionally translate back into English
Copyright © 2006-2010 - Curt Hill
Truth values
• A statement or proposition may have
one of two values: true or false
• We may not know whether a
particular statement is true or false
we just have to know that it must be
one of the two
• Two important mathematical areas,
fuzzy logic and probability can deal
with non discrete values but they are
not covered here
Copyright © 2006-2010 - Curt Hill
Human Thinking
• There was a belief once that all
human reasoning could be
expressed in logic
• Unfortunately this is not so
– People believe things that are true and
false
– They also operate on incomplete
information
– They put varying levels of confidence
on the "facts" at their disposal
Copyright © 2006-2010 - Curt Hill
Operators
• There are a number of connecters
or operators that can be applied to
logical values
• Each of these takes one or two
Boolean values and produces a
Boolean result
• These are mostly based on English
words so should be somewhat
intuitive
Copyright © 2006-2010 - Curt Hill
Common Operators
• You are probably familiar with the
common ones:
• Disjunction (or) 
• Conjunction (and) 
• Negation (not) ¬
– Also sometimes ~ or !
Copyright © 2006-2010 - Curt Hill
Other operators
• Equivalence ≡
– Also 
•
•
•
•
•
Discrepancy or Exclusive Or 
Implication 
Consequence 
NAND |
NOR 
Copyright © 2006-2010 - Curt Hill
Precedence
• Boolean operators have an order of
operation just like arithmetic
operators
–
–
–
–
–
Highest is anything in parenthesis
Not (¬)
And () or () are usually the same
Implication ()
Equivalence (≡) is lowest
Copyright © 2006-2010 - Curt Hill
Equivalence and Equal
•
•
There is often some confusion
between equivalence (≡) and equal
(=)
Equivalence only takes Booleans
–
–
•
55 is not allowed
Equality may take any type of
operands
Equivalence is associative but
equality is not
–
–
(5=5) = true is OK but
5 = (5 = true) is not
Copyright © 2006-2010 - Curt Hill
Completeness
• Is there a subset of operators that
could be used to express all others?
• Yes, several sets
– And, Or and Not are complete
– NAND is complete in itself
– As is NOR
Copyright © 2006-2010 - Curt Hill
Operator Definition
• How do we define the operation of
such operators?
–
–
–
–
–
Informally
In terms of other operators
Truth tables
Venn diagrams
Axiomatic proofs
• We will use the latter three
Copyright © 2006-2010 - Curt Hill
Informal Definitions
• We have an informal notion of what they
do from English
• This is handy for understanding
– It is fortunate that George Boole was a native
English speaker
– Our intuitive notion is often correct
• However, this will not help us much in
proofs and calculation
• The informal definition is often
ambiguous, eg. Inclusive or exclusive OR
Copyright © 2006-2010 - Curt Hill
Construction
• We may declare that an operator is
related to a previously well known
operator
• Consider the exclusive or
– One or the other but not both
• We may define this in terms of the
negation of the equivalence
Copyright © 2006-2010 - Curt Hill
Truth tables
• Since a binary operand can only
have four possible inputs we may
enumerate them
• Truth tables are not necessarily the
best thing for proofs either since our
proofs very often involve a lot more
than two variables and each
additional variable doubles the size
• They are very handy for visualization
and understanding
Copyright © 2006-2010 - Curt Hill
Venn diagrams
• Aka Euler Circles
• An equivalent technique
• Set theory and Boolean algebra are
isomorphic
– This means that anything in one can be
translated into the other
– This includes the proof on a step by
step basis
– Each proposition (statement of fact) in
logic becomes a set membership in set
theory
Copyright © 2006-2010 - Curt Hill
Axiomatic proofs
• An axiom is an unproven assumption or
definition
• An axiom should be self evident or a
fundamental definition
– Each axiom must be consistent with all other
axioms in the system
– From our axioms we may prove theorems
• Our proofs must use valid reasoning
– This type of system is at the heart of all
mathematics
• We will use all three (truth tables, Venn
diagrams, and axiomatic proofs) but only
the latter is actually needed
– Proofs are the most rigorous
Copyright © 2006-2010 - Curt Hill
Now What?
• Truth tables will be covered in one
presentation
• Venn diagrams will be covered in
one presentation
• Axiomatic definition will include
several presentations
• Of course there will be the needed
exercises along the way
Copyright © 2006-2010 - Curt Hill