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

I 0 flashcards i 11 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): sumatoris, lògica, mètodes de demostració, inducció matemàtica, teoria de conjunts i relacions d'equivalència.

APREN.AI Índex 1 Sumatoris, productoris i progressions La notació de sumatori i manipulació d'índexs Propietats algebraiques dels sumatoris Progressions aritmètiques i la seva suma finita Progressions geomètriques i la seva suma finita Notació de productori i les seves propietats 2 Lògica proposicional: connectives, taules de veritat i equivalències Enunciats i construcció de fórmules ben formades Semàntica de les connectives i taules de veritat Equivalència lògica i àlgebra de Boole Connectives derivades i transformacions sintàctiques 3 Lògica de primer ordre: predicats, quantificadors i formalització Predicats, relacions i univers del discurs Sintaxi de la lògica de primer ordre i variables Semàntica dels quantificadors i formalització del llenguatge natural Equivalències lògiques i regles de negació Veracitat, mètodes de refutació i quantificadors barrejats Mètodes de demostració matemàtica 4 Demostració directa, contrarecíproc i reducció a l'absurd Fonaments i passos d'una deducció Axiomes bàsics del cos dels reals Demostració directa Prova pel contrarecíproc Reducció a l'absurd 5 Prova per casos, disjuncions, equivalències i unicitat Tractament d'enunciats amb disjuncions Prova per casos exhaustius Demostració d'equivalències lògiques Demostració de la unicitat Inducció matemàtica 6 Inducció simple i variants amb múltiples casos base Fonament de la inducció simple Aplicació a sumatoris i productoris Desigualtats i divisibilitat Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 1 Variants amb múltiples casos base 7 Inducció completa i aplicacions a successions recurrents Fonament del principi d'inducció completa Variants amb múltiples casos inicials i relacions de recurrència Aplicacions: divisibilitat, algorismes i combinatòria Teoria de conjunts 8 Fonaments, pertinença, inclusió i àlgebra de conjunts Noció de conjunt i relació de pertinença Principi d'extensionalitat, igualtat i inclusió Operacions fonamentals de l'àlgebra de conjunts Relacions combinades i propietats algebraiques 9 Complementari, conjunt de les parts i producte cartesià Conjunt univers i complementari relatiu Conjunt de les parts o conjunt potència Parella ordenada i producte cartesià Guia de receptes canòniques per a demostracions 10 Relacions binàries i relacions d'equivalència Definició de relació binària i representació gràfica Relacions particulars en tot conjunt Propietats fonamentals de les relacions binàries Relacions d'equivalència i caracterització circular Construcció, extensió i propietats algebraiques 11 Classes d'equivalència, conjunt quocient i particions Classes d'equivalència i conjunt quocient Propietats fonamentals de les classes d'equivalència Particions d'un conjunt El teorema fonamental de les relacions d'equivalència Càlcul explícit de classes i conjunts quocients 12 Formulari Sumatoris, productoris i progressions Lògica proposicional i equivalències Lògica de primer ordre i quantificadors Mètodes de demostració matemàtica Inducció matemàtica Teoria de conjunts i relacions d'equivalència Errors típics per evitar Solucions de les preguntes de repàs Fonaments Matemàtics: Lògica, Inducció i Teoria de 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 Teoria de Conjunts 3 1 Sumatoris, productoris i progressions EN ACABAR SABRÀS Manipular expressions amb sumatoris i productoris, incloent canvis d'índex i extracció de constants. Calcular amb exactitud el nombre de termes d'un sumatori o productori entre dos límits enters qualssevol. Deduir i aplicar les fórmules de la suma finita per a progressions aritmètiques i geomètriques.

PENSA-HI ABANS DE LLEGIR 1 Si una quantitat de diners es triplica cada any, quants anys cal sumar per saber el total acumulat i per què no serveix sumar directament els extrems dividits per dos? El llenguatge algebraic requereix mecanismes concisos per representar sumes i productes amb un nombre arbitrari o variable d'elements. Aquesta secció introdueix els operadors sumatori i productori, les seves regles fonamentals i l'estudi de dues famílies de successions essencials: les progressions aritmètiques i les geomètriques.

ESQUEMA Estructura de les eines algebraiques bàsiques La notació de sumatori i manipulació d'índexs Quan cal expressar l'addició reiterada de termes que segueixen un patró determinat, s'utilitza la lletra grega majúscula sigma ( ). El símbol compacta una seqüència de sumands definits per una expressió que depèn d'un índex enter.

Operadors compactes Notacions de sumes i productes Sumatoris ( ) Additivitat, homogeneïtat i canvis d'índex Productoris ( ) Propietats multiplicatives i exponents Progressions Successions recurrents amb patró constant Aritmètiques Diferència constant d i suma d'extrems Geomètriques Raó constant r i suma telescòpica Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 4 DEFINICIÓ DE SUMATORI Donats dos nombres enters i tals que , i una funció o terme general definit per a cada valor enter de l'índex , el sumatori es defineix com: L'índex és una variable muda; per tant, utilitzar una altra lletra com o no altera el resultat de la suma.

El valor inferior s'anomena límit inferior i el valor s'anomena límit superior. ERROR FREQÜENT Un dels errors més estesos en calcular sumatoris és determinar de manera incorrecta el nombre total de sumands. Molts estudiants calculen directament , oblidant que tant el límit inferior com el superior formen part de la suma. El recompte exacte de termes és n - m + 1. Per exemple, per a tenim termes, i nopas 5. Sovint és necessari realitzar un canvi d'índex per unificar sumatoris o fer que comencin des de zero. Si es defineix una nova variable , aleshores quan tenim , i quan tenim .

L'expressió equivalent és: COMPROVA-HO 2 Quants termes té el sumatori que va des d'un índex inferior i = -2 fins a un índex superior n = 50? Propietats algebraiques dels sumatoris Com que el sumatori és una generalització de la suma ordinària, hereta les propietats commutativa, associativa i distributiva dels nombres reals. Aquestes regles s'articulen al voltant de la linealitat i la descomposició per rangs. Propietat Formulació matemàtica Descripció funcional Additivitat El sumatori d'una suma és igual a la suma dels sumatoris individuals. Homogeneïtat (factor comú) Una constant que multiplica tots els termes pot sortir fora del sumatori.

Suma de constant pura Sumar un valor fix equival a multiplicar-lo pel nombre de termes. Descomposició d'intervals Permet separar el rang d'índexs en dos blocs consecutius amb .

m n m n f(i) i f(i) = i=m n f(m) + f(m + 1) + + f(n 1) + f(n) i k j m n n m a i=3 8 i 8 3 + 1 = 6 j = i m i = m j = 0 i = n j = n m f(i) = i=m n f(j + j=0 n m m) (f(i) + i=m n g(i)) = f(i) + i=m n g(i) i=m n c i=m n f(i) = c f(i) i=m n c = i=m n c (n m + 1) f(i) = i=m n f(i) + i=m p f(i) i=p+1 n m p < n Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 5 Dues fórmules canòniques de referència freqüent són la suma dels primers enters positius i la suma dels seus quadrats: COMPROVA-HO 3 Quant val la diferència entre el sumatori des de k = 0 fins a n + 1 de r^k i el sumatori des de k = 0 fins a n de r^k?

Progressions aritmètiques i la seva suma finita Una successió de nombres reals rep el nom de progressió aritmètica quan cada element s'obté a partir de l'anterior sumant-hi una quantitat constant fixa , denominada diferència. TERME GENERAL DE LA PROGRESSIÓ ARITMÈTICA Si la successió arrenca en l'element , el terme que ocupa la posició ve donat per: De manera anàloga, expressat des de l'índex inicial , es té . Per calcular la suma dels termes consecutius compresos entre els índexs i , hom empra el mètode de simetria d'extrems.

Si sumem el primer terme amb l'últim ( ), el segon amb el penúltim ( ), comprovem que la suma de cada parella és constant: Quan el nombre total de termes és parell, tenim exactament parelles que sumen el mateix. Quan és senar, el terme central sense parella té com a valor exacte la mitjana dels extrems, . En ambdós casos s'arriba a la mateixa expressió tancada: Progressions geomètriques i la seva suma finita Una successió s'anomena progressió geomètrica quan cada element s'obté multiplicant el terme precedent per un factor fix no nul, anomenat raó.

