Download parte 1 - Sitios de las cátedras Facultad de Ciencias Exactas y

Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
Lógica de Proposiciones
y de Predicado
Franco D. Menendez
LABIA
FACET - UNT
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
»Cada lógica da lugar a un lenguaje para realizar declaraciones acerca de los objetos y
para realizar razonamientos acerca de las propiedades de esos objetos.
»Las declaraciones en un lenguaje lógico están construidas de acuerdo a un conjunto
predefinido de reglas de formación denominadas Reglas de Sintaxis.
»El lenguaje natural no es adecuado para llevar a cabo un razonamiento lógico.
⋄El lenguaje natural es muy rico en contenido y no puede ser descrito formalmente.
⋄El significado de una oración es ambiguo.
»Un lenguaje lógico tiene cierta sintaxis y el significado o semántica, de una declaración
o proposición expresada en este lenguaje esta dado por una interpretación en su
estructura. Dados un lenguaje lógico y su semántica, podemos tener una o mas sistemas
de comprobación para este sistema lógico.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
»La lógica proposicional es el sistema lógico con la semántica mas simple. Sin embargo
muchos de los conceptos y técnicas utilizadas para estudiar la lógica proposicional es
generalizada para la lógica de predicado de primer orden. En la lógica de predicado
existen proposiciones atómicas y proposiciones compuestas. Los hechos o
proposiciones atómicas pueden ser interpretadas como verdaderas o falsas.
»Las consecuencias del conjunto de proposiciones es una estructura cerrada . Que
pueden ser verdaderas para todas las interpretaciones posibles llamada tautología
(“verdad universal”).
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
El alfabeto L del lenguaje formal, es un conjunto conformado por tres conjuntos sin
elementos en común (conjuntos disyuntos). Ellos son:
»1.-
El conjunto V de variables proposicionales. Este conjunto es infinito y
enumerable.
V = { p1, p2, ....., pn, .... }
»2.-
El conjunto K de conectores proposicionales.
K = {  }  { ,  ,  ,  )
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
»3.El conjunto P de símbolos de puntuación o paréntesis. Este conjunto es de naturaleza
impropia.
P={(,)}
En consecuencia el alfabeto, correspondiente a un lenguaje formal para la lógica, está
definido por la unión de los tres conjuntos antes detallados.
L=V K P
La letra «p» que representan proposiciones, reciben el nombre de «variables lógicas». Estas
variables reciben los siguientes dos valores V y F, por lo que a esta lógica recibe el nombre de
«Lógica Bivalente».
Ejemplo 1:
El niño juega
Ejemplo 2:
El niño juega y no llora
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
»Conectores Proposicionales
CONECTIVO
DENOMINACIÓN
LECTURA EN ESPAÑOL

Conjunción
Y

Disyunción
O

Implicación o
Condicional
si ... entonces

Bicondicional o
Equivalencia
si y sólo si ... entonces

