\documentclass{article}

\input{../temes/latexDefs.tex}

\begin{document}

\title{Propostes de temes sobre el llengutatge matemàtic (pel curs 2021/22)}
\maketitle{}

 \begin{flushright}
    (\href{http:pascal.upf.edu/math21/mates1-21/temes-llenguatge.html}{Enllaç a aquest document en html})\\
    (\href{./temes-llenguatge.pdf}{Enllaç a la versió pdf d'aquest document})\\
    (\href{./temes-llenguatge.tex}{Enllaç a la font LaTeX})\\
    (\href{./figures/}{Enllaç als fitxers de les figures})\\
    (\href{../temes/latexDefs.tex}{Enllaç al fitxer de definicions latex})
  \end{flushright}


\tableofcontents{}

\section{Introducció}

Aquest document inclou una proposta completa del que podria ser una nova primera setmana dedicada a una petita introducció al llenguatge
formal de les matemàtiques i una possible segona setmana per a mates II o III.

La secció T0 correspondria a una primera setmana de mates I, la secció T0B a la possible segona setmana. Inclouen propostes de
guies estructurades en slides, qüestionaris breus pre-classe per després de la primera lectura de la guia i llistes d'exercicis.


\section{T0 El llenguatge de les Matemàtiques I}

Es tracta de fer una lleu introducció al llenguatge formal, limitat a l'àlgebra de conjunts i la de Boole elemental. Posem davant
els conjunts perquè probablement els són més familiars i els poden ajudar a entrar en el més abstracta de la lògica formal, que
tractem només somerament, sense entrar en taules de veritat, demostracions, etc. que poden ser objecte de tractament a mates II o III.

Referències:
\begin{itemize}
\item Pemb-Rau Cap. 3.1
\item S\&H 1.7 Teoría de conjuntos
\item S\&H 1.5 Algunos aspectos de lógica
\end{itemize}

\subsubsection{Guia 01 Llenguatge dels conjunts}

\newcommand{\slide}[1]{\medskip\hrule \smallskip
\centerline{#1}\smallskip
\smallskip\hrule\medskip
}


\slide{Definicions}


Un conjunt és una col·lecció d'objectes considerada com una sola entitat.

Dels objectes en diem que són els \emph{membres} o \emph{elements} del conjunt.

Exemples:
\begin{itemize}
\item Els estudiants matriculats als graus de la UPF el curs 2021/22.
\item Els treballadors d'una empresa
\item Els nombres naturals parells més petits que 10.
\end{itemize}

Els conjunts es poden descriure per enumeració o a través d'una propietat que els seus elements o membres han de satisfer.
El darrer exemple el podem descriure:
$$E = \{2, 4, 6, 8\} = \{n\in {\cal N}: n<10\}$$

 El signe $\in$ es llegeix ``pertany a'' i l'usem per afirmar que un element forma part d'un conjunt. Si no en forma part,
 escriurem $a\notin A$.

 \slide{Subconjunts}

 Diem que un conjunt $A$ és subconjunt d'un conjunt $B$ si tots els elements de $A$ també ho són de $B$. Llavors escribim
 $A\subset B$.

 Per exemple, si $A$ és el conjunt dels treballadors d'una empresa i $B$ és el conjunt dels administratius de l'empresa, $B\subset
 A$.

Sempre es compleix que $A\subset A$. De fet, dos conjunts $A$ i $B$  són iguals, $A=B$ si i només si $A\subset B$ i $B\subset A$.

El conjunt especial $\emptyset$ és el que no té cap element, per exemple. el conjunt de les vaques que poden volar.

\slide{Operacions amb conjunts}

\begin{tabular}[c]{|l|l|l|}\hline
  Unió de $A$ i $B$& $A\cup B$& Els elements que pertanyen almenys a un dels dos\\\hline
  Intersecció & $A\cap B$& Els elements que pertanyen a tots dos\\\hline
  Diferència & $A\backslash B$ & Elements de $A$ que no ho són de $B$\\\hline
\end{tabular}

Els diagrames de Venn són útils per visualitzar això.\\
\grafLink{Fig-SH-1-6.pdf} 

Exemple: Si $A=\{a,b,c,d\}$ i $B=\{c,d,e,f,g\}$, llavors
\begin{itemize}
\item $A\cup B = \{a,b,c,d,e,f,g\}$
\item $A\cap B = \{c,d\}$
\item $A\backslash B = \{a,b\}$ 
\item $B\backslash A = \{e,f,g\}$ 
\end{itemize}

Es compleixen les següents propietats, que podem comprovar amb els corresponents diagrames de Venn:
\begin{description}
\item[O1] $A\cup A = A$, $A\cap A = A$
\item[O2] $A\cup \emptyset = A$, $A\cap \emptyset = \emptyset$
\item[O3] $A\cup B = B\cup A$, $A\cap B = B\cap A$
\item[O2] $(A\cup (B\cup C) = (A\cup B) \cup C$. Ho escriurem $A \cup B\cup C$
\item[O3] $(A\cap (B\cap C) = (A\cap B) \cap C$. Ho escriurem $A \cap B\cap C$
\item[O4] $A\cup(B\cap C) = (A\cup B) \cap (A \cup C)$
\item[O5] $A\cap(B\cup C) = (A\cap B) \cup (A \cap C)$
\end{description}



 \slide{Complementari}

En el cas que tractem amb conjunts inclosos en un cert \emph{univers}, podem parlar del conjunt complementari, el que està format
pels elements que no hi pertanyen. Indiquem amb $A^\prime$ o $A^c$ el complementari de $A$.

Es compleixen les següents propietats, que podem comprovar amb els corresponents diagrames de Venn:
\begin{description}
\item[C1] $A^{\prime\prime} = A$
\item[C2] $(A\cup B)' = A'\cap B'$
\item[C3] $(A\cap B)' = A'\cup B'$
\end{description}


Podeu practicar amb diagrames de Venn de conjunts i els seus complementaris a \url{https://www.geogebra.org/m/KSuUb2TR}.

Per exemple, així es veu $(A\cup B)'$: \includegraphics[width=0.2\linewidth]{figures/Venn1.png}


\smallskip\hrule


 
 \subsubsection{Quizz pre-classe 01}
 \begin{itemize}
 \item Veritat o fals?
   \begin{itemize}
   \item $a\in A$ vol dir que $a$ és un subconjunt de $A$
   \item $a\notin\{a, b, c, d\}$
   \item $A\cup B$ és la intersecció de $A$ i $B$
   \end{itemize}
 \item Si $A$ és el conjunt d'europeus, $B$ el de catalans i $C$ el de barcelonins, quina és correcta?
   \begin{itemize}
   \item $A\subset C$
   \item $C\subset A$
   \item $B\subset C$
   \end{itemize}
 \end{itemize}
 
 
 \subsubsection{Clickers 01}

 \begin{itemize}
 \item El conjunt representat a la figura
   \grafLink{Fig-SH-1-7.pdf}
   correspon a
   \begin{itemize}
   \item $A\cup (B\cap C)$
   \item[*] $A\backslash (B\cup C)$
   \item $A\cap (B\cup C)$
   \item $(B\cup C)\backslash A$
   \end{itemize}
 \item Siguin $A$ el conjunt d'empleats d'una empresa, $B$ el conjunt de les dones empleades de l'empresa, $C$ el conjunt
   de directius de l'empresa, $D$  el conjunt d'empleats de la empresa que cobren més de mil euros al mes.\\
   Digues si són veritables o no les següents:
   \begin{itemize}
   \item $A\subset B$
   \item $B\subset D$
   \item $C\subset D$
   \item $A\backslash B$ és el conjunt d'homes empleats a l'empresa
   \item $B\cap C$ és el conjunt de directives de l'empresa
   \end{itemize}
\item Recorda que $(a,b)$ indica l'interval dels nombres reals que estan entre $a$ i $b$, i que si posem $(a,b]$ indiquem que $b$
  també està inclós en el conjunt.
  Digues si són veritables o no les següents:
   \begin{itemize}
   \item $(2,3) \subset (2, 6)$
   \item  $(2,5) \cap [3, 6) = (3, 5)$
   \item $(2,5) \cup (5, 6) = (2, 6)$
   \end{itemize}
 \end{itemize}

 
\subsubsection{Guia 02 Lògica de les proposicions}

\slide{Proposicions}

Una proposició o enunciat és una afirmació que pot ser veritable o falsa. Per exemple ``$2+2=5$'', o ``$x=2$ és solució de
$x^2-4$''.

No considerem que ``El color vermell és bonic'' sigui una proposició.

Sovint expressem una proposició amb una lletra, per exemple $p=$ ``5  és un nombre primer''.

 
\slide{Operacions amb proposicions}

\begin{tabular}[c]{|l|l|l|}\hline
    & &És veritat quan \\\hline
  Negació de $p$ & $\neg p$ & $p$ és falsa \\
  Disjunció de $p$ i $q$& $p$ ó $q$, $p\vee q$ & \textbf{Almenys  una}  de les dues és veritat\\
  Conjunció de $p$ i $q$ & $p$ i $q$, $p\wedge q$& \textbf{Totes dues} són veritat\\
  Implicació & $p\Rightarrow q$ & Sempre que $p$ és veritat, $q$ també ho és\\
  Equivalència & $p\Leftrightarrow q$ & Sempre que una de les dues és veritat, l'altra també\\\hline
\end{tabular}

Exemples:
\begin{itemize}
\item La negació de $x<2$ és $x\geq 2$.
\item L'acció $A$ ha guanyat valor \textbf{ó} L'acció $B$ ha perdut valor (a la borsa avui)
\item 3 és primer \textbf{i} 25 és divisible per 5
\item $x^2=2 \Rightarrow x=\sqrt{2}$
\item $a<b \Leftrightarrow b>a$
\end{itemize}

Quan tenim $p\Rightarrow q$, diem que:
\begin{itemize}
\item $p$ és l'antecedent i $q$ és el conseqüent.
\item $p$ és condició suficient per $q$
\item $q$ és condició necessària per $p$
\end{itemize}

Exemples:
\begin{itemize}
\item Ser català és condició suficient per ser europeu.
\item Ser espanyol és condició necessària per ser català.
\item $x=2$ és condició suficient per $x^2=4$.
\item $x>2$ és condició necessària per $x>5$.
\end{itemize}

 \slide{Regles lògiques}

 Per a $p, q$ proposicions,
 \begin{description}
 \item[L1] $\neg(\neg p)$ és equivalent a $p$
 \item[L2] $\neg(p\wedge q)$ és equivalent a $\neg p \vee \neg q$
 \item[L3] $\neg (p\vee q)$ és equivalent a $\neg p \wedge \neg q$ 
 \item[L4] $p\Rightarrow q$ és equivalent a $\neg q\Rightarrow \neg p$
 \end{description}

 Exemples:
 \begin{itemize}
 \item El contrari de ``Pere no és estudiant'' és ``Pere és estudiant''.
 \item La negació de ``Joan anirà a votar'' \textbf{ó} ``Irene anirà a votar'' és ``Joan no anirà a votar'' \textbf{i} ``Irene no anirà a votar''.
 \item El contrari de ``Emma i Laia són esportistes'' és ``Emma no és esportista'' \textbf{ó} ``Laia no és esportista''.
 \item La contrària de $2<x<5$ és $x\leq 2$ o $x\geq 5$
 \item Si $x>3$, llavors $x>1$, és equivalent a ``Si $x\leq 1$, llavors $x\leq 3$''.
 \item ``Si plou, porto paraigües'', és equivalent a ``Si no porto paraigües, no plou''.
 \item ``En aquesta empresa, si ets dona no pertanys a la direcció'' és equivalent a ``Si pertany a la direcció, no és dona''.
 \end{itemize}

 Observem el paral·lelisme entre:
 \begin{tabular}{ll}
Negació i complementari d'un conjunt:& $x\in A'$ equival a $\neg(x\in A)$.\\
Disjunció i unió de conjunts:& $x\in A\cup B$ equival a $x\in A \vee x\in B$.\\
Conjunció i intersecció:& $x\in A\cap B$ equival a $x\in A \wedge x\in B$.\\
Implicació i inclusió:& $A\subset B$ equival a $x\in A\Rightarrow x\in B$.
 \end{tabular}

%$\smallskip\hrule

\subsubsection{Quizz pre-classe 02}

\begin{itemize}
\item Cert o fals? Una proposició ha de ser sempre veritable.
\item Cert o fals? "La lluna és una estrella" no pot ser una proposició.
\item $3=5$ no és una proposició
\end{itemize}


 
 \subsubsection{Clickers 02}

 \begin{enumerate}
 \item Quines de les següents frases són proposicions:
   \begin{itemize}
   \item $4^{500}>5^{400}$
   \item És difícil trobar les solucions de $2x^3-3x^2+5x-8=0$
   \item $7238 + 8327$
   \item $ 2021 = 43 * 47 + 1$
   \item Hi ha un nombre primer més gran que $100^{100}$
   \end{itemize}
 \item Marca les correctes:
   \begin{enumerate}
   \item  Ser un hipopòtam és CN per ser un animal
   \item Ser bomber és CS per ser persona
   \item Ser un cotxe és CN per ser una màquina
   \item Tenir 18 anys és CN per traure's el carnet de conduir.
   \end{enumerate}
\item La negació de ``Plou i fa sol'' és
   \begin{enumerate}
   \item No plou i no fa sol
   \item Ni plou ni fa sol
    \item No plou o no fa sol
    \item Plou però no fa sol
    \item Quan plou de vegades fa sol
   \end{enumerate}
 \item Marca les correctes. Si diem que $p$ implica $q$
   \begin{enumerate}
   \item $p$ és condició necessària per $q$
   \item $p$ és condició suficient per $q$
   \item  $q$ és condició necessària per $p$
   \item  $q$ és condició suficient per $p$
   \end{enumerate}
\item Substitueix l'espai en blanc per ``condició necessària'', ``condició suficient'', o ``condició necessària i suficient''.
   \begin{enumerate}
   \item $2 x + 5 > 13$ és \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } per $ x\geq 0$
   \item $x \geq 50$ és \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } per $x\geq 0$
   \item $x \geq 0$  és \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } per $x\geq 4$
   \end{enumerate}
\item Substitueix l'espai en blanc per ``si'', ``només si'', o ``si i només si''.
   \begin{enumerate}
   \item $x=\sqrt{4}$ \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $ x = 2$
   \item $x^2>0$ \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $x> 0$
   \item $x^2=4$ \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $x=2$
   \item $x^2=4$ \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $x=2\vee x=-2$ 
   \item $x^2<9$  \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $x<3$
   \item $x(x^2+1)=0$  \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $x=0$
   \item $x(x+3)$  \fbox{\ \ \ \ \ \ \ \ \ \ \ \ } $x>-3$
   \end{enumerate}
  \item Per cada proposició de les següents, diues quins valors de $a$ fan que sigui veritat.
   \begin{enumerate}
   \item $3<4$ i $a=12$
   \item $4<3$ i $a=12$
   \item $4<3$ ó $a=12$
   \item Si $a=4\times 3$, llavors $3<4$
   \item Si $a=4\times 3$, llavors $3>4$
   \item Si $3>4$. llavors $a=4\times 3$
   \end{enumerate}
 
 \end{enumerate}

% \includegraphics[width=0.5\linewidth]{figures/Exc-IB-AnAp-5-1.png}

 Més clickers sobre logica proposicional bàsica: \url{http://myslu.stlawu.edu/~plock/Math280Clicker/Ma280-1.ppt}

 A la mateixa pàgina n'hi ha d'altres sobre quantificadors, \url{http://myslu.stlawu.edu/~plock/Math280Clicker/Ma280-3.ppt},
 demostracions, etc que podrien ser utils per una setmana de mates II.
 

\subsubsection{Exercicis Llista}

\begin{enumerate}
\item Tal com ho hem definit, quan diem $P$ o $Q$, entenem un ``o'' inclusiva, és a dir, si diem que $P\vee Q$, estem dient que una de les dues o totes dues són certes.\\
  De vegades ens interessa expressar una disjunció excloent, és a dir que només sigui certa quan una de les dues i no totes dues siguin certes.
  \begin{enumerate}
  \item Fent servir només les connectives $\vee, \wedge, \neg$, expressa la proposició: Exactament una de les dues, $P$ o $Q$ són veritat.
  \item Com expresses la contrària de l'anterior amb paraules?
  \item Com expresses aquesta negació formalment?
\end{enumerate}

\item Se'n poden traure del S\&H 1.7: \grafLink{Prob-SH-1-7.pdf}
\end{enumerate}

 
 \subsubsection{Exercicis extra}

\grafLink{Exc-PR-3-1.png}

%\end{document}

\section{T0B El llenguatge de les matemàtiques II}

Es tracta d'ampliar una mica el que s'ha fet a Matemàtiques I sobre el llenguatge. Allà s'ha tractat el llenguatge dels conjunts i
els elements bàsics de la lògica booleana.

Aquí introduirem els quantificadors universal i existencial amb un repàs de les regles bàsiques dels connectors i en una segona guia alguns elements dels
mètodes de demostració.

Referències:
\begin{itemize}
\item Pemb-Rau, Cap. 31.1
\item  IB-AnAppr, capítol 5.
\item S\&H cap. 1.6.
\end{itemize}

\subsubsection{Guia 0B1: Tots o algun, els quantificadors lògics}

\slide{Slide 0: Proposicions amb quantificador}


Recordem:
\begin{tabular}[c]{|l|l|l|}\hline
    & &És veritat quan \\\hline
  Negació de $p$ & $\neg p$ & $p$ és falsa \\
  Disjunció de $p$ i $q$& $p$ ó $q$, $p\vee q$ & \textbf{Almenys  una}  de les dues és veritat\\
  Conjunció de $p$ i $q$ & $p$ i $q$, $p\wedge q$& \textbf{Totes dues} són veritat\\
  Implicació & $p\Rightarrow q$ & Sempre que $p$ és veritat, $q$ també ho és\\
  Equivalència & $p\Leftrightarrow q$ & Sempre que una de les dues és veritat, l'altra també\\\hline
\end{tabular}

I recordem encara:
\begin{tabular}[c]{|l|l|}\hline
 L1 & $\neg(\neg p)$ és equivalent a $p$\\
 L2 & $\neg(p\wedge q)$ és equivalent a $\neg p \vee \neg q$\\
 L3 & $\neg (p\vee q)$ és equivalent a $\neg p \wedge \neg q$\\
 L4 & $p\Rightarrow q$ és equivalent a $\neg q\Rightarrow \neg p$\\\hline
 \end{tabular}

\emph{Nota:\/} En llenguatge no formal hi ha expressions que poden confondre. Per exemple,   en català, les expressions ``Res no és
gratuït, tot té un preu''  i  ``Res és gratuït, tot té un preu'' es consideren vàlides i equivalents.
 
 \slide{Slide 1: Proposicions amb quantificador}

Si tenim un conjunt $X$ i una afirmació $p(x)$ sobre els seus elements $x\in X$ que pot ser veritat o falsa, podem dir

\begin{tabular}[c]{|l|l|}\hline
  Escrivim & Llegim \\\hline
  $\forall x\in X, p(x)$ & \textbf{Per a tots els $x$ de $X$}, $p(x)$ es compleix\\
  $\exists x\in X: p(x)$ & \textbf{Existeix algún} (almenys un) $x$ de $X$ tal que $p(x)$ es compleix\\\hline
\end{tabular}

Exemples, per $\cal N$, el conjunt dels nombres naturals, les següents són veritat:
\begin{itemize}
\item $\forall n\in {\cal N}, (n+1)^2 = n^2+2n+1$
\item $\exists n\in {\cal N}: n^2 = 16$
\item $\exists n\in {\cal N}: n>16$
\item Existeix algún múltiple de 5 que és parell.
\end{itemize}

però les següents són falses:

\begin{itemize}
\item $\forall n\in {\cal N}, (n+1)^2 = n^2+1$
\item $\exists n\in {\cal N}: n^2 = 20$
\item $\exists n\in {\cal N}: n>n-1$
\item Tots els múltiples de 5 són parells.
\item Existeix algún nombre natural $n$ tal que $n-1 = 2n$.
\end{itemize}

 \slide{Slide 2: Negació amb quantificadors}

La negació canvia un quantificador en l'altre.

\begin{tabular}[c]{|lccl|}\hline
  El contrari de & Tot $x$ compleix $p(x)$ & és  & Algun $x$ no compleix $p(x)$\\
  El contrari de & Algun $x$ compleix $p(x)$ & és  & Tot $x$ no compleix $p(x)$\\\hline
\end{tabular}

En versió formal: 
\begin{tabular}[c]{|lcl|}\hline
  $\neg \left(\forall x\in X, p(x) \right)$ & equival a  & $\exists x\in X, \neg p(x)$\\
  $\neg \left(\exists x\in X, p(x) \right)$ & equival a  & $\forall x\in X, \neg p(x)$ \\\hline
\end{tabular}

Exemples:
\begin{itemize}
\item El contrari de ``Ha plogut tots els dies'' és ``Algun dia no ha plogut''.
\item El contrari de ``Tots els treballadors cobraran més'' és ``Algun treballador no cobrarà més''.
\end{itemize}

Exemples en notació formal:
\begin{itemize}
\item El contrari de \fbox{$\forall n\in {\cal N}, n^2>n$} és \fbox{$\exists n\in {\cal N}: n^2\leq n$ }
\item El contrari de \fbox{$\exists n\in {\cal N}: n^2 < n+25$} és  \fbox{$\forall n\in {\cal N}, n^2\leq n+25$}
   
\end{itemize}

Exemples (al tanto amb el llenguatge poc formal, pot induir a confusions, sovint va bé formalitzar la proposició)
\begin{itemize}
\item El contrari de ``tots els homes són honestos'' és ``hi ha algun home que no és honest''.\\
  Això ho formalitzem posant $H$ el conjunt de tots els homes, $p(h)=$ L'home $h$ és honest, i tenim \fbox{$\forall h\in H, p(h)$}
  i el contrari \fbox{$\exists h\in H: \neg p(h)$}.
\item El contrari de ``hi ha alguna vaca que pot volar'' és ``totes les vaques no poden volar'' o ``cap vaca pot volar''.
\item El contrari de ``tots els europeus són espanyols'' és ``algun europeu no és espanyol''.
\item Si neguem que ``Algú ha perdut el mòbil'', direm que ``Ningú ha perdut el mòbil'', o bé ``Tots no han perdut el mòbil''.
\end{itemize}

\slide{Slide 3: Negació amb quantificadors -- 2}
\centerline{\emph{En cap cap cap el que cap en aquest cap}}

Observa que si en una proposició es combina algun quantificador amb altres connectives, cal anar al tanto! I si a més a més s'hi
barreja el llenguatge no formal, més perill!

\begin{itemize}
\item  El contrari de ``Per tot $x$ es compleix $p(x) \wedge q(x)$'' serà ``Per algun $x$ es compleix $\neg p(x)$ o es compleix
  $\neg q(x)$''.
\item El contrari de ``Per tot $x$ es compleix $p(x) \vee q(x)$'' serà ``Per algun $x$ es compleix $\neg p(x)$ i es compleix
  $\neg q(x)$''.
\end{itemize}

Exemples
\begin{itemize}
\item El contrari de ``tots els treballadors faran festa dissabte i diumenge'' és ``algun treballador treballarà dissabte o
  diumenge''.
\item El contrari de ``Algun pais africà té la vacuna de Pfizer o la de Moderna'' és ``Tots els països africans no tenen la
  Pfizer i no tenen la Moderna''.
\end{itemize}

Formalitzem aquest darrer exemple: posem $A$ el conjunt de països africans. $p(a)=$ el país $a$ te la Pfizer. $q(a)=$ el país $a$
té la Moderna''. Llavors traduïm:
\begin{itemize}
\item ``Algun pais africà té la vacuna de Pfizer o la de Moderna'' és $\exists a\in A: p(a) \vee q(a)$''
\item El contrari és $\forall a\in A, \neg p(a) \wedge \neg q(a)$, és a dir ``Tots els països africans no tenen la
  Pfizer i no tenen la Moderna''.
\end{itemize}

\slide{Slide 4: Negació amb quantificadors i implicacions}

Si recordem que \fbox{$\neg (p\Rightarrow q)$ és equivalent a $ p \wedge \neg q$}, podem dir ara:

\begin{tabular}[c]{|lccl|}\hline
  El contrari de & Per tot $x$ es compleix $p(x)\Rightarrow q(x)$ & és  & Per algun $x$ es té $p(x)$ i $\neg q(x)$\\\hline
\end{tabular}




 \subsubsection{Quizz pre-classe 0B1}

 \begin{enumerate}
 \item Repassem les connectives lògiques que vem veure anteriorment.
   \begin{enumerate}
   \item Digues si són veritat o no les següents afirmacions.
     \begin{enumerate}
     \item Per expressar $p$ ó $q$ fem servir $p\vee q$.
     \item Si diem que $p$ ó $q$ és veritat, no pot ser que $p$ i $q$ siguin totes dues veritat.
     \item Si diem que $p$ i $q$ és fals, totes dues $p$ i $q$ han de ser falses.
     \item Si diem que $p\Rightarrow q$ és veritat, llavors $q$ ha de ser veritat.
     \end{enumerate}
   \end{enumerate}
 \item Quina diries que és la contrària de ``Totes les meves amigues tenen moto o cotxe''?
   \begin{enumerate}
   \item Totes les meves amigues no tenen moto.
   \item Totes les meves amigues no tenen moto ni cotxe.
   \item Alguna amiga meva no té cotxe.
   \item Alguna amiga meva no té moto ni cotxe.
   \end{enumerate}
 \item Si és cert que ``Si plou llavors el pati està mullat'', i sabem que el pati està sec,
   \begin{itemize}
   \item[--] Podem assegurar que plou
   \item[*] Podem assegura que no plou
   \item[--] Podem assegurar que fa sol
   \item[--] No podem assegurar cap de les altres
   \end{itemize}

 \end{enumerate}

 
 
\subsubsection{Guia 0B2 La demostració matemàtica}

En aquesta guia introduïm les idees bàsiques dels mètodes de demostració matemàtica.
Tractarem
\begin{itemize}
\item Demostració directa
\item Demostració indirecta
  \begin{itemize}
  \item per contraposició
  \item per contradicció, o reducció a l'absurd.
  \end{itemize}
\end{itemize}

La demostració per inducció quedaria per a treball opcional per a matrícula.

\slide{Slide 0: La demostració matemàtica} %%%%%%%%%%%%%%%%%%%%%%%%%%


És un mètode que consisteix en demostrar que una \textbf{conclusió} és veritat a partir de una o diverses \textbf{hipòtesis} veritables.

Exemple: Demostrar que la suma de dos nombres parells és un nombre parell.

La \textbf{hipòtesi} és que dos nombres $n,m$ són parells.

La \textbf{conclusió} és que la suma $n+m$ és parell.

\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{
  Suposant que $n,m$ són nombres naturals parells, hem de demostrar que $n+m$ és un nombre parell.\\
  Segons la definició de nombre parell, podem escriure $n=2k_1, m=2k_2$.\\
  Llavors, $n+m=2k_1+2k_2=2(k_1+k_2)$, i per tant, $n+m$ és parell.\\
  \rightline{QED}
}}



\slide{Slide 1: Demostració directa} %%%%%%%%%%%%%%%%%%%%%%%%%%%%


La que acabem de veure és una \textbf{demostració directa}: a partir de la hipòtesi fem una cadena de raonaments lògics correctes per
arribar a la conclusió.

Un altre exemple: Demostrar que el quadrat d'un nombre parell és parell.

\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{
    Suposant que $n$ és un nombre natural parell (hipòtesi),\\
    hem de demostrar que $n^2$ és un nombre parell (conclusió).\\
  Segons la definició de nombre parell, podem escriure $n=2k$.\\
  Llavors, $n^2=4k^2=2(2k^2)$, i per tant, $n^2$ és parell.\\
  \rightline{QED}
}}

Proveu ara de demostrar que ``El producte de dos nombres senars és senar''.

\slide{Slide 2: Demostració indirecta per contraposició}%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Recordem que $P \Rightarrow Q$ és equivalent a $\neg Q \Rightarrow \neg P$, o dit d'altra manera: Si $P$ llavors $Q$ és equivalent
a ``Si no$Q$, llavors no$P$''.

La demostració per contraposició de ``Si P, llavors Q'' consisteix en demostrar que ``Si noQ, llavors noP''.

Exemple: Per demostrar que ``Si $n^2$ és parell, $n$ és parell'', ho fem per contraposició, demostrarem que ``Si $n$ no és parell,
$n^2$ no és parell.''

\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{
    Si $n$ és un nombre natural no parell, llavors és senar.\\
  Si $n$ és senar, com que el producte de dos senars és senar, $n\cdot n=n^2$ és senar.
  \rightline{QED}
}}

\slide{Slide 3: Demostració indirecta per contradicció} %%%%%%%%%%%%%%


La demostració \textbf{per contradicció} o per \textbf{reducció a l'absurd} consisteix en suposar falsa la
conclusió i arribar a una contradicció, a una afirmació impossible de ser certa.

Exemple

Demostrar que $\sqrt{2}$ no és racional, és a dir que no es pot expressar com $\sqrt{2}=a/b$ amb $a,b$ enters.

\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{
    Suposem contràriament que sí es pot tenir $\sqrt{2}=a/b$ amb $a,b$ enters.\\
    Si ambdós $a$ i $b$ són parells, els dividim per dos fins que no siguin tots dos parells.\\
    Llavors tenim $2=a^2/b^2$ o bé $a^2=2 b^2$ i veiem que $a^2$ és parell i per tant $a$ és parell.\\
    Podem escriure, $a=2k$ per algún enter $k$, $a^2=4k^2=2b^2$, i tenim $b^2=2k^2$.\\
    Resulta que $b^2$ és parell i per tant $b$ és parell també: contradicció perqué haviem vist que $b$ era senar!\\
    \rightline{QED}
}}

Un exemple no matemàtic: El Sr. X no és culpable de l'assessinat de Y.\\
\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{%
    Demostració per reducció a l'absurd:\\
    Si contràriament fos culpable, necessàriament havia de ser en el lloc dels fets el dia D.\\
Però sabem que X era a la Patagònia el dia D, i no pot ser
que fos a dos llocs tant distants el mateix dia: contradicció! \\
    \rightline{QED}
}}

Exemple: Demostrar (per contradicció) que per $n\in {\cal Z}$, si $3n+2$ és senar, llavors $n$ és senar.\\
\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{%
    Si contràriament fos $3n+2$ senar i $n$ parell, \\
    podriem escriure $n=2k$ per algún $k\in {\cal Z}$.\\
    I tindriem $3n+2=3(2k)+2=6k+2=2(3k+1)$ amb la qual cosa $3n+2$ seria parell,\\
    contradicció! Per tant no pot ser $n$ parell, ha de ser $n$ senar.
    \rightline{QED}
  }}

