In quanti modi si possono quantificare 3 variabili?
La domanda di calcolo combinatorio/logica elementare è la seguente: in quanti modi, in un predicato a 3 variabili, si possono quantificare tutte e 3 le variabili? (naturalmente ottenendo proposizioni che abbiano significato diverso!)
Io ho ragionato così: i modi di permutare le 3 variabili sono 3!, per ciascuna di queste permutazioni posso disporre i quantificatori in 8 modi. In totale ho 48 configurazioni, che si dividono in due classi:
- quelle con 3 quantificatori uguali
- quelle con 2 quantificatori uguali
le prime sono 3! per due, quindi 12, di cui devo contarne solo 2 ai fini dei mio calcolo. (perché se ho tre "esiste" o tre "per ogni", non importa come sono disposte le variabili, ottengo sempre la stessa proposizione).
Le seconde invece sono, per differenza, 48-12=36. E ciascuna è "doppia", cioè si ripresenta la stessa proposizione in due configurazioni diverse semplicemente scambiando le due variabili con lo stesso quantificatore. Quindi in totale le configurazioni della seconda classe danno 36:2=18 proposizioni diverse.
Totale: 18+2=20 proposizioni.
Ci trovate qualcosa di sbagliato o brutto nel ragionamento? Sono ben accetti consigli.
(Non ho il risultato del calcolo né la soluzione quindi potrei aver fatto errori)
In più ho un'altra piccola domanda. Le negazioni di queste proposizioni sono anch'esse 20, e a livello di "configurazione di quantificatori e variabili" (spero capiate cosa voglio dire) sono le stesse di quelle sopra, ma permutate, giusto?
Avevo pensato di elencarle tutte per forza bruta, ma mi annoia.
Io ho ragionato così: i modi di permutare le 3 variabili sono 3!, per ciascuna di queste permutazioni posso disporre i quantificatori in 8 modi. In totale ho 48 configurazioni, che si dividono in due classi:
- quelle con 3 quantificatori uguali
- quelle con 2 quantificatori uguali
le prime sono 3! per due, quindi 12, di cui devo contarne solo 2 ai fini dei mio calcolo. (perché se ho tre "esiste" o tre "per ogni", non importa come sono disposte le variabili, ottengo sempre la stessa proposizione).
Le seconde invece sono, per differenza, 48-12=36. E ciascuna è "doppia", cioè si ripresenta la stessa proposizione in due configurazioni diverse semplicemente scambiando le due variabili con lo stesso quantificatore. Quindi in totale le configurazioni della seconda classe danno 36:2=18 proposizioni diverse.
Totale: 18+2=20 proposizioni.
Ci trovate qualcosa di sbagliato o brutto nel ragionamento? Sono ben accetti consigli.
(Non ho il risultato del calcolo né la soluzione quindi potrei aver fatto errori)
In più ho un'altra piccola domanda. Le negazioni di queste proposizioni sono anch'esse 20, e a livello di "configurazione di quantificatori e variabili" (spero capiate cosa voglio dire) sono le stesse di quelle sopra, ma permutate, giusto?
Avevo pensato di elencarle tutte per forza bruta, ma mi annoia.
Risposte
nessuna risposta... non capisco se sono stato poco chiaro o se l'esercizio sia noioso o che altro...
comunque provo a ripeterlo:
Dato un predicato $P(x,y,z)$, una possibile saturazione di tutte e tre le variabili è, ad esempio:
$EE xAA yEE z:P(x,y,z)$
Quante sono tutte le possibili saturazioni diverse?
Ovviamente cambiando i quantificatori ottengo saturazioni diverse, ma anche permutando le variabili
(dire $AA yEEx:P(x,y)$ è diverso da dire $EEx AAy:P(x,y)$)
comunque provo a ripeterlo:
Dato un predicato $P(x,y,z)$, una possibile saturazione di tutte e tre le variabili è, ad esempio:
$EE xAA yEE z:P(x,y,z)$
Quante sono tutte le possibili saturazioni diverse?
Ovviamente cambiando i quantificatori ottengo saturazioni diverse, ma anche permutando le variabili
(dire $AA yEEx:P(x,y)$ è diverso da dire $EEx AAy:P(x,y)$)
A una prima occhiata hai 3! possibilità per i quantoficatori e 3! per le variabili quindi in totale 36.
Ripensandoci hai 8 possibilità per i quantificatori. Quindi viene 8*6=48.
si ma fra quelle che conti tu ce ne sono molte uguali, ad esempio
$AAx AAy AAz, P(x,y,z)$ è uguale a $AAy AAz AAx, P(x,y,z)$
Ho fatto tutto il ragionamento nel primo messaaggio e sono arrivato a ottenere 20 come risultato, vorrei solo capire se è giusto o no
$AAx AAy AAz, P(x,y,z)$ è uguale a $AAy AAz AAx, P(x,y,z)$
Ho fatto tutto il ragionamento nel primo messaaggio e sono arrivato a ottenere 20 come risultato, vorrei solo capire se è giusto o no
In base al tuo calcolo stai considerando $\forall x \exists y \forall z$ e $\forall x \forall z \exists y$ equivalenti, quando secondo me non lo sono.
No, in realtà considero uguali queste due fra loro
$ AA x EEy AA z$ e $AA z EE y AA x$
e queste altre due fra di loro:
$AA z AAx EEy$ e $AAx AAz EEy$
cioè, da una scrittura con 2 quantificatori uguali ne ottengo una equivalente scambiando di posto le due variabili (con rispettivo quantificatore)
$ AA x EEy AA z$ e $AA z EE y AA x$
e queste altre due fra di loro:
$AA z AAx EEy$ e $AAx AAz EEy$
cioè, da una scrittura con 2 quantificatori uguali ne ottengo una equivalente scambiando di posto le due variabili (con rispettivo quantificatore)
"Oshawott277":Non sono uguali, per esempio
No, in realtà considero uguali queste due fra loro
$ AA x EEy AA z$ e $AA z EE y AA x$
$ AA x EE y AA z$ $x=y$ è vera (basta scegliere $y=x$) mentre
$ AA z EE y AA x$ $x=y$ è ovviamente falsa.
Secondo me puoi scambiare due coppie quantificatore+variabile solo se sono adiacenti. Concordi?
"Martino":Non sono uguali, per esempio
[quote="Oshawott277"]No, in realtà considero uguali queste due fra loro
$ AA x EEy AA z$ e $AA z EE y AA x$
$ AA x EE y AA z$ $x=y$ è vera (basta scegliere $y=x$) mentre
$ AA z EE y AA x$ $x=y$ è ovviamente falsa.
Secondo me puoi scambiare due coppie quantificatore+variabile solo se sono adiacenti. Concordi?[/quote]
Non potresti farmi un esempio con un predicato in 3 variabili?
Ok, al posto di $x=y$ prendi "$x=y$ e $z=z$".
Secondo me le coppie quantificatore-variabile non possono essere scambiate nemmeno se adiacenti.
Siano \( x \) e \( y \) numeri reali.
\( ( \forall x ) ( \exists y ) ( x < y ) \) è vera.
\( ( \exists y ) ( \forall x ) ( x < y ) \) è falsa.
Le coppie quantificatore-variabile possono essere scambiate solo se adiacenti e con quantificatori omogenei.
Siano \( x \) e \( y \) numeri reali.
\( ( \forall x ) ( \exists y ) ( x < y ) \) è vera.
\( ( \exists y ) ( \forall x ) ( x < y ) \) è falsa.
Le coppie quantificatore-variabile possono essere scambiate solo se adiacenti e con quantificatori omogenei.
Sì intendevo adiacenti con lo stesso quantificatore
Quindi in definitiva secondo voi le proposizioni della classe con 2 quantificatori uguali sono tutte diverse fra di loro tranne quelle con quantificatori adiacenti, che sono doppie... quindi divido ulteriormente in altre due sottoclassi:
- quella con quntificatori adiacenti (da contare una volta, anziché due... perché permutando le due variabili (con annesso quantificatore uguale) adiacenti ottengo la stessa proposizione)
- quella con quantificatori non adiacenti (da contare due volte)
della seconda classe ne ho $2\cdot3!$ e devo contarne $12$, mentre della prima ne ho, per differenza $36-12=24$, ognuna doppia, quindi devo contarne $12$.
In definitiva $12+12=24$ sono le prop diverse con 2 quantificatori uguali
più 2 che sono quelle con 3 quantificatori uguali
Totale $ 24+2=26$
non dovrebbe esserci alcuna differenza tra le proposizioni che abbiano due $AA$ adiacenti o due $EE$ adiacenti ottenute scambiando le due variabili con lo stesso quantificatore... giusto?
- quella con quntificatori adiacenti (da contare una volta, anziché due... perché permutando le due variabili (con annesso quantificatore uguale) adiacenti ottengo la stessa proposizione)
- quella con quantificatori non adiacenti (da contare due volte)
della seconda classe ne ho $2\cdot3!$ e devo contarne $12$, mentre della prima ne ho, per differenza $36-12=24$, ognuna doppia, quindi devo contarne $12$.
In definitiva $12+12=24$ sono le prop diverse con 2 quantificatori uguali
più 2 che sono quelle con 3 quantificatori uguali
Totale $ 24+2=26$
non dovrebbe esserci alcuna differenza tra le proposizioni che abbiano due $AA$ adiacenti o due $EE$ adiacenti ottenute scambiando le due variabili con lo stesso quantificatore... giusto?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo