Se define el valor de verdad de una fórmula θ bajo I como una función valuación vI(θ)

de la siguiente manera:
a. si θ es una variable poposicional entonces el valor de verdad de θ, vI(θ), es la
imagen (0 o 1) que le corresponde a la variable proposicional bajo la
interpretación I.
b. Si θ es de la forma ¬Φ entonces vI(θ) = 1 si vI(Φ) = 0 y vI(θ) = 0 si vI(Φ) = 1.
c. Si θ es de la forma (θ ^ Φ) entonces VI (θ) = 1 si VI
Sea θ una fórmula y sea I una interpretación. Se dice que θ es verdadera bajo I si su
valor de verdad es 1. Cuando θ es verdad bajo I, se dice que I satisface a θ; o que θ es
satisfacible pro I. Escribiremos que I satisface a θ como I |= θ. Se dice que θ es falsa
bajo I si su valor de verdad es 0. Cuando θ es falsa bajo I, se dice que I no satisface a θ.
Una fórmula θ se llama tautología si todas las interpretaciones son modelos para la
fórmula. Se utiliza el Símbolo T0 para denotar cualquier tautología. Cuando una fórmula
es tautológica vamos a anotar |= θ.
Una fórmula se llama contradicción, insatisfacible o inconsistente si es falsa para todas
las interpretaciones posibles. Se utiliza F0 para designar toda contradicción. Una
contradicción no tiene interpretaciones que sean modelos.
Una proposición lógica que no es una tautología ni es una contradicción se denomina
contingencia. Una contingencia es satisfacible, pero no es tautología. Esto significa que
existirá alguna interpretación I para la cual VI(θ) = 1 y alguna interpretación J donde
VJ(θ) = 0.
El método más directo para determinar si una fórmula es una tautología es mediante su
tabla de verdad. Si todas sus filas producen “1” (“0”) en la última columna se trata de
una tautología; si algunas filas producen “1” mientras que otras producen “0” se trata de
una contingencia.
P Q ¬p Θ = ¬(p ^ q) Φ = (¬(p ^ q) v q) ρ = (p ^ ¬p) ω = (p v
¬q)
0 0 1 1 1 0 1
0 1 1 1 1 0 1
1 0 0 1 1 0 1
1 1 0 0 1 0 1
Contingencia Tautología Contradicción Tautología

Un conjunto de fórmulas se dice satisfacible si existe una valuación que satisfaga a

todas las fórmulas del conjunto e insatisfacible en caso contrario.

La implicación y la consecuencia lógica

Una fórmula Φ es consecuencia lógica de un conjunto S de fórmulas, si la verdad de
todas las fórmulas de S implica la verdad de Φ.

Sea S un conjunto de fórmulas y Φ una fórmula:

- Se dice que Φ es una consecuencia lógica de S si toda interpretación que es un

modelo de S es también un modelo para Φ. Podemos escribir esto como S |= Φ.
A veces diremos que S implica lógicamente a Φ o simplemente que S implica a
Φ.
- Dicho de otra manera, Φ es consecuencia lógica de S si toda interpretación I que
hace verdadera a todas las fórmulas S, también hace verdadera a Φ.
- Es decir, si v(θ) = 1 para toda θ ϵ S, entonces v(Φ) = 1.
 - Indicaremos Con S = {Φ ϵ Form / S |= Φ} al conjunto de las consecuencias de S.
El conjunto Con S puede ser infinito.
- En particular si S = {θ} podemos escribir θ |= Φ o bien θ → Φ y leemos θ
implica (lógicamente) a Φ, en cualquier caso.

Sean S1 y S2 dos conjuntos de fórmulas. S2 es consecuencia lógica de S1 y escribimos S1

|= S2 si S1 |= Φ para toda fórmula Φ ϵ S2. También podemos decir que S1, implica
(lógicamente) a S2.

Teorema de la Deducción
Sea S un conjunto de fórmulas y θ y Φ fórmulas arbitrarias. Luego S U {θ} |= Φ si y sólo
si S |= (θ → Φ). También podemos enunciarlo así: Φ ϵ Con (S U {θ}) si y solo si (θ →
Φ) ϵ Con S.