\textbf{Observa que}: Sovint una demostració per contradicció es pot reformular com una demostració per contraposició.

\slide{Slide 4: Més exemples}

$\bullet$ Demostrar que, \emph{Donats dos nombres naturals $m,n$, tots dos són senars si i només si el producte $m n $ és senar}.

Cal fer dues demostracions:

1.- $m$ i $n$ són senars $\Rightarrow$ $ m n$ és senar.\\
\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{%
    Demostració directa: Posem $m=2k_1+1, n=2k_2+1$.\\
    Tindrem $m n = (2k_1+1)(2k_2+1) = 4 k_1 k_2 + 2k_1+2k_2+1= 2(2 k_1 k_2 + k_1+k_2)+1$ que és senar.\\
    \rightline{QED}
  }}

2.-  $m$ i $n$ són senars $\Leftarrow$ $ m n$ és senar.\\
\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{%
    Demostració per contraposició: Si algún $m$ o $n$ no és senar, demostrarem que $m n$ no és senar.\\
    Posem que $m$ és parell (si fos $n$ qui és parell, els intrecanviem).\\
    Llavors tenim $m=2k$, i llavors $m n= 2 k n$ és parell. Per tant la contrapositiva és veritat.\\
    \rightline{QED}
  }}

$\bullet$ Demostrar que \emph{Donats dos nombres naturals $m,n$, si $m+n$ és senar, llavors exactament un dels dos $m$ o $n$ és senar.}