TERME GENERAL DE LA PROGRESSIÓ GEOMÈTRICA Amb inici a , el terme en la posició s'escriu com a potència de la raó: Per a un índex genèric de partida , la relació és .

n i = i=1 n , i = 2 n(n + 1) i=1 n 2 6 n(n + 1)(2n + 1) d a 0 i a = i a + 0 i d m a = i a + m (i m)d m n a + m a n a + m+1 a n 1 a + m+1 a = n 1 (a + m d) + (a n d) = a + m a n N = n m + 1 2 n m+1 N 2 a +a m n a = i=m n i 2 (a + a )(n m + 1) m n r a 0 i a = i a 0 ri m a = i a m ri m Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 6 Per deduir la suma finita dels termes d'una progressió geomètrica entre els índexs i (amb ), multipliquem el bloc de la suma pel binomi : En desenvolupar el producte s'obté una sèrie telescòpica on els termes intermedis s'anul·len per parelles: Aïllant la suma, obtenim la fórmula general per a la suma d'una progressió geomètrica: Tipus de progressió Relació de recurrència Terme general Fórmula de la suma finita Aritmètica Geomètrica ( ) COMPROVA-HO 4 Què passa amb la fórmula de la suma de la progressió geomètrica si la raó és r = 1?

Notació de productori i les seves propietats De forma equivalent a com el sumatori formalitza la suma reiterada, el productori utilitza la lletra grega majúscula pi ( ) per denotar multiplicacions consecutives d'una família d'elements.

DEFINICIÓ DE PRODUCTORI Per a enters i un terme general definit en aquest rang, el productori s'expressa com: Les propietats del productori es deriven de les lleis de la multiplicació i de la potenciació de factors: m n r = 1 (r 1) a (r ( i=m n i) 1) = (a + m ra + m + r a )(r n m m 1) a (1 + m r + + r )(r n m 1) = a (r m n m+1 1) = a n+1 a m a = i=m n i = r 1 a a n+1 m r 1 a (r 1) m n m+1 a = i+1 a + i d a = i a + 0 i d 2 (a +a )(n m+1) m n r = 1 a = i+1 r a i a = i a 0 ri = r 1 a a n+1 m r 1 a (r 1) m n m+1 m n f(i) f(i) = i=m n f(m) f(m + 1) f(n 1) f(n) Producte de factors independents: El producte d'una multiplicació de funcions es descompon en el producte de dos productoris separats: 1 (f(i) i=m n g(i)) = f(i) ( i=m n ) g(i) ( i=m n ) Potència d'un productori: Elevar cada factor a un exponent constant equival a elevar el productori sencer a aquesta potència: 2 c (f(i)) = i=m n c f(i) ( i=m n ) c Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 7 PER RECORDAR-HO Mentre que en els sumatoris una constant surt multiplicant de forma lineal ( ), en els productoris la constant surt elevada al nombre total de termes ( ), ja que s'està multiplicant per ella mateixa en cada pas de la iteració.

IDEES CLAU Un sumatori compacta sumes consecutives, i el nombre exacte de termes entre els límits m i n és sempre . L'operador sumatori compleix propietats de linealitat: és additiu respecte a les sumes i homogeni davant de constants multiplicatives. La suma dels n primers nombres enters positius és , i la dels seus quadrats és . La suma finita d'una progressió aritmètica és . La suma d'una progressió geomètrica amb raó és . En extreure una constant d'un productori entre m i n, aquesta queda elevada a . COMPROVA EL QUE HAS APRÈS 5. Com s'expressa el nombre total de termes en un sumatori o productori amb índex inferior m i superior n? 6.

Quina diferència hi ha entre extreure una constant d'un sumatori i extreure-la d'un productori? Test Encercla la resposta correcta. Les solucions són al final. 7. Quants termes conté el sumatori des de i = 4 fins a n = 16? 8.

Si extreiem la constant 3 del productori des de i = 1 fins a n = 5 de f(i), obtenim: Extracció d'una constant multiplicativa: Si cada terme es multiplica per una constant , aquesta es repeteix tantes vegades com sumands té el rang, és a dir vegades: 3 c n m + 1 (c i=m n f(i)) = c f(i) n m+1 i=m n c cn m+1 n m + 1 2 n(n+1) 6 n(n+1)(2n+1) 2 (a +a )(n m+1) m n r = 1 = r 1 a a n+1 m r 1 a (r 1) m n m+1 n m + 1 11 termes a) 13 termes b) 12 termes c) 14 termes d) 3 · f(i) a) 15 · f(i) b) 3 · f(i) c) 3 · f(i) d) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 8 9. Quina és la suma dels primers n nombres enters positius (1 + 2 + ... + n)? 10.

En una progressió geomètrica amb raó r 1, la suma entre m i n equival a: 2 Lògica proposicional: connectives, taules de veritat i equivalències EN ACABAR SABRÀS Distingir enunciats atòmics d'expressions no proposicionals i construir fórmules ben formades. Avaluar taules de veritat per identificar tautologies, contradiccions i fórmules satisfactibles. Demostrar equivalències lògiques sintàcticament aplicant les lleis de l'àlgebra de Boole. PENSA-HI ABANS DE LLEGIR 11 Per què en matemàtiques una afirmació de la forma «si plou, el terra és moll» es considera formalment certa si no està plovent?

La lògica proposicional estudia com es combinen enunciats mitjançant operadors per determinar la validesa o falsedat de raonaments complexos.

ESQUEMA Estructura de la lògica proposicional n(n + 1) / 2 a) n(2n + 1) / 6 b) (n + 1)² / 2 c) n(n - 1) / 2 d) ( - ) / (r - 1) a) a n+1 a m ( + )(n - m + 1) / 2 b) a m a n ( + ) / (r + 1) c) a n+1 a m ( - ) / r d) a n a m Lògica proposicional Fonament del raonament formal lògic Sintaxi Àtoms, connectives i fórmules ben formades Semàntica Taules de veritat, valors 0 i 1 Classificació Tautologies, contradiccions i satisfactibilitat Equivalències Àlgebra de Boole i mètodes de deducció Connectives derivades Condicional, bicondicional, contrarecíproc i XOR Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 9 Enunciats i construcció de fórmules ben formades Un enunciat o proposició és una expressió lingüística amb sentit complet que pot qualificar-se inequívocament com a certa o falsa.

Les oracions interrogatives, les exclamacions o les frases incompletes no són proposicions. DEFINICIÓ Distingim dos tipus d'enunciats: Enunciats atòmics: afirmacions bàsiques i simples que no contenen connectives internes. Es denoten habitualment amb lletres proposicionals com ara . Enunciats moleculars: proposicions complexes formades enllaçant o modificant enunciats atòmics mitjançant connectives lògiques. L'alfabet formal de la lògica proposicional es compon de lletres proposicionals, símbols de connectives ( com a connectiva unària; com a connectives binàries) i parèntesis d'agrupació.

