Appunti di ripasso per l'esame di Logica per il corso di Informatica

DEFINIZIONI

Argument: Esso consiste in una sequenza di asserzioni che portano ad una

conclusione supportata da delle premesse. Questo termine può anche indicare gli

elementi contenuti in una atomic wff (es. LeftOf(x,a) – x, a sono arguments).

Sentence: Le atomic sentences sono la combinazione tra nomi e predicati, le

sentences sono formate da atomic sentences e connettivi booleani.

Logical consequence: Una sentence S è una logical consequence se è impossibile per

le premesse essere vere quando la conclusione è falsa.

Logical truth: Una logical truth è una sentence che è logical consequence di un set di

premesse.

Logical validity: Un argument è logicamente valido se la conclusione è una logical

consequence.

Logical equivalence: Due sentences sono logicamente equivalenti se hanno gli stessi

valori di verità in ogni possibile circostanza.

Tautological consequence: Una sentence S è una tautological consequence se in

ogni caso in cui la premessa sia vera, è vera anche la conseguenza.

Taut Con -> Log Con

Tautological equivalence: Due sentences Q e S sono tautologicamente equivalenti

se e solo se la loro joint table assegna gli stessi valori di verità a Q e S.

First Order consequence: Una sentence S è una conseguenza del primo ordine se è

conseguenza delle premesse solo in virtù del connettivi booleani, dell’identità e i

quantificatori. (Sostituzione delle sentence con altre senza senso)

First Order validity: Una sentence S è valida nel primo ordine se è una logical truth

solo in virtù dei connettivi booleani, dell’identità e i quantificatori. 1

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

Universal Elimination

| ∀xP(x)

|..

|..

|P(c) ∀-Elim

“ c ” è una costante che non è stata utilizzata altrove. L’universale ci permette d

introdurre un oggetto che possieda quella proprietà lì, in quanto appunto viene

soddisfatta universalmente.

Universal Introduction

|..

||[c] P(c)

||---------

||..

||..

||Q(c)

|∀x(P(x) → Q(x)) ∀-Intro

Oppure:

|..

||[c]

||--------

||..

||P(c)

|∀x(P(x) ∀-Intro 2

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

Existential Introduction

|S(c)

|..

|∃x S(x) ∃-Intro

Existential Elimination

|∃x S(x)

||[c] S(c)

||------------

||..

||..

||Q

|Q ∃-Elim

Ci sono almeno 2 cubi:

Cube(y) x ≠ y)

∃x∃y(Cube(x) ∧ ∧

Ci sono al massimo 2 cubi:

↔ (z=x z=y))

∃x∃y∀z(Cube(z) ∨ 3

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

FIRST ORDER SET THEORY

Naive Set Theory

Un insieme è una collezione di cose e segue i due assiomi:

Assioma di comprensione:

x a ↔ P(x) ]

∃a∀x[ ∈

Esiste un insieme i cui membri soddisfano la formula P(x)

Assioma di comprensione non ristretta:

x a ↔ P(x) ]

∀z … ∀z ∃a∀x[ ∈

1 n

Assioma di estensionalità:

Un insieme è completamente determinato dai suoi membri

a ↔ x b) → a=b ]

∀a∀b[ ∀x(x ∈ ∈

Se due insiemi hanno gli stessi elementi, allora sono lo stesso insieme.

Teorema dell’unicità

Per ogni wff P(x) possiamo provare che c’è un unico insieme di oggetti che soddisfa

P(x) …∀z x a ↔ P(x) ]

∀z ∃!a ∀x[ ∈

1 n

INSIEME VUOTO

L’insieme vuoto è di per se una contraddizione, ossia nessun oggetto deve

soddisfare P(x)

A = { x | x ≠ x } è l’insieme vuoto 4

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

SINGOLETTO

Se c’è uno e un solo oggetto che soddisfa P(x)

INSIEME SINGOLETTO {x}

Per ogni oggetto x c’è un insieme “singleton”

COPPIE

Se ci sono 2 oggetti che soddisfano P(x)

COPPIE NON ORDINATE (UNORDERED PAIRS)

x y a={x,y}

Per ogni oggetto e c’è un unico insieme

w a ↔ (w=x w=y) ]

∀x∀y∃!a∀w[ ∈ ∨

SOTTOINSIEME

Dati due insiemi a e b, a è un subset di b se ogni membro di a è anche membro di b

a b ↔ a → x b) ]

∀a∀b[ ⊆ ∀x(x ∈ ∈

UNIONE

L’unione di a e b è l’insieme i cui membri appartengono ad a, b o entrambi.

INTERSEZIONE

L’intersezione di a e b è l’insieme i cui membri appartengono sia ad a che b.

COPPIE ORDINATE

x y, <x,y>

Per ogni oggetto e la coppia ordinata è l’insieme

{{x},{x,y}}

Proprietà delle relazioni: [R(x,y) R(y,z) → R(x,z)]

∀x∀y∀z ∧

- Transitività: R(x,x)

∀x

- Riflessività: ¬R(x,x)

∀x

- Irriflessività: → R(y,x)]

∀x∀y[R(x,y)

- Simmetria: → ¬R(y,x)]

∀x∀y[R(x,y)

- Asimmetria: R(y,x)) → x=y]

