CAP3

SIS 1205 A ANALISIS DISCRETO
INGENIERIA DE SISTEMAS
_____________________________________________________________________________________
CAP.3
LGICA PROPOSICIONAL
3.1. INTRODUCCION.
Al tratar de la lgica, es muy comn utilizar frases como: "Es lgico", "hablando con
lgica", o, "hay que ponerle lgica al asunto", las mismas que pueden ser objetivamente
reemplazadas por expresiones como: "Es correcto", "hablando con correccin", y "hay que
ponerle cuidado y correccin al tema". Por tanto, la lgica trata sobre la correccin, y sta
se refiere de alguna manera, al pensamiento. Y es en este sentido que los tratadistas
tradicionales definieron la lgica como la ciencia que ensea a pensar correctamente.
Pero debemos distinguir entre el pensamiento como facultad y/o funcin del pensamiento
como producto. Pues, cuando utilizamos el trmino "pensamiento" podemos significar,
segn las circunstancias, la facultad y/o funcin o el producto, lo que equivale a distinguir
entre el pensar y lo pensado. Por tanto, la lgica no trata sobre le pensamiento como
facultad y/o funcin, sino como resultado de la funcin de pensar, es decir, de lo que
generalmente llamamos en plural: pensamientos.
Consecuentemente, al abordar la lgica proposicional, debemos reconocer que una
proposicin es una cadena de palabras con sentido completo, calificable de cierta o falsa,
as, por ejemplo, en la proposicin: "Sucre es la Capital de Bolivia". Si se mantienen
independientes, son proposiciones atmicas; pero si se relacionan con alguna conjuncin (u
otras partculas) el resultado es una proposicin molecular, por ejemplo, Juan y Pedro son
alumnos de Sistemas.
Corrientemente, las personas, al expresar ciertos razonamientos en el lenguaje natural, se
incurre en el empleo de aspectos subjetivos y ambiguos,
La parte de la lgica simblica que se ocupa del clculo de proposiciones o enunciados es
la llamada lgica de proposiciones o lgica proposicional. La lgica de proposiciones se
_____________________________________________________________________
M.Cs. Ing Julio Cesar Bermudez vargas

_____________________________________________________________________________________
ocupa de las operaciones entre proposiciones, sin tener en cuenta la estructura interna de las
mismas. Las proposiciones lgicas son expresiones que cumplen con una funcin
informativa, de la cual se puede decir, que sean verdaderas o falsas. Toda proposicin
lgica cumple con una funcin o valor de verdad, ya sea ste verdadero o falso. Las
proposiciones se abstraen o simbolizan mediante las letras proposicionales tales comos p, q,
r, e, ...y las mismas con subndices de ser necesario. As por ejemplo:
La lgica es una ciencia formal.
3.2. USO DEL LENGUAJE.

Entre las formas de utilizar el lenguaje podemos mencionar las siguientes como funciones
bsicas:
3.2.1. LENGUAJE COMO MEDIO DE COMUNICACIN DE INFORMACIN.
Un uso muy importante del lenguaje es aquel referido a la comunicacin de informacin,
lo cual se realiza mediante la formulacin y la afirmacin o la negacin de proposiciones.
Por ello se dice que el lenguaje usado para afirmar o negar proposiciones o para mostrar
razonamientos cumple una funcin informativa.
El discurso informativo es utilizado para describir el mundo y para razonar acerca de l;
pues el lenguaje sirve para suministrar a los dems informaciones, definiendo, declarando,
aclarando, describiendo, etc. los hechos; as, el lenguaje es usado informativamente.
3.2.2. LENGUAJE COMO MEDIO EXPRESIVO.
El lenguaje cumple una funcin expresiva particularmente en la poesa; pues se emplea
para dar rienda suelta a nuestros sentimientos, emociones, deseos y para despertar en los
dems estados anmicos anlogos a los que vivimos.
_____________________________________________________________________

_____________________________________________________________________________________
El verso no pretende transmitir informacin alguna, sino expresar ciertas emociones que el
poeta experimenta muy agudamente y anhela despertar en el lector sentimientos similares.
El lenguaje expresivo es utilizado para dar expansin a sentimientos y emociones, o para
comunicarlos.
Pero no slo el lenguaje potico es expresivo, tambin expresamos pena cuando
exclamamos: Qu desgracia! o Dios mo! o cuando expresamos nuestra alegra al decir:
Bravo! o Felicitaciones!
El discurso expresivo no puede ser ni verdadero ni falso; pues si alguien pretendiera aplicar
tales criterios al discurso expresado en un poema o en un verso, juzgar errneamente y
perder mucho de su valor.
El lenguaje expresivo puede ser descompuesto en dos componentes:
a. Cuando el lenguaje expresa o revela su propia actitud pero no est destinado a despertar
una actitud similar en algn otro, como cuando una persona se maldice a s misma en
momentos de soledad, cuando un poeta escribe poemas que no muestra a nadie o
cuando un hombre ora en soledad;
b. Cuando el lenguaje usado no slo pone de manifiesto las actitudes de los que hablan,
sino que pretende tambin despertar las mismas actitudes en sus oyentes, como cuando
un orador trata de instar a su auditorio, no a la accin, sino a que comparta su
entusiasmo, cuando un enamorado corteja a su amada en lenguaje potico, o cuando
una multitud vitorea a su equipo deportivo preferido.
3.2.3. LENGUAJE COMO MEDIO PRESCRIPTIVO.
Finalmente el lenguaje cumple una funcin prescriptiva o directiva cuando es utilizado con
el propsito de originar o impedir una accin manifiesta; es el caso de las rdenes y los
pedidos. Se ejerce mediante leyes, decretos, mandatos, ruegos, etc. Quien tiene autoridad
_____________________________________________________________________

_____________________________________________________________________________________
emite rdenes sin pretender comunicar informacin alguna ni
manifestar o despertar
alguna emocin particular. Lo que se busca es motivar o causar una accin.

Cuando se plantea una pregunta, se pide una respuesta que debe ser emitida. Esto conlleva
que la diferencia entre una orden y un pedido sea bastante sutil, ya que cualquier orden
puede traducirse en un pedido agregando las palabras "por favor" o mediante cambios
adecuados en el tono de voz o en la expresin facial.
Una orden no puede ser verdadera o falsa en ningn sentido literal. Y que la orden sea o no
obedecida, no afecta ni determina su valor de verdad, pues no tiene ningn valor de verdad.
Se puede no estar de acuerdo acerca de si una orden fue o no obedecida, si debe ser o no
obedecida; pero nunca podemos diferir acerca de si una orden es verdadera o falsa, pues
puede no ser ninguna de ambas.
Las rdenes tienen ciertas propiedades que muestran alguna analoga con la verdad o
falsedad del discurso informativo: son las cualidades de ser "razonables" o "adecuadas", y
"no razonables" o "inadecuadas".
3.3. LENGUAJES NATURALES Y LENGUAJES ARTIFICIALES:
Los lenguajes naturales, se construyen como producto de la relacin. entre los hombres y su
mundo, los matices, la ambigedad y vaguedad son el resultado de esta relacin. la lengua
natural, heredada, creada, y recreada a travs del tiempo, es el instrumento de
comunicacin, y una forma de vida.
Los lenguajes artificiales o formales son lenguajes construidos por la cienda,como resultado
de la necesidad de controlar cientficamente el mundo.
Es un lenguaje de precisin que formulan con mayor justeza las relaciones entre los objetos
y las ciencias respectivas. El lenguaje cientfico debe ser objetivo para tener 'consenso
pblico' dentro de una comunidad cientfica. La objetividad significa que las
_____________________________________________________________________

_____________________________________________________________________________________
correspondencias lxicas son establecidas explcitamente, que.el vocabulario es restringido

