Capítulo 2 Proposición

• Lógica proposicional ,, Un enunciado es una expresión del lenguaje.

~ Una proposición es un enunciado que

,, Lóg ica de predicados
puede ser calificado o de verdadero (V)
o de Falso (F).

" Valores de verdad : L = {V,F}.

Operadores Lógicos Tablas de los operadores

Operador Símbolo Compuesta

y /\ Conjunción vv V V V V F
o (y/o) V Disyunción (Inclusiva) V F F V V F F F
o (o ..o) 6 Disyunción exclusiva F V F V V V F V
entonces • Condicional F F F F F V V V
si y sólo si +-), Bicondicional
no Negación

La Condicional La Condicional

En la condicional p • q, La condicional p • q se puede leer:

p es el antecedente y q es el consecuente.
" p entonces q .
(p• q , no es conmutativa)
,, p sólo si q .

~ q si p.

15
La Condicional Tautología

Si la condicional es p • q Una tautología es una proposición compuesta

que es verdadera, cualesquiera sean los
,~ su recíproca es q • p,
valores de verdad de las proposiciones
componentes.
• su contraria es - p • -q ,

( Una tautología se representa por: 1 )

"' su contrarecíproca es -q • -p .

Ejemplo Contradicción

(p v -p) es una tautologia.

Una contradicción es una proposición
Demostración: compuesta que es falsa, cualesquiera sean
los valores de verdad de las proposiciones
o componentes.

( Una contradicción se representa por: O )

Ejemplo Proposiciones Equivalentes

(p "-p) es una contradicción.

Dos proposiciones p y q son equivalentes,
Demostración: si la proposición p ~ q es una tauto logía.
p (p ¡\ ~p)
O (pes equivalente a q se representa por: p"' q )

16
 Ejemplo Leyes Lógicas

{ p • q } = { -q • -p } 1) Conmutativa: p /\ q = q /\ p ,
Dem ostración: p v q=q v p.
p q ( p • q } tt ( -q • -p ) 2) Identidad: p /\ 1 = p ,
oo O1 O 1 1 1 1 p v 0aap .
3) Complemento: p /\ -p = O ,
o1 o1 1 o 1 1
p v -p = 1 .
1 O 1 OO 1 o o
4) Distributiva: p /\ (q v r) = (p /\ q} v (p /\ r} ,
1 1 1 1 1 o 1o p V (q /\ r} = (p V q) /\ (p V r} .
Entonces: ( p • q } tt ( -q • -p ) = 1

Leyes Lógicas+ Leyes Lógicas ++

1} ldempotencia: P /\ P=P . P V P=P- 1)Condicional: p• q = -p v q .
2) Acotamiento: p /\ 0 :a 0, pv1 aa1 . 2) Bicondici onal: p tt q = {p • q) /\ {q • p) .
3) Absorción: p /\ (p V q) = p • 3) Disyunción Exclusiva : p t,. q = (p v q) /\ - {p /\ q) .
p V (p /\ q) = p .
4) Asociativa: 4)Contraposición: p • q = -q • -p.
p /\ {q /\ r) = (p /\ q) /\ r ,
p V (q V r) = {p V q} V r . S)Negación de la Condicional: -{p • q)= p /\ -q.
5) Involución: -(-p) = p . 6)Negación de la Bicondicional: -{p tt q) = p t,. q.
6) Opuesto: -1 = O , -O= 1 . ?)Absorción generalizada: p /\ (-p v q) = p /\ q
7) De Margan: -(p /\ q) = -p V -q • p V (-p /\ q) = p V q.
-{p V q) = -p /\ -q .

Ejemplo La Implicación

