LICENCIATURA EN INFORMÁTICA

ADMINISTRATIVA I.Q. Iván de Jesús Vilchis

Cuessi

MATEMÁTICAS BÁSICAS (DISCRETAS) Lógica Matemática

CONECTIVAS BÁSICAS En el desarrollo de cualquier teoría, se hacen afirmaciones en forma de oraciones. Tales afirmaciones, llamadas enunciados (o proposiciones), son oraciones declarativas que son verdaderas o falsas (pero no ambas).

Por ejemplo, las siguientes son proposiciones y, para representarlas, utilizaremos las letras minúsculas (como p, q y r). p: Matemáticas discretas es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa q: Margaret Mitchell escribió “Lo que el viento se llevó” r: 2 + 3 = 5

Por otro lado, no consideramos como proposiciones algo como la exclamación (¡Que bonita tarde!) o el mandato (Levántate y haz tus ejercicios)

CONECTIVAS BÁSICAS Las proposiciones anteriores, representadas por las letras mencionadas anteriormente, se consideran proposiciones primitivas, ya que no hay forma de descomponerlas en algo más sencillo. Es posible obtener nuevas proposiciones, a partir de otras existentes, de dos maneras.

1. Transformando una proposición p en la proposición ¬p, que denota su negación y se lee como “no p”.

Para la proposición anterior p, ¬p es la proposición “Matemáticas discretas no es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa”. (No consideramos la negación de una proposición primitiva como una proposición primitiva).

CONECTIVAS BÁSICAS2. Combinando dos o más proposiciones en una proposición compuesta mediante las

siguientes conectivas lógicas. a) Conjunción La conjunción de dos proposiciones p, q se detona como p q, que se lee como “p y q”. En nuestro ejemplo, la proposición compuesta p qse lee como: “Matemáticas discretas es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa y Margaret Mitchell escribió Lo que el viento se llevó”.

b) Disyunción La expresión p q denota la disyunción de cualquier par de proposiciones p, qy se lee como “p o q”. En nuestro ejemplo, la proposición compuesta p q se lee como: “Matemáticas discretas es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa o Margaret Mitchell escribió Lo que el viento se llevó” es la traducción verbal p q cuando p, q son las proposiciones ya mencionadas. Usamos la palabra “o” en el sentido inclusivo. En consecuencia p q es verdadero si una o la otra o ambas proposiciones p, q son verdaderas. La proposición compuesta p y q es verdadera si una u otra, pero no ambas proposiciones son verdaderas. Una forma de expresar p q para este ejemplo es “Matemáticas discretas es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa o Margaret Mitchell escribió Lo que el viento se llevó, pero no ambos”

CONECTIVAS BÁSICASc) Implicación Decimos que “pimplica q” y escribimos p q para designar la proposición que es la implicación de ppor q. En forma alternativa, podemos decir:

i. Si p, entonces qii. p es suficiente para qiii. p es una condición suficiente para qiv. p sólo si qv. q es necesario para pvi. q es una condición necesaria para p

Una traducción verbal de p qusando nuestro ejemplo es “Sí Matemáticas discretas es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa, entonces Margaret Mitchell escribió Lo que el viento se llevó”. La proposición p se conoce como la hipótesis de la implicación, y q como la conclusión. Cuando se combinan las proposiciones de esta forma, no es necesario que haya una relación causal entre las proposiciones que la implican que sea verdadera.

CONECTIVAS BÁSICASd) Bicondicional La bicondicional de dos proposiciones p, q se denota como p q , lo cual se lee como “p si y sólo si q” o “p es necesario y suficiente para q”. Para las proposiciones p y q dadas en el ejemplo, “Matemáticas discretas es un curso obligatorio para el segundo cuatrimestre de la carrera de Licenciatura en Informática Administrativa si y sólo si Margaret Mitchell escribió Lo que el viento se llevó”.

CONECTIVAS BÁSICAS

Conectivas

Negación

Conjunción

Disyunción (“o” inclusivo)

Disyunción (“o” exclusivo)

Implicación

Doble implicación (bicondicional)

Símbolos Auxiliares Para evitar ambigüedades

CONECTIVAS BÁSICAS (CRITERIOS PARA CONSTRUCCIÓN DE TABLA DE VERDAD) Para definir con precisión el significado de los símbolos que representan las distintas conectivas, debemos conocer con precisión el significado de dichas conectivas.

