Fonaments Matemàtics: Lògica, Inducció i Conjunts

I 0 flashcards i 10 preguntes més al document.

Text del document

APUNTS FONAMENTS MATEMÀTICS Grau en Enginyeria Civil Universitat Politècnica de Catalunya AprenAI 2026-2027 Apunts de Fonaments Matemàtics (UPC): lògica, demostracions, inducció simple i completa, àlgebra de conjunts, relacions d'equivalència i particions.

APREN.AI Índex 1 Preliminars — Notació, sumatoris, progressions i productoris Convenis i notació numèrica Sumatoris i manipulació d'índexs Progressions aritmètiques Progressions geomètriques Productoris i les seves propietats 2 Lògica proposicional — Sintaxi, semàntica i equivalències lògiques Sintaxi de la lògica proposicional: enunciats i fórmules ben formades Semàntica i taules de veritat Classificació semàntica: tautologia, contradicció i contingència Equivalència lògica i àlgebra d'operacions Equivalències clau per a les demostracions matemàtiques 3 Lògica de primer ordre — Relacions, quantificadors i formalització Components fonamentals i sintaxi Semàntica i interpretació dels quantificadors Equivalències lògiques i no-equivalències Patrons estàndard de formalització Formalització aritmètica i condicions de cardinalitat 4 Mètodes de demostració — Estratègies i regles d'inferència bàsiques 1.

Veracitat i quantificadors 2. Demostracions formals, regles d'inferència i passos no lògics 3. Mètodes fonamentals: prova directa, contrarecíproc i reducció a l'absurd 4. Demostració de disjuncions, prova per casos i equivalències 5.

Demostració d'unicitat Inducció matemàtica 5 Inducció simple, variants i aplicacions Fonament lògic i estructura canònica Inducció aplicada a sumatoris i productoris Desigualtats i comportament asimptòtic Divisibilitat sobre enters Variants d'inducció simple: múltiples casos base Aplicacions a la complexitat d'algorismes i àlgebra lineal Problemes discrets: recurrències, Hanoi i geometria 6 Inducció completa i recurrències Fonaments Matemàtics: Lògica, Inducció i Conjunts 1 Fonaments de la inducció completa Múltiples casos base i abast de la dependència L'aplicació fonamental: factorització en nombres primers Recurrències divideix i venceràs i funcions de part entera Recurrències lineals d'ordre superior Aplicacions combinatòries, jocs i estructures sintàctiques Teoria de conjunts 7 Conceptes bàsics, inclusió i àlgebra de conjunts Noció de conjunt, pertinença i especificació Principi d'extensionalitat i relació d'inclusió Àlgebra de conjunts: unió, intersecció i conjunts disjunts Diferència de conjunts i diferència simètrica Complementari relatiu a un univers i lleis de De Morgan 8 Conjunt de les parts i producte cartesià El conjunt de les parts o conjunt potència Cardinal del conjunt de les parts i propietats algebraiques Parella ordenada i producte cartesià Receptes metòdiques per a demostracions de conjunts 9 Relacions binàries — Tipologia, propietats i relacions d'ordre Definició i representació de relacions binàries Propietats estructurals fonamentals Interacció de propietats, circularitat i operacions 10 Relacions d'equivalència i particions — Classes d'equivalència i conjunt quocient Relacions d'equivalència, classes i conjunt quocient Propietats fonamentals de les classes d'equivalència Particions i el teorema fonamental Exemples detallats en conjunts numèrics, de parts i geomètrics Estructura del quocient i bona definició d'operacions 11 Formulari Preliminars, sumatoris i progressions Lògica proposicional i de predicats Mètodes de demostració i inducció Conjunts, relacions i quocients Constants, convenis i errors típics Solucions de les preguntes de repàs Fonaments Matemàtics: Lògica, Inducció i Conjunts 2 Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important.

Fonaments Matemàtics: Lògica, Inducció i Conjunts 3 1 Preliminars — Notació, sumatoris, progressions i productoris EN ACABAR SABRÀS Aplicar correctament els convenis de conjunts numèrics i el càlcul de la part entera E(x) Manipular sumatoris mitjançant propietats lineals i canvis d'índex Calcular sumes finites de progressions aritmètiques i geomètriques Operar amb productoris aplicant les propietats de potències i extracció de constants PENSA-HI ABANS DE LLEGIR 1 Si traiem un factor constant c fora d'un sumatori surt com c, però què passa quan el traiem d'un productori de 5 termes?

Aquest bloc inicial estableix el llenguatge i les eines de càlcul bàsiques que s'empraran al llarg de tota la matèria. Fixem primer les convencions dels conjunts numèrics fonamentals i les operacions de sumatori i productori per manipular expressions matemàtiques de manera rigorosa. ESQUEMA Estructura de Fonaments Matemàtics Convenis i notació numèrica Per evitar ambigüitats en els enunciats i en les demostracions, s'adopten uns convenis universals sobre els conjunts de nombres més habituals: Nombres naturals ( ): és el conjunt . Per conveni explícit d'aquest curs, 0 és un nombre natural ( ). Nombres enters ( ): inclou els positius, els negatius i el zero, .

Nombres reals ( ): comprèn la totalitat de la recta real. Preliminars Notació, sumatoris, progressions i productoris Lògica Proposicional, predicats i mètodes de demostració Inducció matemàtica Inducció simple, variants, completa i recurrències Conjunts i relacions Àlgebra de conjunts, parts, ordres i equivalència N N = {0, 1, 2, 3, 4, … } 0 N Z Z = {… , 3, 2, 1, 0, 1, 2, 3, … } R Fonaments Matemàtics: Lògica, Inducció i Conjunts 4 Dins dels reals es distingeix amb precisió el signe dels elements: Un nombre és positiu si compleix la condició estricta . Un nombre és no negatiu quan compleix (inclou el zero). Un nombre és negatiu si compleix .

DEFINICIÓ: PART ENTERA La part entera inferior o part entera d'un nombre real , denotada com a , és l'únic nombre enter que satisfà la doble desigualtat: Així, per exemple, tenim que , mentre que per a valors negatius es compleix , ja que . COMPROVA-HO 2 Quant val la part entera de -0,4 segons la definició de E(x)? Sumatoris i manipulació d'índexs La notació de sumatori permet escriure de forma compacta l'addició d'una seqüència de termes que depenen d'una variable discreta o índex: El valor enter és el límit inferior, mentre que és el límit superior. El nombre total de sumands d'aquesta expressió és exactament n - m + 1 quan .

EXEMPLE: EXPANSIÓ D'UN SUMATORI El sumatori consta de termes: L'operador sumatori gaudeix de propietats lineals bàsiques fonamentals per operar: Separació de sumes: . Extracció de constants: si no depèn de l'índex , llavors . Sovint és necessari realitzar un canvi d'índex per alinear sumatoris o fer que comencin en un valor concret, per exemple en . Si definim un nou índex , cada aparició de se substitueix per , i els límits es desplacen en conseqüència.

x R x > 0 x R x 0 x R x < 0 x E(x) E(x) x < E(x) + 1 E(3,7) = 3 E( 2,3) = 3 3 2,3 < 2 f(i) = i=m n f(m) + f(m + 1) + + f(n 1) + f(n) m n n m 2i i= 2 3 3 ( 2) + 1 = 6 2i = i= 2 3 2( 2) + 2( 1) + 2(0) + 2(1) + 2(2) + 2(3) = 4 2 + 0 + 2 + 4 + 6 = 6 (f(i) + i=m n g(i)) = f(i) + i=m n g(i) i=m n c i c i=m n f(i) = c f(i) i=m n j = 0 j = i k i j + k Fonaments Matemàtics: Lògica, Inducció i Conjunts 5 EXEMPLE: CANVI DE VARIABLE EN UN SUMATORI Per escriure el sumatori començant des de , fem el canvi . D'aquí s'obté .

Quan tenim , i quan tenim : Dues identitats canòniques d'ús recurrent en el càlcul de sumatoris són la suma dels primers enters i la suma dels seus quadrats: COMPROVA-HO 3 Quants sumands té l'expressió sumatori de i=-3 fins a n+2 de (2i + 3)? Progressions aritmètiques Una seqüència de valors forma una progressió aritmètica si la diferència entre qualsevol terme i el seu predecessor immediat és constant.

