maths, like whaaaaaaaaaaaaaaa? Flashcards

1
Q

Propietats T-1, Distributiva

A

φ ∧ (ψ ∨ θ) ≡ (φ ∧ ψ) ∨ (φ ∧ θ)
φ ∨ (ψ ∧ θ) ≡ (φ ∨ ψ) ∧ (φ ∨ θ)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Propietats T-1, De Morgan

A

¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ
¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Propietats T-1, Absorció

A

φ ∧ (φ ∨ ψ) ≡ φ
φ ∨ (φ ∧ ψ) ≡ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Propietats T-1, Idempotència

A

φ ∧ φ ≡ φ
φ ∨ φ ≡ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Propietats T-1, Commutativa

A

φ ∧ ψ ≡ ψ ∧ φ
φ ∨ ψ ≡ ψ ∨ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Propietats T-1, Associativa

A

φ ∧ (ψ ∧ θ) ≡ (φ ∧ ψ) ∧ θ
φ ∨ (ψ ∨ θ) ≡ (φ ∨ ψ) ∨ θ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Propietats T-1, Neutre

A

φ ∧ 1 ≡ φ
φ ∨ 0 ≡ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Propietats T-1, Element absorbent

A

φ ∨ 1 ≡ 1
φ ∧ 0 ≡ 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Propietats T-1, Complementari

A

φ ∨ ¬φ ≡ 1
φ ∧ ¬φ ≡ 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Propietats T-1, Doble negació

A

¬¬φ ≡ φ
¬1 ≡ 0
¬0 ≡ 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Traducció de la →

A

φ → ψ ≡ ¬φ ∨ ψ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Traducció de la ↔

A

φ ↔ ψ ≡ (φ → ψ) ∧ (ψ → φ)

≡ (φ ∧ ψ) ∨ (¬φ ∧ ¬ψ)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

¬∀𝑥φ ≡

A

∃𝑥¬φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

∀𝑥∀𝑦φ ≡

A

∀𝑦∀𝑥φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

∃𝑥∃𝑦φ ≡

A

∃𝑦∃𝑥φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

¬∃𝑥φ ≡

A

∀𝑥¬φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

∀𝑥 (φ ∧ ψ) ≡

A

∀𝑥φ ∧ ∀𝑥ψ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

∃𝑥 (φ ∨ ψ) ≡

A

∃𝑥φ ∨ ∃𝑥ψ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Demostració d’un existencial ∃𝑥𝑃(𝑥):

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Demostració d’un universal ∀𝑥𝑃(𝑥):

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Tema 1.2 passos lògics

A

I. 𝐴 , 𝐵 ⇒ 𝐴
II. 𝐴 ⇒ 𝐴 𝑜 𝐵
III. 𝐴 𝑜 𝐵, 𝑛𝑜 𝐴 ⇒ 𝐵
IV. 𝐴 , 𝐴 ⇒ 𝐵 ⇒ 𝐵
V. 𝑛𝑜 𝐵 , 𝐴 ⇒ 𝐵 ⇒ 𝑛𝑜 𝐴
VI. 𝐴 ⇒ 𝐵 , 𝐵 ⇒ 𝐶 ⇒ 𝐴 ⇒ 𝐶
VII. 𝐴𝐵𝑆𝑈𝑅𝐷 ⇒ 𝐴

tautologies,
I. (𝑝 ∧ 𝑞) → 𝑝
II. 𝑝 → (𝑝 ∨ 𝑞)
III. ((𝑝 ∨ 𝑞) ∧ ¬𝑝) → 𝑞
IV. (𝑝 ∧ (𝑝 → 𝑞)) → 𝑞
V. (¬𝑞 ∧ (𝑝 → 𝑞)) → ¬𝑝
VI. ((𝑝 → 𝑞) ∧ (𝑞 → 𝑟)) → (𝑝 → 𝑟)
VII. 0 → 𝑝

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Tema 1.2 passos no lògics

A

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 ≤.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