Tenim dues proposicions:\\
$P:$ La suma $m+n$ és senar.,\\
$Q:$ Exactament un dels dos, $m$ o $n$ és senar,\\
i volem veure que $P\Rightarrow Q$.

És més senzill demostrar, per contraposició, que $\neg Q\Rightarrow \neg P$, és a dir que\\
$\neg Q:$ tots dos són senars o  tots dos són parells,\\
$\neg P:$ la suma no és senar.

\textbf{Demostració:} \fbox{\parbox[t]{0.8\linewidth}{%
    Hi ha dos casos:\\
    Cas 1.- Tots dos són senars: $m=2k_1+1, n=2k_2+1$,\\
    Llavors $m+n= 2(k_1 + k_2 + 1)$ és parell. \hfill QED.
    
Cas 2.- Tots dos són parells, $m=2k_1, n=2k_2$.\\
    Llavors $m+n=2(k_1+k_2)$ també és parell.  \hfill{QED}
  }}

\slide{Slide 5: Fals per contraexemple} %%%%%%%%%%%%%%

Per mostrar que una afirmació dels tipus ``Tots els \dots compleixen \dots'' és falsa, només cal trobar un cas que no ho
compleix. Haurem provat que és veritable la contrària ``Existeix un \dots que no compleix \dots''.