Aquest increment fix s'anomena diferència ( ): A partir del terme inicial , el terme general que ocupa la posició s'obté sumant la diferència vegades: FÓRMULA: SUMA FINITA D'UNA PROGRESSIÓ ARITMÈTICA La suma dels termes d'una progressió aritmètica compresos entre els índexs i val: Aquesta fórmula es dedueix mitjançant una agrupació simètrica de termes: i i=8 n 2 j = 0 j = i 8 i = j + 8 i = 8 j = 0 i = n j = n 8 i = i=8 n 2 (j + j=0 n 8 8)2 k = k=1 n , k = 2 n(n + 1) k=1 n 2 6 n(n + 1)(2n + 1) d a = i+1 a + i d a 0 i i a = i a + 0 i d m n a = i=m n i 2 (a + a )(n m + 1) m n Sumem el primer terme amb l'últim: .

1 a + m a n Observem que la suma del segon terme i el penúltim dona el mateix resultat: . Totes les parelles simètriques sumen el mateix. 2 a + m+1 a = n 1 (a + m d) + (a n d) = a + m a n Si el nombre de sumands és parell, es formen exactament parelles, cadascuna amb suma . 3 n m + 1 2 n m+1 a + m a n Si és senar, queda un terme central desemparellat, el valor del qual és precisament la mitjana aritmètica dels extrems: . En afegir-lo a les parelles restants, s'arriba exactament a la mateixa expressió global.

4 n m + 1 2 a +a m n 2 n m Fonaments Matemàtics: Lògica, Inducció i Conjunts 6 COMPROVA-HO 4 Per què la suma de termes d'una progressió aritmètica és invariant a l'agrupació per parelles equidistants dels extrems?

Progressions geomètriques Una successió constitueix una progressió geomètrica quan cada terme s'obté de multiplicar l'anterior per una quantitat constant no nul·la anomenada raó ( ): Coneixent el terme inicial , l'expressió del terme general és: FÓRMULA: SUMA D'UNA PROGRESSIÓ GEOMÈTRICA (R 1) Per a qualsevol progressió geomètrica amb raó , la suma entre els índexs i s'obté amb: La demostració es basa en multiplicar el sumatori pel factor : En treure factor comú , l'expressió esdevé: Com que , podem dividir ambdós costats entre i s'obté directament la fórmula. COMPROVA-HO 5 Què passa a la fórmula de la suma de la progressió geomètrica si la raó és r = 1?

Productoris i les seves propietats De manera anàloga a la suma, el productori denota la multiplicació seqüencial dels termes d'una família numerable mitjançant la lletra grega pi majúscula: Les regles algebraiques dels productoris traslladen les propietats de la multiplicació i la potenciació: Producte de factors independents: el productori d'un producte es descompon en el producte dels productoris: r a = i+1 r ai a 0 a i a = i a 0 ri r = 1 m n a = i=m n i r 1 a a n+1 m (r 1) a (r ( i=m n i) 1) = (a + m ra + m + r a )(r n m m 1) a m a (1 + m r + + r )(r n m 1) = a (r m n m+1 1) = a r m n m+1 a = m a n+1 a m r = 1 r 1 f(i) = i=m n f(m) f(m + 1) f(n 1) f(n) Fonaments Matemàtics: Lògica, Inducció i Conjunts 7 Potència d'un productori: elevar cada factor a un exponent fix equival a elevar el resultat complet del productori: Extracció d'un factor constant: com que la constant es multiplica en cadascun dels factors, surt elevada al nombre total de termes: ERROR FREQÜENT: EXTREURE UNA CONSTANT D'UN PRODUCTORI SENSE ELEVAR-LA En els sumatoris, treure una constant manté el factor comú lineal: .

En canvi, en els productoris, la constant apareix multiplicada a cada terme. Si s'extreu fora del productori sense la potència, es comet un error greu. Recorda sempre aplicar l'exponent del nombre total de termes: c^{n-m+1}. La següent taula contraposa les propietats paral·leles entre els dos operadors: Característica Sumatori ( ) Productori ( ) Operació subjacent Suma reiterada Multiplicació reiterada Nombre de termes Comportament de constants Separació d'operacions Separa sumes: Separa productes: IDEES CLAU Per conveni explícit, el zero és considerat un nombre natural ( ). La part entera és l'enter únic que compleix . El nombre de termes d'un sumatori o productori entre els límits i és .

La suma d'una progressió aritmètica és . La suma d'una progressió geomètrica amb raó val . En extreure una constant d'un productori, aquesta queda elevada al nombre de sumands: . (f(i) i=m n g(i)) = f(i) ( i=m n ) g(i) ( i=m n ) (f(i)) = i=m n c f(i) ( i=m n ) c c n m + 1 c i=m n f(i) = c f(i) n m+1 i=m n cf(i) = c f(i) c n m + 1 n m + 1 cf(i) = c f(i) cf(i) = c f(i) n m+1 (f + g) = f + g (f g) = f g 0 N E(x) E(x) x < E(x) + 1 m n n m + 1 a = i=m n i 2 (a +a )(n m+1) m n r = 1 a = i=m n i r 1 a a n+1 m cf(i) = i=m n c f(i) n m+1 i=m n Fonaments Matemàtics: Lògica, Inducció i Conjunts 8 COMPROVA EL QUE HAS APRÈS 6. Com s'expressa el productori en funció de ? 7.

Quin és el valor de la suma obtinguda mitjançant la fórmula d'una progressió aritmètica? Test Encercla la resposta correcta. Les solucions són al final. 8. Quin conjunt inclou el zero segons el conveni d'aquesta matèria? 9. Quants termes conté un sumatori amb límits des de i = m fins a n (amb n m)? 10. Com queda una constant c en extreure-la d'un productori de n - m + 1 termes? 11. Quina és la suma dels termes d'una progressió geomètrica si la raó és r 1? 2 Lògica proposicional — Sintaxi, semàntica i equivalències lògiques EN ACABAR SABRÀS Distingir enunciats d'altres expressions i construir fórmules ben formades.

Avaluar taules de veritat per classificar fórmules en tautologies, contradiccions o contingències. Aplicar equivalències lògiques algebraiques per simplificar fórmules i fonamentar mètodes de demostració. PENSA-HI ABANS DE LLEGIR 12 Per què en matemàtiques una afirmació del tipus «si un triangle té 4 costats, llavors la Terra és plana» es considera formalment certa?

(k i=1 n a ) i A = a i=1 n i i i=1 n Nombres enters estrictament positius a) Naturals, enters i reals b) Només els enters i reals c) Només els racionals positius d) n - m a) n - m + 1 b) n + m - 1 c) n - m - 1 d) Elevada a la potència n - m + 1 a) Dividida pel nombre de termes b) Multiplicada pel nombre de termes c) Multiplicant directament com c d) ( - ) / (r - 1) a) a n+1 a m ( + ) / (r + 1) b) a n+1 a m ( - ) / r c) a n a m ( + ) / 2 d) a m a n Fonaments Matemàtics: Lògica, Inducció i Conjunts 9 La lògica proposicional és la branca de la lògica matemàtica que modela i analitza el raonament formal mitjançant oracions que poden ser veritables o falses.

ESQUEMA Estructura de la lògica proposicional Sintaxi de la lògica proposicional: enunciats i fórmules ben formades Un enunciat o proposició és una expressió del llenguatge susceptible de ser qualificada com a certa o falsa. Les afirmacions amb significat complet tenen valor de veritat, mentre que les oracions interrogatives, imperatives o les expressions incompletes no constitueixen proposicions. EXEMPLES D'ENUNCIATS I NO ENUNCIATS Són enunciats vàlids: « » (que és fals), «la pissarra és blava» o «si llavors la pissarra és blava». En canvi, no són enunciats expressions sense valor de veritat com ara « », «la pissarra», la pregunta «Quina hora és?» o l'ordre «Esborreu la pissarra!».

Distingim entre enunciats atòmics o indescomponibles (representats per lletres proposicionals com ) i fórmules compostes, construïdes connectant àtoms mitjançant símbols lògics.

Sintaxi Regles de formació d'enunciats i fórmules Àtoms i connectives Lletres proposicionals, negació i operadors binaris Fórmules ben formades Construcció recursiva amb parèntesis Semàntica Valors de veritat i avaluació Taules de veritat Assignacions binàries 0 i 1 Classificació Tautologies, contingències i contradiccions Equivalències Transformacions i àlgebra deductiva Lleis fonamentals De Morgan, distributiva, absorció i dualitat Equivalències per a proves Traducció d'implicacions i contrarecíproc 2 + 3 = 6 2 + 3 = 6 2 + 3 p, q, r, s Fonaments Matemàtics: Lògica, Inducció i Conjunts 10 DEFINICIÓ RECURSIVA DE FÓRMULA BEN FORMADA L'alfabet de la lògica proposicional conté lletres proposicionals, connectives unàries ( ), connectives binàries ( ) i parèntesis.

