Lóxica proposicional

La lóxica proposicional o lóxica d'orde cero ye un sistema formal que los sos elementos más simples representen proposiciones, y que les sos constantes lóxiques, llamaes conectivas lóxiques, representen operaciones sobre proposiciones, capaces de formar otres proposiciones de mayor complexidá.^[1]

La lóxica proposicional trata con sistemes lóxicos qu'escarecen de cuantificadores, o variables interpretables como entidaes. En lóxica proposicional magar nun hai signos pa variables de tipo entidá, sí esisten signos pa variables proposicionales (esto ye, que pueden ser interpretaes como proposiciones con un valor de verdá definíu), d'ende'l nome proposicional. La lóxica proposicional inclúi amás de variables interpretables como proposiciones simples signos pa conectivas lóxiques, polo que dientro d'esti tipu de lóxica puede analizase la inferencia lóxica de proposiciones a partir de proposiciones, pero ensin tener en cuenta la estructura interna de les proposiciones más simples.^[2]

Introducción

Considérese'l siguiente argumentu:

Mañana ye miércoles o mañana ye xueves.
Mañana non ye xueves.
Polo tanto, mañana ye miércoles.

Ye un argumentu válidu. Quier dicir que ye imposible que les premises (1) y (2) sían verdaderes y la conclusión (3) falsa.

Sicasí, a pesar de que l'argumentu sía válidu, esto nun quier dicir que la conclusión sía verdadera. N'otres pallabres, si les premises son falses, entós la conclusión tamién podría selo. Pero si les premises son verdaderes, entós la conclusión tamién la ye. La validez del argumentu nun depende del significáu de les espresiones «mañana ye miércoles» nin «mañana ye xueves», sinón de la estructura mesma del argumentu. Estes premises podríen camudase por otres y l'argumentu permanecería válidu. Por casu:

Güei ta soleyeru o ta borrinosu.
Güei nun ta borrinosu.
Polo tanto, güei ta soleyeru.

La validez de los dos argumentos anteriores depende del significáu de les espresiones «o» y «non». Si dalguna d'estes espresiones camudar por otra, entós los argumentos podríen dexar de ser válidos. Por casu, considérese'l siguiente argumentu inválidu:

Nin ta soleyeru nin ta borrinosu.
Nun ta borrinosu.
Polo tanto, ta soleyeru.

Estes espresiones como «o» y «non», de les que depende la validez de los argumentos, llámense conectivas lóxiques. Tocantes a espresiones como «ta borrinosu» y «mañana ye xueves», lo único qu'importa d'elles ye que tengan un valor de verdá. Ye por esto que-y les reemplaza por simples lletres, que la so intención ye simbolizar una espresión con valor de verdá cualesquier. A estes lletres se les llapada variables proposicionales, y polo xeneral tómense del alfabetu llatín, empezando pola lletra p (de «proposición») depués q, r, s, etc. Ye asina que los dos primeros argumentos d'esta seición podríen reescribise asina:

p o q
Non q
Polo tanto, p

Y el tercer argumentu, a pesar de nun ser válidu, puede reescribise asina:

Nin p nin q
Non q
Polo tanto, p

Conectivas lóxiques

Plantía:Conectivas lóxiques

De siguío hai una tabla qu'esplega toles conectivas lóxiques qu'ocupen a la lóxica proposicional, incluyendo exemplos del so usu nel llinguaxe natural y los símbolos que s'utilicen pa representales en llinguaxe formal.

Conectiva	Espresión n'el llinguaxe natural	Exemplu !Símbolu en esti artículu !Símbolos alternativos
Negación	non	Nun ta lloviendo.	$\neg \,$	$\sim \,$
Conxunción	align="left" \| Ta lloviendo y ta borrinosu.	$\land$	$\And \,$ $.$
Dixunción	align="left" \| Ta lloviendo o ta soleyeru.	$\lor$
Condicional material	align="left" \| Si ta soleyeru, entós ye de día.	$\to \,$	$\supset$
Bicondicional	align="left" \| Ta borrinosu si y namái si hai nubes visibles.	$\leftrightarrow$	$\equiv \,$
Dixunción opuesta	nin... nin	Nin ta soleyeru nin ta borrinosu.	$\downarrow \,$
Dixunción esclusiva	o bien... o bien	O bien ta soleyeru, o bien ta borrinosu.	$\nleftrightarrow$	$\oplus ,\not \equiv ,W$

Na lóxica proposicional, les conectivas lóxiques trátense como funciones de verdá. Esto ye, como funciones que tomen conxuntos de valores de verdá y devuelven valores de verdá. Por casu, la conectiva lóxica «nun ye una función que si toma'l valor de verdá V, devuelve F, y si toma'l valor de verdá F, devuelve V. Poro, si aplícase la función «non» a una lletra que represente una proposición falsa, la resultancia va ser daqué verdaderu. Si ye falsu que «ta lloviendo», entós va ser verdaderu que «nun ta lloviendo».

El significáu de les conectivas lóxiques nun ye namás que'l so comportamientu como funciones de verdá. Cada conectiva lóxica estremar de les otres polos valor de verdá que devuelve frente a les distintes combinaciones de valores de verdá que puede recibir. Esto quier dicir que'l significáu de cada conectiva lóxica puede ilustrase por aciu una tabla qu'esplegue los valores de verdá que la función devuelve frente a toles combinaciones posibles de valores de verdá que puede recibir.

