Llògica proposicional

La llògica proposicional, també cridada llògica d'enunciats, llògica d'orde zero o càlcul proposicional, és un sistema formal els elements del qual més simples representen proposicions o enunciats, i que les seues constants llògiques, cridades conectivas llògiques, representen operacions sobre proposicions, capaces de formar atres proposicions de major complexitat.

Les llògiques proposicionals carixen de quantificadors o variables d'individu, pero tenen variables proposicionals (és dir, que es poden interpretar com a proposicions en un valor de veres definit), d'ahí el nom proposicional. Els sistemes de llògica proposicional inclouen ademés conectivas llògiques, per lo que dins d'este tipo de llògica es pot analisar l'inferència llògica de proposicions a partir de proposicions, pero sense tindre en conte l'estructura interna de les proposicions més simples.

Com les llògiques proposicionals no tenen quantificadors o variables d'individu, qualsevol seqüència de signes que constituïxca una fòrmula ben formada admet una valoració en la proposició és verdadera o falsa depenent del valor de veres assignat a les proposicions que la componguen. Açò implica que qualsevol fòrmula ben formada definix una funció proposicional. Per tant, qualsevol sistema llògic basat en la llògica proposicional és decidible i en un número finit de passos es pot determinar la veritat o falsetat semàntica d'una proposició. Açò fa que la llògica proposicional siga completa i en una semàntica molt senzilla.

Introducció

Considere's el següent argument:

1. Demà és dimecres o demà és dijous.
2. Demà no és dijous.
3. Per lo tant, demà és dimecres.

És un argument vàlit. Vol dir que és impossible que les premissas (1) i (2) siguen verdaderes i la conclusió (3) falsa.

No obstant, a pesar de que l'argument siga vàlit, açò no vol dir que la conclusió siga verdadera. En atres paraules, si les premisses són falses, llavors la conclusió també podria ser-ho. Pero si les premisses són verdaderes, llavors la conclusió també ho és. La validea de l'argument no depén del significat de les expressions «demà és dimecres» ni «demà és dijous», sino de l'estructura mateixa de l'argument. Estes premisses podrien canviar-se per unes atres i l'argument permaneixeria vàlit. Per eixemple:

1. Hui està solejat o està nuvolat.
2. Hui no està nuvolat.
3. Per lo tant, hui està solejat.

La validea dels dos arguments anteriors depén del significat de les expressions «o» i «no». Si alguna d'estes expressions es canvia per una atra, llavors els arguments podrien deixar de ser vàlits. Per eixemple, considere's el següent argument inválido:

1. Ni està solejat ni està nuvolat.
2. No està nuvolat.
3. Per lo tant, està solejat.

Estes expressions com «o» i «no», de les que depén la validea dels arguments, es diuen conectivas llògiques. Sobre expressions com «està nuvolat» i «demà és dijous», lo únic que importa d'elles és que tinguen un valor de veres. És per açò que li les reemplaça per simples lletres, l'intenció de les quals és simbolisar una expressió en valor de veres qualsevol. A estes lletres li les crida variables proposicionals, i en general es prenen de l'alfabet llatí, escomençant per la lletra p (de «proposició») despuix q, r, s, etc. És aixina que els dos primers arguments d'esta secció es podrien reescriure aixina:

1. p o q
2. No q

1. Per lo tant, p

I el tercer argument, a pesar de no ser vàlit, es pot reescriure aixina:

1. Ni p ni q
2. No q
3. Per lo tant, p

Conectivas llògiques

Artícul principal → Conectiva llògica.

A continuació hi ha una taula que desplega totes les conectivas llògiques que ocupen a la llògica proposicional, incloent eixemples del seu us en el llenguage natural i els símbols que s'utilisen per a representar-les en llenguage formal.

Conectiva	Expressió en el llenguage natural	Eixemple	Símbol en este artícul	Símbols alternatius
Negació	no	No està plovent.	$\mathrm{\neg }$	$\sim$
Conjunció	i	Està plovent i està nuvolat.	$\wedge$	&
Disjunció	o	Està plovent o està solejat.	$\vee$	|
Condicional material	si... llavors	Si està solejat, llavors és de dia.	$\to$	$\supset$
Bicondicional	si i solament si	Està nuvolat si i solament si hi ha núvols visibles.	$\leftrightarrow$	$\equiv$
Disjunció oposta	ni... ni	Ni està solejat ni està nuvolat.	$\downarrow$
Disjunció exclusiva	o be... o be	O be està solejat, o be està nuvolat.	$\nleftrightarrow$	$\oplus ,\equiv ̸,W$

En la llògica proposicional, les conectivas llògiques es tracten com funcions de veres. És dir, com funcions que prenen conjunts de valors de veres i tornen valors de veres. Per eixemple, la conectiva llògica «no» és una funció que si pren el valor de veres V, torna F, i si pren el valor de veres F, torna V. Per lo tant, si s'aplica la funció «no» a una lletra que represente una proposició falsa, el resultat serà alguna cosa verdader. Si és fals que «està plovent», llavors serà verdader que «no està plovent».