Una seqüència finita de símbols és una fórmula ben formada si compleix: Els parèntesis delimiten l'abast de les connectives binàries per evitar ambigüitats estructurals; per exemple, distingeixen de . La negació no s'acompanya de parèntesis propis (s'escriu i no ). Per conveni, els parèntesis exteriors d'una fórmula es poden suprimir. COMPROVA-HO 13 Quina diferència estructural hi ha entre l'expressió «2 + 5» i l'expressió «2 + 5 = 7» des de la perspectiva lògica? Semàntica i taules de veritat La semàntica assigna a cada fórmula un valor de veritat: 1 per indicar certesa i 0 per indicar falsedat.

El valor de les fórmules compostes depèn exclusivament dels valors dels seus àtoms mitjançant les regles de les connectives. Negació ( ) Conjunció ( ) Disjunció ( ) Condicional ( ) Bicondicional ( ) 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 A la implicació , la fórmula rep el nom d'antecedent i el de conseqüent. L'operador avalua la coincidència de valors entre ambdues subfórmules. ERROR FREQÜENT Assumir que si l'antecedent és fals (0), la implicació ha de ser falsa. La implicació lògica només és falsa quan l'antecedent és cert i el conseqüent és fals ( ). Quan l'antecedent és fals, el condicional sempre pren el valor cert ( i ). ¬ , , , Tota lletra proposicional és una fórmula.

1 Si és una fórmula, la seva negació també és una fórmula. 2 φ ¬φ Si i són fórmules i és una connectiva binària ( ), llavors és una fórmula. 3 φ ψ , , , (φ ψ) (p q) r p (q r) ¬p (¬p) φ ψ ¬φ φ ψ φ ψ φ ψ φ ψ φ ψ φ ψ φ φ ψ 1 0 = 0 0 0 = 1 0 1 = 1 Fonaments Matemàtics: Lògica, Inducció i Conjunts 11 COMPROVA-HO 14 Quin és el valor de veritat de la implicació «Si 2 + 2 = 5, llavors la neu és verda»? Classificació semàntica: tautologia, contradicció i contingència Avaluades totes les combinacions de valors dels àtoms mitjançant una taula de veritat, les fórmules es classifiquen en: Tautologia: fórmula que resulta certa en totes les assignacions possibles dels seus àtoms.

La columna final de la seva taula conté exclusivament uns. Exemples: , o . Contradicció (o insatisfactible): fórmula que pren el valor 0 en totes les assignacions possibles. Exemples: o la negació de qualsevol tautologia. Satisfactible: fórmula que pren el valor 1 en com a mínim una assignació. Les tautologies en formen un subconjunt. Si pren tant valors 1 com valors 0, es tracta d'una contingència. Construir una taula de veritat consisteix a desplegar les combinacions d'interpretacions per a àtoms i calcular els passos intermedis de les subfórmules.

EXEMPLE DE TAULA DE VERITAT PER A UNA FÓRMULA DE TRES VARIABLES Avaluem la fórmula : 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 Com que la darrera columna conté tant valors 1 com 0, la fórmula és satisfactible i contingent. COMPROVA-HO 15 Si una fórmula és satisfactible, és necessàriament una tautologia?

p ¬p p p (p q) p p ¬p 2n n ¬(p ¬r) (p ¬q) p q r ¬r p ¬r ¬(p ¬r) ¬q p ¬q ¬(p ¬r) (p ¬q) Fonaments Matemàtics: Lògica, Inducció i Conjunts 12 Equivalència lògica i àlgebra d'operacions Dues fórmules i són equivalents ( ) quan prenen exactament els mateixos valors de veritat en totes les assignacions possibles dels seus àtoms. Totes les tautologies són equivalents entre si (representades per la constant 1), i totes les contradiccions són equivalents entre si (representades per 0).

Quan en una equivalència només intervenen les connectives i juntament amb les constants 0 i 1, s'aplica el principi de dualitat: si s'intercanvia cada per i cada 0 per 1 (i viceversa), s'obté una nova equivalència vàlida anomenada dual. Nom de la llei Forma directa Forma dual Distributiva Lleis de De Morgan Absorció Idempotència Commutativa Associativa Element neutre Element absorbent Complementari Doble negació / Constants , La propietat associativa permet prescindir de parèntesis en cadenes d'una mateixa operació ( ), i la distributiva es generalitza a conjuncions o disjuncions de múltiples termes: .

Equivalències clau per a les demostracions matemàtiques Per demostrar propietats sense taules de veritat és fonamental expressar els condicionals i bicondicionals mitjançant conjuncions, disjuncions i negacions. Aquestes equivalències connecten directament amb les estratègies bàsiques de demostració (vegeu «Mètodes de demostració — Estratègies i regles d'inferència bàsiques»).

Concepte Equivalència fonamental Negació o variant Traducció de la implicació Traducció de la doble implicació Negació de la doble implicació Contrarecíproc — φ ψ φ ψ φ (ψ θ) (φ ψ) (φ θ) φ (ψ θ) (φ ψ) (φ θ) ¬(φ ψ) ¬φ ¬ψ ¬(φ ψ) ¬φ ¬ψ φ (φ ψ) φ φ (φ ψ) φ φ φ φ φ φ φ φ ψ ψ φ φ ψ ψ φ φ (ψ θ) (φ ψ) θ φ (ψ θ) (φ ψ) θ φ 1 φ φ 0 φ φ 1 1 φ 0 0 φ ¬φ 1 φ ¬φ 0 ¬¬φ φ ¬1 0 ¬0 1 p q r φ (ψ 1 ψ ) n (φ ψ ) 1 (φ ψ ) n φ ψ ¬φ ψ ¬(φ ψ) φ ¬ψ φ ψ (φ ψ) (ψ φ) φ ψ (φ ψ) (¬φ ¬ψ) ¬(φ ψ) (φ ¬ψ) (ψ ¬φ) ¬(φ ψ) (φ ψ) (¬φ ¬ψ) φ ψ ¬ψ ¬φ Fonaments Matemàtics: Lògica, Inducció i Conjunts 13 Concepte Equivalència fonamental Negació o variant Reducció a l'absurd Disjunció al conseqüent Disjunció a l'antecedent — L'operador de disjunció exclusiva (XOR), denotat per , expressa que exactament una de les dues fórmules és certa i es defineix com .

Compleix propietats algebraiques com l'associativitat , la distributivitat respecte a la conjunció , així com les identitats , , i . EXEMPLE DE DEMOSTRACIÓ ALGEBRAICA SENSE TAULA DE VERITAT Demostrem la llei d'absorció emprant únicament les propietats algebraiques: COMPROVA-HO 16 Quina és la negació lògica simplificada de la implicació «Si plou, la carretera rellisca»? φ ¬φ 0 φ ψ (φ ¬ψ) 0 ψ θ ¬ψ θ φ (ψ θ) (φ ¬ψ) θ (ψ θ) φ (ψ φ) (θ φ) φ ψ ¬(φ ψ) φ (ψ θ) (φ ψ) θ φ (ψ θ) (φ ψ) (φ θ) φ 1 ¬φ φ 0 φ φ ¬φ 1 φ φ 0 p (p q) p Apliquem l'element neutre: . 1 p (p q) (p (p q)) 1 Apliquem el complementari a la constant: . 2 (p (p q)) (p ¬p) Reagrupem per associativitat: .

3 p ((p q) (p ¬p)) Extraiem factor comú per distributivitat inversa: . 4 p (p (q ¬p)) Distribuïm sobre la disjunció: . 5 p (p p) (p (q ¬p)) Idempotència i commutativitat: . 6 p (p (¬p q)) Associem el terme dret: . 7 p ((p ¬p) q) Complementari: . 8 p (0 q) Element absorbent: . 9 p 0 Element neutre final: . 10 p Fonaments Matemàtics: Lògica, Inducció i Conjunts 14 IDEES CLAU Un enunciat és una oració que té sentit complet i que pot ser estrictament certa (1) o falsa (0). La implicació és falsa únicament quan és cert i és fals; si l'antecedent és fals, la implicació és sempre certa. Una tautologia és certa per a qualsevol combinació dels seus àtoms, mentre que una contradicció és sempre falsa.

L'equivalència lògica permet substituir subfórmules per expressions de mateix valor semàntic, com ara . El principi de dualitat permet obtenir noves equivalències vàlides intercanviant sistemàticament amb i les constants 0 amb 1. COMPROVA EL QUE HAS APRÈS 17. Per què la fórmula és una tautologia i com es denota el seu valor com a constant? 18. Quina és l'expressió equivalent a la implicació emprant el seu contrarecíproc? 19. En què es fonamenta la demostració d'una implicació pel mètode de reducció a l'absurd en lògica proposicional? Test Encercla la resposta correcta. Les solucions són al final. 20. En quin cas la implicació proposicional pren valor de veritat 0? 21.

Com s'expressa la negació d'una conjunció segons De Morgan? 22. Quina fórmula és equivalent a la implicació p q? 23. Com es defineix una fórmula contradictòria o insatisfactible?

φ ψ φ ψ φ ψ ¬φ ψ p ¬p φ ψ p q Quan antecedent és cert i conseqüent fals a) En cap assignació de valors b) Quan antecedent és fals i conseqüent cert c) Quan antecedent i conseqüent són falsos d) ¬p ¬q a) ¬p q b) p ¬q c) ¬p ¬q d) ¬p q a) ¬p q b) p ¬q c) p ¬q d) Falsa en almenys una assignació a) Certa en almenys una assignació b) Falsa en totes les assignacions c) Equivalenta la constant 1 d) Fonaments Matemàtics: Lògica, Inducció i Conjunts 15 3 Lògica de primer ordre — Relacions, quantificadors i formalització EN ACABAR SABRÀS Distingir entre relacions de diferents aritats, variables lliures i variables lligades en una fórmula.

