Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2001

Práctica 1

Fecha sugerida de finalización: 5/4/2001

Primera Parte: Lógica Proposicional

Alfabeto

·       Variables proposicionales: p, q, r, s, …

·       Conectivos lógicos: Ø (negación), Ù (conjunción), Ú (disyunción), Þ (implicación), º (equivalencia).

·       Símbolos auxiliares: ( (paréntesis abierto), ) (paréntesis cerrado).

Expresión

Lista finita de símbolos del alfabeto.

Expresiones bien formadas

Una expresión a es una expresión bien formada, a la que podemos llamar también fórmula bien formada o fórmula, si se cumple que:

·       a es una variable proposicional; o

·       a es de la forma Øb, y b es una fórmula; o

·       a es de la forma (b Ù g), o de la forma (b Ú g), o de la forma (b Þ g), o de la forma (b º g), y b y g son fórmulas.

Ejercicio 1

Utilizando las definiciones anteriores: ¿Cuáles de la siguientes expresiones son fórmulas? (p, q son variables proposicionales)

i.                     Øp

ii.                    Ø(p)

iii.                  (Øp)

iv.                  p Ú q

v.                   p Ú q)

vi.                  (p Ú q)

vii.                Øp Ù

viii.               Øp Ù q

ix.                   (Øp Ù q)

x.                    p q

xi.                   (p Û q)

xii.                 p + q

Convenciones de notación

Las convenciones de notación son reglas que se utilizan, simplemente, por una cuestión de comodidad. Ellas son:

·       No es necesario escribir paréntesis exteriores. Ejemplo: escribir p Þ (q Þ r) en lugar de (p Þ (q Þ r)).

·       Sea * el conectivo para la disyunción, conjunción o implicación. La expresión a₁ * a₂ * … * a_n representa la fórmula (a₁ * (a₂ * (… * a_n))).

Precedencias

Teniendo en cuenta que el orden de precedencias entre los símbolos es:

Ø (negación)

Ù (conjunción) Ú (disyunción)

Þ (implicación)

º (equivalencia)

se pueden omitir paréntesis cuando no haya ambigüedades.

Ejemplos:

·       p Þ q Ù r       representa             (p Þ (q Ù r))

·       p Þ q º r        representa             ((p Þ q) º r)

·       p Ú q Ù r         no representa una fórmula porque no hay precedencia entre Ù y Ú. En este caso se presenta una ambigüedad.

Ejercicio 2

¿Cuáles de las expresiones del ejercicio 1 son fórmulas teniendo en cuenta las convenciones de notación?

Valuación

Una valuación es una asignación de valores de verdad a las variables proposicionales. La podemos ver como una función que recibe un nombre de variable y devuelve un valor de verdad. Una vez fijada una valuación, se puede determinar el valor de verdad de una fórmula aplicando las tablas de verdad de los conectivos.

Ejercicio 3

Dada una valuación m tal que m(a), m(b) y m(c) son verdaderas, y m(x) y m(y) son falsas, determinar el valor de verdad de las siguientes proposiciones para dicha valuación:

i.                     Øa Ú b

ii.                    (c Ú y) Ù (x Ú b)

iii.                  c Ú (y Ù x) Ú b

iv.                  (c Ú y) Ù (x Ú b) º c Ú (y Ù x) Ú b

v.                   Ø(c Ú y)

vi.                  Øc Ù Øy

vii.                Ø (c Ú y) º Øc Ù Øy

Tautología

Una fórmula b es una tautología si y sólo si b es verdadera para toda posible asignación de valores de verdad a las variables proposicionales que aparecen en b.

Contradicción

Una fórmula b es una contradicción si y sólo si b es falsa para toda posible asignación de valores de verdad a las variables proposicionales que aparecen en b.

Contingencia

Una fórmula b es una contingencia si y sólo si b no es una tautología ni una contradicción, es decir, su valor de verdad depende de los valores de verdad que tomen sus variables proposicionales.

Ejercicio 4

Determinar, utilizando tablas de verdad, si las siguientes fórmulas son tautologías, contradicciones o contin­gen­cias.

i.                     Øp

ii.                    p Ú Øp

iii.                  p Ù