Una fórmula ben formada es defineix de manera recursiva mitjançant tres regles fonamentals: Per evitar ambigüitats d'interpretació, com distingir de , s'utilitzen parèntesis. Com a norma d'escriptura, la negació unària mai no s'embolcalla amb parèntesis propis (s'escriu i no ) i els parèntesis més externs de la fórmula completa se suprimeixen sistemàticament. COMPROVA-HO 12 Per quina raó l'expressió «Quina hora és?» no és una proposició lògica vàlida? Semàntica de les connectives i taules de veritat S'utilitza el dígit 1 per designar la veritat d'una proposició i el dígit 0 per indicar-ne la falsedat.

El comportament exacte de cada connectiva s'especifica formalment mitjançant la seva taula semàntica bàsica. 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 p, q, r, s ¬ , , , Qualsevol lletra proposicional aïllada é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 un connector binari ( ), l'expressió és una fórmula. 3 φ ψ , , , (φ ψ) (p q) r p (q r) ¬p (¬p) φ ψ ¬φ φ ψ φ ψ φ ψ φ ψ Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 10 A la implicació , la subfórmula rep el nom d'antecedent i rep el de conseqüent.

L'expressió només resulta falsa quan l'antecedent és cert i el conseqüent és fals. La construcció d'una taula de veritat per a una expressió composta requereix avaluar ordenadament les columnes des dels components més senzills cap a la fórmula global considerant les assignacions possibles dels àtoms ( files per a variables). EXEMPLE Avaluem pas a pas la fórmula : Fórmula final 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 PER RECORDAR-HO Segons els valors finals obtinguts a la seva taula, les fórmules es classifiquen en: Tautologia: fórmula que pren el valor 1 en totes les assignacions possibles.

Contradicció (o fórmula insatisfactible): fórmula que pren el valor 0 en totes les assignacions possibles. Satisfactible: fórmula que resulta certa almenys per a una assignació possible de valors. Tota tautologia és satisfactible. COMPROVA-HO 13 Quina relació hi ha entre la satisfactibilitat i una contradicció? Equivalència lògica i àlgebra de Boole Dues fórmules i s'anomenen equivalents (notat ) quan tenen idèntics valors de veritat sota qualsevol assignació dels seus àtoms. Totes les tautologies són equivalents entre si (representades per 1) i totes les contradiccions són equivalents entre si (representades per 0).

φ ψ φ ψ 2n n ¬(p ¬r) (p ¬q) p q r ¬r p ¬r ¬(p ¬r) ¬q p ¬q φ ψ φ ψ Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 11 Quan en una equivalència només intervenen les connectives , , i les constants 0 i 1, s'aplica el principi de dualitat: si s'intercanvien per i la constant 0 per 1, s'obté una nova equivalència anomenada fórmula dual. Llei lògica Forma directa Forma dual Distributiva De Morgan Absorció Idempotència Commutativa Associativa Element neutre Element absorbent Complementari Doble negació i constants i La propietat associativa permet suprimir parèntesis entre operadors idèntics, escrivint directament expressions com o .

ERROR FREQÜENT És habitual confondre la negació d'un condicional amb un altre condicional. Recorda que (una conjunció) i mai . Connectives derivades i transformacions sintàctiques Les connectives derivades es poden reescriure en termes de conjuncions, disjuncions i negacions. Això resulta imprescindible per estructurar mètodes de demostració (vegeu «Mètodes de demostració matemàtica — Demostració directa, contrarecíproc i reducció a l'absurd»): Traducció del condicional: . Negació del condicional: . Bicondicional: . La seva negació compleix . Contrarecíproc: . Reducció a l'absurd: i . Disjuncions a l'antecedent i conseqüent: , i .

Disjunció exclusiva (XOR): denotada com , es defineix formalment com . És commutativa, associativa, i verifica identitats bàsiques com , , i ¬ φ (ψ θ) (φ ψ) (φ θ) φ (ψ θ) (φ ψ) (φ θ) ¬(φ ψ) ¬φ ¬ψ ¬(φ ψ) ¬φ ¬ψ φ (φ ψ) φ φ (φ ψ) φ φ φ φ φ φ φ φ ψ ψ φ φ ψ ψ φ φ (ψ θ) (φ ψ) θ φ (ψ θ) (φ ψ) θ φ 1 φ φ 0 φ φ 1 1 φ 0 0 φ ¬φ 1 φ ¬φ 0 ¬¬φ φ ¬1 0 ¬0 1 p q r p ¬q ¬p r ¬(φ ψ) φ ¬ψ φ ¬ψ φ ψ ¬φ ψ ¬(φ ψ) φ ¬ψ φ ψ (φ ψ) (ψ φ) (φ ψ) (¬φ ¬ψ) ¬(φ ψ) (φ ¬ψ) (ψ ¬φ) φ ψ ¬ψ ¬φ φ ¬φ 0 φ ψ (φ ¬ψ) 0 ψ θ ¬ψ θ (ψ θ) φ (ψ φ) (θ φ) φ (ψ θ) (φ ¬ψ) θ φ ψ ¬(φ ψ) φ 1 ¬φ φ 0 φ φ ¬φ 1 Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 12 .

Les demostracions d'equivalència es poden dur a terme sintàcticament aplicant de manera reiterada la llista de propietats algebraiques bàsiques, transformant una expressió en una altra sense haver d'escriure la taula de veritat completa. COMPROVA-HO 14 Com es demostra sintàcticament que el contrarecíproc és cert? IDEES CLAU Un enunciat és una sentència declarativa que pren de forma unívoca el valor 1 (cert) o 0 (fals). Una fórmula és una tautologia si val 1 per a totes les assignacions, contradicció si val sempre 0, i satisfactible si val 1 almenys un cop. L'equivalència del condicional material ve donada per .

El principi de dualitat permet obtenir noves equivalències vàlides intercanviant amb i el valor 0 amb l'1. L'operador XOR ( ) representa la disjunció exclusiva i equival formalment a . COMPROVA EL QUE HAS APRÈS 15. En quina única circumstància resulta falsa una implicació ? 16. Com expressen les lleis de De Morgan la negació de la conjunció i de la disjunció ? Test Encercla la resposta correcta. Les solucions són al final. 17. Quin valor pren la implicació p q si p és falsa i q és falsa? 18. Com es defineix sintàcticament la disjunció exclusiva p q? 19. Quina és la fórmula dual de la identitat d'absorció φ (φ ψ) φ?

φ φ 0 φ ψ ¬ψ ¬φ φ ψ ¬φ ψ ¬(φ ψ) φ ψ φ ψ φ ψ Indeterminat a) Insatisfactible b) Fals (0) c) Cert (1) d) ¬(p q) a) ¬(p q) b) (p q) (p q) c) p ¬q d) φ (φ ψ) φ a) φ (φ ψ) φ b) φ (φ ψ) φ c) ¬φ (¬φ ¬ψ) ¬φ d) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 13 20. Quina de les següents afirmacions descriu correctament una tautologia? 3 Lògica de primer ordre: predicats, quantificadors i formalització EN ACABAR SABRÀS Distingir l'arietat d'un predicat i el paper de les variables lliures enfront de les lligades. Formalitzar afirmacions del llenguatge natural emprant els patrons adequats amb quantificadors. Negar correctament fórmules que combinen quantificadors i connectives lògiques.

Diferenciar i justificar el comportament de fórmules amb quantificadors barrejats com i . PENSA-HI ABANS DE LLEGIR 21 És el mateix dir que «per a tot número n'hi ha un altre de més gran» que afirmar que «hi ha un número que és més gran que tots els altres»? Predicats, relacions i univers del discurs La lògica proposicional tracta els enunciats com a blocs indivisibles (vegeu «Lògica proposicional: connectives, taules de veritat i equivalències»). En canvi, la lògica de primer ordre o lògica de predicats permet analitzar l'estructura interna de cada afirmació.

Per poder establir relacions, cal definir primer un domini d'individus o univers, que és el conjunt no buit d'elements sobre els quals prenen valor les variables. Una propietat o relació s'expressa mitjançant un símbol de relació amb una arietat determinada, és a dir, el nombre d'arguments que necessita: Arietat 1: Propietats que depenen d'un únic individu. En el domini dels enters , exemples típics són «ser parell» o «ser múltiple de 4». En un grup d'alumnes, «portar ulleres» o «ser alt». Arietat 2: Propietats que relacionen parelles d'individus. Per exemple, relacions binàries com « », la igualtat « » o la congruència « ». Entre persones, «seure al costat de» o «calçar el mateix número».

Sovint s'utilitza notació infixa ( ) en comptes de prefixa ( ). Arietat 3 o superior: Relacionen tres o més individus simultàniament, com ara « està entre i » o « és congruent amb mòdul ». És certa per a tota assignació a) La seva negació és satisfactible b) Té com a mínim un 1 c) Té igual nombre de 0 que d'1 d) Z x < y x = y x y (mod 5) xRy R(x, y) x y z x y z Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 14 DEFINICIÓ Si és un símbol de relació d'arietat i els termes representen variables, constants o expressions més elaborades (com ), aleshores rep el nom de fórmula atòmica.