Negación
No
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
Símbolos de Puntuación
Los símbolos de puntuación permiten ordenar grupos de palabras y separarlos de otros. En la lógica
se utiliza signos de puntuación para evitar equívocos.
EJEMPLO
pqr
(p  q)  r
p  (q  r)
Se podrán utilizar paréntesis, corchetes y llaves, significando lo mismo desde el punto de
vista de la sintaxis del lenguaje formal.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
Cadenas de Caracteres: Concatenación
CADENA VACÍA: es aquella cadena que no contiene ningún signo o símbolo del alfabeto L y la
denotamos de la siguiente forma: " < > ".
CONCATENACIÓN: Cuando colocamos dos cadenas, una a continuación de la otra, obtenemos otra
cadena y que la representaremos por " ᴖ " y que es una ley de composición interna a la que
denominamos concatenación, es asociativa pero no es conmutativa.
( A ᴖ B ) ᴖ C es lo mismo que A ᴖ ( B ᴖ C )
A ᴖ B es diferente de B ᴖ A
CADENA NEUTRA: La cadena vacía es denominada también cadena neutra a derecha e izquierda
para la concatenación ( no altera a la cadena concatenada con ella ).
Aᴖ <>=<>ᴖ A=A
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
El lenguaje del Calculo de Proposiciones (EBF)
El conjunto de EBF constituye el lenguaje del calculo proposicional. Por lo que este conjunto (F) es un
subconjunto del alfabeto L.
REGLAS DE BUENA FORMACION:
El conjunto F de todas las EBF, se define como un conjunto de Reglas Recurrentes, denominadas Reglas de
Buena Formación.
REGLA I: Una variable proposicional cualquiera es una EBF.
" p  V; p  F o lo que es lo mismo V  F
REGLA II:
REGLA II-1: Si A es una EBF, entonces  A es una EBF
REGLA II-2: Si A y B son EBF, entonces (A * B) es una EBF, donde * K – { }
REGLA III: es también denominada la regla de CLAUSURA. Solamente las cadenas formadas
por las Reglas I, II-1 Y II-2 son EBF.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
»Definición Algebraica de la semántica del Lenguaje Proposicional: A los efectos
de poder tratar de la manera booleana la semántica del lenguaje, confundiremos
los valores de verdad (FALSO, VERDADERO) con la dupla (0,1);
»Evaluación de las EBF: sea F una formula conformada por p0, p1, …. pk, la
semantica no dice bajo que condición px son verdaderos o falsos. Lo que permite
es una interpretación de la distribución de valores de verdad del mismo, el cual
determina el resultado de F.
»Ejemplo
(p  (q  r))
Donde δ(p)=0 , δ(q)=1 δ( r) =1
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
Definición por Recurrencia de la Semántica de las EBF
Sea δ una distribución de verdad que posee las variables proposicionales p1,p2,…. Pn cuyos valores
tomados del conjunto son {0,1}donde su notación será de la forma δ (p1). Definimos una aplicación Fδ
del conjunto F de las EBF sobre el conjunto Z={0,1}.
Fδ = F  { 0,1 }
La Función por recurrencia se define de la siguiente manera:
1.Fδ (p) = δ (p) : " p  V
2.Fδ ( A) = ’ δ (A) = 1 - Fδ ( A)
3.Fδ (A  B) = ’ (Fδ (A ), Fδ ( B))= MIN ((Fδ (A ), Fδ ( B))
4.Fδ (A  B) = ’ (Fδ (A ), Fδ ( B))= MAX ((Fδ (A ), Fδ ( B))
5.Fδ (A  B) = ’ (Fδ (A ), Fδ ( B))= MAX ((Fδ ( A ), Fδ ( B))
6.Fδ (A  B) = ’ (Fδ (A ), Fδ ( B))= MIN ((Fδ (A  B ), Fδ ( B  A))
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
TAUTOLOGIA, CONTRADICCION E INDEFINICION
Los otros usos mas que realizaremos de la tabla de verdad es:
1.Para determinar el valor de verdad de las proposiciones.
2.Para determinar el carácter de las proposiciones.
3.Para descubrir relaciones entre proposiciones dadas.
4.Para determinar la validez de razonamientos.
Definimos
»Avaloración: al conjunto de combinaciones de los valores de verdad de una formula.
»Dominio: alude solamente a aquellos casos de avaloración verdaderos. Se define dominio
pleno cuando todas las avaloraciones tienen resultado verdadero siempre. El dominio se
dice vacío cuando en la avaloración solo figuran F.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
TAUTOLOGIA, CONTRADICCION E INDEFINICION
Ejemplo: (p  q) ; (p  q)  ( p  q) ;
p  ( p  q)
(p  q) (p  q)  ( p  q)
p  ( p  q)
p
q
V
V
V
V
V
V
F
F
V
F
V
F
V
F
F
F
F
V
V
V
V
V
F
V
F
F
F
V
V
V
F
F
Los enunciados o fórmulas del primer tipo, aquellos que a veces son falsos y otras
verdaderos, reciben el nombre de INDEFINIDOS. Los del segundo tipo, siempre verdaderos,
se denominan TAUTOLOGÍAS; los del tercer tipo, siempre falsos, son denominados
CONTRADICCIONES.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT1: Lenguaje Formal (Sintaxis y Semántica)
Validez y Consecuencia
»Definición: Una fórmula proposicional A es satisfactoria si su valor es verdadero en alguna
interpretación. Una interpretación satisfactoria es denominada como un modelo para A. Una
fórmula A es válida si su valor es verdadero para todas interpretaciones, a lo cual lo
denotamos como: A
»Definición: Una fórmula proposicional A es no satisfactoria o contradictoria si no es
satisfactoria, o sea que, su valor es falso para todas interpretaciones. Es no válida o falsa si
no es válida, o sea que, es falsa para algunas interpretaciones.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Noción general de sistemas axiomáticos
Un sistema axiomático, consiste en los siguientes objetos:
i.
Términos primitivos: constituidos por elementos, conjuntos o relaciones, cuya
naturaleza no queda especificada de antemano.
ii.
Axiomas: son funciones proposicionales cuantificadas, relativas a las variables (T.P.),
son propiedades a las que deben satisfacer dichos términos primitivos.
iii.
Definiciones: se definen todos los términos no primitivos.
iv.
Teoremas: propiedades que se deducen de los axiomas.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
DECISION POR FORMAS NORMALES
»Las formas normales o canónicas, llamadas así acaso porque el pensamiento expresado
en ellas ofrece mayor claridad, son fórmulas o EBF construidas solamente con los
conectivos lógicos de conjunción y disyunción y bajo ciertas condiciones.
»Existen dos formas normales; la forma normal conjuntiva (que abreviamos de la siguiente
forma: f.n.c.) y la forma normal disyuntiva (que abreviamos f.n.d.).
»Forma Normal Conjuntiva
Una forma normal conjuntiva es una serie continua de conjunciones y donde los
factores de esas conjunciones son sólo disyunciones.
»Por ejemplo, consideremos lo siguiente expresión lógica que es una f.n.c.:
( p  q)  (p   q)  ( p   q)
»Forma Normal Disyuntiva
Una forma normal disyuntiva es una serie continua de disyunciones y donde los
factores de esas disyunciones son sólo conjunciones.
(p  q)  (p   q)  ( p  q)
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
»1).La f.n.c. no es tautológica. Transformada en f.n.d., se observa que no es
contradictoria. Entonces es indefinida.
»2).La f.n.c. no es tautológica. Transformada en f.n.d. cada factor incluye una
variable proposicional y su negación. Entonces es una contradicción.
»3).La f.n.d. no es contradictoria. Transformada en f.n.c., se observa que no es
tautológica. Entonces es indefinida.
»4).La f.n.d. no es contradictoria. Transformada en f.n.c. cada factor incluye una
variable proposicional y su negación. Entonces es una tautología.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Enunciados y Formas de Enunciados
Ahora podemos decir que una forma de enunciado es una fórmula o expresión lógica EBF,
construida con variables proposicionales. Si se reemplazan las variables por constantes
proposicionales, cuidando en todos y en cada caso de sustituir la misma variable por la
misma constante, obtenemos un enunciado. Continuando con la significación atribuida a A
y a  B, los ejemplos siguientes muestran enunciados y sus correspondientes formas:
»Enunciados
1) A  B
2) A   B
3)  A  A
4) B   B
Formas de Enunciados
1) p  q
2) p   q
3)  p  p
4) p   p
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Razonamiento
Un razonamiento está constituido por enunciados de tal modo que el último (conclusión) se
deriva con necesidad lógica de los anteriores (premisas).
Razonamiento
Forma de Razonamiento
V Si Güemes es salteño es argentino
V Es argentino
V Luego es salteño
1) p  q
q
 p