El significat de les conectivas llògiques no és res més que el seu comportament com a funcions de veres. Cada conectiva llògica es distinguix de les atres pels valors de veres que torna front a les distintes combinacions de valors de veres que pot rebre. Açò vol dir que el significat de cada conectiva llògica pot ilustrar-se per mig d'una taula que desplegue els valors de veres que la funció torna front a totes les combinacions possibles de valors de veres que pot rebre.

Negació	Conjunció	Disjunció	Condicional	Bicondicional	Disjunció exclusiva
$\begin{array}{cc}p& \mathrm{\neg }p\\ F& V\\ V& F\end{array}$	$\begin{array}{ccc}p& q& p\wedge q\\ V& V& V\\ F& V& F\\ V& F& F\\ F& F& F\end{array}$	$\begin{array}{ccc}p& q& p\vee q\\ V& V& V\\ F& V& V\\ V& F& V\\ F& F& F\end{array}$	$\begin{array}{ccc}p& q& p\to q\\ V& V& V\\ F& V& V\\ V& F& F\\ F& F& V\end{array}$	$\begin{array}{ccc}p& q& p\leftrightarrow q\\ V& V& V\\ F& V& F\\ V& F& F\\ F& F& V\end{array}$	$\begin{array}{ccc}p& q& p\nleftrightarrow q\\ V& V& F\\ F& V& V\\ V& F& V\\ F& F& F\end{array}$

Lleis notables en llògica

Entre les regles de la llògica proposicional clàssica algunes de la més notables són llistades a continuació:

• Llei de doble negació.
• Lleis d'idempotencia.
• Lleis Asociatividad.
• Lleis conmutativas.
• Lleis distributivas.
• Lleis de De Morgan.

Atres lleis com el principi del tercer exclós són admissibles en llògica clàssica, pero en llògica intuicionista i en fins a les seues aplicacions matemàtiques no existix un equivalent del tercer exclós.

Llímits de la llògica proposicional

La maquinària de la llògica proposicional permet formalisar i teorizar sobre la validea d'una gran cantitat d'arguments. No obstant, també existixen arguments que són intuitivamente vàlits, pero la validea dels quals no es pot provar per la llògica proposicional. Per eixemple, considere's el següent argument:

1. Tots els hòmens són mortals.
2. Sócrates és un home.
3. Per lo tant, Sócrates és mortal.

Com este argument no conté cap de les conectivas «no», «i», «o», etc., segons la llògica proposicional, la seua formalisació serà la següent:

1. p
2. q

1. Per lo tant, r

Pero esta és una forma d'argument inválida, i això contradiu la nostra intuïció de que l'argument és vàlit. Per a teorizar sobre la validea d'este tipo d'arguments, es necessita investigar l'estructura interna de les variables proposicionals. D'açò s'ocupa la llògica de primer orde. Atres sistemes formals permeten teorizar sobre atres tipos d'arguments. Per eixemple la llògica de segon orde, la llògica modal i la llògica temporal.

Dos sistemes formals de llògica proposicional

A continuació es presenten dos sistemes formals estàndar per a la llògica proposicional. El primer és un sistema axiomàtic simple, i el segon és un sistema sense axioma, de deducció natural.

Sistema axiomàtic

Alfabet

L'alfabet d'un sistema formal és el conjunt de símbols que pertanyen al llenguage del sistema. Si L és el nom d'este sistema axiomàtic de llògica proposicional, llavors l'alfabet de L consistix en:

• Una cantitat finita pero arbitrariamente gran de variables proposicionals. En general li les pren de l'alfabet llatí, escomençant per la lletra p, despuix q, r, etc., i utilisant subíndexs quan és necessari o convenient. Les variables proposicionals representen proposicions com "està plovent" o "els metals s'expandixen en la calor".
• Un conjunt d'operadors llògics: $\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$
• Dos signes de puntuació: els paréntesis esquerre i dret. La seua única funció és desambiguar certes expressions ambigües, en exactament el mateix sentit en que desambiguan l'expressió 2 + 2 ÷ 2, que pot significar tant (2 + 2) ÷ 2, com 2 + (2 ÷ 2).

Gramàtica

Una volta definit l'alfabet, el següent pas és determinar qué combinacions de símbols pertanyen al llenguage del sistema. Açò es conseguix per mig d'una gramàtica formal. La mateixa consistix en un conjunt de regles que definixen recursivamente les cadenes de caràcters que pertanyen al llenguage. A les cadenes de caràcters construïdes segons estes regles li les crida fòrmules ben formades. Les regles del sistema L són:

1. Les variables proposicionals de l'alfabet de L són fòrmules ben formades.
2. Si $\varphi$ és una fòrmula ben formada de L, llavors $\mathrm{\neg }\varphi$ també ho és.
3. Si $\varphi$ i $\psi$ són fòrmules ben formades de L, llavors $(\varphi \wedge \psi )$, $(\varphi \vee \psi )$, $(\varphi \to \psi )$ i $(\varphi \leftrightarrow \psi )$ també ho són.
4. Solament les expressions que poden ser generades per mig de les clàusules 1 a 3 en un número finit de passos són fòrmules ben formades de L.

Segons estes regles, les següents cadenes de caràcters són eixemples de fòrmules ben formades:

$p$

$\mathrm{\neg }\mathrm{\neg }\mathrm{\neg }q$