a la ciencia en cuestin, y que la sintaxis se simplifica.
El lenguaje artificial en general es un lenguaje con estructura de clculo, el clculo es un
sistema de relacines compuesto por un conjunto de trminos primitivos, o smbolos
elementales definidos por enumeracin o por propiedades; un conjunto de reglas de
formacin o construccin que determina las posibles combinaciones correctas de
losmbolos, y un conjunto de reglas de transformacin que determina las posibilidades de
reemplazar una combinacn correcta entre smbolos por otra combinacin igualmente
correcta. As por ejemplo en el agedrez: las piezas son los smbolos primitivos, las
instrucciones sobre la posicin de las piezas, son las reglas de formacin, y las reglas del
movimiento de las piezas, son las reglas de transformacin.
Clculos y juegos se parecen en que son autrquicos, es decir, carecen de otra finalidad que
no sea calcular o jugar. Lo esencial del clculo es su carcter exclusivamente formal, su
naturaleza puramente sintctica. No es un lenguaje en tanto medio de comunicacin, sino
una pura estructura sintctica. Sus elementos carecen de significado, son entidades opacas
que se manipulan con una serie de reglas. Sin embargo, un clculo se puede transformar en
un lenguaje cmo?, interpretando sus simbolos, proporcionando a stos, un significado. Al
interpretar los simbolos, el clculo se convierte en un lenguaje, ste no es un lenguaje
natural, sino un lenguaje formalizado, es decir, un lenguaje con estructura de clculo.Un
lenguaje donde no solo es artificial su vocabulario, sino"tambin la sintaxis del mismo. A
partir del siglo XIX Boole y Frege (1854-1879) se piensa que la lgica es un lenguaje
formalizado, o un conjunto de clculos a los que se da una interpretacin determinada en el
mbito de la investigacin.
3.4. PROPSITO DE LA LOGICA.Si se toma como punto de partida de que la Lgica Formal estudia la formalizacin del
lenguaje natural en un lenguaje formal y los principios de la inferencia valida, entonces un
propsito fundamental
en el proceso de formalizacin del lenguaje natural es la
_____________________________________________________________________

_____________________________________________________________________________________
formulacin de un lenguaje formal que se debe emplear
para el estudio de los
razonamientos.
La Lgica Proposicional
enfoca el estudio de la formulacin de un lenguaje formal
tomando como elemento central a la proposicin o enunciado simple, que puede ser
verdadero o falso.
No enfatiza en los componentes internos de las proposiciones como el sujeto y predicado,
mas bien considera a la proposicin como un todo indivisible.
3.5. PROPOSICIONES.
Una proposicin es una frase declarativa simple que puede ser verdadera o falsa. Es la
unidad mnima del lenguaje con contenido de informacin.
Las proposiciones, segn la lgica proposicional, pueden ser simples o atmicas, y
compuestas o moleculares.
Las proposiciones simples o atmicas son aquellas proposiciones que no admiten dentro de
si, ms que una sola proposicin, as por ejemplo:
La aritmtica, el lgebra y la geometra comparten las matemticas.
Juan, Pedro y Mara son hermanos.
En cada uno de estos casos, se trata de una sola proposicin, pues y no cumple con la
funcin de unir o de conjuncin, sino que cumple con la funcin de relacionar, como se
ver ms adelante en la lgica de predicados. Razn por la cual stos ejemplos se
simbolizan con la letra 'p'. En cambio si decimos:
La aritmtica, el lgebra y la geometra son disciplinas matemticas
_____________________________________________________________________

_____________________________________________________________________________________
Se trata de una proposicin compuesta por tres proposiciones tales como:

La aritmtica es una disciplina matemtica.
El lgebra es una disciplina matemtica.
La geometra es una disciplina matemtica
Y la simbolizacin correspondiente a las mismas ser mediante las letras proposicionales

p, q, r, respectivamente, con lo cual la simbolizacin correspondiente en es: p . q . r
En este ejemplo (1) y cumple con la funcin de unir o nexo conjuntivo de las tres
proposiciones.
Las proposiciones compuestas o moleculares son proposiciones que admiten dentro de s,
dos o ms proposiciones; o tambin, las proposiciones moleculares son aquellas
compuestas por dos o ms proposiciones atmicas, relacionadas entre s mediante
expresiones lingsticas llamadas conectivas. En el ejemplo ltimo dado, la conectiva que
se ha utilizado es la conjuncin.
3.5.1. TIPOS DE PROPOSICIONES.

Dependiendo del tipo de informacin que se quiera representar, las proposiciones pueden
ser de diferente tipo:
a) De accin.- Expresa la ocurrencia de un hecho y no hace referencia a algn objeto
o individuo especifico.
Ej:
-
Hace calor.
Llueve.
Es viernes.
_____________________________________________________________________

_____________________________________________________________________________________
b) De atribucin de propiedades a sujetos especficos.- Este tipo de proposiciones

describen una propiedad o caracterstica que tiene un objeto o individuo especifico.
Ej:
-
Juan juega futbol.
La casa es verde.
Pedro es bueno.
c) De Relacin: Relacionan sujetos u objetos, se debe tener cuidado en que la

proposicin no se constituya en una proposicin molecular o la combinacin de dos
proposiciones atmicas (frases declarativas simples).
Ej:
-
Juan y Pedro son primos.
Juan esta sentado entre luis y Jaime.
3.6. CONECTIVAS.
las elementos que relacionan unas proposiciones con otras se denominan conectivas
(conectores), pues toda proposicin molecular necesariamente est determinada o afectada
por una o varias conectivas.
Si se considera los siguientes ejemplos de proposiciones moleculares:
Melgar Y Vallejo son dos grandes hombres.
Juan sabe francs Y ingls.
Juan se casa O termina su noviazgo.
Si es estudioso, ENTONCES aprobar el examen.
Manuel ir al estadio SI, Y SLO SI, juega San Jos.
NO es cierto que Luis Y Ana sean buenos estudiantes.
_____________________________________________________________________

_____________________________________________________________________________________
Se puede observar que los elementos (resaltados con maysculas) son conectivas porque
relacionan unas proposiciones con otras.
Es importante notar que el elemento NO, en lgica es considerado una conectiva, pues,
aunque no conecta, afecta negativamente tanto a proposiciones atmicas por separado como
a relaciones entre proposiciones. Ello significa que la parte de la lgica que estudia los
diversos modos de relacin de las proposiciones en un discurso, sin intentar ingresar en un
anlisis de la estructura de las mismas, se denomina lgica proposicional, sentencial o de
enunciados; pues, proposicin, sentencia, o enunciado son trminos sinnimos.
CONECTIVA
NEGACION
SIMBOLO
EXPRESION EN LENGUAJE NATURAL
~p
NO p
no ocurre que p
no es cierto que p
es falso que p
etc.
P y/e q
p aunque q
p pero q
p sin embargo q
p no obstante q
p a pasar de q
etc.
p o/u q
o bien p o bien q
al menos p o q
como minimo p o q
etc.
si p entonces q
solo si q entonces p
p suficiente para q
q necesario para p
no p a menos que q
etc.
p si y solo si q
p necesario y suficiente para q
CONJUNCION
pq
DISYUNCION
pq
IMPLICACION
pq
BICONDICIONAL
pq
_____________________________________________________________________

_____________________________________________________________________________________
3.7. DEFINICIN FORMAL DEL LENGUAJE PROPOSICIONAL.

El punto de partida para la definicin de un lenguaje formal es el establecimiento del
alfabeto del lenguaje, todos los lenguajes comportan un conjunto finito de smbolos que
permiten la formacin de las estructuras del lenguaje, es decir, la formacin de palabras
oraciones, etc. El lenguaje natural, castellano en nuestro caso, considera un conjunto de
smbolos (letras) mediante las cuales es posible construir las palabras y oraciones, las
cuales contienen alguna informacin.
3.7.1. ALFABETO DEL LENGUAJE.
Constituyen el conjunto de smbolos que el lenguaje requiere, el lenguaje para una Lgica
Proposicional requiere tres tipos de smbolos:
1. Smbolos para proposiciones.: llamados tambin letras proposicionales son
codificaciones de proposiciones atmicas o frases declarativas simples. Se
recomienda emplear letras minsculas a partir de la letra p, por ejemplo p, q, r, s,
...... para grupos pequeos y letras subindicadas para grupos grandes, por ejemplo
p1, p2, p3, p4, .................
Al conjunto de de smbolos para las letras proposicionales se las denota con la letra
P.
Por ejemplo:
P = { p, q , r, s ,t }
2. Smbolos para Conectivos lgicos: elementos de conexin que permiten formar
estructuras complejas del lenguaje: (negacin) ; (disyuncin) ; (conjuncin)
; (implicacin) ; (doble implicacin) .
_____________________________________________________________________
10