Aplicar correctament les equivalències de negació i distributivitat de quantificadors. Evitar l'ús d'implicacions dins de quantificadors existencials en formalitzar afirmacions. Formalitzar enunciats sobre propietats aritmètiques, unicitat i fites de cardinalitat. PENSA-HI ABANS DE LLEGIR 24 Per què formalitzar «hi ha un nombre parell que és múltiple de 4» com a x (Parell(x) Múltiple4(x)) és un error lògic greu? La lògica proposicional (vegeu «Lògica proposicional — Sintaxi, semàntica i equivalències lògiques») tracta cada enunciat atòmic com un bloc indivisible sense estructura interna.

Per analitzar afirmacions matemàtiques com «tot nombre parell és múltiple de dos» o «hi ha un nombre primer més gran que cent», cal expressar propietats d'individus i relacions entre ells mitjançant la lògica de primer ordre o lògica de predicats. Components fonamentals i sintaxi DEFINICIÓ Un domini o univers del discurs és un conjunt no buit d'elements sobre els quals prenen valors les variables. Un símbol de relació d'aritat n representa una propietat o condició que depèn de individus del domini. Segons el nombre d'arguments, parlem de diferents tipus de relacions: Aritat 1 (propietats): depenen d'un sol element.

Per exemple, sobre el domini dels enters , les propietats «ser parell», «ser quadrat» o «ser múltiple de 4». En un domini de persones, «portar ulleres» o «ser alt». Aritat 2 (binàries): relacionen parelles d'individus. Per exemple, «ser menor que» ( ), «ser igual que» ( ), o «seure al costat de». En relacions binàries és habitual fer servir la notació infixa ( ) en lloc de la prefixa ( ). Aritat 3 (ternàries): depenen de tres elements, com ara « està entre i » o « ».

En bases de dades relacionals es treballa de forma natural amb relacions d'aritat arbitrària mitjançant lògica many-sorted (amb diversos dominis etiquetats com a atributs), on cada taula representa una relació i les files en són les tuples.

Una fórmula atòmica es construeix aplicant un símbol de relació d'aritat a termes (variables, constants com 0, 1, 2 o expressions complexes com o ): n Z x < y x = y xRy R(x, y) x y z x y (mod z) n n y2 x + 2 2x Fonaments Matemàtics: Lògica, Inducció i Conjunts 16 A partir de les fórmules atòmiques, definim recursivament el conjunt de totes les fórmules de la lògica de primer ordre mitjançant les connectives lògiques ( ) i els quantificadors: Tota fórmula atòmica és una fórmula. Si i són fórmules, aleshores i són fórmules (on és qualsevol connectiva binària). Si és una fórmula i és una variable, aleshores i són fórmules.

Només s'escriuen parèntesis a les connectives binàries i se'n suprimeix el parèntesi més exterior; no s'afegeixen parèntesis ni a la negació ni als quantificadors. COMPROVA-HO 25 Quina diferència estructural hi ha entre una relació d'aritat 1 i una relació d'aritat 2? Semàntica i interpretació dels quantificadors Per assignar un valor de veritat a una fórmula cal definir una interpretació, la qual exigeix fixar un univers no buit i associar relacions concretes als símbols predicatius. El quantificador universal ( ) afirma que tots els individus del domini compleixen la fórmula . El quantificador existencial ( ) afirma que almenys un individu del domini compleix la fórmula .

Sovint l'univers de variació s'especifica directament a la notació, com ara . Quan es volen restringir subconjunts de dominis més amplis dins la pròpia fórmula, s'introdueix un predicat auxiliar: per exemple, expressa la pertinença als naturals amb el predicat . Una variable en una fórmula és una variable lligada si cau sota l'abast d'un quantificador ( o ); en cas contrari, s'anomena variable lliure. Una fórmula sense variables lliures rep el nom de sentència i adquireix un valor cert o fals sota una interpretació donada. COMPROVA-HO 26 A la fórmula P(x) y Q(x, y), quin estat tenen les variables x i y?

Equivalències lògiques i no-equivalències Dues fórmules sense variables lliures són equivalents si i només si tenen el mateix valor de veritat en qualsevol domini i sota tota interpretació possible. Equivalència fonamental Nom o regla associada Negació del quantificador universal Negació del quantificador existencial Commutació de quantificadors universals Commutació de quantificadors existencials R(x , x , …

, x ) 1 2 n ¬, , , , φ ψ ¬φ (φ ψ) φ x x φ x φ x φ φ x φ φ x Z φ(x) x y(N(y) x < y) N(y) ¬ x φ x ¬φ ¬ x φ x ¬φ x y φ y x φ x y φ y x φ Fonaments Matemàtics: Lògica, Inducció i Conjunts 17 Equivalència fonamental Nom o regla associada Distributivitat de sobre la conjunció Distributivitat de sobre la disjunció D'aquestes regles bàsiques i de les equivalències clàssiques de la implicació ( ) se'n deriven altres identitats útils per simplificar o negar fórmules complexes: ERROR FREQÜENT Assumir distributivitats o commutacions que no són vàlides en general és un dels errors més habituals en lògica de predicats: COMPROVA-HO 27 Per què la fórmula x (P(x) ¬P(x)) és vàlida, però x P(x) x ¬P(x) pot ser falsa?

Patrons estàndard de formalització La traducció del llenguatge natural a la lògica de primer ordre se sosté sobre dos patrons canònics fonamentals segons el tipus d'afirmació: Tipus d'afirmació Estructura formal Lectura correcta Universal condicionada «Tots els individus que tenen la propietat A tenen la propietat B» Existencial condicionada «Hi ha almenys un individu que té tant la propietat A com la propietat B» x(φ ψ) x φ x ψ x(φ ψ) x φ x ψ φ ψ ¬φ ψ ¬ x(C(x) N(x)) x(C(x) ¬N(x)) x(N(x) ¬C(x)) ¬ x(P (x) Q(x)) x(P (x) ¬Q(x)) x(P (x) Q(x)) xP (x) xQ(x) Barrejar quantificadors diferents: no és equivalent a . L'enunciat implica , però el recíproc és fals.

Sobre els naturals, és cert (per a tot nombre n'hi ha un de més gran), però és fals (no existeix un únic natural estrictament superior a tots). 1 x y φ y x φ y x φ x y φ x y(x < y) y x(x < y) Distribuir el quantificador universal sobre la disjunció: En general, . Si indica «ser parell» i indica «ser senar» en els naturals, és veritat, però és fals. 2 x(φ ψ) x φ x ψ P (x) S(x) x(P (x) S(x)) xP (x) xS(x) Distribuir el quantificador existencial sobre la conjunció: En general, . 3 x(φ ψ) x φ x ψ x(A(x) B(x)) x(A(x) B(x)) Fonaments Matemàtics: Lògica, Inducció i Conjunts 18 PER RECORDAR-HO Mai no utilitzeu la implicació dins d'un quantificador existencial per expressar condicions.

La fórmula equival a , de manera que esdevé certa amb l'existència d'un sol objecte que no sigui de tipus , encara que no existeixi cap que compleixi . ESQUEMA Patrons clau de formalització Podem observar aquests patrons en el conegut món de blocs de Tarski, on s'analitzen figures geomètriques en un tauler: Diagrama del món de blocs de Tarski amb figures geomètriques etiquetades. Si definim les propietats (triangle), (cercle), (quadrat), els colors (blau), (negre), (gris) i les relacions relatives de posició ( a l'esquerra de ) i ( a sobre de ): «Hi ha un quadrat negre»: .

