UNIVERSIDAD FERMIN TORO

ESCUELA DE INGENIERIA

CABUDARE ESTADO LARA

ESTRUCTURA DISCRETA

CALCULO PROPOSICIONAL

ALEXXAVIER BARCO

OCTUBRE 2013

1

lógica proposicional:

Lenguaje

Es una construcción a partir de ciertas unidades llamadas signos (marcas –

letras) a partir de las cuales se construyen expresiones (sucesión finita de signos sin

significado) y entre las cuales se destacan las fórmulas bien formadas (expresiones con

significado)

Observación: el lenguaje en conjunción con axiomas y reglas de inferencia constituyen

lo que se denomina un sistema deductivo formal (sintaxis)

Lenguaje de la lógica proposicional:

Consta de:

Alfabeto de signos:

o Variables proposicionales: p, q, r, s,… (simbolizan proposiciones simples)

o Conectivos lógicos u operadores lógicos: negación (¬), disyunción no

excluyente (∨), conjunción (∧), condicional (→) y bicondicional (↔) entre otros

enlazan variables proposicionales para formar formas proposicionales

compuestas.

o Signos auxiliares: true (constante de verdad), false (constante de falsedad), “(“,

“)” (paréntesis).

Fórmulas proposicionales (fórmulas bien formadas, definidas en forma inductiva)

Notación: A, B, C, … (letras metalingüísticas)

o Las variables proposicionales son fórmulas bien formadas (base de la

definición).

o Si A y B son fórmulas proposicionales entonces: ¬ A, (A ∧ B), (A ∨ B), (A → B)

y (A ↔ B) son fórmulas proposicionales (paso inductivo).

2

o El conjunto de fórmulas proposicionales (F) es el generado por las reglas

anteriores (cláusula de cierre).

1) Dadas p y q: variables proposicionales, indicar cuáles de las siguientes expresiones

son fórmulas bien formadas:

a) p ∨ q b) (p ∨ q)

c) p ∨ q → r d) (p ∨ q) → r

e) ((p ∨ q) → r) f) (true ↔ p)

g) (p → ¬ p → q) h) p = q

2) Eliminar los paréntesis innecesarios de las siguientes fórmulas bien formadas

(fórmulas proposicionales) según criterios de reducción de paréntesis:

a) (((¬ p) ∧ q) → ¬ (p ∨ (r ∧ q)))

b) (¬ (((p ∧ q) ∨ (q ↔ r)) → (((¬ p) ∨ q) ↔ (p ∨ (¬ r)))))

c) ((p ∧ ((¬ p) ↔ q)) → ((¬ q) ∧ (¬ (p ∧ q))))

Observación:

La eliminación de paréntesis está sujeto a los siguientes criterios de reducción de

paréntesis:

o se pueden eliminar los paréntesis externos.

o la precedencia de asociación de conectivos es: ¬, ∧, ∨, →, ↔ (alcance de

conectivos).

3

o si un conectivo se usa repetidamente, se asocia según la siguiente tabla de

asociatividad:

3) Indicar los árboles de análisis (o árboles de formación) de las fórmulas

proposicionales dadas en el ejercicio anterior.

Observación:

Tener en cuenta las siguientes reglas de inscripción:

A¬ BA∗

A¬

A

A, B: fórmulas proposicionales

∗: conectivo binario

Semántica de la lógica proposicional:

Hasta ahora las fórmulas proposicionales son meras combinaciones de símbolos que

responden a ciertas reglas de formación pero sin sentido alguno. Ahora se dotará al

lenguaje de un poder de expresión a través de una interpretación. La semántica hace

referencia fundamentalmente a la manera en que se asignan valores de verdad a las

expresiones del cálculo.

∧ izquierda

∨ izquierda

→ derecha

↔ derecha

4

A B

Semántica clásica (lógica bivaluada o bivalente – semántica basada en tablas de verdad)