Sintaxi de la lògica de primer ordre i variables Les fórmules ben formades de la lògica de primer ordre es construeixen de manera recursiva a partir de les fórmules atòmiques: La presència de quantificadors distingeix dos papers essencials per a les variables dins d'una expressió: Una variable lliure és aquella que no es troba sota l'abast de cap quantificador. Una expressió amb variables lliures no té un valor de veritat fixat fins que no s'assignen valors concrets a aquestes variables. Una variable lligada està emmarcada dins de l'efecte d'un quantificador universal o existencial.

Quan totes les variables d'una fórmula estan lligades, l'expressió representa una proposició completa i té un valor de veritat definit en cada interpretació. COMPROVA-HO 22 Quina és la diferència entre una variable lliure i una variable lligada pel que fa al valor de veritat d'una fórmula? Semàntica dels quantificadors i formalització del llenguatge natural Per avaluar el sentit d'una fórmula, cal assignar-li un domini d'individus i una interpretació concreta per a cada símbol de relació: El quantificador universal ( ) afirma que la propietat es compleix per a absolutament tots els individus del domini.

El quantificador existencial ( ) expressa que hi ha com a mínim un individu en el domini que satisfà la condició . En traslladar enunciats en llenguatge natural a fórmules formals s'empren regularment dos patrons fonamentals: R n x , x , … , x 1 2 n 0, 1, y , x + 2 2 2x R(x , … , x ) 1 n Tota fórmula atòmica és una fórmula. 1 Si i són fórmules, aleshores també és una fórmula, on és qualsevol connectiva binària ( ). 2 φ ψ (φ ψ) , , , Si és una fórmula, la seva negació és una fórmula. 3 φ ¬φ Si és una fórmula i és una variable, i són fórmules.

4 φ x xφ xφ xφ φ x xφ x φ Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 15 Patró lògic Traducció natural Connectiva correcta Tots els individus de tipus tenen la propietat Condicional ( ) Hi ha algun individu de tipus que té la propietat Conjunció ( ) ERROR FREQÜENT Canviar la connectiva típica de cada quantificador és un dels errors més greus: escriure per dir «tots els són » exigeix falsament que tot l'univers sigui alhora de tipus i de tipus . De la mateixa manera, emprar per dir «hi ha un que és » fa que la fórmula sigui trivialment certa si existeix qualsevol element que no compleixi , ja que un antecedent fals valida un condicional.

Diagrama de figures geomètriques en un món de Tarski amb colors i posicions. Per exemple, sobre la graella geomètrica d'un món de Tarski com el de la figura anterior, si indica que és un triangle, que és un cercle, que és un quadrat, que és blau, que és negre, i que està sobre : «Hi ha un quadrat negre»: . «Tots els cercles són blaus»: . «No hi ha cap cercle negre»: , que equival a . « està a sobre de »: .

x(A(x) B(x)) A B x(A(x) B(x)) A B x(A(x) B(x)) A B A B x(A(x) B(x)) A B A T(x) x C(x) Q(x) B(x) N(x) S(x, y) x y x(Q(x) N(x)) x(C(x) B(x)) ¬ x(C(x) N(x)) x(C(x) ¬N(x)) a e S(a, e) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 16 COMPROVA-HO 23 Com es formalitza «cap nombre primer és un quadrat» sobre el domini dels enters amb els predicats P(x) («x és primer») i Q(x) («x és quadrat»)? Equivalències lògiques i regles de negació Dues fórmules sense variables lliures són lògicament equivalents quan prenen idèntic valor de veritat sota qualsevol domini i qualsevol interpretació dels seus símbols relacionals.

De la mateixa manera que les lleis de De Morgan operen en la lògica proposicional, els quantificadors es neguen intercanviant el quantificador i negant la fórmula interior: PER RECORDAR-HO Negar que tothom compleixi una propietat equival a trobar algú que no la compleixi ( ). Negar que n'hi hagi algun equival a afirmar que tots la incompleixen ( ).

Aquestes regles fonamentals es resumeixen a la taula següent: Llei o equivalència Formulació lògica Negació del quantificador universal Negació del quantificador existencial Commutació d'universals Commutació d'existencials Distributivitat de l'universal sobre Distributivitat de l'existencial sobre És fonamental recordar que no distribueix respecte a la disjunció ( ), ni distribueix respecte a la conjunció ( ). Per exemple, en el domini dels nombres naturals, si és « és parell» i és « és senar», l'afirmació és vertadera, però és clarament falsa.

¬ xφ x¬φ ¬ xφ x¬φ ¬ xφ x¬φ ¬ xφ x¬φ x yφ y xφ x yφ y xφ x(φ ψ) xφ xψ x(φ ψ) xφ xψ P (x) x S(x) x x(P (x) S(x)) xP (x) xS(x) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 17 ESQUEMA Elements de la lògica de primer ordre Veracitat, mètodes de refutació i quantificadors barrejats La forma en què es demostra o es refuta un enunciat depèn estrictament dels quantificadors que el componen: Per provar que un existencial és cert, n'hi ha prou de presentar un únic exemple: un element del domini tal que sigui vertader. Per exemple, és cert prenent . Per refutar un universal (demostrar que és fals), n'hi ha prou de trobar un sol contraexemple, és a dir, un element tal que .

Per exemple, l'afirmació és falsa perquè fa l'antecedent cert i el conseqüent fals. Per provar que un universal és cert sobre un domini infinit, cal fer un raonament general o demostració per a un element arbitrari. Per provar que un existencial és fals, cal demostrar que la seva negació universal és certa. Quan es combinen quantificadors de diferent tipus, l'ordre en què apareixen és decisiu. Vegem la diferència clau entre i : En , cal exhibir un únic valor fix i constant que funcioni simultàniament per a tots els . La tria de no pot dependre de . En , per a cada valor de s'ha de poder trobar un valor apropiat. Aquí pot dependre de ( ).

En conseqüència, es compleix la implicació unilateral següent: Domini d'individus Univers no buit sobre el qual prenen valors les variables Predicats i relacions Propietats amb arietat definida sobre els individus Arietat 1 Propietat que afecta un sol individu Arietat 2 o superior Relacions entre dos o més individus Quantificadors Indiquen per a quants elements s'afirma la propietat Universal ( ) La propietat es compleix per a tots els individus Existencial ( ) Hi ha com a mínim un individu que la compleix xP (x) a P (a) x R (x > 0 x 2 1 < 0) x = 0,5 xP (x) a ¬P (a) x R (x > 0 x 1) x = 0,5 xP (x) y xP (x, y) x yP (x, y) y xP (x, y) y = a x y x x yP (x, y) x y y x y = E(x) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 18 PER RECORDAR-HO L'afirmació implica , però el recíproc és fals en general.

Per exemple, en els naturals , l'afirmació és certa (prenent ), però és falsa perquè no existeix cap nombre natural que sigui estrictament més gran que tots els naturals alhora. Objectiu a demostrar Estratègia requerida cert Donar un exemple: trobar un que compleixi fals Donar un contraexemple: trobar un que compleixi cert Fixar una constant tal que sigui cert cert Per a cada , definir tal que es compleixi COMPROVA-HO 24 Per què l'afirmació y x (xy = 0) és certa sobre el domini dels nombres reals? IDEES CLAU Un predicat requereix un domini d'individus no buit i té una arietat que indica quants arguments rep.

Una variable és lliure si no està afectada per cap quantificador, i lligada quan cau sota l'abast d'un o d'un . El patró «tots els A són B» es formalitza amb el condicional , mentre que «hi ha un A que és B» es tradueix amb la conjunció . Les regles de negació estableixen que i que . Un únic contraexemple refuta una sentència universal, mentre que un únic exemple demostra la certesa d'una existencial. L'afirmació és més forta i implica , però el recíproc és fals en general. COMPROVA EL QUE HAS APRÈS 25. Com es nega l'afirmació pas a pas? 26. Per què no són equivalents les expressions i ? 27. En el domini dels nombres naturals, per què és certa però en canvi és falsa ?

