Logic Lecture Notes

logic lectures
week / propositional logic
VALID ARGUMENT
"
if the train arrives late and there are no taxis at the station ,
then jane is late for her
,




meeting " .




·



jane is not l a te for the
meeting .




·

the train does arrive l a te .




·
therefore ,
there a re taxis at the station .




DECLARATIVE SENTENCES
a declarative sentence (or proposition) is a statement that is either true or false.




I
57 3 true


513 false



grass is true
green

is and roses a re blue false
grass green


grass is green or roses are blue true


if X31 ,
then x*X true




ARGUMENT ABSTRACTION
"
if the train arrives late and there are no taxis if p and not a then r
.




-
, ,




station jane is late for her ."
at the ,
then
meeting .




·



jane is not l a te for the
meeting .
not r


·

the train does arrive l a te .
P

·
therefore ,
there a re taxis at the station . therefore , 9.



key of translation

·




P the train arrives l a te



a there are taxis at the station


r
Jane is l a te fo r her meeting




logical formalization :
(((p1 -9) -
r) - (ur -p)) -
d




Validity of the arguments is due to their logical form .




it does not depend on the ac tual con te n t of propositions p, 9 and r.




SYMBOLS
we wa n t to study logic without being distracted by the concrete contents of pro-

positions .

, ropositional variables

P p , a , ,
r . . .




connectives

1 and conjunction
v op disjunction

eithe r. . . exclusive
⑰
or . . . or


not negation
>
-
if
... then . . . implication

- if and only if bi-implication



SENTENCES AND FORMULAS



I
57 3 P


grass is
green P

is blue 1
grass green and roses a re p a


grass is green or roses are blue pra

if X31 ,
then x*X p-
-
a

↳ where p: X- 1 and 9 : x2 =
X




FORMULAS OF PROPOSITIONAL LOGIC


,
P 9 , ,
r . . .
a re propositional variables .




- is a unary connective ↑




1 V 0 -
connectives .
, , , , are binary


inductive definition :




.
1 base Step


every propositional variable is a formula .




.
2 construction steps

-
a
if is a for mula ,
then so is -
(4)

-


if $ and 4 a re formulas ,
then so a re (414) ,
(414) .
(404) ,
(4e4) ,
and

(P =t .




PARSING A FORMULA
( -
(p) -q) +
(p +
(av -
(r))


porcauer
·
↓
⑮ ↓
⑰

,OMITTING PARENTHESES
to omit parentheses from formulas . Without causing ambiguity , we use the priority

schema :

1v


>
- Ex




I
spra)
va -
P va

r +
pra
-




rv(p va)
-
( -
(p)) - -

p




(p1 -
(a)) =
r) (-
(r)1p))2q
↳ (p- -

q
+ r) -( r -
p) +
q



SYNTAX AND SEMANTICS
the syntax is how a word(or formula) is written .

↳ "cow"

the semantics is its meaning
↳ "a white mammal with black spots ,
that eats grass .
"




TRUTH VALUES
formulas of propositional logic are used to express declarative statements ,
which

are either true or false.




the truth value of a formula such as Put is determined by the truth

values of its components ,
& and ↑
.


NEGATION

[
$ true if I is false
·
negation -
"not $") is

false ifI is true


& -
O

1 0



S T




CONJUNCTION

[
/"D true I
if is true and I is true
a conjunction &1 ↑ and tr") is

false all other cases


a ↑ Out

11 I


1 O O


G 1 O


g G O

, DISJUNCTION -> inclusive "or"




[
/"D true I
if is true ↑ is true /or both
a disjunction & V to or tr") is
or


false all other cases

a ↑ Out

1 1 1


1 O 1


G 1 1


000




EXCLUSIVE OR

[
$ /"either true I
if is true ↑ is true (not
an exclusive or or r") is
or

both)
false all other cases

P ↓ out

1 1 O


1 O 1


G 1 1


0 O O




IMPLICATION
# - ↑ means : if I is true ,
then t is true .

↳ I
if true and I false then - false .
,




E
- false if I is true and ↑ is false
an implication ("if & then") is

true otherwise

P ↓ # - ↓


1 1 1


1 O O



G 1 1


0 O 1




B1- IMPLICATION


[
a bi-implication & 4 ("O if and iI
f ") is true if 4 and It have the
only
to




same truth va l u e

① ↑ est
false otherwise

1 1 1



10 O


G 1 S



g G 1