Hay dos valores de verdad posible: verdadero (V - 1) y falso (F - 0)

El valor de verdad de una fórmula proposicional depende del valor de verdad de las

variables proposicionales que intervienen en la fórmula.

p ¬ p0 11 0

4) Analizar si las siguientes oraciones son proposiciones.

el signo se interpreta comotrue 1false 0

¬ “no” y se llama negación

∧ “y” y se llama conjunción

∨ “o” (no excluyente) y se llama disyunción

→ “si…entonces” y se llama condicional

↔ “….si y sólo si…” y se llama condicional

p q p ∧ q p ∨ q p → q p ↔ q0 0 0 0 1 10 1 0 1 1 01 0 0 1 0 01 1 1 1 1 1

5

a) Prolog. es un lenguaje declarativo basado en las reglas de la lógica.

b) ¿Vienes hoy a clase?

c) Visite las playas de Pinamar.

d) Visité las playas de Pinamar.

e) 5 es múltiplo de 2.

f) Pascal es un lenguaje de procedimientos.

g) Si Borges no hubiera nacido, Sábato sería el mejor escritor argentino.

h) x + 4 = 10.

i) Hay números enteros que satisfacen la ecuación x +4 = 10.

j) Si estudias hoy podrás salir mañana.

k) En la última década ha habido un creciente énfasis en el uso de métodos formales

para el desarrollo de sistemas hardware y software.

5) Asignar letras a las proposiciones simples (átomos) y expresar, mediante el uso de

conectivos, las siguientes proposiciones:

a) Iré al médico aunque me siento bien.

b) No serán sancionados si la notificación llegó con retraso y tampoco serán

sancionados si tienen justificativo médico.

c) No cometió el crimen si no pudo comprar un revolver.

6

d) El cuadro es de valor de verdad si solo tiene por lo menos 600 años.

e) Es suficiente que deje de fumar para que mi rendimiento físico mejore.

f) Es necesario que deje de fumar para que mi rendimiento físico mejore.

g) Es necesario y suficiente que no tenga deudas para que salga de garante.

6) Construir las tablas de verdad de las siguientes fórmulas proposicionales:

a) (p ∧ ¬ q) → ¬ q

b) (p ∨ q) ↔ p

c) ¬ (¬ p ∧ ¬ q) ∧ (¬ p → ¬ q)

d) p ∧ (p ∨ q) ↔ p

e) p → p ∨ q

f) ¬ (p ↔ q) ↔ (p ∨ ¬ q)

Observaciones:

O1) Una fórmula proposicional es una tautología o ley lógica ó verdad lógica, si para

toda asignación de valores de verdad de las componentes simples resulta ser verdadera.

Si para toda asignación resulta ser falsa, es una contradicción. Finalmente una fórmula

que no es ni tautología ni contradicción, es una contingencia.

7

Dado el condicional: A → B, además del giro idiomático asociado; “Si A entonces B”

otros giros asociados son:

A sólo si BB si AA es condición suficiente para BB es condición necesaria para A

O2) Si un condicional (A → B) o (A ⊃ B) es tautológico, se dice que el antecedente

implica lógicamente el consecuente. Se indica: (A ⇒ B)

03) Si un bicondicional (A ↔ B) es tautológico, se dice que una de sus componentes

equivale lógicamente a la otra. Se indica: (A ⇔ B) o (A ≡ B)

7) Determinar el valor de verdad de las siguientes fórmulas proposicionales a partir de

la siguiente valuación: v(p) = v(s) = V y v(q) = v(r) = F

a) (p ∨ q) ∧ r

b) (¬ p) ∨ ((¬ (q ∧ s)) ∧ r ∧ s)

c) (q ∨ s) ∧ (r → s)

8) Dada la fórmula A : (r ∧ (¬ p)) → (¬ q)

a) Si v(A) = V, v(q) = V y v(p) = F, hallar v(r)

b) Si v(A) = F, v (r) = V y v(p) = F, hallar v(q)

