Logica, appunti e esercizi

LOGICA

LOGICA

Argomenti principali:

1. Logica proposizionale:
   • Sintassi
   • Semantica
   • Teoria della dimostrazione
2. Logica del primo ordine
   • Sintassi
   • Semantica: modelli e soddisfacibilità
   • Traduzione dal linguaggio normale a quello di primo ordine

Libreria sotto LOGICA appunti + materiale on-line AU-UL

Affermiamo matematiche → TEOREMI

Sotto data ipotesi (o asserzioni) vale una tesi (o conclusione)

↗ DIMOSTRAZIONE

→ verifica che la tesi di un teorema valga, ammettendo che ipotesi valgano

→ Gerarchia termini logici

Esempio: Affermazione:

• n è un n. naturale dispari.
• → vera con n=3
• → falsa con n=8

Dimostrazione:

1. diretta
2. non diretta
3. per trasposizione
4. (per) ^{(n+1) composizione}

◁ Proposizione

Teorema

Corollario

Equivalenza

• Siano P e Q tali che
  • Se P allora Q
  • Se Q allora P

In questo caso c'è equivalenza, perché sostanzialmente l'uno può "informarsi" dell'altro.

Nozione di conseguenza

• Riflessiva: Qualunque sia P: P ha come conseguenza P
• Transitiva: Se P ha come conseguenza Q e Q ha come conseguenza R, P ha come conseguenza R (controllare che sia giusto)

Nozione di equivalenza

• Riflessiva: P è equivalente a P
• Transitiva: Se P è equivalente a Q e Q è equivalente a R, P è equivalente a R
• Simmetrica: Se P è equivalente a Q, allora Q è equivalente a P

Esempio: Definiamo su numeri interi xRy se e solo se x - y è pari

Esercizio: Dimostrare che R è riflessiva, transitiva e simmetrica

Se P ≡ R e Q ≡ S allora P ∧ Q ≡ R ∧ S

in fatti, assumo che P ≡ R e Q ≡ S, se vale P ∧ Q allora

valgono P e Q, conseguentemente valgono R e S e

quindi R ∧ S:

P ∧ Q ∈ R ∧ S

R ∧ S ∉ P ∧ Q

e quindi

P ∧ Q ≡ R ∧ S

La DISGIUNZIONE

P ∨ Q è vera se e solo se almeno una tra P, Q è vera

es. ( x pari → P ) e un quadrato perfetto → Q

è vera in certi casi e falsa in altri

P ∨ Q → nel es. con x = 4, x = 16 è vera con x = 9 è vera

Proprietà della Disgiunzione:

• P ∨ Q = Q ∨ P → proprietà commutativa
• (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) → proprietà associativa
  • perché nel caso (P ∧ Q) ∨ R ≠ P ∧ (Q ∨ R) - parentesi cambiano
  • P ∧ Q → R → non servono parentesi perché lega più strettamente l'AND tra P ∧ Q rispetto a ∧∧
• P ⊢ E P ∨ Q → se P è vera consegue P ∨ Q V
• Q ⊢ E P ∨ Q → se Q è vera consegue P ∨ Q
• P ∨ Q, ¬P ⊢ E Q → se è falsa conseguo che Q n è vera per tre
• P ∨ Q, ¬Q ⊢ E P → se Q è falsa consegue che P ma vero per quattro
• se P ≡ R e Q ≡ S allora P ∨ Q ≡ R ∨ S
  • in fatti, se P ≡ R e Q ≡ S n vale P ∨ Q allora vale che almeno uno è vero. Se vale P allora vale R o quindi vale R ∨ S, se vale Q allora vale S ∧ quindi R ∨ S

P₁, P₂, ..., P_n ⊨ Q

se e solo se

P₁ ∧ P₂ ∧ ... ∧ P_n ⊨ Q

se e solo se

F= P₁ ∧ P₂ ∧ ... ∧ P_m → Q

TERMINOLOGIA

• se P allora Q
• P è (sufficiente) sufficiente per Q
• Q è (condizione) necessaria per P

↳ se Q non vale non può valere nemmeno P

↶ infatti, P → Q vuol dire che se vale P deve valere anche Q e viceversa

Asserire un'implicazione

P → Q

non significa ottenere una relazione di causa/effetto

ad es.

• ∈ Q → gli studenti sono belli

L'⇐ è vera perché non devono necessariamente esser legati

L'implicazione non è commutativa

P → Q ≠ Q → P

se P è vera e Q è falsa l'implicazione è falsa, mentre se Q è falsa e P è vera l'implicazione vera

L'implicazione non è associativa