Teorema 1.3
Para todo conjunto de fórmulas S, S C Form y para toda formula θ, se tiene que S |= θ si y
solo si S U {¬ θ} es insatisfacible. Las interpretaciones que satisfagan a “S”, no
satisfacen a (¬θ) por lo tanto es insatisfacible.

La equivalencia Lógica
Dos fórmulas θ y Φ son lógicamente equivalentes si tienen los mismo modelos, es decir,
si para toda interpretación I, los valores de verdad coinciden; es decir VI (θ) = VI (Φ) para
toda interpretación.

Decir que dos fórmulas θ y Φ son lógicamente equivalentes si y solo se verifican θ |= Φ y

Φ |= θ.

Si θ y Φ son fórmulas arbitrarias, entonces θ ↔ Φ si y solo si |= (θ ↔ Φ). Consecuencia

lógica del vacío.

Leyes – Tabla
1 ¬¬ θ ↔ θ Ley de la doble negación o
Ley de involución

2 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes de Morgan

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)

3 (θ v (Φ ) ↔ (θ ^ Φ) v ρ) Leyes conmutativas

(θ ^ (Φ ) ↔ (θ v Φ) ^ ρ)

4 (θ v Φ) ↔ (θ ^ Φ) Leyes asociativas

(θ ^ Φ) ↔ (θ v Φ)

5 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes distributivas

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)

6 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes idempotentes

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)
 7 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes de identidad

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)

8 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes inversas

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)

9 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes de dominación

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)

10 ¬ (θ v Φ) ↔ (¬θ ^ ¬Φ) Leyes de absorción

¬ (θ ^ Φ) ↔ (¬θ v ¬ Φ)

Redes de conmutación

Una red de conmutación esta formada por cables e interruptores que conectan dos
terminales T1 y T2. Si un interruptor está abierto, entonces no pasa la corriente por él y
lo indicaremos con un “0”, mientras que un “1” indicará que el interruptor está cerrado
y por consiguiente pasa la corriente por él.

Predicados, relaciones y cuantificadores. Primer acercamiento a la LPO.

En las ciencias de la computación aparecen muy a menudo expresiones relacionales o

predicados del tipo “x < 4”, “y2 > 9”, “| x | > 0”, “x < 0 mientras que y > 0”, “x > y”,
“ABC es triángulo rectángulo”, “María es hermana de José”. Tales expresiones
relacionales o predicados expresan propiedades de un objeto o relaciones entre objetos.
Se convierten en proposiciones lógicas que tienen valores de verdad 0 o 1 cuando se
reemplaza a las variables x, y por los valores constantes o cuando se cuantifican.
Tomando x = 2 en “x < 4” obtenemos la proposición verdadera “2 < 4” mientras que si
x = 5, “5 < 4” es una proposición falsa; “todo x es menor o igual que 4” es falsa,
mientras que “existe un número real cuyo cuadrado es mayor o igual que 9” es
verdadera.

Estas expresiones relacionales juegan un papel importante en estructuras de decisión

que pueden aparecer en algunos lenguajes de programación y se pueden manipular
como proposiciones lógicas, aunque no lo sean.

¿Cómo se obtienen proposiciones?

Forma 1: Sustitución

La variable se reemplaza en el predicado por una constante perteneciente a un dominio

o universo dado. Esto significa que la elección de la constante es importante, y que
debemos atender además al dominio o universo al cual pertenece.

Las Expresiones Relacionales o Predicados se operan lógicamente como si fuesen

proposiciones, obteniéndose nuevas expresiones relacionales. Es decir, si P(x) y Q(x)
son expresiones relacionales, también lo son:
 ¬P(x); Q(x) ^ P(x); Q(x) v P(x) ; P(x) → Q(x)

Por sustitución, estas nuevas expresiones relacionales también se convierten en

proposiciones cuyos valores de verdad dependen de los valores de verdad de las
proposiciones que las componen. Es decir, algunas sustituciones producen
proposiciones verdaderas y otros reemplazos producen proposiciones falsas.

