Lògica proposicional Sec1

Petita introducció a la lògica proposicional

Exercicis previstos

1) Determineu quines expressions són fórmules proposicionals.

a) $P$ b) $PQ\lor S$ c) $\neg (P\rightarrow P)$ d) $(\neg P)\rightarrow P$ e) $\neg P\neg Q$ f) $P\leftrightarrow (\neg Q)$

g) ${\big (}(P\lor )\land Q{\big )}$ h) ${\big (}\neg (P\rightarrow Q){\big )}\land (\neg R)$ i) $\lor P\land Q$ j) $P\lor (Q\neg R)$ k) $P\lor (Q\land R)$ l) $P\lor Q\land R$

2) Elimineu tots els parèntesis innecessaris

a) $(P\land Q)\rightarrow {\big (}\neg (R){\big )}$ b) ${\Big (}\neg {\big (}P\land (Q\rightarrow R){\big )}{\Big )}\lor (S\lor P)$ c) ${\Big (}P\rightarrow {\big (}Q\rightarrow (R\rightarrow S){\big )}{\Big )}$ d) ${\Big (}{\big (}(P\rightarrow Q)\rightarrow R{\big )}\rightarrow S)$ e) ${\bigg (}{\Big (}\neg {\big (}P\land (\neg Q){\big )}{\Big )}\land {\big (}\neg (R\lor S){\big )}{\bigg )}$

f) ${\Big (}{\big (}(\neg P)\lor (\neg Q){\big )}\rightarrow {\big (}(\neg R)\land S{\big )}{\Big )}$ g) ${\bigg (}{\big (}\neg (\neg P){\big )}\land {\Big (}\neg {\big (}(P\rightarrow R)\lor Q{\big )}{\Big )}{\bigg )}$ h) ${\big (}(P\land Q)\lor {\big )}$ i) ${\big (}P\land (Q\lor R){\big )}$ j) ${\Big (}\neg {\big (}(\neg P)\lor \neg (Q){\big )}{\Big )}$

3) Escriviu tots els parèntesis superflus i determineu quina és la connectiva principal

a) $\neg R\lor R$ b) $P\land Q\rightarrow R$ c) $P\land Q\land R$ d) $P\land Q\lor R$ e) $P\lor \neg Q\rightarrow \neg R\lor \neg (S\rightarrow Q)$

f) $\neg \neg P\land \neg Q$ g) $\neg (\neg R\rightarrow S\lor P)$ h) $P\rightarrow Q\rightarrow R$ i) $P\rightarrow Q\land S\rightarrow R$ j) $(P\land \neg Q)\lor S\rightarrow P$

4) Formalitzeu les següents frases mitjançant fórmules proposicionals.

Nota: per formalitzar frases hem de identificar els àtoms que seran idees concretes que simplement no es poden trencar en altres àtoms ( A, B, C, ... , P, Q, R, S, ...) i connectius ($\neg$ = la negació, $\,\lor$ = o = la disjunció, $\land$ = i = la conjunció, $\rightarrow$ = tenir com a conseqüència = implicació i $\leftrightarrow$ = si, i solament si = equivalència).

a) Ser o no ser. b) Si menjo massa i em prenc un cafè, no puc dormir. c) Sempre que la vaixella xinesa de porcellana que vam comprar a Hong Kong es renta amb aigua massa calenta, es trenquen un parell de plats d'aquells tan fins que no sé perquè serveixen. d) Si fas els deures, no et castiguen; i si no(no fas els deures), sí(et castiguen). e) Quan vaig a la platja , llegeixo el diari o em banyo(però no les dues coses) f) Quan plou i fa sol, surt l'arc de Sant Martí i estic content. g) Si quan plou, fa sol, aleshores surt l'arc de Sant Martí i estic content. h) Quan plou i surt l'arc de Sant Martí, estic content si fa sol. i) Plou, fa sol, surt l'arc de Sant Martí i estic content. j) Quan no plou, no surt l'arc de Sant Martí i no estic content si no fa sol. k) Quan no plou no surt l'arc de Sant Martí, i no estic content si no fa sol. l) Només et mulles quan plou. m) Una relació és d'equivalència si, i només si és reflexiva, simètrica i transitiva. n) No es podrà curar el càncer fins que no es determini la seva causa i es trobi un nou medicament. o) Es necessita coratge i habilitat per escalar una muntanya. p) Quan sento parlar dels darrers aconteixements, ni entec que passa, ni sento simpatia per les persones involucrades. q) Si vaig en cotxe, trobo aparcament quan arribo aviat. r) Si vaig en cotxe, només trobo aparcament quan arribo aviat. s) Quan cal portar calculadora per aprovar, cal recordar les fórmules per estar tranquil. t) Tant si plou com si neva, cal portar gavardina per no mullar-se.