Consideremos una a una todas las conectivas:Negación Sea A un enunciado, denotaremos por ¬ A a su negación. Si A toma el valor verdadero (falso) entonces ¬A tomará el valor falso (verdadero) siendo irrelevante el significado de A. Esto se puede describir mediante la tabla de verdad:p

V F

F V 𝑓 ¬ (𝑉 )=𝐹

Esta conectiva ¬ da lugar a una función f del conjunto {V, F} en si mismo definida por f:

𝑓 ¬ (𝐹 )=𝑉

CONECTIVAS BÁSICAS (CRITERIOS PARA CONSTRUCCIÓN DE TABLA DE VERDAD)Conjunción Sean A y B dos enunciados, denotamos por A ∧ B a la conjunción de ambos. Su tabla de verdad depende de los valores de verdad que tomen A y B.

Esta conectiva ∧ nos define una función del conjunto {V, F} en si mismo definida por f:p q p q

V V V

V F F

F V F

F F F

𝑓 ¬ (𝑉 ,𝑉 )=𝑉

𝑓 ¬ (𝑉 ,𝐹 )=𝐹

𝑓 ¬ (𝐹 ,𝑉 )=𝐹

𝑓 ¬ (𝐹 ,𝐹 )=𝐹

CONECTIVAS BÁSICAS (CRITERIOS PARA CONSTRUCCIÓN DE TABLA DE VERDAD)Disyunción Sean A y B dos enunciados. En castellano tenemos dos usos distintos para la disyunción “o”, elegimos “A o B o ambos” para nuestra disyunción que denotamos por A ∨ B. Su tabla de verdad será:

p q p q

V V V

V F V

F V V

F F F

𝑓 ∨ (𝑉 ,𝑉 )=𝑉

𝑓 ∨ (𝑉 ,𝐹 )=𝑉

𝑓 ∨ (𝐹 ,𝑉 )=𝑉

𝑓 𝑉 (𝐹 ,𝐹 )=𝐹

De nuevo tenemos una función de verdad con dos argumentos:

Nótese que el otro uso de la disyunción “A o B pero no ambas” se puede simbolizar mediante:

(A ∨ B) ∧ [¬ (A ∧ B)]

CONECTIVAS BÁSICAS (CRITERIOS PARA CONSTRUCCIÓN DE TABLA DE VERDAD)Condicional Sean A y B dos enunciados, Denotaremos por A → B para representar el enunciado “A implica B” o “si A entonces B”. Ahora el castellano no nos ayudará a construir una tabla de verdad.

p q

V V V

V F F

F V V

F F V

𝑓 → (𝑉 ,𝑉 )=𝑉

𝑓 → (𝑉 ,𝐹 )=𝑉

𝑓 → (𝐹 ,𝑉 )=𝐹

𝑓 → (𝐹 ,𝐹 )=𝑉

De nuevo tenemos una función de verdad con dos argumentos:

Lo extraño de esta tabla es la asignación del valor V cuando p toma el valor F. Nótese que en matemáticas este tipo de enunciados no nos dicen nada a partir de la falsedad de A.

CONECTIVAS BÁSICAS (CRITERIOS PARA CONSTRUCCIÓN DE TABLA DE VERDAD)Bicondicional Sean A y B dos enunciados. Denotamos el enunciado “A si y sólo si B” o “A equivale a B” por A ↔B.

p q p q

V V V

V F F

F V F

F F V

𝑓 ↔ (𝑉 ,𝑉 )=𝑉

𝑓 ↔ (𝑉 ,𝐹 )=𝐹

𝑓 ↔ (𝐹 ,𝑉 )=𝐹

𝑓 ↔ (𝐹 ,𝐹 )=𝑉

De nuevo tenemos una función de verdad con dos argumentos:

En lo que sigue veremos que el valor de verdad de una forma enunciativa compuesta depende de los valores de verdad de los enunciados simples o de las variables de enunciado que la formen.

FÓRMULAS ENUNCIATIVAS Una fórmula es una secuencia de caracteres, pero es precioso delimitar de la totalidad de combinaciones posibles de caracteres aquellas que sean como “bien formadas”, para ello , se da una definición de lo que es una fórmula bien formada (fbf):

