mathematical logic

Question 1

dimostrazione del compatness theorem

Answer 1

costruzione, 4 fatti, conseguenze e collegamento con structural induction principle, estensione massima FL

Question 2

logica preposizionale, sentenze semplici/complesse, principio di induzione strutturale

Question 3

proprietà logica preposizionale, fissare mondo possibile, tautologia, dimostraizone semantica implica

Question 4

lemma generico e unique redability

Answer 4

lemma che in sostanza sancisce relazoine v, ~v e unique redability derivata da structural induction principle per capire se una formula appritene e FL

Question 5

definizione teorie, corollario lemma generico

Answer 5

cos’è teoria e come si soddisfa, e corollario lemma generico (valutazione formula)

Question 6

semantica teorie

Answer 6

sematntica teorie -> teorema not A e semantical deduction

Question 7

relazione d’ordine parziale, isomorfismo, lattice,costanti logiche, struttura algebrica, lattice e struttura algebrica

Answer 7

poset, come rendo latttice in struttura algebrica (check) proprietà delle varie strutture

Question 8

congruenza, sostituzione

Answer 8

conceto di congurenza, definizione di induzione in maniera induttiva, teorema e lemma sostutizione

Question 9

algebra booleana

Question 10

bolean algebra applicata a insiemi, lindembaum algebra, term function, idempotenza da assorbimento, boolean algebra term function

Answer 10

cardinalità boolean algebra, FL di n, equivalenza term function -> lindembaum algebra, definizione induttiva di term function

Question 11

enunciato completness theorem, forme normali e idee associate, continuos iphotesis, set di operatori funzionalmente completo

Answer 11

precisare anche che completeness theorem funziona solo con n finito, forme normali anche induction e negation free

Question 12

sottoformula, da generale a ifnf, da ifnf a nnf, terminologie, generic formula equivalente a CNF o DNF

Question 13

struttura mdt, mdt non deterministica, definizione formale di P,NP, NP completo, concetto di guess and check, formulaizone di f.polinomiale e riduzione

Question 14

idea dietro teorema cook, DNF sat, riducibilità SAT-CNF, equisat

Answer 14

equisat come classe di equivalenza, non congruenza

Question 15

dimostrazione riducbilità SAT-CNF, CNF come insieme

Answer 15

dimostrazione CNF, dimostrazione A equisat A+1 dimostrazione A+1 equisat A

Question 16

refutational methods, resolution principle, proprietà logical calculus

Question 17

completezza,semi decidibilità resolution principle, refutazione, refutational completeness e completeness ,subsumption rule

Question 18

DPP procedure

Answer 18

idea, procedura,terminazione, clausole triviali, correttezza, completezza

Question 19

deduction by resolution, assiomatic calculus