Volver a Matemática Discreta
Unidad 1: Fundamentos de Lógica Simbólica Proposicional
1.1. Introducción: Historia y objetivos de la lógica.
1.2. Proposiciones: proposiciones lógicas y principios de la lógica clásica, proposiciones
simples y compuestas, tablas de verdad.
1.3. Operaciones entre proposiciones: conectivos lógicos unarios y binarios, operaciones
entre proposiciones (negación, conjunción, disyunción inclusiva y exclusiva,
condicional simple y condicional doble),
1.4. Clasificación según valor de verdad: tautología, contradicción y contingencia;
satisfacibilidad. [Autoestudio: forma normal disyuntiva y conjuntiva a partir de una
tabla de verdad].
1.5. Relaciones entre proposiciones: equivalencia lógica, demostración de equivalencias
por tabla de verdad y por método algebraico, leyes lógicas usuales (propiedades de las
operaciones), consecuencia o implicación lógica.
1.6. Razonamiento deductivo: concepto, razonamiento válido y falacia, reglas de
inferencia usuales, método de deducción algebraico, concepto de teorema, lema,
corolario y demostración.
Unidad 1: Fundamentos de Lógica Simbólica Proposicional
1.1. INTRODUCCIÓN
1.1.1. Breve reseña histórica
La lógica clásica tiene sus raíces en la antigua Grecia, particularmente con Aristóteles,
quien la sistematizó en un cuerpo de principios y reglas de inferencia. Durante más de
dos mil años, la lógica permaneció prácticamente sin cambios, mientras que las
matemáticas evolucionaban independientemente. En el siglo XIX, George Boole
introdujo la lógica simbólica, seguido por otros matemáticos como Bertrand Russell y
Alfred North Whitehead. La lógica matemática formalizó y precisó el lenguaje,
corrigiendo algunas deficiencias en los planteamientos aristotélicos y generando nuevas
revelaciones.
1.1.2. Objetivos de la unidad
Los objetivos de la unidad incluyen formalizar la lógica matemática, definir conceptos y
símbolos, establecer reglas para el manejo y combinación de estos, y eliminar la
ambigüedad del lenguaje natural. Al finalizar la unidad, se espera que los estudiantes
puedan interpretar el formalismo lógico, utilizar correctamente los símbolos lógico-
matemáticos, aplicar propiedades de las operaciones lógicas y identificar razonamientos
deductivos válidos.
1.2. PROPOSICIONES
La lógica clásica, basada en el enfoque aristotélico, hace una distinción importante entre
juicio y proposición. El juicio es el acto mental mediante el cual pensamos un enunciado,
mientras que la proposición es el contenido de ese acto, es decir, lo que se piensa.
1.2.1. Proposición lógica
Definición: Una proposición lógica es una oración declarativa de la cual puede conocerse
que es verdadera o falsa. En castellano, son sencillamente afirmaciones de las cuales un
experto en el tema al cual se refieren, puede decir si son verdaderas o falsas.
Notación: Denotaremos las proposiciones con las letras p, q, r, … o con las letras con
subíndices p1 , p2 , …, pn . En aquellos casos en que se utilicen las letras p, q, r, ..., sin
aclarar explícitamente a qué proposiciones se refieren, hablaremos de variables
proposicionales
1.2.2. Principios de la lógica
Lógica bivalente: UNA PROPOSICIÓN SIMPLE SÓLO PUEDE SER: O BIEN
VERDADERA, O BIEN FALSA.
La definición de proposición lógica al afirmar que sólo pueden ser VERDADERAS o
FALSAS, integra en ella implícitamente los
Principios Fundamentales de la lógica
clásica
, a saber:
Principio de Identidad: Toda proposición es idéntica a sí misma y sólo a sí misma.
Principio de No Contradicción: Dadas dos proposiciones contradictorias entre sí, no
pueden ser ambas verdaderas.
Principio del Tercero Excluido: Dadas dos proposiciones contradictorias entre sí, no
pueden ser ambas falsas. Estos principios son verdades autoevidentes en lógica (axiomas o
postulados) que no pueden ser demostrados, sino que se los supone verdaderos y desde
ellos se construye toda la lógica clásica.
1.2.3. Proposiciones Simples y Compuestas
• SIMPLES: aquellas que no pueden ser divididas o descompuestas en partes más simples
desde el punto de vista de la lógica. En otras palabras, son afirmaciones que expresan una
idea o un hecho que puede ser verdadero o falso
• COMPUESTAS: toda combinación de proposiciones simples mediante vocablos lingüísticos
denominados conectivos lógicos.
1.2.4. Tablas de Verdad
Los valores de verdad de una proposición pueden disponerse como una tabla, como la de
la derecha. Si la proposición es simple, tendrá dos (2) filas posibles (V y F), pero si es
una proposición compuesta por n proposiciones simples combinadas con
conectivos lingüísticos, entonces necesitaremos 2
n
filas para poder analizar TODAS
las posibilidades; donde ‘2’ son los valores V y F y ‘n’ es el número de proposiciones
simples de una proposición compuesta.
Notación: Denotaremos las proposiciones compuestas con letras en mayúsculas P, Q, R,
… o con letras con subíndices P1, P2, …, Pn.
Si se quiere enfatizar que una proposición compuesta P está armada con las proposiciones
simples p, q, r escribiremos P(p, q, r). Los conectivos lingüísticos utilizados para generar
proposiciones compuestas, serán llamados en este contexto conectivos lógicos y
operadores lógicos.
1.3. CONECTIVOS LÓGICOS Y OPERACIONES LÓGICAS
Los conectivos lingüísticos funcionan como operadores sobre los valores de verdad de
las proposiciones que conectan.
Conectivo Lingüístico
Símbolo
Operación
Significado en Castellano
no
⎯ , ,
Negación
no p
no es cierto que p
y
, & , .
Conjunción
p y q
p pero q
o
, | , +
Disyunción Inclusiva
o p, o q, o ambos
p y/o q
,
Disyunción Exclusiva
o p, o q, pero no ambos
o bien p, o bien q
si ... entonces
→
Condicional Simple
si p entonces q
p implica q; q sólo si p
sí y sólo si
, sii
Condicional Doble
p si y sólo si q
p
V
F
1.3.1. Negación (unario)
Dada una proposición lógica p, la NEGACIÓN DE p es una nueva proposición
denotada p o p, que leeremos no p, la cual es verdadera si p es falsa y falsa si p es
verdadera.
Se pueden negar proposiciones simples y compuestas.
1.3.2. Conjunción (binario)
Dadas dos proposiciones lógicas p y q, la CONJUNCIÓN DE p Y q es
una nueva proposición denotada p q, que leeremos p y q, la cual es
verdadera si tanto p como q son verdaderas y falsa en todos los otros
casos.
1.3.3. Disyunción Inclusiva
Dadas dos proposiciones lógicas p y q, la DISYUNCIÓN INCLUSIVA DE
p Y q, o simplemente la DISYUNCIÓN DE p Y q, es una nueva proposición
denotada p q, que leeremos p o q, la cual es falsa si tanto p como q son
falsas y verdadera en todos los otros casos.
1.3.4. Disyunción Exclusiva
Dadas dos proposiciones lógicas p y q, la DISYUNCIÓN EXCLUSIVA DE
p Y q, es una nueva proposición denotada p q, que leeremos o bien p o
bien q, la cual es verdadera si p y q tienen distinto valor de verdad y falsa si p
y q tienen igual valor de verdad.
1.3.5. Condicional Simple
Dadas dos proposiciones lógicas p y q, el CONDICIONAL SIMPLE
DE p Y q es una nueva proposición lógica denotada p → q, que
leeremos si p entonces q o p implica q, la cual es falsa sólo en el caso que
p sea verdadera y q sea falsa, y es verdadera en todos los otros casos.
Muchos teoremas de la matemática se presentan como un condicional
simple SI p ENTONCES q, por lo cual se le asignan un nombre especial a sus
componentes y a formas similares:
Definición: Si R: p→q es una proposición compuesta, decimos que:
• p es el antecedente, hipótesis o condición suficiente para R.
• q es el consecuente, conclusión o condición necesaria para R.
• La proposición q → p es la proposición recíproca de R.
• La proposición p → q es la proposición contraria de R.
• La proposición q→ p es la proposición contrarrecíproca de R
p
F
V
p
q
p q
V
V
V
V
F
F
F
V
F
F
F
F
p
q
p q
V
V
V
V
F
V
F
V
V
F
F
F
p
q
p q
V
V
F
V
F
V
F
V
V
F
F
F
p
q
p → q
V
V
V
V
F
F
F
V
V
F
F
V
1.3.6. Condicional Doble
Dadas dos proposiciones lógicas p y q, el CONDICIONAL DOBLE
ENTRE p Y q (o DOBLE IMPLICACIÓN ENTRE p Y q), es una nueva
proposición lógica denotada p q, que leeremos p si y sólo si q (o
también p implica doblemente a q), que es verdadera si p y q tienen el
mismo valor de verdad, y falsa si tienen distintos valores de verdad.
1.4. CLASIFICACIÓN DE PROPOSICIONES SEGÚN SUS VALORES DE
VERDAD
Se denomina TAUTOLOGÍA, y se la denota con V
0
, a una proposición compuesta que
siempre es verdadera, cualesquiera sean los valores de verdad de las proposiciones simples
que la forman.
Se denomina CONTRADICCIÓN, y se la denota con F
0
, a una proposición compuesta
que siempre es falsa, cualesquiera sean los valores de verdad de las proposiciones simples
que la forman.
Se denomina CONTINGENCIA, a una proposición compuesta que es verdadera o
falsa, según sean los valores de verdad de las proposiciones simples que la forman.
Se dice que una proposición compuesta es SATISFACIBLE si es verdadera para alguna
combinación de valores de verdad de las proposiciones simples que la forman.
1.4.1. FORMA NORMAL DISYUNTIVA Y CONJUNTIVA
• DISYUNTIVA
Dada una tabla de verdad de una proposición compuesta P que involucra a n
proposiciones simples p1, p2, …, pn, se debe seguir el siguiente procedimiento:
a) MIRAR LAS LÍNEAS de la tabla de verdad en las que LA PROPOSICIÓN P ES
VERDADERA.
b) Realice la conjunción de todas las proposiciones simples teniendo en cuenta que
SI P
J
es VERDADERA se coloca como está en la conjunción y si es FALSA se
coloca negada. A esta construcción la llamaremos un min-término.
c) Repita el paso b) hasta conseguir todos los min-términos correspondientes
d) ESCRIBA en símbolos la PROPOSICIÓN P COMO LA DISYUNCIÓN DE
TODOS LOS MIN-TÉRMINOS construidos.
• CONJUNTIVA
PRINCIPIO DE DUALIDAD. Esta propiedad ESTABLECE QUE AL
INTERCAMBIAR “disyunción y conjunción”, “tautología y contradicción” y “verdadero
y falso” en cualquier enunciado, teorema, algoritmo, propiedad o procedimiento, SE
OBTIENE UNO ANÁLOGO. Aplicando esta propiedad al procedimiento para
determinar la Forma Normal Disyuntiva de una proposición compuesta P, obtendremos
otro procedimiento para determinar la Forma Normal Conjuntiva de ella. Lo hacemos en
lo que sigue:
Dada una tabla de verdad de una proposición compuesta P que involucra a n
proposiciones simples p1, p2, …, pn, se debe seguir el siguiente procedimiento:
e) MIRAR LAS LÍNEAS de la tabla de verdad en las que LA PROPOSICIÓN P ES
FALSA.
p
q
p q
V
V
V
V
F
F
F
V
F
F
F
V
f) Suponga que en la i-ésima LÍNEA DE LA TABLA DE VERDAD DE P HAY UN
FALSO. En esa línea las proposiciones simples pj tendrán valores falsos o
verdaderos; realice la DISYUNCIÓN de todas las proposiciones simples teniendo
en cuanta que si PJ es FALSA se coloca como está en la disyunción y si es
VERDADERA se coloca negada. A esta construcción la llamaremos un max-
término.
g) Repita el paso b) hasta conseguir todos los max-términos correspondientes a las
líneas de la tabla en que P es falsa.
h) Finalmente, ESCRIBA en símbolos la PROPOSICIÓN P COMO LA
CONJUNCIÓN DE TODOS LOS MAX-TÉRMINOS construidos.
1.4.2. Precedencia de operadores
Jerarquía
Conectivo
Mayor 1°
~
2°
3°
4°
→
Menor 5°
El uso de paréntesis permite modificar la jerarquía
En caso de tener más de un conectivo de la misma jerarquía en una expresión dada, la
evaluación se realiza siempre de izquierda a derecha.
1.5. EQUIVALENCIA LÓGICA ,
Dadas dos proposiciones P(r1 , r2 , …, rn ) y Q(r1 , r2 , …, rn ) compuestas, se dice que P
ES LÓGICAMENTE EQUIVALENTE A Q, y se lo denota P Q, si para cualquier
combinación de valores de verdad de las proposiciones simples r1 , r2 , … y rn que las
componen, P y Q tienen el mismo valor de verdad.
En otras palabras, P y Q pueden escribirse distinto, pero significan lo mismo. Si P Q,
decimos que P y Q están relacionadas por la equivalencia lógica, o que la equivalencia
lógica es VÁLIDA.
1.5.1. Leyes Lógicas
Las propiedades de las operaciones lógicas (llamadas leyes lógicas) solo son equivalencias
que se verifican entre proposiciones compuestas obtenidas utilizando esas operaciones.
Las leyes lógicas son teoremas que se pueden demostrar sencillamente construyendo las
tablas de verdad de las proposiciones para determinar la equivalencia que especifican. Por
ello, se presentarán las siguientes propiedades como un teorema que involucra muchas
equivalencias. Se sugiere que se practique la construcción de tablas de verdad o el método
algebraico, para demostrar cada una de ellas.
Teorema: Si P, Q y R son proposiciones lógicas no necesariamente distintas, V
0
una
tautología y F
0
una contradicción, entonces se verifican las siguientes propiedades de la
negación, conjunción, disyunción y sus combinaciones:
Involución
(P) P
De la Conjunción
De la Disyunción
Idempotencia
P P P
P P P
Conmutativa
P Q Q P
P Q Q P
Asociativa
P Q) R P (Q R)
(P Q) R P (Q R)
Distributiva
P (Q R) (P Q) (P R )
P (Q R) (P Q) (P R )
De Morgan
(P Q) P Q
(P Q) P Q
Neutro
P V
0
P
P F
0
P
Complemento
P P F
0
P P V
0
Acotación
P F
0
F
0
P V
0
V
0
Absorción
P (P Q) P
P (P Q) P
Principio de Dualidad
Dado un teorema T de la lógica matemática que involucre en su
enunciado V
0
, F
0
, y , el dual de T denotado Td , obtenido al
intercambiar en T: V
0
por F
0
, F
0
por V
0
, por , y por , es
también un teorema de la lógica.
1.5.2. Consecuencia Lógica (Implicación Lógica)
En lenguaje cotidiano usamos el vocablo implica, queriendo significar que, si el
antecedente de la implicación es verdadero, entonces necesariamente el consecuente
también debe serlo, esto es, es una consecuencia lógica que se deriva del antecedente. En
este sentido se define la siguiente relación:
Definición: Dadas dos proposiciones compuestas P(r1, r2, …, rn) y Q(r1, r2, …, rn), se
dice que P IMPLICA LÓGICAMENTE A Q (o que Q ES CONSECUENCIA LÓGICA
DE P), y se lo denota P Q, si para cualquier combinación de valores de verdad de las
proposiciones simples r1, r2, … y rn que hagan a P verdadera, resulta Q ser también
verdadera.
Es decir que, si al confeccionar la tabla de verdad de las proposiciones compuestas, en
cada fila que P sea verdadera Q también lo es, decimos que hay implicación lógica entre
ellas por lo cual la relación P Q es válida. De ocurrir que, en alguna fila de la tabla de
verdad resulta que P es verdadera y Q es falsa, entonces diremos que la relación P Q
es inválida.
1.6. RAZONAMIENTO DEDUCTIVO
Dadas las proposiciones lógicas P1, P2, …, Pn llamadas hipótesis o premisas, y una
proposición Q denominada conclusión, llamaremos RAZONAMIENTO DEDUCTIVO
a la relación existente entre ellas, denotada por: P1, P2, …, Pn Q, que leeremos si P1 y
P2 y … y Pn por lo tanto Q, la cual será válida si cada vez que todas las premisas sean
simultáneamente verdaderas, la conclusión resulta ser también verdadera.
Un razonamiento es un esquema de pensamiento, un encadenamiento de proposiciones
en una argumentación que intenta deducir o justificar algo. Un razonamiento VÁLIDO
recibe también el nombre de REGLA DE INFERENCIA pues permite inferir la verdad
de la conclusión desde la verdad de las premisas. De un razonamiento INVÁLIDO se dice
que es una FALACIA.
Cada vez que las premisas son verdaderas al mismo tiempo en una fila de la tabla de
verdad, resulta que la conclusión también es verdadera en esa fila, por lo que el
razonamiento es válido.
En el lenguaje natural, los razonamientos suelen escribirse en vertical en vez de
horizontalmente, como sigue:
Una vez que un razonamiento deductivo se ha establecido como válido, el mismo
constituye una regla de inferencia sintáctica, esto es, un esquema general de pensamiento
que puede ser utilizado con cualesquiera premisas particulares en el formato indicado en
el esquema, para obtener la verdad de una conclusión particular según el mismo
esquema. Por ello se suele decir que:
La deducción es un proceso que trabaja de lo general a lo particular
El concepto de razonamiento deductivo válido establecido en la definición dice varias
cosas importantes, que hay que visualizar y sobre las que hay que reflexionar:
• Un razonamiento es una relación entre proposiciones, la cual no puede decirse que
sea verdadera o falsa porque no es una proposición, sino válida o inválida.
• Si un razonamiento es válido, entonces la verdad de las hipótesis es evidencia de la
verdad de la conclusión, o sea que con su utilización no es posible que las premisas
sean verdaderas y la conclusión resulte falsa.
• En la definición se dice que el razonamiento es válido si, cada vez que todas las
premisas sean verdaderas simultáneamente la conclusión también es verdadera. Pero
todas las premisas serán verdaderas cuando su conjunción también lo sea; esto es,
cada vez que (P1 P2 … Pn) es verdadera la conclusión Q también es verdadera.
Lo anterior dice que hay implicación lógica entre la conjunción de las premisas y la
conclusión, o sea que es válida la relación:
(P1 P2 … Pn) Q
• Pero sabemos que si (P1 P2 … Pn) Q es válida, la implicación simple entre
ellas es una tautología; en símbolos:
(P1 P2 … Pn) → Q es una tautología
1.6.1. Reglas de Inferencia
Ahora estableceremos unas pocas reglas de inferencia, que usualmente son utilizadas
para desarrollar las demostraciones.
Las mostradas en el siguiente teorema son solo algunas de las infinitas reglas de
inferencia que pueden establecerse; las tres primeras expuestas son las de uso más común
en matemáticas y ciencias. Solo a modo de comentario, las reglas cuarta y quinta son la
base para un método muy utilizado en programación lógica e inteligencia artificial: le
método de resolución de Robinson.
1.6.2. Método de deducción algebraico
Cuando el número de variables proposicionales involucradas crece más allá de cuatro o
cinco, el método de construir la tabla de verdad para decidir la validez de un
razonamiento se vuelve cada vez más laborioso ya que el número de filas de la tabla se
duplica cada vez que se agrega otra variable.
Un método alternativo es el denominado MÉTODO DEDUCTIVO ALGEBRAICO o
de DEDUCCIÓN NATURAL. Con este método no se trata de probar que la verdad de
las premisas es evidencia de la verdad de la conclusión, sino que la conclusión puede
derivarse mediante reglas de inferencia y equivalencias desde las premisas.
La validez del razonamiento se deduce al demostrar que la conclusión es una
consecuencia lógica (sintáctica) de las premisas, por lo cual, si las premisas son verdaderas,
entonces la conclusión también lo será.
1.6.3. Teorema, Lema, Corolario, Demostración
• Una proposición interesante dentro de una teoría, cuya verdad puede ser “probada”,
ya sea utilizando equivalencias lógicas, consecuencias lógicas o razonamientos
deductivos, se dice que es un TEOREMA de la teoría.
• El proceso por el cual se prueba la verdad del teorema recibe el nombre de
DEMOSTRACIÓN del teorema.
• Si el teorema no es muy interesante, pero es una propiedad que sirve para demostrar
un teorema interesante, se denomina LEMA.
• Si el Teorema se deriva trivialmente de otro Teorema recientemente demostrado, se
llama COROLARIO de aquel.
resumen LED U1.pdf
browser_emoji Estamos procesando este archivo...
browser_emoji Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.
Descargar
. . . . .