Logica appunti

 

---

 

Logica appunti

 

Questo sito utilizza cookie, anche di terze parti. Se vuoi saperne di più leggi la nostra Cookie Policy. Scorrendo questa pagina o cliccando qualunque suo elemento acconsenti all’uso dei cookie.I testi seguenti sono di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente a studenti , docenti e agli utenti del web i loro testi per sole finalità illustrative didattiche e scientifiche.

 

 

 

Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).

 

 

 

 

 

Logica appunti

 

Appunti di Logica

 

 

insiemi

 

Insieme :                    collezione di elementi dove è sempre possibile stabilire se un elemento appartiene o meno all’insieme in questione.

 

Sottoinsieme:             all’interno di un insieme, l’insieme stesso e l’insieme vuoto Æ sono i

Improprio                  sottoinsiemi impropri. Se prendo un insieme A, i sottoinsiemi impropri sono: A e Æ.

                                   

Rappresentazione:    I = {1;2;5}     

Tabulare

 

Rappresentazione:    I = {x: (condizione che deve rispettare x affinché appartenga all’insieme)}

Caratteristica

 

Relazione tra:            è un sottoinsieme del prodotto cartesiano A x B

A e B

 

Classe di:                   si scrive come: [a]  dove: a Î I  ed il suo risultato appartiene a R Í IxI.

Equivalenza               Consiste nel sottoinsieme di I costituito dagli elementi x: (a;x) Î R. In pratica: prendi l’insieme a cui appartiene a, fai il prodotto cartesiano; considera tutte le coppie ottenute dal prodotto che hanno come primo membro a.

 

Insieme quoziente:    Viene scritto I/R, dove I è un insieme e R = IxI. Si tratta dell’insieme delle classi di equivalenza degli elementi di I rispetto ad R. Con l’operazione I/R si ottiene una partizione di I in classi d’equivalenza.

 

Ordine totale:            Ogni elemento dell’insieme è confrontabile con tutti gli altri. Se a Î I e b Î I; allora alla relazione d’ordine S definita su I abbiamo (a;b) Î S e/o (b;a) Î S.

 

Ordine parziale:        Non tutte le coppie di elementi sono confrontabili. Esistono 2 elementi a; b nell’insieme I, per cui nella relazione d’ordine S: (a;b)  Ï S e (b;a) Ï S.

 

Insieme delle parti:   Insieme composto da tutti i sottoinsiemi di un insieme, anche quelli impropri. È composto da 2ⁿ elementi, con n cardinalità dell’insieme.

 

Proiezione di S :        sia S una relazione AxB; l’insieme di tutti gli elementi al primo membro delle

 

su A                            coppie generate dalla relazione. Formalmente: U={x: xÎA e (x;b) Î S per almeno un b}

 

Proprietà riflessiva:  ogni elemento dell’insieme è un relazione con sé stesso: a Î I Þ (a;a) Î R

 

 

Proprietà:                  nessun elemento è in relazione con sé stesso: a Î I Þ (a;a) Ï R.

Antiriflessiva

 

Proprietà:                  Se esiste la coppia (a;b), esiste anche la coppia (b;a): a Î I, b Î I, (a;b) Î R 

Simmetrica                Þ (b;a) Î R. 

 

Proprietà:                  Se esiste la coppia (a;b), esiste anche la coppia (b;a): a Î I, b Î I, (a;b) Î R 

Antisimmetrica          Þ (b;a) Ï R. 

 

Proprietà:                  Se esistono (a;b) e (b;c), esiste anche (a,c): (a;b) Î R, (b;c) Î R Þ (a,c) Î R.

Transitiva

 

Chiusura:                  la chiusura di un relazione R è la più piccola relazione transitiva tale che A

Transitiva                  sia contenuta in quest’ultima. Si tratta di prendere A e aggiungere tutte le relazioni che è possibile dedurre tramite la proprietà transitiva. (es. BDD: equivale a calcolare la chiusura di un insieme di attributi).

 

Relazione di               relazione che gode delle proprietà: riflessiva, simmetrica e transitiva.

Equivalenza:

 

Relazione:                  relazione che gode delle proprietà: riflessiva, antisimmetrica e transitiva.

d’ordine

 

Relazione:                  relazione che gode delle proprietà: antiriflessiva, transitiva.