x(A(x) B(x)) x(¬A(x) B(x)) A A B Tot A compleix B Universal amb implicació: x(A(x) B(x)) Cap A compleix B x(A(x) ¬B(x)) o bé ¬ x(A(x) B(x)) Algun A compleix B Existencial amb conjunció: x(A(x) B(x)) Com a màxim un A Unicitat: x y((A(x) A(y)) x = y) T(x) C(x) Q(x) B(x) N(x) G(x) E(x, y) x y S(x, y) x y x(Q(x) N(x)) Fonaments Matemàtics: Lògica, Inducció i Conjunts 19 «Tots els cercles són blaus»: . «No hi ha cap cercle negre»: , que equival a . «Tot triangle blau té un cercle a sobre»: .

Formalització aritmètica i condicions de cardinalitat En el domini dels nombres enters , molts conceptes aritmètics es formalitzen a partir de les operacions bàsiques ( ) i la igualtat: Divisibilitat: « divideix » ( ) expressa que existeix un factor enter: Quadrat: « és un quadrat»: Primalitat: « és un nombre primer» (amb com a variable lliure): Infinitud de primers: «Hi ha infinits nombres primers» (per a tot nombre en trobem un de més gran): La formalització permet comptar quants elements verifiquen un determinat predicat utilitzant exclusivament la relació d'igualtat: EXEMPLE Volem expressar diferents fites de cardinalitat per als elements que compleixen : Com a molt un element té la propietat P: si dos elements la tenen, han de coincidir obligatòriament: Com a mínim dos elements diferents tenen P: Hi ha un únic element amb la propietat P: combinació d'existència i unicitat: Com a màxim dos elements tenen P: si en triem tres, com a mínim dos han de ser el mateix: Exactament dos elements tenen P: existeixen dos elements diferents amb la propietat i qualsevol altre individu amb la propietat és necessàriament un d'ells: x(C(x) B(x)) ¬ x(C(x) N(x)) x(C(x) ¬N(x)) x((T(x) B(x)) y(C(y) S(y, x))) Z +, x y x y k (y = x k) x k (x = k k) x x x > 1 d ((d x) (d = 1 d = x)) n p (p > n P (p)) P P x y ((P (x) P (y)) x = y) x y (x = y P (x) P (y)) x (P (x) y(P (y) y = x)) x y z ((P (x) P (y) P (z)) (x = y x = z y = z)) x y (x = y P (x) P (y) z(P (z) (z = x z = y))) Fonaments Matemàtics: Lògica, Inducció i Conjunts 20 COMPROVA-HO 28 Com es nega l'afirmació «com a molt un element compleix P»?

IDEES CLAU Un predicat d'aritat assigna una condició sobre elements d'un domini no buit. El quantificador universal requereix que la condició sigui satisfeta per tots els elements, mentre que l'existencial només requereix almenys un element que la compleixi. Negar un quantificador inverteix el seu tipus i nega l'afirmació interna: i . La commutació de quantificadors de tipus diferent no és equivalent en general: implica , però el recíproc és fals. Els enunciats de tipus «tot A és B» es formalitzen amb implicació, , mentre que «hi ha un A que és B» es formalitzen amb conjunció, . Les condicions de recompte i unicitat es construeixen comparant variables mitjançant el predicat d'igualtat.

COMPROVA EL QUE HAS APRÈS 29. Per què no s'ha d'utilitzar la implicació en el patró existencial x (A(x) B(x)) per formalitzar «hi ha algun A que és B»? 30. Com es formalitza la condició que 2 és l'únic nombre primer parell sobre el domini dels enters, usant els predicats P(x) («x és primer») i Par(x) («x és parell»)? Test Encercla la resposta correcta. Les solucions són al final. 31. Quina és la negació lògica correcta de la fórmula x (P(x) Q(x))? 32. Quina de les afirmacions sobre quantificadors barrejats és correcta en general? 33. Com es formalitza que com a molt un element del domini compleix la propietat P?

n n ¬ x φ x ¬φ ¬ x φ x ¬φ y x φ x y φ x(A(x) B(x)) x(A(x) B(x)) x (P(x) ¬Q(x)) a) x (P(x) ¬Q(x)) b) x (¬P(x) ¬Q(x)) c) x (P(x) ¬Q(x)) d) Cap de les dues fórmules implica l'altra a) y x φ implica sempre x y φ b) x y φ és equivalent a y x φ c) x y φ implica sempre y x φ d) x y (P(x) P(y)) a) x y ((P(x) P(y)) x = y) b) x y (x y (P(x) P(y))) c) x (P(x) y (y x P(y))) d) Fonaments Matemàtics: Lògica, Inducció i Conjunts 21 34. Quina equivalència és universalment vàlida per a qualsevol parell de fórmules? 4 Mètodes de demostració — Estratègies i regles d'inferència bàsiques EN ACABAR SABRÀS Justificar formalment enunciats universals i existencials emprant exemples o contraexemples.

Formular i executar demostracions directes, pel contrarecíproc i per reducció a l'absurd. Aplicar correctament el mètode per casos garantint l'exhaustivitat del domini considerat. Estructurar demostracions d'equivalències lògiques i proves d'unicitat per a propietats matemàtiques. PENSA-HI ABANS DE LLEGIR 35 Si sabem que un nombre enter elevat al quadrat és parell, podem afirmar automàticament que el nombre original també ho és sense haver de calcular una arrel quadrada inexacta? 1. Veracitat i quantificadors Per justificar la certesa d'un enunciat matemàtic cal analitzar la seva forma lògica, prestant especial atenció a la presència de quantificadors explícits o implícits.

La naturalesa de la prova canvia radicalment segons si l'afirmació és de caràcter existencial o universal. DEFINICIÓ: DEMOSTRACIÓ D'UN EXISTENCIAL I REFUTACIÓ D'UN UNIVERSAL Per demostrar un enunciat existencial és suficient trobar un element concret del domini tal que sigui cert (un sol exemple prou). Anàlogament, com que , per provar que un enunciat universal és fals cal trobar un element particular tal que sigui cert; aquest element rep el nom de contraexemple. En canvi, per verificar un enunciat universal cert de la forma sobre un domini infinit (com , o ), no n'hi ha prou amb comprovar exemples: cal construir un raonament formal o semiformal vàlid per a una variable genèrica.

El mateix s'aplica per demostrar que un existencial és fals, atès que . Quan apareixen quantificadors barrejats, l'ordre en què estan col·locats és determinant: Ordre : Cal fixar un valor concret independent de i provar que és cert. L'elecció de no pot dependre de . Ordre : Per a cada element donat, cal trobar un que compleixi . Aquí la tria de pot dependre del valor de mitjançant una expressió .

x y φ y x φ a) x (φ ψ) x φ x ψ b) x (φ ψ) x φ x ψ c) x (φ ψ) x φ x ψ d) xP (x) a P (a) ¬ xP (x) x¬P (x) xP (x) a ¬P (a) xP (x) N Z R ¬ xP (x) x¬P (x) y xP (x, y) y = a x xP (x, a) y x x yP (x, y) x y P (x, y) y x y = E(x) Fonaments Matemàtics: Lògica, Inducció i Conjunts 22 Com a fet fonamental, la condició és sempre vàlida, però el recíproc és fals en general. Objectiu a demostrar Estat Estratègia requerida Cert Donar un exemple: trobar que compleixi . Fals Donar un contraexemple: trobar tal que . Cert Fixar una constant (independent de ) tal que . Cert Per a cada , definir i provar . COMPROVA-HO 36 Per què l'enunciat « x , (x > 0 x 1)» és fals i com es refuta formalment? 2.

Demostracions formals, regles d'inferència i passos no lògics Una demostració és una justificació rigorosa de la certesa d'un enunciat mitjançant una seqüència de passos elementals que combinen implicacions bàsiques, axiomes i definicions. En la pràctica matemàtica s'utilitza un llenguatge semiformal: es manté el rigor deductiu de la lògica de primer ordre (vegeu «Lògica de primer ordre — Relacions, quantificadors i formalització»), però s'expressa en llenguatge natural estructurat amb connectors com «implica» ( ), «si i només si» ( ) o conjuncions com «i» en comptes dels símbols formals estrictes.

