Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 35 di 36

Validità del primo ordine

Una formula del primo ordine è valida, cioè vera in tutti i modelli?

\htmlData{term=RE}{\mathrm{RE}} \setminus \htmlData{term=R}{\mathrm{R}}

Nelle tracce · 2 domande

F06, domanda 6 SE23, domanda 2

Un esempio, passo dopo passo

1 / 3

Leggi la formula. Per ogni x, R(x) oppure la sua negazione. La domanda riguarda tutti i modelli. — 1. Leggi la formula
Per ogni $x$ , $R(x)$ oppure la sua negazione. La domanda riguarda tutti i modelli.

Scorri l'immagine o usa Avanti.

Ogni formula valida del primo ordine ha una dimostrazione formale. Enumerare le dimostrazioni permette di trovare prima o poi una prova delle istanze sì. Sulle istanze no la ricerca può non terminare: la validità è semidecidibile, ma non decidibile.

Complemento e collegamenti

Complemento:

restringere la forma delle formule: da indecidibile a NEXP-completo

Indecidibilità del primo ordine

Domande e trappole d'esame

F06#6
La validità di una formula del primo ordine è in RE?
SÌSi enumerano le dimostrazioni. Ripetuta in SE23#2.

Problemi del corso

1. Leggi la formula

2. Usa una legge logica

3. Concludi la validità