Transcript Propositional Logic

Logic and Critical
Thinking
Dr. Rogelio Dávila Pérez
ITESM, Campus Guadalajara
[email protected]
http://www.rogeliodavila.com
“Good sense is the best shared-out
thing in the world; for everyone
thinks he has such a good supply of
it …”
René Descartes (1596-1650)
“The Discourse of the method”
Why is it important to study logic?
(i)
Learning logic helps you to support your
own arguments.

When your arguments are not well supported
your proposal is week.
Why is it important to study logic?
(ii) Learning logic helps you to improve your
ability to analyse others’ arguments.

Once you know how to construct arguments
and to distinguish bad-formed arguments, it is
easer to realise that we are exposed to many
week assertations.
Why is it important to study logic?
(iii) Learning logic improves your ability to
write papers and to build propposals.


Understanding logic helps you tu justify your
arguments and to express in clearer form our
ideas.
Your presentations will be more consistent and
solid in your proposals.
Why is it important to study logic?
Typical sentences:
“Do not buy in XX buy in YYY”
“The car that you need is WWW”
“Do not vote for YYY but for”
“Invest in RRR and not in TTT”
etc.
but … ¿are this information is enough?
Why is it important to study logic?
Being able to recognize invalid arguments has
the following adventages:


.
Accepting an argument as valid allowes you to
understand and defend it.
Rejecting an argument as invalid, give us the
knowledge to show others its inconsistency.
Logic
Logic is related with the concepts of truth and
inference, that is, to determine:
a). The conditions that make a proposition
true.
b). The conditions under which a proposition
can be drawn from premises.
What is an argument?
Consider the following arguments:
a).
Rose lives in Puebla or lives in Guadalajara
Rose is not living in Puebla
Hence, Rose lives in Guadalajara
b).
If Mike has hepatyties then his sking is yellow
The skin of Mike is yellow
Hence, Mike has hepatyties
What is an argument?


Arguments are made by propositions.
A proposition is a declarative sentence, an affirmation of
certain facts.
Examples:
 London is the capital of England.
 Humans are the only animals that use language.
 Hernán Cortés conquered México.
…

A declarative sentence is the minimal unit of language
that can be associated a truth value. We can say for a
certain sentence that it is true or is false.
What is an argument?




Logic is the study of valid arguments.
A valid argument is the one in which true premises give
us always true conclusions.
The validity of an argument do not depend on the truth
of the premises but with the fact that if someone
accepts the truth of the premises he/she must accept
the conclusion.
If someone does not accept the premises, he/she wont
accept the conclusions but this does not invalidate the
argument.
What is an argument?
a).
Rosa lives in Puebla or lives in Guadalajara
Rosa is not living in Puebla
Hence, Rosa lives in Guadalajara
b).
If Mike has hepatytis his skin is yellow
the skin of Mike is yellow
hence, Mike has hepatytis
Valid
Argument
Invalid
Argument
What is an argument?

An argument consists of three components:
All Greeks are philosophers
Socrates is Greek
Hence, Socrates is philosopher
Premises
Conclusion
The process by which we arrive from premises to
conclusion is called inference.
What is an argument?
Premises
 Evidence that supports the conclusion
 Premises are always assumed to be true
 Are introduced by phrases like: “because …”,
“obviously …”, etc.
 The “obviously” expression should be analysed
carefully as generlly it is used as an intimidatory
argument.
What is an argument?
Conclusion
 Is a proposition that is drawn from the premises.
 Most of the times it occurs by the end of the
argumentation.
 It is frecuently introduced with phrases as:
“hence …”, “concluding …”, “then we know …”,
etc.
What is an argument?
Inference
 Process that allows us to go from premises to
conclusions.
 From propositions already accepted generates a
conclusion.
 There are different types of inference, not all of
them are logically valid.
What is an argument?
Activity 2.
a). Comics analysis
b). Text analysis
Logical constants
George Bool in his book, “Laws of Though” [1847],
present an analysis of sentence connectors using
expressions like:

Conjunction: AND, “”.

