Lógica proposicional
Una Proposiciones un enunciado, declaración,
sentencia que puede tomar valores de verdadero o falso. Ejemplo de proposiciones:
·
Bogotá es la capital de Colombia
·
Madrid es la capital de España.
·
3 + 5 = 7.
·
2 + 1 = 3.
·
La tierra es el único planeta en el
universo que tiene vida.
·
Los únicos enteros positivos que
dividen a 7 son 1 y el propio 7.
·
Otros?
Son propensiones?
·
Qué hora es?.
·
¡Cierra la puerta!.
·
x + 1 = 2.
·
x + y = z.
·
Ella es muy inteligente.
·
compre dos boletos para el concierto
de rock para el viernes
Para representar las proposiciones se utilizan
letras mayúsculas tales como P, Q, R, etc. Por ejemplo, sea:
·
P: Hoy es martes.
·
Q: Hay clase de matemáticas
En cualquier lógica, las proposiciones se
clasifican en simples o compuestas. Las proposiciones simples se identifican
porque no contienen otras afirmaciones que la compongan (átomos)
Las proposiciones compuestas se obtienen al
combinar proposiciones simples para expresar afirmaciones más complejas
Pag. Recomendada
Video tutorial
Concepto de proposición
La proposición
es un enunciado declarativo que puede tener caracteres de verdad o falso pero
no ambos.Enunciados declarativos:
*El día esta nublado—–Verdadero
*Carlos está matriculado en el tecnológico—-Verdadero
NOTA: Una proposición no puede ser escrita como pregunta ni como admiración un enunciado de exclamación o que represente ambigüedad (que no pueda ser determinado si es verdadero o falso).
PROPOSICIÓN SIMPLE:
Átomo declarativo o unidad definida que puede ser determinada como falso o verdadero.
PROPOSICIÓN COMPUESTA:
Se conforma por dos o más proposición simples y se relaciona por conectores o conectivos.
pág. recomendada
Proposiciones compuestas
(Disyunción, Conjunción, Negación,
Condicional, Bicondicional)
Proposiciones Compuestas:
Una proposición compuesta
es una frase que consta de uno o varios sujetos y de un predicado que afirma
algo en torno a dichos sujetos. Los sujetos de una proposición simple deben ser
todos términos singulares. El predicado debe contener un verbo que exprese la
acción sobre los sujetos. En matemáticas se usan ciertos símbolos para
representar predicados de uso frecuente como: el símbolo “_”, como
representante del predicado “es igual a “, y el símbolo “<” como sustituto
de “es menor que”.
EJEMPLOS:
Simples:
•La ballena es roja.
•La raíz cuadrada de 16 es 4.
•Gustavo es alto.
•Teresa va a la escuela.
•La raíz cuadrada de 16 es 4.
•Gustavo es alto.
•Teresa va a la escuela.
Compuestas:
•La ballena no es roja.
•Gustavo no es alto.
•Teresa va a la escuela o María es inteligente.
•4 es menor que 8 o 6 es mayor que 10.
•El 1 es el primer número primo y es mayor que cero.
•El 7 es mayor que 5 y 7 es menor que 10.
•Si Yolanda es estudiosa entonces pasará el examen.
•Si corro rápido entonces llegaré temprano.
•Terminaré rápido si y sólo si me doy prisa.
•Aprenderé Matemáticas si y sólo si estudio mucho.
•Gustavo no es alto.
•Teresa va a la escuela o María es inteligente.
•4 es menor que 8 o 6 es mayor que 10.
•El 1 es el primer número primo y es mayor que cero.
•El 7 es mayor que 5 y 7 es menor que 10.
•Si Yolanda es estudiosa entonces pasará el examen.
•Si corro rápido entonces llegaré temprano.
•Terminaré rápido si y sólo si me doy prisa.
•Aprenderé Matemáticas si y sólo si estudio mucho.
Disyunción
Se representan dos enunciados separadas por la
expresión o basta con que una sea verdadera para que se
cumpla la proposición (pvq). Su símbolo es: V
EJEMPLOS:
Está lloviendo o es de noche.
Está feliz o está enojado.
Está caminando o está lloviendo.
Hay derivadas o hay integrales.
Conjunción
Es cuando dos proposiciones simples se
combinan mediante la expresión y, la proposición
compuesta resultante se le llama conjunción (pΛq). Su símbolo es: Λ, &,
·
EJEMPLOS:
La puerta está vieja y oxidada.
Hace frío y está nevando.
Está lloviendo y es de noche.
Tiene gasolina y tiene corriente.
Negación
Si p es una proposición fundamental, de ésta
se puede formar otra proposición, que se le llama Negación de p,
escribiendo: “Es falso que” antes de p, ó, cuando
es posible, se inserta en p la palabra “No”,
(¬p) Su símbolo es: ¬, ~
EJEMPLOS:
No está lloviendo.
La señora no ceno.
Es falso que 5×2=12.
Es falso que Alemania se encuentra en Europa.
Condicional
El condicional
material es un operador que opera sobre dos valores de verdad, típicamente
los valores de verdad de dos proposiciones, devolviendo el valor de
verdad falso sólo cuando la primera proposición es verdadera y
la segunda falsa, y verdadero en cualquier otro caso.
La condicional de
dos proposiciones p, q da lugar a la proposición; si p entonces q, se
representa por p → q
EJEMPLOS:
Si está dormido entonces está soñando.
Si quiere comer entonces tiene hambre.
Si Londres está en Inglaterra entonces París
está en Francia.
Si hay gasolina en mi tanque entonces mi
automóvil funciona.
Bicondicional
El bicondicional o
doble implicación es un operador que funciona sobre dos valores de verdad,
típicamente los valores de verdad de dos proposiciones, devolviendo el valor de
verdad verdadero cuando ambas proposiciones tienen el mismo
valor de verdad, y falso cuando sus valores de verdad difieren.
EJEMPLOS
p: ”10 es un número impar”
q: “6 es un número primo”
p↔q: “10 es un número impar si y solo si 6 es un número primo”
p: ”3 + 2 = 7″
q: “4 + 4 = 8″
p↔q: “3 + 2 = 7 si y solo si 4 + 4 = 8″
p: ”10 es un número impar”
q: “6 es un número primo”
p↔q: “10 es un número impar si y solo si 6 es un número primo”
p: ”3 + 2 = 7″
q: “4 + 4 = 8″
p↔q: “3 + 2 = 7 si y solo si 4 + 4 = 8″
pág. recomendada
Estas tablas
pueden construirse haciendo una interpretación de los signos lógicos, como: no,
o, y, si…entonces, sí y sólo si, respectivamente. La interpretación corresponde
al sentido que estas operaciones tienen dentro del razonamiento.
Puede
establecerse una correspondencia entre los resultados de estas tablas y la
deducción lógico matemática. En consecuencia, las tablas de verdad constituyen
un método de decisión para chequear si una proposición es o no un
teorema.
Para la
construcción de la tabla se asignará el valor 1(uno) a una proposición cierta y
0 (cero) a una proposición falsa.
Negación: El valor de
verdad de la negación es el contrario de la proposición negada.
P
|
P
|
1
|
0
|
0
|
1
|
Disyunción: La
disyunción solamente es falsa si lo son sus dos componentes.
P
|
Q
|
P Q
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
Conjunción: Solamente
si las componentes de la conjunción son ciertas, la conjunción es cierta.
P
|
Q
|
P Q
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
Condicional: El
condicional solamente es falso cuando el antecedente es verdadero y el
consecuente es falso. De la verdad no se puede seguir la falsedad.
P
|
Q
|
P Q
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
Bicondicional: El
bicondicional solamente es cierto si sus componentes tienen el mismo valor de
verdad.
P
|
Q
|
P Q
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
Se denomina tautología
una proposición que es cierta para cualquier valor de verdad de sus
componentes. Por tanto, la última columna de su tabla de verdad estará
formada únicamente por unos.
Contradicción es la
negación de una tautología, luego es una proposición falsa cualquiera sea el
valor de verdad de sus componentes. La última columna de la tabla de
verdad de una contradicción estará formada únicamente por ceros.
Ejercicios 1.3
1. Sean P, Q,
R y S fórmulas. Si se sabe únicamente que P es verdadero, ¿Qué puede afirmarse
del valor de verdad de cada una las proposiciones siguientes?
- P Q
R P
S P
- R P P
Q
R
(S P)
- R P P
P S P S (Q P)
- S P P Q R
Q P R Q
2. ¿Qué puede
concluirse de cada una de las proposiciones anteriores, en los siguientes
casos?
- Si P es falsa.
- Si P es falsa, Q es verdadera y R es
verdadera.
3. Sean P, Q y
R fórmulas, entonces:
- Si R
P Q
P es falsa y P es falsa; ¿Qué puede afirmarse de R y de Q?.
- Si Q Q
P es verdadera y P es falsa; ¿Qué puede afirmarse de Q?.
- Si
R P Q P es falsa; ¿Qué puede afirmarse de P, Q
y R?.
- Si (Q
R) (PQ) R es falsa; ¿Qué puede
afirmarse de P, Q y R?.
- Si (P
Q) R P R Q) es verdadera; ¿Qué puede afirmarse
de P, Q y R?
4. Sean P, Q y
R fórmulas. Determinar cuáles de las siguientes proposiciones son tautologías:
- P Q P R
(P
Q ) ( Q P )
- P P Q
(P
Q) (P Q)
- P (Q
P)
P
((P Q) R)
- (P (Q P)) Q
P (P R)
Videos tutoriales
Tautología
Las tautologías son identidades lógicas que siempre serán verdaderas, no son solo un útil objeto en la lógica son usadas primordialmente para pruebas senténciales, desempeñan un papel fundamental en los procesos de la deducción dentro de esta lógica (sentencia).
Ejemplo:
La expresión ‘(p ^ q) → (p v r)’ es una tautología.
Las tautologías son identidades lógicas que siempre serán verdaderas, no son solo un útil objeto en la lógica son usadas primordialmente para pruebas senténciales, desempeñan un papel fundamental en los procesos de la deducción dentro de esta lógica (sentencia).
Ejemplo:
La expresión ‘(p ^ q) → (p v r)’ es una tautología.
Contradicción
Si una
proposición compuesta es falsa para todas las asignaciones entonces es una
contradicción. Son formulas sentencialmente contra-validas o de tercer grado.
Ejemplo:
P ∧ ¬P (se lee: P y no P). Su tabla de verdad es la siguiente.
P ∧ ¬P (se lee: P y no P). Su tabla de verdad es la siguiente.
Tautología, contradicción y
contingencia
•TAUTOLOGÍA: Una
proposición compuesta es una tautología si es verdadera para todas las
asignaciones de valores de verdad para sus proposiciones
componentes. Dicho de otra forma, su valor V no depende de los valores de
verdad de las proposiciones que la forman, sino de la forma en que están
establecidas las relaciones sintácticas de unas con otras. Sea el caso:
•CONTRADICCIÓN: Se
entiende por proposición contradictoria, o contradicción, aquella proposición
que en todos los casos posibles de su tabla de verdad su valor siempre es F.
Dicho de otra forma, su valor F no depende de los valores de verdad de las
proposiciones que la forman, sino de la forma en que están establecidas las
relaciones sintácticas de unas con otras. Sea el caso:
•CONTINGENCIA: Se entiende por verdad contingente, o verdad de
hecho, aquella proposición que puede ser verdadera o falsa, (combinación entre
tautología y contradicción) según los valores de las proposiciones que la
integran. Sea el caso:
https://sites.google.com/site/cursomatematicasdiscretas/3-4-tautologias-contradiccion-y-contingencia
EQUIVALENCIAS LOGICAS
Definición: Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos los posibles valores de verdad de sus componentes atómicos. Diremos que dos proposiciones P y Q son lógicamente equivalentes si es una tautología, es decir, si las tablas de verdad de P y Q son iguales.
Dadas dos proposiciones P y Q diremos que P implica lógicamente Q, y escribiremos P \Rightarrow Q si P rightarrow Q es una tautología. Si P es falso, entonces la proposición P, Q es verdadera independientemente del valor de Q. Por tanto, P si los valores de las variables que hacen a P verdadero también hacen verdadero a Q. De manera equivalente P Q significa que P y Q no tienen nunca de manera simultánea los valores de verdad 1 y 0 respectivamente. Como hemos dicho, las proposiciones pueden tomar dos valores, verdadero o falso, que representaremos respectivamente con los números 1 y 0. Por tanto, cuando digamos que una proposición toma valor 1 estaremos diciendo que es verdadera. El valor de verdad de una proposición compuesta queda determinado por los valores de las proposiciones simples que la forman. Las tablas de verdad nos indican los valores de verdad de una proposición para cada posible combinación de los valores de las proposiciones simples. A modo ilustrativo demostraremos, a continuación, que, en virtud de la ley asociativa de la conjunción, la fórmula p (qr) es lógicamente equivalente a (pq) r. Para ello no hay más que hacer la tabla de verdad de cada una de esas expresiones y comprobar si, en efecto, todas sus interpretaciones son iguales para la conectiva dominante. Te proponemos que rellenes la siguiente tabla con “Vs” y “Fs” donde proceda para comprobar que, en virtud de la ley asociativa de la disyunción, la fórmula p (qr) es equivalente a (pq) r. (p → ¬q) ∨ (¬p ∨ r) ¬p ∨ ¬q ∨ r
Las equivalencias se relacionan con las tautologías de la siguiente forma. |
Página recomendada
Reglas de inferencia
Las reglas de inferencia son esquemas básicos de
inferencia deductiva que se suelen escribir poniendo cada premisa en una línea
y la conclusión en otra línea al final. Toda regla, como toda inferencia
deductiva, tiene que estar basada en la implicación de la conclusión a partir
de las premisas. Veamos algunas de las más conocidas:
La
regla de modus ponens dice que si una premisa
tiene la forma de condicional y la otra afirma el antecedente entonces es
válida la inferencia que consiste en afirmar el consecuente:
P1:
P2:
C:
Está
basada en la tautología (que en un sistema axiomático completo es también una
ley, llamada modus ponens: ((( ) ) )
En
rigor, una cosa es la tautología, que es una sentencia en el lenguaje de la
lógica, y otra la regla de inferencia que de ella se deriva, que es una norma
para hacer deducciones y pertenece al metalenguaje («premisa», «conclusión»,
«regla», etc. se refieren al lenguaje; por tanto son parte de un metalenguaje).
No obstante utilizaremos el mismo nombre para ambas. El nombre es una forma
abreviada de la expresión «modus ponendo ponens»
con la que los lógicos medievales se referían a aquél modo de razonar mediante
el cual afirmando (ponendo) el antecedente
de un condicional se puede afirmar (ponens)
su consecuente.
La
regla de modus tollens dice que si se niega
el consecuente de un condicional entonces se puede negar su antecedente:
P1:
P2: ¬
C: ¬
Está
basada en ((( ) ¬) ¬)
El
nombre completo es «modus tollendo tollens»:
negando (tollendo) el consecuente se puede
negar (tollens) el antecedente.
Las
reglas de introducción de conjunción y disyunción permiten
concluir la conjunción y la disyunción de dos premisas:
P1:
P2:
C1:
C2:
Están
basadas en (( ) ( )) y (( ) ( ))
La
regla de eliminación de conjunción:
P:
C1:
C2:
Está
basada en (( ) ) y (( ) )
La
regla de encadenamiento:
P1:
P2:
C:
Está
basada en la transitividad del condicional: ((( ) ( )) ( ))
Las
reglas anteriores son intuitivamente «razonables». He aquí otra que no lo es
tanto, pero que como veremos nos va a resultar muy útil:
La
regla de resolución:
P1:
P2: ¬
C:
Está
basada en ((( ) (¬ )) ( ))
Cualquier
implicación lógica, y, por tanto, cualquier equivalencia, da lugar a una inferencia
deductiva. Por ejemplo:
( ( )) ( ( ))
De aquí
que podamos hacer las inferencias:
P: ( )
C: ( )
y
P: ( )
C: ( )
Página recomendada
Videos tutoriales
Lo que hace que podamos hablar de razonamiento es la
relación que existe entre los enunciados que llamamos premisas y la conclusión.
La transición o movimiento desde las premisas hasta la conclusión, es decir, la
conexión lógica entre las premisas y la conclusión,
es la inferencia sobre la que descansa el
argumento. Según sea la relación cabe hablar de razonamientos válidos o
inválido, correctos o incorrectos, bien construidos o mal construidos.
Verdad y validez son dos conceptos independientes. La verdad es una
propiedad de los enunciados, y un enunciado (o una
proposición) es verdadero, cuando hay una correspondencia entre la realidad y
el enunciado. Sólo los enunciados del tipo "Sócrates es un
hombre" o " "El fruto de las encinas son las manzanas",
pueden ser verdaderos o falsos. La validez de un argumento depende de la relación
de consecuencia lógica entre las premisas y la conclusión.
Cuando es a la vez formalmente válido y materialmente
adecuado (sus premisas y su conclusión son verdaderas) se dice que es un
argumento sólido.
Ejemplo
(1):
Si Picasso nació
en Málaga (p), entonces no es cierto que naciera en Francia (¬ q). Pero,
Picasso no nació en Francia (¬ q). Por tanto, nació en Málaga (p).
Analizando el ejemplo 1, podemos comprobar que aunque las
premisas y la conclusión sean verdaderas, conforme a los hechos, el argumento
no parece correcto.
Si el argumento fuera correcto, con ese mismo esquema
podríamos obtener otro correcto.
Ejemplo
(2):
Si Picasso nació
en Londres (p), entonces no es cierto que naciera en Francia (¬ q). Picasso no
nació en Francia (¬ q). Por tanto, Picasso nació en Londres (p)
Pero este ejemplo nos demuestra que no es así.
Las premisas pueden ser verdaderas o falsas, la conclusión puede
ser verdadera o falsa, y el argumento puede ser válido o inválido. Veamos resumidas en las
siguientes tablas todas las posibles combinaciones de verdad o falsedad de las
premisas y la conclusión, y de validez o invalidez de las inferencias:
Razonamientos correctos o válido,
clasificados por los valores de verdad de sus hipótesis y conclusión en la
realidad:
Si las premisas son:
|
Si la conclusión es:
|
|
verdadera
|
falsa
|
|
verdaderas
|
válido
(1)
|
imposible (2)
|
falsas
|
válido
(3)
|
válido (4)
|
Razonamientos incorrectos o inválido, clasificados por los
valores de verdad de sus hipótesis y conclusión en la realidad:
Si las premisas son:
|
Si la conclusión es:
|
|
verdadera
|
falsa
|
|
verdaderas
|
inválido
(5)
|
inválido (6)
|
falsas
|
inválido (7)
|
inválido (8)
|
A la lógica le interesa sólo la forma, la relación que se
establece entre las premisas y la conclusión. Existen tres combinaciones
posibles entre las premisas y la conclusión que dan lugar a argumentos o
inferencias válidas:
1. premisas
verdaderas y conclusión verdadera;
2. premisas
verdadera y conclusión falsa;
3. premisas falsas
y conclusión falsa.
Y sólo un caso en el que la inferencia resulta ser inválida:
cuando las premisas son verdaderas y la conclusión es falsa.
Los razonamientos incorrectos los descartamos pues no
garantizan la verdad de la conclusión, ni siquiera cuando las premisas sabemos
que son verdaderas. La validez es independiente de la verdad de sus premisas.
Sólo queda garantizada la verdad de la conclusión, haciendo una inferencia
válida a partir de premisas verdaderas.
Las falacias constituyen argumentos incorrectos,
algunas de las falacias más conocidas son:
a. Ad baculum: apelar a la
fuerza
b. ad hominem: contra la
persona
c. ad populum: usando en su
favor los prejuicios del grupo.
d. ad verecundiam: recurriendo
al principio de autoridad.
e. petitito
principii: en círculo.
f. ignoratio
elenchii: cambiar de tema.
¿Qué condiciones debe respetar un razonamiento para ser válido?
Un razonamiento es formalmente válido si:
1. La conclusión
se deriva de las premisas y o axiomas del sistema, por la aplicación de las
reglas de razonamiento establecidas en dicho sistema (Validez sintáctica)
2. Cuando es
imposible mantener al mismo tiempo sin contradecirse la verdad de las premisas
con la falsedad de la conclusión.
Página recomendada
Demostración formal (directa por contradicción)
Un sistema matemático consta de axiomas,
definiciones y términos no definidos. Se suponen verdaderos los axiomas. Las
definiciones se utilizan para crear conceptos nuevos en términos de los
existentes. Algunos términos no se definen en forma explícita, sino que se
definen en forma implícita mediante los axiomas. Dentro de un sistema
matemático es posible deducir teoremas. Un Teorema es una proposición cuya
verdad se ha demostrado. Un argumento que establece la verdad de un teorema es
una demostración. La lógica es una herramienta para el análisis de las
demostraciones. En esta sección describiremos dos métodos generales de
demostración: Directa y por contradicción. Si una fórmula tiene la forma A? B y
es una tautología, en donde A y B pueden ser proposiciones compuestas, entonces
decimos que B se desprende lógicamente de A y se representa por A |= B.
También podemos considerar tautologías de la forma (p1 p2 ^ … ^ pn)? q Entonces está implicación es verdadera sin importar los valores de verdad de cualquiera de sus componentes. En este caso, se dice que q se desprende lógicamente de p1,p2,…,pn. Se escribe. p1 , p2 , … , pn |= q o también
p1
p2 . . . pn __
__ q Significa que si se sabe que p1 es verdadera, p2 es verdadera ,…, y pn también es verdadera, entonces estamos seguros que q es verdadera. Una demostración directa comienza con las hipótesis, seguidas de las tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión. Demostración por contradicción.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción. La demostración del siguiente teorema por el método de contradicción es como se indica
p ? (q ^ r), (q ? s) ? t, (p ? s) |= t
Demostración: 1. p ? (q ^ r) Premisa
2. (q ? s) ? t Premisa
3. p ? s Premisa
4. ¬t Premisa Adicional
5. ¬(q ? s) MPP(2,4)
6. ¬q ^ ¬s Ley de Morgan(5)
7. ¬q LS(6)
8. ¬s LS(6)
9. p SD(3,8)
10. q ^ r MPP(1,9)
11. q LS(10)
12. q ^ ¬q Conjunción (7,11) pero esto último es una contradicción, por lo que queda demostrado el argumento.
También podemos considerar tautologías de la forma (p1 p2 ^ … ^ pn)? q Entonces está implicación es verdadera sin importar los valores de verdad de cualquiera de sus componentes. En este caso, se dice que q se desprende lógicamente de p1,p2,…,pn. Se escribe. p1 , p2 , … , pn |= q o también
p1
p2 . . . pn __
__ q Significa que si se sabe que p1 es verdadera, p2 es verdadera ,…, y pn también es verdadera, entonces estamos seguros que q es verdadera. Una demostración directa comienza con las hipótesis, seguidas de las tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión. Demostración por contradicción.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción. La demostración del siguiente teorema por el método de contradicción es como se indica
p ? (q ^ r), (q ? s) ? t, (p ? s) |= t
Demostración: 1. p ? (q ^ r) Premisa
2. (q ? s) ? t Premisa
3. p ? s Premisa
4. ¬t Premisa Adicional
5. ¬(q ? s) MPP(2,4)
6. ¬q ^ ¬s Ley de Morgan(5)
7. ¬q LS(6)
8. ¬s LS(6)
9. p SD(3,8)
10. q ^ r MPP(1,9)
11. q LS(10)
12. q ^ ¬q Conjunción (7,11) pero esto último es una contradicción, por lo que queda demostrado el argumento.
Página recomendada
Video tutorial
No hay comentarios.:
Publicar un comentario