$(p\wedge q)$

$\mathrm{\neg }(p\wedge q)$

$(p\leftrightarrow \mathrm{\neg }p)$

$((p\to q)\wedge p)$

$(\mathrm{\neg }(p\wedge (q\vee r))\vee s)$

I els següents són eixemples de fòrmules mal formades^{cita requerida}:

Fòrmula	Error	Correcció
$(p)$	Sobren paréntesis	$p$
$\mathrm{\neg }(p)$	Sobren paréntesis	$\mathrm{\neg }p$
$(\mathrm{\neg }p)$	Sobren paréntesis	$\mathrm{\neg }p$
$p\to q$	Falten paréntesis	$(p\to q)$
$(p\wedge q\to r)$	Falten paréntesis	$((p\wedge q)\to r)$

Per una atra part, ya que l'única funció dels paréntesis és desambiguar les fòrmules, en general s'acostuma ometre els paréntesis externs de cada fòrmula, ya que estos no complixen cap funció. Aixina per eixemple, les següents fòrmules generalment es consideren ben formades:

$p\wedge q$

$\mathrm{\neg }p\to q$

$(p\wedge q)\vee \mathrm{\neg }q$

$(p\leftrightarrow q)\leftrightarrow (q\leftrightarrow p)$

Una atra convenció sobre l'us dels paréntesis és que les conjuncions i les disjunció tenen «menor jerarquia» que els condicionals materials i els bicondicionales. Açò significa que donada una fòrmula sense paréntesis, les conjuncions i les disjunció deuen agrupar-se abans que els condicionals materials i els bicondicionales. Per eixemple:

Fòrmula	Llectura correcta	Llectura incorrecta
$p\wedge q\to r$	$(p\wedge q)\to r$	$p\wedge (q\to r)$
$\mathrm{\neg }p\leftrightarrow q\vee r$	$\mathrm{\neg }p\leftrightarrow (q\vee r)$	$(\mathrm{\neg }p\leftrightarrow q)\vee r$
$p\wedge q\leftrightarrow r\vee s$	$(p\wedge q)\leftrightarrow (r\vee s)$	$(p\wedge (q\leftrightarrow r))\vee s$

Estes convencions són anàlogues a les que existixen en l'àlgebra elemental, a on la multiplicació i la divisió sempre deuen resoldre's abans que la suma i la resta. Aixina per eixemple, l'equació 2 + 2 × 2 podria interpretar-se com (2 + 2) × 2 o com 2 + (2 × 2). En el primer cas el resultat seria 8, i en el segon cas seria 6. Pero com la multiplicació sempre deu resoldre's abans que la suma, el resultat correcte en este cas és 6, no 8.

Axioma

Els axioma d'un sistema formal són un conjunt de fòrmules ben formades que es prenen com a punt de partida per a demostracions ulteriors. Un conjunt de axioma estàndar és el que va descobrir Jan Łukasiewicz:

• $(p\to (p\to p))$
• $((p\to (p\to r))\to ((p\to p)\to (p\to r)))$
• $((\mathrm{\neg }p\to \mathrm{\neg }p)\to (p\to p))$

Regles d'inferència

Una regla d'inferència és una funció que va de conjunts de fòrmules a fòrmules. Al conjunt de fòrmules que la funció pren com a argument li'l crida premisses, mentres que a la fòrmula que torna com a valor li la crida conclusió. En general es busca que les regles d'inferència transmeten la veritat de les premisses a la conclusió. És dir, que siga impossible que les premisses siguen verdaderes i la conclusió falsa. En el cas de L, l'única regla d'inferència és el modus ponens, el qual diu:

$(p\to q),p⊢q$

Recordant que $pyq$ no són fòrmules, sino metavariables que poden ser reemplaçades per qualsevol fòrmula ben formada.

Deducció natural

Artícul principal → Deducció natural.

Siga ${ℒ}_2=ℒ(\mathrm{A},\Omega ,\mathrm{Z},\mathrm{I})$, a on $\mathrm{A}$, $\Omega$, $\mathrm{Z}$, $\mathrm{I}$, es definix com:

• El conjunt Alfa $\mathrm{A}$ és un conjunt finit de símbols que és lo suficientment gran com per a satisfer les necessitats d'una discussió donada, per eixemple:

  $\mathrm{A}=\{p,q,r,s,t,u\}.$

• El conjunt Omega $\Omega ={\Omega }_1\cup {\Omega }_2$ com a partició de

*: ${\Omega }_1=\{\mathrm{\neg }\},$

• ${\Omega }_2=\{\wedge ,\vee ,\to ,\leftrightarrow \}.$

En el següent eixemple és d'un càlcul proposicional, les regles presentades de transformació tenen que ser interpretades com a regles d'inferència d'un sistema de deducció natural. El sistema particular ací presentat no té punts inicials, lo que significa que la seua interpretació per a les aplicacions llògiques deriva d'una teorema de conjunts de axioma buits.

*El conjunt de punts inicials està buit, est és $\mathrm{I}=\varnothing$.

*El conjunt de regles de transformació $\mathrm{Z}$ es descriu com :