Disjunction: OR, “”.

Negation: “it is not true that”, NOT, “”.

Conditional: “if … then”,“”

Biconditional, “if and only if”, iff, “”
Logical constants
If we have two propositions, to say:
P = Tom study law
Q = Laura plays golf
These propositions may be combined as follows:
P  Q = Tom study law and Laura plays golf
P  Q = Tom study law or Laura plays golf
 P = It is not true that Tom study law
P  Q = If Tom study law then Laura plays golf
P  Q = Tom study law if and only if Laura plays golf
Logical constants
Meaning of logic constants (0-false, 1-true):
P
Q
PQ
PQ
P
PQ
PQ
0
0
0
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
1
1
0
1
1
Example
(a) P  Q  P  Q
P
Q
PQ

0
0
1
1
0
1
1
1
0
1
1


Q
1
1
0
1
1
1
1
0
1
0
0
0
1
1
0
1
1
P
Propositional Logic
I. Syntax
1.
Vocabulary: The language of propositional logic has an
alphabet consisting in:
(a)
Propositional variables: Pi, Qi, Ri (i  N)
(b)
Logical constants: 
(c)
Logical connectors: , , , 
(d)
Auxiliary symbols: “(“, “)”, “,”
2.
Well-formed formulas (wffs)
(a)
(b)
(c)
(d)
If  is a propositional variable, then  is a wff.
 is called contradiction an is a wff.
If  and  are wffs, then ,  ,  ,    are also wffs.
Nothing else is a wff.
Propositional Logic
II. Rules of Inference (Natural Deduction [Gentsen, 60s])
(a)
Conjunction Rules
-Intro
-Elim





(b)
Conditional Rules
 -Intro

…




 -Elim (modus ponens rule)



Propositional Logic
(c)
(d)
Contradiction Rules
-Intro


Negation Rules
 -Intro

…


-Elim


 -Elim (Double negation rule)


Propositional Logic
(e)
Disjunction Rules
-Intro

-Elim







Propositional Logic
An axiomatic system for propositional logic
1.
Axiom schemata
(A1) (X  (Y  X))
(A2) ((X  (Y  Z))  ((X  Y)  (X  Z)))
(A3) ((X  Y)  ((X  Y)  X))
2.
Inference rules
(MP) If X and (X  Y) are both theorems then Y is a theorem.
3.
We can use the equivalences
  
     (    )
Propositional Logic
A traditional way of characterizing validity and logical
consequence is in terms of derivation, or proof, and
inference rules. This may be accomplished either by an
axiomatic system or, through a natural deduction system.
Some definitions:
Def. An axiom is a statement considered as valid.
Def. An inference rule is a machinery for producing new
valid statements from previously obtained ones.
Def. An axiomatic system consists of a set of axioms (or
axioms schemata) and a set of inference rules.
Def. In an axiomatic system, valid statements produced by
the system are called theorems.
Propositional Logic
Def. A derivation or proof of a theorem is the ordered list of
axioms, theorems and statements produced by the
application of inference rules on previously obtained
theorems.
Def. For an axiomatic system, derivability or provability, of a
formula  is written:
|— 
( is a theorem)
Def. If  is a set of formulas, the expression
 |— 
means that  is derivable from . In this case the formulas
in  are considered as hypotheses.
Def. Two formulas  and  are logically equivalent (  ),if each
of them is provable from the other.
Propositional Logic
Disjunctive Syllogism
pvq
~p
q
Resolution rule [Robinson, 1965]
p v q1 v q2 v … v qn
~p v r1 v r2 v … v rm
q1 v … v qn v r1 v … v rm
Propositional Logic (semantics)
The purpose of semantics is to assign meaning to all the wellformed formulas in the language.
 Definition. An interpretation of a formula of PL consists in
assigning a truth value (0-false, 1-true), to each
propositional symbol in the formula.
The logical connectors are said to be truth-functional as their
meaning is a function of the meanings of its constituents. It
is common to express the meaning of logical connectors
through a truth-table.
Propositional Logic (semantics)
Truth tables




