TEMA # 1

TEMA#1 Lógica Matemática

 

MATERIA:                           ESTRUCTURAS DISCRETAS

DOCENTE:                          

ESTUDIANTE:                    JAIME JUNIOR AGUILAR  LEAÑOS 

CARRERA:                           ING. DE SISTEMAS

TURNO:                               MAÑANA

TEMARIO

UNIDAD I

TEMA:  LOGICA MATEMATICA

1.-Introducción

2.- Proposición

3.- Notación

4.- Conectivos Lógicos

5.- Operaciones Proposicionales

6.- Formulas Proposicionales

6.1.- Clasificación de las Formulas Proposicionales

6.2 Contradicción de tablas de verdad

7.-Álgebra de Proposiciones 

7.1.-Leyes Lógicas

7,2.-Simplificación de Formulas Proposicionales  

8.- Circuitos Lógicos

9.- Funciones proposicionales y cuantificadores

9.1.-Cuantificadores 

UNIDAD I                LÓGICA MATEMÁTICA

1.-Introducción:

La lógica es una disciplina que trata de los métodos, modos formas del razonamiento humano, ofreciendo reglas y técnicas para determinar si un argumento es válido o no; Una de las metas fundamentales de la lógica es eliminar las ambigüedades del lenguaje común introduciendo símbolos o conectivos lógicos  en la construcción de proposiciones.

Lógica = Analizar el comportamiento humano.

Ambigüedades  =  los elementos que no están definidos claramente.

2.- Proposición:

Es todo enunciado u oración respecto de la cual se puede decir si es verdadero o falso, pero no ambos a la vez, es decir que toda proposición tienes los valores de verdad 1 verdadero u el otro falso.

a)      Los siguientes enunciados son proposiciones:

“Carlos estudia estructuras discretas el mes de abril”                           V

“El cuadrado tiene 3 lados”                                                                               F

“Un partido de futbol dura 90 minutos”                                                      V

“Los gatos ladran”                                                                                                 F

“15 es múltiplo de 3”                                                                                           V

“ ≥2 “                                                                                                     F

Los siguientes enunciados no son proposiciones:

Todos los que son interrogación o admiración, no son proposiciones:

“Viva Bolivia!!!”

“¿Hola como estas?”

“2 – 4+5”

3.- Notación:

Las proposiciones simples o numéricas se acostumbran a demostrar con letras minúsculas del alfabeto.

p, q, r, s, t…etc.

Ejemplo:

p: “El sol es cuadrado”

q: “El hombre es arquitecto de su propio destino”

r: “- 2 + 5 = 3”

s: “Los elefantes vuelan”

4.- Conectivos Lógicos:

Son símbolos que aparte de proposiciones simples nos permiten generar estas proposiciones simples o complejas.

Estos conectivos lógicos representan operaciones lógicas definidas.

CONECTIVOS	OPERACIÓN ASICIADA	SIGNIFICADO
˜	Negación	No p : no es cierto que p
˄	Conjunción	p˄ q
˅	Disyunción	p ˅ q (sentido inclusivo)
=>	Implicación (condicional)	Si p entonces q
<=>	Doble Implicación	p si y solo si q
v	Disyunción Exclusiva	P o q (sentido exclusivo)

5.- Operaciones Proposicionales:

Dada una  o más proposiciones cuyos valores de verdad se conoce, las operaciones proposicionales tratan de generar otras proposiciones para caracterizar las proposiciones resultantes a través de su valor de verdad utilizando las siguientes operaciones lógicas.

a)      Negación: (~)

p	~p
V	F
F	V

Cuando la proposición simple de “p” es antecedido por la el símbolo de negación “˜”, su valor de verdad cambia al valor contrario.

b)      Conjunción  (˄  = n)

P	q	p ˄  q
V	F	V
V	V	F
F	F	F
F	V	F

Regla.- La conjunción de 2 proposiciones es verdadera cuando ambos valores de verdad son verdades, en otro caso son falso.

c)       Disyunción:

P	q	p ˅ q
V	F	V
V	V	V
F	F	F
F	V	V

Regla.- La disyunción de 2 proposiciones es falsa cuando ambos valores de verdad son falso, en otro caso son verdaderos.

d)      Implicación:

p	q	p => q
V	F	V
V	V	F
F	F	V
F	V	V