El nostre càlcul proposicional té dèu regles d'inferència. Estes regles nos permeten derivar atres fòrmules verdaderes donat un conjunt de fòrmules que se supon que són verdaderes. Les primeres nou simplement declaren que podem inferir certes fòrmules ben formades d'atres fòrmules ben formades; i l'última regla utilisa el raonament hipotètic en el sentit de que la premissa de la regla assumixca temporalment una hipòtesis( no provada) per a formar part del conjunt de fòrmules deduïdes per a vore si podem inferir alguna atra fòrmula. Ya que les primeres nou regles no són hipotètiques , usualment es descriurien com a regles no hipotètiques, i l'última regla com una regla hipotètica.

En descriure les regles de transformació, podem introduir un símbol de metallenguage $⊢$. És bàsicament una taquigrafia convenient per a dir " inferir que ". El format és $\Gamma ⊢\psi$, en el qual Γ és un conjunt de fòrmules nomenades premisses, i ψ és una fòrmula per a trobar la conclusió. La regla de tranformacíon $\Gamma ⊢\psi$ significa que si tota proposició enΓ és una teorema ( o té el mateix valor de veres que els axioma ), llavors ψ és també una teorema. Tinga en conte que tenint en conte la següent regla l'introducció de conjunció Γ té més d'una fòrmula, sempre podem reduir-la en seguritat en una fòrmula usant una conjunció. Aixina que per a abreviar, a partir d'eixe moment podem representar Γ com una fòrmula en lloc d'un conjunt. Una atra omissió per conveniència és quan Γ és un conjunt buit, en el cas del qual Γ pot no aparéixer.

Un sistema de llògica proposicional també pot construir-se a partir d'un conjunt buit d'axiomas. Per a això s'especifiquen una série de regles d'inferència que intenten capturar el modo en que naturalment raonem sobre les conectivas llògiques.

Introducció de la negació

De $(p\to q)$ i $(p\to \mathrm{\neg }q)$, es infiere $\mathrm{\neg }p$.

Açò és, $\{(p\to q),(p\to \mathrm{\neg }q)\}⊢\mathrm{\neg }p$.

Eliminació de la negació

De $\mathrm{\neg }p$, es infiere $(p\to r)$.

Açò és, $\{\mathrm{\neg }p\}⊢(p\to r)$.

Eliminació de la doble negació

De $\mathrm{\neg }\mathrm{\neg }p$, es infiere $p$.

Açò és, $\mathrm{\neg }\mathrm{\neg }p⊢p$.

Introducció de la conjunció

De $p$ i $q$, es infiere $(p\wedge q)$.

Açò és, $\{p,q\}⊢(p\wedge q)$.

Eliminació de la conjunció

De $(p\wedge q)$, es infiere $p$.

De $(p\wedge q)$, es infiere $q$.

Açò és, $(p\wedge q)⊢p$ i $(p\wedge q)⊢q$.

Introducció de la disjunció

De $p$, es infiere $(p\vee q)$.

Açò és, $p⊢(p\vee q)$ i $q⊢(p\vee q)$.

Eliminació de la disjunció

De $(p\vee q)$ i $(p\to r)$ i $(q\to r)$, es infiere $r$.

Açò és, $\{p\vee q,p\to r,q\to r\}⊢r$.

Introducció del bicondicional

De $(p\to q)$ i $(q\to p)$, es infiere $(p\leftrightarrow q)$.

Açò és, $\{p\to q,q\to p\}⊢(p\leftrightarrow q)$.

Eliminació del bicondicional

De $(p\leftrightarrow q)$, es infiere $(p\to q)$.

De $(p\leftrightarrow q)$, es infiere $(q\to p)$.

Açò és, $(p\leftrightarrow q)⊢(p\to q)$ i $(p\leftrightarrow q)⊢(q\to p)$.

Modus ponens (eliminació del condicional)

De $p$ i $(p\to q)$, es infiere $q$.

Açò és, $\{p,p\to q\}⊢q$.

Prova condicional (introducció del condicional)

De [acceptant que $p$ permet una prova de $q$], es infiere $(p\to q)$.

Açò és, $(p⊢q)⊢(p\to q)$.

Formes d'arguments bàsiques i derivades

