maths, like whaaaaaaaaaaaaaaa? Flashcards
Propietats T-1, Distributiva
φ ∧ (ψ ∨ θ) ≡ (φ ∧ ψ) ∨ (φ ∧ θ)
φ ∨ (ψ ∧ θ) ≡ (φ ∨ ψ) ∧ (φ ∨ θ)
Propietats T-1, De Morgan
¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ
¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ
Propietats T-1, Absorció
φ ∧ (φ ∨ ψ) ≡ φ
φ ∨ (φ ∧ ψ) ≡ φ
Propietats T-1, Idempotència
φ ∧ φ ≡ φ
φ ∨ φ ≡ φ
Propietats T-1, Commutativa
φ ∧ ψ ≡ ψ ∧ φ
φ ∨ ψ ≡ ψ ∨ φ
Propietats T-1, Associativa
φ ∧ (ψ ∧ θ) ≡ (φ ∧ ψ) ∧ θ
φ ∨ (ψ ∨ θ) ≡ (φ ∨ ψ) ∨ θ
Propietats T-1, Neutre
φ ∧ 1 ≡ φ
φ ∨ 0 ≡ φ
Propietats T-1, Element absorbent
φ ∨ 1 ≡ 1
φ ∧ 0 ≡ 0
Propietats T-1, Complementari
φ ∨ ¬φ ≡ 1
φ ∧ ¬φ ≡ 0
Propietats T-1, Doble negació
¬¬φ ≡ φ
¬1 ≡ 0
¬0 ≡ 1
Traducció de la →
φ → ψ ≡ ¬φ ∨ ψ
Traducció de la ↔
φ ↔ ψ ≡ (φ → ψ) ∧ (ψ → φ)
≡ (φ ∧ ψ) ∨ (¬φ ∧ ¬ψ)
¬∀𝑥φ ≡
∃𝑥¬φ
∀𝑥∀𝑦φ ≡
∀𝑦∀𝑥φ
∃𝑥∃𝑦φ ≡
∃𝑦∃𝑥φ
¬∃𝑥φ ≡
∀𝑥¬φ
∀𝑥 (φ ∧ ψ) ≡
∀𝑥φ ∧ ∀𝑥ψ
∃𝑥 (φ ∨ ψ) ≡
∃𝑥φ ∨ ∃𝑥ψ
Demostració d’un existencial ∃𝑥𝑃(𝑥):
El mètode més senzill és donar un element 𝑎 del domini que tingui la propietat 𝑃. Un sol exemple és suficient.
Això mateix s’aplica a la demostració que un enunciat universal és fals, ja que ¬∀𝑥𝑃(𝑥) ≡ ∃𝑥¬𝑃(𝑥). La demostració de la falsedat de ∀𝑥𝑃(𝑥) es fa donant un element 𝑎 del domini que no tingui la propietat 𝑃; 𝑎 rep el nom de contraexemple.
Demostració d’un universal ∀𝑥𝑃(𝑥):
Hem de veure que tots els elements del domini satisfan la propietat 𝑃. Si hi ha pocs elements, ho podem verificar un a un. Si n’hi ha molts o infinits no quedarà més remei que donar-ne una “demostració”. Una demostració és un raonament que segueix unes certes regles. Tot i que fer una demostració pot arribar a ser molt difícil, la comprovació que aquesta és correcte no hauria de ser-ho. Però això requereix que la demostració estigui ben escrita. A l’apartat següent explicarem com es fa això. El mateix s’aplica a la demostració que un existencial és fals.
Tema 1.2 passos lògics
I. 𝐴 , 𝐵 ⇒ 𝐴
II. 𝐴 ⇒ 𝐴 𝑜 𝐵
III. 𝐴 𝑜 𝐵, 𝑛𝑜 𝐴 ⇒ 𝐵
IV. 𝐴 , 𝐴 ⇒ 𝐵 ⇒ 𝐵
V. 𝑛𝑜 𝐵 , 𝐴 ⇒ 𝐵 ⇒ 𝑛𝑜 𝐴
VI. 𝐴 ⇒ 𝐵 , 𝐵 ⇒ 𝐶 ⇒ 𝐴 ⇒ 𝐶
VII. 𝐴𝐵𝑆𝑈𝑅𝐷 ⇒ 𝐴
tautologies,
I. (𝑝 ∧ 𝑞) → 𝑝
II. 𝑝 → (𝑝 ∨ 𝑞)
III. ((𝑝 ∨ 𝑞) ∧ ¬𝑝) → 𝑞
IV. (𝑝 ∧ (𝑝 → 𝑞)) → 𝑞
V. (¬𝑞 ∧ (𝑝 → 𝑞)) → ¬𝑝
VI. ((𝑝 → 𝑞) ∧ (𝑞 → 𝑟)) → (𝑝 → 𝑟)
VII. 0 → 𝑝
Tema 1.2 passos no lògics
Passos no lògics: (aquí 𝑎, 𝑏, 𝑐, 𝑑… són números reals)
I. 𝑎 = 𝑏 ⇒ 𝐸(𝑎) = 𝐸(𝑏) (aquí 𝐸(𝑥) és una expressió on apareix 𝑥)
II. 𝑎 = 𝑏 , 𝑏 = 𝑐 ⇒ 𝑎 = 𝑐.
III. 𝑎 = 𝑏, 𝑎’ = 𝑏’ ⇒ 𝑎 + 𝑎’ = 𝑏 + 𝑏’, 𝑎𝑎’ = 𝑏𝑏’.
IV. 𝑎 ≤ 𝑏, 𝑏 ≤ 𝑎 ⇒ 𝑎 = 𝑏.
V. 𝑎 ≤ 𝑏 ⇒ − 𝑏 ≤− 𝑎.
VI. 𝑎 ≤ 𝑏 ⇒ 𝑎 + 𝑐 ≤ 𝑏 + 𝑐.
VII. 𝑎 ≤ 𝑏, 𝑐 ≤ 𝑑 ⇒ 𝑎 + 𝑐 ≤ 𝑏 + 𝑑.
VIII. 𝑎 ≤ 𝑏, 𝑐 ≥ 0 ⇒ 𝑎𝑐 ≤ 𝑏𝑐.
IX. 0 ≤ 𝑎 ≤ 𝑏, 0 ≤ 𝑐 ≤ 𝑑 ⇒ 𝑎𝑐 ≤ 𝑏𝑑.
X. Les propietats V,VI,VII,VIII i IX també valen amb < enlloc de ≤.
llenguatge demostratiu
Mètodes de demostració
Prova directa.
Prova pel contrarecíproc.
Reducció a l’absurd
Reducció a l’absurd II
Prova d’una disjunció
Disjunció al conseqüent
Disjunció a l’antecedent
Prova per casos
Demostració d’una equivalència
Demostració de la unicitat
1.3 Passos no lògics, Propietats de la igualtat
- 𝑎 = 𝑎 (reflexiva)
- 𝑎 = 𝑏 ⇒ 𝑏 = 𝑎 (simètrica)
- 𝑎 = 𝑏 , 𝑏 = 𝑐 ⇒ 𝑎 = 𝑐 (transitiva)
- 𝑎 = 𝑏 ⇒ 𝐸(𝑎) = 𝐸(𝑏) (aquí 𝐸(𝑥) és una expressió on apareix 𝑥)
- 𝑎 = 𝑏 ⇒ 𝑎 + 𝑐 = 𝑏 + 𝑐
- 𝑎 = 𝑏 ⇒ 𝑎𝑐 = 𝑏𝑐
- 𝑎 = 𝑏 ⇒ 𝑎
2 = 𝑏
2 - 𝑎 = 𝑏, 𝑎’ = 𝑏’ ⇒ 𝑎 + 𝑎’ = 𝑏 + 𝑏’
- 𝑎 = 𝑏, 𝑎’ = 𝑏’ ⇒ 𝑎𝑎’ = 𝑏𝑏’
1.3 Passos no lògics, Propietats de la suma i el producte
- 𝑎 + (𝑏 + 𝑐) = (𝑎 + 𝑏) + 𝑐 (Associativa de la suma)
- 𝑎 + 𝑏 = 𝑏 + 𝑎 (Commutativa de la suma)
- 𝑎 + 0 = 𝑎 (0 és el neutre de la suma)
- 𝑎 + (− 𝑎) = 0 (− 𝑎 és l’invers de 𝑎 per la suma)
- 𝑎(𝑏𝑐) = (𝑎𝑏)𝑐 (Associativa del producte)
- 𝑎𝑏 = 𝑏𝑎 (Commutativa del producte)
- 𝑎1 = 𝑎 (1 és el neutre del producte)
- 𝑎 ≠ 0 ⇒ 𝑎·(1/𝑎) = 1 (1/𝑎 és l’invers de 𝑎 pel producte)
- 𝑎(𝑏 + 𝑐) = 𝑎𝑏 + 𝑎𝑐 (distributiva )
1.3 Passos no lògics, Propietats de l’ordre
1.3 Passos no lògics, Altres:
Inducció simple
Inducció completa
Prova directa.
Prova pel contrarecíproc.
Reducció a l’absurd
Reducció a l’absurd II
Prova d’una disjunció
Disjunció al conseqüent
Disjunció a l’antecedent
Prova per casos
Demostració d’una equivalència
Demostració de la unicitat
Descripció d’un conjunt
Igualtat entre conjunts (principi d’extensionalitat)
𝐴 = 𝐵 ⇔ ∀𝑥 (𝑥 ∈ 𝐴 ↔ 𝑥 ∈ 𝐵)
𝐴 = 𝐵 ⇔ 𝐴 ⊆ 𝐵, 𝐵 ⊆ A
Conjunt buit
Ø = {} = {𝑥 | 𝑥 ≠ 𝑥}
Inclusió entre conjunts
𝐴 ⊆ 𝐵 ⇔ ∀𝑥 (𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵)
propietats d’inclusió
I. Ø ⊆ 𝐴.
II. 𝐴 ⊆ 𝐴.
III. 𝐴 ⊆ 𝐵 i 𝐵 ⊆ 𝐶 implica 𝐴 ⊆ 𝐶.
Unió
𝐴 ∪ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵}
𝑥 ∈ 𝐴 ∪ 𝐵 ⇔ 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ B
propietats unió
I. 𝐴 ∪ 𝐴 = 𝐴.
II. 𝐴 ∪ Ø = 𝐴.
III. 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴.
IV. 𝐴 ∪ (𝐵 ∪ 𝐶) = (𝐴 ∪ 𝐵) ∪ 𝐶.
V. 𝐴 ⊆ 𝐴 ∪ 𝐵, 𝐵 ⊆ 𝐴 ∪ 𝐵.
VI. 𝐴 ⊆ 𝐵 ⇔ 𝐴 ∪ 𝐵 = 𝐵.
VII. 𝐴 ∪ 𝐵 ⊆ 𝐶 ⇔ 𝐴 ⊆ 𝐶 , 𝐵 ⊆ 𝐶 .
Intersecció
𝐴 ∩ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵}
𝑥 ∈ 𝐴 ∩ 𝐵 ⇔ 𝑥 ∈ 𝐴 𝑖 𝑥 ∈ 𝐵
𝐴 i 𝐵 són disjunts ⇔ 𝐴 ∩ 𝐵 = Ø
propietats intersecció
I. 𝐴 ∩ 𝐴 = 𝐴.
II. 𝐴 ∩ Ø = Ø.
III. 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴.
IV. 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ 𝐶.
V. 𝐴 ∩ 𝐵⊆ 𝐴, 𝐴 ∩ 𝐵⊆ 𝐵.
VI. 𝐴 ⊆ 𝐵 ⇔ 𝐴 ∩ 𝐵 = 𝐴.
VII. 𝐶 ⊆ 𝐴 ∩ 𝐵 ⇔ 𝐶 ⊆ 𝐴 i 𝐶 ⊆ 𝐵.
Diferència
𝐴 − 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵}
𝑥 ∈ 𝐴 − 𝐵 ⇔ 𝑥 ∈ 𝐴 𝑖 𝑥 ∉ 𝐵
propietats diferència
I. 𝐴 − 𝐴 = Ø
II. 𝐴 − Ø = 𝐴
III. Ø − 𝐴 = Ø
IV. 𝐴 − 𝐵⊆ 𝐴
V. (𝐴 − 𝐵) ∩ 𝐵 = Ø
VI. 𝐴 ⊆ 𝐵 ⇔ 𝐴 − 𝐵 = Ø
VII. 𝐶 ⊆ 𝐴 − 𝐵 ⇔ 𝐶 ⊆ 𝐴 , 𝐶 ∩ 𝐵 = Ø
Altres propietats de conjunts
I. (distributiva)
𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶),
𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶)
II. 𝐴 ∩ (𝐴 ∪ 𝐵) = 𝐴, 𝐴 ∪ (𝐴 ∩ 𝐵) = 𝐴
III. 𝐴 − (𝐵 ∪ 𝐶) = (𝐴 − 𝐵) ∩ (𝐴 − 𝐶)
IV. 𝐴 ∪ 𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴) ∪ (𝐴 ∩ 𝐵) i la unió és disjunta (els conjunts
(𝐴 − 𝐵), (𝐵 − 𝐴), (𝐴 ∩ 𝐵) són disjunts 2 a 2)
Complementaris
𝐴^c= Ω − 𝐴 = { 𝑥 ∈ Ω | 𝑥 ∉ 𝐴 }
𝑥 ∈ 𝐴^c ⇔ 𝑥 ∈ Ω ∧ 𝑥 ∉ A
propietats complementaris
Parts d’un conjunt
𝑃(𝐴) = { 𝑥 | 𝑥 ⊆ 𝐴 }
𝑥 ∈ 𝑃(𝐴) ⇔ 𝑥 ⊆ A
𝑃( {1, 2, 3} ) = { Ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }
Propietat de parts de conjunts
I. Ø ∈ 𝑃(𝐴).
II. 𝐴 ∈ 𝑃(𝐴).
Parella ordenada
(𝑎, 𝑏) = (𝑐, 𝑑) ⇔ 𝑎 = 𝑐 , 𝑏 = �
Producte cartesià
𝐴 × 𝐵 = { 𝑥 | 𝑥 = (𝑎, 𝑏) 𝑝𝑒𝑟 𝑎 𝑢𝑛𝑠 𝑐𝑒𝑟𝑡𝑠 𝑎 ∈ 𝐴 𝑖 𝑏 ∈ 𝐵 }
𝐴 × 𝐵 = { (𝑎, 𝑏) | 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 }
{1, 2, 3, 4} × {𝑎, 𝑏} = { (1, 𝑎), (2, 𝑎), (3, 𝑎), (4, 𝑎), (1, 𝑏), (2, 𝑏), (3, 𝑏), (4, 𝑏) }
𝑥 ∈ 𝐴 × 𝐵 ⇔ 𝑥 = (𝑎, 𝑏) 𝑝𝑒𝑟 𝑎 𝑢𝑛𝑠 𝑐𝑒𝑟𝑡𝑠 𝑎 ∈ 𝐴 𝑖 𝑏 ∈ B
(𝑎, 𝑏) ∈ 𝐴 × 𝐵 ⇔ 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ B
Notem que: |𝐴 × 𝐵| = |𝐴|·|𝐵|
propietats producte cartesia
I. 𝐴 × Ø = Ø, Ø × 𝐴 = Ø.
II. 𝐴 × (𝐵 ∩ 𝐶) = (𝐴 × 𝐵) ∩ (𝐴 × 𝐶).
III. 𝐴 × (𝐵 ∪ 𝐶) = (𝐴 × 𝐵) ∪ (𝐴 × 𝐶).
IV. 𝐴 × (𝐵 − 𝐶) = (𝐴 × 𝐵) − (𝐴 × 𝐶).
Demostracions amb conjunts
Demostració de la igualtat entre conjunts (1a. manera)
Volem veure: 𝐴 = 𝐵
Sigui x qualsevol:
𝑥 ∈ 𝐴 ⇔ ··· ⇔ ··· ⇔ 𝑥 ∈ 𝐵
Demostracions amb conjunts
Demostració d’una inclusió entre conjunts
Volem veure: 𝐴 ⊆ 𝐵
Sigui x qualsevol:
𝑥 ∈ 𝐴 ⇒ ··· ⇒ ··· ⇒ 𝑥 ∈ B
Demostracions amb conjunts
Demostració de la igualtat entre conjunts (2a. manera)
Volem veure: 𝐴 = 𝐵
Demostrem dues coses: 𝐴 ⊆ 𝐵, 𝐵 ⊆ A
Demostracions amb conjunts
Demostració que un conjunt és buit
Volem veure: 𝐴 = ∅
Per reducció a l’absurd:
∃𝑥 ∈ 𝐴 ⇒ ··· ⇒ ··· ⇒ 𝐴𝑏𝑠𝑢𝑟d
Més generalment:
Demostració on intervé que un conjunt és buit
En aquest tipus de demostracions una bona estratègia és usar contrarecíproc o
reducció a l’absurd per tal que la condició “ser buit” hi aparegui negada.
Notem que:
● 𝐴 ≠ ∅ ⇔ ∃𝑥 𝑥 ∈ 𝐴
● 𝐴⊈𝐵 ⇔ ∃𝑥 ( 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵 )
● 𝐴 ≠ 𝐵 ⇔ ∃𝑥 ( 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵 ) ∨ ∃𝑥 ( 𝑥 ∈ 𝐵 ∧ 𝑥 ∉ 𝐴 )
RELACIONS binaries
Idea intuïtiva: una relació binària en un conjunt 𝐴 “relaciona” parelles d’elements de 𝐴. Cada parella d’elements de 𝐴 poden estar o no estar relacionats. Determinar la relació consisteix en indicar quines parelles estan relacionades i quines no.
Siguin 𝑥, 𝑦ϵ𝐴. Si estan relacionats per la relació 𝑅 ho escriurem així:
𝑥𝑅𝑦 (si no, R tachada)
Propietats importants que poden tenir les relacions:
Reflexiva ∀𝑥ϵ𝐴 𝑥𝑅𝑥
Simètrica ∀𝑥, 𝑦ϵ𝐴 ( 𝑥𝑅𝑦 → 𝑦𝑅𝑥 )
Transitiva ∀𝑥, 𝑦, 𝑧ϵ𝐴 ( (𝑥𝑅𝑦 ∧ 𝑦𝑅𝑧) → 𝑥𝑅𝑧 )
Antisimètrica ∀𝑥, 𝑦ϵ𝐴 ( (𝑥𝑅𝑦 ∧ 𝑦𝑅𝑥) → 𝑥 = 𝑦 )
Una relació d’equivalència és una relació binària que és reflexiva, simètrica i transitiva
Classes d’equivalència i conjunt quocient
-𝑎- = { 𝑥ϵ𝐴 | 𝑥𝑅𝑎 }
𝑥ϵ-𝑎- ⇔ 𝑥𝑅a
El conjunt quocient , que denotem per 𝐴/𝑅, és el conjunt de totes les classes:
𝐴/𝑅 = { 𝑥 | 𝑥 = -𝑎- 𝑝𝑒𝑟 𝑎 𝑢𝑛 𝑐𝑒𝑟𝑡 𝑎ϵ𝐴 } = { -𝑎- | 𝑎ϵ𝐴 }
Notem que:
1. Cada classe d’equivalència és un subconjunt del domini 𝐴.
2. El conjunt quocient 𝐴/𝑅 és un subconjunt de 𝑃(𝐴)
Propietats que satisfà tota relació d’equivalència:
PARTICIONS
La idea de partició és molt senzilla: tenim un conjunt 𝐴 i el trenquem (o repartim) en trossos.
El conjunt format per aquestes 4 parts és una partició de 𝐴:
{ {𝑏, 𝑐}, {𝑑}, {𝑒, 𝑓, 𝑔, 𝑗}, {𝑎, ℎ, 𝑖} }
Definició:
Una partició 𝑃 de 𝐴 és un conjunt de subconjunts no buits de 𝐴,
disjunts dos a dos i tal que la seva reunió és 𝐴.