Forma 2: Cuantificación

Otra forma de obtener proposiciones a partir de expresiones relacionales es

introduciendo el uso de símbolos, denominados cuantificadores.

“Para algún x”, “Para algunos x, y”, “Para todo x”, “Para todos x, y” aparecen como
cuantificadores de las expresiones proposicionales. Los cuantificadores son: El
existencial “Para algún x” y el universal “Para todo x”.

Cuantificador existencial:

Se escribe “Ǝx” y se lee de distintas maneras: “Para algún x se verifica”, “Existe un x tal
que” o “Para al menos un x se verifica”.

EJ, si en la oración “Existen alumnos que disfrutan estudiando”, representamos a un

alumno con la letra x y con P(x) a “x disfruta estudiando”, podemos escribir esta
oración en forma simbólica usando el cuantificador existencial de la siguiente forma:
“Ǝx P(x)”.

Cuantificador Universal:

Se escribe “∀ x” y se lee. “Para todo x se verifica”, “Para cada x se verifica” o “Para

cualquier x se verifica”.

EJ, en la oración “Todos los ingresantes de la Universidad deben completar su ficha

médica”, representamos a un ingresante con la letra x, al dominio (Universidad) con la
letra U y con R(x): “x debe completar su ficha médica”, podemos escribir esta oración
en forma simbólica usando el cuantificador universal y expresarla como “∀ x (x ϵ U →
R(x))”. Cuando el dominio se define previamente, como en este caso, podemos escribir
“∀ x R(x)”
Las expresiones en dos variables “Ǝx Ǝy S(x, y)” se lee “Para algunos x, y se cumple
S(x, y)” y la expresión “∀ x ∀y S(x, y) se lee “Para todos x, y se verifica S(x, y)”.

Cuando las expresiones proposicionales están cuantificadas, tienen un valor de verdad y

se convierten en proposiciones.

Ǝx P(x), es verdadera si existe al menos un elemento a, que pertenece al dominio, tal

que P(a) es verdadera

Ǝx P(x), es falsa cuando P(a) es falsa para cualquier a del dominio.

“∀x P(x), es verdadera cuando P(a) es verdadera para cualquier sustitución de x por un
sujeto a del dominio

“∀x P(x), es falsa cuando al menos se encuentre una sustitución de x por un sujeto a del
dominio tal que P(a) es falsa.

Expresiones que contienen más de un cuantificador

Vamos a aclarar el significado de expresión cuantificada cuando aparecen dos
cuantificadores.

∀x Ǝy P(x, y) ↔ Ǝy ∀x P(x, y)

Para cada valor de x en mi Dominio, existen un valor de “y” que satisface a P (x, y)

Existe al menos un elemento de “y” que sirve para todos “x” del Dom, que
hacen/verifican a P (x,y).

Ejemplo:

∀x Ǝy (x + y = y + x = 0) Verdadero

Para cada “x” entero, encuentro un “y” tal que (x + y = y + x = 0). Cada “x” entero,
tiene asociado un “y”, que es el opuesto de “x”, tal que su suma = 0 x = 5 y = -5.

∀5 Ǝ-5 (x + y = y + x = 0) Verdadero

Ǝy ∀x (x + y = y + x = 0) Falso

Definición 1.15

Si P (x, y) es una expresión relacional en dos variables x, y entonces la proposición Ax

Ay P (x, y) es lógicamente equivalente a la proposición Ay Ax P (x, y). De aquí que
podamos escribir que: Ax Ay P(x, y) ↔ Ay Ax P (x, y)

Podemos simplificar la notación y escribir que: Ax Ay P (x, y) ↔ Ax, y P (x, y)

Definición 1.16

Si P(x, y) es una expresión relacional en dos variables x, y entonces la proposición Ǝx

Ǝy P(x, y) es lógicamente equivalente a la proposición Ǝy Ǝx P(x, y) y podemos escribir
que:

Reglas de Inferencia
Un razonamiento es una implicación:

- El antecedente (hipótesis) es la conjunción de un número finito de fbfs,

denominadas premisas
- El consecuente es una fbf denominada conclusión