En diem un \textbf{contraexemple}.
\begin{itemize}
\item 
``Tots els polítics són honestos'' és fals, només cal esmentar-ne un que no ho sigui.
\item Totes les equacions del tipus $a x^2+b x+c = 0$ tenen dues solucions reals diferents. Fals: l'equació $x^2 +2 = 0$ no té cap
solució real.
\item Tot múltiple de 5 és també múltiple de 15. Fals: 20 és un contraexemple.
\end{itemize}

\textbf{Atenció}: Un exemple no mostra que l'afirmació sigui veritable, un contraexemple sí mostra que és falsa!

\begin{itemize}
\item És cert que la suma de tres nombres consecutius és divisible per tres?\\
  Sí: $n + (n+1) + (n+2) = 3n+3=3(n+1)$ és divisible per tres
sigui qui sigui $n$. Ho hem demostat per tots els $n$.
\item És cert que la suma de quatre nombres consecutius és divisible per quatre? \\
  No! Contraexeemple: $1+2+3+4=10$.
\end{itemize}


\subsubsection{Quizz pre-classe 0B2}




\subsubsection{Exercicis Llista}

\begin{enumerate}
\item Expressa la contrària de cadascuna de les següents afirmacions. Recorda que no es tracta aquí si són afirmacions verdaderes
  o no.
  \begin{enumerate}
  \item Cada dia de les vacances vem anar a la platja o al parc d'atraccions
  \item Totes les treballadores de l'empresa tenen categoria inferior a $D$.
  \item Tots els nois de la classe porten bambes Rivuk.
  \item Alguna noia de la classe porta texans Leibis.
  \item Algun dels meus amics és alemany.
  \item Cap professor de la facultat és de nacionalitat australiana.
  \item La funció $f(x)$ és diferenciable en tots els punts de $(0,1)$.
  \item Tot nombre natural és parell o senar.
  \item Tot múltiple de 3 és també múltiple de 5.
  \item Existeix un punt $x_0$ tal que  $f(x_0)=0$.
  \item Per tots els punts $x_1> x_2$ de l'interval $(0,1)$ es compleix $f(x_1)>f(x_2)$.
  \item En algun punt $x_0$ del domini de la funció $f(x)$, es compleix que $f'(x)=0$ i $f''(x_0)<0$. 
  \item La matriu $M$ té alguna fila amb tots els elements iguals a zero.
  \end{enumerate}
  