Simplificar:
{ p /\ ( q • q ) ) /\ { -p • ( q /\ -p ) ) /\ { r • p ) La proposición p implica la proposición q ,
Solución :
si la proposición p • q es una tautología .
{ P /\ ( q • q ) ) /\ { -p • ( q /\ -p ) ) /\ { r • P ) -
{ p /\ { -q V q ) ) /\ ( p V ( q /\ -p ) ) /\ { -r V p ) =
( p implica q se representa por: p • q )
( p /\ 1 ) /\ ( p V q ) /\ ( - r V p ) -
p /\ ( p V (q /\ -r)) -
p

17
 La Implicación Ejemplo

(p /\ q)=>P
si p implica q , decimos que : Demostración 1:
p q (p A q) • p
o o 000 1 o
p es suficiente para q .
r:,
O 1 001 a
o 1 ao 1
.. q es necesario para p. 1 1 111

Inferencias lógicas

Demostración 2: 1)Adición: p => (p V q) .

2) Simplificación : (p /\ q) => p .
(p A q) • p =
3)Modus ponens: ((p • q) /\ p) => q .
~( p /\ q) V p "'
(-p V -q) V p = 4)Modus tollens : ((p • q) /\ -q) => -p .
( ~p V p) V ~q - 5)Silogismo disyuntivo: ((p V q) /\ -p) => q.
1 V -q - 6)Silogismo hipotético :
1 ((p • q) /\ (q • r)) => (p • r) .

Consecuencia lógica Ejemplo

La proposición q es consecuencia lóg ica

de la propos ición p, si p => q .
Ya que: ( p /\ q) => p
(q es consecuencia lógica de p
se representa por: q e: p )

18
 Teorema (Reducción al absurdo) Predicados

q <= p si y sólo si (p "-q) = O . Sean X1 , ... , Xn conjuntos no vacíos

y sea O e X1 X ... X Xn .
(La proposición q es consecuencia lógica
Un predicado p definido en O
de la proposiciones p , si y sól~ si
es una función de O en L = { V , F} .
la proposición (p "-q) es una contradicción)
( p:D • L)

Predicados Ejemplo

Si p es un predicado en D y a E O , Si o = z+ y p(x): x es par,

entonces p(a) es una proposición . entonces:
p(4) es V
p(3) es F

Ejemplo Operaciones con predicados

Dados los predicados p y q ,

Si O = Z x Z y p(x,y): x < y , se definen los predicados:
entonces: 1) (-p)(x) = -p(x) .
p(2,3) es V 2) (p " q)(x) = p(x) " q(x) .
3) (p v q)(x) = p(x) v q(x) .
p(3,2) es F
4) (p ó. q)(x) = p(x) ó. q(x) .
5) (p • q)(x) = p(x) • q(x) .
6) (p s--+ q)(x) = p(x ) t t q(x) .

19
 Cuantificador Universal Cuantificador Existencial

El cuantificador universal es la expresión El cuantificador existencial es la expresión

"para todo" que se representa por 'i . "existe" que se representa por 3 .

Si p(x) es un predicado definido en D , Si p(x) es un predicado definido en D ,

la expresión '</ x e D : p(x) , es una proposición. la expresión 3 xe D : p(x) , es una proposición.

Ejemplo Leyes de Predicados

1) 'e/ x e z+: x > O, es verdadera Sean p(x) y q(x) dos predicados:

2) 'el x e Z : x > O, es falsa 1) -('</ x : p(x)) = 3 x : -p(x) .

2) -(3 x : p(x)) = 'e/ x : -p(x) .
3) 'i x: (p(x) /\ q(x)) = ('i x: p(x)) /\ ('e/ x: q(x)) .
3) 3 x e Z: x + 2 = 2, es verdadera 4) 3 x: (p(x) y q(x)) = (3 x: p(x)) v (3 x: q(x)) .
5) 3 x: (p(x) /\ q(x)) • (3 x: p(x)) /\ (3 x: q(x)) .
4) 3 x e z+: x + 2 = 2, es falsa 6) 'e/ x: (p(x) v q(x)) e('</ x: p(x)) v ('e/ x: q(x)) .

Ejemplo Teorema (Particularización)

1) -('c/xe Z: x > O) = 3xeZ: X:;; O Sea p : D • L un predicado y a e D ,

entonces p(a) es una consecuencia lógica de
2) -(3xeZ: x+2 = 2) = 'ixe Z: x+2 a= 2 ('e/ x e D : p(x)) .

