Lógica computacional

Índice
Unidad I Lógica Matemática
1.1 1.2 1.3 1.4 1.5 1.6 1.7 Lógica y Lenguaje ¿Qué es lógica? Verdad y validez Funciones de verdad y tablas de verdad Proposiciones Lógica y lingüística Reglas de deducción natural 7 7 8 8 6 6 6

Unidad II Conjuntos
2.1 2.2 2.3 2.4 2.5 Operaciones básicas Conjuntos finitos y conjuntos infinitos Subconjuntos Producto cartesiano Funciones 8 9 10 10 10Unidad III Lenguaje preposicional
3.1 3.2 3.3 Preposiciones simples y compuestas Términos de enlace de preposiciones Simbolización de preposiciones y de los términos de enlace 3.4 Tipos de preposiciones (conjunción, negación, disyunción, condicional y bicondicional) 12 12 11 11

Unidad IV Formulas lógicas
4.1 4.2 4.3 Valores de certeza Tablas de verdad de las preposiciones Tautología 13 13 154.4 4.5 4.6

Contradicción Reglas de inferencia Inferencias validas y no validas

16 16 16

Unidad V Relaciones
5.1 5.2 5.3 Relaciones binarias Relaciones de equivalencia Clases de equivalencias y particiones 16 17 17

Unidad VI Funciones
6.1 6.2 6.3 6.4 6.5 6.6 6.7 Composición de funciones Clases de funciones Inyectivas Suprayectivas Biyectivas Funciones inversas Funciones localizadoras19 19 18 19 18 18 18

Unidad VII Teoría de grafos
7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 Nodos Ramas y lazos Valencia Caminos Ramas paralelas Grafos simples Grafos de similaridad Grafos bipartidos y grafos completos 21 21 19 20 20 20 21 21

2

Unidad VIII Representación matricial de grafos
8.1 8.2 8.3 8.4 Ramas sucesivas de longitud n Matriz de adyacencia e incidencia Caminos Caminos simples 2222 23 23

Unidad IX Grafos conexos
9.1 9.2 Camino de Euler y Hamilton Componente de un grafo 23 24

Unidad X Grafos ponderados
10.1 10.2 10.3 Longitud de un camino El camino más corto Dos problemas clásicos (El problema de lo puentes de Königsberg y el problema de la locura instantánea) 10.4 10.5 10.6 10.7 Grafos isomorfos Grafos planos Grafos homeomorfos Teoremas de Kuratowski y de Euler 2625 26 24 25 24 24

Biliografia

27

3

Objetivo

Empleará los conceptos fundamentales de la lógica computacional, con el fin de aplicarlos posteriormente en la resolución de problemas de programación y análisis de sistemas.

4

UNIDAD 1. LÓGICA MATEMÁTICA
1.1 Lógica y lenguaje Hoy día se considera una única ciencia lógico-matemática cuya expresión más importante en el campo de laciencia es la creación de modelos gracias sobre todo a la aplicación técnica en los circuitos lógicos que hacen posible la informática y el cálculo numérico. La lógica matemática guarda estrechas conexiones con las ciencias de la computación y la lógica filosófica. 1.2 ¿Qué es lógica? La lógica toma, desde años atrás muchos significados, siendo Aristóteles el primero en utilizar esta palabra,para referirse a la razón. La lógica pretende ser el instrumento con el cual discernir cuándo una argumentación es válida. 1.3 Verdad y validez Por lo común la gente suele confundir un argumento válido con uno verdadero. Son cosas distintas, aunque estén relacionadas. Así, la lógica no pretende ver si una afirmación es o no cierta, sino si es válida o no. Un ejemplo de esto seria. El perro maúlla.Esto es falso El perro tiene tres patas. Esto es válido puesto que por un accidente pudo haber perdido la otra pata.

5

1.4

Funciones de verdad y tablas de verdad Una función de verdad es una función de un conjunto de valores de

verdad a otro conjunto de valores de verdad. Como en lógica solamente tenemos dos valores una fórmula solamente puede ser verdadera o falsa. Las tablas de verdadse utilizan para analizar la estructura de las proposiciones compuestas así como el valor de verdad de las mismas, también se utiliza para demostrar la validez de cierto tipo de razonamiento deductivo 1. Entre las más conocidas están las de: Conjunción, Disyunción, Condicional y Bicondicional. 1.5 Proposiciones Una proposición o enunciado es una oración que puede ser falso o verdadero pero no...