Insiemi e Logica

Gli insiemi

Definizione

Un insieme è una collezione ben definita di oggetti, detti elementi dell'insieme.

Notazione: \[A = \{x \in U : P(x)\}\]

dove U è l'insieme universo e P(x) è la proprietà caratteristica

La rappresentazione di un insieme

Metodi di Rappresentazione

  • Per elencazione: \[A = \{1, 2, 3, 4\}\]
  • Per proprietà caratteristica: \[B = \{x \in \mathbb{N} : x < 5\}\]
  • Mediante diagrammi di Venn

I sottoinsiemi

Definizione

A è sottoinsieme di B se ogni elemento di A appartiene anche a B

\[A \subseteq B \iff \forall x(x \in A \rightarrow x \in B)\]

Sottoinsieme proprio:

\[A \subset B \iff A \subseteq B \land A \neq B\]

Operazioni con gli insiemi

Operazioni Fondamentali

  • Unione: \[A \cup B = \{x : x \in A \lor x \in B\}\]
  • Intersezione: \[A \cap B = \{x : x \in A \land x \in B\}\]
  • Differenza: \[A \setminus B = \{x : x \in A \land x \notin B\}\]
  • Complementare: \[A' = \{x \in U : x \notin A\}\]

Insieme delle parti e partizione di un insieme

Insieme delle Parti

L'insieme di tutti i sottoinsiemi di A si indica con \(\mathcal{P}(A)\)

Se A ha n elementi: \[|\mathcal{P}(A)| = 2^n\]

Partizione

Una partizione di A è una famiglia di sottoinsiemi di A tali che:

  • Sono non vuoti
  • Sono disgiunti a due a due
  • La loro unione è A

Proposizioni logiche

Definizione

Una proposizione è un'affermazione che può essere vera o falsa

Valori di verità:

  • V = vero
  • F = falso

Connettivi logici ed espressioni - Parte 1

Connettivi Fondamentali

  • Negazione (NOT): \[\neg p\]
  • Congiunzione (AND): \[p \land q\]
  • Disgiunzione (OR): \[p \lor q\]

Connettivi logici ed espressioni - Parte 2

Altri Connettivi

  • Implicazione: \[p \rightarrow q\]
  • Doppia implicazione: \[p \leftrightarrow q\]

Connettivi logici ed espressioni - Espressioni logiche

Tavole di Verità

Esempio per \(p \rightarrow q\):

p q \(p \rightarrow q\)
V V V
V F F
F V V
F F V

La logica e gli insiemi

Corrispondenze

  • \(p \land q \leftrightarrow A \cap B\)
  • \(p \lor q \leftrightarrow A \cup B\)
  • \(\neg p \leftrightarrow A'\)

Quantificatori

Quantificatori Universali ed Esistenziali

  • Universale: \[\forall x P(x)\] "per ogni x vale P(x)"
  • Esistenziale: \[\exists x P(x)\] "esiste almeno un x tale che P(x)"

Negazione dei quantificatori:

  • \[\neg(\forall x P(x)) \equiv \exists x \neg P(x)\]
  • \[\neg(\exists x P(x)) \equiv \forall x \neg P(x)\]