y xP (x, y) x yP (x, y) N x y(x < y) y = x + 1 y x(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 A P (x, a) x A y A P (x, y) x A y = E(x) P (x, E(x)) x(A(x) B(x)) x(A(x) B(x)) ¬ xφ x¬φ ¬ xφ x¬φ y xP (x, y) x yP (x, y) x(P (x) Q(x)) x(P (x) Q(x)) xP (x) xQ(x) y x(y x) y x(x < y) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 19 Test Encercla la resposta correcta. Les solucions són al final. 28. Quin és el patró correcte per formalitzar «cap enter primer és parell» amb predicats P(x) i Q(x)? 29. Com es refuta de manera directa l'enunciat universal x (x > 0 x 1)? 30. Quina relació lògica mantenen y x P(x, y) i x y P(x, y)? 31.

Quina de les següents equivalències lògiques és FALSA en lògica de predicats?

x (P(x) ¬Q(x)) a) x (P(x) ¬Q(x)) b) x (P(x) ¬Q(x)) c) ¬ x (P(x) Q(x)) d) Negant el domini dels nombres reals a) Provant que per a tot x és fals b) Trobant un contraexemple com x = 0,5 c) Demostrant que x = 2 compleix la propietat d) Són independents i cap implica l'altra a) Són fórmules plenament equivalents b) La primera implica sempre la segona c) La segona implica sempre la primera d) x (P(x) Q(x)) x P(x) x Q(x) a) x (P(x) Q(x)) x P(x) x Q(x) b) x (P(x) Q(x)) x P(x) x Q(x) c) ¬ x φ x ¬φ d) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 20 4 Demostració directa, contrarecíproc i reducció a l'absurd EN ACABAR SABRÀS Distingir l'estructura d'una hipòtesi i d'una tesi en un enunciat condicional.

Construir una prova directa encadenant axiomes d'igualtat i ordre dels reals. Formular i desenvolupar la demostració d'un enunciat mitjançant el seu contrarecíproc. Aplicar el procediment de reducció a l'absurd per refutar la falsedat d'una proposició. PENSA-HI ABANS DE LLEGIR 32 Per què de vegades resulta molt més senzill demostrar una afirmació negant la conclusió que no pas treballant directament amb les dades de l'enunciat? Una demostració és una justificació rigorosa de la certesa d'un enunciat matemàtic mitjançant regles lògiques ben definides. Cada raonament s'articula encadenant deduccions elementals, definicions i principis bàsics que no requereixen prova.

ESQUEMA Mètodes fonamentals de demostració matemàtica Mètodes de demostració matemàtica 4 Demostració directa, contrarecíproc i reducció a l'absurd 5 Prova per casos, disjuncions, equivalències i unicitat Mètodes directes Deducció seqüencial a partir d'axiomes i hipòtesis Prova directa Seqüència A implica A' implica ...

implica B Mètodes indirectes Raonament a través de negacions i equivalències lògiques Prova pel contrarecíproc Demostració de la implicació equivalent no B implica no A Reducció a l'absurd Derivació d'una contradicció a partir de la negació Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 21 Fonaments i passos d'una deducció Quan s'escriu una demostració, s'empra habitualment un llenguatge semiformal. Aquest format expressa la lògica matemàtica amb paraules clares i connectors comuns com «i», «o», «no», «implica» ( ) o «si i només si» ( ), mentre que els quantificadors universals se solen sobreentendre pel context.

Notació formal Expressió semiformal Significat lògic i, coma (,) Conjunció lògica o Disjunció lògica no Negació implica, per tant, si... llavors, Condicional o pas deductiu si i només si, Bicondicional o equivalència Els passos elementals que fonamenten qualsevol argument es divideixen en dues categories: Passos lògics bàsics: regles d'inferència derivades de tautologies de la lògica proposicional (vegeu «Lògica proposicional: connectives, taules de veritat i equivalències»). Entre aquestes destaquen: Simplificació: (tautologia ). Addició disjuntiva: (tautologia ). Sil·logisme disjuntiu: (tautologia ). Modus ponens: (tautologia ). Modus tollens: (tautologia ). Sil·logisme hipotètic: .

Principi d'explosió: d'una contradicció se segueix qualsevol proposició, (tautologia ). Passos no lògics (axiomes): propietats matemàtiques que s'accepten com a veritables sense necessitat de prova prèvia. COMPROVA-HO 33 Quina regla lògica permet deduir que una premissa A és falsa si sabem que l'enunciat «A implica B» és cert i B resulta ser fals? Axiomes bàsics del cos dels reals Les deduccions sobre nombres reals es recolzen sobre axiomes d'igualtat, operacions aritmètiques i relacions d'ordre. Els axiomes bàsics d'igualtat estableixen les propietats fonamentals per a qualssevol nombres reals : Reflexiva: . Simètrica: .

¬ A, B A (p q) p A A B p (p q) A B, ¬A B ((p q) ¬p) q A, A B B (p (p q)) q ¬B, A B ¬A (¬q (p q)) ¬p (A B), (B C) (A C) 0 A 0 p a, b, c a = a a = b b = a Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 22 Transitiva: . Substitució funcional: , on és una expressió aritmètica o algebraica ben definida. A partir d'aquests quatre axiomes es demostren directament la suma d'una constant ( ), el producte per una constant ( ), el quadrat ( ) o les sumes i productes membre a membre ( i quan i ). Pel que fa a les operacions del cos dels reals, es compleixen els axiomes estructurals de suma i producte: Associativitat de la suma: . Commutativitat de la suma: . Element neutre de la suma: .

Element oposat: . Associativitat del producte: . Commutativitat del producte: . Element neutre del producte: . Element invers: si , aleshores . Distributivitat del producte respecte de la suma: . Els axiomes bàsics d'ordre per a la relació governen les desigualtats a : Reflexiva: . Antisimètrica: . Transitiva: . Ordre total: per a qualssevol , es compleix . Compatibilitat amb la suma: . Compatibilitat amb el producte: . D'aquestes regles troncals se'n dedueixen propietats auxiliars habituals: el canvi de signe inverteix el sentit ( ), la positivitat dels quadrats ( ), o el producte de desigualtats positives ( ).

COMPROVA-HO 34 Quina condició sobre el nombre c és imprescindible per preservar el sentit d'una desigualtat a b en multiplicar ambdós costats per c?

a = b, b = c a = c a = b E(a) = E(b) E(x) a = b a + c = b + c ac = bc a = 2 b2 a + a = b + b aa = bb a = b a = b a + (b + c) = (a + b) + c a + b = b + a a + 0 = a a + ( a) = 0 a(bc) = (ab)c ab = ba a 1 = a a = 0 a (1/a) = 1 a(b + c) = ab + ac R a a a b, b a a = b a b, b c a c a, b a b b a a b a + c b + c a b, c 0 ac bc a b b a a 2 0 0 a b, 0 c d ac bd Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 23 Demostració directa DEFINICIÓ La demostració directa és l'estratègia deductiva mitjançant la qual s'assumeix la veracitat de la hipòtesi i, aplicant una successió finita de passos lògics, definicions i axiomes, s'obté la certesa de la tesi : EXEMPLE Demostreu que si és un nombre enter senar, aleshores és parell.

Prova pel contrarecíproc La prova pel contrarecíproc aprofita l'equivalència lògica fonamental següent: Per demostrar que una condició implica ( ), se suposa la negació de la tesi ( ) com a punt de partida i es dedueix la negació de la hipòtesi ( ): A B A A A B 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ó objectiu desenvolupant el quadrat de la suma: 2 n + 2 4n 1 = (2k + 1) + 2 4(2k + 1) 1 = (4k + 2 4k + 1) + (8k + 4) 1 Simplificació de termes: Operant els termes s'obté: 3 4k + 2 12k + 4 Factorització: Traient factor comú 2: 4 2(2k + 2 6k + 2) Conclusió: Com que és un enter, el resultat s'expressa de la forma , fet que certifica per definició que és parell. 5 m = 2k + 2 6k + 2 2m n + 2 4n 1 φ ψ ¬ψ ¬φ A B A B ¬B ¬A ¬B ¬A Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 24 EXEMPLE Sigui . Demostreu que si és parell, aleshores és parell.