Negación	Conxunción	Dixunción	Condicional	Bicondicional	Dixunción esclusiva
${\begin{array}{c\|\|c}\phi &\neg \phi \\\hline F&V\\V&F\\\end{array}}$	${\begin{array}{c\|c\|\|c}\phi &\psi &\phi \land \psi \\\hline V&V&V\\F&V&F\\V&F&F\\F&F&F\\\end{array}}$	${\begin{array}{c\|c\|\|c}\phi &\psi &\phi \lor \psi \\\hline V&V&V\\F&V&V\\V&F&V\\F&F&F\\\end{array}}$	${\begin{array}{c\|c\|\|c}\phi &\psi &\phi \to \psi \\\hline V&V&V\\F&V&V\\V&F&F\\F&F&V\\\end{array}}$	${\begin{array}{c\|c\|\|c}\phi &\psi &\phi \leftrightarrow \psi \\\hline V&V&V\\F&V&F\\V&F&F\\F&F&V\\\end{array}}$	${\begin{array}{c\|c\|\|c}\phi &\psi &\phi \nleftrightarrow \psi \\\hline V&V&F\\F&V&V\\V&F&V\\F&F&F\\\end{array}}$

Lleis notables en lóxica

Ente les regles de la lóxica proposicional clásica dalgunes de la más notables son llistaes de siguío:

Otres lleis como'l principiu del terceru escluyíu son almitibles en lóxica clásica, pero en lóxica intuicionista y con fines a les sos aplicaciones matemátiques nun esiste un equivalente del terceru escluyíu, por casu.

Llendes de la lóxica proposicional

La maquinaria de la lóxica proposicional dexa formalizar y teorizar sobre la validez d'una gran cantidá d'argumentos. Sicasí, tamién esisten argumentos que son intuitivamente válidos, pero que la so validez non poder probar pola lóxica proposicional. Por casu, considérese'l siguiente argumentu:

Tolos homes son mortales.
Sócrates ye un home.
Poro, Sócrates ye mortal.

Como esti argumentu nun contién nenguna de les conectivas «non», «y», «o», etc., según la lóxica proposicional, la so formalización va ser la siguiente:

p
q
Poro, r

Pero esta ye una forma d'argumentu inválida, y eso contradiz la nuesa intuición de que l'argumentu ye válidu. Pa teorizar sobre la validez d'esti tipu d'argumentos, precísase investigar la estructura interna de les variables proposicionales. D'esto ocupa la lóxica de primer orde. Otros sistemes formales dexen teorizar sobre otros tipos d'argumentos. Por casu la lóxica de segundu orde, la lóxica modal y la lóxica temporal.

Dos sistemes formales de lóxica proposicional

De siguío preséntense dos sistemes formales estándar pa la lóxica proposicional. El primeru ye un sistema axomáticu simple, y el segundu ye un sistema ensin axomes, de deducción natural.

Sistema axomáticu

Alfabetu

L'alfabetu d'un sistema formal ye'l conxuntu de símbolos que pertenecen al llinguaxe del sistema. Si L ye'l nome d'esti sistema axomáticu de lóxica proposicional, entós l'alfabetu de L consiste en:

Una cantidá finita pero arbitrariamente grande de variables proposicionales. Polo xeneral tomar del alfabetu llatín, empezando pola lletra p, depués q, r, etc., y utilizando subíndices cuando ye necesariu o conveniente. Les variables proposicionales representen proposiciones como "ta lloviendo" o "los metales espandir col calor".
Un conxuntu d'operadores lóxicos: $\neg ,\land ,\lor ,\to ,\leftrightarrow$
Dos signos de puntuación: los paréntesis esquierdu y derechu. La so única función ye desambiguar ciertes espresiones ambigues, n'esactamente'l mesmu sentíu en que desambiguan la espresión 2 + 2 ÷ 2, que puede significar tantu (2 + 2) ÷ 2, como 2 + (2 ÷ 2).

Gramática

Una vegada definíu l'alfabetu, el siguiente pasu ye determinar qué combinaciones de símbolos pertenecen al llinguaxe del sistema. Esto llógrase por aciu una gramática formal. La mesma consiste nun conxuntu de regles que definen recursivamente les cadenes de calteres que pertenecen al llinguaxe. A les cadenes de calteres construyíes según estes regles se les llapada fórmules bien formaes. Les regles del sistema L son:

Les variables proposicionales del alfabetu de L son fórmules bien formaes.
Si $\phi \,$ ye una fórmula bien formada de L, entós $\neg \phi \,$ tamién lo ye.
Si $\phi \,$ y $\psi \,$ son fórmules bien formaes de L, entós $(\phi \land \psi )$ , $(\phi \lor \psi )$ , $(\phi \to \psi )\,$ y $(\phi \leftrightarrow \psi )$ tamién lo son.
Namái les espresiones que pueden ser xeneraes por aciu les clauses 1 a 3 nun númberu finito de pasos son fórmules bien formaes de L.

Según estes regles, les siguientes cadenes de calteres son exemplos de fórmules bien formaes:

p\,

\neg \neg \neg q\,

(p\land q)

\neg (p\land q)

