Matematicas Discretas

1. LÓGICA MATEMÁTICA

Conectivos Lógicos

Símbolo Nombre Modo de leerse

¬ Negación No

^ Conjunción Y

v Disyunción O

→ Implicación Si … entonces

↔ Bicondicional Si y sólo si

Fórmulas Bien Formadas (FBF)

Una fórmula está bien formada si cumple con determinadas reglas de sintáxis. Las

reglas de sintáxis del cálculo proposicional son:

a) Un átomo es una fórmula bien formada.

b) Si G es una FBF entonces ¬G también lo es.

c) Si G y H son FBF entonces también lo son: GˆH , GˇH , G→H , G↔H

Tablas de verdad

Una tabla de verdad para una proposición compuesta construida a partir de

proposiciones p, q, r, ... es una tabla que proporciona los valores de verdad de la

proposición compuesta a partir de los valores de verdad de p, q, r, ... Llamamos a p, q, r,

... las variables de la tabla y de la proposición compuesta.

Negación

p ¬ p

F V

V F

Y

p q p ^ q

F F F

F V F

V F F

V V V

O

p q p v q

F F F

F V V

V F V

V V V

Si y sólo si

p q p ↔ q

F F V

F V F

V F F

V V V

Implica (si … entonces)

p q p →

q

F F V

F V V

V F F

V V V

MCC Blanca Esthela Solís

Recéndez

Equivalencias lógicas

Dos proposiciones compuestas P y Q se consideran lógicamente equivalentes si

tienen los mismos valores de verdad para cada opción de los valores de verdad de las

variables p, q, etc. Cuando esto ocurre escribimos P ⇔ Q, ya que P ↔ Q tiene los valores

de verdad verdaderos precisamente cuando los valores de P y Q coinciden

P ⇔ Q si y sólo si P ↔ Q es una tautología

Sean p, q y r proposiciones, C una contradicción y T una tautología.

( ) ( )

( ) ( )

( ) ( )

[( ) ] [ ( )] [ ]

[( ) ] [ ( )] [ ]

[ ( )] [( ) ( )]

[ ( )] [( ) ( )]

( )

( )

( )

( )

( )

( )

( )

( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

b (p q) (p q)

p q p q

p q q p

d p q p q

c p q p q

b p q p q

a p q p q

C

p T

p

C

T T

p

p

p

p q r p q p r

p q r p q p r

b r p q r p q r

r p q r p q r

c p q q p

b p q q p

a p q q p

p p

→ ⇔¬ ∧¬

→ ⇔ ¬ ∨

→ ⇔ ¬ →¬

⎪ ⎪

⎭

⎪ ⎪

⎬

⎫

∧ ⇔¬ ¬ ∨ ¬

∨ ⇔¬ ¬ ∧¬

¬ ∧ ⇔ ¬ ∨ ¬

¬ ∨ ⇔ ¬ ∧¬

∧¬ ⇔

∨ ¬ ⇔

⎪ ⎪

⎭

⎪ ⎪

⎬

⎫

∧ ⇔

∧ ⇔

∨ ⇔

∨ ⇔

⎭ ⎬ ⎫

∧ ⇔

∨ ⇔

⎭ ⎬ ⎫

∧ ∨ ⇔ ∧ ∨ ∧

∨ ∧ ⇔ ∨ ∧ ∨

⎭ ⎬ ⎫

∧ ∧ ⇔ ∧ ∧ ⇔ ∧ ∧

∨ ∨ ⇔ ∨ ∨ ⇔ ∨ ∨

⎪ ⎭

⎪ ⎬

⎫

↔ ⇔ ↔

∧ ⇔ ∧

∨ ⇔ ∨

¬¬ ⇔

10 )

10a)

9) contrapositiva

leyes de De Morgan

8 )

8 )

8 )

8 )

7b) p p

7a) p

leyes de identidad

6d) p T

6c) p C

6b) p

6a) p C

leyes de idempotencia

5b) p p

5a) p p

leyes distributivas

4b)

4a)

leyes asociativas

3 ) p q

3a) p q

leyes conmutativas

2 )

2 )

2 )

1. doble negación

MCC Blanca Esthela Solís Recéndez

( ) ( )

( ) ( )

[( ) ( )] [( ) ]

[( ) ( )] [ ( )]

( ) [( ) ( )]

[( ) ] [ ( )]

15)(p q) [( ) ] reducción al absurdo

14) ley de exportación

13) equivalencia

12 )

12 )

11 )

11 )

p q C

p q r p q r

p q p q q p

b p q p r p q r

a p r q r p q r

b p q p q

a p q p q

→ ⇔ ∧ ¬ →

∧ → ⇔ → →

↔ ⇔ → ∧ →

→ ∧ → ⇔ → ∧

→ ∧ → ⇔ ∨ →

∧

...