_____________________________________________________________________________________
3. Smbolos de parntesis o de puntuacin: para el establecimiento de subestructuras

y niveles de prioridad : ( , )
Ej:
p : Juan juega futbol.

r : Juan es bueno.
s : Pedro es bueno
t : Llueve
Observaciones:
Los conjuntos 2. y 3. son comunes para todo lenguaje proposicional, es decir no

cambian.
El conjunto 1. varia de acuerdo al fenmeno o razonamiento que se esta modelando,

es decir cada razonamiento proporciona un conjunto P diferente cuyas letras
proposicionales codifican proposiciones diferentes aun cuando las letras sean las
mismas.
Por ejemplo:
r1
P={p, q, r, s, t}
r2
P={p, q, r}
r3
P={a, b, c, d, e, f, g}
Como el conjunto P es variable, por lo tanto el lenguaje proposicional a desarrollar esta en

funcin del conjunto P y se lo denota como sigue:
L(P)
3.7.2. SINTAXIS DEL LENGUAJE PROPOSICIONAL:

Tomando como base el conjunto de smbolos del lenguaje (alfabeto) se debe establecer el
conjunto de reglas para la obtencin de formulas bien construidas (fbc) del lenguaje, porque
_____________________________________________________________________
11

_____________________________________________________________________________________
la simple combinacin de proposiciones y conectivas no garantiza la obtencin de frases

sintacticamente correctas..
Definicin.- Las Formulas Bien Construidas (fbc) del lenguaje proposicional se definen
recursivamente con la aplicacin de las siguientes reglas:
1. Toda Letra Proposicional es una formula bien construida del lenguaje. A estas
formulas se las denomina Formulas Atmicas.
2. Si A y B son frmulas del lenguaje , entonces:
A , B , (A B) , (A B ) , (A B), (A B ) tambin son frmulas del
lenguaje.
3. Son frmulas del lenguaje nicamente las obtenidas con la aplicacin de las reglas 1
y 2.
La descripcin de estas tres reglas contempla una definicin recursiva.
CASO BSICO: Regla 1.
PROCESO INDUCTIVO: Reglas 2 y 3
Ej: Dado el conjunto P de letras proposicionales: P{p, q, r, s}
Son formulas del lenguaje:
-
s,
(formula atmica) por la regla 1.

(pq) r , ((pq) r) t ( por la regla 2.)
El uso adecuado de parntesis es muy importante para definir las sub estructuras del una
formula.
Por lo tanto:
p q
es diferente a (p q) r
_____________________________________________________________________
12

_____________________________________________________________________________________
El empleo del alfabeto del lenguaje y de las reglas sintcticas establecidas permiten formar
proposiciones complejas que se las desglosa de la siguiente manera:
Proposiciones conjuntivas:
Las proposiciones conjuntivas surgen de la unin de dos proposiciones atmicas, que se
denominarn componentes conjuntivos, y la alteracin de la ubicacin de los mismos no
incide en la funcin de la conjuncin, que es unir. La condicin que hace una conjuncin
verdadera, es que ambos componentes conjuntivos sean verdaderos, en caso contrario la
conjuncin es falsa.
As por ejemplo:
p q
Locke y Hume son representantes del empirismo ingls

Los componentes conjuntivos son:
Locke es representante del empirismo ingls
Hume es representante del empirismo ingls
Descartes es racionalista, pero Hume es empirista
p q
Donde :
p: Descartes es racionalista.
q: Hume es empirista.
Aunque Descartes es idealista, Hume es empirista
p q
Donde :
_____________________________________________________________________
13

_____________________________________________________________________________________
p: Descartes es idealista.
q: Hume es empirista.
Proposiciones disyuntivas:
Las proposiciones disyuntivas surgen de la inclusin o no de dos alternativas. las
proposiciones que las componen, se denominarn componentes disyuntivos, y como en el
caso de la conjuncin, la alteracin de la ubicacin de los mismos no incide en la funcin
de la disyuncin.
As por ejemplo en la disyuncin inclusiva:
A menos que se tomen medidas, el Riachuelo seguir contaminado.

pvq
donde:
p: se toman medidas.
q: el riachuelo seguir contaminado.
Las becas de investigacin son para Francia y/o Alemania

p vq
donde:
p: las becas de investigacin son para Francia.
q: las becas de investigacin son para Alemania.
Un ejemplo de disyuncin exclusiva:
La tarifa area incluye un viaje de cabotaje o a Bariloche o a cataratas

pvq
donde:
p: la tarifa area incluye un viaje de cabotaje a Bariloche.
q: la tarifa area incluye un viaje a cataratas.
_____________________________________________________________________
14

_____________________________________________________________________________________
O bien descartes es racionalista, o bien es empirista

p vq
donde:
p: Descartes es racionalista.
q: Descartes es empirista.
La condicin que hace una disyuncin verdadera, radica en que siempre al menos uno de
los componentes sea verdadero. Solamente en la disyuncin inclusiva tambin es verdadera
cuando ambos componentes sean verdaderos, en caso contrario es falsa.
Se utilizar la disyuncin inclusiva, para todos los ejemplos posteriores, en todos los casos
de disyuncin que se encuentren en las operaciones entre proposiciones y/o razonamientos.
Proposiciones condicionales:
las proporciones condicionales presentan una estructura muy peculiar, en la cual los
elementos (antecedentes y consecuentes), que las componen no puedan alterar su ubicacin,
pues esto modificara la funcin de la misma. En las proposiciones condicionales, la
ubicacin de las proposiciones que la componen (antecedentes y consecuente) se determina
por la estructura misma. La nica condicin que hace un condicional falso, radica en el
caso de un antecedente verdadero y un consecuente falso, por cuanto ser verdadero en
todos los otros casos. As por ejemplo:
Si los pasajes se reservan con tiempo, viajaremos en primera.

Antecedente p: Los pasajes se reservan con tiempo.
consecuente
p
q: viajaremos en primera.
q
Viajaremos en primera, Si los pasajes se reservan con tiempo.

Consecuente p:viajaremos en primera.
Antecedente q: Los pasajes se reservan a tiempo.
q
_____________________________________________________________________
15

_____________________________________________________________________________________
Iremos al campo, Solo si hace buen tiempo.

Antecedente p: hace buen tiempo.
Consecuente q: Iremos al campo.
p
Cabe sealar, que este tipo de proposiciones condicionales se denominan tambin

materiales, se caracterizan por tener los verbos en modo indicativo. Pero hay otro tipo de
proposicin condicional que se denomina contra fctico y se caracterizan por tener verbos
en modo subjuntivo, con lo cual no es posible determinar el valor de verdad de las
proposiciones que lo componen, ya que stas refieren a situaciones que no existen. Por lo
tanto los condicionales contra fcticos exceden el mbito de la lgica, y sta no se ocupa de
ellos. As por ejemplo:
Si San Martn no se hubiera muerto, seguira vivo.
A partir de lo visto en los ejemplos de proposiciones condicionales materiales, es
importante tener en cuenta que: si bien la asignacin de las letras proposicionales es
arbitraria, en la simbolizacin de las proposiciones, sin embargo es conveniente seguir un
orden determinado. Por lo tanto se sugiere que la adjudicacin de las letras siga la
secuencia de las mismas: p, q, r, s, t y en funcin del orden en que vayan apareciendo las
proposiciones, una vez simbolizadas las proposiciones, se procede a abstraer la forma
proposicional segn lo indique la conectiva en cuestin. As por ejemplo:
Descartes es idealista, si Locke es realista y Hume es realista.

P
q
r
(q r)
(1)
Segn Kant, si la intuicin se constituye de materia y de forma,

p
q
entonces la materia es la sensacin y la forma es Espacio tiempo.
r
s
_____________________________________________________________________
16

_____________________________________________________________________________________
(p q)
(r s)
(2)
En la simbolizacin correspondiente a las formas proposicionales compuestas, se utilizan