Regla.- La implicación de 2 proposiciones es falsa cuando el antecedente es verdadero o y el consecuente es falso,en otro caso son verdaderos.

e)      Doble Implicación:

P	q	p <=> q
V	F	V
V	V	F
F	F	F
F	V	V

Regla.- La doble implicación de 2 proposiciones es verdadera cuando ambos valores de verdad son iguales,en otro caso es falso.

f)       Disyunción Exclusiva:

P	q	p v q
V	F	F
V	V	V
F	F	V
F	V	F

Regla.- La disyunción exclusiva de 2 proposiciones es verdadera cuando ambos valores de verdad son diferentes,en otro caso es falso.

6.- Formulas Proposicionales:

Es una combinación de proposiciones y conectivos lógicos que simbolizan a una proposición compuesta.

Ejemplo:

˜p =>q           ; ˜ (˜r v t) <=> ˜p                ;( ˜q ^ r) =>[(p v s) v (t <=>q)]

a)      ”Si la planta no crece, entonces necesita mas agua o necesita mejor abono”

˜p: “La planta no crece”

q: “La planta necesita más agua”

r: “La planta necesita mejor abono”

˜p=> (q v r)

b)      “La decisión depende del juicio o la intuición, y no de quien pago más”

p: “La decisión depende del juicio”

q: “La decisión depende de la intuición”

r: “La decisión depende de quién pago más”

(p v q) ^ ˜ r

c)       “21 es divisible entre 3 y por 7, pero no por 5”

p: “21 es divisible entre 3”

q: “21 es divisible entre 7”

r: “21 es divisible entre 5”

(p ^ q)^˜ r

6.1.- Clasificación de las Formulas Proposicionales”

Las formulas proposicionales se dividen según sus valores en:

a)      Tautología:

Se presenta cuando todos los valores de verdad resultante son verdaderas.

b)      Contradicción:

Se presenta cuando todos los valores de verdad resultante son falsos, se reconoce también como anti-tautología.

c)       Contingencia:

Se presenta cuando todos los valores de verdad resultante son verdaderos y falsos.

6.2 Contradicción de tablas de verdad.

Se deben analizar todas las posibles combinaciones de valores de verdad de las proposiciones que conforman la formula proposicional; para determinar dichas combinaciones se utiliza las siguientes formula de recurrencia.

2^n = Numero de combinaciones diferente del valor de verdad.

n = Numero de proposiciones simples diferentes.

Ejemplo: Clasifique mediante tablas de verdad, las siguientes formulas proposicionales.

1).- [˜q^( ˜P=>Q)]=>P

p	q	[˜q^( ˜P=>Q)]=>P
V	F	F	F	F	V	V	V	V
V	V	V	V	F	V	F	V	V
F	F	F	F	V	V	V	V	F
F	V	V	F	V	F	F	V	F

RESULTADO: TAUTOLOGIA.

2).-˜(p v q) <=> (˜ p => q)

p	q	˜(p v q) <=> (˜ p => q)
V	F	F	F	V	V	F	V	V
V	V	F	V	V	V	F	V	F
F	F	F	F	V	V	F	V	V
F	V	V	F	F	F	F	F	F

RESULTADO: CONTRADICCION.

3).-[q =>(r^ ˜q) <=>[(q v ˜p) => r]

p

q

r

˜(p v q) <=> (˜ p => q)

V

V

V

V

F

V

F

F

V

V

V

F

V

V

V

V

F

V

F

F

F

F

F

V

V

F

F

F

V

F

V

F

V

V

V

V

F

F

F

F

V

V

V

F

F

F

V

F

F

V

F

F

F

F

V

F

F

V

V

V

F

V

F

F

V

V

V

V

V

V

F

V

F

V

F

F

F

F

F

V

V

V

F

F

F

F

V

F

V

V

V

V

F

F

V

V

V

V

F

F

F

F

V

F

F

V

V

F

V

V

F

F

RESULTADO: CONTINGENCIA.

4).- Son p y r, proposiciones con valores de verdad f y v respectivamente; q y s proposiciones y tales que la formula proposicional ˜ (˜q ^ s) es falsa. Con esta información determine el valor de verdad de las siguientes formulas proposicionales:

[(p ^ ˜q) ^ s] => ˜ (˜r v s)