∀x∀y[(R(x,y) ∧

- Antisimmetria: 5

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

MATHEMATICAL INDUCTION

Viene generalmente utilizzta per provare affermazioni del tipo

P(x) → Q(x) ]

∀x[

Se P(x) è definita tramite INDUCTIVE DEFINITION la dimostrazione per induzione è

più potente della general conditional proof.

Una INDUCTIVE DEFINITION consiste in:

- Una proposizione base che specifica gli elementi essenziali dell’insieme

- Una o più proposizioni induttive che spiegano come generare elementi

addizionali

- Una proposizione finale che dice che tutti gli elementi sono o base o generati

dall’uso di proposizioni induttive.

Es.

Inductive definition dei numeri naturali:

1. 0 è un numero naturale

2. Se n è un numero naturale, allora lo è anche n+1

3. Nulla è un numero naturale se non è ottenuto applicando i passi 1 e 2.

PEANO ARITHMETIC (PA)

Utilizza come simboli: o

E come funzioni: s, +, x

Assiomi dell’aritmetica di Peano:

1. S(x) ≠ 0 )

∀x(

2. S(x)=S(y) → x=y )

∀x∀y(

3. x+0=x )

∀x(

4. x + S(y) = S(x+y) )

∀x∀y(

5. x × 0 = 0)

∀x(

6. x × S(y) = (x × y) + x )

∀x( 6

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

STRONG INDUCTION

Se si può dimostrare che una qualsiasi proprietà vale per tutti i numeri minori di n,

allora vale anche per n e si può quindi concludere che vale per tutti i numeri

naturali. < n → Q(k)) → Q(n)] →

∀n[∀k((k ∀xQ(x)

ADVANCED TIPS IN PROPOSITIONAL LOGIC

Truth Assignments

Ogni funzion h che va dall’insieme delle atomic sentences di una FOL all’insieme

{TRUE, FALSE}.

➔ Data una atomic sentence A, h(A) è vera o falsa.

Tautologia

S è una tautologia se ogni truth assignment h rende S vera ( h(S) = TRUE ).

Tautological Consequence

S è una conseguenza tautologica dell’insieme T di sentences se ogni truth

assignment che rende vere le sentences in T, rende vera anche S.

TT-Satisfiable

S è TT-Satisfiable se esiste un truth assignment h tale che h(S) = TRUE

COMPLETNESS IN PROPOSITIONAL LOGIC

Se la sentence S è conseguenza tautologica dell’insieme T di sentences, allora T

deriva tautologicamente S.

HORN SENTENCES

Sentence in CNF in cui ogni disgiunzione di letterali della sentence contiene al

massimo un letterale positivo.

(A ¬B ¬C) (¬B ¬C) A

∨ ∨ ∧ ∨ ∧

Es. 7

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

Ogni Horn Sentence della Propositional Logic è logicamente equivalente alla

congiunzione di affermazioni condizionali del tipo:

1. (A B C D) → E

∧ ∧ ∧

2. (A B) →

∧ ⊥

3. A

Satisfaction Algorithm for Horn Sentences A …A

Data una Horn Sentence S formata da atomic sentences , per determinare se

1 n

S è TT-Satisfiable è utile usare il seguente algoritmo:

1. Scrivere una tabella in cui si elencano tutte le atomic sentences nella prima

riga seguite da S ¬A

∧ ( ∨ ) ∧

A A A A A A A

1 2 3 4 2 3 1 4

2. Controllare se qualche atomic sentence è congiunto di S. In tal caso scrivere

TRUE sotto tali atomic sentences ¬A

∧ ( ∨ ) ∧

A A A A A A A

1 2 3 4 2 3 1 4

T T TRUE

3. Considerare le sentences in cui abbiamo scritto per riempire la colonna

A FALSE ¬A

di destra. Se abbiamo messo TRUE sotto ad , mettere sotto

3 3

¬A

∧ ( ∨ ) ∧

A A A A A A A

1 2 3 4 2 3 1 4

T T T T

4. A questo punto ci si trova in 2 possibili situazioni:

a. Uno dei congiunti di S è FALSE: in questo caso S è FALSE e non è TT-

Satisfiable

b. Nessuno dei congiunti di S è FALSE: S è TT-Satisfiable e si possono

riempire le colonne rimanenti di atomic sentences con FALSE. Questo

renderà S vera. ¬A

∧ ( ∨ ) ∧

A A A A A A A

1 2 3 4 2 3 1 4

F T F T T T T 8

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

ADVANCED TOPICS IN FOL

FIRST ORDER STRUCTURES

Rappresenta circostanze che determinano i valori di verità di tutte le sentences di un

FOL, rispettando identità è quantificatori

DOMAIN OF DISCOURSE

Insieme D degli oggetti facenti parte della struttura che si vuole rappresentare.

DEFINITION OF FIRST-ORDER STRUCTURE

La funzione M (modello) è definita con i predicati del linguaggio, i nomi del

∀.

linguaggio e il simbolo di quantificazione Nella funzione di first-order structure

sono soddisfatte le seguenti condizioni:

1. M(∀) è un insieme non vuoto D, chiamato “dominio del discorso di M”

2. Se P è un predicato n-ario del linguaggio, allora M(P) è un insieme di n-tupli

<x , x , … , x > di elementi di D. Questo insieme è chiamato ESTENSIONE di P

1 2 n

in M. ∈

L’estensione dell’identità è formata da tutte le coppie <x,x> con x D.

3. Se c è un nome del linguaggio, allora M(c) è un elemento di D ed è chiamato

REFERENTE di c in M.

N.B. Quando si compie l’estensione dei predicati, il significato di questi non viene

considerato (tranne l’identità), vengono considerati invece gli oggetti coinvolti e

l’arità dei predicati.

D = { b , b , b }

1 2 3

M

Cube = { b , b , b }