(p\leftrightarrow \neg p)

((p\to q)\land p)

(\neg (p\land (q\lor r))\lor s)

Y los siguientes son ejempos de fórmules mal formaes^{[ensin referencies]}:

Fórmula !align="left"\|Error !align="left"\|Correición
$(p)\,$	Sobren paréntesis	$p\,$
$\neg (p)\,$	Sobren paréntesis	$\neg p\,$
$(\neg p)\,$	Sobren paréntesis	$\neg p\,$
$p\to q\,$	Falten paréntesis	$(p\to q)\,$
$(p\land q\to r)$	Falten paréntesis	$((p\land q)\to r)\,$

Per otra parte, yá que la única función de los paréntesis ye desambiguar les fórmules, polo xeneral acostúmase omitir los paréntesis esternos de cada fórmula, una y bones estos nun cumplen nenguna función. Asina por casu, les siguientes fórmules xeneralmente considérense bien formaes:

p\land q

\neg p\to q\,

(p\land q)\lor \neg q

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

Otra convención avera del usu de los paréntesis ye que les conxunciones y les dixunciones tienen «menor xerarquía» que los condicionales materiales y los bicondicionales. Esto significa que dada una fórmula ensin paréntesis, les conxunciones y les dixunciones tienen d'arrexuntase antes que los condicionales materiales y los bicondicionales. Por casu:

Fórmula !align="left"\|Llectura correuta !align="left"\|Llectura incorreuta
$p\land q\to r\,$	$(p\land q)\to r\,$	$p\land (q\to r)\,$
$\neg p\leftrightarrow q\lor r\,$	$\neg p\leftrightarrow (q\lor r)\,$	$(\neg p\leftrightarrow q)\lor r\,$
$p\land q\leftrightarrow r\lor s\,$	$(p\land q)\leftrightarrow (r\lor s)\,$	$(p\land (q\leftrightarrow r))\lor s\,$

Estes convenciones son análogues a les qu'esisten nel álxebra elemental, onde la multiplicación y la división siempres tienen de resolvese primero que la suma y restar. Asina por casu, la ecuación 2 + 2 × 2 podría interpretase como (2 + 2) × 2 o como 2 + (2 × 2). Nel primer casu la resultancia sería 8, y nel segundu casu sería 6. Pero como la multiplicación siempres tien de resolvese primero que la suma, la resultancia correuta nesti casu ye 6, non 8.

Axomes

Los axomes d'un sistema formal son un conxuntu de fórmules bien formaes que se tomen como puntu de partida pa demostraciones ulteriores. Un conxuntu d'axioma estándar ye'l qu'afayó Jan Łukasiewicz:

$(\phi \to (\psi \to \phi ))\,$
$((\phi \to (\psi \to \chi ))\to ((\phi \to \psi )\to (\phi \to \chi )))\,$
$((\neg \phi \to \neg \psi )\to (\psi \to \phi ))\,$

Regles de inferencia

Plantía:Regles de tresformamientu

Una regla de inferencia ye una función que va de conxuntos de fórmules a fórmules. Al conxuntu de fórmules que la función toma como argumentu llamar premises, ente que a la fórmula que devuelve como valor se la llapada conclusión. Polo xeneral búscase que les regles de inferencia tresmitan la verdá de les premises a la conclusión. Esto ye, que sía imposible que les premises sían verdaderes y la conclusión falsa. Nel casu de L, la única regla de inferencia ye'l modus ponens, que diz:

(\phi \to \psi ),\phi \vdash \psi

Recordando que $\phi \,$ y $\psi \,$ nun son fórmules, sinón metavariables que pueden ser reemplazaes por cualesquier fórmula bien formada.

Deducción natural

Dexar ${\mathcal {L}}_{2}={\mathcal {L}}(\mathrm {A} ,\Omega ,\mathrm {Z} ,\mathrm {I} )$ , onde $\mathrm {A}$ , $\Omega$ , $\mathrm {Z}$ , $\mathrm {I}$ , defínese como:

Alpha conxuntu de $\mathrm {A}$ ye un conxuntos finito de símbolos que ye lo suficientemente grande como pa satisfaer les necesidaes d'un discutiniu dau, por casu:
$\mathrm {A} =\{p,q,r,s,t,o\}.$
Omega conxuntu de $\Omega =\Omega _{1}\cup \Omega _{2}$ como partición de :
$\Omega _{1}=\{\lnot \},$

$\Omega _{2}=\{\land ,\lor ,\to ,\leftrightarrow \}.$

Nel siguiente exemplu ye d'un cálculu proposicional, les regles presentaes de tresformamientu tienen que ser interpretaes como regles de inferencia d'un sistema de deducción natural. El sistema particular equí presentáu nun tien puntos iniciales, lo que significa que la so interpretación pa les aplicaciones lóxiques deriva d'un teorema de conxuntos d'axomes vacíos.

*El conxuntu de puntos iniciales ta vacíu, este ye $\mathrm {I} =\varnothing$ .

*El conxuntu de regles de tresformamientu $\mathrm {Z}$ descríbese como :