3) -(3xeZ: x >O/\ x+2 = 2) = 'c/xeZ: x:;; O v x+2 a= 2

4) - ('c/xe Z: x > O • x+ 2 = 2) ·= 3xeZ: x >O/\ x+2 a= 2

20
 Teorema (Generalización) Variables ligadas y variables libres

Si p : O • L es un pred icado
Sea p : O • L un predicado y a E O , en las n variables X 1 , ... , Xn , entonces
entonces (3 x E O : p(x)) \/ xk : p(X1 , ... , Xnl 1/
es una consecuencia lógica de p(a). 3 xk : p(X1 ' ... ' Xnl
son predicados en las (n-1) variables que no son Xk.

En estos casos se dice que la variable Xk está ligada

y que las variables restantes son libres.

Ejemplo

Si O= Z xZ:
1) ( x + y = O ) y ( x * y = O ), son predicados en 4) \/ x, 3 y: x +y= O, es una proposición verdadera .
las variables x e y.

5) 3 y,\/ x: x +y= O, es una proposición falsa.

2) \/ x: x + y= O, es un predicado en la variab le y,
la variable x está ligada y la variable y está libre.
6) 3 y, \/ x: x * y = O, es una proposición verdadera.
3) 3 y: x + y= O, es un predicado en la variable x,
la variable y está ligada y la variable x está libre.

Números naturales (IN) Axioma de inducción

Axiomas:
1) IN es un conjunto totalmente ordenado. Si A e IN es ta l que:
2) Existe una función sucesor S : IN • IN 1) Ü E A.
donde S(n) es el número que le sigue a n
2) n E A• (n+ 1) E A.
en el orden total.
Entonces A= IN.
3) Existe un único O E IN tal que: O .; S(IN),
donde S (IN) = { S(a) / a E IN} .

21
Definiciones por inducción Ejemplo

Definir: n!, V n 2: O.
Si n y n0 e IN.
1) O! = 1
Para definir D(n) V n 2: n0 :

1) Se define D(n 0 ) . 2} (n+1)! = (n+1) .n!, n?: O

2) Supuesto definido D(n) V n ?: n0 ,

se define D(n+1 ).

Ejemplo Demostraciones por inducción

n

Definir: ¿ak, V n ~ l Si n y n0 E IN.

k=I

Para demostrar P(n) V n ?: n0 :

1) Se demuestra P(n 0 ) .
n+1 n
2) Supuesto demostrado P(n) V n 2: n0
¿ = L Qk + Qn+I
,
2) Qk
se demuestra P(n+1 ).
k=I k=I

Ejemplo

Demostrar: I k = (n)(n + l), V n ~ l 2) I, k = (n)(n + 1) •

k=I 2 k•I 2

i)+(n+l) (n)(n+l) +(n+l) •

1) k=I 2

f k = (n + I )( n + I + 1)
k=I 2

22
 Programa lógico (P.L.) Consulta

Un hecho es una proposición no compuesta. Una consulta es una proposición.

Una regla es una proposición de la forma En las consultas las variables son cuantificadas
existencialmente.
q f- (P1 /\ ·· · /\ Pnl ·
En los hechos y en las reglas las variables son Si se ingresa una consu lta después de un programa
lógico, la salida será "si" en caso de que la consulta
cuantificadas universalmente.
sea una consecuencia lógica de programa, y la
salida será "no" en caso contrario.
Un programa lógico es un conjunto de hechos y
Si la consulta posee variables, la salida indicará
reglas. todas las soluciones.

Ejemplo

/* Hecho: progenitor (x, y) = x es progenitor de y •¡ /* Hecho: varón (x) = x es varón */

progenitor Qosé, roberto) . varón Qosé) .
progenitor (rosa, roberto). varón (roberto) .
progenitor Qosé, juana) . varón Qaime) .
progenitor (rosa, juana) . /* Hecho: mujer (x) - x es mujer */
progenitor (roberto, ana) . mujer (rosa).
progenitor (ana, jaime) . mujer {ana).
mujer uuana).

