Riepilogo di Metodi Matematici per Informatica

Metodi matematici per l'informatica

05/10/2015 – 16/01/2016

Riepilogo

Definizione di sintassi e semantica in una proposizione

La sintassi è la forma in cui è scritta una proposizione, mentre la semantica indica il contenuto.

Proposizione e predicato

La proposizione logica è una frase di senso compiuto che contiene un'affermazione che può essere VERA (1) o FALSA (0).

Il predicato logico è una frase che contiene un'affermazione relativa ad alcune variabili e che diventa una proposizione quando a queste variabili assegniamo dei valori che rendono V o F la proposizione stessa.

Operatori logici

Gli operatori logici sono AND, OR, XOR, NOT, implicazione ed equivalenza (¬, ∨, ⊻, ⇒, ⇔, ∧). Si indicano rispettivamente con:

• AND = ipotesi e tesi devono essere vere per rendere vero il predicato, altrimenti il predicato sarà falso.
• OR = ipotesi o tesi o entrambe devono essere vere per rendere vero il predicato.
• XOR = o l'ipotesi o la tesi devono essere vere; se sono entrambe vere o entrambe false, il predicato è falso.
• NOT = rende P vero se è falso e viceversa.
• Implicazione (⇒) = l'ipotesi implica la tesi (P Q) e se P=0 e Q=1 allora il predicato sarà vero; se P=1 e Q=0, il predicato sarà falso. Se entrambe sono 0 oppure sono 1, allora il predicato sarà vero.
• Equivalenza (⇔) = se P implica Q e viceversa, allora si ha un'equivalenza tra P e Q e si scrive ⇔P Q. Se P=0 e Q=0 oppure P=1 e Q=1, il predicato sarà vero; se una delle due è falsa, allora il predicato sarà falso.

Formule ben formate

Le formule ben formate sono le formule corrette sia dal punto di vista sintattico che semantico.

Quantificatori universali ed esistenziali

I quantificatori universali indicano che quell'oggetto, o numero, appartiene a quell'insieme (universo).

Esempio: M = insieme MONDO, tutti gli animali appartengono all'insieme M ∀ e scriveremo x ∈ M.

Il quantificatore esistenziale indica che esiste un valore che appartiene a quell'insieme. ∀ ∃

Esempio: x ∈ M x|x=cane (si legge per ogni x appartenente ad M esiste una x tale che x è un cane).

Dimostrazioni

Diretta o logico-deduttiva

In questo caso bisogna verificare che, dopo aver posto vera l'ipotesi, anche la tesi sia vera. (Es. ipotesi x<9 e la tesi è x+3<12. Se a x sostituiamo qualunque valore <9 otterremo che anche x+3<12 sempre).

Per assurdo

In questo caso dobbiamo lasciare vera l'ipotesi e negare la tesi e quindi arrivare ad una contraddizione. Es. P = x<9 e Q = x+3 ≥ 12, quindi se a x assegniamo un qualunque valore <9 nella P, la Q verrà per esempio (con x=7) 7+3≥12 [contraddizione]

Per contrapposizione

Dobbiamo negare la tesi e l'ipotesi e la negazione della tesi diventa l'ipotesi e la negazione dell'ipotesi diventa la tesi. Es. P = x ≥ 9 e Q = x+3 ≥ 12 diventano P = x+3 ≥ 12 e Q = x ≥ 9. Se poniamo per esempio x=10 diventa 10+3≥12 e 10≥9, P e Q sono vere.

Forma esplicita di un insieme

A = {1,2,3,...,n}