9) Justificar si la información indicada es suficiente, en cada caso, para determinar el

valor de verdad de la fórmula proposicional indicada:

a) (p ∧ q) → (p ∨ r) v (p) = V y v(r) = F

b) ((¬ p) ∧ (¬ q )) ↔ (p ∨ q) v (p) = V

c) (p → q) ∧ r v (r→ p) = V

Semántica basada en el concepto de satisfactibilidad

8

Una valuación (v) es una función que asigna valores de verdad a las variables proposicionales: v: V →{0, 1}(V: conjunto de variables proposicionales que intervienen en la fórmula proposicional dada)

Dada una valuación (v) y una fórmula proposicional A, se define que “v satisface A” y

se indica v ⊨ A en forma inductiva:

En función de esto se dice que:

10) Obtener una fórmula proposicional más simple equivalente a la dada en cada caso.

Indicar las leyes lógicas aplicadas:

a) ¬ (¬ p ∧ ¬ q) ∧ (¬ p → ¬ q)

b) ¬ (¬ (p→ ¬ q ) ∧ ¬ (q→ ¬ p)

c) ((p ∧ q) ∨ (¬ p ∨ q)) ∧ p

9

v ⊨P si v (P) = 1v ⊨ truev ⊭ false (no es cierto que v ⊨ false)v ⊨ A ∧ B sii v ⊨ A y v ⊨ Bv ⊨ A ∨ B sii v ⊨ A o v ⊨ Bv ⊨ A → B sii v ⊭A o v ⊨ Bv ⊨ A ↔ B sii (v ⊨ A sii v ⊨ B)

A es tautologia si toda valuación v la satisface (v ⊨ A, cualquiera sea v) se indica ⊨ A

A es contradicción si ninguna valuación v la satisface (v ⊭ A, cualquiera sea v) A es contradicción si A ni es tautología ni es contradicción (alguna valuación la satisface y alguna no)

d) ((p ∧ (q ∨ ¬ q) ∧ (¬ r ∨ r)) ∨ p ∨ (¬ r)

11) Verificar que las siguientes fórmulas son tautológicas mediante el uso de leyes

lógicas:

a) ((p ∧ q) → r) y (p → (q → r))

b) ((p ∨ q) → r) y ((p → r) ∧ (q → r))

12) Ídem 11) pero a través de una “tabla simplificada”:

a) (p ∨ (q → ¬ r)) ∨ (¬ p ↔ q)

b) ((p → q) ∨ (q → p)) ↔ ((p ∧ q) → (p ∨ q)

Observación:

A los efectos de analizar si una fórmula proposicional es tautologia, contradicción o

contingencia, en lugar de hacer una tabla completa, se puede hacer una tabla

simplificada o abreviada. La misma consiste :

en el caso de que sea tautología en descartar la posibilidad de que la tabla arroje

algún resultado falsoen el caso de que sea contradicción en descartar la posibilidad de que la tabla arroje

algún resultado verdaderoen el caso de que sea contingencia en mostrar una valuación que satisfaga la

fórmula y otra que no la satisfaga

13) Determinar la relación de fuerza entre los siguientes pares de fórmulas:

10

a) true, false b) (p ∧ q) →(p ∨ q) c) true, true d) false, false

e) p,(p ∧ q) f) p,(p ∨ q) g) p, (p →q) h) (p↔q), (p →q)

¿ Hay una fórmula más fuerte que todas las demás?

¿ Hay una fórmula más débil que todas las demás?

14) Factorizar y reducir las siguientes fórmulas proposicionales:

a) (p ∧ q ∧ r) ∨ (p ∧ q) ∨ (p ∧ (¬ r))

b) (p ∧ q) ∨ (p ∧ r) ∨ (p ∧ (q ∨ (¬ r))

c) ((¬ p) ∨ r) ∧ ((¬ p) ∨ (¬ r))

15) Hallar en cada caso una fórmula proposicional, cuya tabla de verdad arroje el