/* Consultas y salidas */
/* Regla: padre (x, y) •¡
?: progeni(or Uosé, juana).
padre (x, y) +--- progenitor (x, y), varón (x) .
Si.
?: padre Uosé, roberto) .
?: progenitor Uosé, jaime).
Si.
No .
?: padre Qosé, x).
?: progenitor Qosé, x).
Si.
Si.
x = roberto.
x = roberto.
x = juana.
x = juana.
?: padre (rosa, roberto). -
?: progenitor Uosé, roberto), varón Uosé) .
No.

23
 /* más reglas : •¡
abuelo (x, y) +--
padre (x, z), progenitor (z, y) .
madre (x, y) +--
abuela (x, y) +--
progenitor (x, y), mujer (x) .
madre (x, z), progenitor (z, y) .
hijo (x, y) +--
progenitor (y, x), nieto (x, y) +--
varón (x) . abuelo (y, x), varón (x) .
hija (X, y) +-- nieto (x,y) +--
progenitor {y, x), mujer (x) . abuela (y, x), varón (x) .

nieta (x, y) +-- tío (x, y) ~

abuelo (y, x), mujer (x) . progenitor (z, y), hermanos (x, z), varón (x).
nieta (x, y) +- tía (x, y) ~
abuela (y, x), mujer (x) . progenitor (z, y), hermanos (x, z), mujer (x).
hermanos (x, y) +- antepasado (x, y) ~
progenitor (z, x), progenitor (z, y), progenitor (x, z), antepasado (z, y).
not (misma-persona (x, y)) . antepasado (x, y) ~
misma-persona (x, x) . progenitor (x, y) .

P.L. natural Ejemplo

/* natural(x) - x elN */ ? natural(3).

Si.
natural(O).
natural(S(x)) +- natural(x). ? natural(0.5) .
No.

24
P.L igual y diferente Ejemplo

/* igual{x,y) = x = y */ ? igual(3,3).
Si.
? igual(3,2).
igual(x,x) . No.
? igual(x,3).
Si
/* diferente(x,y) = x * y */ X= 3.
? diferente(3,3).
diferente(x,y) +- not(igual(x,y)) . No.

P.L. menor y menor-igual Ejemplo

/* menor(x,y) = x < y */ ? menor(2,4).

Si.
menor(S(x),S(y)) +- menor(x,y).
menor(O,S(x)). ? menor(2,2).
No .
/* menor-igual(x,y) = x :S y */

menor-igual(S(x),S(y)) +- menor-igual(x,y). ? menor-igual(2,2).

menor-igual(O,x). Si.

P.L. menor-igual2 y diferente2 P.L. mayor y mayor-igual

/* menor-igual2(x,y) = x :S y */ /* mayor(x,y) = x > y */

mayor(x,y) +- menor(y,x).
menor-igual2(x,y) +- menor(x,y). /* mayor-igual(x,y) = x 2 y */
menor-igual2(x,y) +- igual(x,y). mayor-igual(x,y) +- menor-igual(y,x).
/* mayor2(x,y) = x > y */
/* diferente2(x,y) = x st y */ mayor2(x,y) +- not(menor-igual(x,y)).
/* mayor-igual2(x,y) = x 2 y */
diferente2(x,y) +- menor(x,y).
mayor-igual2(x,y) +- not(menor(x,y)).
diferente2(x,y) +- menor(y,x).

25
P.L. suma y resta Ejemplo