ERROR FREQÜENT No confongueu mai el contrarecíproc ( ), que és lògicament equivalent a l'enunciat inicial , amb el recíproc ( ) ni amb la inversa ( ). Cap d'aquests dos últims és equivalent a la implicació original. Assumir que provar el recíproc demostra l'enunciat original és una fal·làcia greu que invalida completament l'exercici. Reducció a l'absurd La reducció a l'absurd és un mètode de prova indirecta basat en el fet que cap sistema lògic pot admetre contradiccions.

Es desplega principalment en dues variants estructurals: Variant I (demostració d'una asseveració simple): Per verificar la certesa d'un enunciat , s'assumeix provisionalment la seva falsedat ( ) i es deriva un absurd lògic: Variant II (demostració d'un condicional): Per provar , s'assumeix que la hipòtesi és certa alhora que la tesi és falsa ( ), buscant derivar una contradicció: n Z n2 n Formulació contrarecíproca: L'enunciat té la forma , on és « és parell» i és « és parell». El seu contrarecíproc és: «si és senar, aleshores és senar». 1 A B A n2 B n ¬B ¬A n n2 Punt de partida: Suposem , és a dir, que és senar. Aleshores per a cert .

2 ¬B n n = 2k + 1 k Z Deducció algebraica: Elevant al quadrat obtenim: 3 n = 2 (2k + 1) = 2 4k + 2 4k + 1 = 2(2k + 2 2k) + 1 Arribada a : Com que és un enter, té l'estructura d'un nombre senar, demostrant . Per equivalència lògica, queda demostrat que si és parell, és necessàriament parell. 4 ¬A 2k + 2 2k n2 ¬A n2 n ¬B ¬A A B B A ¬A ¬B A ¬A ¬A 0 (fonamentat en φ ¬φ 0) A B A ¬B A, ¬B 0 (fonamentat en φ ψ (φ ¬ψ) 0) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 25 EXEMPLE Demostreu que és un nombre irracional utilitzant la reducció a l'absurd. COMPROVA-HO 35 Quines premisses inicials s'assumeixen com a certes per fer una reducció a l'absurd d'una implicació A B?

IDEES CLAU Una demostració valida una tesi mitjançant deduccions recolzades en passos lògics (tautologies) i passos no lògics (axiomes del cos ordenat dels reals). La demostració directa assumeix la hipòtesi i encadena deduccions vàlides fins a concloure la tesi . La demostració pel contrarecíproc demostra provant de forma directa l'equivalència lògica . La reducció a l'absurd demostra suposant i deduint una contradicció (0), o bé demostra assumint conjuntament i fins a generar un conflicte lògic. 2 Supòsit d'absurd: Suposem que no és irracional, és a dir, suposem que és racional.

1 2 Formulació en fracció irreductible: Existeixen enters positius i tals que: on la fracció està simplificada, és a dir, i no comparteixen factors comuns (com a mínim un dels dos és senar). 2 a b = 2 b a a b Operacions algebraiques: Elevant al quadrat a ambdós costats s'obté , per tant: 3 2 = a /b 2 2 a = 2 2b2 Paritat de : L'expressió indica que és múltiple de 2 (és a dir, parell). Havent provat que el quadrat d'un nombre només és parell si el nombre és parell, deduïm que és parell. Així, per a algun enter . 4 a a2 a a = 2k k Paritat de : Substituint a l'equació anterior: Això implica que és parell i, en conseqüència, també ha de ser parell.

5 b a = 2k (2k) = 2 2b 2 4k = 2 2b 2 b = 2 2k2 b2 b Contradicció i conclusió: Si tant com són parells, tots dos són divisibles per 2, la qual cosa contradiu la premissa que la fracció era irreductible. Per tant, el supòsit inicial és fals i és irracional. 6 a b a/b 2 A B A B ¬B ¬A A ¬A A B A ¬B Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 26 COMPROVA EL QUE HAS APRÈS 36. Per què demostrar que no és vàlid per demostrar ? 37. En quina tautologia formal es fonamenta la reducció a l'absurd quan volem provar una implicació condicional?

MÈTODES DE DEMOSTRACIÓ MATEMÀTICA 5 Prova per casos, disjuncions, equivalències i unicitat EN ACABAR SABRÀS Aplicar equivalències lògiques per demostrar enunciats amb disjuncions a l'antecedent o a la conclusió Construir particions exhaustives del domini en demostracions mitjançant prova per casos Optimitzar demostracions d'equivalències múltiples utilitzant cadenes cícliques d'implicacions Utilitzar la plantilla canònica per demostrar la unicitat d'un element PENSA-HI ABANS DE LLEGIR 38 Si has de provar que un nombre compleix una propietat o bé una altra, com pots procedir sense provar totes dues alhora?

Tractament d'enunciats amb disjuncions En el raonament matemàtic, la presència de disjuncions (l'operador lògic «o») requereix estratègies deductives específiques segons si la connectiva es troba en la conclusió o en les premisses de partida (vegeu «Lògica proposicional: connectives, taules de veritat i equivalències»). Disjunció a la conclusió Quan l'objectiu és demostrar un enunciat simple de la forma , la tautologia fonamental aplicada és .

En termes pràctics, es parteix de la negació d'un dels termes de la disjunció per deduir necessàriament l'altre: ESTRATÈGIA PER PROVAR UNA DISJUNCIÓ Per provar , assumim com a hipòtesi auxiliar que és cert i deduïm : Aquesta mateixa tècnica s'estén a disjuncions de múltiples termes, . Per tant, per verificar , se suposen falsos tots els termes excepte un i es demostra la veritat de l'últim: B A A B B C (q r) (¬q r) B C ¬B C ¬B C p 1 p 2 p n (¬p 1 ¬p 2 ¬p ) n 1 p n B 1 B 2 Bn ¬B , ¬B , … , ¬B 1 2 n 1 B n Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 27 Quan la disjunció apareix com a conseqüent d'una implicació, , la regla d'equivalència associada és .

La hipòtesi de treball s'amplia incorporant tant l'antecedent original com la negació d'un dels disjunts: Generalitzant per a disjunts al conseqüent, , s'assumeix i la negació de tots els components menys l'últim, . Disjunció a l'antecedent Si la disjunció es troba a l'antecedent d'una implicació, , l'equivalència lògica fonamental és: Això exigeix establir dues derivacions independents: primer que , i en segon lloc que . Si es tracta de múltiples alternatives, , cal comprovar que per a tot índex . COMPROVA-HO 39 Com es transforma la demostració d'una implicació amb disjunció al conseqüent, A (B C D), en una implicació amb antecedent conjuntiu?

Prova per casos exhaustius La prova per casos permet demostrar una conclusió general analitzant per separat diferents situacions particulars que cobreixen totes les possibilitats. Es fonamenta en la tautologia: Per provar que una afirmació és vertadera, es divideix el problema en diversos supòsits o casos : ERROR FREQÜENT L'omissió de casos possibles invalida completament la deducció. Quan es treballa amb nombres enters, per exemple, no n'hi ha prou d'analitzar nombres positius o residus parcials: cal garantir que la unió dels casos cobreixi tot el domini (per exemple, paritat: parell o senar; mòdul 3: residus 0, 1 o 2; mòdul 4: 0, 1, 2 o 3).

A (B C) p (q r) (p ¬q) r A A, ¬B C n A (B 1 B ) n A A, ¬B , … , ¬B 1 n 1 B n (B C) A (q r) p (q p) (r p) B A C A (B 1 B ) n A B i A i {1, … , n} (p 1 p ) n (p ((p 1 p) (p n p))) B A , A , … , A 1 2 n Definir una col·lecció d'estats o condicions tals que s'asseguri l'exhaustivitat total: ha de ser una certesa absoluta. 1 A , … , A 1 n A 1 A n Demostrar la implicació per al primer cas: . 2 A 1 B Demostrar successivament cadascun dels altres casos: fins a . 3 A i B A n B Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 28 EXEMPLE Demostrar que si és un nombre enter, aleshores és parell.