Semàntica

Combinacions de V i F segons la quantitat d'àtoms.
1 ${\begin{array}{c}P\\\hline V\\F\end{array}}$	2 ${\begin{array}{cc}P&Q\\\hline V&V\\V&F\\F&V\\F&F\end{array}}$	3 ${\begin{array}{ccc}P&Q&R\\\hline V&V&V\\V&V&F\\V&F&V\\V&F&F\\F&V&V\\F&V&F\\F&F&V\\F&F&F\end{array}}$

La següent secció vol analitzar la veracitat d'una determinada afirmació, però, aquesta veracitat(V) o falsedat(F) dependrà de les condicions inicials de veracitat de cada àtom que compon aquesta afirmació. Per fer aquest anàlisi cal estudiar totes les possibles combinacions de V i F que tenen aquests àtoms, així si cada àtom té 2 valors V i F, llavors 5 àtoms tenen $2^{5}$ valors que són 32 possibles valors.

Per estalviar contingut s'ha de pensar en si determinats successos són possibles a la fórmula proposicional, llavors direm que són verdaders en cas contrari falsos. Un altre forma és pensar en si determinats successos poden contradir la hipòtesi o fórmula proposicional, llavors direm que són falsos en cas contrari verdader.

Podem omplir taules a partir de les taules següents:

${\begin{array}{c|cc}P&\neg P\\\hline V&F\\F&V\\\end{array}}$ ${\begin{array}{cc|c}P&Q&P\rightarrow Q\\\hline V&V&V\\V&F&F\\F&V&V\\F&F&V\\\end{array}}$ ${\begin{array}{cc|c}P&Q&P\leftrightarrow Q\\\hline V&V&V\\V&F&F\\F&V&F\\F&F&V\\\end{array}}$ ${\begin{array}{cc|c}P&Q&P\lor Q\\\hline V&V&V\\V&F&V\\F&V&V\\F&F&F\\\end{array}}$ ${\begin{array}{cc|c}P&Q&P\land Q\\\hline V&V&V\\V&F&F\\F&V&F\\F&F&F\\\end{array}}$

Per fer taules de la veritat d'una fórmula proposicional només cal ser conscient del seu arbre i fer la taula començant per les puntes(àtoms) i arribar fins la tija(fórmula proposicional), exemple per completar:

5) Fes l'arbre i omple la taula de veritat de la fórmula $P\lor \neg Q\rightarrow \neg (P\land \neg Q)$

${\begin{array}{cc||c|c|c|c|c}P&Q&\neg Q&P\lor \neg Q&P\land \neg Q&\neg (P\land \neg Q)&P\lor \neg Q\rightarrow \neg (P\land \neg Q)\\\hline V&V&&\\V&F&&\\F&V&&\\F&F&&\\\end{array}}$

6) Feu les taules de la veritat per cada apartat.

a) $\neg \neg P\rightarrow P$

b) $(P\rightarrow Q)\rightarrow (\neg Q\rightarrow \neg P)$

c) $P\lor (Q\rightarrow \neg P)$

d) $\neg P\rightarrow P$

e) $P\lor Q\rightarrow \neg (R\land Q)$

f) $\neg {\big (}P\lor (Q\rightarrow R){\big )}\land (R\lor \neg P)$

g) $\neg (P\lor \neg Q)\land \neg Q$

h) $P\lor (P\rightarrow Q)$

i) $\neg P\land {\big (}\neg (P\rightarrow Q){\big )}$

j) $P\rightarrow P\land Q$

k) $(P\rightarrow Q)\rightarrow (Q\rightarrow P)$

l) $(P\lor \neg Q)\land (\neg P\lor Q)$

7) Demostreu les següents equivalències

a) $(P\rightarrow Q)\land (P\rightarrow R)\approx {\big (}P\rightarrow (Q\land R){\big )}$

b) $(P\rightarrow Q)\rightarrow (P\land Q)\approx (\neg P\rightarrow Q)\land (Q\rightarrow P)$

c) $P\land Q\land (\neg P\lor \neg Q)\approx \neg P\land \neg Q\land (P\lor Q)$

d) $P\lor {\big (}P\rightarrow (P\land Q){\big )}\approx \neg P\lor \neg Q\lor (P\land A)$