El nuesu cálculu proposicional tien diéz regles de inferencia. Estes regles déxennos derivar otres fórmules verdaderes dau un conxuntu de fórmules que se supón que son verdaderes. Les primeres nueve a cencielles declaren que podemos inferir ciertes fórmules bién formaes d'otres fórmules bien formaes; y l'última regla utiliza'l razonamientu hipotéticu nel sentíu de que la premisa de la regla asuma temporalmente una hipótesis( non probada) pa formar parte del conxuntu de fórmules deducíes pa ver si podemos inferir dalguna otra fórmula. Yá que les primeres nueve regles nun son hipotétiques , usualmente describiríense como regles non hipotétiques, y l'última regla como una regla hipotética.

Al describir les regles de tranformación, podemos introducir un símbolu de metallinguaxe $\vdash$ . Ye básicamente una taquigrafía conveniente pa dicir " inferir que ". El formatu ye $\Gamma \vdash \psi$ , nel cual $Γ$ ye un conxuntu de fórmules llamaes premises, y $ψ$ ye una fórmula pa topar la conclusión. La regla de tranformacíon $\Gamma \vdash \psi$ significa que si toa proposición en $Γ$ ye un teorema ( o tien el mesmu valor de verdá que los axomes ), entós $ψ$ ye tamién un teorema. Tenga en cuenta que teniendo encuenta la siguiente regla la introducción de conxunción $Γ$ tien más d'una fórmula, siempres podemos amenorgala con seguridá nuna fórmula usando una conxunción. Asina que pa embrivir, a partir d'esi momentu podemos representar $Γ$ como una fórmula en llugar d'un conxuntu. Otra omisión por conveniencia ye cuando $Γ$ ye un conxuntu vacíu, y nesi casu $Γ$ puede nun apaecer.

Un sistema de lóxica proposicional tamién puede construyise a partir d'un conxuntu vacíu d'axomes. Pa ello especifiquen una serie de regles d'inferencia qu'intenten prindar la manera en que naturalmente razonamos alrodiu de les conectivas lóxiques.

Introducción de la negación: De $(p\to q)$ y $(p\to \neg q)$ , infierse $\neg p$ .; Esto ye, $\{(p\to q),(p\to \neg q)\}\vdash \neg p$ .
Eliminación de la negación: De $\neg p$ , infierse $(p\to r)$ .; Esto ye, $\{\neg p\}\vdash (p\to r)$ .
Eliminación de la doble negación: De $\neg \neg p$ , infierse $p$ .; Esto ye, $\neg \neg p\vdash p$ .
Introducción de la conxunción: De $p$ y $q$ , infierse $(p\land q)$ .; Esto ye, $\{p,q\}\vdash (p\land q)$ .
Eliminación de la conxunción: De $(p\land q)$ , infierse $p$ .; De $(p\land q)$ , infierse $q$ .; Esto ye, $(p\land q)\vdash p$ y $(p\land q)\vdash q$ .
Introducción de la dixunción: De $p$ , infierse $(p\lor q)$ .; Esto ye, $p\vdash (p\lor q)$ y $q\vdash (p\lor q)$ .
Eliminación de la dixunción: De $(p\lor q)$ y $(p\to r)$ y $(q\to r)$ , infierse $r$ .; Esto ye, $\{p\lor q,p\to r,q\to r\}\vdash r$ .
Introducción del bicondicional: De $(p\to q)$ y $(q\to p)$ , infierse $(p\leftrightarrow q)$ .; Esto ye, $\{p\to q,q\to p\}\vdash (p\leftrightarrow q)$ .
Eliminación del bicondicional: De $(p\leftrightarrow q)$ , infierse $(p\to q)$ .; De $(p\leftrightarrow q)$ , infierse $(q\to p)$ .; Esto ye, $(p\leftrightarrow q)\vdash (p\to q)$ y $(p\leftrightarrow q)\vdash (q\to p)$ .
Modus ponens (eliminación del condicional): De $p$ y $(p\to q)$ , infierse $q$ .; Esto ye, $\{p,p\to q\}\vdash q$ .
Prueba condicional (introducción del condicional): De [aceptando que $p$ dexa una prueba de $q$ ], infierse $(p\to q)$ .; Esto ye, $(p\vdash q)\vdash (p\to q)$ .

Formes d'argumentos básiques y derivaes