¬
 
0
0
0
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
1
1
0
1
1
Propositional Logic (semantics)





Definition. An interpretation that makes a formula true
(=1) is a model of that formula.
Definition. A formula is consistent, sound or satisfiable,
if it has a model.
Definition. A non consistent formula is called
inconsistent or unsatisfiable.
Definition. A formula is valid when every interpretation
of it is a model. This formula is called a tautology.
Definition . A formula is contingent when it is not valid,
but consistent.
Some relations between the concepts:


If  is valid then ¬ is inconsistent
If  is consistent then ¬ is not valid.
Propositional Logic (semantics)
Definition. Two wffs  and  are equivalent,   , if both of
them yield the same true values for any interpretation.
Propositional logical equivalences (also called logical
identities):
(a)       v 
(b) Contraposition Law:         
(c) Distributive Laws:
(i)  v (  )  ( v )  ( v )
(ii)   ( v )  (  ) v (  )
(e) DeMorgan’s Laws:
(i)  ( v )      
(ii)  (  )    v  
Propositional Logic (semantics)
Definition. An interpretation function or interpretation is a
function that assigns a truth value to each propositional
variable in the formula.
Definition. A mapping v: PROP  {0,1} is a interpretation if:
v(  ) = min(v(), v())
v(  ) = max(v(), v())
v(  ) = 0 iff v()=1 and v()=0
v(  ) = 1 iff v()=v()
v() = 1 - v()
Propositional Logic
Definition. (i)  is a tautology if v() = 1 for all interpretations
v,
(ii) |= stands for ‘ p is a tautology’
Definition. A set of wffs  is consistent, sound, or satisfiable, if
all their elements admit the same model. Otherwise it is
said to be inconsistent.
Definition. Let  be a set of wffs and  a wff, we say that 
entails , or that  is a logical consequence of ,  |= ,
iff every model of  is a model of .
Definition.  is a logical consequence of , iff    is a
tautology.
Propositional Logic
Soundness and Completeness
There are two important definitions that connect
inference with entailment:
1.
If, for any set of wffs, , and wff  ,  |— 
implies that  |= , we say that the set of
inference rules, , is sound.
2.
If, for any set of wffs, , and wff , it is the
case that whenever  |= , there exists a proof
of  from ,  |— , using the set of inference
rules, , we say that  is complete.
Propositional Logic
PSAT Problem
The problem of finding at least one model of the set of
formulas  that is also a model of the formula , is known
as the propositonal satisfiability (PSAT) problem.
An exhaustive procedure for solving the PSAT problem is to
try systematically all of the ways to assign True and False
to the atoms in the formula, checking the assignment to
see if all formulas have value True under that
assignment. If there are n atoms in the formula, there
are 2n different assignments, so for large n, the
exhaustive procedure is computationally infeasible, thus
the general PSAT problem is NP-complete.
Inference Rules
(  I)
P Q
PQ
( I)
P
…
Q
PQ
( I)
P

P
(  E)
PQ
P
( I)
PQ
Q
( E)
P
PvQ
PQ
P
R
( E)
P Q
P
Q
( E)
P
P
Q
R
R
( I)
( E)
P  P


R
Logical identities
(a) Conmutativity
(d) DeMorgan Laws
(  )    
(  )    
    (  )
    (  )
(b) Asociativity
  (  )  (  )  
  (  )  (  )  
(c) Distributives Laws
(e) Idempotency


(f) Contraposition Law
     
  (  )  (  )  (  )
(e) …
  (  )  (  )  (  )
      
Inference Rules
Transforming to Conjunctive Normal Form
1. Elimination of conditional symbols () using the identity:
  v
2. Negation introduction: reduce the scope of the negation
symbol applying the deMorgan Laws.
(i)  ( v )      
(ii)  (  )    v  
3. Transform the formula to Conjunctive Normal Form applying
the Distribution Laws:
(i)  v (  )  ( v )  ( v )
(ii)   ( v )  (  ) v (  )
4. Elimination of conjuctive symbols (). Put the expression in
clauses.