apunte discreta utn frt



MATEMATICA DISCRETA 2010

UNIDAD 1:

LÓGICA PROPOSICIONAL Y DE PREDICADOS

Lógica proposicional.

Se define como proposición a toda oración que pueda asumir un valor de verdad (verdadero o falso).

Las proposiciones se clasifican en atómicas y compuestas.

Se llama proposición atómica a toda oración en la cual no aparecen conectores u operadores lógicos. Y se llama proposicióncompuesta a la relación entre dos o más proposiciones atómicas.


Tablas de verdad

Es un arreglo de filas y columnas que se utiliza para determinar los valores de verdad de las proposiciones lógicas atreves de asignación verdadera o falsa.

Está compuesta por un encabezado de filas en el cual aparecen las proposiciones que intervienen y la proposición compuesta cuyo valor de verdad sepretende establecer.

En las filas todas las 2n combinación posibles de los valores de verdad de las n proposiciones atómicas que intervienen y en la última columna el resultado de las combinaciones.










Conectivos lógicos.

Conjunción:

Dados las proposiciones p y q el conectivo es verdadero solo cuando ambas son verdaderas.

P  q: se lee p y q”

P
Q
P  Q
V
V
V
VF
F
F
V
F
F
F
F


Disyunción:

Dados las proposiciones p y q el conectivo es verdadero solo si por lo menos una de las proposiciones es verdadera

P  q: se lee “p o q”

P
Q
P  Q
V
V
V
V
F
V
F
V
V
F
F
F

Negación:

Dados las proposiciones p el conectivo toma el valor contrario al de p

P: se lee “No p”

P
P
V
F
F
V

Condicional:

Dados lospredicados p y q el conectivo es falso solo en el caso en que p = V y q = F.

P  q: se lee “Si p, entonces q”

P
Q
P  Q
V
V
V
V
F
F
F
V
V
F
F
V

Bicondicional:

Dados los predicados p y q el conectivo es verdadero solo en el caso en que ambos tienen el mismo valor de verdad.

P  q: se lee “p si y solo si q”

P
Q
P  Q
V
V
V
V
F
F
F
V
F
F
F
V


Equivalenciasemántica

Dadas p, q diremos que p es semánticamente equivalente a q y escribiremos p ≈ q, si ambas tienen la misma tabla de verdad

p → q ≈  p  q,

P
Q
PQ
p  q
V
V
V
V
V
F
F
F
F
V
V
V
F
F
V
V
Tautologías

Una proposición que es verdadera para todas las combinaciones posibles de sus variables se llama tautologías.

P
Q
P  Q
V
V
V
V
F
V
F
V
V
F
F
VContradicciones

Una proposición que es falsa para todas las combinaciones posibles de sus variables se llama contradicción.

P
Q
P  Q
V
V
F
V
F
F
F
V
F
F
F
F


Contingencias


Una proposición que no es tautologías ni contradicción se llama contingencia

P
Q
P  Q
V
V
V
V
F
F
F
V
F
F
F
F


Implicaciones y equivalencias lógicas.

EquivalenciasLógicas:

  A = A Doble negación

A  B = B  A, A  B = B  A Leyes Conmutativa

A  (B  C) = (A  B)  C, A  (B  C) = (A  B)  C Leyes asociativas

A  (B  C) = (A  B)  (A  C), A  (B  C) = (A  B)  (A  C) Leyes Distributiva

A  A = A, A  A = A Leyes de Idempotencia

A  F = A, A  V = ALeyes de Identidad

A  V = A, A  F = A Leyes de Dominación

A   A = V, A   A = F Leyes de los Inversos

 (A  B) =  A   B,  (A  B) =  A   B, Leyes de De Morgan

A → B =  B →  A Ley de la contrapositiva

A → B =  A  B,  (A → B) = A  B, Ley de la condicional

(A  B)  A = A, (A  B)  A = A Leyes de absorción

A↔B = (A B)  ( A   B),

 (A↔B) = (A  B)  (A  B), Leyes del Bicondicional





Implicaciones Lógicas:

A, B  A  B Ley de Combinación

A  B  A, A  B  B Leyes de simplificación

A  A  B, B  A  B Leyes de adición

A,A→BB...