Els passos deductius vàlids es divideixen en dues categories essencials: Passos lògics (regles d'inferència) Són esquemes formals la validesa dels quals descansa en una tautologia subjacent de la lògica proposicional (vegeu «Lògica proposicional — Sintaxi, semàntica i equivalències lògiques»): Modus Ponens: De les premisses i es dedueix . Es fonamenta en la tautologia . Modus Tollens: De i es dedueix . Es basa en . Sil·logisme hipotètic: De i es dedueix , recolzat en . Sil·logisme disjuntiu: De i s'infereix , basat en . Principi de l'absurd: Una contradicció lògica implica qualsevol proposició ( ). Simplificació i addició: De es dedueix ; i de es dedueix .

Passos no lògics (axiomes algebraics i d'ordre a ) Són propietats matemàtiques acceptades sense demostració en el context dels conjunts numèrics bàsics: Propietats de la igualtat: Reflexiva ( ), simètrica ( ), transitiva ( ) i substitució funcional ( ). D'aquestes se'n deriven la suma membre a membre ( ) i el producte ( ).

x yP (x, y) y xP (x, y) x A, P (x) a A P (a) x A, P (x) a A ¬P (a) y A x A, P (x, y) a A x xP (x, a) x A y A, P (x, y) x y = E(x) xP (x, E(x)) A A B B (p (p q)) q ¬B A B ¬A (¬q (p q)) ¬p A B B C A C ((p q) (q r)) (p r) A o B ¬A B ((p q) ¬p) q 0 p A B A A A B a = a a = b b = a a = b b = c a = c a = b E(a) = E(b) a + a = b + b aa = bb Fonaments Matemàtics: Lògica, Inducció i Conjunts 23 Operacions amb nombres reals: La commutativitat, associativitat, elements neutres (0 per a la suma, 1 per al producte), elements oposats i inversos multiplicatius per a , i la distributivitat de la multiplicació respecte a la suma.

Propietats d'ordre a : L'ordre és reflexiu, antisimètric ( ), transitiu i total ( ). És compatible amb la suma ( ) i amb el producte per no negatius ( ). A més, multiplicar per un nombre negatiu inverteix el sentit: . Clausura d'enters i racionals: La suma i el producte de naturals són naturals (on convenim que ). Si , aleshores . Si amb , aleshores i . COMPROVA-HO 37 Quina regla d'inferència lògica s'aplica si sabem que «Si plou, el terra és mullat» i observem que «El terra no és mullat»? 3. Mètodes fonamentals: prova directa, contrarecíproc i reducció a l'absurd Per demostrar una proposició condicional , on s'anomena hipòtesi i tesi, disposem de tres mètodes deductius principals.

ESQUEMA Mètodes de demostració d'implicacions Prova directa La prova directa consisteix a acceptar que la hipòtesi és certa i encadenar successives implicacions bàsiques o propietats conegudes fins a assolir la tesi : a = 0 R a b b a a = b a b b a a b a + c b + c a b c 0 ac bc a b b a 0 N a, b Z a, a + b, ab Z a, b Q b = 0 1/b Q a/b Q A B A B Mètodes de prova Estratègies deductives per a enunciats condicionals Prova directa Suposa A i dedueix B per cadenes deductives Contrarecíproc Suposa ¬B i dedueix ¬A Reducció a l'absurd Suposa A ¬B i troba una contradicció Prova per casos Descompon la hipòtesi en disjuncions exhaustives A B A A A B Fonaments Matemàtics: Lògica, Inducció i Conjunts 24 EXEMPLE: PROVA DIRECTA DE LA PARITAT D'UN POLINOMI Volem demostrar que per a tot , si és senar, aleshores és parell.

Prova pel contrarecíproc La prova pel contrarecíproc s'aplica a implicacions i utilitza l'equivalència lògica del contrarecíproc: En comptes de provar , s'assumeix la negació de la tesi ( B) com a premissa de partida i es dedueix la negació de la hipòtesi ( A): EXEMPLE: PROVA PEL CONTRARECÍPROC Sigui . Volem demostrar que si és parell, llavors és parell. Reducció a l'absurd El mètode per reducció a l'absurd es basa en la tautologia . Té dues variants segons l'estructura de la proposició: 1. Forma general (per provar un enunciat ): Se suposa cert i s'arriba a una contradicció manifesta (0), verificant així que ha de ser veritable. 2.

Forma específica per a implicacions ( ): Es basa en l'equivalència . S'assumeix conjuntament que la hipòtesi és certa ( ) i que la tesi és falsa ( ), derivant d'ambdues premisses una contradicció. n Z n n + 2 4n 1 Hipòtesi: Suposem que és senar. Per definició d'enter senar, existeix tal que . 1 n k Z n = 2k + 1 Substitució algebraica: Calculem l'expressió avaluant : 2 n n + 2 4n 1 = (2k + 1) + 2 4(2k + 1) 1 = (4k + 2 4k + 1) + 8k + 4 1 = 4k + 2 12k + 4 Factorització i conclusió: Traient factor comú 2 obtenim . Com que , el terme és un enter. Per tant, l'expressió és de la forma , la qual cosa conclou que és parell.

3 2(2k + 2 6k + 2) k Z m = 2k + 2 6k + 2 2m A B p q ¬q ¬p A B ¬ ¬ ¬B ¬A n Z n2 n Formulació del contrarecíproc: La hipòtesi és i la tesi és . El seu contrarecíproc és , és a dir: «si és senar, llavors és senar». 1 A : n s parell 2 e ˊ B : n s parell e ˊ ¬B ¬A n n2 Desenvolupament: Si és senar, per a algun . Elevant al quadrat: 2 n n = 2k + 1 k Z n = 2 (2k + 1) = 2 4k + 2 4k + 1 = 2(2k + 2 2k) + 1 Conclusió: Com que és enter, és de la forma , és a dir, senar ( ). Queda demostrat l'enunciat original.

3 2k + 2 2k n2 2m + 1 ¬A p ¬p 0 A ¬A A A B (p q) ((p ¬q) 0) A ¬B Fonaments Matemàtics: Lògica, Inducció i Conjunts 25 EXEMPLE: RACIONALITAT I IRRACIONALITAT PER REDUCCIÓ A L'ABSURD Demostrem que la suma d'un nombre racional i un d'irracional és irracional. COMPROVA-HO 38 Quina premissa inicial cal assumir per demostrar per reducció a l'absurd que «Si xy > 1, llavors x > 1 o y > 1»? 4. Demostració de disjuncions, prova per casos i equivalències Demostració d'una disjunció i disjunció al conseqüent Per demostrar una sentència disjuntiva pura , s'aplica l'equivalència lògica .

L'estratègia consisteix a suposar que un dels disjunts és fals ( ) i demostrar que l'altre ha de ser obligatòriament cert ( ). Si tenim múltiples disjunts , se suposa la negació dels primers ( ) i es dedueix l'últim ( ). Quan la disjunció apareix com a conseqüent d'una implicació , s'utilitza la propietat . Es pren com a punt de partida la hipòtesi conjuntament amb , i es dedueix . Demostració per casos (esgotament) El mètode per casos es fonamenta en la tautologia: Quan la hipòtesi conté una disjunció explícita a l'antecedent , aquesta equival exactament a provar cadascuna de les implicacions independents , ja que . r x Identificació d'hipòtesi i tesi: Sigui . Volem provar .

1 A : r Q x / Q B : r + x / Q Supòsit d'absurd ( ): Suposem simultàniament que , i que la tesi falla, és a dir, . 2 A ¬B r Q x / Q r + x = q Q Deducció de la contradicció: Aïllant la variable irracional tenim . Com que , per la propietat de clausura de la diferència de racionals es compleix que , el que implica . 3 x = q r q, r Q q r Q x Q Absurd: Arribem a , una contradicció flagrant. Per tant, la suma és necessàriament irracional. 4 x Q x / Q r + x B C q r ¬q r ¬B C B 1 B 2 B n n 1 ¬B , … , ¬B 1 n 1 B n A (B C) p (q r) (p ¬q) r A ¬B C (p 1 p ) n (p ((p 1 p) (p n p))) (B 1 B ) n A B 1 A, …

, B n A (q r) p (q p) (r p) Fonaments Matemàtics: Lògica, Inducció i Conjunts 26 ERROR FREQÜENT: INCOMPLETSA EN LA PARTICIÓ DE CASOS Un error molt habitual que invalida completament una prova per casos és analitzar només alguns supòsits particulars sense comprovar formalment que s'esgoten totes les possibilitats del domini. Perquè la demostració sigui vàlida és imprescindible que la disjunció dels casos cobreixi tot l'univers possible ( sigui una tautologia en aquell domini). Per exemple, en considerar la paritat d'un enter cal cobrir tant els parells com els senars; o en avaluar valors reals segons el signe, no es pot oblidar el cas zero ( ).

Demostració d'equivalències lògiques Per provar que dos enunciats són equivalents ( ), la definició requereix demostrar una doble implicació independent: 1. La implicació directa: . 2. La implicació recíproca: . Quan es tracta de demostrar l'equivalència mútua de tres o més proposicions ( ), resulta ineficient provar les implicacions dues a dues. El mètode estàndard organitza una cadena circular d'implicacions: Gràcies a la propietat transitiva del condicional, si la cadena es tanca sobre si mateixa, qualsevol parella d'enunciats queda automàticament connectada en ambdós sentits.

COMPROVA-HO 39 Quantes implicacions cal demostrar per provar que quatre proposicions són equivalents dues a dues mitjançant una cadena circular? 5. Demostració d'unicitat En molts teoremes matemàtics no només es formula l'existència d'un cert objecte amb una propietat , sinó també la seva unicitat. Afirmar que «hi ha com a molt un element que compleix » o que «si existeix, és únic» significa formalment que no poden coexistir dos elements diferents que satisfacin dita propietat simultàniament. DEFINICIÓ: CONDICIÓ FORMAL D'UNICITAT La fórmula expressa la unicitat.

En lògica de predicats, aquesta afirmació és equivalent a la sentència universal: L'esquema estàndard per demostrar la unicitat consisteix a introduir dos elements arbitraris i del domini, suposar com a hipòtesi que ambdós satisfan la propietat ( ), i deduir mitjançant passos algebraics o lògics que necessàriament x = y. A 1 A 2 A n x > 0, x = 0, x < 0 A B A B B A A , A , …

, A 1 2 n n(n 1) A 1 A 2 A n 1 A n A 1 P P ¬ x y(x = y P (x) P (y)) x y((P (x) P (y)) x = y) x y P P (x) P (y) Fonaments Matemàtics: Lògica, Inducció i Conjunts 27 PER RECORDAR-HO Provar l'enunciat «existeix un únic tal que » exigeix dues tasques completament independents: primer, una demostració d'existència (trobant o construint almenys un element que satisfaci ), i segon, la demostració d'unicitat (suposant dos elements que la compleixen i provant que han de ser idèntics). EXEMPLE: UNICITAT DE L'ELEMENT NEUTRE Demostrem que en una estructura amb una operació binària definida sobre un conjunt , si existeix element neutre, aquest és únic.

COMPROVA-HO 40 Quina és l'estructura de les premisses inicials quan s'afronta una prova d'unicitat? IDEES CLAU Per demostrar un existencial o refutar un universal és suficient aportar un únic exemple o contraexemple. La implicació és vàlida, però el recíproc no ho és en general. La prova pel contrarecíproc transforma l'objectiu en la deducció directa equivalent . La reducció a l'absurd per a una implicació assumeix simultàniament la certesa de la hipòtesi i la falsedat de la tesi ( ) per derivar una contradicció. En una prova per casos cal garantir formalment que el conjunt de casos considerats exhaureix la totalitat de possibilitats del domini.

Per demostrar la unicitat d'una propietat se suposa que dos elements la verifiquen ( ) i es dedueix que són iguals ( ). x P (x) P A Definició de la propietat: Un element és neutre si per a tot es compleix . 1 u A x A x u = u x = x Supòsit de dos neutres: Suposem que tant com són elements neutres per a l'operació . 2 e 1 e 2 Aplicació creuada de la propietat de neutre: Com que és neutre aplicat a l'element , tenim que . Com que és neutre aplicat a l'element , tenim que . 3 e 2 e 1 e 1 e = 2 e 1 e 1 e 2 e 1 e = 2 e 2 Conclusió: Per la propietat transitiva i simètrica de la igualtat, , la qual cosa imposa que .

4 e = 1 e 1 e = 2 e 2 e = 1 e2 x yP (x, y) y xP (x, y) A B ¬B ¬A A ¬B P P (x) P (y) x = y Fonaments Matemàtics: Lògica, Inducció i Conjunts 28 COMPROVA EL QUE HAS APRÈS 41. En què es diferencia metodològicament provar un existencial de provar un universal sobre un conjunt infinit? 42. Com s'estructura deductivament la prova d'una implicació amb disjunció al conseqüent de la forma ? 43. Quins dos passos lògics són estrictament necessaris per provar l'enunciat «existeix un únic tal que »? Test Encercla la resposta correcta. Les solucions són al final. 44. Com es refuta un enunciat de la forma x P(x)? 45. Quin és el punt de partida en la prova pel contrarecíproc de A B? 46.

Quina condició és obligatòria perquè una prova per casos sigui vàlida? 47. Com es demostra formalment la unicitat de la propietat P?

A (B C) x P (x) Provant que P(x) té excepcions infinites a) Aportant un contraexemple particular b) Assumint que ¬P(x) genera contradicció c) Demostrant ¬P(x) per a tot x d) Suposar que A és fals a) Suposar que B és cert b) Suposar que B és fals c) Suposar A i ¬B alhora d) Que cada cas es provi per reducció a l'absurd a) Que tingui exactament dos casos b) Que els casos no tinguin intersecció c) Que els casos esgotin tot el domini d) Provant !x P(x) amb un exemple a) Suposant P(x) P(y) i deduint x = y b) Provant x P(x) c) Provant que ¬P(x) és contradicció d) Fonaments Matemàtics: Lògica, Inducció i Conjunts 29 5 Inducció simple, variants i aplicacions EN ACABAR SABRÀS Formular i estructurar amb precisió la redacció formal del principi d'inducció simple.