\item (problema 1.6-1 de S\&H) Considerem l'afirmació (discutible):\emph{ Si la inflació augmenta, l'atur disminueix}. Digues quines de les següents afirmacions són equivalents.
  \begin{enumerate}
  \item Perquè disminueixi l'atur cal que augmenti la inflació.
  \item Una condició suficient per tal que disminueixi l'atur és que creixi la inflació.
  \item L'atur disminueix només si creix la inflació.
  \item Si l'atur no disminueix, la inflació no creix.
  \item Una condició necessària per tal que creixi la inflació és que l'atur disminueixi.
  \end{enumerate}
  
  
\item Expressa les set primeres afirmacions de l'exercici anterior en la forma $\forall x\in X, p(x)$ o en la forma $\exists x\in X: p(x)$
    segons el cas. Per exemple, per la primera, direm: Sigui $X$ el conjunt dels dies de vacances, $p(x)=$ ``El dia $x$ vem anar a
    la platja'' i $q(x)=$ ``El dia $x$ vem anar al parc d'atraccions''. L'afirmació queda expressada amb $\forall x\in X, p(x)\vee q(x)$.

\item Demostra (per demostració directa) que la suma de cinc nombres naturals consecutius és múltiple de cinc.

    
\item \textbf{Eficiència Pareto}\label{sec:pareto-efic}
 En el llibre de text de Introducció a la Microeconomia que heu
  estudiat trobem, a 
  \href{https://www.core-econ.org/the-economy/book/es/text/leibniz-05-08-01.html}
  {5.8.1  La curva de eficiencia de Pareto}
  la següent definició:
  \emph{Una asignación factible es
  eficiente en términos de Pareto si no 
  existe una asignación dominante en términos de Pareto: es decir,
  nadie puede mejorar sin empeorar la situación de otro}.

Llegeix altre cop el capítol si no tens clar què vol dir la eficiència en termes Pareto.

Aquí ens interessa formalitzar els conceptes que apareixen. Posem que $A_1, A_2$ siguin dues assignacions factibles, és a dir que
assignen a cada individu unes quantitats que no superen el disponible i denotem $A_1(i), A_2(i)$ la utilitat que obté l'individu $i$ segons
les assignacions respectives.

Diem que $A_1$ \emph{domina} $A_2$ si, per tots els individus,  l'assignació segons $A_1$ és més gran o igual  que segons
$A_2$, és a dir que $\forall i, A_1(i)\geq  A_2(i)$ . Escribim $A_1\succeq A_2$ en aquest cas.

Llavors, si $\cal A$ denota el conjunt d'assignacions factibles, diem que $A^\star$ és una assignació Pareto-eficient si $\forall
A\in {\cal A}, A^\star \succeq A$.

\begin{enumerate}
\item Digues si per qualsevol assignació $A$ és cert que $A\succeq A$.
  \emph{Resposta:\/} Sí és cert, perquè per qualsevol individu es compleix $A(i) \geq  A(i)$.
\item Expressa fent aquestes notacions la afirmació ``$A_1$ no domina $A_2$''.\\
  \emph{Resposta:\/} Existeix algun individu pel qual l'assignació segons $A_1$ no és major o igual que segons $A_2$, o bé:
  $\exists i: A_1(i) < A_2(i)$.
\item Creus que  ``$A_1$ no domina $A_2$'' és aquivalent a ``$A_2$ domina $A_1$''?. Raona la teva resposta.\\
  \emph{Resposta:\/} No. La segona afirmació diu que per tots els individus la assignació segons $A_1$ és menor o igual que segons
  $A_2$.
\item Expressa amb les teves paraules la afirmació ``$A^\star$ no és una assignació Pareto-eficient''.
  \emph{Resposta:\/} Voldrà dir que hi ha alguna assignació $A\in {\cal A}$ tal que $A^\star$ no domina $A$.
  \end{enumerate}

%% \item \textbf{Finançament de les CCAA} En la distribució de recursos entre les CCAA 


\end{enumerate}



\subsubsection{Exercicis extra}

\begin{enumerate}
\item (Problema 1.6-2 del S\&H) Analitzeu el següent epitafi (a) des del punt de vista lògic i (b) des del punt de vista poètic.
  \begin{quote}
    Els que el van conèixer el van estimar\\
    Els que no el van estimar no el van conèixer.
  \end{quote}
\end{enumerate}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%% temporal