Es divideix la totalitat dels enters en dos casos exhaustius segons la seva paritat: Cas 1 ( és parell): Aleshores existeix un enter tal que . Substituint a l'expressió, . Com que és enter, el resultat és parell. Cas 2 ( és senar): Existeix un enter tal que . Substituint, , que també és múltiple de 2 i per tant parell. Com que tot enter és parell o senar ( ), l'enunciat queda demostrat per exhaustivitat. COMPROVA-HO 40 Quina condició lògica indispensable han de complir els casos escollits A , A , ..., A en una demostració? Demostració d'equivalències lògiques Una equivalència lògica simple de la forma expressa que dos enunciats tenen exactament el mateix valor de veritat.

Es basa en la definició del bicondicional: Per establir la veracitat de cal desglossar la feina en dues implicacions: La implicació directa: . La implicació recíproca: . Equivalència de múltiples condicions: la cadena cíclica Quan s'ha de demostrar que tres o més enunciats són equivalents dos a dos, provar totes les dobles implicacions possibles exigiria demostracions independents (per a 3 enunciats serien 6 implicacions; per a 4, 12).

Per optimitzar aquest procés s'utilitza una cadena cíclica d'implicacions, recolzada en la tautologia: D'aquesta manera, només cal demostrar implicacions simples disposades en cicle: n n + 2 n n k n = 2k n + 2 n = (2k) + 2 2k = 4k + 2 2k = 2(2k + 2 k) 2k + 2 k n k n = 2k + 1 n + 2 n = (2k + 1) + 2 (2k + 1) = 4k + 2 4k + 1 + 2k + 1 = 4k + 2 6k + 2 = 2(2k + 2 3k + 1) A 1 A 2 A B p q (p q) (q p) A B A B B A A , A , … , A 1 2 n n(n 1) (p 1 p ) 2 (p n 1 p ) n (p 1 p ) 2 (p 2 p ) 3 (p n 1 p ) n (p n p ) 1 n Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 29 CICLE Cadena cíclica d'equivalències per a tres proposicions 1. A implica A : Primer pas deductiu del cicle 2.

A implica A : Segon pas deductiu del cicle 3. A implica A : Tanca el cicle garantint l'equivalència mútua Format Estructura de la prova Nombre d'implicacions Equivalència simple ( ) i 2 Cadena cíclica ( ) 3 Cadena cíclica general ( condicions) L'ordre dels enunciats en el cicle es pot alterar lliurement per facilitar les deduccions matemàtiques més directes o senzilles. COMPROVA-HO 41 Quantes implicacions cal demostrar per provar l'equivalència mútua de 4 proposicions mitjançant una cadena cíclica?

Demostració de la unicitat Dins la lògica de primer ordre, assegurar que «si hi ha un element que compleix una propietat , aquest és únic» significa formalment que no en poden existir dos de diferents que la verifiquin alhora (vegeu «Lògica de primer ordre: predicats, quantificadors i formalització»): Mitjançant lleis d'equivalència lògica, aquesta expressió es transforma en la plantilla canònica de la unicitat: 1 A implica A 2 A implica A 3 A implica A n = 2 A B B A n = 3 A 1 A 2 A 3 A 1 n A 1 A 2 A n A 1 n A , A , …

, A 1 2 n P ¬ x y (x = y P (x) P (y)) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 30 PLANTILLA CANÒNICA DE DEMOSTRACIÓ DE LA UNICITAT Per demostrar que com a màxim un element compleix , es prenen dos elements arbitraris x i y, se suposa que tots dos verifiquen la propietat, i s'arriba a la seva identitat: Cal distingir de forma rigorosa dos tipus d'enunciats sobre unicitat: Unicitat condicional: Garanteix que «com a màxim hi ha un element» que satisfà la condició, sense afirmar que en realitat n'hi hagi cap. Per exemple, la unicitat de l'element neutre o de la matriu inversa (en cas d'existir). Existència i unicitat: Afirma que «hi ha un i només un element» ( ).

En aquest cas la demostració es divideix estrictament en dues fases independents: provar primer que efectivament existeix un objecte amb dita propietat, i provar tot seguit que és únic (com passa amb el quocient i el residu de la divisió euclidiana). COMPROVA-HO 42 Quina hipòtesi inicial es pren com a punt de partida a la plantilla estàndard per provar la unicitat d'un element amb propietat P? IDEES CLAU Per provar una disjunció es pot suposar la falsedat d'un terme ( ) i deduir la veritat de l'altre ( ). Una disjunció a l'antecedent equival a realitzar una prova per casos: demostrar i . En una prova per casos, la unió de tots els supòsits analitzats ha de ser estrictament exhaustiva.

L'equivalència entre proposicions es demostra de forma eficient mitjançant una cadena cíclica d' implicacions. Per establir la unicitat d'un element amb propietat , la regla canònica consisteix a suposar i demostrar . COMPROVA EL QUE HAS APRÈS 43. Com s'estructura formalment la prova d'una implicació amb disjunció a l'antecedent de la forma (B B B ) A? 44. Quina diferència conceptual existeix entre provar la unicitat condicional d'un objecte i provar la seva existència i unicitat ( !x)? x, y ((P (x) P (y)) x = y) P P (x), P (y) x = y !x P (x) B C ¬B C (B C) A B A C A n n P P (x) P (y) x = y Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 31 Test Encercla la resposta correcta.

Les solucions són al final. 45. Quin enunciat és formalment equivalent a la implicació p q? 46. Quina combinació d'hipòtesis s'assumeix per provar A B per reducció a l'absurd? 47. Quin axioma d'ordre garanteix que si a b i c 0, aleshores ac bc? 48. En la demostració que 2 és irracional, quina contradicció s'obté en suposar que és racional a/b? 49. Com es pot demostrar una disjunció B C a partir de la seva equivalència lògica condicional? 50. Què exigeix obligatòriament el mètode de prova per casos per ser considerat vàlid? 51. Quin és el nombre mínim d'implicacions per demostrar que A, B i C són equivalents dos a dos? 52.

Quina és la premissa inicial estàndard per demostrar la unicitat d'un element que satisfà P?

¬p ¬q a) q p b) p ¬q c) ¬q ¬p d) A i ¬B a) Només ¬A b) ¬A i ¬B c) ¬A i B d) Transitivitat de l'ordre a) Compatibilitat amb el producte b) Compatibilitat amb la suma c) Antisimetria de l'ordre d) Que el quadrat de 2 és senar a) Que b ha de ser zero b) Que a i b són ambdós parells c) Que a és més gran que b d) Demostrant que B és sempre cert a) Suposant B i deduint C b) Suposant B C c) Suposant ¬B i deduint C d) Que cap cas utilitzi enters negatius a) Que els casos siguin només dos b) Que cada cas tingui la mateixa llargada c) Que els casos siguin completament exhaustius d) 2 implicacions a) 3 implicacions b) 4 implicacions c) 6 implicacions d) Suposar que existeix un únic x a) Suposar ¬P(x) ¬P(y) b) Suposar que x = y c) Suposar P(x) P(y) d) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 32 6 Inducció simple i variants amb múltiples casos base EN ACABAR SABRÀS Escriure amb rigor l'esquema formal d'una prova per inducció distingint hipòtesi i tesi Demostrar identitats algebraiques de sumatoris i productoris mitjançant inducció simple Identificar i verificar problemes que requereixen múltiples casos base abans d'iniciar el pas inductiu PENSA-HI ABANS DE LLEGIR 53 Com podem estar absolutament segurs que una fórmula és certa per a infinits nombres enters si només tenim temps de comprovar-ne un nombre finit?

La inducció matemàtica és una tècnica fonamental per demostrar propietats que depenen d'un índex enter. Funciona com un efecte dominó: si la primera fitxa cau i cada fitxa fa caure la següent, totes les fitxes cauran sense excepció.

ESQUEMA Mètodes d'inducció matemàtica Inducció matemàtica 6 Inducció simple i variants amb múltiples casos base 7 Inducció completa i aplicacions a successions recurrents Inducció simple Pas base i pas inductiu d'un sol terme predecessor Pas base únic Verificació d'un sol inici n Múltiples casos base Verificació manual fins a assolir el llindar n Inducció completa La hipòtesi assumeix tots els valors anteriors Successions recurrents Resolució de termes que depenen de diversos predecessors Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 33 Fonament de la inducció simple Considerem una propietat formulada sobre els nombres enters a partir d'un valor inicial (un predicat sobre els naturals; vegeu «Lògica de primer ordre: predicats, quantificadors i formalització»).