Solución:

˜ (˜q ^ s) = F                                                                     [(F ^ V) ^ V] =>˜(F v V)

(˜q ^ s)  = V                                                                      (F ^ V) =>˜ V

˜q  = V                                                                               F  =>  F

s  =  V                                                                                  V

5)- Son q y r proposiciones con valores de verdad F,  F, p y s proposiciones tales que la formula proposicional ˜ (p v ˜s) = V; Determine el valor de verdad de la formula proposicional.

Datos:

q = F                                     [F  =>(F ^ V) v (V => F)

r = F

(p ^ s) =˜ (p v ˜s) = V

˜ (p v ˜s) = V

p = F

˜s = F

6).- Determinar el valor de verdad d las proposiciones p, q, r, s, sabiendo que:

a)      La fórmula proposicional es falso: ˜(r =>˜p) =>( ˜q v s) = F

b)      La fórmula proposicional es verdadero: ˜(p v ˜r) ^ ˜(q =>˜ s) = V

a)      ˜(r =>˜p) =>( ˜q v s) = F

V                         F

˜(r =>˜p)  = V

˜q v s = F

r = V

˜p = F

˜q = F

S = F

Entonces:

p = V;                   q = V;                   r = V;                    s = F;

b)      ˜(p v ˜r) ^ ˜ (q => ˜s) = V

˜(p v ˜r) = V

 7.-Álgebra de Proposiciones

Son operaciones lógicas que se realizan en una formula proposicional, aplicando adecuadamente ciertas reglas básicas llamadas leyes lógicas. Es decir, al igual que en álgebra básica donde la simplificación de expresiones algebraicas es muy importante, en lógica también existe la necesidad de simplificar formulas proposicionales complejas , a través de ciertas equivalencias llamadas leyes lógicas.

7.1.-Leyes Lógicas

Son formulas proposicionales lógicamente equivalente, estas son :

1) Leyes de idempotencia:              p ^ p = p ;  p v p = p 

2)Leyes de conmutativas:               p ^ q = q v p :   pv q = q v p 

3)Leyes asociativas:                      (p ^q)v r =p^(q ^ r)

                                                       (p v q) v r = p v (q v r) 

4)Leyes de negación:                     ˜(˜ p) = p 

                                                      p^ ˜ p  = F    ;   p v ˜ p = V 

5)Leyes de identidad:                     p ^ V = p     ; p v F = p 

6)Leyes de De Morgan:                 ˜(p ^ q) = ˜p v ˜q 

                                                      ˜(p v q) = ˜p ^ ˜q 

7)Leyes distributivas                      p ^ (q v r) = (p ^ q) v (p ^ r)  

                                                       p v (q ^ r) = (p v q) v (p v r)  

8)Definición de implicación :         p > q = ˜ p v q 


9)Leyes de absorción                   p ^ (p v q)= p ; p v (p ^ q) = p 
                                                     p ^ F = F ; p V = V 

10)Definición de doble implicación:     p <> q = (p > q) ^ (q >  p) 

7.2.- Simplificación de Formulas proposicionales 

La simplificación de una proposición, o dicho de otra manera, la simplificación de una expresión lógica consiste en reducir la expresión lógica a una forma más simple mediante el uso de los axiomas y/o leyes lógicas.

La simplificación consiste en ir desarrollando la expresión paso a paso mediante la sustitución en cada paso de una expresión lógica equivalente a la anterior, hasta llegar a una expresión lógica irreducible.

A través de la simplificación podemos también demostrar una equivalencia lógica sin usar tablas de verdad.

Simplificar

[~(p Ú q) Ú (~p Ù q)] ® (~p Ù q           Ley de Morgan

[(~p Ù ~q) Ú (~p Ù q)] ® (~p Ù q)       Distributiva

[~p Ù (~q Ú q)] ® (~p Ù q)                  Complemento

(~p Ù V) ® (~p Ù q)                            Forma Normal

~p ® (~p Ù q)                                     Condicional 

~ (~p) Ú (~p Ù q)                                 Doble negación   

p Ú (~p Ù q)                                         Distributiva

(p Ú ~p) Ù (p Ú q)                                Complemento

V Ù (p Ú q)                                          Forma Normal       

p Ú q                                                   

. 

8.- Circuitos Lógicos: 

Un circuito lógico es una red de conmutación que está formada por cables e interruptores que conectan 2 terminales entre si.

Si una red de conmutación asociamos a un circuito lógico; entonces tenemos:

A————–.—.———-B

A————–./  .———–B

8.2.- Circuitos lógicos:

Se tienen 2 tipos de circuitos básicos:

a)      Circuito en serie:

