Transcript Logic - Lnu.se

Logic
What is it?
1
• Formal logic is the science of deduction.
• It aims to provide systematic means for
telling whether or not given conclusions
follow from given premises, i.e., whether
arguments are valid or not
2
A valid argument is one whose
conclusion is true in every case
in which all its premises are true.
3
Premise 1: Some cave dwellers use fire.
Premise 2: All who use fire have intelligence.
Conclusion: Some cave dwellers have
intelligence.
Valid or not?
Valid
4
P1: All geniuses are illogical.
P2: Some politicians are illogical.
Conclusion: Some politicians are geniuses.
Valid or not?
Not valid
5
P1: If you overslept, you will be late.
P2: You aren’t late.
Conclusion: You didn’t oversleep.

IF
you oversleep, you will be late
AND you are not late
THEN you didn’t oversleep.
6
P1
P2
.
.
.
Pn

IF P1 and P2 and … Pn THEN C
C
7
A valid argument does not say that C is true
but that C is true if all the premises are true.
That is, there are NO counterexamples.
P1: Bertil is a professional musician.
P2: All professional musicians have pony-tail.
Therefore: Bertil has pony-tail.
8
Postulates
Axioms
9
Einstein's Postulates for the
Special Theory of Relativity
•
•
The laws of physics are the same in all
reference frames.
The speed of light through a vacuum
(300,000,000 m/s) is constant as
observed by any observer, moving or
stationary.
10
Euclid's fifth axiom (parallel axiom):
For each point P and each line l, there exists
at most one line through P parallel to l.
11
Different Geometries
• Euclidean: Given a line L and a point P not on L,
there is exactly one line passing through P,
parallel to L.
• Hyperbolic: Given a line L and a point P not on L,
there are at least two lines passing through P,
parallel to L.
• Elliptic: Given a line L and a point P not on L,
there are no lines passing through P, parallel to L.
12
Euclidian
Elliptic
Hyperbolic
 180
 180
 180
Sum of the angles:
13
Premises/Postulates/Axioms
 Conclusion
Logic is about how to deduce, on mere form,
a valid argument.
Valid is a semantic concept.
Deduction is a syntactic concept.
14
Logic
• Propositional calculus
• Quantification theory (predicate logic)
15
Proposition
Propositions are expressed, in natural
language, in sentences.
It is raining.
It is snowing.
Where is Jack? (NOT a proposition)
Propositions are declarative sentences: saying
something that is true or false.
16
More examples:
Napoleon was German.
All men are mortal.
Tweety is a robin.
Oxygen is an element.
Jenkins is a bachelor.
No bachelor are married.
If it is raining then it is it is snowing.
It is not raining.
It is raining or it is snowing
It is raining and it is snowing.
17
Propositional CALCULUS uses variables for
propositions and study the form, not the
content (semantics), in order to deduce valid
conclusions.
If it is raining then it is it is snowing.
It is not raining.
It is raining or it is snowing
It is raining and it is snowing.
If A then B
not A
A or B
A and B
18
Compare with mathematics.
(1) x  y  ( x  y)(x  y)
2
2
(2) 15  7  (15  7)(15  7)
2
2
19
We shall treat propositions as unanalyzed,
thus making no attempt to discern their logical
structure.
We shall be concerned only with the relations
between propositions, and then only insofar as
those relations concern truth or falsehood.
20
OR
Either you wash the car or you cut the grass.
The symbol V (from Latin vel) is used to indicate ‘or’
as in ‘Either A or B’.
V is inclusive.
21
Exact definition of V.
Lower-case letters ‘p’, ‘q’, ‘r’, etc., are used for
propositional variables, just as ‘x’, ‘y’ are numerical
variables.
p
q
pVq
F
F
T
T
F
T
F
T
F
T
T
T
22
‘Socrates is alive V Plato is alive’ is false.
‘Socrates is alive V Plato is dead’ is true.
23
p
q
pVq
0
0
1
1
0
1
0
1
0
1
1
1
24
Not:

A : It is raining.
A : (it is not thecase that)it is raining,or
It is not raining.
p
0
1
p
1
0
25
AND:

Socrates is alive
 Plato is alive
p
q
pq
0
0
1
1
0
1
0
1
0
0
0
1
26
p q p p  q q
T
T
T
F
F
F
T
F
F
T
.
.
.
p  q ( p  q)
F
T
T
F
27
How is ‘if … then ___’ represented?
An ‘if … then ___’ is called a conditional.
The proposition replacing ‘…’ is called the
antecedent, and that replacing the ‘___’ is called the
consequent.
‘if it isn’t raining, then he is at game’
antecedent
consequent
28
Truth value for conditionals.
if p then q
Things that are q
Things that are p
Things that are
neither p nor q
p  q
29
Truth Table
p
q
pq
0
0
1
1
0
1
0
1
1
1
0
1
30
pq
if p, then q
p only if q
q
p
You have malaria only if you have fever.
31
Only men are whisky-drinkers.
Only M is W

If W then M
32
Equivalence
p  q  p  q
De Morgan’s laws:
p  q
( p  q)  p  q
( p  q)  p  q
33
Tautology is a proposition that is always true.
p  (q  p)
Contradiction is a proposition that is always
false:
  
Falsum:

symbolizes a contradiction
   , any 
34
if  is a tautology, then  is a contradiction.
if  is a contradiction, then  is a tautology.
35
Inference rules
pq
pq
 eliminat ion