Aplicar la tècnica d'inducció a identitats algebraiques, desigualtats i problemes de divisibilitat. Analitzar la complexitat computacional d'algorismes i resoldre recurrències discretes mitjançant inducció. PENSA-HI ABANS DE LLEGIR 48 Com podem tenir la certesa absoluta que una fórmula és certa per a infinits nombres naturals fent només dues comprovacions finites? La demostració de propietats sobre els nombres naturals requereix eines específiques adaptades a la seva estructura discreta i ordenada. El mètode fonamental per excel·lència és el principi d'inducció matemàtica, que permet verificar una quantitat infinita d'afirmacions mitjançant un procediment finit de dos passos.

ESQUEMA Estructura del tema d'Inducció Matemàtica Inducció matemàtica 5 Inducció simple, variants i aplicacions 6 Inducció completa i recurrències Inducció Simple Pas base i pas inductiu estàndard Múltiples passos base Casos inicials finits abans del pas inductiu Àlgebra i Sumatoris Sumes notables, productes i desigualtats Complexitat i Recurrències Triangulació de Gauss i Torres de Hanoi Inducció Completa H.I. estesa a tots els predecessors Fonaments Matemàtics: Lògica, Inducció i Conjunts 30 Fonament lògic i estructura canònica Sigui un predicat que depèn d'un nombre natural , i sigui (on , és a dir, amb ).

El principi d'inducció simple afirma l'equivalència lògica: DEFINICIÓ El principi d'inducció simple estableix que per demostrar una propietat per a tot enter , n'hi ha prou de validar el cas inicial i provar que la validesa d'un cas predecessor implica la del següent. A la pràctica, redactem la demostració respectant escrupolosament l'esquema formal canònic: ERROR FREQÜENT L'error més penalitzat en els exàmens és oblidar utilitzar explícitament la hipòtesi d'inducció en la justificació del pas inductiu, o assumir directament el que es vol demostrar ( ) en lloc de partir de per arribar a deduir . Sempre cal assenyalar el punt exacte de la igualtat o desigualtat on s'aplica la H.I.

COMPROVA-HO 49 Quina és la diferència clau entre la hipòtesi d'inducció i la tesi d'inducció en el pas inductiu? Inducció aplicada a sumatoris i productoris Els operadors de sumatori i productori (vegeu «Preliminars — Notació, sumatoris, progressions i productoris») presenten una definició recursiva natural: separar l'últim terme permet aïllar l'expressió acumulada fins a i substituir-la per la fórmula predita per la H.I. P (n) n n fixat 0 0 s considerat natural per conveni e ˊ 0 i el domini s a la classe e ˊ 0 com a base admissible n a partir den , P (n) s cert si i nom s siP (n ) i n > 0 e ˊ e ˊ 0 n (P (n 0 1) P (n)) n amb n a partir den 0 Pas Base: Es comprova directament la veracitat de .

