T1 Lógica prop Flashcards
Proposición lógica
Sentencia que puede ser V o F
las proposiciones se pueden componer de…
conectores lógicos
p^q
Conjunción ,(i), ambas son 1
pvq
Disyunción (o), alguna
p(+)q
Disyunción exclusiva, solo una de ellas
p→q
Implicación, solo no lo es cuando p es verdadera y q no
p ⇔q
Doble implicación, equivalentes
Proposición atómica
Proposición que no se puede descomponer en otras
Importancia de mayor a menor, los conectores
negación, disy y conj, implicación, equivalencia
Tablas de Verdad
Forma de expresar V(1) o F(0) en función de las proposiciones y los conectores
lógicamente equivalentes
Tienen los mismos valores sea cual sea la asignación
Tautologia
Siempre es V, p ∨ ¬p ⇐⇒ V
Contradicción
Siempre es F, p ∧ ¬p ⇐⇒ F
LL. d’identitat
p ∧ V ⇐⇒ p
p ∨ F ⇐⇒ p
LL dominación
p ∧ F ⇐⇒ F
p ∨ V ⇐⇒ V
LL idempotencia
p ∧ p ⇐⇒ p
p ∨ p ⇐⇒ p
LL de Doble Negación
¬(¬p) ⇐⇒ p
LL commutativas
p ∧ q ⇐⇒ q ∧ p
p ∨ q ⇐⇒ q ∨ p
Ll associatives
p ∧ (q ∧ r) ⇐⇒ (p ∧ q) ∧ r
p ∨ (q ∨ r) ⇐⇒ (p ∨ q) ∨ r
Ll de Morgan
¬(p ∧ q) ⇐⇒ ¬p ∨ ¬q
¬(p ∨ q) ⇐⇒ ¬p ∧ ¬q
LL de implicación
p → q ⇐⇒ ¬p ∨ q ⇐⇒ ¬(p ∧ ¬q)
LL distributivas
p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r)
Lógica 1 orden/ Predicativa
Proposiciones p que dependen de variables
Cuantificador universal
-(∀x ∈ Ω)P(x) o ∀x[P(x)] o ∀xP(x). o es decir para todo x
Cuantificador Existencial
(∃x ∈ Ω)P(x) o ∃x[P(x)] o ∃xP(x). o es decir para alguna x
Cuantificador existencial con unicitad
(∃!x)P(x) ⇐⇒ ∃xP(x) ∧ (∀x∀y)[(P(x) ∧ P(y)) → (x = y)], o es decir para una unica x
Como se puede escribir la prop ∀xP(x). de otra manera? y la prop ∃xP(x)?
P(x1) ∧ P(x2) ∧ · · · ∧ P(xn) y P(x1) ∨ P(x2) ∨ · · · ∨ P(xn).
Es lo mismo ∃x∀yP(x, y) que ∀y∃xP(x, y)?
no no es lo mismo, el orden de los cuantificadores influye en la expresión.
Qué pasa si niegas un cuantificador?
¬(∀xP(x)) ⇐⇒ ∃x(¬P(x)),
¬(∃xP(x)) ⇐⇒ ∀x(¬P(x)).
Lemas
resultado auxiliar que se utiliza para demostrar otros y que en principio no son significativos
teoremas
proposiciones que son importantes y queremos destacar
corolaris
resultado que se siguen de manera inmediata a partir de otros
Reglas de inferencia , cómo se escribe en lógica prop? p → q p ------------------------------ ∴ q
((p → q) ∧ p) → q
Demostración directa p y q
suponemos que una es cierta, hacemos uso de las reglas de indiferencia i otros resultados y axiomas para demostrar que q es cierto
Demostración por contrarrecíproco
basada en la equivalencia lógica
Demostración de reducción al absurdo
suponemos que el resultado es falso y llegamos a una contradicción
Demostraciones existenciales constructivas
se puede dar una respuesta si es posible construir explicitamente una c tal que p(c) sea cierto
Demostraciones por contra ejemplo
usados en cuantificadores existenciales, solo hace falta encontrar un ejemplo que no cumpla con ello
Dobles implicaciones y equivalencias
para demostrar equivalencias, se pudee hacer con dobles equivalencias o con un ciclo de implicaciones( la ultima debe de volver a la primera )
Inducción matemática
método de domstración donde la aplicación es el conjunto de nombres naturales
Inducción simple
- Cas inicial: P(n0) és cert.
* Pas d’inducció: Per a n > n0 arbitrari, es té que P(n) → P(n + 1).
Inducción completa
Cas inicial: P(n0) és cert.
• Pas d’inducció: Per a n > n0 arbitrari es té que (P(n0) ∧ · · · ∧ P(n)) → P(n + 1).