? suma(2,3,5) .
/* suma(x,y,z) = z := x + y */
Si.
? suma(2,3,6) .
suma(S(x),y,S(z)) ~ suma(x,y,z).
suma(O,x,x) . No.
? suma(2,3,x).
Si
/* resta(x,y,z) = z:= x - y */ X= 5.
resta(x,y,z) ~ suma(z,y,x).

P.L. producto

? suma(x,3,5) .
Si /* producto(x,y,z) = z:= x * y */
X= 2.
producto(S(x),y,z) ~ producto(x,y, t),
? Resta(5 ,3,x). suma(t,y,z).
Si producto(O;x,O) .
X= 2.

Ejemplo P.L. div

? producto(2,3,6).
Si. /* div(x,y,z) = z :=(x DIV y) */
? producto(2,3, 7).
No. div(x,y,S(z)) ~ resta(x,y,1),
? producto(2,3,x). div(t,y,z).
Si div(x,y,O) ~ menor(x,y).
X= 6.

26
Ejemplo P.L. mod

? div(17,5,3). /* mod(x,y,z) = z :=(x MOD y) */

Si.
mod(x,y,z) ~ resta(x,y,t) ,
? div(17,5,x). mod(t,y,z).
Si mod(x,y,x) ~ menor(x,y) .
X= 3.

Ejemplo P.L. potencia

? mod(17,5,2) . /* potencia(x,y,z) = z:= xY */

Si.
potencia(x,S(y),z) ~ potencia(x,y,t),
? mod(17,5,x) . producto(x,t,z).
Si potencia(S(x),O, S(O)).
X= 2. potencia(O,S(y),O).

Ejemplo P.L. factorial

? potencia(2,4, 16). /* factorial(x,y) = y:=x! */

Si.
factorial(S(x) ,y) ~ factorial( x, t) ,
? potencia(2,4,x). producto(S(x),t,y) .
Si factorial(O , S(O) ).
X= 16.

27
Ejemplo Listas

Una lista es la lista vacía o

? factorial(4,24) . una lista es una colección ordenada de
Si. objetos donde se reconocen dos partes, la
cabeza de la lista que es el pri mer elemento
? factoriaI(4,x). de la lista y la cola de la lista formada por el
Si resto de los elementos.
x= 24.

Listas P.L. lista

Sea L una lista :

lista ( [ ] ).
1) Si L es la lista vacía, lista([xlxs]) ~ lista(xs).
Representamos L=[ ].

/*
2) Si L no es la lista vacía,
Una lista es la lista vacía o
representamos L = [x J xs] ,
donde x es la cabeza y xs la cola. una lista es un elemento seguido de una lista
*/

P.L. añade Ejemplo

/* añade(x, L 1,L2) = L2 = [x L 1 ]
J •¡ ? añade(S,[4,7,2], [5,4,7,2]).
Si.
añade(x,xs,[x ¡ xs]).
? añade(S,[4,7,2], L).
Si
L = (5,4,7,2].

28
 P.L. pertenece Ejemplo

? pertenece(5,(3,7,5,4,2]).
/* pertenece(x,L) = x E L */ Si.
? pertenece(5,(3,7,4,2]).
No.
pertenece(x,(y ¡ ys]) +- pertenece(x,ys).
? pertenece(x,(3,7,4]).
pertenece(x,(x I xs]) .
Si
x=3
x=7
X= 4.

P.L. longitud Ejemplo

/* longitud(L,n) = n:= l!L!I, ? longitud([2,5, 7],3).

donde l!L!I es el número de elementos de L */ Si.

longitud([x I xs],S(n)) +- longitud (xs,n). ? longitud((2,5,7],x).

longitud([ ],O). Si
X= 3. ·

P.L. concatena Ejemplo

/* concatena(L 1,L2,L3) = L3 = L 1L2 */ ? concatena([2,9, 1],(5,2],[2,9, 1,5,2]).

