El llenguatge de la Lògica Proposicional

Alfabet de la Lògica Proposicional

El llenguatge de la lògica proposicional treballa amb els següents conjunts de símbols:

• Constants: V, ⊤, 1 (Vertader) i F, ⊥, 0 (Fals)
• Variables o lletres proposicionals: p, q, r, ... A, B, C, ... , M, P, S, ...
• Símbols i connectives: ¬, ∧, ∨, →, ↔, ≡, ≢, ⊨, ⊭

Utilitzant-se els símbols lògics habituals

Definicions generals

• Si F és un símbol proposicional, aleshores F és un literal positiu
• Si F és un símbol proposicional, aleshores ¬F és un literal negatiu
• F és un literal sí i només sí F és literal positiu o negatiu
• Literals: L, L1, L2, ...
• Complementari d'un literal: L  = ¬p (si L = p) i p (si L = ¬p)
• Literals d'una fórmula: lit(F)
• Exemple: lit(p ∨ ((¬q) ∨ r )) = {p, ¬q, r }

Objectiu de la Lògica Proposicional

La lògica Proposicional pretén estudiar les frases declaratives simples (enunciats o proposicions), els elements bàsics de transmissió del coneixement humà. De manera informal, una proposició és una frase que pot ser considerada Vertader (V) o Fals (F) i que no es pot descompondre en altres frases Vertaderes o Falses.

Connectives

Per a relacionar les diferents proposicions s'utilitzen les següents connectives:

• Negació: (¬p)
• "no p"
• "és Fals p"
• "no és Vertader p"
• Conjunció: (p ∧ q)
• "p i q"
• "p però q"
• "p tanmateix q"
• "si p també q"
• "p malgrat q"
• Disjunció: (p ∨ q)
• "ó p ó q ó ambdós"
• "al menys p ó q"
• "com a mínim p ó q"
• Condicional material -implicació-: (p → q)
• "si p aleshores q"
• "p només sí q"
• "q si p"
• "q quan p"
• "q és necessari per a p"
• "per a p és necessari q"
• "p és suficient per a q"
• "per a q és suficient p"
• "no p a menys que q"
• Bicondicional material -equivalència-: (p ↔ q)
• "p és necessari i suficient per a q"
• "p sí i només sí q"

Sintaxi de la Lògica Proposicional

Les regles de formació de frases en el llenguatge de la lògica proposicional són:

• { Vertader, Fals, 1, 0, ⊤, ⊥} ⋲ LPROP
• {A, B} ⋲ LPROP → { (¬A), (¬B), (A ∨ B), (A ∧ B), (A → B), (A ↔B) } ⋲ LPROP
• per tal d'evitar l'ús excessiu del parèntesi s'estableixen les següents prioritats:
1. ¬
2. ∧, ∨
3. →, ↔

Així, per exemple, la fórmula: [((¬p) ∨ q) → (p ∧ r)] serà equivalent a: [¬p ∨ q → p ∧ r]

Semàntica de la Lògica Proposicional

La teoria semàntica de la lògica proposicional tracta d'atribuir significats (Vertader ó Fals) a les diferents fórmules del llenguatge. Aquests significats depenen del context particular en el que s'utilitzi la fórmula. Cada context es denomina Interpretació.

Definició 1

Una interpretació d'una fórmula F en lògica proposicional és una assignació de valors {Vertader, Fals} a cada una de les lletres proposicionals de F. El valor d'una proposició p sota una interpretació I s'anota com V_I(p).

Definició 2

Donada una fórmula F i una interpretació I, el valor de F sota I , anotat per V_I(F) és:

• Si F és formada per una proposició p, aleshores V_I(F) = V_I(p)
• Si F és de la forma ¬G aleshores V_I(F) serà:
• Vertader si V_I(G) = Fals
• Fals si V_I(G) = Vertader
• Si F és de la forma (G ∧ H) aleshores V_I(F) serà:
• Vertader si V_I(G) = V_I(H) = Vertader
• Fals en cas contrari
• Si F és de la forma (G ∨ H) aleshores V_I(F) serà:
• Fals si V_I(G) = V_I(H) = Fals
• Vertader en cas contrari
• Si F és de la forma (G → H) aleshores V_I(F) serà:
• Fals si V_I(G) = V i V_I(H) = Fals
• Vertader en cas contrari
• Si F és de la forma (G ↔ H) aleshores V_I(F) serà:
• Vertader si V_I(G) = V_I(H)
• Fals en cas contrari

Exemple:

Sigui la fórmula F = (p → q) ↔ ¬q ∨ ¬p i la interpretació I que assigna V_I(p) = Fals i V_I(q) = Vertader. Aleshores V_I(F) = Vertader

Definició 3

Una interpretació I és un model per a una fórmula F si V_I(F) = Vertader

Classificació de les fórmules proposicionals

És possible establir una classificació de les fórmules proposicionals en funció dels valors que prenguin sota les diferents interpretacions, d'aquesta forma una fórmula F es classifica en:

• Vàlida ó Tautologia - Totes les interpretacions són un model: Per a tota interpretació I, V_I(F) = Vertader/li>
• Satisfacible ó Contingència - Alguna interpretació és un model: Existeix alguna interpretació I tal que V_I(F) = Vertader
• Insatisfacible ó Contradicció - Cap interpretació és un model: No existeix cap interpretació I tal que V_I(F) = Vertader

Una fórmula pot ser: satisfacible o insatisfacible. Un tipus especial de fórmula satisfacible, és aquella que pren sempre valor Vertader (és vàlida). Per tant, les fórmules vàlides són un subconjunt de les satisfacibles.