los signos de puntuacin tales como el parntesis, corchete y llave, en el mismo sentido con
que operan en las matemticas, es decir, determinan el alcance de una operacin, en este
caso la operacin, que se lleva a cabo por una conectiva.
En el ejemplo (1), el si indica el antecedente de la construccin principal que es el
condicional, dicho antecedente, es a su vez una proposicin compuesta conjuntiva, por lo
tanto, el parntesis nos indica el alcance de la conjuncin y a su vez, el antecedente del
condicional.
En el ejemplo (2), el si nos indica el antecedente proposicin conjuntiva y el entonces
nos indica el consecuente proposicin conjuntiva- en cada uno de ellos el parntesis
indica el alcance de la conjuncin respectiva, y adems determina el antecedente por un
lado, y el consecuente del condicional, por el otro.
Otro aspecto que se debe tener en cuenta en la simbolizacin, es que cuando una
proposicin atmica se repite, tambin debe repetirse la letra proposicional adjudicada en la
simbolizacin de la misma. As por ejemplo:
O Descartes es idealista, o Descartes no es idealista.
p
-p
p w -p
Proposiciones Bicondicionales:
Las proposiciones bicondicionales son las proposiciones construidas por la equivalencia ( o
mutua implicacin) entre las proposiciones que la componen. Los componentes del
bicondicional se denominan:
_____________________________________________________________________
17

_____________________________________________________________________________________
Componente izquierdo y componente derecho. Un bicondicional es un condicional doble,

esto quiere decir, que la proposicin bicondicional p = q, es equivalente a la conjuncin
de dos condicionales, donde el antecedente del primero es consecuente del segundo, y el
consecuente del primero es antecedente del segundo. La condicin que hace una
proposicin bicondicional, verdadera, es que ambos componentes tengan el mismo valor de
verdad, ya sea ste verdadero, o falso. As por ejemplo:
Ingresa a la facultad si y solo si aprueba el ciclo bsico

Componente izquierdo
componente derecho
P
q
P q
Bicondicional o doble implicacin:

Si ingresa a la facultad, aprob el ciclo bsico. Y si aprueba el ciclo bsico, ingresa a la
facultad
P
q
q
p
(p
q) ( q
p)
As como en las proposiciones condicionales vimos que hay casos de condicionales contra
fcticos, en las proposiciones bicondicionales tambin se dan las bicondicionales contra
fcticas como por ejemplo:
Habra alcanzado el triunfo si y solo si se hubiera esforzado.
La lgica solo se interesa por las proposiciones bicondicionales materiales, y no se ocupa
de las bicondicionales contra fcticas pues de stas no es posible determinar su valor de
verdad.
Como la definicin de las reglas sintcticas
contempla una definicin recursiva o
inductiva, entonces es posible aplicar la induccin para demostrar propiedades y conceptos

acerca de las formulas del lenguaje.
_____________________________________________________________________
18

_____________________________________________________________________________________
INDUCCIN SOBRE FRMULAS.La definicin inductiva de las reglas sintcticas permiten aplicar la induccin matemtica
para la demostracin de propiedades del lenguaje, en este proceso puede existir mas de un
caso bsico.
Ejemplo: Definir una funcin para determinar el nmero de conectivos que aparecen en una
frmula A
La funcin a definir es numconect( - ) que da como resultado el numero de conectivos que
tiene una formula arbitraria.
CASO BSICO.- Si A es una frmula atmica.
numconect(A) = 0
Ya que una frmula atmica est formada por una letra proposicional.
PROCESO INDUCTIVO.-Si A es de la forma B
numconect(A) = 1+numconect(B)
-Si A es de la forma (B*C) donde * puede ser{, , , }entonces:
numconect(A)=1+numconect(B)+numconect(C)
SEGUIMIENTO DE LA FUNCION INDUCTIVA:
Sea la formula A = (p q) r
_____________________________________________________________________
19

_____________________________________________________________________________________
Numconect ((p q) r)
= 1+ numconect ((p q)) + numconect(r)

2
1 + numconect(p q)
1
1 + numconect(p) + numconect( q)
0
Numconect ((p q) r) = 3
3.7.3. SEMANTICA DEL LENGUAJE PROPOSICIONAL.Si bien se tiene estructurado en conjunto de reglas de correcta escritura de las formulas del
lenguaje, es con la semntica que se proporciona el significado y el valor de verdad que se
asumir para los procesos de validacin de argumentos.
PROPSITO.El propsito de la semntica del lenguaje proposicional se puede resumir en los siguientes
aspectos:
-
Dar significado a los elementos del lenguaje.
Definir el concepto de verdad.
Definir el concepto de consecuencia lgica.
a) Definir el conjunto de significados.La definicin de significados consiste en establecer el conjunto de posibles valores que
pueden tomar las letras proposicionales y las formulas del lenguaje. La Lgica
_____________________________________________________________________
20

_____________________________________________________________________________________
proposicional al ser parte del razonamiento matemtico, contempla un conjunto de

valores que puede ser Verdadero o Falso.
Conjunto de significados = {V , F } o {1 , 0}
Todas las letras proposicionales toman valor de dos posibles, es por este motivo que
corresponde a una lgica bi- valente.
b) Definicin semntica de conectivos.Se debe establece un r el significado de estructuras formadas por la relacin de
proposiciones atmicas y conectivos lgicos. Se lo muestra en las siguientes tablas:
Disyuncin Conjuncin Implicacin Bi condicional

Negacin
p q
pq
pq
pq
pq
V V
V F
F V
F F
c) Letras Proposicionales:
Las letras proposicionales representan informacin diferente en funcin al fenmeno
que se est representando. Es decir:
-
Codificacin de proposiciones (frases declarativas simples).
Representan informacin.
_____________________________________________________________________
21

_____________________________________________________________________________________
Ej: Si Manuel juega ftbol y no estudia entonces reprobar el examen .

p:
Manuel juega futbol.
q : Manuel estudia.
r : Reprueba el exmen.
Y su representacin simblica es:
(pq) r
3.7.3.1. CONCEPTO DE VERDAD.Todo lo visto hasta este momento supone que no se ha establecido un valor de verdad para
las diferentes letras proposicionales, es decir, las letras proposicionales solo son
codificaciones de frases declarativas simples que pueden ser verdaderas o falsas, la
definicin del concepto de verdad se establece asignando valores de verdad a los elementos
fundamentales del lenguaje, las letras proposicionales.
La asignacin de valores de verdad a las letras proposicionales se lleva a cabo por medio de
una funcin de asignacin de valores de verdad, a esta funcin se la denomina funcin a.
Funcin de asignacin de valores de verdad.
La funcin a asigna valores de verdad al conjunto de letras proposicionales del lenguaje.
Cada letra proposicional toma un valor de dos posibles, el universo o conjunto de
significados se ha establecido previamente y esta formado por {Verdadero, Falso} y se
denota como sigue:
a: p {V,F}
Ej:
Sea P={p, q, r} el conjunto de letras proposicionales del lenguaje.
Se puede establecer las siguientes funciones de asignacin de valores de verdad:

_____________________________________________________________________
22

_____________________________________________________________________________________
a1= {p=V, q=F, r =V}
Conjunto de significados
a2= {p=F , q = F , r= V}
V=1
F =0
.
an= {p=V , q= V , r=v}
Observaciones:
-
A una funcin de asignacin de valores de verdad se las denomina tambin

VALUACIONES.
Si P contiene n letras proposicionales entonces se tiene 2n valuaciones diferentes.
Toda letra proposiocional toma 1 valor de 2 posibles.
3.7.3.2. INTERPRETACIN DE FRMULAS.Una valuacin asigna valores de verdad a los elementos atmicos del lenguaje, letras
proposicionales, sin embargo el lenguaje esta conformado por estructuras mas complejas
llamadas formulas que representan informacin resultante de la combinacin de letras
proposicionales y conectivos lgicos. Por lo tanto es importante definir claramente la forma
en que una estructura compleja, una formula, toma un valor de verdad determinado, a este
proceso se lo denomina interpretacin de formulas del lenguaje. En resumen la
interpretacin de formulas tiene por objetivo:
Determinar el valor de verdad de una frmula para una valuacin especifica.
Como se mostr en la definicin de la Sintaxis del lenguaje proposicional, la definicin de
una formula contempla una definicin inductiva, es decir, la construccin de una formula,
tiene una definicin recursiva, por lo tanto, la interpretacin de formulas, para determinar
su valor de verdad para una valuacin especifica, se lo realiza por medio de una definicin
inductiva.
_____________________________________________________________________
23

