Transcript INTRODUCTION TO SYMBOLIC LOGIC

INTRODUCTION TO
SYMBOLIC LOGIC
Propositional Logic & Truth
Functional Analysis
What is Symbolic Logic?
• It uses symbolic notation in expressing
propositions and arguments.
“If, if the first then the second
and if the second then the third,
then, if the first then the third.”
[(p q) (q r)] (p r)
• Concentrates in the form.
• Simplest kind of logic.
• Its modern development began with George
Boole in the 19th century.
What prompted the creation of
symbolic logic?
• Ordinary everyday language is flowery and
ambiguous (because of equivocation, amphiboly,
accent, vagueness, & confusion in emotive
significances)
• In order to avoid the common difficulties of
ordinary language, we need an artificial language
that substitutes it using minimal characters, and,
consequently, represents it with high degree of
clarity and simplicity.
• There is also economy of space and time.
GOALS
1. Learn the elements of the new language
2. Learn how to translate ordinary language
grammar into symbolic notation
3. Represent arguments in this new language
The 2 Subfields of Symbolic
Logic…
1. Propositional Logic
•
•
Originally called propositional calculus
Studies the properties of propositions formed from
“constants” and logical “operators”
2. Predicate Logic
•
•
•
Originally called predicate calculus
expands on propositional logic by introducing variables,
usually denoted by x, y, z, or other lowercase letters,
It also introduces sentences containing variables, called
predicates, usually denoted by an uppercase letter
followed by a list of variables, such as P(x) or Q(y,z).
Propositional Logic:
Propositions and Operators
•
•
Propositions are considered as “ATOMS”
of propositional logic.
What are the two types of propositions?
1. Simple Propositions
2. Compound propositions
Propositional Logic:
Propositions and Operators
• What are “Simple Propositions”?
– Statements which cannot be broken down
without a loss in meaning.
– E.g. “John and Leah is a couple” cannot be
broken down without a change in meaning of
the statement. Note what happens if we break it
down to “John is a couple” and “Leah is a
couple”
Propositional Logic
– But “Juanita and Juanito are diligent students” is not a
simple sentence because it can be broken down without
a change in meaning. “Juanita is a diligent student.”
“Juanito is a diligent student.”
– This is an example of a “Compound Proposition.”
• How do we represent (simple) propositions in
propositional logic?
– Conventionally, capital letters (usually towards the
beginning of the alphabet) may be used as
abbreviations for propositions.
Propositional Logic
• “John and Leah is a couple.”
=A
• “Juanita and Juanito are diligent students.”
=A • B
• The symbol “•” is used to represent the
logical operator “and” or “conjunction”
Constants and Variables
• What are constants?
– Capital letters that represent the actual statements.
Since it represents an definite statement, it does not
vary.
– E.g. “John and Leah is a couple.” =
A
• What are variables?
– It is not a proposition, but is a “place holder” for any
proposition.
– Used for making templates of forms.
– E.g. “John and Leah is a couple.” = a
– “Chimps and Men are apes” = a
Simple vs Compound
• Tuguegarao is the capital of Cagayan and Basco is
the capital of Batanes.
• Either I will be forgotten or I will forever be
remembered.
• If I will be remembered, then my soul will shout
for joy.
• Noli De Castro is the future president if and only
if Manny Villar is not a presidential candidate.
Propositional Logic
• What are Logical Operators?
– Another basic element of propositional logic.
– They “connect” propositions.
– Compound Proposition = proposition “+” proposition
“+” …
• What then is the basic skill needed in studying
elementary propositional logic?
– Knowing the “truth value of propositions”
– All you need to know is the definition of the “operator”
and the “truth value of the propositions used.”
Propositional Logic:
Truth Functionality
• Any argument’s worth is quite dependent on the
combination of the truth values of the component
sentences.
• Understanding arguments is basically:
– Understanding how truth values of the component
sentences are distributed in the compound or complex
sentence used to express the argument
– Understanding how the component sentences are
connected to one another
Propositional Logic:
Truth Functionality
• In order to know the truth value of the proposition
which results from applying an operator to
propositions, all that need be known is the
definition of the operator and the truth value of the
propositions used.
• The basic symbolic conventions of Propositional
Logic are thus about propositions and about the
operators used to connect them.
The Operators
Connective
Not
Symbol
~
Formal Name
Negation
And
•
Conjunction
Or
V
Disjunction
If… then…
Conditional /
Implication
… if and only if…
Biconditional
=
NEGATION
• The phrase “It is false that …” or “not” inserted in
the appropriate place in a statement.
• E.g., “It is not the case that Bugoy is ugly” can be
represented by “~B”.
• It is represented by the following truth table:
p
~p
T
F
F
T
CONJUNCTION
• Truth-functional connective
similar to “and” in English
and is represented in
symbolic logic with the dot
“•”
• A connective forming
compound propositions
• Expressed in the following
truth table:
p
q
p.q
T
T
F
F
T
F
T
F
T
F
F
F
CONJUNCTION
• The statement “Miko is cute and Popo is hideous”
can be represented as “ M • P ”
• There are four possible states of affairs which
might have occurred with respect to Miko as cute
and Popo as hideous.
p
q
p.q
T
T
F
F
T
F
T
F
T
F
F
F
CONJUNCTION
• Some characteristics of conjunction (in
mathematical jargon) include:
1. associative—internal grouping is immaterial
I. e., “[(p • q) • r]” is equivalent to “[p • (q • r)]”.
2. communicative—order is immaterial
I. e., “p • q” is an equivalent expression to “q • p”.
3. idempotent—reduction of repetition
I. e., “p • p” is an equivalent expression to “p”.
DISJUNCTION
• Sometimes called alternation
• A connective which forms compound propositions
which are false only if both statements (disjuncts)
are false.
• Expressed in the following truth table:
p
q
pvq
T
T
F
F
T
F
T
F
T
T
T
F
DISJUNCTION
• The connective “or” in English is quite different
from disjunction. “Or” in English has two quite
distinctly different senses.
1. The exclusive sense of “or” is “Either A or B (but not
both)” as in “You may go to the left or to the right.” In
Latin, the word is “aut.”
2. The inclusive sense of “or” is “Either A or B {or
both).” as in “John is at the library or John is studying.”
In Latin, the word is “vel.”
• We use the second sense of “Or.”
DISJUNCTION
• E.g
– “Either Gloria or Erap is the greatest Filipino
president.”
–GvE
– “Neither Gloria nor Erap is the greatest Filipino
president.”
– ~(G v E) or (~G) • (~E)
DISJUNCTION
• The order of the words “both” and “not” is
very important in translating propositions
connected by disjunction.
• Eg.
– Willy and Joey will not both be elected.
• ~(W•J)
– Willy and Joey will both not be elected.
• (~W) • (~J)
DISJUNCTION
• How should we understand this?
– ~W•J
• ~(W•J)
• ~ (W) • J
– It is understood in the 2nd sense. The original
notation is accepted for brevity purposes.
IMPLICATION
• “material implication”
• The falsity of such a statement is
established only when the antecedent is true
and the consequent if false.
p
q
p q
T
T
F
F
T
F
T
F
T
F
F
F
IMPLICATION
• E.g.
– If the Miko lives morally (p), then he will go to
heaven (q).
p
q
p q
T
T
F
F
T
F
T
F
T
F
T
T
BICONDITIONAL
• Material Equivalence “If and only if”
• Two statements are materially equivalent if they have the
same truth value, i.e. if both is true or false.
• Expressed in the following truth table:
p
q
p q
T
T
F
F
T
F
T
F
T
F
F
T
Summary of Operators
p•q
p
q pvq
p
q p
q
T
T
T
T
T
T
T
F
T
F
F
F
F
T
T
F
T
F
F
F
F
F
T
T
Punctuation
• When sentences involved are complex enough to
have more than two sentences, we use
parentheses, brackets, or braces.
• To avoid ambiguities in understanding complex
sentences like “P • Q • R • S”, we use the grouping
apparatuses in this one possible fashion “(P • Q) •
(R • S)”
• Mistake in the punctuation means a mistake in
determining the truth value of arguments.
Punctuation
•
In using punctuations, the following rules are to
be followed:
1. The major truth functional connective representing the
entire compound statement must be identified.
2. If negation symbol is found immediately outside a set
of punctuated symbols then it must be interpreted to
mean that the whole punctuated symbols are negated.
3. If negation symbol is attached to a symbol outside a
set of punctuated symbols then the negation symbol
negates only that particular symbol.
Punctuation
• Examples
– Either philosophers are intelligent and
innovative thinkers or they are simply insane
and weird.
(I • N) v (S • W)
– If mountains are high and majestic then they are
either not small nor plain.
(H • M)
~(S v P)
Determine the main operator of
the following statements
~(A v M) • (C E)
(G • ~P) ~(H v ~W)
~[P • (S K)]
~(K • ~O) ~(R v ~B)
(M • B) v ~ [E ~(C v I)]
~[(P • ~R) (~E v F)]
~[(S v L) • M] (C v N)
Translate the following molecular
statements in symbolic form
• It is not the case that Hitler killed millions
of innocent Jews.
• Either Caesar married Cleopatra or FJP
became the President of the Philippines.
• Alexander the Great conquered America if
Napoleon rules France.
• Arabs are treated as terrorists only if Bin
laden bombed the Twin Towers.
TRUTH TABLE
1
2
3
4
5
6
7
8
p
q
r
qvr
p v (q v r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
T
T
F
T
T
T
F
T
T
T
T
T
T
T
F
TRUTH TABLE 2









p
v
T
T
T
T
F
F
F
F
T
T
T
T
T
T
T
F
( q v r )
T
T
F
F
T
T
F
F
T
T
T
F
T
T
T
F
T
F
T
F
T
F
T
F
Forms of Propositions
• Inconsistent Proposition
– Two or more beliefs are said to be inconsistent
when they both cannot be true at the same time
for any possible situation.
– E.g.
p
q
p
q
~(~p v q)
T
T
T
F
T
F
F
T
F
T
T
F
F
F
T
F
• Inconsistent Proposition
– If a belief cannot be true in any possible
occasion
– Often it is referred to as self-contradictory or
simply contradiction
– E.g.
p
~p
p • ~p
T
F
F
T
F
F
F
T
T
F
F
F
• Consistent Proposition
– If two or more beliefs can be true together in
some possible situation.
p
q
p . q
pvq
T
T
T
T
T
F
F
T
F
T
F
T
F
F
F
F
• Consistent Proposition
– If a belief can be true in some possible
occasion.
p
q
p
q
T
T
T
T
F
F
F
T
T
F
F
T
• Tautologous Proposition
– Beliefs that are always true no matter what
– E.g.
• If it rains then it rains.
•R
R
• Equivalent Proposition
– Propositions that are perfectly consistent.
p
q
p
q
~p v q
T
T
T
T
T
F
F
F
F
T
T
T
F
F
T
T
Determine what type of
Proposition
R v ~R
R • ~R
(R v S) • T
R ~R
R S
Compare the following pairs of
proposition and determine whether they
are consistent, inconsistent, contradictory
1.
2.
3.
4.
5.
6.
7.
R
S
~S
~R
D
E
D • ~E
O v P
P • O
~D v T
~(D • ~T)
~K
K
(O
L
P)
Q
O • (P v Q)
~L
O (P Q)
(O • P) v (O • Q)
Replacement
• Equivalent sentences can replace each other
within any complex proposition salva
veritate, meaning without gain or loss of
truth values.
• Equivalent sentences are represented using
material equivalence ( ) and all forms are
summarized in the
Rules of Replacement
1. Material Implication (Impl.)
(p
q)
(~p v q)
2. Association (Assoc.)
[p v ( q v r)] [(p v q) v r]
[p • ( q • r)] [(p • q) • r]
3. Distribution (Dist.)
[p • ( q v r)] [(p • q) v (p • r)]
[p v ( q • r)] [(p v q) • (p v q)]
Rules of Replacement
4. Commutation (Com.)
(p v q)
(p • q)
(q v p)
(q • p)
5. De Morgan’s Rule (De M.)
~(p • q)
(~p v ~q)
~(p v q)
(~p • ~q)
6. Double Negation (D.N.)
p ~~p
Rules of Replacement
7. Transposition (Trans.)
(p v q)
(q v p)
8. Material Equivalence (Equiv.)
(p q)
(p q) • (q p)
(p q)
(p • q) v (~p • ~q)
9. Exportation (Exp.)
[(p • q) r] [p (q r)]
10. Tautology (Taut.)
p
(p v p)
p
(p • p)
Formal Proof
• The following are said to be the Elemtary
Rules of Inference for Modern Symbolic
Logic:
1. Modus Ponens (M.P.)
p q
p
q
2. Modus Tolens (M.P.)
p q
~q
~p
3. Addition (Add.)
p
pvq
Formal Proof
4. Simplification (Simp.)
p•q
p
7. Hypothetical
Syllogism (H.S.)
p q
q r
p r
5. Conjunction (Conj.)
p
q
p•q
8. Constructive
Dilemma (C.D.)
p q
r
s
p v r
q v s
10. Absorption (Abs.)
p q
p (p • q)
6. Disjunctive
Syllogism (D.S.)
pvq
~p
~q
9. Destructive
Dilemma (D.D.)
p q
r
s
~q v ~s
~p v ~r
Exercise. Determine what argument form
was used in the following arguments
1. Thomas will apologize or Michelle will be angry.
Thomas will not apologize.
Therefore, Michelle will be angry.
2. If Tuguegarao is in Cagayan, then San Gabriel is in Cagayan.
If San Gabriel is in Cagayan, then Sir Mike’s house is in Cagayan.
If Tuguegarao is in Cagayan, then Sir Mike’s house is in Cagayan.
3. If this flashlight works, then the batteries are good.
This flashlight does work.
Therefore, the batteries are good.
4. If this flashlight works, then the batteries are good.
The batteries are not good.
Therefore, the flashlight does not work.
5. If this punch contains gin, then Emil will like it, and if it contains Matador, then
Loid will like it.
This punch contains either gin or Matador.
Therefore, either Emil will like it or Loid will like it.
6. If this punch contains gin, then Emil will like it, and if it contains Matador, then
Loid will like it.
Either Emil will not like it or Loid will not like it.
Therefore, either this does not contain gin or it does not contain Matador.
7. If Napoleon was killed in a plane crash, then Napoleon is dead.
Napoleon was not killed in a plane crash.
Therefore, Napoleon is not dead.
Proving the validity of an
argument
If the Lakers win the playoff, then the Pistons
will lose the championship. If the Lakers do
not win the playoff, then either Jackson or
Bryant will be fired. The Pistons will not
lose the championship. Furthermore, Bryant
will not be fires. Therefore, Jackson will be
fired.
Proving the validity of an
argument
1. If the Lakers win the playoff,
then the Pistons will lose the
championship.
2. If the Lakers do not win the
playoff, then either Jackson or
Bryant will be fired.
The Pistons will not lose the
championship.
Furthermore, Bryant will not be
fired.
Therefore, Jackson will be fired.
1. L
P
2. ~L (J v B)
3. ~P
4. ~B
/
J
Proving the validity of an
argument
1. L P
2. ~L (J v B)
3. ~P
4. ~B
/ J
5. ~L
1, 3, MT
6. B v J
2, 5, MP
7. J
4, 6, DS
Proving the validity of an
argument
EX. 1
1. S T
2. T U
3. R S
4. R T
5. R U
/ R U
1, 3, HS
2, 4, HS
Proving the validity of an
argument
EX. 2
1. A v B
2. ~C ~A
3. C D
4. ~D
/ B
5. ~C
3, 4, MT
6. ~A
2, 5, MP
7. B
1, 6, DS
Proving the validity of an
argument
EX. 3
1. E
(K
2. F
(L
3. G v E
4. ~G
5. F
6. E
7. K
L
8. L M
7. K
M
L)
M)
/K
M
3, 4, DS
1, 6, MP
2, 5, MP
7, 8, HS
Exercise. Supply the required justification
for the derived steps in the following proofs:
(1) 1. J
(K
L)
2. L v J
3. ~L
/~K
4. J
_______
5. K L _______
6. ~K
_______
(Ans) 1. J
(K
L)
2. L v J
3. ~L
/~K
4. J
__
5. K L _______
6. ~K
_______
Exercise. Supply the required justification
for the derived steps in the following proofs:
(2) 1. ~(S
2. (S
3. ~P
4. ~(S
5. ~P
6. Q
T) (~P Q)
T) P
/Q
T) _______
Q _______
_______
(Ans) 1. ~(S
2. (S
3. ~P
4. ~(S
5. ~P
6. Q
T) (~P
T) P
/Q
T) _
Q _
_
Q)
Exercise. Use the first four rules of inference to
derive the conclusions of the following symbolized
arguments:
(1) 1. (G J) v (B
2. ~(G J)
(2) 1. (K • O)
2. K • O
P)
/B
P
(N v T)
/NvT