Teorema 1

Una fórmula F es vàlida sí i només sí la seva negació ¬F és insatisfacible.

Demostració:

NOTA: Al llarg d'aquests apunts s'utilitza un format lineal per a les demostracions promogut per E. W. Dijkstra [Dijkstra, 90]. En aquest format, les línies senars contenen els principals passos de la demostració i les línies parells, comentaris per a passar d'un pas a altre. En ocasions, el comentari recorre a la regla de Leibniz que diu que: Si s'acompleix F(X) y X = Y aleshores també s'acompleix F(Y)

Equivalència lògica

• F i G són equivalents si es verifica: ⊨ F ↔ G, i es representa com F ≡ G

Definició 4

• F ≡ G sí i només sí per a tota interpretació I de { F, G }, seg(F, I ) = seg(G, I )

Prova:

• Dreta-Esquerra: Si per a tota interpretació I seg(F, I ) = seg(G, I ), aleshores és Vertader que per a tota I tenim: I ⊨ F ↔ G . I si això és Vertader per a tota I, aleshores podem afirmar que ⊨ F ↔ G. Que és el mateix que dir que F ≡ G.
• Esquerra-Dreta: F ≡ G implica ⊨ F ↔ G. El que significa que per a qualsevol interpretació I , es té Vertader F ↔ G. Per a qualsevol interpretació, es té que I ⊨ F ↔ G i, a la vegada, I ⊨ G ↔ F.

Raonant per reducció a l'absurd, si no fos que seg(F, I ) = seg(G, I )), es tindria un dels casos següents:

• seg(F, I ) = V i seg(G, I ) = F, el que porta a I ⊭ F → G
• seg(F, I ) = F i seg(G, I ) = V, el que porta a I ⊭ G → F

Definició 5

Es diu que dues fórmules A i B són equivalents lògicament (A ≡ B ó A ↔ B) si per a tota interpretació I, s'acompleix que V_I(A) = V_I(B).

Teorema 2

A ≡ B sí i només sí la fórmula A ↔ B és vàlida

Demostració:

NOTA:El teorema anterior redueix la demostració d'equivalència entre fórmules a la demostració de validesa d'una fórmula.

Teorema 3

Si A es vàlida i A ≡ B aleshores B es vàlida.

Demostració:

NOTA:Segons aquest teorema, si es sap que X és vàlida, per a demostrar que Z es vàlida es podrà utilitzar el format:

Equivalències lògiques d'ús comú i de fàcil demostració

• Supressió de la implicació: A → B ≡ ¬A ∨ B
• Contraposició: A → B ≡ ¬B → ¬A
• Supressió de la doble implicació: A ↔ B ≡ (A → B) ∧ (B → A)
• Absorció:

A ∧ (B ∨ A) ≡ AA ∨ (B ∧ A) ≡ ADominació:

• A ∧ Fals ≡ A
• A ∨ Vertader ≡ Vertader

Element neutre:

• A ∧ Vertader ≡ A
• A ∨ Fals ≡ A

Complementari:

• Contradicció: A ∧ ¬A ≡ Fals
• Medi exclòs: A ∨ ¬A ≡ Vertader

Idempotència:

• A ∧ A ≡ A
• A ∨ A ≡ A

Commutativa:

• A ∧ B ≡ B ∧ A
• A ∨ B ≡ B ∨ A

Associativa:

• A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C
• A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C

Distributiva:

• A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
• A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)

De Morgan:

• ¬(A ∨ B) ≡ ¬A ∧ ¬B
• ¬(A ∧ B) ≡ ¬A ∨ ¬B

Doble negació (involució): ¬ ¬ A ≡ A

Propietats de l'equivalència lògica

Les connectives preserven l'equivalència:

• Si F ≡ F', aleshores ¬F ≡ ¬F'
• Si F ≡ F', G ≡ G' i ⋆ ∈ {∨, ∧, →, ↔}, aleshores F ⋆ G ≡ F' ⋆ G

Propietat de les subfórmules equivalents

Sigui G una subfórmula de F i F' la obtinguda al substituir una ocurrència de G en F per G'. Si G ≡ G', aleshores F ≡ F'

Conseqüència Lògica

Definició 6

Sigui C un conjunt de fórmules {P₁, P₂, ...P_n} i sigui Q una fórmula. Es diu que Q és conseqüència lògica del conjunt C, i s'anotarà C ⇒ Q. si tota interpretació que és un model de C és també un model de Q.

És a dir, si per a tota interpretació I s'acompleix que si V_I(P₁) = V_I(P₂) = ... = V_I(P_n) = Veritat, aleshores s'acompleix V_I(Q) = Veritat

Intuïtivament, es podria considerar cada interpretació com una possible situació. Dir que Q és conseqüència lògica d'unes premisses és equivalent a pensar que Q pren valor Veritat en qualsevol situació en la que les premisses prenen valor Veritat.

Una estructura de la forma {P₁, P₂, ...P_n} ⇒ Q s'anomena raonament. On {P₁, P₂, ...P_n} és el conjunt de premisses i Q és la conclusió.

Es diu que un raonament és correcte si la conclusió és conseqüència lògica de les premisses.

Teorema 4

{P₁, P₂, ...P_n} ⇒ Q és correcte sí i només sí P₁ ∧ P₂ ∧ ··· ∧ P_n → Q és vàlida.

Demostració:

 

Jordi Coll Vera - 2020