Nome	Consecuente	Descripción
Modus ponens	$((p\to q)\land p)\vdash q$	Si $p$ entós $q$ ; $p$ ; polo tanto $q$
Modus tollens	$((p\to q)\land \neg q)\vdash \neg p$	Si $p$ entós $q$ ; non $q$ ; polo tanto non $p$
Siloxismu hipotéticu	$((p\to q)\land (q\to r))\vdash (p\to r)$	Si $p$ entós $q$ ; si $q$ entós $r$ ; poro, si $p$ entós $r$
Siloxismu disyuntivu	$((p\lor q)\land \neg p)\vdash q$	Si $p$ o $q$ , Y; non $p$ ; poro, $q$
Dilema constructivu	$((p\to q)\land (r\to s)\land (p\lor r))\vdash (q\lor s)$	Si $p$ entós $q$ ; y si $r$ entós $s$ ; pero $p$ o $r$ ; polo tanto $q$ o $s$
Dilema destructivu	$((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\vdash (\neg p\lor \neg r)$	Si $p$ entós $q$ ; y si $r$ entós $s$ ; pero non $q$ o non $s$ ; polo tanto non $p$ o non $r$
Dilema bidireccional	$((p\to q)\land (r\to s)\land (p\lor \neg s))\vdash (q\lor \neg r)$	Si $p$ entós $q$ ; y si $r$ entós $s$ ; pero $p$ o non $s$ ; polo tanto $q$ o non $r$
Simplificación	$(p\land q)\vdash p$	$p$ y $q$ son verdaderos; polo tanto $p$ ye verdaderu
Conxunción	$p,q\vdash (p\land q)$	$p$ y $q$ son verdaderos xebradamente; entós son verdaderos conxuntamente.
Adición	$p\vdash (p\lor q)$	$p$ ye verdaderu; polo tanto la dixunción ( $p$ o $q$ ) ye verdadera
Composición	$((p\to q)\land (p\to r))\vdash (p\to (q\land r))$	Si $p$ entós $q$ ; y si $p$ entós $r$ ; polo tanto si $p$ ye verdaderu entós $q$ y $r$ son verdaderos
Llei de De Morgan (1)	$\neg (p\land q)\vdash (\neg p\lor \neg q)$	La negación de ( $p$ y $q$ ) ye equivalente a (non $p$ o non $q$ )
Llei de De Morgan (2)	$\neg (p\lor q)\vdash (\neg p\land \neg q)$	La negación de ( $p$ o $q$ ) ye equivalente a (non $p$ y non $q$ )
Conmutación (1)	$(p\lor q)\vdash (q\lor p)$	( $p$ o $q$ ) ye equivalente a ( $q$ o $p$ )
Conmutación (2)	$(p\land q)\vdash (q\land p)$	( $p$ y $q$ ) ye equivalente a ( $q$ y $p$ )
Conmutación (3)	$(p\leftrightarrow q)\vdash (q\leftrightarrow p)$	( $p$ ye equivalente a $q$ ) ye equivalente a ( $q$ ye equivalente a $p$ )
Asociación (1)	$(p\lor (q\lor r))\vdash ((p\lor q)\lor r)$	$p$ o ( $q$ o $r$ ) ye equivalente a ( $p$ o $q$ ) o $r$
Asociación (2)	$(p\land (q\land r))\vdash ((p\land q)\land r)$	$p$ y ( $q$ y $r$ ) ye equivalente a ( $p$ y $q$ ) y $r$
Distribución (1)	$(p\land (q\lor r))\vdash ((p\land q)\lor (p\land r))$	$p$ y ( $q$ o $r$ ) ye equivalente a ( $p$ y $q$ ) o ( $p$ y $r$ )
Distribución (2)	$(p\lor (q\land r))\vdash ((p\lor q)\land (p\lor r))$	$p$ o ( $q$ y $r$ ) ye equivalente a ( $p$ o $q$ ) y ( $p$ o $r$ )
Doble negación	$p\vdash \neg \neg p$	$p$ ye equivalente a la negación de non $p$
Transposición	$(p\to q)\vdash (\neg q\to \neg p)$	Si $p$ entós $q$ ye equivalente a si non $q$ entós non $p$
Implicación material	$(p\to q)\vdash (\neg p\lor q)$	Si $p$ entós $q$ ye equivalente a non $p$ o $q$
Equivalencia material (1)	$(p\leftrightarrow q)\vdash ((p\to q)\land (q\to p))$	( $p$ si y solu si $q$ ) ye equivalente a (si $p$ ye verdaderu entós $q$ ye verdaderu) y (si $q$ ye verdaderu entós $p$ ye verdaderu)
Equivalencia material (2)	$(p\leftrightarrow q)\vdash ((p\land q)\lor (\neg p\land \neg q))$	( $p$ si $q$ ) ye equivalente a cualesquier de los dos ( $p$ y $q$ son verdaderos) o (tantu $p$ como $q$ son falsos)
Equivalencia material (3)	$(p\leftrightarrow q)\vdash ((p\lor \neg q)\land (\neg p\lor q))$	( $p$ si $q$ ) ye equivalente a: tantu ( $p$ como non $q$ son verdaderos) y (non $p$ o $q$ ye verdaderu)
Esportación^[3]	$((p\land q)\to r)\vdash (p\to (q\to r))$	dende (si $p$ y $q$ son verdaderos, entós $r$ ye verdaderu) puede probase que (si $q$ ye verdaderu entós $r$ ye verdaderu, si $p$ ye verdaderu)
Importación	$(p\to (q\to r))\vdash ((p\land q)\to r)$	$p$ implica que $q$ implica $r$ ye equivalente a que $p$ y $q$ impliquen $r$
Tautoloxía (1)	$p\vdash (p\lor p)$	$p$ ye verdaderu ye equivalente a $p$ ye verdaderu o $p$ ye verdaderu
Tautoloxía (2)	$p\vdash (p\land p)$	$p$ ye verdaderu ye equivalente a $p$ ye verdaderu y $p$ ye verdaderu
Principiu del terceru escluyíu	$\vdash (p\lor \neg p)$	$p$ o non $p$ ye verdaderu
Principiu de non contradicción	$\vdash \neg (p\land \neg p)$	$p$ y non $p$ ye falsu

Exemplu d'una demostración

Demostrar: $A\to A\,$

Una posible prueba d'esto (que, anque válida, pasa a contener más pasos de los necesarios) puede disponese de la siguiente manera:

Pasu	Fórmula	Razón
1	$A$	Premisa.
2	$A\lor A$	Dende (1) por introducción de la dixunción.
3	$(A\lor A)\land A$	Dende (1) y (2) por introducción de la conxunción.
4	$A$	Dende (3) por eliminación de la conxunción.
5	$A\vdash A$	Resume de (1) hasta (4).
6	$\vdash A\to A$	Dende (5) por introducción del condicional. QED

Interpretar $A\vdash A$ como: "Asumiendo que $A$ , inferire $A$ ". Lleer $\vdash$ $A\to A$ como "Suponiendo nada, inferir que $A$ implica $A$ ", o "Ye una tautoloxía que $A$ implica $A$ ", o "Siempres ye ciertu que $A$ implica $A$ ".

Llinguaxe formal na notación BNF

El llinguaxe formal de la lóxica proposicional puede xenerase cola gramática formal descrita usando la notación BNF como sigue:

{\begin{array}{rcl}{\rm {\langle Bicondicional\rangle }}&::=&{\rm {\langle Condicional\rangle \leftrightarrow \langle Bicondicional\rangle \mid \langle Condicional\rangle }}\\{\rm {\langle Condicional\rangle }}&::=&{\rm {\langle Conjunci{\acute {o}}n\rangle \rightarrow \langle Condicional\rangle \mid \langle Conjunci{\acute {o}}n\rangle }}\\{\rm {\langle Conjunci{\acute {o}}n\rangle }}&::=&{\rm {\langle Disyunci{\acute {o}}n\rangle \vee \langle Conjunci{\acute {o}}n\rangle \mid \langle Disyunci{\acute {o}}n\rangle }}\\{\rm {\langle Disyunci{\acute {o}}n\rangle }}&::=&{\rm {\langle Lliteral\rangle \wedge \langle Disyunci{\acute {o}}n\rangle \mid \langle Lliteral\rangle }}\\{\rm {\langle Lliteral\rangle }}&::=&{\rm {\langle {\acute {A}}tomu\rangle \mid \neg \langle {\acute {A}}tomu\rangle }}\\{\rm {\langle {\acute {A}}tomu\rangle }}&::=&{\rm {\top \mid \bot \mid \langle Lletra\rangle \mid \langle Agrupaci{\acute {o}}n\rangle }}\\{\rm {\langle Agrupaci{\acute {o}}n\rangle }}&::=&{\rm {(\langle Bicondicional\rangle )\mid [\langle Bicondicional\rangle ]\mid \{\langle Bicondicional\rangle \}}}\end{array}}

La gramática anterior define la precedencia d'operadores de la siguiente manera:

Negación ( $\neg \,$ )
Conxunción ( $\land \,$ )
Dixunción ( $\lor \,$ )
Condicional material ( $\to \,$ )
Bicondicional ( $\leftrightarrow$ )

Semántica

Una interpretación pa un sistema de lóxica proposicional ye una asignación de valores de verdá pa cada variable proposicional, sumada a la asignación avezada de significaos pa los operadores lóxicos. A cada variable proposicional asígnase-y unu de dos posibles valores de verdá: o V (verdaderu) o F (falsu). Esto quier dicir que si hai n variables proposicionales nel sistema, el númberu d'interpretaciones distintes ye de 2ⁿ.

Partiendo d'esto ye posible definir una cantidá de nociones semántiques. Si A y B son fórmules cualesquier d'un llinguaxe L, $\Gamma$ ye un conxuntu de fórmules de L, y M ye una interpretación de L, entós:

A ye verdadera so la interpretación M si y namái si M asigna'l valor de verdá V a A.
A ye falsa so la interpretación M si y namái si M asigna'l valor de verdá F a A.
A ye una tautoloxía (o una verdá lóxica) si y namái si pa toa interpretación M, M asigna'l valor de verdá V a A.
A ye una contradicción si y namái si pa toa interpretación M, M asigna'l valor de verdá F a A.
A ye satisfacible (o consistente) si y namái si esiste siquier una interpretación M qu'asigne'l valor de verdá V a A.
$\Gamma$ ye consistente si y namái si esiste siquier una interpretación que faiga verdaderes a toles fórmules en $\Gamma$ .
A ye una consecuencia semántica d'un conxuntu de fórmules $\Gamma$ si y namái si nun esiste interpretación na que toles fórmules que pertenecen a $\Gamma$ sían verdaderes y A sía falsa. Cuando A ye una consecuencia semántica de $\Gamma$ nun llinguaxe L, escríbese: $\Gamma \models _{L}A$ .
A ye una verdá lóxica si y namái si A ye una consecuencia semántica del conxuntu vacíu. Cuando A ye una verdá lóxica d'un llinguaxe L, escríbese: $\models _{L}A$ .

Tables de verdá

La tabla de verdá d'una fórmula ye una tabla na que se presenten toles posibles interpretaciones de les variables proposicionales que constitúi la fórmula y el valor de verdá de la fórmula completa pa cada interpretación. Por casu, la tabla de verdá pa la fórmula $\neg (p\lor q)\to (p\to r)$ ye:

{\begin{array}{c|c|c||c|c|c|c}p&q&r&(p\lor q)&\neg (p\lor q)&(p\to r)&\neg (p\lor q)\to (p\to r)\\\hline 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}}

Como se ve, esta fórmula tien 2ⁿ interpretaciones posibles —una per cada llinia de la tabla— onde n ye'l númberu de variables proposicionales (nesti casu 3, ye dicir p, q, r) y resulta ser una tautoloxía, ye dicir que so toles interpretaciones posibles de les variables proposicionales, el valor de verdá de la fórmula completa termina siendo V.

Formes normales

De cutiu ye necesariu tresformar una fórmula n'otra, sobremanera tresformar una fórmula a la so forma normal. Esto consíguese tresformando la fórmula n'otra equivalente y repitiendo el procesu hasta consiguir una fórmula que namái use los conectivos básicos ( $\land ,\lor ,\neg$ ). Pa llograr esto utilicen les equivalencies lóxiques:

(p\to q)\leftrightarrow (\neg p\lor q)

(p\leftrightarrow q)\leftrightarrow [(\neg p\lor q)\land (\neg q\lor p)]

Por casu, considérese la siguiente fórmula:

(p\to q)\land (\neg q\leftrightarrow p)

La mesma puede desenvolvese asina:

(\neg p\lor q)\land (q\lor p)\land (\neg p\lor \neg q)

Dizse qu'una fórmula ta en forma normal disyuntiva (FND) si y namái si tien la siguiente forma:

A_{1}\lor A_{2}\lor ...\lor A_{n}

onde cada A ye una conxunción de fórmules. Por casu, la siguiente fórmula ta en forma normal disyuntiva:

p\lor (q\land s)\lor (\neg q\land p)

Dizse qu'una fórmula ta en forma normal conxuntiva (FNC) si y namái si tien la siguiente forma:

A_{1}\land A_{2}\land ...\land A_{n}

onde cada A ye una dixunción de fórmules. Por casu, la siguiente fórmula ta en forma normal conxuntiva:

p\land (q\lor s)\land (\neg q\lor p)

Poles lleis de De Morgan, ye posible pasar d'una forma normal disyuntiva a una forma normal conxuntiva y viceversa:

\neg (A\lor B)\leftrightarrow (\neg A\land \neg B)

\neg (A\land B)\leftrightarrow (\neg A\lor \neg B)

Les FNC y FND son mutuamente duales. La demostración fai usu de les lleis de De Morgan y de la propiedá distributiva de la conxunción y la dixunción. Tien de cumplise que:

\neg [(A_{1}\land B_{1})\lor (A_{2}\land B_{2})\lor ...\lor (A_{n}\land B_{n})]\leftrightarrow [(\neg A_{1}\lor \neg B_{1})\land (\neg A_{2}\lor \neg B_{2})\land ...\land (\neg A_{n}\lor \neg B_{n})]

Y viceversa:

\neg [(A_{1}\lor B_{1})\land (A_{2}\lor B_{2})\land ...\land (A_{n}\lor B_{n})]\leftrightarrow [(\neg A_{1}\land \neg B_{1})\lor (\neg A_{2}\land \neg B_{2})\lor ...\lor (\neg A_{n}\land \neg B_{n})]

La lóxica proposicional y la computación

Por cuenta de que los ordenadores trabayen con información binaria, la ferramienta matemático fayadiza pal analís y diseñu del so funcionamientu ye l'Álxebra de Boole. La Álxebra de Boole foi desenvuelta primeramente pal estudiu de la lóxica. Foi a partir de 1938, fecha en que Claude Shannon publicó un llibru llamáu "Analís simbólicu de circuitos con relés", estableciendo los primeros conceutos de l'actual teoría de la conmutación, cuando se produció un aumentu considerable nel númberu de trabayos d'aplicación de la Álxebra de Boole a los ordenadores dixitales. Anguaño, esta ferramienta resulta fundamental pal desenvolvimientu de los ordenadores yá que, cola so ayuda, l'analís y síntesis de combinaciones complexes de circuitos lóxicos puede realizase con rapidez.

Historia

La lóxica ye conocida como una de les ciencies más antigües, tantu ye asina que se-y atribúi a Aristóteles la paternidá d'esta disciplina. Partiendo de que correspuende a Aristóteles ser el primeru en tratar con tou detalle la lóxica, considérase-y el so fundador. Nun principiu llamóse Analítica, en virtú del títulu de les obres en que trató los problemes lóxicos. Más tarde los escritos de Aristóteles relativos a estos eventos fueron arrexuntaos polos sos discípulos col títulu de Órganon, por considerar que la lóxica yera un preséu pa la conocencia de la verdá.

Aristóteles plantegóse cómo ye posible probar y demostrar qu'una conocencia ye verdaderu, esto ye, que tien una validez universal. Aristóteles atopa'l fundamentu de la demostración na deducción, procedimientu que consiste en derivar un fechu particular de daqué universal. La forma en que s'afecta esa derivación ye'l siloxismu, por que la so razón la siloxística apuerta a el centru de la lóxica aristotélica.

Anque la lóxica proposicional (que ye intercambiable col cálculu proposicional) fuera suxerida polos filósofos anteriores, foi desenvuelta nuna lóxica formal por Chrysippus nel sieglu III AC y ampliada pol so socesor Stoics. La lóxica proposicional centrar en proposiciones. Esta meyora foi distinta de la lóxica siloxística tradicional que se centró nos términos. Sicasí, más tarde na antigüedá, la lóxica proposicional desenvuelta polos estoicos nun s'entendía [¿Quién?]. En consecuencia d'ello, el sistema foi reinventáu esencialmente por Peter Aberlard nel sieglu XII.

La lóxica proposicional foi finalmente refinada usando la lóxica simbólica, acreditóse ser el fundador de la lóxica simbólica'l matemáticu Gottfried Leibniz sieglu XVII/XVIII, pol so trabayu ratiocinator del cálculu. Anque'l so trabayu yera unos de los primeres, yera desconocíu pa la comunidá lóxica más grande. Arriendes d'ello, munchos de les meyores llograes por Leibniz fueron recreaos por lóxicos como George Boole y Augustus De Morgan dafechu independientes a Leibniz.

Según la lóxica proposicional puede considerase una meyora de la lóxica silogísta anterior, la lóxica del predicada de Gottlob Frege yera una meyora de la lóxica proposicional anterior. Un autor describe esta lóxica como la combinación de les traces distintives de la lóxica siloxística y la lóxica proposicional. Poro, la lóxica predicái marcó l'empiezu d'una nueva era na hestoria de la lóxica; sicasí, les meyores na lóxica proposicional fixéronse entá dempués de Frege, incluyendo Deducción Natural, Árboles de la Verdá y Tables de verdá. La deducción natural foi inventada por Gerhard Gentzen y Jan Lukasiewicz. Los árboles de la verdá fueron inventaos por Evert Willem Beth. La invención de les tables de la verdá, sicasí, ye d'atribución revesosa.

Dientro de les obres de Frege y Bertrand Russell, hai idees qu'inflúin na invención de les tables de la verdá. La estructura tabular real acredítase xeneralmente a Ludwig Wittgenstein o a Emil Post ( o dambos independientemente). Adeám de Frege y Russell, otros acreditaos con idees anteriores a les tables de la verdá inclúin a Philo, Boole, Charles Sanders Peirce. Otros acreditaos de la estructura tabular inclúin Lukasiewicz, Alfred North Whitehead, Guillermo Stanley Jevons, John Venn, y Clarence Irving Lewis. N'última instancia, dalgunos llegaron a la conclusión, como John Shosky, de que " ta lloñe de tar claro qu'a cualquier persona tien de dáse-y el títulu de 'inventor' de les tables de la verdá".

Ver tamién

Notes y referencies

↑ Simon Blackburn, ed., «propositional calculus» (n'inglés), propositional calculus, Oxford University Press, http://www.oxfordreference.com/views/ENTRY.html?subview=Main&entry=t98.y2552, consultáu'l 13 d'agostu de 2009
↑ Klement, Kevin C., «Propositional Logic» (n'inglés), Propositional Logic, http://www.iep.utm.edu/prop-log/, consultáu'l 6 de febreru de 2012
↑ Toida, Shunichi (2 d'agostu de 2009). «Proof of Implications» (inglés). CS381 Discrete Structures/Discrete Mathematics Web Course Material. Department Of Computer Science, Old Dominion University. Consultáu'l 10 de marzu de 2010.

Bibliografía

Enderton (1972). A Mathematical Introduction to Logic. Academic Press.
Hamilton (1981). Lóxica pa matemáticos editorial=Paraningo.
Mendelson (1997). Introduction to Mathematical Logic, 4ª, Chapman and May.
Pla, J. (1991). Lliçons de lóxica matemática. P.P.O..
Badesa, C.; Jané, I.; Jansana, R. (1998). Elemento de lóxica formal. Ariel.
Barnes; Mack (1978). Una introducción alxebraica a la lóxica matemática. Eunibar.
Bridge, J. (1977). Beginning Model Theory. Oxford University Pres.
Ershov, Y.; Paliutin, Y. (1990). Lóxica matemática. Mir.
Hofstadter, D. (1987). Gödel, Escher, Bach: un Eternu y Grácil Bucle. Tusquets Editores.
Jané, I. (1989). Álgebra de Boole y lóxica. Publicaciones O.B..
Monk (1976). Mathematical Logic. Springer-Verlag.
Nidditch (1978). El desenvolvimientu de la lóxica matemática. Cátedra.
Van Dalen, D. (1983). Logic and Structure, 2ª, Universitext, Springer-Verlag.

Enllaces esternos

Wikiversidá contién proyeutos d'aprendizaxe sobre Lóxica proposicional.
Introducción a la lóxica proposicional

[1] Simon Blackburn, ed., «propositional calculus» (n'inglés), propositional calculus, Oxford University Press, http://www.oxfordreference.com/views/ENTRY.html?subview=Main&entry=t98.y2552, consultáu'l 13 d'agostu de 2009

[iep-2] Klement, Kevin C., «Propositional Logic» (n'inglés), Propositional Logic, http://www.iep.utm.edu/prop-log/, consultáu'l 6 de febreru de 2012

[3] Toida, Shunichi (2 d'agostu de 2009). «Proof of Implications» (inglés). CS381 Discrete Structures/Discrete Mathematics Web Course Material. Department Of Computer Science, Old Dominion University. Consultáu'l 10 de marzu de 2010.

[1]

[2]

[3]