Un circuito representado en serie representa a la operación lógica de conjunción es decir:

q

p

A———-.∕    .———–.∕   .———>B = p ^ q

b)      Circuito en paralelo:

Un circuito representado en paralelo representa a la operación lógica de disyunción es decir:

|——p.∕   .——-|

A —|                              |—-B = p v q

|——-q.∕  .——|

Ejemplo:

1.- Representar por medio de circuitos lógicos las siguientes formulas proposicionales:

a): q  p

b): p óq

c): p v q

2.- Dada la formula proposicional siguiente, represente el circuito lógico correspondiente y simplifique la formula proposicional.

{[p ^(q v r)] v (p ^ ˜r)} ^ (˜p v ˜q)

9.-Funciones proposicionales y cuantificadores

Una función Proposicional en una variable X es toda expresión  en la que X representa al sujeto o objeto perteneciente a cierto conjunto. La cual se convierte en proposición  para cada especifican de X. Es decir, si P(X) es una expresión que se convierte en proposición al sustituir la variable X por objeto matemático, se dice que P es una función proposiciones.

Supongamos los enunciados abiertos: 

" x es la capital de Buenos Aires"

" y + 4 = 11"

Estos no tienen un valor veritativo. Pero si en el primero de ellos hacemos x = La Plata, tenemos:

"La Plata es la capital de Buenos Aires" (V)

Asimismo, si en el segundo hacemos x = 9, resulta:  9 + 4 = 11 (F)

Podemos, entonces, dar la siguiente definición: "Una función proposicional es un enunciado abierto de la forma P_(x) que se convierte en una proposición cuando se le asigna un valor específico a la variable".

Ejemplos:

p_(x) : 2x + 5 > 11 , si x = 4 \ 13 > 11 (Verdadero)

q_(x) : 3x + 7 = 11 , si x = 5 \ 22 = 16 (Falso)

r_(x) : 2x + 1 = 5 , si x = 2 \ 5 = 5 (Verdadero)

s_(x) : x es un animal, si x = mesa se tendrá : mesa es un animal (Falso)

t_(x) : x es un ave, si x = flamenco se tiene: el flamenco es un ave (Verdadero)

9.1.-Cuantificadores

A partir de funciones proposicionales es posible obtener proposiciones generales mediante un proceso llamado de cuantificación. Asociados a la indeterminada x, introducimos los símbolos " x y $ x, llamados cuantificador universal y cuantificador existencial respectivamente. Las expresiones

Para todo x, se verifica p_(x) se denota por " x : p_(x)

Existe x, tal que se verifica p_(x) se denota por $ x / p_(x)

Corresponden a una función proposicional p_(x) cuantificada universalmente en el primer caso, y existencial mente en el segundo.

Ejemplo: Una función proposicional cuantificada universalmente es V si y sólo si son V todas las proposiciones particulares asociadas a aquella. Para asegurar la verdad de una proposición cuantificada universalmente es suficiente que sea verdadera alguna de las proposiciones asociadas a la función proposicional.

Un problema de interés es la negación de funciones proposicionales cuantificadas. Por ejemplo, La negación de "Todos los enteros son impares" es "Existen enteros que no son impares"   y en símbolos: $ x / ~ p_(x)

Entonces, para negar una función proposicional cuantificada universalmente se cambia el cuantificador en existencial, y se niega la función proposicional.

Ejemplo:  Supongamos la proposición: Todos los alumnos de mi colegio son aplicados

La vamos a escribir en lenguaje simbólico, negarla y retraducir la negación al lenguaje ordinario.

Nos damos cuenta pronto que se trata de la implicación de dos funciones proposicionales:

p_(x) : es alumno de mi colegio

q_(x) : es aplicado

Tenemos:  " x : p_(x) Þ q_(x)

Teniendo en cuenta la forma de negar una función proposicional cuantificada universalmente y una implicación resulta:

$ x / p_(x) Ù ~ q_(x)