Nom	Conseqüent	Descripció
Modus ponens	$((p\to q)\wedge p)⊢q$	Si $p$ llavors $q$; i $p$; per lo tant $q$
Modus tollens	$((p\to q)\wedge \mathrm{\neg }q)⊢\mathrm{\neg }p$	Si $p$ llavors $q$; i no $q$; per lo tant no $p$
Silogisme hipotètic	$((p\to q)\wedge (q\to r))⊢(p\to r)$	Si $p$ llavors $q$; i si $q$ llavors $r$; per lo tant, si $p$ llavors $r$
Silogisme disyuntivo	$((p\vee q)\wedge \mathrm{\neg }p)⊢q$	Si $p$ o $q$; i no $p$; per lo tant, $q$
Dilema constructiu	$((p\to q)\wedge (r\to s)\wedge (p\vee r))⊢(q\vee s)$	Si $p$ llavors $q$; i si $r$ llavors $s$; pero $p$ o $r$; per lo tant $q$ o $s$
Dilema destructiu	$((p\to q)\wedge (r\to s)\wedge (\mathrm{\neg }q\vee \mathrm{\neg }s))⊢(\mathrm{\neg }p\vee \mathrm{\neg }r)$	Si $p$ llavors $q$; i si $r$ llavors $s$; pero no $q$ o no $s$; per lo tant no $p$ o no $r$
Dilema bidireccional	$((p\to q)\wedge (r\to s)\wedge (p\vee \mathrm{\neg }s))⊢(q\vee \mathrm{\neg }r)$	Si $p$ llavors $q$; i si $r$ llavors $s$; pero $p$ o no $s$; per lo tant $q$ o no $r$
Simplificació	$(p\wedge q)⊢p$	$p$ i $q$ són verdaders; per lo tant $p$ és verdader
Conjunció	$p,q⊢(p\wedge q)$	$p$ i $q$ són verdaders separadament; llavors són verdaders conjuntament.
Adició	$p⊢(p\vee q)$	$p$ és verdader; per lo tant la disjunció ($p$ o $q$) és verdadera
Composició	$((p\to q)\wedge (p\to r))⊢(p\to (q\wedge r))$	Si $p$ llavors $q$; i si $p$ llavors $r$; per lo tant si $p$ és verdader llavors $q$ i $r$ són verdaders
Llei de De Morgan (1)	$\mathrm{\neg }(p\wedge q)⊢(\mathrm{\neg }p\vee \mathrm{\neg }q)$	La negació de ($p$ i $q$) és equivalent a (no $p$ o no $q$)
Llei de De Morgan (2)	$\mathrm{\neg }(p\vee q)⊢(\mathrm{\neg }p\wedge \mathrm{\neg }q)$	La negació de ($p$ o $q$) és equivalent a (no $p$ i no $q$)
Conmutación (1)	$(p\vee q)⊢(q\vee p)$	($p$ o $q$) és equivalent a ($q$ o $p$)
Conmutación (2)	$(p\wedge q)⊢(q\wedge p)$	($p$ i $q$) és equivalent a ($q$ i $p$)
Conmutación (3)	$(p\leftrightarrow q)⊢(q\leftrightarrow p)$	($p$ és equivalent a $q$) és equivalent a ($q$ és equivalent a $p$)
Associació (1)	$(p\vee (q\vee r))⊢((p\vee q)\vee r)$	$p$ o ($q$ o $r$) és equivalent a ($p$ o $q$) o $r$
Associació (2)	$(p\wedge (q\wedge r))⊢((p\wedge q)\wedge r)$	$p$ i ($q$ i $r$) és equivalent a ($p$ i $q$) i $r$
Distribució (1)	$(p\wedge (q\vee r))⊢((p\wedge q)\vee (p\wedge r))$	$p$ i ($q$ o $r$) és equivalent a ($p$ i $q$) o ($p$ i $r$)
Distribució (2)	$(p\vee (q\wedge r))⊢((p\vee q)\wedge (p\vee r))$	$p$ o ($q$ i $r$) és equivalent a ($p$ o $q$) i ($p$ o $r$)
Doble negació	$p⊢\mathrm{\neg }\mathrm{\neg }p$	$p$ és equivalent a la negació de no $p$
Transposició	$(p\to q)⊢(\mathrm{\neg }q\to \mathrm{\neg }p)$	Si $p$ llavors $q$ és equivalent a si no $q$ llavors no $p$
Implicació material	$(p\to q)⊢(\mathrm{\neg }p\vee q)$	Si $p$ llavors $q$ és equivalent a no $p$ o $q$
Equivalència material (1)	$(p\leftrightarrow q)⊢((p\to q)\wedge (q\to p))$	($p$ si i solament si $q$) és equivalent a (si $p$ és verdader llavors $q$ és verdader) i (si $q$ és verdader llavors $p$ és verdader)
Equivalència material (2)	$(p\leftrightarrow q)⊢((p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q))$	($p$ si $q$) és equivalent a qualsevol dels dos ($p$ i $q$ són verdaders) o (tant $p$ com $q$ són falsos)
Equivalència material (3)	$(p\leftrightarrow q)⊢((p\vee \mathrm{\neg }q)\wedge (\mathrm{\neg }p\vee q))$	($p$ si $q$) és equivalent a: tant ($p$ com no $q$ són verdaders) i (no $p$ o $q$ és verdader)
Exportació	$((p\wedge q)\to r)⊢(p\to (q\to r))$	des de (si $p$ i $q$ són verdaders, llavors $r$ és verdader) es pot provar que (si $q$ és verdader llavors $r$ és verdader, si $p$ és verdader)
Importació	$(p\to (q\to r))⊢((p\wedge q)\to r)$	$p$ implica que $q$ implica $r$ és equivalent a que $p$ i $q$ impliquen $r$
Tautologia (1)	$p⊢(p\vee p)$	$p$ és verdader és equivalent a $p$ és verdader o $p$ és verdader
Tautologia (2)	$p⊢(p\wedge p)$	$p$ és verdader és equivalent a $p$ és verdader i $p$ és verdader
Principi del tercer exclós	$⊢(p\vee \mathrm{\neg }p)$	$p$ o no $p$ és verdader
Principi de no contradicció	$⊢\mathrm{\neg }(p\wedge \mathrm{\neg }p)$	$p$ i no $p$ és fals