llenguatge demostratiu

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Mètodes de demostració

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
1.3 Passos no lògics, Propietats de la igualtat
1. 𝑎 = 𝑎 (reflexiva) 2. 𝑎 = 𝑏 ⇒ 𝑏 = 𝑎 (simètrica) 3. 𝑎 = 𝑏 , 𝑏 = 𝑐 ⇒ 𝑎 = 𝑐 (transitiva) 4. 𝑎 = 𝑏 ⇒ 𝐸(𝑎) = 𝐸(𝑏) (aquí 𝐸(𝑥) és una expressió on apareix 𝑥) 5. 𝑎 = 𝑏 ⇒ 𝑎 + 𝑐 = 𝑏 + 𝑐 6. 𝑎 = 𝑏 ⇒ 𝑎𝑐 = 𝑏𝑐 7. 𝑎 = 𝑏 ⇒ 𝑎 2 = 𝑏 2 8. 𝑎 = 𝑏, 𝑎' = 𝑏' ⇒ 𝑎 + 𝑎' = 𝑏 + 𝑏' 9. 𝑎 = 𝑏, 𝑎' = 𝑏' ⇒ 𝑎𝑎' = 𝑏𝑏'
26
1.3 Passos no lògics, Propietats de la suma i el producte
1. 𝑎 + (𝑏 + 𝑐) = (𝑎 + 𝑏) + 𝑐 (Associativa de la suma) 2. 𝑎 + 𝑏 = 𝑏 + 𝑎 (Commutativa de la suma) 3. 𝑎 + 0 = 𝑎 (0 és el neutre de la suma) 4. 𝑎 + (− 𝑎) = 0 (− 𝑎 és l’invers de 𝑎 per la suma) 5. 𝑎(𝑏𝑐) = (𝑎𝑏)𝑐 (Associativa del producte) 6. 𝑎𝑏 = 𝑏𝑎 (Commutativa del producte) 7. 𝑎1 = 𝑎 (1 és el neutre del producte) 8. 𝑎 ≠ 0 ⇒ 𝑎·(1/𝑎) = 1 (1/𝑎 és l’invers de 𝑎 pel producte) 9. 𝑎(𝑏 + 𝑐) = 𝑎𝑏 + 𝑎𝑐 (distributiva )
27
1.3 Passos no lògics, Propietats de l’ordre
28
1.3 Passos no lògics, Altres:
29
Inducció simple
30
Inducció completa
31
Prova directa.
32
Prova pel contrarecíproc.
33
Reducció a l’absurd
34
Reducció a l’absurd II
35
Prova d’una disjunció
36
Disjunció al conseqüent
37
Disjunció a l’antecedent
38
Prova per casos
39
Demostració d’una equivalència
40
Demostració de la unicitat
41
Descripció d’un conjunt
42
Igualtat entre conjunts (principi d’extensionalitat)
𝐴 = 𝐵 ⇔ ∀𝑥 (𝑥 ∈ 𝐴 ↔ 𝑥 ∈ 𝐵) 𝐴 = 𝐵 ⇔ 𝐴 ⊆ 𝐵, 𝐵 ⊆ A
43
Conjunt buit
Ø = {} = {𝑥 | 𝑥 ≠ 𝑥}
44
Inclusió entre conjunts
𝐴 ⊆ 𝐵 ⇔ ∀𝑥 (𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵)
45
propietats d'inclusió
I. Ø ⊆ 𝐴. II. 𝐴 ⊆ 𝐴. III. 𝐴 ⊆ 𝐵 i 𝐵 ⊆ 𝐶 implica 𝐴 ⊆ 𝐶.
46
Unió
𝐴 ∪ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵} 𝑥 ∈ 𝐴 ∪ 𝐵 ⇔ 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ B
47
propietats unió
I. 𝐴 ∪ 𝐴 = 𝐴. II. 𝐴 ∪ Ø = 𝐴. III. 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴. IV. 𝐴 ∪ (𝐵 ∪ 𝐶) = (𝐴 ∪ 𝐵) ∪ 𝐶. V. 𝐴 ⊆ 𝐴 ∪ 𝐵, 𝐵 ⊆ 𝐴 ∪ 𝐵. VI. 𝐴 ⊆ 𝐵 ⇔ 𝐴 ∪ 𝐵 = 𝐵. VII. 𝐴 ∪ 𝐵 ⊆ 𝐶 ⇔ 𝐴 ⊆ 𝐶 , 𝐵 ⊆ 𝐶 .
48
Intersecció
𝐴 ∩ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵} 𝑥 ∈ 𝐴 ∩ 𝐵 ⇔ 𝑥 ∈ 𝐴 𝑖 𝑥 ∈ 𝐵 𝐴 i 𝐵 són disjunts ⇔ 𝐴 ∩ 𝐵 = Ø
49
propietats intersecció
I. 𝐴 ∩ 𝐴 = 𝐴. II. 𝐴 ∩ Ø = Ø. III. 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴. IV. 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ 𝐶. V. 𝐴 ∩ 𝐵⊆ 𝐴, 𝐴 ∩ 𝐵⊆ 𝐵. VI. 𝐴 ⊆ 𝐵 ⇔ 𝐴 ∩ 𝐵 = 𝐴. VII. 𝐶 ⊆ 𝐴 ∩ 𝐵 ⇔ 𝐶 ⊆ 𝐴 i 𝐶 ⊆ 𝐵.
50
Diferència
𝐴 − 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵} 𝑥 ∈ 𝐴 − 𝐵 ⇔ 𝑥 ∈ 𝐴 𝑖 𝑥 ∉ 𝐵
51
propietats diferència
I. 𝐴 − 𝐴 = Ø II. 𝐴 − Ø = 𝐴 III. Ø − 𝐴 = Ø IV. 𝐴 − 𝐵⊆ 𝐴 V. (𝐴 − 𝐵) ∩ 𝐵 = Ø VI. 𝐴 ⊆ 𝐵 ⇔ 𝐴 − 𝐵 = Ø VII. 𝐶 ⊆ 𝐴 − 𝐵 ⇔ 𝐶 ⊆ 𝐴 , 𝐶 ∩ 𝐵 = Ø
52
Altres propietats de conjunts
I. (distributiva) 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶), 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶) II. 𝐴 ∩ (𝐴 ∪ 𝐵) = 𝐴, 𝐴 ∪ (𝐴 ∩ 𝐵) = 𝐴 III. 𝐴 − (𝐵 ∪ 𝐶) = (𝐴 − 𝐵) ∩ (𝐴 − 𝐶) IV. 𝐴 ∪ 𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴) ∪ (𝐴 ∩ 𝐵) i la unió és disjunta (els conjunts (𝐴 − 𝐵), (𝐵 − 𝐴), (𝐴 ∩ 𝐵) són disjunts 2 a 2)
53
Complementaris
𝐴^c= Ω − 𝐴 = { 𝑥 ∈ Ω | 𝑥 ∉ 𝐴 } 𝑥 ∈ 𝐴^c ⇔ 𝑥 ∈ Ω ∧ 𝑥 ∉ A
54
propietats complementaris
55
Parts d’un conjunt
𝑃(𝐴) = { 𝑥 | 𝑥 ⊆ 𝐴 } 𝑥 ∈ 𝑃(𝐴) ⇔ 𝑥 ⊆ A 𝑃( {1, 2, 3} ) = { Ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }
56
Propietat de parts de conjunts
I. Ø ∈ 𝑃(𝐴). II. 𝐴 ∈ 𝑃(𝐴).
57
Parella ordenada
(𝑎, 𝑏) = (𝑐, 𝑑) ⇔ 𝑎 = 𝑐 , 𝑏 = �
58
Producte cartesià
𝐴 × 𝐵 = { 𝑥 | 𝑥 = (𝑎, 𝑏) 𝑝𝑒𝑟 𝑎 𝑢𝑛𝑠 𝑐𝑒𝑟𝑡𝑠 𝑎 ∈ 𝐴 𝑖 𝑏 ∈ 𝐵 } 𝐴 × 𝐵 = { (𝑎, 𝑏) | 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 } {1, 2, 3, 4} × {𝑎, 𝑏} = { (1, 𝑎), (2, 𝑎), (3, 𝑎), (4, 𝑎), (1, 𝑏), (2, 𝑏), (3, 𝑏), (4, 𝑏) } 𝑥 ∈ 𝐴 × 𝐵 ⇔ 𝑥 = (𝑎, 𝑏) 𝑝𝑒𝑟 𝑎 𝑢𝑛𝑠 𝑐𝑒𝑟𝑡𝑠 𝑎 ∈ 𝐴 𝑖 𝑏 ∈ B (𝑎, 𝑏) ∈ 𝐴 × 𝐵 ⇔ 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ B Notem que: |𝐴 × 𝐵| = |𝐴|·|𝐵|
59
propietats producte cartesia
I. 𝐴 × Ø = Ø, Ø × 𝐴 = Ø. II. 𝐴 × (𝐵 ∩ 𝐶) = (𝐴 × 𝐵) ∩ (𝐴 × 𝐶). III. 𝐴 × (𝐵 ∪ 𝐶) = (𝐴 × 𝐵) ∪ (𝐴 × 𝐶). IV. 𝐴 × (𝐵 − 𝐶) = (𝐴 × 𝐵) − (𝐴 × 𝐶).
60
Demostracions amb conjunts Demostració de la igualtat entre conjunts (1a. manera)
Volem veure: 𝐴 = 𝐵 Sigui x qualsevol: 𝑥 ∈ 𝐴 ⇔ ··· ⇔ ··· ⇔ 𝑥 ∈ 𝐵
61
Demostracions amb conjunts Demostració d’una inclusió entre conjunts
Volem veure: 𝐴 ⊆ 𝐵 Sigui x qualsevol: 𝑥 ∈ 𝐴 ⇒ ··· ⇒ ··· ⇒ 𝑥 ∈ B
62
Demostracions amb conjunts Demostració de la igualtat entre conjunts (2a. manera)
Volem veure: 𝐴 = 𝐵 Demostrem dues coses: 𝐴 ⊆ 𝐵, 𝐵 ⊆ A
63
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: ● 𝐴 ≠ ∅ ⇔ ∃𝑥 𝑥 ∈ 𝐴 ● 𝐴⊈𝐵 ⇔ ∃𝑥 ( 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵 ) ● 𝐴 ≠ 𝐵 ⇔ ∃𝑥 ( 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵 ) ∨ ∃𝑥 ( 𝑥 ∈ 𝐵 ∧ 𝑥 ∉ 𝐴 )
64
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
65
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 𝑃(𝐴)
66
Propietats que satisfà tota relació d’equivalència:
67
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 𝐴.