_____________________________________________________________________________________
DEFINICIN INDUCTIVA PARA INTERPRETACIN DE FORMULAS.

Sea la Frmula A. Una formula arbitraria del lenguaje proposicional.
Se define la funcin a(...)
:El valor de verdad de ...
La funcin a() se aplica a un parmetro que es la formula que se quiere evaluar.

CASO BSICO.- Si A es una frmula atmica.
a(A) =
valor asignado por una funcin de asignacin de valores de verdad

(VALUACIN) a las letras proposicionales.
PROCESO INDUCTIVO.- Si A es de la forma B:

a(A) = 1- a(B)
-Si A es de la forma (B C)
a(A) = max (a(B), a(C))
-Si A es de la forma (B V)
a(A) = min (a(B), a(C))
-Si A es de la forma (BC)
a(A)= 0 si a(B) = 1 y a(C) = 0
1
en caso contrario
-Si A es de la forma (BC)

a(A) =
1 si a(B) = a(C)
0
en caso contrario.
Ej: Determinar el valor de verdad de la siguiente frmula:

A = (p q ) (r ( p q ))
para a: {p=1 ; q=0; r=1}
_____________________________________________________________________
24

_____________________________________________________________________________________
primero el parntesis interno:

A = (p q ) (r ( p q ))
a() = max(a(p),a(q))
a() = max(1,0)
A = (p q ) (r 1)
Luego el parntesis de la izquierda:
A = (p q ) (r 1)
a() = min(a(p),a( q))
a() = 1-a(q)
a() = 1 0
a() = min (1,1)
A = 1 (r 1)
Ahora el parntesis de la derecha:
A = 1 (r 1)
a() = (1-a(r)) 1
a() = (1 1) 1
a() = 0 1
a() = 1
A =11
Finalmente:
a(A) = 1
Para la valuacin establecida la formula es verdadera.
_____________________________________________________________________
25

_____________________________________________________________________________________
La determinacin del valor de verdad de una formula para una valuacin determinada
aplicando la definicin inductiva de la funcin es un poco larga, es por este motivo que se
puede recurrir a procesos que simplifican dicha evaluacin pero aplicando la funcin
inductiva como sigue:
Se debe descomponer la formula en subformulas hasta encontrar elementos atmicos, es
decir letras proposicionales en una estructura ramificada, donde en las ramas inferiores
aparecen nicamente letras proposicionales y en funcin al valor que tienen estas, por
medio de una asignacin de valores de verdad, se procede a evaluar la formula de abajo
hacia arriba.
(p q ) ( r (q q)) = 1
p q =1
p=1
r (p q) =1
q = 1
q=0
r = 0 p q =1
r=1
p=1
q=0
-De otro modo: Sin necesidad de descomponer en subformulas, nicamente se desarrolla la

evaluacin en funcin de los valores de verdad de las letras proposicionales:
(p q) (r (pq) )
1
1 0
1
1
_____________________________________________________________________
26

_____________________________________________________________________________________
3.7.3.3. EVALUACIN SEMNTICA DE FORMULAS.