Eixemple d'una demostració

Demostrar: $A\to A$

Una possible prova d'açò (que, encara que vàlida, passa a contindre més passos dels necessaris) es pot dispondre de la següent manera:

Pas	Fòrmula	Raó
1	$A$	Premissa.
2	$A\vee A$	Des de (1) per introducció de la disjunció.
3	$(A\vee A)\wedge A$	Des de (1) i (2) per introducció de la conjunció.
4	$A$	Des de (3) per eliminació de la conjunció.
5	$A⊢A$	Resum de (1) fins a (4).
6	$⊢A\to A$	Des de (5) per introducció del condicional. QED

Interpretar $A⊢A$ com: "Assumint que $A$, inferire $A$". Llegir $⊢$ $A\to A$ com "Suponent res, inferir que $A$ implica $A$", o "És una tautologia que $A$ implica $A$", o "Sempre és cert que $A$ implica $A$".

Llenguage formal en la notació BNF

El llenguage formal de la llògica proposicional es pot generar en la gramàtica formal descrita usant la notació BNF com seguix:

$\begin{array}{ccc}\mathrm{⟨}\mathrm{B}\mathrm{i}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}& ::=& \mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{\leftrightarrow }\mathrm{⟨}\mathrm{B}\mathrm{i}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{\mid }\mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\\ \mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}& ::=& \mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\mathrm{\to }\mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{\mid }\mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\\ \mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}& ::=& \mathrm{⟨}\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{y}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\mathrm{\vee }\mathrm{⟨}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\mathrm{\mid }\mathrm{⟨}\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{y}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\\ \mathrm{⟨}\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{y}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}& ::=& \mathrm{⟨}\mathrm{L}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{\wedge }\mathrm{⟨}\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{y}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\mathrm{\mid }\mathrm{⟨}\mathrm{L}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{⟩}\\ \mathrm{⟨}\mathrm{L}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{⟩}& ::=& \mathrm{⟨}\acute{\mathrm{A}}\mathrm{t}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{⟩}\mathrm{\mid }\mathrm{\neg }\mathrm{⟨}\acute{\mathrm{A}}\mathrm{t}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{⟩}\\ \mathrm{⟨}\acute{\mathrm{A}}\mathrm{t}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{⟩}& ::=& \mathrm{\top }\mathrm{\mid }\mathrm{\perp }\mathrm{\mid }\mathrm{⟨}\mathrm{L}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{⟩}\mathrm{\mid }\mathrm{⟨}\mathrm{A}\mathrm{g}\mathrm{r}\mathrm{u}\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}\\ \mathrm{⟨}\mathrm{A}\mathrm{g}\mathrm{r}\mathrm{u}\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{i}\acute{\mathrm{o}}\mathrm{n}\mathrm{⟩}& ::=& \mathrm{(}\mathrm{⟨}\mathrm{B}\mathrm{i}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{)}\mathrm{\mid }\mathrm{[}\mathrm{⟨}\mathrm{B}\mathrm{i}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{]}\mathrm{\mid }\mathrm{\{}\mathrm{⟨}\mathrm{B}\mathrm{i}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{⟩}\mathrm{\}}\end{array}$

La gramàtica anterior definix la precedència d'operadors de la següent manera:

1. Negació ($\mathrm{\neg }$)
2. Conjunció ($\wedge$)
3. Disjunció ($\vee$)
4. Condicional material ($\to$)
5. Bicondicional ($\leftrightarrow$)

Semàntica

Una interpretació per a un sistema de llògica proposicional és una assignació de valors de veres per a cada variable proposicional, sumada a l'assignació usual de significats per als operadors llògics. A cada variable proposicional se li assigna un de dos possibles valors de veres: o V (verdader) o F (fals). Açò vol dir que si hi ha n variables proposicionals en el sistema, el número d'interpretacions distintes és de 2ⁿ.

Partint d'açò és possible definir una cantitat de nocions semàntiques. Si A i B són fòrmules qualsevol d'un llenguage L, $\Gamma$ és un conjunt de fòrmules de L, i M és una interpretació de L, llavors:

• A és verdadera baix l'interpretació M si i solament si M assigna el valor de veres V a A.
• A és falsa baix l'interpretació M si i solament si M assigna el valor de veres F a A.
• A és una tautologia (o una veritat llògica) si i solament si para tota interpretació M, M assigna el valor de veres V a A.
• A és una contradicció si i solament si para tota interpretació M, M assigna el valor de veres F a A.
• A és satisfacible (o consistent) si i solament si existix a lo manco una interpretació M que assigne el valor de veres V a A.
• $\Gamma$ és consistent si i solament si existix a lo manco una interpretació que faça verdaderes a totes les fòrmules en $\Gamma$.
• A és una conseqüència semàntica d'un conjunt de fòrmules $\Gamma$ si i solament si no existix interpretació en la que totes les fòrmules que pertanyen a $\Gamma$ siguen verdaderes i A siga falsa. Quan A és una conseqüència semàntica de $\Gamma$ en un llenguage L, s'escriu: $\Gamma {\models }_{L}A$.
• A és una veritat llògica si i solament si A és una conseqüència semàntica del conjunt buit. Quan A és una veritat llògica d'un llenguage L, s'escriu: ${\models }_{L}A$.