Si.
concatena((x ¡ xs],L,[x ¡ ys]) +- concatena(xs,L,ys).
concatena(( ], L ,L). ? concatena([2,9, 1],(5,2],l).
Si
L = [2 ,9, 1,5,2].

29
 P.L. invierte Ejemplo

/* invierte(L 1,L2) = L2 es la lista L 1 invertida •¡ ? invierte([3,4,7],[7,4,3]).

Si.
invierte([x I xs],L) ~ invierte(xs,ts),
concatena(ts,[x], L). ? invierte([3,4,7],L) .
invierte([ ],[ ]). Si
L = [7,4,3].

P.L. posición Ejemplo

/* posición(x,L,n) = n:= la posición del elemento x ? posición(S,[7,4,5,9, 1],3).

en la lista L */ Si.

posición(x,[y I ys],S(n)) ~ posición(x,ys,n). ? posición(S ,[7,4,5,9, 1),x).

posición(x,[x ¡ xs],S(O}}. Si
X= 3.

P.L. menor-elemento

? posición(S,[7,5,9, 1,9,5, 1],x). /* menor-elemento(L,x) x := el menor elemento

Si en la lista L */
x=2
X= 6.
menor-elemento([x ¡ xs],x) ~ menor-elemento(xs,y} ,
menor(x,y}.
? posición(x,[7,4,5,9],3).
Si
menor-elemento([x ¡ xs),y} ~ menor-elemento(xs ,y),

X= 5. not(menor (x,y}).
menor-elemento([ x ),x).

30
 Ejemplo Matrices

? menor-elemento([S,3.7,2,8],2).
Si. Una matriz de dimensión m x n es una lista,
de m listas, de longitud n cada una de ellas.
? menor-elemento([5,3, 7,2,8],x) .
Si
X= 2.

P.L suma-filas y suma-matrices Ejemplo

*/ suma-filas(L 1,L2,L3) = L3 := L1 + L2 * /
suma-filas ([x / xs],[y / ys],[z I zsl) -f- suma(x, y, z ), ? suma-filas([2,5 ,3],[1,0,4],[3,5,7]).
suma-filas(xs ,ys,zs). Si.
suma-filas([ ],[ ],[ ]).
*/ suma-matrices(A ,B,C) _ C :=A+ 8 • /
? suma-filas([2,5 ,3],[1,0,4],L).
suma-matrices ([xs I As] ,[ys I Bs],[zs / Cs]) -f- Si
suma-filas(xs,ys ,zs),
L = [3 ,5,7].
suma-matrices (As ,Bs ,Cs).
suma-matrices([ ] ,[ ],[ ]).

P. L escalarxfila y escalarxmat riz

/* escalarxfila(x,L 1,L2) = L2 := x .L 1 */
? suma-matrices([[4,3],[2 ,0]],[[1,5],[1,3]], [[5,8],[3,3]]). escalarxfila (x,[y / ys] ,[z I zsl) -f- producto (x, y, z),
escalarxfila(x,ys,zs ).
Si.
escalarxfila(x,[ ],[ ]) .
/* escalarxmatriz (x,A,B) - B := x.A */
? suma-matrices([ [4,3] , [2,0]] , [ [1 ,5] , [1,3]] , L) .
escalarxmatriz(x,[ys/A],[zs/8]) -f-
Si
escalarxfila (x,ys,zs ),
L = [ [5,8] , [3,3] ]. esca larxmatriz(x,A,B).
esca larxmatriz (x, [ ],[ ]) .

31
 Ejemplo

? escalarxfila( 4,[3,8,2],[12,32,8]). ? escalarxmatriz(3, [ [4,3] , [2,0]], [ [12,9] , [6,0]] ).

Si. Si.

? escalarxfila(4,[3,8,2],L). ? escalarxmatriz(3, [ [4,3] , [2,0] ] , L).

Si Si
L = [12,32,8] . L = [ [12,9], [6,0]].

32