El principi d'inducció simple garanteix que la propietat és certa per a tot si es verifiquen dues condicions essencials: La demostració s'organitza rigorosament en dos passos: PER RECORDAR-HO Una formulació equivalent habitual consisteix a fixar un enter arbitrari, assumir com a hipòtesi d'inducció i provar . Ambdues formes són idèntiques en essència. COMPROVA-HO 54 Què passaria si demostrem el pas inductiu n > n (P(n-1) P(n)) però ometem la comprovació del pas base P(n )? Aplicació a sumatoris i productoris La inducció és l'eina estàndard per verificar fórmules tancades de sumatoris i productoris (vegeu «Sumatoris, productoris i progressions»).

Vegem-ne la mecànica amb la suma dels quadrats dels primers enters positius: P (n) n 0 n n 0 n n P (n) 0 P (n ) 0 n > n (P (n 0 1) P (n)) Pas base: es comprova directament la veritat de avaluant l'expressió en el valor inicial . 1 P (n ) 0 n 0 Pas inductiu: per a un valor genèric , se suposa que la propietat és certa per a l'element anterior (l'anomenada hipòtesi d'inducció) i, utilitzant aquest fet, es demostra la veritat de (la tesi d'inducció). 2 n > n 0 P (n 1) P (n) k n 0 P (k) P (k + 1) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 34 EXEMPLE Demostreu que per a tot es compleix: Pas base ( ): El costat esquerre és . El costat dret és . Com que ambdós coincideixen, és cert.

Pas inductiu: Sigui . Assumim certa la hipòtesi d'inducció : Volem provar la tesi d'inducció . Descomponem el sumatori separant l'últim terme i apliquem la hipòtesi: Traiem factor comú i operem: Com que , obtenim finalment , completant la demostració. Aquesta mateixa tècnica s'aplica a sumes telescòpiques com o a productoris com . ERROR FREQÜENT Un error crític consisteix a afirmar directament la tesi al principi del pas inductiu i operar ambdós costats de la igualtat alhora fins a arribar a . Això suposa allò que volem demostrar (circularitat).

Cal partir sempre d'un membre de la igualtat per a , introduir-hi la hipòtesi per a i deduir el segon membre mitjançant manipulacions algebraiques vàlides. COMPROVA-HO 55 A l'hora d'avaluar un productori _{i=1}^n a_i en el pas inductiu, quina és la descomposició clau per utilitzar la hipòtesi d'inducció?

n 1 i = i=1 n 2 6 n(n + 1)(2n + 1) n = 1 i = i=1 1 2 1 = 2 1 = 6 1(1+1)(2 1+1) = 6 1 2 3 1 P (1) n > 1 P (n 1) i = i=1 n 1 2 = 6 (n 1)n(2(n 1) + 1) 6 (n 1)n(2n 1) P (n) i = i=1 n 2 i + ( i=1 n 1 2 ) n = 2 + 6 (n 1)n(2n 1) n2 n = n = [ 6 (n 1)(2n 1) + 6n ] n = [ 6 2n 3n + 1 + 6n 2 ] 6 n(2n + 3n + 1) 2 2n + 2 3n + 1 = (n + 1)(2n + 1) 6 n(n+1)(2n+1) = i=1 n i(i+1) 1 n+1 n 1 = k=2 n ( k 1 ) n 1 P (n) 0 = 0 n n 1 Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 35 Desigualtats i divisibilitat Quan s'aplica a desigualtats, el pas inductiu sovint requereix acotar l'expressió combinant la hipòtesi amb propietats d'ordre: EXEMPLE Demostreu que per a tot . Pas base ( ): i .

Com que , es compleix. Pas inductiu: Sigui . Suposem . Aleshores: Com que , tenim que . Per tant: Concloem que per a tot . En problemes de divisibilitat, l'objectiu del pas inductiu és expressar l'enunciat per a en funció de l'expressió per a per tal d'aïllar el factor comú del múltiple.

Tipus de propietat Estratègia al pas inductiu Exemple de les fonts Sumatoris / Productoris Separar l'últim terme: Desigualtats Multiplicar/sumar a la hipòtesi i acotar el terme addicional per a Divisibilitat Descompondre potències per fer aparèixer el múltiple hipotètic múltiple de 210 Successions recurrents Substituir la definició recursiva en la fórmula general La inducció també és fonamental per analitzar problemes geomètrics i algorísmics recursius clàssics, com la resolució òptima de la torre de Hanoi o el recobriment d'un tauler d' caselles amb una casella eliminada mitjançant peces en forma d'ela: 3 < n (n + 2)! n 0 n = 0 3 = 0 1 (0 + 2)! = 2! = 2 1 < 2 n > 0 3 < n 1 (n + 1)!

3 = n 3 3 < n 1 3 (n + 1)! n 1 3 n + 2 3 (n + 1)! (n + 2)(n + 1)! = (n + 2)! 3 < n (n + 2)! n 0 n n 1 S = n S + n 1 a n i = i=1 n 2 n(n+1) 4 < n n! n 9 6 2n+1 6 a = n 3a + n 1 6 a = n 3 n 3 2 × n 2n Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 36 Esquema del problema de la torre de Hanoi amb n discos. Diagrama de la peça en ela per recobrir taulers defectuosos. COMPROVA-HO 56 Per què a 2·3 + 5^{2n-1} és útil expressar 5^{2n-1} com 25·5^{2(n-1)-1} durant el pas inductiu? Variants amb múltiples casos base En determinades ocasions, la implicació del pas inductiu només és vàlida quan l'índex supera un cert llindar .

En aquests casos cal realitzar una comprovació explícita de diversos casos base inicials: Un cop verificats individualment tots aquests casos inicials, s'estableix el pas inductiu per a tot assumint . P (n 1) P (n) n > 1 n 0 P (n ), P (n + 0 0 1), … , P (n ) 1 n > n 1 P (n 1) Fonaments Matemàtics: Lògica, Inducció i Teoria de Conjunts 37 EXEMPLE Demostreu que per a tot enter . Si intentem fer el pas inductiu ordinari , voldríem deduir que això és menor o igual que . Tanmateix, la condició només és certa a partir de . Per tant, és necessari comprovar per separat com a casos base els valors de entre 0 i 4: : (Cert) : (Cert) : (Cert) : (Cert) : (Cert) Pas inductiu: Sigui (és a dir, ).

Suposant certa la hipòtesi : ja que . La propietat queda així provada per a tot . IDEES CLAU El principi d'inducció simple requereix verificar el pas base i la implicació inductiva . La hipòtesi d'inducció consisteix a assumir la propietat per a l'índex anterior , mai a donar per suposada la tesi . En identitats de sumatoris i productoris, la clau rau a separar el terme final per aplicar la hipòtesi al bloc restant. Quan el pas inductiu requereix una condició numèrica que no es compleix als primers valors (com ara ), cal verificar manualment múltiples casos base inicials. COMPROVA EL QUE HAS APRÈS 57. Per què cal verificar manualment diversos casos base a la desigualtat per a tot ? 58.

En què es diferencia formalment plantejar el pas inductiu amb o bé amb ? 5 n 27 n! n 0 5 = n 5 5 n 1 5 27(n 1)! 27 n! = 27 n(n 1)! 5 n n 5 n n = 0 5 = 0 1 27 0! = 27 n = 1 5 = 1 5 27 1! = 27 n = 2 5 = 2 25 27 2! = 54 n = 3 5 = 3 125 27 3! = 162 n = 4 5 = 4 625 27 4! = 648 n 5 n > 4 5 n 1 27(n 1)! 5 = n 5 5 n 1 5 27(n 1)! n 27(n 1)! = 27 n! 5 n n 0 P (n ) 0 n > n (P (n 0 1) P (n)) P (n 1) P (n) n 5 5 n…