Taules de veres

Artícul principal → Taules de veres.

La taula de veres d'una fòrmula és una taula en la que es presenten totes les possibles interpretacions de les variables proposicionals que constituïx la fòrmula i el valor de veres de la fòrmula completa per a cada interpretació. Per eixemple, la taula de veres per a la fòrmula $\mathrm{\neg }(p\vee q)\to (p\to r)$ és:

$\begin{array}{ccccccc}p& q& r& (p\vee q)& \mathrm{\neg }(p\vee q)& (p\to r)& \mathrm{\neg }(p\vee q)\to (p\to r)\\ V& V& V& V& F& V& V\\ V& V& F& V& F& F& V\\ V& F& V& V& F& V& V\\ V& F& F& V& F& F& V\\ F& V& V& V& F& V& V\\ F& V& F& V& F& V& V\\ F& F& V& F& V& V& V\\ F& F& F& F& V& V& V\end{array}$

Com es veu, esta fòrmula té 2ⁿ interpretacions possibles —una per cada llínea de la taula— a on n és el número de variables proposicionals (en este cas 3, és dir p, q, r) i resulta ser una tautologia, és dir que baix totes les interpretacions possibles de les variables proposicionals, el valor de veres de la fòrmula completa termina sent V.

Formes normals

A sovint és necessari transformar una fòrmula en una atra, sobretot transformar una fòrmula a la seua forma normal. Açò es conseguix transformant la fòrmula en una atra equivalent i repetint el procés fins a conseguir una fòrmula que solament use els conectivos bàsics ($\wedge ,\vee ,\mathrm{\neg }$). Per a conseguir açò s'utilisen les equivalència llògiques:

$(p\to q)\leftrightarrow (\mathrm{\neg }p\vee q)$

$(p\leftrightarrow q)\leftrightarrow [(\mathrm{\neg }p\vee q)\wedge (\mathrm{\neg }q\vee p)]$

Per eixemple, considere's la següent fòrmula:

$(p\to q)\wedge (\mathrm{\neg }q\leftrightarrow p)$

La mateixa pot desenrollar-se aixina:

$(\mathrm{\neg }p\vee q)\wedge (q\vee p)\wedge (\mathrm{\neg }p\vee \mathrm{\neg }q)$

Es diu que una fòrmula està en forma normal disyuntiva (FND) si i solament si té la següent forma:

$A_1\vee A_2\vee \mathrm{...}\vee A_n$

a on cada A és una conjunció de fòrmules. Per eixemple, la següent fòrmula està en forma normal disyuntiva:

$p\vee (q\wedge s)\vee (\mathrm{\neg }q\wedge p)$

Es diu que una fòrmula està en forma normal conjuntiva (FNC) si i solament si té la següent forma:

$A_1\wedge A_2\wedge \mathrm{...}\wedge A_n$

a on cada A és una disjunció de fòrmules. Per eixemple, la següent fòrmula està en forma normal conjuntiva:

$p\wedge (q\vee s)\wedge (\mathrm{\neg }q\vee p)$

Per les lleis de De Morgan, és possible passar d'una forma normal disyuntiva a una forma normal conjuntiva i viceversa:

$\mathrm{\neg }(A\vee B)\leftrightarrow (\mathrm{\neg }A\wedge \mathrm{\neg }B)$

$\mathrm{\neg }(A\wedge B)\leftrightarrow (\mathrm{\neg }A\vee \mathrm{\neg }B)$

Les FNC i FND són mútuament duals. La demostració fa us de les lleis de De Morgan i de la propietat distributiva de la conjunció i la disjunció. Es deu complir que:

$\mathrm{\neg }[(A_1\wedge B_1)\vee (A_2\wedge B_2)\vee \mathrm{...}\vee (A_n\wedge B_n)]\leftrightarrow [(\mathrm{\neg }{A}_1\vee \mathrm{\neg }{B}_1)\wedge (\mathrm{\neg }{A}_2\vee \mathrm{\neg }{B}_2)\wedge \mathrm{...}\wedge (\mathrm{\neg }{A}_n\vee \mathrm{\neg }{B}_n)]$

I viceversa:

$\mathrm{\neg }[(A_1\vee B_1)\wedge (A_2\vee B_2)\wedge \mathrm{...}\wedge (A_n\vee B_n)]\leftrightarrow [(\mathrm{\neg }{A}_1\wedge \mathrm{\neg }{B}_1)\vee (\mathrm{\neg }{A}_2\wedge \mathrm{\neg }{B}_2)\vee \mathrm{...}\vee (\mathrm{\neg }{A}_n\wedge \mathrm{\neg }{B}_n)]$

Història

Artícul principal → Història de la llògica.

La llògica és coneguda com una de les ciències més antigues, tant és aixina que se li atribuïx a Aristóteles la paternitat d'esta disciplina. Partint de que correspon a Aristóteles haver segut el primer en tractar en tot detalle la llògica, se li considera el seu fundador. En un principi es va cridar Analítica, en virtut del títul de les obres en que va tractar els problemes llògics. Més tart els escrits d'Aristóteles relatius a estos events varen ser recopilats pels seus discípuls en el títul de Órganon, per considerar que la llògica era un instrument per al coneiximent de la veritat.