• (P → Q) → R ≠ (P → (Q → R); ad esempio, se P o R sono T
• P → Q è vera quindi (P → Q) → R è falsa, invece
• P → T (Q → R) è vera perché infatti (Q → R) sono FALSE

P(x, y, z, ...) → definisco le variabili, o soggetti

(in modo tale da non fare confusione)

∃y ∀x x+y=0 ⊢

⊩ c'è un y tale che qualsiasi x prenda mi dà come gli opposti

in ℕ è falso

in ℤ è falso

∀y ∀x P ⊩ ∀x ∀y P

P(x, y): x è invitato a cena da y

∀x ∃y P: ognuno ha qualcuno che lo invita a cena

∃y ∀x P: c'è qualcuno che invita tutti a cena

Non è la stessa cosa scrivere prima o dopo i quantificatori.

Però sono uno la conseguenza dell'altro

∃y ∀x P ⊢ ∀x ∃y P

quindi:

∀x ∃y P ⊬ ∃y ∀x P

solo nel caso in cui sono identici i quantificatori:

∃x ∃y P ≡ ∃y ∃x P

∀x ∀y P ≡ ∀y ∀x P

affermazione che parla di x e y

affermazione che parla solo di x

x + y = 0 →: P(x, y) ⊢ ?

∃y P(x, y) ⟹ ∃y ∀x x+y=0 →: Q(x) "esiste l'opposto di y"

∀x Q(x): ∀x ∃y P(x, y) → ∀x ∃y x+y=0 →: R

Tavola di verità di P₁:

P₁ : (B → A) ∧ ((B ∨ C) ↔ A)

stermini atomici

A B C B → A B ∨ C (B ∨ C) ↔ A P

• 0 0 0 1 0 1 0
• 0 0 1 1 1 0 0
• 0 1 0 1 1 1 1
• 0 1 1 1 1 1 1
• 1 0 0 0 0 0 0
• 1 0 1 0 1 0 0
• 1 1 0 1 1 1 1
• 1 1 1 1 1 1 1

1° colonna | 3° posizione: 8

2° formula inversa: B è falsa o A è vera

3°: U non è vera e tutte e due false, tutte e due vere

L'argomento è molto differente.

P: A ∧ (B → ¬A)

A B ¬A B → ¬A A ∧ (B → ¬A)

• 0 0 1 1 0
• 0 1 1 0 0
• 1 0 0 1 0
• 1 1 0 0 0

Tavole di verità e conseguenza logica

P₁, P₂, ..., P_n |= Q

(k) X ho usato una serie di formule

(Z) per costruire questa, il dom... anche Q è vera.

Significa che X non è vera, P₁, P₂, ..., P_N allora anche Q è vera.

P₁ non è vera seconda ai valori delle formule atomiche che la compongono.

Come faccio a parlare di una tavola di ver...

Legge di Peirce

(¬((A → B) → A) → A

A, B ⊢ A → B, (A → B) → A (A ↔ B) → A

A ∨ B, C ⊢ (A ∨ B) ↔ C

si può calcolare

• A
• B
• C

[ A ∨ B ]

¬A ↔ ¬B ⊢ la bicondizionale è una tautologia

A ∧ B ≡ ¬(A ∧ B) → A ∧ B ≡ ¬A ∨ ¬B

Esempio: Se P è una formula atomica

Se |A(P)| = 3 ht(P) = 0

Se

P:=(¬(A)∧((B)→(¬A))))

allora |h(P)|=1 e ht(P)=?

G(A, ¬(B)) ⊂ Prop_(L)

(¬(A)) ∈ Prop_(L)

((B)→(¬(A))) ∈ Prop₂(L)

((¬(A))∧((B)→(¬(A)))) ∈ Prop₃(L)

-------------

ESEMPI

Siano A, B ∈ L:

• A ∧ B ∉ prop(L) perché non è una formula
• ¬A ∈ prop(L)
• ((A)→(B))  è una formula in prop_(L) ; (A), (B) ∈ prop_(L)
• ((¬(A)→(B)))) è una formula di prop_(L)
• (AB) non è una formula perché mancano i connettivi

ALB SRI.

ad ogni formula è associato un albero di costruzione.

È un insieme non vuoto. I dettati sono su un ordine parziale, ovvero che dato un nodo quelli prima sono in ordine.

non tutti -> non vanno d.l.

Gli -> quelli h: sono detti nodi

il nodo minimo in due radici dell’albero.

Se ∀x ∈ T : ∃y ∈ T⎬y ∈ x⎬

se x è un predecessore di y. o che y è un successore h:x più esterno immediato ? o meno