1 P (n ) 0 Pas Inductiu: Suposem un enter arbitrari . Hipòtesi d'Inducció (H.I.): Assumim que és cert. Tesi d'Inducció: Volem veure que és cert. 2 n > n 0 P (n 1) P (n) En efecte: Es desenvolupa el raonament deductiu, manipulant l'expressió associada a fins a aplicar-hi explícitament la hipòtesi . 3 P (n) P (n 1) P (n) P (n 1) P (n) n 1 Fonaments Matemàtics: Lògica, Inducció i Conjunts 31 EXEMPLE Demostrem per a tot la suma dels primers enters positius: Pas Base ( ): El costat esquerre és 1, i el dret és . Es compleix. Pas Inductiu: Sigui . H.I.: . Tesi: Volem veure que . En efecte: Separem l'últim sumand de la suma: Substituint la H.I.

en el bloc anterior: Queda demostrada la igualtat per a tot . Tipus d'expressió Fórmula canònica demostrable Cas base habitual Progressió aritmètica Quadrats d'enters Telescòpica fraccionària Productori elemental Progressió geomètrica COMPROVA-HO 50 Quin és el mecanisme comú emprat en la tesi per poder utilitzar la H.I. en sumatoris i productoris? Desigualtats i comportament asimptòtic En abordar desigualtats per inducció, el pas crític rau en la preservació del sentit de la relació d'ordre en aplicar la H.I.

D'acord amb els mètodes de demostració (vegeu «Mètodes de demostració — Estratègies i regles d'inferència bàsiques»), sovint s'empra la transitivitat de la desigualtat: n amb n almenys1 n i = i=1 n 2 n(n + 1) n = 1 1(1 + 1)/2 = 1 n > 1 i = i=1 n 1 2 (n 1)n i = i=1 n 2 n(n+1) i = i=1 n i + ( i=1 n 1 ) n + 2 (n 1)n n = = 2 n n + 2n 2 2 n(n + 1) n amb n almenys 1 Suma de a = i 2 (a +a )(n m+1) m n n = m Suma de i = 2 6 n(n+1)(2n+1) n = 1 Suma de = i(i+1) 1 n+1 n n = 1 Producte de (1 ) = k 1 n 1 n = 2 Suma de a = i per a r = r 1 a a n+1 m 1 n = m A(n) > B(n 1) × c i B(n 1) × c > B(n) conclou A(n) > B(n) Fonaments Matemàtics: Lògica, Inducció i Conjunts 32 Aquest enfocament és essencial per analitzar taxes de creixement.

Per exemple, relacions com o s'estableixen observant com el factor addicional del factorial supera la raó exponencial en créixer el valor de . PER RECORDAR-HO En una desigualtat d'inducció, no intentis calcular el valor absolut de cada membre: acota sempre per trànsit un dels costats utilitzant la relació que et proporciona la hipòtesi inductiva. Divisibilitat sobre enters Les proposicions de divisibilitat solen presentar-se com a divideix f(n), és a dir, per a algun enter . En el pas inductiu, l'estratègia general consisteix a descompondre expressant-lo en funció de , aïllant un múltiple visible del divisor. EXEMPLE Demostrem que per a tot , l'expressió és múltiple de 210. Pas Base ( ): .

Com que , 0 és múltiple de 210. Pas Inductiu: Sigui . H.I.: per a algun enter , d'on . Tesi: Volem veure que per a algun enter . En efecte: Descomponem la potència utilitzant propietats dels exponents: Desenvolupant els termes: Com que és un enter, hem obtingut un múltiple de 210, completant la demostració. COMPROVA-HO 51 Per què es reorganitza algebraicament l'expressió en els problemes de divisibilitat durant el pas inductiu?

Variants d'inducció simple: múltiples casos base En determinades ocasions, el comportament d'una propietat o el domini d'aplicació del pas inductiu no comença immediatament en el primer terme, o bé el pas inductiu requereix una regularitat que només es manté a partir d'un cert llindar . En aquesta variant, l'esquema d'inducció simple s'ajusta avaluant explícitament un conjunt finit de casos inicials: 3 < n (n + 2)! 4 < n n!

n f(n) = k × a k f(n) f(n 1) n a partir de 0 6 2n+1 6 n = 0 6 2(0)+1 6 = 6 6 = 0 0 = 210 × 0 n > 0 6 2(n 1)+1 6 = 6 2n 1 6 = 210k k 6 = 2n 1 210k + 6 6 2n+1 6 = 210m m 6 2n+1 6 = 6 × 2 6 2n 1 6 = 36(210k + 6) 6 36 × 210k + 216 6 = 36 × 210k + 210 = 210(36k + 1) 36k + 1 n > 1 n 0 Pas Base: Es verifica la validesa individual per a . 1 P (n ), P (n + 0 0 1), fins a P (n ) 1 Pas Inductiu: Per a tot , se suposa la certesa de i es demostra . 2 n > n 1 P (n 1) P (n) Fonaments Matemàtics: Lògica, Inducció i Conjunts 33 Aquesta tècnica és necessària quan la relació inductiva només funciona de forma estable a partir d'un índex avançat, mentre que els primers valors es comproven manualment.

Aplicacions a la complexitat d'algorismes i àlgebra lineal La complexitat d'algorismes s'estudia quantificant el consum de recursos en funció de la mida de l'entrada. En molts algorismes matricials, les relacions de recurrència permeten deduir i certificar la quantitat d'operacions bàsiques. Triangulació de Gauss En el mètode d'eliminació gaussiana per a una matriu quadrada de mida , es comptabilitzen les multiplicacions i divisions necessàries per transformar-la en una matriu triangular superior.

El nombre d'aquestes operacions satisfà: Mitjançant el principi d'inducció simple, es demostra que el nombre total d'operacions val: En el cas general d'una matriu de dimensions (on n és menor o igual a m), el nombre d'operacions obeeix la relació recurrent amb , la qual té com a solució tancada verificable inductivament: Càlcul de determinants per menors Si es calcula el determinant d'una matriu d'ordre desenvolupant per files o columnes, la quantitat de multiplicacions requerides obeeix la recurrència i quan .

Amb inducció simple es comprova fàcilment que el cost computacional queda fitat per: Problemes discrets: recurrències, Hanoi i geometria La inducció matemàtica és l'eina natural per formalitzar solucions a problemes de combinatòria discreta que es descriuen recursivament. Les Torres de Hanoi El conegut problema de les Torres de Hanoi consisteix a traslladar una pila de discs de radis decreixents d'un pal inicial a un pal de destí, emprant un pal auxiliar, amb la restricció de moure un únic disc cada vegada i no col·locar mai un disc sobre un altre de mida menor.

n × n a = 1 0 i a = n n(n 1) + a per a n > n 1 1 a = n 3 n n 3 n × m O(n, m) = m(n 1) + O(n 1, m 1) O(1, m) = 0 O(n, m) = 6 n(n 1)(3m n + 2) n × n a n a = 1 0 a = n n × a + n 1 n n > 1 n! s menor o igual a a < e ˊ n n × n! per a tot n a partir de 2 n Fonaments Matemàtics: Lògica, Inducció i Conjunts 34 Esquema clàssic del joc de les Torres de Hanoi amb discs ordenats Per resoldre el trencaclosques amb discs, cal realitzar tres fases: Això defineix l'equació en recurrència , amb la condició inicial . Mitjançant inducció simple, es demostra immediatament que el nombre mínim de passos és f(n) = 2^n - 1.

Enrajolats de taulers deficients Considerem un tauler quadrat de dimensions al qual s'ha retirat una casella de (tauler deficient). Mitjançant inducció simple es demostra que sempre es pot cobrir la superfície restant sense solapaments utilitzant peces en forma de «L» (trominós de tres caselles): En el pas inductiu, es divideix el tauler de en quatre quadrants de mida . Un quadrant conté la casella eliminada original. En els altres tres quadrants, es col·loca una peça en «L» centrada que cobreix justament una cantonada de cadascun, convertint els quatre quadrants en taulers deficients de mida inferior que admeten solució per hipòtesi d'inducció.

n Moure els discs superiors al pal auxiliar ( moviments). 1 n 1 f(n 1) Moure el disc més gran restant directament al pal final (1 moviment). 2 Moure els discs del pal auxiliar sobre el disc gran ( moviments). 3 n 1 f(n 1) f(n) = 2f(n 1) + 1 f(1) = 1 2 × n 2n 1 × 1 2 × n 2n 2 × n 1 2n 1 Fonaments Matemàtics: Lògica, Inducció…