and
p
q
p, q
 int roduct on
i
pq
p  r , p  q, r  q
 eliminat ion
q
p
q
 int roduct on
i
and
pq
pq
p
Double negat ion
p
p, p  q
 eliminat ion
(modus ponens)
p
36
introduction
1.
p
q
and
pq
pq
p
q
2.
pq
37
1
1
pq
pq
E
E
q
p
I
q

p
1
I
pqq p
Compare:
p
q
pq
38
1
2
p 
p
1
2
E

I
( p ) 
I
p  [( p ) ]
Compare:
p
q
pq
39
1
1
p
I
q p
I
p  (q  p)
q
Compare
pq
40
Proof or Deduction
P1,P2 ,...,Pn  C
 stands for a proof: there is one or more
inferences that together lead to C.
41
A Proof
1
1
pq
E
q
2
pq
E
p
2
p  (q  r )
E
qr
r
1
I
pq r
I
[ p  (q  r )]  [ p  q  r ]
42
Soundness and completeness
A logic is sound if a deduction yields a valid argument.
It is complete if there is a deduction for a valid argument.
43
Quantification Theory
For all member in a set …
There exist a member in a set …
44
All teachers are friendly.
For all x (if x is a teacher then x is friendly)
Some teachers are unfriendly
There is (exists) a teacher such that
(x is a teacher and x is unfriendly)
45
All teachers are friendly.
x (if x is a teacher then x is friendly)
Some teachers are unfriendly
x (x is a teacher and x is unfriendly)
46
All teachers are friendly.
x( x is a teacher x is friendly)
Some teachers are unfriendly
x( x is a teacher x is unfriendly)
47
All teachers are friendly.
x( x is a teacher x is friendly)
Some teachers are unfriendly
x( x is a teacher x is not friendly)
48
A predicate is expressed by an incomplete
sentence or sentence skeleton containing an open
place.
“___ is a man” expresses a predicate.
When we fill the open place with the name of a
subject, such as Socrates, the sentence “Socrates
is a man” is obtained.
49
Consider the skeleton “___ loves ___”.
In grammatical terminology, this consists
of a transitive verb and two open places,
one to be filled by the name of a subject,
such as “Jane”, the other of an object,
such as “John”.
Binary relation
50
Another example:
“___ is less than ___”.
“2 is less than 3”.
In mathematical language:
23
51
Man(Socrates)
Loves( Jane, John)
alternatively
JaneLovesJ ohn
52
“___ is a man”
“___ loves ___”
Man(x)
Loves( x, y)
53
Existential quantifier
There is something with a particular property.
xUnicorn(x)
54
Universal quantifier
Every man is mortal.
x(Man( x)  Mortal( x))
55
there are right-angled triangles
OR
there is a triangle that is right-angled
OR
there is a triangle with the property of being
right-angled.
x(triangle( x)  right  angled( x))
56
All teachers are friendly.
x(T ( x)  F ( x))
Some teachers are unfriendly
x(T ( x)  F ( x))
57
Combinations of universal and existential
quantifiers.
x( x  0  y( x  S ( y)))
58
Problems
1. Interpretation
S ( x)  S ( y )  x  y
59
S ( x)  S ( y )  x  y
Three different interpretations:
1. S is the “security number of a person”.
2. S is the “successor function in arithmetic.
3. S is the “DNA sequence of a person”.
60
2. Difficulties in expressing natural language
sentences.
a. All men are mortal.
b. Dog is a quadruped.
c. Only drunk drivers under eighteen cause
bad accident.
a. Driving is risky, if you are drunk.
61
All have the same form:
x( A( x)  B( x))
62
All men are mortal.
A( x)  x is a man
B( x)  x is mortal
Dog is a quadruped.
A( x)  x is a dog
B( x)  x is a quadruped
Only drunk drivers under eighteen cause bad
accident.
A( x)  x causes bad accident
B( x)  x is a drunk driver under 18
Driving is risky, if you are drunk.
A( x)  x is drunk
B( x)  for x to drive is risky
63
Al men are not good.
There are no good men.
Not all men are good.
64
Everything with F has G
x( F ( x)  G( x))
Something with F has G
x( F ( x)  G( x))
Nothing with F has G
x( F ( x)  G( x))
Something with F has not G
x( F ( x)  G( x))
65
Negation
xP(x) can be read
‘it is not the case that all x have the property P’
i.e., ‘some x has not property P’
i.e., there exist some x which not has property P
i.e., xP(x)
66
xP( x)  xP( x)
‘there is no x with the property P’
i.e., all x have the property notP
67
Interpretation
What does it mean for a quantified expression
to be true or false?
68
xP(x)
says that all element in a particular domain (a nonempty
set) have the property P,
i.e., all x belongs to the set that is decided by the
interpretation of P.
xP(x)
says that in the domain, decided by the interpretation of P,
there is at least one element with the property P.
69
D( x, y)
The meaning of D: ‘x has the dog y’
Domain: Växjö.
The interpretation of D is the all pairs p, d such that
p is the name of a person in Växjö that has a dog with
the name d.
70
x( R( x)  B( x))
Let R stands for raven and B for black.
Then the sentence expresses that all ravens are black.
Black animals
Ravens
Animals
71
x( D( x)  T ( x))
‘There is a dog that is toothless’.
Domain: All animals
If there is a dog that is toothless the sentence is true.
72
END
73