d’ordine stretto

funzioni

 

Funzione:                   è una relazione R contenuta in DxB dove per ogni elemento a Î D esiste uno e un solo elemento b Î B tale che (a;b) Î R. Per ogni elemento del dominio esiste un solo elemento del codominio.

 

Funzione niettiva:     ad ogni elemento del codominio corrisponde un solo elemento del dominio.

 

Funzione:                   per ogni elemento del codominio corrisponde almeno un elemento del

Suriettiva                   dominio.

 

Funzione biiettiva:    è sia iniettiva che suriettiva.

 

Funzione:                   una funzione si dice invertibile se la sua relazione inversa rispetta la

invertibile                   di funzione. In pratica quando la funzione è biiettiva.

 

Funzione identità:     dato un insieme I, è definita la funzione identità su IxI che ad ogni elemento associa sè stesso.

 

Relazione inversa:     si indica con R^-1, consiste nella relazione formata dalle coppie invertite della relazione R. R^-1={(b;a): (a;b) Î R}}

 

 

 

 

 

 

 

Equipotenza:             due insiemi si dicono equipotenti se esiste una funzione biiettiva tra i due. In pratica ciò si ha quando i due insiemi hanno lo stesso numero di elementi.

 

Cardinalità:               Numero di elementi di un insieme, equivale a dire potenza di un insieme.

 

Teorema di:               Per ogni insieme I, il numero di elementi di I è strettamente minore del

Cantor                       numero di elementi compreso nell’insieme delle parti di I. #I < #P(I). (dimostrazione non richiesta)

 

Insieme finito:           Insieme che non è equipotente ad alcun sottoinsieme proprio.

 

Insieme infinito:        Insieme che è equipotente  ad un suo sottoinsieme proprio.

 

Aritmetica di:            è fondata su 3 concetti primitivi e 6 assiomi:

Peano                         a) lo zero;

                                    b) il numero;

                                    c) il successivo;

 

                                    ax0) i numeri formano una classe;

                                    ax1) lo zero è un numero;

                                    ax2) se a è un numero, il successivo a+ è un numero;

ax3) se la classe s contiene lo 0 e per ogni elemento b di s b+ Î s, allora ogni

        numero naturale è in s;

ax4) se a, b sono numeri e  a+, b+ sono numeri uguali, a e b sono uguali;

ax4) se a è un numero, i suo successivo a+ non può essere lo zero;

 

la relazione creata è una funzione f: a ® a+ con dominio N e condominio N\{0}. Peano introduce N in ordine stretto.

 

Massimo comune:     Si calcola rispetto a una coppia (a;b) in un insieme parzialmente ordinato (X,

minorante                  £) e si indica con aÇb, è il piu’ grande elemento che è £ sia di a che di b. aÇb = MinCM se  ( aÇb £ a, aÇb £ b ) e per  ogni c ( c£a, c£b ) troviamo che c £ (aÇb).

                                   

 

Minimo comune:       Si calcola rispetto a una coppia (a;b) in un insieme parzialmente ordinato (X,

maggiorante              £)  e si indica con aÈb, è il più piccolo elemento che è ³ sia di a che di b. aÈb = MaxCM se  ( aÈb ³ a, aÈb ³ b ) e per  ogni c ( c³a, c³b ) troviamo che c ³ (aÈb).

 

Reticolo:                     insieme parzialmente ordinato (X, £, Ç, È) dove per ogni coppia di elementi

                                   Esiste un massimo comune minorante e un massimo comune maggiorante.

 

Reticolo:                    reticolo (X, £, Ç, È) che gode della proprietà distributiva.

Distributivo

 

 

 

Reticolo:                    reticolo (X, £, Ç, È)  che possiede un massimo (max.) e un minimo (min.),  e

Complementato         ogni a ÎX esiste un a’ (detto complemento di a) per cui il massimo comune minorante di (a;a’) = max. e il minimo comune maggiorante di (a;a’) = min.

 

Algebra di Boole:      un reticolo complimentato distributivo. (Un reticolo distributivo, se è anche complimentato è unico).

 

N divisibile:                un numero naturale N è divisibile per un naturale b, se esciste un naturale c tale che a = b*c. b viene detto divisore di a.

 

Numero primo:         un numero naturale p di dice primo se è maggiore di 1 ed è divisibile solo per 1 e per se stesso, altrimenti viene detto composto.

 

