Conidicion

Notes de L`
ogica Proposicional
L`ogica Computacional
Grau en Enginyeria Inform`atica
Universitat de Lleida
Curs 2013-14

2

´Index
1 L`
ogica Proposicional
1.1 Introducci´o . . . . . . . . . . . . .
1.2 El Llenguatge del CP0 . . . . . . .
1.2.1 Llenguatge i metallenguatge
1.3 Sem`antica . . . . . . . . . . . . . .
1.4 Tipus d’enunciats . . . . . . . . . .
1.5 Conseq¨
u`encial`ogica . . . . . . . . .
1.6 Equival`encies l`ogiques . . . . . . .
1.7 Decidibilitat . . . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

2 Procediments de prova proposicionals
2.1 Introducci´o . . . . . . . . . . . . . . .
2.2 Forma normal conjuntiva . . . . . . . .
2.3 Resoluci´o . . . . . . . . . . . . . . . .
2.3.1 Forma Clausal . . . . . . . . . .
2.3.2Principi de Resoluci´o . . . . . .
2.3.3 Completesa i solidesa . . . . . .
2.3.4 Procediments de Resoluci´o . . .

3

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
..
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
..
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

5
5
6
8
9
11
13
14
16

.
.
.
.
.
.
.

21
21
22
24
24
25
27
31

4

´INDEX

Cap´ıtol 1
L`
ogica Proposicional
1.1

Introducci´
o

La L`ogica s’ocupa de l’estudi dels mecanismes que permeten fer raonaments v`alids.
Un raonamentdiem que ´es v`alid si sempre que les premisses s´on certes la conclusi´o
´es necess`ariament certa. La l`ogica no estudia la veritat o falsetat de les premisses
i la conclusi´o a¨ılladament, sin´o la relaci´o entre la veritat o falsetat de les premisses
i la veritat o falsetat de la conclusi´o. Dit d’una altra manera, li interessa com es
propaga la veritat des de les premisses cap a laconclusi´o. Tot seguit veurem alguns
exemples de raonaments v`alids:

per tant

per tant

Si el cotxe no t´e gasolina llavors no arranca
El cotxe no t´e gasolina
el cotxe no arranca

Si el cotxe no t´e asseguranca llavors no arranca
El cotxe no t´e asseguran¸ca
el cotxe no arranca

Observem en aquests raonaments que no es pot donar que les premisses siguin certes
i la conclusi´o falsa.Aquest no ´es el cas del seg¨
uent raonament:

per tant

Si el cotxe no t´e gasolina llavors no arranca
el cotxe no arranca
el cotxe no te gasolina

aquest ´es un raonament no v`alid, ja que poden haver moltes altres raons, apart que
no hi hagi gasolina, per a que el cotxe no arranqui. La validesa d’un raonament no t´e
res a veure amb la tem`atica que tracten les premisses i lesconclusions, ni amb la seva
5

`
CAP´ITOL 1. LOGICA
PROPOSICIONAL

6

veritat o falsetat. La validesa, des d’un punt de vista l`ogic, dep´en exclusivament de
l’estructura (forma) del raonament. Els raonaments v`alids que hem fet servir com
exemples tenen la seg¨
uent forma:

per tant

Si A llavors B
A
B

Aix´ı doncs, si substituim A i B per qualsevol enunciat obtindrem un raonamentv`alid. Noteu que hi ha altres estructures de raonaments v`alids, com per exemple:

per tant

Si A llavors B
Si A llavors C
Si A llavors B i C

Els l`ogics construeixen sistemes que formalitzen la noci´o de raonament v`alid. El
primer pas, per a construir aquests sistemes, ´es definir un llenguatge formal en el
qual pogu´essim representar les premisses i les conclusions com enunciats...