Propositiponal logic
1
Department of Computer Science,
Faculty of Electrical Engineering and Computer Science,
VSB - Technical University of Ostrava
Propositiponal logic
2
•
An argument is valid iff it is
necessary that under all interpretations
(valuations in propositional logic),
in
which the premises are true
the conclusion is true as well: P
1
,...,P
n
|= Z
•
P
1
,...,P
n
|= Z
if and only if
The statement of the form
P
1
and ... and P
n
implies Z
is
necessarily
true (a tautology):
|=
(P
1
& … & P
n
)
Z
Some more arguments
∀
∃
α
β
λ
|
-
3
P
1
, ..., P
n
|= Z
iff
|=
(P
1
& … & P
n
)
Z
•
BUT
!!!
•
It does not mean that the conclusion is (or must be) true
.
We are
dealing with a
valid logical form
,
a necessary relation between
premises and the conclusion
.
Arguments
∀
∃
α
β
λ
|
-
4
No prime is divisible by 3
9 is divisible by 3
----------------------------------
9 is not a prime
•
It is a valid argument though the first premise is not true (3 is a
prime divisible by 3). Another interpretation:
All men are rational.
A stone is not rational.
--------------------------------
A stone is not a man.
Arguments
∀
∃
α
β
λ
|
-
5
•
Or, by substituting:
If the number 12 is a prime then it is not divisible by 3.
12 is divisible by 3.
12 is not a prime.
•
Or:
12 is not a prime number or it is not divisible by 3.
12 is divisible by 3.
12 is not a prime number.
Valid argument schemes (examples of logical forms)
:
•
A
B, A |= B
modus ponens
•
A
B, B |=
A,
modus ponens + transposition
•
A
B,
B |=
A
modus ponens + transposition
•
A
B, B |=
A
elimination of disjunction
(disjunctive syllogism)
Arguments
∀
∃
α
β
λ
|
-
6
•
Hence if we prove that the conclusion logically follows from the assumptions,
then by virtue of it we
do not prove that the conclusion is true
•
It is true,
provided the premises are true
•
The argument the premises of which are true is called
sound.
•
Truthfulness or Falseness of premises can be a
contingent
matter.
But
the relation of logical entailment is a
necessary
relation
(“in all the
circumstances ...“).
•
Similarly a
tautology is a logically, necessarily true formula.
•
If a tautology is of an implication form, then according to the definition of the
implication it is true also in case of the antecedent being false, and false only
in case the antecedent is true and consequent false, which corresponds to the
definition of logical entailment:
•
A
1
,…,A
n
|= C
iff
|= A
1
…
A
n
C
Arguments
∀
∃
α
β
λ
|
-
7
•
The simplest logical system. It analyzes a way of composing a complex
sentence (proposition) from elementary propositions by means of logical
connectives.
•
What is a proposition?
A proposition (sentence) is a statement that can be said
to be true or false.
•
The Two-Value Principle
– tercium non datur – two-valued logic
(
but there are
many-valued logical systems, logics of partial functions, fuzzy logics, etc.)
•
Is the definition of a sentence trivial? Are all the statements sentences, or in
other words, do all the statements denote a proposition?
No, it is not so:
•
The (current) King of France is bald.
•
True? But then the King of France exists. False? But then it is true that the King of
France is not bald, hence the King of France exists as well. The statement is
neither
true nor false
, it is not a sentence.
•
Did you stop beating your wife?
(try to answer in case you have never been married or never beat your wife)
Propositional (Sententional) Logic
∀
∃
α
β
λ
|
-
8
•
There are two kinds of
Sentences
:
•
Atomic (Elementary)
–
no proper part of the sentence is a
sentence as well
•
Molecular (Composed)
–
the sentence has its own part(s) that is
(are) a sentence(s) as well
•
The Compositionality Principle
:
meaning of a composed
sentence is a function (depends only on) the meanings of
its components
.
•
The meaning of sentences is in propositional logic reduces
to: True
(1),
False
(0).
•
An algebra of truth values
.
Propositional logic: semantic exposition
(Semantics = meaning)
∀
∃
α
β
λ
|
-
9
It is raining in Prague
a
nd
it
is a sunshine in Brno
.
S
1
connective
S
2
•
It is not true
that it is raining in Prague
.
connective
S
Examples of composed sentences
∀
∃
α
β
λ
|
-
10
•
A formal language
is defined by an
alphabet
(a set of
symbols) and a
grammar
(a set of rules that define
the way of forming “Well Formed Formulas” - WFF)
•
Language of Propositional Logic (PL)
•
alphabet
:
a)
Symbols for propositions:
p, q, r, ...
(also with indexes p
1
,
p
2
, …)
b)
Symbols for logical connectives:
,
,
,
,
c)
Auxiliary symbols: (, ), [, ], {, }•
Symbols ad a) stand for elementary sentences
•
Symbols ad b), i.e.,
,
,
,
,
are called:
negation (
)
,
disjunction (
)
,
conjunction (
)
,
implication (
)
,
equivalence (
)
.
Definition: language of PL
∀
∃
α
β
λ
|
-
11
Grammar
(defines inductively well-formed-formulas)
Inductive definition of an infinite set of WFF:
1.
Symbols
p, q, r, ...
a
re (well-formed)
formulas
(the definition base).
2.
If A, B are formulas, then expressions
A
,
A
B
,
A
B
,
A
B
,
A
B
are (well-formed)
formulas
(inductive definition step).
3.
Only expressions due to 1. and 2. are WFFs.
(the definition closure).
•
The language of PL
is the set of well-formed formulas.
Note:
Formulas according to 1. are
atomic formulas
Formulas according to 2. are
composed formulas
Definition: language of PL
∀
∃
α
β
λ
|
-
12
N
o
tes
:
Symbol
s
A, B
are
metasymbol
s
.
We can substitute for them any WFF created
according to the definition
.
The outermost parentheses can be omitted
.
For the logical connectives other symbols are sometimes used
:
Symbol
alternat
e
--------------------------------
,
,
&
~
Example
:
(
p
q)
p
is a WFF
(
the outer parentheses omitted
)
(p
)
q
is not a WFF
Well-formed formulas
∀
∃
α
β
λ
|
-
13
The truth-value
valuation
of propositional symbols
is
a mapping
v
that
to each propositional symbol
p
assigns a truth value, i.e., a
value from the set
{1,0},which codes the set
{True, False
}:
{p
i
}
{1,0}The truth-value function of a PL formula
is
a function
w
,
which for
each valuation
v
of propositional symbols
p
i
associates the
formula with its truth value in the following way
:
•
The truth value of an elementary formula p
:
w
p
v
=
v
p
for
any
propositional variable
p.
•
If the truth values of formulas
A, B
are given
,
then the truth value
of the formulas
A, A
B, A
B, A
B, A
B
are defined by the table 2.1.:
Defini
tion: semantics (meaning) of formulas
∀
∃
α
β
λ
|
-
14
Tab
le
2.1.
:
the truth–value functions
∀
∃
α
β
λ
|
-
15
•
Elementary sentences:
by the propositional variables p, q, r, ...
•
Connectives of natural language: by means of the symbols for logical connectives:
•
Negation:
•
“it is not true that”:
(unary connective)
•
Conjunction:
•
“and”
:
(binary, commutative connection)
•
Prague is a capital
and
2+2=4:
p
q
•
Note: not every “and” denotes a logical connective!
Example: “Peter came home and opened the window”
.
•
Disjunction
:
•
“or”:
(binary, commutative connection)
•
Prague
or
Brno is a great city
.
p
q
•
non-alternative
•
In a natural language we often use “or” as an alternative “either, or”:
“I’ll go to the cinema
or
I’ll stay at home”
•
Alternative “or” is a non-equivalence
Transforming natural language to the PL language
∀
∃
α
β
λ
|
-
16
•
“if … then …
“
:
•
(binary,
non-
commutative connective)
A
B; A is the
antecedent
, B is the
consequent
.
•
Implication (as well as any other connective of propositional
logic) does not render any
semantic connection
between
antecedent and consequent:
•
material implication
(middle ages: ”
suppositio materialis”
).
•
Hence implication
does not render a causal or chronological
connection
:
•
”If 1+1=2, then iron is a metal” (a true proposition): p
q
•
”If the UFOs (flying saucers) exist, then I am the Pope”:
p
r
(What do I want to say?
Since I am not the Pope, the UFOs do not exist)
Implication – be careful !!
∀
∃
α
β
λ
|
-
17
•
Note: The
connectives “because”, “therefore”, “since”, etc.
do not correspond to the logical implication!
•
“The ice-hockey team lost the match,
therefore
the
players came home from the world championship earlier”.
“
Because
I am sick, I stay at home”.
•
“sick”
“home”?
But then it would have to be true even if I am not sick
(see the table 2.1 – the definition of implication)
•
We might analyze it by means of the
modus ponens
:
[p
(p
q)]
q
Implication – be careful !!
∀
∃
α
β
λ
|
-
18
•
Equivalence
:
•
”if and only if” (iff)
•
”The Greek army used to win
if and only if
the result of the battle depended
on their physical strength”:
p
q
•
It is most frequently used in mathematics (in definitions), in a natural
language its use is seldom
•
Example
:
a)
“
I’ll slap you if you cheat on me
”
cheat
slap
b)
“
I’ll slap you if and only if you cheat on me
”
cheat
slap
Situation: You did not cheat. When can you be slapped?
Ad a) – You may be slapped,
Ad b) – You might not be slapped.
The equivalence connective
∀
∃
α
β
λ
|
-
19
•
A model of a formula A
is a
valuation
v
such that A is true in
v
:
w
(A)
v
= 1
.
•
A formula is satisfiable
iff it has
at least one
model
•
A formula is a contradiction
iff
it has no
model
•
A formula is a tautology
iff
any valuation
v
is its model.
•
A set of formulas {A1
,…,A
n
} is satisfiable
iff there is a valuation
v
such
that
v
is a model of
every
formula
A
i
, i = 1,...,
n
. The valuation
v
is then a
model of the set
{A1
,…,A
n
}.
Defini
tion: Satisfiable formulas, tautology,
contradiction, model
∀
∃
α
β
λ
|
-
20
•
Example
. Formul
a
A
is a tautology
,
A
is a contradiction
,
formul
as
(p
q), (p
q)
are satisfiable.
•
Formul
a
A:
(p
q)
(p
q)
Satisfiable formulas, tautology,
contradiction, model
∀
∃
α
β
λ
|
-
21
•
A formula A
logically follows from
a set of
formulas M, denoted
M
|= A, iff
A is true in every
model of the set
M.
•
Note
: Mind the Definition 1 (slide 5 of Lesson 1).
The
circumstances
are in propositional logic
mapped as
valuations (
True – 1, False - 0) of
elementary atomic sentences
:
•
Under all the
circumstances
(means
valuations
valuations
of
of
atomic propositional variables
atomic propositional variables
in PL) such that the
premises are true the conclusion must be true as well.
Logical entertaiment in PL
∀
∃
α
β
λ
|
-
22
•
He is at home (
h
) or he has gone to a pub
(
p
)
•
If he is at home (
h
) then he is waiting for us
(
w
)
•
If he is not waiting (
w
) for us then he has gone to the pub (
p
).
h
,
p
,
w
|
h
p
,
h
w
|
w
p
1 1 1
1 1
1
conclusion
1 1 0
1 0
1
1 0 1
1 1
1
is true in all
1 0 0
1 0
0
0 1 1
1 1
1
the four models
0 1 0
1 1
1
of
premises
0 0 1
0 1
1
0 0 0
0 1
0
Examples: Logical entertaiment
∀
∃
α
β
λ
|
-
23
•
He is at home (
h
) or he has gone to a pub
(
p
)
•
If he is at home (
h
) then he is waiting for us
(
w
)
•
If he is not waiting (
w
) for us then he has gone to the pub (
p
).
h
p
,
h
w
|
w
p
•
T
he table has
2
n
lines
!
Hence,
an indirect proof is more effective
:
•
Assume that the argument is
not valid.
But then all the premises may be
true and the conclusion false
:
•
h
p
,
h
w
|
w
p
1
1
0
1 0
0
1 0
1 0
0
contradiction
Examples: Logical entertaiment
∀
∃
α
β
λ
|
-
24
•
All the arguments with
the same logical form
as a
valid argument are valid:
h
p
,
h
w
|=
w
p
For variables
h
,
p
,
w
any elementary sentence
s
can be
substituted:
He plays a piano or studies logic.
If he plays a piano then he is a virtuous.
Hence
If he is not a virtuous then he studies logic.
Valid argument – the same valid logical form
Examples: Logical entertaiment
∀
∃
α
β
λ
|
-
25
•
T
he argument is valid
P
1
,...,
P
n
|=
Z
if
if
the formula of the implicati
ve
form is a tautology:
|=
(
P
1
...
P
n
)
Z
.
•
The
proof that a formula is a tautology or that a conclusion Z
logically follows from premises can be
done
:
a)
In the
direct
way
–
for instance by a truth-value table
b)
In the
indirect
way
:
P
1
...
P
n
Z
is a contradiction; hence
the set of premises +
the
negated conclusion
{P
1
,
...
,
P
n
,
Z
}
is contradictory, i.e., does not have a model: there is no valuation under
which all the formulas – its elements were true.
Examples: Logical entertaiment
∀
∃
α
β
λ
|
-
26
|= ((p
q)
q)
p
Indirect
:
((p
q)
q)
p
neg
ated
f
., must be a contradiction
1 1
attempt whether it can be
1
1 1
1 1 0
contradiction
There is no valuation under which the negated formula were true. Therefore, the
original formula is a tautology
A proof of tautology
∀
∃
α
β
λ
|
-
27
Tautologies with one propositional variable:
|=
p
p
|=
p
p
the law of excluded middle
|=
(
p
p
)
the law of contradiction
|=
p
p
the law of double negation
The most important tautologies
∀
∃
α
β
λ
|
-
28
•
|= (p
q)
(q
p)
commutative laws
•
|= (p
q)
(q
p)
•
|= (p
q)
(q
p)
•
|= [(p
q)
r]
[p
(q
r)]
associative laws
•
|= [(p
q)
r]
[p
(q
r)]
•
|= [(p
q)
r]
[p
(q
r)]
•
|= [(p
q)
r]
[(p
r)
(q
r)]
distributive laws
•
|= [(p
q)
r]
[(p
r)
(q
r)]
Algebraic laws for conjunction,
disjunction and equivalence
∀
∃
α
β
λ
|
-
29
|=
p
(q
p)
law of simplification
|=
(p
p)
q
Duns Scot’s law
|=
(p
q)
(
q
p)
law of
contra-position
|=
(p
(q
r))
((p
q)
r)
premises joint
|=
(p
(q
r))
(q
(p
r))
order of premises does not matter
|=
(p
q)
((q
r)
(p
r))
hypothetic sylogism
|=
((p
q)
(q
r))
(p
r)
transitivity of implication
|=
(p
(q
r))
((p
q)
(p
r))
Frege’s law
|=
(
p
p)
p
reductio ad absurdum
|=
((p
q)
(p
q))
p
reductio ad absurdum
|=
(p
q)
p , |= (p
q)
q
|=
p
(p
q) , |= q
(p
q)
Laws for implication
∀
∃
α
β
λ
|
-
30
|= (p
q)
(p
q)
(q
p)
|= (p
q)
(p
q)
(
q
p)
|= (p
q)
(
p
q)
(
q
p)
|=
(p
q)
(
p
q)
|=
(p
q)
(p
q)
Negation of implication
|=
(p
q)
(
p
q)
De Morgan
law
|=
(p
q)
(
p
q)
De Morgan
law
These laws define a method for
negating
Laws for transformation
∀
∃
α
β
λ
|
-
Mathematical Logic
31
Parents
: If you
behave
well
you will
get a new ski at Christmas!
(p
q)
Child
: I
did behave well
the whole
year and there is no ski under the
Christmas tree!
p
q
(Did the parents fulfill their promise?)
Attorney general:
If the accused man is guilty then there was an accessory in the fact
Defence lawyer:
It is not true !
Question: Did the advocate (defence lawyer) help the accused man; what did he
actually claim?
(The man is guilty and he performed the illegal act alone!)
Negation of implication
∀
∃
α
β
λ
|
-
32
Sentence in the future tense
:
If you steel it I’ll kill you!
(p
q)
It is not true
: I will steel it and yet you will not kill me.
p
q
OK, but:
If the 3
rd
world war breaks out tomorrow then more than three million people
will be killed.
It is not true
: The 3
rd
world war will break out tomorrow and less than three
million people will be killed
???
Probably by negating the sentence we did not intend to claim that (certainly)
the 3
rd
world war will break out tomorrow:
There is an unsaid
(
ecliptic
)
modality:
Necessarily,
if the 3
rd
world war breaks
out tomorrow then more than three million people will be killed.
It is not true
:
Possibly
the 3
rd
world war breaks out tomorrow but at that case
less than three million people will be killed.
Handled by modal logics – not a subject of this course.
Negation of implication
∀
∃
α
β
λ
|
-
33
•
Transformation from natural language may be
ambiguous
:
If a man has high blood pressure and breathes with
difficulties or he has a fever then he is sick
.
p
– ”X
has high blood pressure
”
q
– ”X
breathes with difficulties
”
r
– ”X
has a fever
”
s
– ”X
is sick
”
1.
possible analysis
:
[(p
q)
r]
s
2. possible analysis:
[p
(q
r)]
s
Some more arguments
∀
∃
α
β
λ
|
-
34
If Charles has high blood pressure and breathes with
difficulties or he has a fever then he is sick
.
Charles is not sick but he breathes with difficulties.
What can be deduced
from these facts
?
We have to distinguish the
first and second
reading
,
because they are not equivalent. The conclusions will
be different
.
Some more arguments
∀
∃
α
β
λ
|
-
35
1.
analysis:
[(p
q)
r]
s,
s, q
???
a)
By means of equivalent transformations
:
[(p
q)
r]
s,
s
[(p
q)
r]
(de transposition Morgan)
(
p
q)
r
(
p
q),
r
, but
q
holds
p,
r
(consequences)
Hence
Charles does not have a high blood pressure and does not have a
fever.
Analysis of the 1. reading
∀
∃
α
β
λ
|
-
36
2.
anal
ysis
:
[p
(q
r)]
s
,
s,
q
???
a)
reasoning with equivalent transformations
:
[p
(
q
r
)
]
s,
s
[p
(
q
r
)
]
transpo
sition
,
de Morgan
:
p
(
q
r
)
but
q
is true
the second disjunct cannot be true
the
first
must be
true
:
p
(
consequence
)
Hence
Charles does not have a high blood pressure
(
we cannot conclude anything about his temperature
r)
Analysis of the 2. reading
∀
∃
α
β
λ
|
-
37
1. analysis:
[(p
q)
r]
s,
s, q |=
p,
r
2. analysis:
[p
(q
r)]
s,
s, q |=
p
home work
a)
1. case – by means of a table: home work
b)
Indirect: premises + negated conclusion
(
p
r
)
(p
r)
and we assume
that every f. is true:
•
[(p
q)
r]
s,
s, q,
p
r
•
1 1 0 1 1
•
0 0
•
0 0
•
0 1
p
r = 0
contradiction
A proof of both cases
∀
∃
α
β
λ
|
-
In the realm of Propositional Logic, it is crucial to distinguish between valid arguments and the truth of conclusions. This logical system involves forming complex sentences from elementary propositions using logical connectives. The core principle revolves around the necessary relation between premises and conclusions, focusing on logical forms rather than truth or falsity. Explore the essence of Propositional Logic in the academic setting of the Department of Computer Science at VSB - Technical University of Ostrava.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB - Technical University of Ostrava Propositiponal logic 1
Some more arguments An argument is valid iff it is necessary that under all interpretations (valuations in propositional logic), in which the premises are true the conclusion is true as well: P1,...,Pn|= Z P1,...,Pn|= Z if and only if The statement of the form P1and ... and Pnimplies Z is necessarily true (a tautology): |= (P1& & Pn) Z 2
Arguments P1, ..., Pn |= Z |= (P1& & Pn) Z iff BUT !!! It does not mean that the conclusion is (or must be) true. We are dealing with a valid logical form, a necessary relation between premises and the conclusion. 3
Arguments No prime is divisible by 3 9 is divisible by 3 ---------------------------------- 9 is not a prime It is a valid argument though the first premise is not true (3 is a prime divisible by 3). Another interpretation: All men are rational. A stone is not rational. -------------------------------- A stone is not a man. 4
Arguments Or, by substituting: If the number 12 is a prime then it is not divisible by 3. 12 is divisible by 3. 12 is not a prime. Or: 12 is not a prime number or it is not divisible by 3. 12 is divisible by 3. 12 is not a prime number. Valid argument schemes (examples of logical forms): A B, A |= B A B, B |= A, A B, B |= A A B, B |= A elimination of disjunction modus ponens modus ponens + transposition modus ponens + transposition (disjunctive syllogism) 5
Arguments Hence if we prove that the conclusion logically follows from the assumptions, then by virtue of it we do not prove that the conclusion is true It is true, provided the premises are true The argument the premises of which are true is called sound. Truthfulness or Falseness of premises can be a contingent matter. But the relation of logical entailment is a necessary relation ( in all the circumstances ... ). Similarly a tautology is a logically, necessarily true formula. If a tautology is of an implication form, then according to the definition of the implication it is true also in case of the antecedent being false, and false only in case the antecedent is true and consequent false, which corresponds to the definition of logical entailment: A1, ,An|= C iff |= A1 An C 6
Propositional (Sententional) Logic The simplest logical system. It analyzes a way of composing a complex sentence (proposition) from elementary propositions by means of logical connectives. What is a proposition? A proposition (sentence) is a statement that can be said to be true or false. The Two-Value Principle tercium non datur two-valued logic (but there are many-valued logical systems, logics of partial functions, fuzzy logics, etc.) Is the definition of a sentence trivial? Are all the statements sentences, or in other words, do all the statements denote a proposition? No, it is not so: The (current) King of France is bald. True? But then the King of France exists. False? But then it is true that the King of France is not bald, hence the King of France exists as well. The statement is neither true nor false, it is not a sentence. Did you stop beating your wife? (try to answer in case you have never been married or never beat your wife) 7
Propositional logic: semantic exposition (Semantics = meaning) There are two kinds of Sentences: Atomic (Elementary) no proper part of the sentence is a sentence as well Molecular (Composed) the sentence has its own part(s) that is (are) a sentence(s) as well The Compositionality Principle: meaning of a composed sentence is a function (depends only on) the meanings of its components. The meaning of sentences is in propositional logic reduces to: True (1), False (0). An algebra of truth values. 8
Examples of composed sentences It is raining in Prague and it is a sunshine in Brno. S1 connective S2 It is not true that it is raining in Prague. connective S 9
Definition: language of PL A formal language is defined by an alphabet (a set of symbols) and a grammar (a set of rules that define the way of forming Well Formed Formulas - WFF) Language of Propositional Logic (PL) alphabet: a) Symbols for propositions: p, q, r, ... (also with indexes p1, p2, ) b) Symbols for logical connectives: , , , , c) Auxiliary symbols: (, ), [, ], {, } Symbols ad a) stand for elementary sentences Symbols ad b), i.e., , , , , are called: negation ( ), disjunction ( ), conjunction ( ), implication ( ), equivalence ( ). 10
Definition: language of PL Grammar (defines inductively well-formed-formulas) Inductive definition of an infinite set of WFF: 1. Symbols p, q, r, ... are (well-formed) formulas (the definition base). 2. If A, B are formulas, then expressions ( ( A) ), ( (A B) ), ( (A B) ), ( (A B) ), ( (A B) ) are (well-formed) formulas (inductive definition step). 3. Only expressions due to 1. and 2. are WFFs. (the definition closure). The language of PL is the set of well-formed formulas. Note: Formulas according to 1. are atomic formulas Formulas according to 2. are composed formulas 11
Well-formed formulas Notes: Symbols A, B are metasymbols. We can substitute for them any WFF created according to the definition. The outermost parentheses can be omitted. For the logical connectives other symbols are sometimes used: Symbol alternate -------------------------------- , , & ~ Example: (p q) p is a WFF (the outer parentheses omitted) (p ) q is not a WFF 12
Definition: semantics (meaning) of formulas The truth-value valuation of propositional symbols is a mapping v that to each propositional symbol p assigns a truth value, i.e., a value from the set {1,0}, which codes the set {True, False}: {pi} {1,0} The truth-value function of a PL formula is a function w, which for each valuation v of propositional symbols pi associates the formula with its truth value in the following way: The truth value of an elementary formula p: w( (p) )v = v( (p) ) for any propositional variable p. If the truth values of formulas A, B are given, then the truth value of the formulas A, A B, A B, A B, A B are defined by the table 2.1.: 13
Table 2.1.: the truth value functions A 0 0 1 1 A B A B A B A B 1 1 1 0 1 0 0 0 A 1 1 0 0 B 1 0 1 0 1 0 0 1 1 0 1 1 14
Transforming natural language to the PL language Elementary sentences: by the propositional variables p, q, r, ... Connectives of natural language: by means of the symbols for logical connectives: Negation: it is not true that : (unary connective) Conjunction: and : (binary, commutative connection) Prague is a capital and 2+2=4: p q Note: not every and denotes a logical connective! Example: Peter came home and opened the window . Disjunction: or : (binary, commutative connection) Prague or Brno is a great city. p q non-alternative In a natural language we often use or as an alternative either, or : I ll go to the cinema or I ll stay at home Alternative or is a non-equivalence 15
Implication be careful !! if then : (binary, non-commutative connective) A B; A is the antecedent, B is the consequent. Implication (as well as any other connective of propositional logic) does not render any semantic connection between antecedent and consequent: material implication (middle ages: suppositio materialis ). Hence implication does not render a causal or chronological connection: If 1+1=2, then iron is a metal (a true proposition): p q If the UFOs (flying saucers) exist, then I am the Pope : p r (What do I want to say? Since I am not the Pope, the UFOs do not exist) 16
Implication be careful !! Note: The connectives because , therefore , since , etc. do not correspond to the logical implication! The ice-hockey team lost the match, therefore the players came home from the world championship earlier . Because I am sick, I stay at home . sick home ? But then it would have to be true even if I am not sick (see the table 2.1 the definition of implication) We might analyze it by means of the modus ponens: [p (p q)] q 17
The equivalence connective Equivalence: if and only if (iff) The Greek army used to win if and only if the result of the battle depended on their physical strength : p q It is most frequently used in mathematics (in definitions), in a natural language its use is seldom Example: cheat slap a) I ll slap you if you cheat on me cheat slap b) I ll slap you if and only if you cheat on me Situation: You did not cheat. When can you be slapped? Ad a) You may be slapped, Ad b) You might not be slapped. 18
Definition: Satisfiable formulas, tautology, contradiction, model A model of a formula A is a valuation v such that A is true in v: w(A)v= 1. A formula is satisfiable iff it has at least one model A formula is a contradiction iff it has no model A formula is a tautology iff any valuation v is its model. A set of formulas {A1, ,An} is satisfiable iff there is a valuation v such that v is a model of every formula Ai, i = 1,...,n. The valuation v is then a model of the set {A1, ,An}. 19
Satisfiable formulas, tautology, contradiction, model Example. Formula A is a tautology, A is a contradiction, formulas (p q), (p q) are satisfiable. Formula A: (p q) (p q) p q p q (p q) (p q) (p q) A p q 1 1 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 20
Logical entertaiment in PL A formula A logically follows from a set of formulas M, denoted M |= A, iff A is true in every model of the set M. Note: Mind the Definition 1 (slide 5 of Lesson 1). The circumstances are in propositional logic mapped as valuations (True 1, False - 0) of elementary atomic sentences: Under all the circumstances (means valuations of atomic propositional variables in PL) such that the premises are true the conclusion must be true as well. 21
Examples: Logical entertaiment He is at home (h) or he has gone to a pub (p) If he is at home (h) then he is waiting for us (w) If he is not waiting (w) for us then he has gone to the pub (p). h, p, w | h p, h w | w p 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 conclusion is true in all the four models of premises 22
Examples: Logical entertaiment He is at home (h) or he has gone to a pub (p) If he is at home (h) then he is waiting for us (w) If he is not waiting (w) for us then he has gone to the pub (p). h p, h w | w p The table has 2n lines! Hence, an indirect proof is more effective: Assume that the argument is not valid. But then all the premises may be true and the conclusion false: h p, h w | w p 1 1 1 0 1 0 0 contradiction 1 0 0 0 23
Examples: Logical entertaiment All the arguments with the same logical form as a valid argument are valid: h p, h w |= w p For variables h, p, w any elementary sentences can be substituted: He plays a piano or studies logic. If he plays a piano then he is a virtuous. Hence If he is not a virtuous then he studies logic. Valid argument the same valid logical form 24
Examples: Logical entertaiment The argument is valid P1,...,Pn |= Z if the formula of the implicative form is a tautology: |= (P1 ... Pn) Z. The proof that a formula is a tautology or that a conclusion Z logically follows from premises can be done: a) In the direct way for instance by a truth-value table b) In the indirect way: P1 ... Pn Z is a contradiction; hence the set of premises + the negated conclusion {P1, ..., Pn, Z} is contradictory, i.e., does not have a model: there is no valuation under which all the formulas its elements were true. 25
A proof of tautology |= ((p q) q) p Indirect: ((p q) q) p 1 1 1 1 1 1 0 contradiction There is no valuation under which the negated formula were true. Therefore, the original formula is a tautology negated f., must be a contradiction attempt whether it can be 1 26
The most important tautologies Tautologies with one propositional variable: |= p p |= p p the law of excluded middle |= (p p) the law of contradiction |= p p the law of double negation 27
Algebraic laws for conjunction, disjunction and equivalence |= (p q) (q p) |= (p q) (q p) |= (p q) (q p) commutative laws |= [(p q) r] [p (q r)] |= [(p q) r] [p (q r)] |= [(p q) r] [p (q r)] associative laws |= [(p q) r] [(p r) (q r)] |= [(p q) r] [(p r) (q r)] distributive laws 28
Laws for implication |= p (q p) |= (p p) q |= (p q) ( q p) |= (p (q r)) ((p q) r) |= (p (q r)) (q (p r)) law of simplification Duns Scot s law law of contra-position premises joint order of premises does not matter |= (p q) ((q r) (p r)) |= ((p q) (q r)) (p r) |= (p (q r)) ((p q) (p r)) |= ( p p) p |= ((p q) (p q)) p |= (p q) p , |= (p q) q |= p (p q) , |= q (p q) hypothetic sylogism transitivity of implication Frege s law reductio ad absurdum reductio ad absurdum 29
Laws for transformation |= (p q) (p q) (q p) |= (p q) (p q) ( q p) |= (p q) ( p q) ( q p) |= (p q) ( p q) |= (p q) (p q) Negation of implication |= (p q) ( p q) |= (p q) ( p q) De Morgan law De Morgan law These laws define a method for negating 30
Negation of implication Parents: If you behave well you will get a new ski at Christmas! (p q) Child: I did behave well the whole year and there is no ski under the Christmas tree! p q (Did the parents fulfill their promise?) Attorney general: If the accused man is guilty then there was an accessory in the fact Defence lawyer: It is not true ! Question: Did the advocate (defence lawyer) help the accused man; what did he actually claim? (The man is guilty and he performed the illegal act alone!) Mathematical Logic 31
Negation of implication Sentence in the future tense: If you steel it I ll kill you! It is not true: I will steel it and yet you will not kill me. p q OK, but: If the 3rdworld war breaks out tomorrow then more than three million people will be killed. It is not true: The 3rdworld war will break out tomorrow and less than three million people will be killed ??? Probably by negating the sentence we did not intend to claim that (certainly) the 3rdworld war will break out tomorrow: There is an unsaid (ecliptic) modality: Necessarily, if the 3rdworld war breaks out tomorrow then more than three million people will be killed. It is not true: Possibly the 3rdworld war breaks out tomorrow but at that case less than three million people will be killed. (p q) Handled by modal logics not a subject of this course. 32
Some more arguments Transformation from natural language may be ambiguous: If a man has high blood pressure and breathes with difficulties or he has a fever then he is sick. p X has high blood pressure q X breathes with difficulties r X has a fever s X is sick 1. possible analysis: [(p q) r] s 2. possible analysis: [p (q r)] s 33
Some more arguments If Charles has high blood pressure and breathes with difficulties or he has a fever then he is sick. Charles is not sick but he breathes with difficulties. What can be deduced from these facts? We have to distinguish the first and second reading, because they are not equivalent. The conclusions will be different. 34
Analysis of the 1. reading analysis: [(p q) r] s, s, q ??? a) By means of equivalent transformations: [(p q) r] s, s [(p q) r] ( p q) r ( p q), r, but q holds p, r (consequences) Hence Charles does not have a high blood pressure and does not have a fever. 1. (de transposition Morgan) 35
Analysis of the 2. reading analysis: [p (q r)] s, s, q ??? a) reasoning with equivalent transformations: [p (q r)] s, s [p (q r)] transposition, de Morgan: p ( q r) but q is true the second disjunct cannot be true the first must be true: p (consequence) Hence Charles does not have a high blood pressure (we cannot conclude anything about his temperature r) 2. 36
A proof of both cases 1. analysis: [(p q) r] s, s, q |= p, r 2. analysis: [p (q r)] s, s, q |= p a) 1. case by means of a table: home work b) Indirect: premises + negated conclusion ( p r) (p r) and we assume that every f. is true: [(p q) r] s, s, q, p r 1 1 0 1 1 0 0 0 0 0 1 home work p r = 0 contradiction 37