La evaluacin semntica de formulas supone determinar el valor de verdad de la formula
para todas las posibles valuacin, es decir, se debe establecer el valor de verdad para todas
las posibles combinaciones existentes. Este proceso se lo lleva a cabo por medio de tablas
de verdad.
Normalmente una formula, por la definicin inductiva en su construccin, contiene
subformalas, es decir, esta formada por otras formulas mas simples, por lo tanto se debe
establecer el valor de verdad , en forma gradual, de todas las subformulas hasta, finalmente,
obtener la evaluacin de la formula completa. La siguiente tabla ilustra este proceso:
A = (p q ) (r ( p q ))
p
1
1
1
1
0
0
0
0
q
1
1
0
0
1
1
0
0
R q r ( p q )
1 0
0
1
0 0
1
1
1 1
0
1
0 1
1
1
1 0
0
1
0 0
1
1
1 1
0
0
0 1
1
0
(p q )
0
0
1
1
0
0
0
0
(r ( p q ) (p q ) (r ( p q ))
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
FRMULAVLIDA.Es cuando para cualquier valuacin el valor de verdad de la frmula es V. (tablas de

verdad).
La columna de la formula en la tabla de verdad es siempre 1 o V.
_____________________________________________________________________
27

_____________________________________________________________________________________
Estas formulas se denominan TAUTOLOGIA.

Ej: ((p q) p) q
P
pq
(p q) p
((p q) p) q
FRMULA SATISFASCIBLE:
Una formula es satisfascible si es verdadera por lo menos para una valuacin.
Estas formulas se llaman tambin CONTINGENCIA. El siguiente ejemplo muestra esta
situacin.
A = (p (r ( p q ))
p
1
1
1
1
0
0
0
0
q
1
1
0
0
1
1
0
0
R r ( p q )
1 0
1
0 1
1
1 0
1
0 1
1
1 0
1
0 1
1
1 0
0
0 1
0
(r ( p q )
(p (r ( p q ))
1
1
1
1
1
1
1
0
1
1
1
1
0
0
0
0
FRMUAL INSATISFASCIBLE:
Una formula es insatisfascible si es falsa para cualquier valuacin.
Estas formulas se llaman tambin CONTRADICCIN.
_____________________________________________________________________
28

_____________________________________________________________________________________
3.7.3.4. EVALUACIN SEMNTICA DE DEDUCCIONES.

Una deduccin o razonamiento se compone de un conjunto de premisas, que es la
informacin conocida respecto a algn fenmeno, y una conclusin, que es la informacin
que se trata de obtener a partir del conjunto de premisas.
-Conjunto de premisas => lo conocido
-Conclusin:
=> lo que se quiere conocer.
{p1, p2, p3, ......................,pn} => Q
La verdad de la conclusin se sigue a partir de la verdad del conjunto de premisas.

Si la conclusin se puede obtener a partir del conjunto de premisas, entonces se dice que la
conclusin es consecuencia lgica del conjunto de premisas, en caso contrario se dice que
la conclusin no es consecuencia lgica del conjunto de premisas.
CONSECUENCIA LGICA.Deduccin:
Conjunto de premisas
Conclusin
=> Q
Q es consecuencia logia de
Q no es consecuencia lgica de
ARGUMENTO VLIDO.-
_____________________________________________________________________
29

_____________________________________________________________________________________
Un argumento es valido si Q es consecuencia lgica de . A nivel semntico un argumento

es valido cuando no existe ninguna valuacin que haga simultneamente verdadera al
conjunto de premisas y falsa a la conclusin.
La demostracin de la validez de un argumento a nivel semntico supone evaluar todas las
formulas del conjunto de premisas y la conclusin, este proceso se lo realiza por medio de
tablas de verdad, si en las diferentes valuaciones no existe ninguna fila (valuacin) en la
que todas las formulas, del conjunto de premisas, son verdaderas y la conclusin es falsa
simultneamente, entonces el argumento o deduccin es valida en caso contrario el
argumento no es valido. El siguiente ejemplo ilustra esta situacin
Ej: Demostrar la validez del siguiente argumento:
Un lquido es cido si y solo si colorea de azul el papel tornasol rojo. Un lquido colorea
de azul el papel tornasol rojo si y solo si contiene iones de hidrgeno libres. Por lo tanto, un
lquido es cido si y solo si contiene iones de hidrgeno libres.
1: letras proposicionales: en este punto se debe identificar el conjunto de letras
proposicionales del lenguaje.
p: Un lquido es cido.
q: Un lquido colorea de azul el papel tornasol rojo.
r: Un lquido contiene iones de hidrgeno libres.
El conjunto de letras proposicionales del lenguaje es:
P={p, q, r}
2: Frmulas de lenguaje: A partir de las letras proposicionales identificadas en el paso
anterior se debe construir las formulas del lenguaje, mediante las cuales se reproduce todo
el argumento a nivel simblico, se debe construir la base de conocimiento (el conjunto de
_____________________________________________________________________
30

_____________________________________________________________________________________
premisas que es la informacin conocida) y la conclusin (que es la informacin que se

desea obtener a partir de de la base de conocimiento):
Un lquido es cido si y solo si colorea de azul el papel tornasol rojo.

pq
Un lquido colorea de azul el papel tornasol rojo si y solo si contiene iones de

hidrgeno libres.
qr
La base de conocimiento o el conjunto de premisas a nivel simblico es:

={pq; qr}
La conclusin es la siguiente:
un lquido es cido si y solo si contiene iones de hidrgeno libres.

pr
Q = {pr}
3: Tablas de verdad: Se debe evaluar, tanto las formulas de la base de conocimiento y de la

conclusin por medio de tablas de verdad:
pq
qr
Pr
_____________________________________________________________________
31

_____________________________________________________________________________________
En la tabla se observa que las nicas filas (valuaciones) donde el conjunto de premisas son
verdaderas son la fila 1 y fila 8, entonces solo debemos analizar estas filas y observar el
valor de verdad de la conclusin para estas filas, como la conclusin para estas filas
tambin es verdadera, entonces el argumento es valido. En el supuesto caso de que existiera
un valor de verdad falso, para la conclusin, en una de estas dos filas
entonces el
argumento seria invalido.

Ejemplo: Demostrar la validez de la siguiente deduccin:
O Juan y Jos tienen la misma edad o Juan es mayor que Jos. Si Juan y Jos tienen la
misma edad entonces Pedro y Juan no tienen la misma edad. Si Juan es mayor que Jos
entonces Juan es mayor que Maria . Por lo tanto o Pedro y Juan no tienen la misma edad o
Juan es mayor que Maria.
1: letras proposicionales:
p: Juan y Jos tienen la misma edad.
q: Juan es mayor que Jos.
r: Pedro y Juan tienen la misma edad
s: Juan es mayor que Maria.
2: frmulas de lenguaje.
= { p q ; p r ; qs}
Q={r s }
3: Tablas de verdad
Como el conjunto de letras proposicionales contiene cuatro letras, entonces se tiene un total
de 16 valuaciones diferentes.
_____________________________________________________________________
32

_____________________________________________________________________________________
pq
p r
qs
r s
En la tabla de verdad al no existir ninguna valuacin que haga simultneamente verdadera

al conjunto de premisas y falsa a la conclusin, entonces el argumento es valido, es decir, la
conclusin es consecuencia lgica del conjunto de premisas.
Ejemplo: Demostrar la validez del siguiente argumento:
O la lgica es difcil o no le gusta a muchos estudiantes. Si la matemtica es fcil,
entonces la lgica no es difcil. Por lo tanto, si a muchos estudiantes les gusta la lgica, la
matemtica no es difcil.
p: La lgica es difcil
_____________________________________________________________________
33

_____________________________________________________________________________________
q: La lgica gusta a muchos estudiantes.

r: la matemtica es fcil.
2: Frmulas del lenguaje
= { p q ; r p }
Q = {q r}
3: tablas de verdad:
p q
r p
q r
De la misma forma que en los casos anteriores el argumento es Vlido.

En alguno casos los argumentos no presentan en forma explicita los dos componentes
fundamentales, es decir, la base de conocimientos y la conclusin, en estos casos, la
conclusin a validar se la obtiene a base de consultas a la base de conocimientos, el
siguiente ejemplo muestra una situacin como esta.
Ejemplo: Formalizar en el lenguaje proposicional:
Manuel, Mauricio y Gabriel son acusados de fraude fiscal en el juicio ellos declaran lo
siguiente:
_____________________________________________________________________
34

_____________________________________________________________________________________
Manuel: Mauricio es culpable y Gabriel es inocente.

Mauricio: Manuel es culpable solo si Gabriel es tambin culpable.
Gabriel : Yo soy inocente pero al menos uno de los otros es culpable.
p: Manuel es inocente.
q: Mauricio es inocente.
r: Gabriel es inocente.
2: Frmulas de lenguaje:
Las formulas del lenguaje se las obtiene a partir de los que dice cada uno de los acusados.
Manuel dice:
q r
Mauricio dice:
rp
Gabriel dice:
r (p q)
= { q r , r p , r (p q)}
3: Contestar las siguientes preguntas:

a) Si todos son inocentes Quien ha mentido?
b) Si se supone que todos dicen la verdad , Quin es inocente y quien es culpable?
Por medio de tablas de verdad se puede establecer el valor de verdad respecto a lo que
dice cada uno de los acusados y en funcin a los valores obtenidos se podr respuesta a
las interrogantes.
_____________________________________________________________________
35

_____________________________________________________________________________________
p q r Manuel Mauricio p q
q r
r p
Gabriel
r (p q)
R.- a)
Para dar respuesta a la primera interrogante, se observa que la primera fila es
la valuacin en la que todos son inocentes y de acuerdo a los valores obtenidos en la

tabla de verdad los que han mentido son Manuel y Gabriel.
b) La tercera valuacin es la valuacin en la que todos dicen la verdad y rn este
caso Mauricio es culpable.
3.7.3.5. TEOREMA DE LA CONSECUENCIA LGICA.1: Monotona.Sea
Si
Entonces :
L(P) ;
* L(P)
y
: Q L(P)
=> Q
* => Q
Si se tiene una deduccin valida ( => Q) la incorporacin de nueva informacin

a (*) no invalida la deduccin.
Ej:
= { (p q) r ; q r ; r q)}
Q = {p}
_____________________________________________________________________
36

_____________________________________________________________________________________
=> Q
* = {(p q) r ; q r ; r q,( rq ) p , q}
Q = p
* => Q ............Se mantiene
2: Sea
L(P) y Q L(P)
es insatisfascible
Si y Solo Si
=> Q
De un conjunto de premisas insatisfascibles se puede coincidir cualquier

informacin.
3: Sea F una contradiccin fija de L(P) y (P)
es insatisfascible
Si y Solo Si
=> F
De una Base de conocimientos es insatisfascible si a partir de ella se puede concluir

una contradiccin fija.
4: Sea Q L(P) y un conjunto vaco de frmulas
Q es vlida si y solo si
=> Q
Una formula es valida (tautologa) si es consecuencia lgica de un conjunto vaco

de formulas, es decir, si la negacin de la formula es una contradiccin.
5: TEOREMA DE DEDUCCIN
Sea:
L(P)
{Q} => P
Q, P L(P)
si y solo si => (Q P)
_____________________________________________________________________
37

_____________________________________________________________________________________
Si en la conclusin hay una implicacin entonces el antecedente de la implicacin

puede formar parte del conjunto
{p1 , p2, p3,.....................,pn} => (QP)
{p,, p2, p3,.....................,pn,Q} => P
6:REDUCCIN ENTRE CONSISTENCIA Y CONSECUENCIA LGICA
Sea:
=> Q
L(P)
Q L(P)
si y solo si (Q) es insatisfascible.
Para demostrar que una formula es valida, basta con demostrar que la negacin de
la formula es una contradiccin, por extensin, para demostrar que una formula es
consecuencia lgica de un conjunto de formulas, basta con demostrar que la
negacin de la formula (conclusin) unida al conjunto de formulas (base de
conocimientos) es una contradiccin, es decir, insatisfascible.
A este mecanismo de demostracin se lo denomina:
-Demostracin por refutacin.
-Demostracin por reduccin al absurdo.
3.7.4. SISTEMA DEDUCTIVO.El establecimiento del sistema deductivo, proporciona el mecanismo por el cual se tiene la
posibilidad de generar conclusiones o nueva informacin, a partir de cierta informacin
existente, a nivel simblico.
Fundamentalmente tiene el propsito de:
-
Determinar la validez de un argumento o deduccin a nivel simblico.
_____________________________________________________________________
38