Entonces, un razonamiento es una fbf. Simbólicamente:

(p1 ^ p2 ^ … ^ pn) → c o bien

Validez de un razonamiento
La LPC es la ciencia encargada de distinguir los razonamientos válidos de los no
válidos.
Antes de analizar la validez de un razonamiento debemos verificar que el conjunto de
premisas (antecedente) sea consistente, es decir que exista una interpretación bajo la
cual todas las premisas sean verdaderas.

Ejemplo:

Un razonamiento es válido cuando el condicional es tautológico, esto es, si las premisas

son verdaderas entonces la conclusión debe ser necesariamente verdadera y si las
premisas son falsas no importará lo que ocurre con la conclusión ya que el condicional
será verdadero y por consiguiente el razonamiento será válido.

En términos lógicos, un razonamiento válido tiene la forma:

(p1 ^ p2 ^ p3 ^ … ^ pn )→ c

Razonamiento válido ≡ Regla de inferencia

Dado el razonamiento:

“Si llueve, llevo paraguas. Si llevo paraguas, no uso sombrero. Uso sombrero. Luego
no llueve”

a) Identificar premisas y conclusión

b) Justificar la validez de razonamiento

Proposiciones: p: “llueve”, q: “llevo paraguas”, r: “uso sombrero”;

Premisas (¿?); Conclusión: c: “no llueve”

Razonamiento: ((p → q) ^ (q →¬r) ^ r) → ¬p

Justificación: v(r) = 1; v(¬r) = 0 luego v(q) = 0; entonces v(p) = 0 de donde v(¬p) = 1 y

el razonamiento es válido.

Reglas de Inferencia (MP – MT – SH)

Modus Ponens (MP) :
(p ^ (p → q)) → q

Las premisas son verdaderas si v(p) = 1; y para que v (p → q) = 1, debe ser

v(q) = 1. Luego el razonamiento es válido.
Modus Tollens (MT) :

Las premisas son verdaderas si v(¬q) = 1; y para que v(p → q) = 1, debe ser v(p) = 0.
Luego v(¬p) = 1 y el razonamiento es válido.

Silogismo Hipotético (SH):

Justificación:

Aplicando el Teorema de la Deducción,

Las premisas son verdaderas si v(p) = 1; y para que v(p → q) = 1, debe ser v(q) = 1.
Luego para que v(q → r) = 1 debe ser v(r) = 1, y el razonamiento es válido.

Prueba Formal
Una prueba formal de la validez de un razonamiento es una sucesión de fbfs cada una de
las cuales es, o bien una premisa, o bien se deduce (lógicamente) de las precedentes y
tal que el último enunciado de la sucesión es la conclusión del razonamiento cuya
validez se quiere demostrar.

Ejemplo 1: (Dilema Destructivo)

Observación:

¬p v ¬r es equivalente a p →¬r. Por el teorema de la deducción agregamos a “p” como

premisa y la conclusión será c: ¬r.

Prueba Formal

Ejemplo 2:

θΦ¬ϵ

Teoría del Conteo