1. Una letra enunciativa es una fbf.2. Toda fbf a la cual se antepone el símbolo “¬” (negación) es una

fbf.3. Si A y B son fbfs, entonces también lo son las secuencias (A B),

(A B), (A B)y (A B).4. Toda secuencia de caracteres producida por la aplicación de los

pasos 1,2,3, en cualquier orden, constituye una fbf. 5. Ninguna otra secuencia constituye una fbf.

REGLA DE FORMACIÓN DE FÓRMULAS Para abreviar se siguen las siguientes directrices:Omisión de paréntesis externos.Prioridad entre conectivas: Asociatividad de la implicación: Asocia a la derecha

TABLAS DE VERDAD Las tablas de verdad representan todos los posibles valores veritativos de las fórmulas básicas, es decir, que las tablas de verdad son una representación de las funciones.

Para hallar la tabla de verdad de cualquier fórmula hay que dar los siguientes pasos:

1. En primer lugar, se asignan los valores 1 y 0 a las proposiciones simples que componen la fórmula, combinando de todos los modos posibles tales valores.

Recordemos que para una fórmula con dos proposiciones distintas, las combinaciones posibles de sus valores de verdad son

p q

1 1

1 0

0 1

0 0

TABLAS DE VERDAD Para una fórmula de tres proposiciones distintas, las combinaciones posibles de sus valores de verdad son . Con cuatro proposiciones , etcétera.

p q r

1 1 1

1 1 0

1 0 1

1 0 0

0 1 1

0 1 0

0 0 1

0 0 0

p q r s

1 1 1 1

1 1 1 01 1 0 11 1 0 01 0 1 11 0 1 01 0 0 11 0 0 00 1 1 1

0 1 1 00 1 0 10 1 0 00 0 1 10 0 1 00 0 0 10 0 0 0

El modo más fácil de combinar los valores de verdad de las proposiciones que integran a cualquier fórmula, consiste en asignarle a la proposición por orden alfabético la mitad de uno y la mitad de cero.

A la siguiente proposición, la mitad de la mitad de uno, la mitad de la mitad de cero, hasta completar el número de las combinaciones que permita la fórmula. Y a la ultima proposición de la fórmula siempre se le asignará uno y cero alternativamente hasta completar las combinaciones posibles de la fórmula.

TABLAS DE VERDAD2. Y en segundo lugar, se hallan los valores

de verdad de las conectivas existentes en la fórmula, empezando por las menos dominantes (es decir, por las que afectan a menor parte de la fórmula) y terminando por la conectiva dominante (es decir, por aquella que afecta a toda la fórmula y cuya tabla de verdad, por tanto, será la tabla de verdad de la fórmula completa).

Ejemplos: Tabla de verdad de la fórmula: … se lee “Si no p, entonces r y no q”. La conectiva dominante es el “”

p q r

1 1 1 0 0 0 1

1 1 0 0 0 0 1

1 0 1 1 1 0 1

1 0 0 1 0 0 1

0 1 1 0 0 1 0

0 1 0 0 0 1 0

0 0 1 1 1 1 1

0 0 0 1 0 1 0

TABLAS DE VERDAD De manera más abreviada, la anterior tabla de verdad también se podría escribir así:

p q)

0 1 1 1 0 0 1

0 1 1 0 0 0 1

0 1 1 1 1 1 0

0 1 1 0 0 1 0

1 0 0 1 0 0 0

1 0 0 0 0 0 1

1 0 1 1 1 1 0

1 0 0 0 0 1 0

FORMAS NORMALES Llamaremos forma enunciativa restringida a una forma enunciativa en la que sólo aparecen las conectivas ¬, ∧ y ∨

Proposición 1.1. Toda función de verdad es la función de verdad determinada por una forma enunciativa restringida.

Corolario 1.1. Toda forma enunciativa, que no es una contradicción, es lógicamente equivalente a una forma enunciativa restringida de la forma:

Donde cada Qijjes una variable de enunciado o la negación de una variable de enunciado. Esta forma se llama forma normal disyuntiva.

FORMAS NORMALES Corolario 1.2. Toda forma enunciativa, que no es una tautología, es lógicamente equivalente a una forma enunciativa restringida de la forma:

Donde cada Qijjes una variable de enunciado o la negación de una variable de enunciado. Esta forma se llama forma normal conjuntiva.