V Si Güemes es tucumano es argentino
V Es argentino
F Luego es tucumano
2)p  q
q
 p
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Razonamiento


Razonamiento
AB
1)
BC
AB
CB
Enunciado correspondiente
2)(A  B)  (B  C)  (A  B)  (C  B)
En (2) hemos unido las distintas premisas del razonamiento (1), mediante la
conjunción. Este procedimiento está justificado por una de las formas válidas
de razonamiento.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Formas de Razonamiento
Forma de Enunciados
Forma de Razonamiento
1) [(p  q)  r]  p
1) (p  q)  r
p
2) [(p  q)   q]   p
2) p  q
q
p
Forma de Razonamiento
Forma de Enunciado
Válida
Tautológica
Inválida
Indefinida o Contradictoria
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Sistemas para Derivaciones
»1.Existe una lista dada de argumentos o formas de razonamientos lógicos
admisibles, llamadas Reglas de Inferencia. Esta lista se la conoce con el nombre de L.
»2.La derivación por si misma es una lista de expresiones lógicas. Originalmente
esta lista esta vacía. Se le pueden añadir expresiones a ésta si constituyen una premisa o si
pueden obtenerse a partir de expresiones previas, aplicando una de las reglas de inferencia.
Este proceso continua hasta que se alcanza la conclusión.
»Si existe una derivación para la conclusión C, dado que A1, A2, . . . ., An son las premisas
y dado que L es el conjunto de reglas de inferencia admisibles, entonces escribimos:
»A1, A2, . . . ., An |= L C
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Cuadro Semántico
El método del cuadro semántico es un algoritmo relativamente eficiente para la decisión y
su comprobación en el cálculo proposicional. El principio es muy simple, pues para comprobar la satisfiabilidad debemos buscar siempre un modelo.
Definición Un literal es una proposición simple o una fórmula atómica o la negación de la
fórmula atómica. Definimos a {p,  p} como el par complementario de literales, si y solo si p
es una fórmula atómica.
Definición Para cualquier tipo de fórmula A, el conjunto {A,  A} es el par complementario
de fórmulas. A es el complemento de  A y por lo tanto  A es el complemento de A.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Cuadro Semántico
Recordemos las siguientes definiciones:
Definición 1.-Una fórmula A es satisfactoria, si su valor es verdadero para alguna
interpretación. Una interpretación satisfactoria es denominada como un Modelo de A. La
notación empleada para un modelo es : = A
Definición 2.- Una fórmula es Válida si su valor es verdadero para todas las
interpretaciones.
Definición 3.- Una fórmula lógica o proposición compuesta es Insatisfactoria o
Contradictoria, si la misma no es satisfactoria, o sea que es FALSA (F) para todas sus
interpretaciones.
Definición 4.-Una fórmula lógica es Inválida o No Válida o Falsificable, si no es válida, o
sea que su valor es FALSO (F) para alguna interpretación de sus valores de verdad.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
UT2: : Sistemas Axiomáticos
»Si la formula B es una formula-B, crear dos nuevos nodos I’ y I’’ como hijos de I, etiquetar a I’ con la
siguiente formula:
U(I’)=(U(I) – {B}) U (B1)
Y etiquetar I’’ con la siguiente fórmula:
U(I’)=(U(I)-{B}) U (B2)
La construcción termina cuando todas las hojas del árbol están marcadas con un símbolo X o bien O.
• Definición: Un cuadro cuya construcción ha finalizado se lo denomina Cuadro Completo. Un cuadro
completo se dice que está cerrado si todas sus hojas están marcadas con la notación de cerrado, de
otra forma o modo se dice que el cuadro esta Abierto.
• Teorema : Sea T un cuadro semántico completo para una formula A. la expresión A es No
satisfactoria si y solo si T es cerrado.
• Corolario 1: La expresión A es una expresión lógica satisfactoria si y solo si T esta abierto.
• Corolario 2: La expresión A es una expresión lógica valida si y solo si el cuadro semántico para  A
es cerrado.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
BIBLIOGRAFIA
»ESTRUCTURAS DE MATEMÁTICAS DISCRETAS. Bernard Kolman. Robert Busby & Sharon Ross. –
2003.
»MATEMÁTICA DISCRETA Y LÓGICA. Roberto H. Fanjul – 2005.
»MATEMÁTICAS DISCRETAS - SEXTA EDICIÓN Richard Johnsonbaugh - PRENTICE HALL INC. –
2005.
»LÓGICA COMPUTACIONAL. Roberto H. Fanjul. Autor y Editor. Primera Edición – 2005.
»MATEMÁTICAS DISCRETA Y COMBINATORIA Ralph P. Grimaldi- Addison Wesley Longman – 2001.
Universidad Nacional de Tucumán
Facultad de Ciencias Exactas y Tecnología
¡GRACIAS!
Preguntas?
» [email protected]