close

Вход

Log in using OpenID

embedDownload
Introduction to Logic
(‘Methodenkurs Logik’)
Winter term 2014-2015
Mondays 2:30--4:00pm @ 2321.HS 3H
INSTRUCTOR
Todor Koev (Todor.Koev@uni-duesseldorf.de)
Propositional logic: semantics
 Logical translations
 Truth tables
 Working with truth tables
 Special formulas: contingencies, tautologies, contradictions
Syntax of propositional logic
 We now know how (well-formed) formulas of propositional
are constructed.
 We know that roughly:
o p
o pq
o pq
o pq
o p q
means
means
means
means
means
‘it’s not the case that p’
‘p and q’
‘p or q’
‘if p, then q’
‘p just when q’
 We can then translate back and forth between English and
propositional logic.
Logical translations I
 Translating English into propositional logic:
(1) Jay Z is cool.  p
translation key: p = ‘Jay Z is cool’
pq
(2) Jay Z is cool and Kim K is annoying. 
translation key: p = ‘Jay Z is cool’, q = ‘Kim K is annoying’
(3) If I don’t kiss Sarah Dingens, I’ll cry.  p  q
translation key: p = ‘I kiss Sarah Dingens’, q = ‘I’ll cry’
 Hint: Try to represent in the propositional logic formula all
logical connectives found in the English sentence.
Logical translations II
(4) The engine is not noisy and it does not use a lot of gas.
translation key: p = ‘the engine is noisy’, q = ‘the engine
uses a lot of gas’
 p  q
(5) Nobody laughed or applauded.
translation key 1: p = ‘nobody laughed’, q = ‘nobody
applauded’
p  q (Q: Anything funny about this translation?)

translation key 2: p = ‘somebody laughed’, q = ‘somebody
applauded’
 ( p  q )
Language and the Mind
 Gottfried Leibniz (1646-1706) envisaged creating an artificial “universal
language” which represents concepts/ideas and provides logical rules for
their valid manipulation.
 Natural languages stand for complex, or derivative, concepts that can be
reduced to simpler concepts.
 “…when there are disputes among persons, we can simply say: Let us
calculate, without further ado, and see who is right.” (G. Leibniz)
Truth tables
 Truth tables are an easy way of determining the truth value
of a complex formula from the truth values of its immediate
parts and the connective that connects those parts. (It is
assumed that each sentence is true or false.)
 Truth tables thus obey the Principle of Compositionality!
 There is a truth table for each connective.
 Truth tables can be regarded as providing the meaning of
propositional connectives (i.e., negation, conjunction,
disjunction, implication, and equivalence).
Negation
 
1
0
0
1
 If the first sentence is true/false, then the second sentence is false/true.
(6) People in Düsseldorf are friendly.
(7) People in Düsseldorf are not friendly.
 Potential issues: “Metalinguistic” negation can negate any feature of a
sentence:
(8) He doesn’t eat pot[a]toes. He eats pot[ej]toes.
(9) He is not smart. He is a genius!
Conjunction
   
1
1
0
0
1
0
1
0
1
0
0
0
 The following sentence is true only if both parts are true.
(10) Jay Z is cool and Kim K is annoying.
 Potential issues:
(11) She got married and got pregnant. ≠ She got pregnant and got married.
(12) He has rich parents but he doesn’t have any money.
(13) Faruk traveled to Istanbul. He has family there.
Disjunction
   
1
1
0
0
1
0
1
0
1
1
1
0
 The following sentence is true as long as one part of it is true.
(14) Jay Z is cool or Kim K is annoying.
 Potential issue: English ‘or’ may be exclusive, i.e. require that    is
false when both  and  are true.
(15) He is either in Paris or (he is) in Berlin.
(16) He is in Paris or (he is) in Berlin.
Implication
   
1
1
0
0
1
0
1
0
1
0
1
1
 The conditional sentence below is false only when the antecedent (=the
if-clause) is true and the consequent is false.
(17) If Hans passed the exam, he will happy.
 Problem: Counterfactual conditionals are incorrectly predicted to be
always true because the antecedent is false.
(18) If I was a millionaire, I would stop teaching logic.
 Our ‘material’ implication doesn’t say much about counterfactual sents.
Equivalence
   
1
1
0
0
1
0
1
0
1
0
0
1
 An equivalence is true when the two formulas have the same truth value:
both are true or both are false.
(19) I’ll go out (if and) only if you do the dishes.
Working with truth tables 1
 Truth tables derive the truth value of a complex formula from
the truth values of the atomic parts.
 We consider all possible combinations of truth values
assigned to atomic sentences and derive
 We only need to know how the formula was constructed. For
this purpose, we first draw the construction tree.
Working with truth tables 2
 Example: Provide a truth table for the formula ( p  q )  p .
( p  q )  p (iii,  , omitting outer parens)
 Construction tree:
( p  q ) (iii,)
p (i)
q (i)
p (ii)
p (i)
 Truth table:
p
1
1
0
0
q p  q p ( p  q )  p
1
1
0
1
0
0
0
0
1
1
1
1
0
1
1
1
Boolean operators
 The connectives  ,  ,  are called Boolean operators (after
George Boole).
 Those operators have nice formal properties (to be discussed next
week) and have been fundamental in the development of modern
digital electronics.
 Boolean operators and searches:
https://www.youtube.com/watch?v=lPEmrzTOWEg
Special formulas: contingencies
 Most formulas of propositional logic are true or false, depending on the
truth values assigned to their atomic sentences.
 Such formulas are called contingencies. Contingencies have both 1s and
0s in the final column of their truth table.
 For example, p  q is a contingency:
p
1
1
0
0
q
1
0
1
0
pq
1
0
0
0
 Fact 1: If  is a contingency,  is also a contingency. Why?
Special formulas: tautologies
 Some formulas however are always true, independently of the truth values
of their atomic sentences.
 Such formulas are called tautologies. Tautologies only have 1s in the final
column of their truth table.
 For example, p  p is a tautology (because p is either true or false, no
third option left).
p
1
0
p p  p
0
1
1
1
Special formulas: contradictions
 Finally, some formulas are always false, no matter what the truth values
of their atomic sentences are.
 Such formulas are called contradictions. Contradictions only have 0s in
the final column of their truth table.
 For example, p  p is a contradiction (because p cannot be both true and
false).
p
1
0
p p  p
0
0
1
0
 Fact 2: If  is a tautology,  is a contradiction (and vice versa). Can you
tell why?
For next time
 No new reading!
1/--pages
Пожаловаться на содержимое документа