_____________________________________________________________________________________
Una demostracin a nivel semntica, es decir por medio de tablas de verdad, si bien resulta
un mtodo sumamente sencillo, presenta algunas limitaciones, principalmente cuando el
numero de letras proposiconales es grande, por ejemplo; si se tiene n letras
proposicionales, se tendr 2n interpretaciones o valuaciones diferentes, es en este sentido
que la tabla de verdad puede ser muy grande (muchas filas), con 6 letras proposicionales se
tiene 64 posibles valuaciones, y se tiene que interpretar todas las formulas del lenguaje para
cada una de las valuaciones, este trabajo, si bien es sencillo es muy moroso y fcil de
cometer errores. Es por este motivo que se requiere un mecanismo de demostracin que
permita realizar la demostracin a nivel simblico, el sistema deductivo tiene este
propsito. Si bien el sistema deductivo permite demostrar la validez de una deduccin o de
un argumento a nivel simblico presenta algunas caractersticas:
-
Solo indica que un conjunto de frmulas es insatisfascible (contradiccin). Pero con

una aplicacin adecuada del Teorema de Reduccin entre Consistencia y
Consecuencia Lgica es posible demostrar la validez de un argumento.
No indica en que valuaciones o interpretaciones el argumento es valido o invalido.
FORMULACION DEL SISTEMA DEDUCTIVO.

Se parte de un conjunto de clusulas, es decir, opera sobre clusulas, por lo tanto, ya que el
lenguaje proposicional esta formado por formulas correctamente escritas, es necesario
desarrollar un proceso de transformacin de dichas formulas a clusulas. Para la obtencin
de clusulas se requiere algunos elementos importantes que a continuacin se detallan.
3.7.4.1. CONECTIVOS FUNCIONALMENTE COMPLETOS
Los conectivos funcionalmente completos es un sub conjunto de conectivos que permiten
representar al resto de conectivos. Se tiene principalmente dos subconjuntos:
a) ,
La negacin y la conjuncin permiten representar a las otras
conectivas, es decir a la disyuncin, implicacin y la doble implicacin
{; ;
}
_____________________________________________________________________
39

_____________________________________________________________________________________
b) ,
conectivas
La negacin y la disyuncin permiten representar al resto de las

{; ; }
De estos dos grupos de conectivas funcionalmente completos el mas importante para el

proceso transformacin de una formula a clusulas es el segundo grupo, es decir la (, )
Por ejemplo empleando el conjunto de coactivos funcionalmente completos : (, )
CONJUNCION.
(pq) => (pq)
=>(pq )
DISYUNCION.
(pq) => pq
DOBLE IMPLICACION.
(pq) => (pq) (qp)
3.7.4.2. FORMA NORMAL CONJUNTIVA (FNC).Toda frmula del lenguaje proposicional se puede representar en F.N.C.
Una frmula en F.N.C. esta constituida por una conjuncin de disyunciones de literales,
donde un literal es una letra proposicional o negacin de letra proposicional y se lo
representa de la siguiente manera:
i =1
j =1
IUl
ij
Donde lij es una letra proposicional o negacin de letra proposicional.
Es decir, desde el punto de vista matemtico se lo puede concebir como un producto de

sumas.
_____________________________________________________________________
40

_____________________________________________________________________________________
Ej: (3+2)*(5+3)*(3)*(2+3+6)
en matemticas: producto de sumas.
Pero desde el punto de vista de la lgica proposicional es un producto de sumas lgicas.

(pq) (q rt) (r s) (p)
Una formula es satisfascible si y solo si su equivalencia en F.N.C, tambin lo es. Es decir,
se cambia la representacin de la formula, pero las interpretaciones que la hacen verdadera
o que la satisfacen, tambin satisfacen a su equivalente en Forma Normal Conjuntiva.
El proceso de transformacin de una formula a FNC se lo realiza aplicando algunas
equivalencias lgicas y las leyes del algebra booleana.
Principios lgicos y leyes lgicas
En la lgica proposicional, todas las leyes lgicas son tautolgicas, es decir, formas
proposicionales, cuyos casos de sustitucin son siempre verdaderos. En la lgica de
predicados, como veremos en el prximo captulo, no son tautolgicas.
Las leyes lgicas son infinitas, a continuacin se proporciona la formulacin de las ms
importantes:
Distributividad de la conjuncin respecto de la disyuncin:
[ p ( q v r) ]
[( p q ) v ( p r )]
Distributividad de la disyuncin respecto de la conjuncin:

[ p v ( q r) ]
[( p v q ) ( p v r )]
Distributividad del condicional respecto de la disyuncin:

[p
( q v r) ]
[( p
q) v (p
r )]
_____________________________________________________________________
41

_____________________________________________________________________________________
Distributividad del condicional respecto de la conjuncin:

[p
( q r) ]
q) (p
[( p
r )]
De Morgan:
- (p q)
(-p v q)
-(p v q)
(-p q)
Definicin del condicional:

(p
q)
(-p v q)
(p
q)
-(p -q)
Definicin del bicondicional:

q) (q
(p
q)
(p
p)
(p
q)
(p q) v (-p -q)
Transposicin:
(p
q)
(-q
-p)
Exportacin:
[(p q)
r]
[p
(q
r)]
Idempotencia:
p
(p p)
(p v p)
Expansin Booleana:
p
p (q v -q)
p v (q -q)
Absorcin:
_____________________________________________________________________
42

_____________________________________________________________________________________
p (p v q))
p v (p q)
Ej: Obtener el equivalente en F.N.C. de la siguiente frmula:

(pq) (rt)
(p q) (rt)
(pq) (rt)
(p q) r t ...........== F.N.C.
3.7.4.3. FORMA NORMAL DISYUNTIVA (F.N.D).Una frmula en F:ND: esta constituida por una disyuncin de conjunciones de literales.
n
i=1
j=1
U I
l ij
Donde lij es una letra proposicional o negacin de letra
proposicional.
Ej:
(pqt) (rs) s .expresar en F.N.D.
(pq) (rt)
(pq) (r t)
(pq) (rt)
(prt) (qrt)esta en F.N.D.
3.7.4.4. FORMA CLAUSURAL O CLAUSAL.Es una frmula representada por clusulas.
CLAUSULA: Disyuncin de literales, donde un literal es un letra proposicional o negacin
de letra proposicional.
_____________________________________________________________________
43

_____________________________________________________________________________________
Tomando como referencia esta caracterstica una formula en Forma Normal Conjuntiva
(F.N.C) es una Conjuncin de clusulas.
l1 l2l3...................ln
CLAUSULA
donde li es una letra proposicional o negacin de letras proposicional.

F.N.C.:
C1 C2 C3.............Cn
Para simplificar la escritura de una formula en trminos de clusula se puede reemplazar el

smbolo de la conjuncin () por el smbolo de la coma (,):
C1 , C2 , C3 , ............. , Cn
Toda formula se puede representar por una o mas clusulas .Una frmula es consistente
(inconsistente) si y solo si, su equivalente es clusula tambin lo es. Por lo tanto, da lo
mismo trabajar con la formula original que trabajar con el conjunto de clusulas resultante
de la misma.
CLAUSULA ESPECIAL: CLAUSULA VACIA.Una clusula que no contiene literales es una clusula vaca y representa un contradiccin,
es decir, algo insatisfascible.
Clusula vaca : Clusula sin literales y se lo representa por:
Si
o por
n= 0
CONTRADICCIN
3.7.4.5. PRINCIPIO DE RESOLUCIN.-
_____________________________________________________________________
44

_____________________________________________________________________________________
Es un procedimiento de demostracin automtica por refutacin que lleva a cabo en una

nica operacin toda la variedad de procesos involucrados en el razonamiento. Es decir,
consiste en una nica regla de inferencia.
El principio de resolucin opera siempre sobre clusulas, por lo que cuando se utiliza para
demostrar la insatisfacibilidad de una formula, esta ha debido convertirse previamente a su
forma clausular.
La comprobacin de la insatisfacibilidad de un conjunto de clusulas mediante resolucin
consiste en la aplicacin reiterada de su nica regla de inferencia hasta encontrar la clusula
vaca.
Dos clusulas Cm y Cp se puede resolver para dar como resultado una clusula Cr
(Conclusin), pero Cm y Cp deben contener al menos el mismo literal en un caso negado y
en el otro sin negar y Cr , que es la clausula resolverte, contiene al resto de los literales,
excepto al literal que se encuentra en Cm y Cp que estaba negado y sin negar.
Por ejemplo si:
Cm = p q r
Cp = t q
Cr = p r t
Conclusin.
Si una valuacin o interpretacin satisface a Cm y Cp , entonces tambin satisface a Cr.