resultado indicado, en su forma normal disyuntiva (FND) o bien en su forma normal

conjuntiva (FNC), según convenga.

p q r f (p ,q, r) g (p ,q, r) h (p ,q, r)0 0 0 1 1 00 0 1 1 0 00 1 0 0 0 10 1 1 0 1 11 0 0 1 1 01 0 1 0 1 11 1 0 0 1 01 1 1 0 1 1

11

Así como dada una fórmula proposicional se puede confeccionar una única tabla de verdad correspondiente (salvo el orden en que arman las filas), dada una tabla de verdad arbitraria, se puede hallar una fórmula proposicional (standard) asociada a la misma

Se dice que una fórmula proposicional A es más fuerte que una fórmula B (o que A fuerza B) cuando ⊨ A → B

16) Hallar una fórmula proposicional equivalente a la dada usando sólo los conectivos

de los siguientes conjuntos adecuados de conectivos: {∼, ∧, ∨}, {↓}, {}

a) ((p → q) ∨ (∼p)) ∧ (∼(p ∧ q))

b) (p ↔ q) ∨ (∼(∼p ∧ q))

c) (p ∨ q) ∧ (∼(p → q))

Observaciones:

O1) Se dice que {∼, ∧, ∨} es un conjunto adecuado o completo de conectivos ya que

toda proposición compuesta se puede expresar usando únicamente los conectivos de

dicho conjunto

O2) Se puede decir lo mismo de los conjuntos {∼, ∧}; {∼, ∨} y {∼, →}

Observación: los giros idiomáticos que caracterizan a las operaciones NOR y NAND,

tienen que ver con las equivalencias:

(p ↓ q) ≡ ¬ (p ∨ q) ≡ ¬ p ∧ ¬ q

(p | q) ≡ ¬ (p ∧ q) ≡ ¬ p ∨ ¬ q

12

Hay dos conectivos que merecen especial atención por las consecuencias en el diseño y estudio de computadoras.Estos son el conectivo NOR (negación de disyunción), denotado por ↓ y caracterizado por el giro idiomático “ni ...ni” (negación conjunta) y el conectivo NAND (negación de conjunción), denotado por | y caracterizado por el giro idiomático “o no... o no...” (negación alternativa).

y llevan naturalmente a las tablas:

17) Demostrar, en la forma indicada, que los siguientes condicionales son verdaderos:

en forma directa:

a) Si un número entero es múltiplo de 6 entonces dicho número es múltiplo

de 2 y múltiplo de 3.

b) El producto de dos enteros impares es impar.

en forma indirecta o por contrarecíproco:

1. Si el cuadrado de un número entero es impar, dicho número es impar

2. Si al multiplicar un número entero por cinco y a dicho resultado se le

suma tres se obtiene un entero par, el número dado es impar.

por absurdo:

1. Si un número entero es menor que otro, necesariamente el primero es menor

o igual que el sucesor del segundo.

2. Un número entero es impar sólo si su sucesor es par.

p q p ↓ q p | q0 0 1 10 1 0 11 0 0 11 1 0 0

13

18) Refutar las siguientes afirmaciones:

a) la suma de dos naturales pares es un natural impar.

b) el producto de dos naturales impares es un natural par

c) La suma de dos múltiplos de 3 es un número par.

d) La suma de un múltiplo de 3 y de un múltiplo de 2 nunca es múltiplo de 3.

19) Demostrar o refutar (según corresponda) las siguientes afirmaciones:

a) Si un número natural es múltiplo de 100 entonces es múltiplo de 10.

b) Si un número natural es múltiplo de 10 entonces es múltiplo de 100.

c) Si n = 3 k + 2 con k ∈ N , entonces n es impar.

d) Si n = 3 k + 2 con k ∈ N , entonces n es divisible por 3.

e) Si n = 3 k + 2 con k ∈ N , entonces n es divisible por 2.

14