Apuntes de Lógica
Apuntes de Lógica
Apuntes de Lógica
1 Proposiciones Lógicas
• Una proposición lógica es un enunciado al cual se le puede asignar un valor de verdad,
verdadero (V ) o falso (F ). Denotaremos a estas por letras minúsculas p, q, r, . . . etc.
2 Conectivos Lógicos
• Al operar con proposiciones y según sean tales operaciones, se utilizan ciertos símbolos,
llamados Conectivos Lógicos
3 Tablas de Verdad
• Las operaciones básicas se definen mediante Tablas de Verdad.
p ∼p
V F
F V
1
• El bicondicional p ⇔ q , conocida también como Equivalencia Lógica establece que
p es condición necesaria y suficiente para q .
Dada dos o más proposiciones, usando los conectivos lógicos podemos construir nuevas
proposiciones.
Una proposición que contiene conectivos se llama “proposición compuesta”.
El cálculo proposicional se preocupa de la determinación del valor lógico de una
proposición compuesta a partir de los valores lógicos de las proposiciones básicas que la
componen. A una proposición compuesta se le asocia una tabla de valores lógicos, con
2n valores en cada columna, donde n es el número de símbolos distintos que representan
a las componentes de la proposición. El uso reiterado, de la tabla que describe los
posibles valores lógicos asociado a cada conectivo, permite determinar el valor lógico
de una proposición compuesta.
Ejemplo
2
4 Tautologı́as
• Una Tautología o Teorema lógico es una proposición compuesta que es siempre ver-
dadera independientemente del valor de verdad de las proposiciones componentes. Una
proposición siempre falsa es una Contradicción.
(p ∧ p̄) ⇔ 1 (Tautología)
(p ∨ q) ⇔ p̄ ∧ q̄
8. Leyes de Morgan
(p ∧ q) ⇔ p̄ ∨ q̄
9. Contrarecíproca (p ⇒ q) ⇔ (q̄ ⇒ p̄)
p ∧ (p ∨ q) ⇔ p
10. Absorción
p ∨ (p ∧ q) ⇔ p
(p ∧ 1) ⇔ p (p ∨ 1) ⇔ 1
11. Identidad
( p ∧ 0) ⇔ 0 (Contradicción ) (p ∨ 0) ⇔ p
p q p∨q ˜p ˜p =⇒ q
V V V F V
V F V F V
F V V V V
F F F V F
* *
3
B.- Algunas Equivalencias Fundamentales
E.1 (p ⇒ q) ≡ ˜p ∨ q
E.2 p ∧ (˜p ∨ q) ≡ p ∧ q
E.3 p ∨ (˜p ∧ q) ≡ p ∨ q
E.4 p ⇒ q ≡ ˜q ⇒ ˜p
E.5 p ⇒ q ≡ [(p ∧ ˜q) ⇒ 0]
E.6 (p ∧ q) ⇒ r ≡ p ⇒ (q ⇒ r)
E.7 (p ∧ q) ⇒ r ≡ (p ∧ ˜r) ⇒ ˜q
E.8 p ⇒ (q ∧ r) ≡ (p ⇒ q) ∧ (p ⇒ r)
E.9 p ⇒ (q ∨ r) ≡ (p ⇒ q) ∨ (p ⇒ r)
E.10 (p ∧ q) ⇒ r ≡ (p ⇒ r) ∨ (q ⇒ r)
E.11 (p ∨ q) ⇒ r ≡ (p ⇒ r) ∧ (q ⇒ r)
E.12 ˜(p ⇐⇒ q) ≡ ˜p ⇐⇒ q ≡ p ⇐⇒ ˜q
Un buen ejercicio es verificar que cada una de estas leyes, equivalencias implicaciones son
tautologías, para ello basta construir las tablas de verdad correspondientes y verificar que
sólo se obtiene V.
4
Algunos argumentos válidos:
p q p =⇒ q (p =⇒ q) ∧ p [(p =⇒ q) ∧ p] =⇒ q
V V V V V
V F F F V
F V V F V
F F V F V
es una Tautología ( T.4)
El esquema deductivo asociado al principio anterior se representa por:
(A =⇒ B) y A entonces B
• Ejemplo
Si A2 = B 2 ⇐⇒ (A − B = 0 ∨ A + B = 0) es válido y A2 = B 2 es válido ,
entonces (A − B = 0 ∨ A + B = 0) es válido
3. Principio de Silogísmo
• Ejemplo
5
Cuantificadores
5 Función Proposicional
• Una función proposicional (f.p.) es una expresión o afirmación que contiene una
o más variables, la expresión se convierte en una proposición. en una proposición al
sustituir dicha(s) variable(s) por un (o algunos) elemento (s) de un conjunto referencial
(Universo) A.
• En otros términos, una función proposicional es un enunciado abierto con una variable
( también puede ser con más variables) del tipo p(x) ( o p(x, y) , p(x, y, z) ,...)
que al ser referido a un determinado conjunto referencial A , puede ser siempre,
parcialmente o nunca verdadero.
• Notemos que una f.p. p(x), no es una proposición, pero si genera proposiciones al
sustituir la variable x por un elemento a ∈ A ,esta proposiicón se denota por p(a)
Si p(a) es verdadera entonces se dice que el valor x=a, satiface a la f.p. p(x)
Ejemplo: Sea p(x) : x es divisible por 3 con A=Z
p(20) : 20 es divisible por 3 ( Falso ) P(174) es Verdadero
6 Cuantificador Universal
• Si queremos afirmar que todos los elementos x ∈ A cumplen p(x) ,
entonces simbolizaremos
∀x ∈ A, p (x)
esta expresión es una Proposición.,donde ∀ se lee “para todo”, o “para cada” o
“para cualquier” y se denomina cuantificador universal.
∀x ∈ A, p (x) se lee ”para todo x en A, p(x) es verdadero” o ”para todo x
en A, p(x) se cumple”
• En consecuencia :
7 Cuantificador Existencial
• Si queremos afirmar que para algunos elementos de a ∈ A se cumple p(x) . Esto es
si p(x) no se cumple para todos los elementos de A , sólo se cumple para algunos,
escribimos
∃ x ∈ A, p(x)
donde ∃ se lee “ existe ”,o “para algún ” o “hay ” y se denomina cuantificador
existencial.
Se tiene en consecuencia :
6
E1) ∃ x ∈ A, p (x) es verdadero si y sólo si existe a lo menos un elemento a ∈ A
para el cual p (a) es verdadero.
E2) ∃ x ∈ A, p (x) es falso si y sólo no existe a ∈ A para el cual p (a) sea ver-
dadera, es decir p(a) es Falsa para cada a ∈ A
Con nuestro ejemplo:
p(x) : x es divisible por 3 con A=Z.
tenemos que ∃x ∈ A, p (x) ≡ ∃x ∈ Z, x es divisible por 3
es Verdadero porque p(-15) : -15 es divisible por 3 es Verdadero
Sin embargo ∃x ∈ Z, 3 < x < 4 es Falso ¿ por qué ? ;
∃n ∈ N, n(n + 1) = 35 es Falso ¿ por qué ?
9 Negación de Cuantificadores
• Como los cuantificadores universal y existencial son proposiciones por lo tanto sus
negaciones son proposiciones y se relacionan mediante el conectivo de la negación.La
negación de cuantificadores se atiene a las siguientes leyes :
Si F(x) es una f.p. con referencia A, las negaciones de las proposiciones ”∀x ∈
A, p (x) ”; ”∃x ∈ A, p (x)” estan dadas por las siguientes equivalencias:
• Ejemplo
˜[(∀n ∈ IN)(n + 1 > 5)] ≡ [(∃n ∈ IN)(n + 1 ≤ 5)]
Esto sugiere el método del contraejemplo, ya que mostrar que una proposición:
∀x, F (x) es falsa, significa mostrar que ∃x, F (x) verdadera.
=================================================
curso : algebra i - ingenieria
UTA - i semestre 2009