REGLA DE RESOLUCIN.-(Binaria).2 clusulas se pueden resolver para obtener una clusula resolvente.
Se selecciona dos clusulas Cm y Cp , llamadas clusulas padre, tales que una contenga un
literal R y la otra a R , y se resuelven entre si, obtenindose una nueva clusula Cr ,
llamada clusula resolvente o clusula hijo.
_____________________________________________________________________
45

_____________________________________________________________________________________
La clusula resolverte ser la disyuncin de todos los literales de ambas clusulas padre
con la excepcin del par R y R.
Si la clusula resolvente no es la clusula vaca, se adiciona al conjunto de clusulas
disponibles y se repite el proceso. En caso contrario, si se encuentra la clusula vaca,
significa que el conjunto de clusulas es insatisfascible, es decir, una contradiccin.
{C1 {R} }
Cr =
{ C2 {R} }
C1 C2
Tomar en cuenta: Las clusulas implcitamente estn conjuncionadas.

Cm : p q
Cm : p
Cp : p
Cr :
Cp : q
Cr : p
Como las clusulas estn relacionadas por una conjuncin, en realidad se tiene la siguiente
formula:
p p
lo que constituye una Contradiccin fija, siempre es Falso
MTODO GENERAL.La demostracin de la valides o invalides de una deduccin o de un argumento por medio
del principio de resolucin, se lleva a cabo por medio del Teorema de Reduccin entre
Consistencia y Consecuencia Lgica, ya que el principio de resolucin solo permite
demostrar que un conjunto de clusulas es insatisfascible o no, para lo cual se establece el
siguiente mtodo general:
Para demostrar que la deduccin => Q es valida:
1.
Incorporar (Q) a
{Q}
2.
Expresar {Q}
en clusulas
_____________________________________________________________________
46

_____________________________________________________________________________________
3.
Aplicar la regla de resolucin a *. Si se logra encontrar la clausula vacia,

entonces se habria demostrado que el conjunto de clausulas es una
contradiccin y por lo tanto el
argumento es valido, es decir Q es
consecuencia logica de (=>Q), en caso contrario el argumento no es

vlido, es decir, Q no es consecuencia logica de ( > Q).
Ej: Demostrar si el siguiente argumento es vlido.
= {(r p) (q s) , p , s}
Q = {q}
=> Q a demostrar:
Agregar la conclusin negada (q) a la base de conocimiento.
{(r p) (q s), p , s ,q}
Expresar las formulas como clusulas.
(r p) (q s) =
(r p) (q s)
(r p) (q s)
(r q s) (p q s)
De la formula se obtiene dos clausulas:
(r q s) , (p q s)
El conjunto de clausulas es: {r q s , p q s , p , s ,q}

Aplicando el principio de resolucin:
_____________________________________________________________________
47

_____________________________________________________________________________________
Como a partir del conjunto de clusulas resultante de {Q} se obtiene la clusula

vaca, por lo tanto el conjunto de clusulas es una contradiccin y por lo tanto Q es
consecuencia lgica de , es decir, el argumento es valido. Esta afirmacin se sustenta por
el teorema siguiente:
=> Q
si y solo si (Q) es insatisfascible.
ARBOL DE REFUTACIN.El rbol de refutacin muestra grficamente al conjunto de clusulas que intervienen en el
proceso de obtencin de la clusula vaca. Para el ejemplo anterior es el siguiente:
_____________________________________________________________________
48

_____________________________________________________________________________________
En los nodos terminales del rbol de refutacin solo se encuentran las clusulas iniciales
con las que se empieza la aplicacin del principio de resolucin.
Ejemplo: Demostrar la validez del siguiente argumento :

No pongo la calefaccin elctrica solo si tengo gas. No consumo lea a menos que el
petrleo sea caro o no ponga calefaccin elctrica. El petrleo no es caro. Consumo lea a
menos que tengo fri. Por lo tanto solo si tengo fri tengo gas.
p: Yo pongo la calefaccin electrica.
q: Yo tengo gas.
r : Yo consumo lea.
s : El petrleo es caro.
t : Yo tengo fro.
2: formulas del lenguaje:
= {q p , (s p) r , s , t r}
Q = tq
_____________________________________________________________________
49

_____________________________________________________________________________________
3. U { Q}
{q p , (s p) r , s , t r , (tq)}
4. clausulas:
{q p , s p r , s , t r , t , q}
5. Resolucion:
Como a partir del conjunto de clusulas se logra obtener la clusula vaca, por lo tanto, el
conjunto de clusulas es una contradiccin, entonces el conjunto de formulas original
tambin es una contradiccin, por lo tanto se establece que el argumento es valido.
_____________________________________________________________________
50

CAP3

Cargado por

Copyright:

Formatos disponibles

CAP3

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

CAP3

Cargado por

Copyright:

Formatos disponibles

SIS 1205 A ANALISIS DISCRETO

SIS 1205 A ANALISIS DISCRETO

3.2. USO DEL LENGUAJE.

SIS 1205 A ANALISIS DISCRETO

SIS 1205 A ANALISIS DISCRETO

emite rdenes sin pretender comunicar informacin alguna ni

alguna emocin particular. Lo que se busca es motivar o causar una accin.

SIS 1205 A ANALISIS DISCRETO

correspondencias lxicas son establecidas explcitamente, que.el vocabulario es restringido

en el proceso de formalizacin del lenguaje natural es la

SIS 1205 A ANALISIS DISCRETO

formulacin de un lenguaje formal que se debe emplear

para el estudio de los

enfoca el estudio de la formulacin de un lenguaje formal

SIS 1205 A ANALISIS DISCRETO

Se trata de una proposicin compuesta por tres proposiciones tales como:

El lgebra es una disciplina matemtica.

La geometra es una disciplina matemtica

Y la simbolizacin correspondiente a las mismas ser mediante las letras proposicionales

3.5.1. TIPOS DE PROPOSICIONES.

SIS 1205 A ANALISIS DISCRETO

b) De atribucin de propiedades a sujetos especficos.- Este tipo de proposiciones

Juan juega futbol.

c) De Relacin: Relacionan sujetos u objetos, se debe tener cuidado en que la

Juan y Pedro son primos.

Juan esta sentado entre luis y Jaime.

Melgar Y Vallejo son dos grandes hombres.

Juan sabe francs Y ingls.

Juan se casa O termina su noviazgo.

Si es estudioso, ENTONCES aprobar el examen.

Manuel ir al estadio SI, Y SLO SI, juega San Jos.

NO es cierto que Luis Y Ana sean buenos estudiantes.

SIS 1205 A ANALISIS DISCRETO

EXPRESION EN LENGUAJE NATURAL

SIS 1205 A ANALISIS DISCRETO

3.7. DEFINICIN FORMAL DEL LENGUAJE PROPOSICIONAL.

SIS 1205 A ANALISIS DISCRETO

3. Smbolos de parntesis o de puntuacin: para el establecimiento de subestructuras

p : Juan juega futbol.

Los conjuntos 2. y 3. son comunes para todo lenguaje proposicional, es decir no

El conjunto 1. varia de acuerdo al fenmeno o razonamiento que se esta modelando,

Como el conjunto P es variable, por lo tanto el lenguaje proposicional a desarrollar esta en

3.7.2. SINTAXIS DEL LENGUAJE PROPOSICIONAL:

SIS 1205 A ANALISIS DISCRETO

la simple combinacin de proposiciones y conectivas no garantiza la obtencin de frases

(formula atmica) por la regla 1.

SIS 1205 A ANALISIS DISCRETO

Locke y Hume son representantes del empirismo ingls

Hume es representante del empirismo ingls

Descartes es racionalista, pero Hume es empirista

SIS 1205 A ANALISIS DISCRETO

A menos que se tomen medidas, el Riachuelo seguir contaminado.

Las becas de investigacin son para Francia y/o Alemania

Un ejemplo de disyuncin exclusiva:

La tarifa area incluye un viaje de cabotaje o a Bariloche o a cataratas

SIS 1205 A ANALISIS DISCRETO

O bien descartes es racionalista, o bien es empirista

Si los pasajes se reservan con tiempo, viajaremos en primera.

Viajaremos en primera, Si los pasajes se reservan con tiempo.