Definición: Técnica, habilidad o arte de contar sin que necesariamente debamos
enumerar.
Regla de la suma
Si un experimento (proceso que posee una cantidad finita de resultados observables) se
puede separar en dos etapas o tareas, donde una se puede realizar de n maneras posibles,
la otra de m maneras posibles y no se pueden realizar las dos simultáneamente (son
excluyentes), entonces el experimento se puede realizar m + n maneras.
Ejemplo: si en dos pequeñas salas de cine se cuentan en un determinado momento, 32 y
18 personas, respectivamente ¿Cuántas personas asistieron en ese horario? 32 + 18 = 50
Generalización de la suma y del producto
Generalización de la Regla de la suma: Si un experimento se puede separar en e1,
e2, ..., en etapas excluyentes y hay m1 , m2 , ..., mn resultados posibles para cada una de
ellas, respectivamente, entonces el experimento puede realizarse de m1 + m2 + ... + mn
maneras distintas.
Ejemplo: Un profesor posee distintos libros sobre tres lenguajes de programación: C++,
Java y Python. Cuenta con 5 libros de lenguaje C++, 7 libros de Java y 6 de Python. Si
un estudiante está interesado en aprender un primer lenguaje de programación, ¿de
cuantas maneras distintas podrá elegir un libro para este fin? Tres tareas excluyentes: 5
+ 7 + 6 = 18 formas distintas de realizar esta tarea.
Regla del producto: Si un experimento se puede separar en dos etapas no
excluyentes (ambas tienen lugar), donde una se puede realizar de m maneras posibles y
la otra se puede realizar de n maneras posibles, entonces existen m x n resultados
posibles.
Ejemplo: Si tenemos que seleccionar dos estudiantes, uno de ellos de un grupo de 60
alumnos de un curso de primer año y el otro representativo de un curso de 45 alumnos
de segundo año, por la regla del producto, habrá: 60 x 45 = 2700 formas distintas de
seleccionar a los dos estudiantes
Generalización de la Regla del producto: Si un experimento se puede separar en e1,
e2, ..., en etapas excluyentes y hay m1, m2, ..., mn resultados posibles para cada una de
ellas, respectivamente, entonces el experimento tiene m1 x m2 x ... x mn resultados
posibles.
Ejemplo: Con los dígitos 0, 1, 2, 3 y 4
¿Cuántos números de cuatro cifras puedo formar? ¿Y cuantos de tres cifras distintas?
- Cantidad de número de cuatro cifras: 4x5x5x5 = 500
- Cantidad de números de tres cifras distintas: 4x4x3 = 48
Ejemplo 2: Con los dígitos 0, 1, 2, 3 y 4
¿Cuántas claves de acceso a un cajero automático tendría disponibles con esos dígitos,
si las claves usan 4 dígitos?
Cantidad de claves: 5x5x5x5 = 625
Cadenas de símbolos. Alfabeto
Interesa saber la cantidad de listas que se pueden formar con determinadas
características
Ejemplo: ¿Cuántas claves de cuatro cifras comienzan o terminan con 2?
 1000 números de cuatro cifras que comienzan con 2
 100 números de cuatro cifras que
terminan con 2

 100 número de cuatro cifras que comienza y terminan con 2

1000 + 1000 – 100 = 1900 claves de cuatro cifras que comienzan o terminan con 2.
Ejemplo 2: ¿Cuántos mensajes de hasta 4 caracteres puedo formar con los dígitos del
alfabeto {0, 1}?
 2 mensajes de un carácter

 4 mensajes de dos caracteres

 8 mensajes de tres caracteres

 16 mensajes de cuatro caracteres

2 + 4 + 8 + 16 = 30 mensajes de hasta cuatro caracteres formados con los dígitos del

alfabeto {0, 1}

Función Factorial
Se denomina función factorial a la función F: N0 → N definida por:
F(0) = 1
F (n) = n * F (n - 1) si n > 0
F (1) = 1 * F (0) = 1 * 1
F (2) = 2 * F (1) = 2 * 1
F (3) = 3 * F (2) = 3 * 2 * 1
F (4) = 4 * F (3) = 4 * 3 * 2 * 1
Notación: F (n) = n!
Permutaciones
Definición: Dado un conjunto X = {x1, x2, x3, …, xn} que contiene n elementos
distintos, una permutación de tamaño “r” (0 ≤ r ≤ n) de los n elementos de X, es una
disposición (ordenación) de “r” elementos distintos seleccionados entre los n elementos
de X.
Características:
- Interesa distinguir el orden en el que aparecen los elementos
- No se permiten repetir los elementos
Teorema: La cantidad de permutaciones de tamaño r de un conjunto de n elementos
distintos es:
n!
P (n, r) = n (n - 1) (n - 2) ……(n - (r - 1)) =
( n−r ) !
Ejemplo: ¿De cuantas formas puedo ordenar 3 libros de un conjunto de 5 textos
distintos?
5! 5!
P (5, 3) = = = 5 * 4 * 3 = 60
( 5−3 ) ! 2!
60 formas de ordenar 3 libros de un conjunto de 5 textos distintos