Negazione quantificatori

aritmetico
Ciao :)

Avrei una domanda abbastanza terra-terra cui vorrei cercare di darmi risposta. Nelle lezioni di algebra ci sono alcune nozioni di logica e il professore ha detto di mostrare che

Dato un P(x) mostrare l'equivalenza logica
¬(∀xP(x)=∃x(¬P(x))

Il problema è che riesco a vederlo con esempi di P(x) concreti, ma non so come dimostrarlo per un P(x) qualunque.
So che l'equivalenza logica si ha di due proposizioni A=B si ha quando A<=>B è sempre vera (cioè quando A e B hanno stesso valore di verità) però non credo saperlo sfruttare in questo caso.

Leggendo qui: https://www.matematicamente.it/appunti/ ... negazione/ vengono dati come DEFINIZIONI nemmeno come qualcosa di dimostrabile.

Non ho quindi capito se ho frainteso io la richiesta del Professore o se mi sfugge qualcosa.

RIngrazio per gli aiuti.

Risposte
G.D.5
Dipende da qual è il livello al quale stiamo lavorando.
Innanzitutto in che modo sono stati definiti i quantificatori?
In che tipo di logica siamo? Ci sono delle logiche dove non vale questa equivalenza.
Come è definito il concetto di equivalenza logica?

Edit.
Si potrebbe anche definire un quantificatore in funzione dell'altro sicché questa equivalenza diventerebbe semplice conseguenza della legge di doppia negazione.

Edit #2.
Che fine ha fatto il tuo altro thread? Quando sono entrato nella sezione di Algebra sono sicuro di aver visto un'altra tua richiesta.

aritmetico
Ciao grazie per la risposta:

1) sto studiando algerba 1 quindi molto base :D

2) Non lo sapevo!

3)Ho modificato perche avevo commesso un typo e credo sia andato in moderazione di nuovo per essere approvato.

G.D.5
E allora.

Premessa importante: supponendo che i due quantificatori siano stati definiti separatamente e che questa equivalenza non sia data come assioma (assieme ad eventuali altri) proprio allo scopo di definire i quantificatori, e facendo l'ipotesi che il significato dei quantificatori sia fornito nel linguaggio naturale (i.e. \( \forall x P(x) \) significa che qualunque \(x\) del dominio del discorso rende vera \(P(x)\) e \( \exists x P(x) \) significa che almeno una \( x \) del dominio del discorso rende vera \(P(x)\)), quelle che seguono non sono delle dimostrazioni formali. Qui entriamo nel campo della logica vera e propria, quindi occorrerebbe definire come si deve il linguaggio, la semantica, le regole di deduzione e tante altre cosucce per avere delle dimostrazioni formali vere e proprie. Diciamo che le prove che seguono sono la versione informale e in linguaggio naturale di possibili prove formali. Per produrre le quali prove ci serviremo delle seguenti regole derivanti dalle definizioni dei quantificatori:

    [*:2pu50hpk] da \(\forall x P(x)\), deriviamo \(P(x_0)\) per qualunque \(x_0\) nel dominio del discorso;[/*:m:2pu50hpk]
    [*:2pu50hpk] da \(\exists x P(x)\), deriviamo \(P(x_0)\) per qualche \(x_0\) nel dominio del discorso;[/*:m:2pu50hpk]
    [*:2pu50hpk] se riusciamo a dimostrare che vale \(P(x_0)\) per una \(x_0\) nel dominio del discorso sulla quale non siano state fatte ipotesi, allora possiamo derivare \(\forall x P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] se riusciamo a dimostrare che vale \(P(x_0)\) per qualche \(x_0\) nel dominio del discorso sulla quale siano state fatte o meno delle ipotesi, possiamo derivare \(\exists x P(x)\).[/*:m:2pu50hpk][/list:u:2pu50hpk]

    Dimostriamo che \( \neg \forall x P(x) \leftrightarrow \exists x \neg P(x) \). Bisogna dimostrare due condizionli:

    \[
    \begin{align}
    \neg \forall x P(x) \to \exists x \neg P(x) \\
    \exists x \neg P(x) \to \neg \forall x P(x)
    \end{align}
    \]

    Dimostriamo prima \((2)\). Lo facciamo per assurdo.
    [list=a]
    [*:2pu50hpk] Assumiamo l'antecedente del condizionale \((2)\), i.e. \(\exists x \neg P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] assumiamo anche la negazione del conseguente del condizionale \((2)\), i.e. \(\neg\neg\forall x P(x) \equiv \forall x P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] da \( \exists x \neg P(x) \), otteniamo \(\neg P(x_0)\) per qualche \(x_0\);[/*:m:2pu50hpk]
    [*:2pu50hpk] da \(\forall x P(x)\), otteniamo che, per lo stesso \(x_0\), deve essere \(P(x_0)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] (c) e (d) costituiscono una contraddizione, sicché \(\forall x P(x)\) va rigettata e si conclude che è \(\neg \forall x P(x)\). [/*:m:2pu50hpk][/list:o:2pu50hpk]

    Dimostriamo adesso \((1)\):
    [list=i]
    [*:2pu50hpk] assumiamo l'antecedente del condizionale \((2)\), i.e. \(\neg \forall x P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] assumiamo la negazione del conseguente del condizionale \((2)\), i.e. \(\neg \exists x \neg P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] sia \(x_0\) nel dominio del discorso: o è \(\neg P(x_0)\) o è \(P(x_0)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] assumiamo che sia \(\neg P(x_0)\): per le regole sui quantificatori possiamo introdurre il quantificatore esistenziale su (iii): \(\exists x \neg P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] ma (ii) e (iv) sono in contraddizione, quindi, non potendo essere \(\neg P(x_0)\), deve essere \(\neg \neg P(x_0) \equiv P(x_0)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] se è \(P(x_0)\), essendo \(x_0\) arbitraria, per le regole sui quantificatori possiamo introdurre su (v) il quantificatore universale: \(\forall x P(x)\);[/*:m:2pu50hpk]
    [*:2pu50hpk] ma (vi) è in contraddizione con (i), quindi rigettiamo (ii) - è infatti grazie a (ii) che avevamo stabilito che per una arbitraria \(x_0\) doveva essere \(P(x_0)\) - e concludiamo \(\neg \neg \exists x \neg P(x) \equiv \exists x \neg P(x)\).[/*:m:2pu50hpk][/list:o:2pu50hpk]

    Alternativamente avremmo potuto produrre una sorta di prova basata sulla semantica: se il significato di \(\forall x P(x)\) è che qualunque \(x_0\) si sostituisca a \(x\) si ottiene una \(P(x_0)\) vera, allora il significato di \(\neg \forall x P(x)\) è che quanto prima non è vero, il che significa che sostituendo a \(x\) i valori del dominio del discorso, ad un certo punto ci imbatteremo in una \(x_0\) che rende falsa \(P(x)\), rendendo quindi vera \(\neg P(x)\), la quale occorrenza è il significato di \(\exists x \neg P(x)\). Valendo anche il vicecersa, si conclude l'equivalenza. Questa è più una prova basata sulle proprietà che hanno nel linguaggio naturale i significati dei quantificatori, significati che a loro volta costituiscono una definizione dei quantificatori.

aritmetico
Non ci sarei davvero mai arrivato. Grazie per la spiegazione così dettagliata. Veramente, grazie mille :)

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.