Aristóteles es va plantejar cóm és possible provar i demostrar que un coneiximent és verdader, és dir, que té una validea universal. Aristóteles troba el fonament de la demostració en la deducció, procediment que consistix en derivar un fet particular d'alguna cosa universal. La forma en que s'afecta eixa derivació és el silogisme, per la raó del qual la silogística aplega a ser el centre de la llògica aristotèlica.

Encara que la llògica proposicional (que és intercanviable en el càlcul proposicional) havia segut insinuada pels filòsofs anteriors, va ser desenrollada com un sistema formal pel filòsof estoico Crisipo en el III i ampliada pels seus successors de la mateixa escola. La llògica proposicional es va centrar en proposicions. Este alvanç va ser diferent de la llògica silogística tradicional que es va centrar en els térmens. No obstant, més vesprada en l'antiguetat, la llògica proposicional desenrollada pels estoicos no es comprenia. En conseqüència d'això, el sistema va ser reinventat essencialment per Pedro Abelardo en el XII.

La llògica proposicional va ser finalment refinada usant la llògica simbòlica, es va acreditar ser el fundador de la llògica simbòlica el matemàtic Gottfried Leibniz XVII/XVIII, pel seu treball ratiocinator del càlcul. Encara que el seu treball era uns dels primers, era desconegut per a la comunitat llògica més gran. En conseqüència, molts dels alvanços conseguits per Leibniz varen ser recreats per llògics com George Boole i Augustus De Morgan completament independents a Leibniz.

Aixina com la llògica proposicional pot considerar-se un alvanç de la llògica silogísta anterior, la llògica de predicats de Gottlob Frege era un alvanç de la llògica proposicional anterior. Un autor descriu esta llògica com la combinació de les traces distintives de la llògica silogística i la llògica proposicional. Per lo tant, la llògica predicativa va marcar el començ d'una nova era en l'història de la llògica; no obstant, els alvanços en la llògica proposicional es varen fer encara despuix de Frege, incloent Deducció Natural, Arbres de la Veritat i Taules de veres. La deducció natural va ser inventada per Gerhard Gentzen i Jan Lukasiewicz. Els arbres de la veritat varen ser inventats per Evert Willem Beth. L'invenció de les taules de la veritat, no obstant, és d'atribució controvertida.

Dins de les obres de Frege i Bertrand Russell, hi ha idees que influïxen en l'invenció de les taules de la veritat. L'estructura tabular real s'acredita generalment a Ludwig Wittgenstein o a Emil Post ( o abdós independentment). Adeám de Frege i Russell, atres acreditats en idees anteriors a les taules de la veritat inclouen a Philo, Boole, Charles Sanders Peirce. Atres acreditats de l'estructura tabular inclouen Lukasiewicz, Alfred North Whitehead, Guillermo Stanley Jevons, John Venn, i Clarence Irving Lewis. En última instància, alguns han aplegat a la conclusió, com John Shosky, de que " està llunt d'estar clar que a qualsevol persona se li deu donar el títul de 'inventor' de les taules de la veritat".

Llògiques

Llògica Llògica formal Llògica clàssica Llògica d'orde zero o Llògica proposicional Llògica d'orde superior Llògica de primer orde o llògica de predicats Llògica de segon orde ... Llògica no clàssica Llògica modal Llògica deóntica Llògica doxástica Llògica epistémica Llògica temporal Llògica quàntica Llògica difusa Llògica intuicionista Llògica rellevant Llògica no monotónica ... Llògica informal

Vore també

• Àlgebra de Boole
• Càlcul llògic
• Càlcul proposicional de Frege
• Gràfics existencials
• Llògica matemàtica
• Llògica de primer orde
• Llògica modal
• Taula de veres
• Teoria de grafos
• Silogisme
• Valor de veres
• Raonament diagramático

Bibliografia

• Enderton, H. B. (1972). A Mathematical Introduction to Logic, Academic Press.
• (1981) Llògica per a matemàtics, Paraningo.
• Mendelson, E. (1997). Introduction to Mathematical Logic, 4ª edició, Chapman and May.
• (1991) Lliçons de llògica matemàtica, P.P.U..
• Badesa, C.; Jané, {{{nom2}}}; Jansana, {{{nom3}}} (1998). Elements de llògica formal, Ariel.
• (1978) Una introducció algebraica a la llògica matemàtica, Eunibar.
• Bridge, J. (1977). Beginning Model Theory, Oxford University Pres.
• (1990) Llògica matemàtica, Mir.

• Hofstadter, D. (1987). Gödel, Escher, Bach: un Etern i Grácil Bucle, Tusquets Editors.
• (1989) Àlgebra de Boole i llògica, Publicacions U.B..
• Monk, J. D. (1976). Mathematical Logic, Springer-Verlag.
• Nidditch, P. H. (1978). El desenroll de la llògica matemàtica, Càtedra.
• Van Dalen, D. (1983). Logic and Structure, 2ª edició, Universitext, Springer-Verlag.

Enllaços externs

• Plantilla:Wikiversidad
• Introducció a la llògica proposicional