Potenza del:               lo è un insieme  equipotente ad N.

Numerabile

 

Potenza del:               lo è un insieme  equipotente ad R.

Continuo

 

 

 

Linguaggio:               oggetto dello studio.

Oggetto

 

Metalinguaggio:        linguaggio nel quale la definizione viene formulata.

 

Enunciato:                 proposizione che assume uno ed un solo valore di verità: vero o falso.

 

Enunciato atomico:   Enunciati costituiti da una sola affermazione (es: “la neve è bianca”).

 

Connettivi:                 collegano più enunciati atomici, tenendo conto solo dei valori di verità degli enunciati stessi. Sono definiti tramite le tavole di verità.

 

Interpretazione:        si dice interpretazione di un enunciato composto una funzione che assegna uno dei valori di verità V o F a ciascun enunciato atomico e quindi quello composto, sulla base delle tavole di verità.

 

Logicamente:             due enunciati si dicono logicamente equivalenti se assumo lo stesso valore di

Equivalenti                verità per ogni interpretazione.

 

Modello:                     interpretazione che assegna il valore di verità ad ogni enunciato.

 

Enunciato:                 se assume il valore di verità V per almeno 1 interpretazione.

Soddisfacibile           

 

Enunciato valido:      se assume il valore di verità V per ogni interpretazione.

(tautologia)

 

Enunciato:                 se non assume il valore di verità V nessuna interpretazione.

Insoddisfacibile        

Enunciato:                 se assume il valore di verità F per almeno 1 interpretazione.

Falsificabile

 

Dimostrazione:          basta prendere le a e le b regole e biforcare in caso di a - regole invece che di

In Gentzen                 b. Se si ottiene con queste un tableau (rovesciato) chiuso si dimostra una tautologia.

 

Sistema di Hilbert:    Formato da 3 assiomi e su una regola di inferenza (modus ponens)

1) |-  A®(B®A)

                                    2) |- [A®(B®C)]®[(A®B)®(A®C)]

                                    3) |- [(ØB)®(ØA)]®(A®B)

                                    modus ponens:           |- A, |- (A®B) Þ |- B

 

Regola di:                  |- (ØB)®(ØA)

Contrapposizione          |- A®B

 

Regola di:                  U |- A®B       U |- B®C

Transitività                            |- A®C

 

Regola di:                  |- (ØB)®(ØA)

Contrapposizione          |- A®B

 

Regola di:                  |- (ØB)®(ØA)

Contrapposizione          |- A®B

 

 

 

Quantificatore:         Simbolo che garantisce l’esistenza di almeno un oggetto tale da verificare la

Esistenziale                proprietà data.

 

Quantificatore:         Simbolo che garantisce Il rispetto della proprietà data da parte di tutti gli

Universale                 oggetti di una considerata totalità.

 

Campo d’azione:       in una formula ("xa), oppure ($xa), a viene detto campo d’azione o  ambito del quantificatore " oppure $.

 

Variabile:                  (detta anche variabile vincolata) variabile che deve sottostare a qualche

Quantificata              condizione, ad esempio in     ("xa), oppure ($xa), x è la variabile vincolata, una variabile non vincolata si dice libera.

 

T. Liberamente:        un termine t si dice liberamente se sostituendolo con tutte le variabili libere

Sostituibile                 di un certo tipo all’interno di una formula, nessuna occorrenza di t risulta vincolata.

 

Complessità:              ogni volta che si trova un connettivo binario si aggiunge + 1 alla complessità.

Logica                        se si ha un quantificatore riferito a una formula b, si aggiunge +1.

 

Termine chiuso:        se si ha un termine tipo ("xa) senza variabili, quel termine si dice chiuso.

 

Conseguenza:            l’enunciato P si dice conseguenza logica di a se P vale per tutti i modelli in

Logica                        cui valgono le formule di a, ciò si esprime scrivendo: a|= P.

 

 

 

Fonte http://twiki.dsi.uniroma1.it/pub/Users/LucaPastorello/AppuntidiLogica.doc

 

Autore del testo: non indicato nel documento di origine

Parola chiave google : Logica appunti tipo file : doc

 

 

 

 

 

Visita la nostra pagina principale

 

Logica appunti

 

Termini d' uso e privacy