Esercizi di Matematica Discreta e Logica
Non riesco a svolgere nè il punto b) nè il punto c)
Per quanto riguarda il punto b) Gli elementi di $S4$ dovrebbero essere ${[0][1][2][3]}$ giusto? Da qui mi viene da pensare che devo calcolare l'insieme di tutti gli interi tali che, divisi per $n$, danno lo stesso resto dalla divisione di $ a/n $ . Però non riesco ad ottenere nessun risultato simile alle soluzioni
c) La soluzione dice che $S4$ ha 4!=24 elementi e l'insieme $M$ avendo 9 elementi (quindi sopra già sbaglio tutto) non può essere sottogruppo in quanto 9 non divide 6
a) Non riesco a capire come dimostrare che l'anello contiene elementi non nulli e non invertibili.
Lui dice:
Ma quella forma di scrittura mi destabilizza, non ho idea di cosa stia facendo a parte il MCD
Per quanto riguarda il punto b) non ho idea di come si faccia
Infine sono alla ricerca disperata di appunti di LOGICA su Reticoli, algebre di Boole e Cardinalità.
Non riesco a trovare niente di utile per capire come disegnare i reticoli o svolgere esercizi (presenti nel compito all'esame) del tipo:
sapreste consigliarmi qualche videolezione o appunti dai quali prendere spunto per capirci qualcosa?
Grazie in anticipo.
Risposte
Ciao, ti rispondo ai primi due quesiti e ti invito, la prossima volta, a trascrivere il problema e a non postare foto.
No, sbagliato. Mi sa che ti stai confondendo con $(\mathbb{Z_4}, +)$. $S_4$ è l'insieme di tutte le funzioni bigettive da un insieme di 4 elementi in sé. In pratica prendi $I_4 = {1, 2, 3, 4}$, considera tutte le funzioni biettive $f:I_4 \to I_4$, queste si chiamano permutazioni di un insieme di $4$ elementi e formano $S_4$ che forma un gruppo rispetto alla composizione di funzioni. Adesso: quante sono le funzioni bigettiva da $I_4$ in sé? Beh vediamo quante sono queste funzioni: prendiamo $1$ per esempio, dove posso mandarlo? Posso mandarlo $1, 2, 3$ o $4$,per $2$ avrò $3$ scelte(escludo infatti il numero che ho scelto per $1$), per $3$ avrò $2$ scelte(escludo i numeri scelti precedentemente), per $4$ ho una sola scelte. Quindi in totale ho $4*3*2*1 = 4! = 24$ permutazioni di $4$ elementi.
Per caso ti hanno detto come si rappresentano delle permutazioni? Per esempio, hai mai sentito parlare della rappresentazione in cicli disgiunti?
Non è l'unica strada percorribile, in un campo vale la legge di annullamento del prodotto, cioè: se $ab = 0$ e $a != 0$ allora $b = 0$.
In questo caso prendi $a = [2]_14$ e $b = [7]_14$ allora $ab = [14]_14 = [0]_14$ ma né $a$ né $b$ sono nulli, pertanto non è campo.
$[2k]_14 = [1]_14$ equivale a dire che $2k \equiv 1 \mod 14$, adesso: questa è una congruenza lineare, cioè un'equazione del tipo $ax \equiv b \mod n$, che ha soluzione se e solo se $MCD(a, n) | b$(sai spiegare il perché?).
Dunque $2k \equiv = 1 \mod 14$ ha soluzione se e solo se $MCD(2, 14) = 2 | 1$, che è falso e pertanto non ha soluzione, cioè $2$ non è invertibile.
Per il punto $b$: 1)$K$ ha cardinalità $\phi(14) = 6$, dato che $(3, 14) = 1$ allora $[3]_14 \in K$, applichiamo il teorema di Eulero: $601 = 6*100 + 1$ quindi $[3^{601}]_14 = [(3^{6})^{100} * 3]_14 = [ 1^(100) * 3]_14 = [3]_14$.
Calcoliamoci le prime $6$ potenze di $3$ modulo $14$: $3^1 \equiv 3 \mod 14$, $3^2 \equiv 9 \mod \4$, $3^3 \equiv 27 \equiv 13 \mod 14$, $3^4 \equiv 39 \equiv 11 \mod 14$, $3^5 \equiv 33 \equiv 5 \mod 14$, $3^6 \equiv 15 \equiv 1 \mod 14$, sono $6$ elementi coprimi con $14$, quindi appartengono a $K$ ma $K$ ha cardinalità $6$ quindi $[3]_14$ genera $K$.
Per quanto riguarda il punto b) Gli elementi di $S4$ dovrebbero essere ${[0][1][2][3]}$ giusto?
No, sbagliato. Mi sa che ti stai confondendo con $(\mathbb{Z_4}, +)$. $S_4$ è l'insieme di tutte le funzioni bigettive da un insieme di 4 elementi in sé. In pratica prendi $I_4 = {1, 2, 3, 4}$, considera tutte le funzioni biettive $f:I_4 \to I_4$, queste si chiamano permutazioni di un insieme di $4$ elementi e formano $S_4$ che forma un gruppo rispetto alla composizione di funzioni. Adesso: quante sono le funzioni bigettiva da $I_4$ in sé? Beh vediamo quante sono queste funzioni: prendiamo $1$ per esempio, dove posso mandarlo? Posso mandarlo $1, 2, 3$ o $4$,per $2$ avrò $3$ scelte(escludo infatti il numero che ho scelto per $1$), per $3$ avrò $2$ scelte(escludo i numeri scelti precedentemente), per $4$ ho una sola scelte. Quindi in totale ho $4*3*2*1 = 4! = 24$ permutazioni di $4$ elementi.
Per caso ti hanno detto come si rappresentano delle permutazioni? Per esempio, hai mai sentito parlare della rappresentazione in cicli disgiunti?
a) Non riesco a capire come dimostrare che l'anello contiene elementi non nulli e non invertibili.
Non è l'unica strada percorribile, in un campo vale la legge di annullamento del prodotto, cioè: se $ab = 0$ e $a != 0$ allora $b = 0$.
In questo caso prendi $a = [2]_14$ e $b = [7]_14$ allora $ab = [14]_14 = [0]_14$ ma né $a$ né $b$ sono nulli, pertanto non è campo.
Lui dice:
Ma quella forma di scrittura mi destabilizza, non ho idea di cosa stia facendo a parte il MCD
Per quanto riguarda il punto b) non ho idea di come si faccia
$[2k]_14 = [1]_14$ equivale a dire che $2k \equiv 1 \mod 14$, adesso: questa è una congruenza lineare, cioè un'equazione del tipo $ax \equiv b \mod n$, che ha soluzione se e solo se $MCD(a, n) | b$(sai spiegare il perché?).
Dunque $2k \equiv = 1 \mod 14$ ha soluzione se e solo se $MCD(2, 14) = 2 | 1$, che è falso e pertanto non ha soluzione, cioè $2$ non è invertibile.
Per il punto $b$: 1)$K$ ha cardinalità $\phi(14) = 6$, dato che $(3, 14) = 1$ allora $[3]_14 \in K$, applichiamo il teorema di Eulero: $601 = 6*100 + 1$ quindi $[3^{601}]_14 = [(3^{6})^{100} * 3]_14 = [ 1^(100) * 3]_14 = [3]_14$.
Calcoliamoci le prime $6$ potenze di $3$ modulo $14$: $3^1 \equiv 3 \mod 14$, $3^2 \equiv 9 \mod \4$, $3^3 \equiv 27 \equiv 13 \mod 14$, $3^4 \equiv 39 \equiv 11 \mod 14$, $3^5 \equiv 33 \equiv 5 \mod 14$, $3^6 \equiv 15 \equiv 1 \mod 14$, sono $6$ elementi coprimi con $14$, quindi appartengono a $K$ ma $K$ ha cardinalità $6$ quindi $[3]_14$ genera $K$.
"Shocker":
Ciao, ti rispondo ai primi due quesiti e ti invito, la prossima volta, a trascrivere il problema e a non postare foto.
Ok scusa, l'ho fatto solo per una questione di velocità visto che non conosco il codice per tutti i simboli
Per caso ti hanno detto come si rappresentano delle permutazioni? Per esempio, hai mai sentito parlare della rappresentazione in cicli disgiunti?
Si, ho fatto alcune simulazioni d'esame svolgendo esercizi del genere!
$[2k]_14 = [1]_14$ equivale a dire che $2k \equiv 1 \mod 14$, adesso: questa è una congruenza lineare, cioè un'equazione del tipo $ax \equiv b \mod n$, che ha soluzione se e solo se $MCD(a, n) | b$(sai spiegare il perché?).
No, non saprei spiegarlo
Per il punto $b$: 1)$K$ ha cardinalità $\phi(14) = 6$, dato che $(3, 14) = 1$ allora $[3]_14 \in K$, applichiamo il teorema di Eulero: $601 = 6*100 + 1$ quindi $[3^{601}]_14 = [(3^{6})^{100} * 3]_14 = [ 1^(100) * 3]_14 = [3]_14$.
Calcoliamoci le prime $6$ potenze di $3$ modulo $14$: $3^1 \equiv 3 \mod 14$, $3^2 \equiv 9 \mod \4$, $3^3 \equiv 27 \equiv 13 \mod 14$, $3^4 \equiv 39 \equiv 11 \mod 14$, $3^5 \equiv 33 \equiv 5 \mod 14$, $3^6 \equiv 15 \equiv 1 \mod 14$, sono $6$ elementi coprimi con $14$, quindi appartengono a $K$ ma $K$ ha cardinalità $6$ quindi $[3]_14$ genera $K$.
Non capisco alcuni passaggi qui
$\phi(14) = 6$ perché? Sugli appunti ho come calcolare $\phi(n)$ Se $n$ è primo o $r$ ed $s$ sono coprimi, ma non arrivo a niente di utile!
$601 = 6*100 + 1$ quindi $[3^{601}]_14 = [(3^{6})^{100} * 3]_14 = [ 1^(100) * 3]_14 = [3]_14$ quale parte di teoria devo leggere per comprendere questi calcoli?
Anche per questa parte non trovo corrispondenze con gli appunti che ho, confusione totale...$3^4 \equiv 39 \equiv 11 \mod 14$, $3^5 \equiv 33 \equiv 5 \mod 14$, $3^6 \equiv 15 \equiv 1 \mod 14$
Perché $3^4 \equiv 39 \equiv 11 \mod 14$ e non $3^4 \equiv 81 $ ??
Grazie mille per la risposta.
"MatematiNO":
Per caso ti hanno detto come si rappresentano delle permutazioni? Per esempio, hai mai sentito parlare della rappresentazione in cicli disgiunti?
Si, ho fatto alcune simulazioni d'esame svolgendo esercizi del genere!
Perfetto, allora iniziamo a capire come sono fatti gli elementi di $S_4$ di ordine che divide $3$: se l'ordine è $1$ abbiamo solo l'identità, se l'ordine è $3$ abbiamo solo i tricicli, cioè permutazioni del tipo $(a, b, c)$, per esempio $(1, 2, 3)$ è un triciclo e ha ordine $3$(verifica). Ce ne possono essere altri di ordine $3$? La risposta è no: le trasposizioni(cicli del tipo $(a, b)$, tipo $(1, 2)$) hanno ordine $2$ mentre i 4-cicli hanno ordine $4$, per esempio $(1, 2, 3, 4)$, esistono altri tipi di permutazioni in $S_4$? Sì, le doppie coppie come $(1, 2)(3, 4)$ ma anche queste hanno ordine $2$. In definitiva in $S_4$ gli unici elementi che hanno ordine che divide $3$ sono i tricicli e l'identità.
Ti passo questi appunti di Aritmetica, a pagina 72 trovi una breve presentazione di $S_n$, ti consiglio di provare a fare anche gli esercizi, sono molto importanti per la comprensione di questo gruppo.
[quote]
$[2k]_14 = [1]_14$ equivale a dire che $2k \equiv 1 \mod 14$, adesso: questa è una congruenza lineare, cioè un'equazione del tipo $ax \equiv b \mod n$, che ha soluzione se e solo se $MCD(a, n) | b$(sai spiegare il perché?).
No, non saprei spiegarlo
[/quote]
Riflettiamo sul significato di $ax \equiv b mod n$, questo vuol dire che esiste almeno un $z \in \mathbb{Z}$ tale che $ax + nz = b$, adesso vediamo questa scrittura come equazione nelle variabili $x$ e $y$. Un'equazione di questo tipo, di cui si ricercano le soluzioni intere, viene detta equazione diofantea e ha soluzione se e solo se $MCD(a, n) | b$. La dimostrazione la puoi trovare su un qualunque libro di testo o dispense, per esempio la puoi trovare a pagina 23 delle dispense che ti ho linkato.
Non capisco alcuni passaggi qui
$\phi(14) = 6$ perché? Sugli appunti ho come calcolare $\phi(n)$ Se $n$ è primo o $r$ ed $s$ sono coprimi, ma non arrivo a niente di utile!
$\phi(14) = \phi(7*2)$, $7$ e $2$ sono coprimi quindi $\phi(7*2) = \phi(7)*\phi(2) = 6*1 = 6$
$601 = 6*100 + 1$ quindi $[3^{601}]_14 = [(3^{6})^{100} * 3]_14 = [ 1^(100) * 3]_14 = [3]_14$ quale parte di teoria devo leggere per comprendere questi calcoli?
Ho applicato il teorema di eulero: $K$ è un gruppo quindi $\forall a \in K$ si ha che $a^(|K|) = e$ dove per $e$ intendo l'identità rispetto all'operazione del gruppo e per $|K|$ intendo la cardinalità di $K$.
nel nostro caso $|K|= 6$ e $[3]_14 \in K$, quindi $[(3^(6))^(m)]_14 = [1]_14$ per ogni $m$ intero.
$3^4 \equiv 39 \equiv 11 \mod 14$, $3^5 \equiv 33 \equiv 5 \mod 14$, $3^6 \equiv 15 \equiv 1 \mod 14$
Perché $3^4 \equiv 39 \equiv 11 \mod 14$ e non $3^4 \equiv 81 $ ??
Grazie mille per la risposta.
Sì $3^4 \equiv 81 \mod 14$ ma possiamo evitare tutti questi conti: $3^4 = 3^3 * 3$ e $3^3 \equiv 13 \mod 14$ quindi $3^4 \equiv 3^3 * 3 \equiv 13* 3 \equiv 39 \equiv 11 \mod 14$. Chiaro?
Anche con $3^4 \equiv 81 \mod 14$ otteresti comunque $11$: basta dividere $81$ per $14$ e vedere il resto.
"Shocker":
[quote="MatematiNO"]
Per caso ti hanno detto come si rappresentano delle permutazioni? Per esempio, hai mai sentito parlare della rappresentazione in cicli disgiunti?
Si, ho fatto alcune simulazioni d'esame svolgendo esercizi del genere!
Perfetto, allora iniziamo a capire come sono fatti gli elementi di $S_4$ di ordine che divide $3$: se l'ordine è $1$ abbiamo solo l'identità, se l'ordine è $3$ abbiamo solo i tricicli, cioè permutazioni del tipo $(a, b, c)$, per esempio $(1, 2, 3)$ è un triciclo e ha ordine $3$(verifica). Ce ne possono essere altri di ordine $3$? La risposta è no: le trasposizioni(cicli del tipo $(a, b)$, tipo $(1, 2)$) hanno ordine $2$ mentre i 4-cicli hanno ordine $4$, per esempio $(1, 2, 3, 4)$, esistono altri tipi di permutazioni in $S_4$? Sì, le doppie coppie come $(1, 2)(3, 4)$ ma anche queste hanno ordine $2$. In definitiva in $S_4$ gli unici elementi che hanno ordine che divide $3$ sono i tricicli e l'identità.
Ti passo questi appunti di Aritmetica, a pagina 72 trovi una breve presentazione di $S_n$, ti consiglio di provare a fare anche gli esercizi, sono molto importanti per la comprensione di questo gruppo.
[quote]
$[2k]_14 = [1]_14$ equivale a dire che $2k \equiv 1 \mod 14$, adesso: questa è una congruenza lineare, cioè un'equazione del tipo $ax \equiv b \mod n$, che ha soluzione se e solo se $MCD(a, n) | b$(sai spiegare il perché?).
No, non saprei spiegarlo
[/quote]
Riflettiamo sul significato di $ax \equiv b mod n$, questo vuol dire che esiste almeno un $z \in \mathbb{Z}$ tale che $ax + nz = b$, adesso vediamo questa scrittura come equazione nelle variabili $x$ e $y$. Un'equazione di questo tipo, di cui si ricercano le soluzioni intere, viene detta equazione diofantea e ha soluzione se e solo se $MCD(a, n) | b$. La dimostrazione la puoi trovare su un qualunque libro di testo o dispense, per esempio la puoi trovare a pagina 23 delle dispense che ti ho linkato.
Non capisco alcuni passaggi qui
$\phi(14) = 6$ perché? Sugli appunti ho come calcolare $\phi(n)$ Se $n$ è primo o $r$ ed $s$ sono coprimi, ma non arrivo a niente di utile!
$\phi(14) = \phi(7*2)$, $7$ e $2$ sono coprimi quindi $\phi(7*2) = \phi(7)*\phi(2) = 6*1 = 6$
$601 = 6*100 + 1$ quindi $[3^{601}]_14 = [(3^{6})^{100} * 3]_14 = [ 1^(100) * 3]_14 = [3]_14$ quale parte di teoria devo leggere per comprendere questi calcoli?
Ho applicato il teorema di eulero: $K$ è un gruppo quindi $\forall a \in K$ si ha che $a^(|K|) = e$ dove per $e$ intendo l'identità rispetto all'operazione del gruppo e per $|K|$ intendo la cardinalità di $K$.
nel nostro caso $|K|= 6$ e $[3]_14 \in K$, quindi $[(3^(6))^(m)]_14 = [1]_14$ per ogni $m$ intero.
$3^4 \equiv 39 \equiv 11 \mod 14$, $3^5 \equiv 33 \equiv 5 \mod 14$, $3^6 \equiv 15 \equiv 1 \mod 14$
Perché $3^4 \equiv 39 \equiv 11 \mod 14$ e non $3^4 \equiv 81 $ ??
Grazie mille per la risposta.
Sì $3^4 \equiv 81 \mod 14$ ma possiamo evitare tutti questi conti: $3^4 = 3^3 * 3$ e $3^3 \equiv 13 \mod 14$ quindi $3^4 \equiv 3^3 * 3 \equiv 13* 3 \equiv 39 \equiv 11 \mod 14$. Chiaro?
Anche con $3^4 \equiv 81 \mod 14$ otteresti comunque $11$: basta dividere $81$ per $14$ e vedere il resto.[/quote]
Tutto chiaro!! Grazie mille
Perché citare tutto ? Ringraziare non ti bastava? ](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo