Logica delle proposizioni

Prima di parlare di insiemi serve un linguaggio per dire vero o falso. Le proposizioni, combinate con i connettivi logici e lette attraverso le tavole di verità, sono i mattoni di ogni dimostrazione. Vedremo le equivalenze fondamentali (fra cui le leggi di De Morgan), il modo di negare i quantificatori e il parallelo che rende la logica e l’algebra degli insiemi due facce dello stesso oggetto.

• Le proposizioni
• I connettivi logici
• Tavola di verità dei connettivi
• L’implicazione materiale
• La disgiunzione esclusiva (aut)
• Equivalenze logiche e leggi di De Morgan
• Verifica di un’equivalenza con la tavola di verità
• Quantificatori e loro negazione
• Parallelo tra logica e insiemi

Before talking about sets we need a language for saying true or false. Propositions, combined with the logical connectives and read through truth tables, are the building blocks of every proof. We shall see the fundamental equivalences (among them De Morgan’s laws), how to negate the quantifiers and the parallel that makes logic and the algebra of sets two faces of the same object.

• Propositions
• Logical connectives
• Truth table of the connectives
• Material implication
• Exclusive disjunction (aut)
• Logical equivalences and De Morgan’s laws
• Checking an equivalence with the truth table
• Quantifiers and their negation
• Parallel between logic and sets

Prima di parlare di insiemi serve un linguaggio per dire vero o falso. Le proposizioni sono i mattoni di ogni dimostrazione: saperle combinare con i connettivi e leggerne la tavola di verità è il prerequisito di tutta l’algebra (le operazioni tra insiemi rispecchiano la logica), di tutta la geometria (“se… allora…”) e di tutto lo studio di funzione (”$f$ continua e derivabile…”).

Definizione — Proposizione

Una proposizione è un’asserzione di cui si può dire, senza ambiguità, se è vera (V, oppure $1$) o falsa (F, oppure $0$).

“Roma è in Italia” è una proposizione (vera); “Il numero $7$ è bello” non lo è, perché non se ne può stabilire con certezza il valore di verità.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Proposizione

Before talking about sets we need a language for saying true or false. Propositions are the building blocks of every proof: knowing how to combine them with connectives and how to read their truth table is the prerequisite for all of algebra (the operations between sets mirror logic), for all of geometry (“if… then…”) and for the whole study of functions (”$f$ continuous and differentiable…”).

Definition — Proposition

A proposition is an assertion for which one can say, without ambiguity, whether it is true (T, or $1$) or false (F, or $0$).

“Rome is in Italy” is a proposition (true); “The number $7$ is beautiful” is not, because its truth value cannot be established with certainty.

Links

Topics: Set theory
Concepts: Proposition

A partire da una o più proposizioni ne possiamo costruire di nuove usando i connettivi logici. I cinque connettivi fondamentali, con il loro simbolo e il modo di leggerli, sono i seguenti.

Ogni connettivo trasforma i valori di verità delle proposizioni di partenza in un nuovo valore di verità: il modo sistematico per descriverlo è la tavola di verità.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Congiunzione · Connettivi logici · Disgiunzione · Doppia implicazione · Implicazione · Negazione

Starting from one or more propositions we can build new ones using the logical connectives. The five fundamental connectives, with their symbol and how to read them, are the following.

Each connective transforms the truth values of the starting propositions into a new truth value: the systematic way to describe this is the truth table.

Links

Topics: Set theory
Concepts: Conjunction · Logical connectives · Disjunction · Double implication · Implication · Negation

La tavola di verità elenca tutte le combinazioni possibili dei valori di verità delle proposizioni di partenza e, per ciascuna, il valore del connettivo. Con due proposizioni $p$ e $q$ i casi da esaminare sono quattro.

Proprietà — Tavola di verità dei connettivi

p & q & \lnot p & p\land q & p\lor q & p\Rightarrow q & p\Leftrightarrow q \\ \hline V & V & F & V & V & V & V \\ V & F & F & F & V & F & F \\ F & V & V & F & V & V & F \\ F & F & V & F & F & V & V \end{array}$$

Osserviamo le regole essenziali: la congiunzione è vera solo quando lo sono entrambe; la disgiunzione è falsa solo quando lo sono entrambe; la doppia implicazione è vera quando $p$ e $q$ hanno lo stesso valore di verità.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Connettivi logici · Tavola di verita
Competenze: Ragionare per casi

The truth table lists all the possible combinations of the truth values of the starting propositions and, for each, the value of the connective. With two propositions $p$ and $q$ there are four cases to examine.

Property — Truth table of the connectives

p & q & \lnot p & p\land q & p\lor q & p\Rightarrow q & p\Leftrightarrow q \\ \hline V & V & F & V & V & V & V \\ V & F & F & F & V & F & F \\ F & V & V & F & V & V & F \\ F & F & V & F & F & V & V \end{array}$$

We observe the essential rules: the conjunction is true only when both are; the disjunction is false only when both are; the double implication is true when $p$ and $q$ have the same truth value.

Links

Topics: Set theory
Concepts: Logical connectives · Truth table
Skills: Reasoning by cases

L’implicazione $p\Rightarrow q$ è il connettivo che all’inizio sorprende di più, perché il suo comportamento nei casi in cui l’ipotesi è falsa non corrisponde all’intuizione del linguaggio comune.

Osservazione — L'implicazione è strana solo all'inizio

La riga curiosa della tavola di verità è la terza: se l’ipotesi è falsa, l’implicazione è vera. “Se piove allora prendo l’ombrello” resta vera anche nei giorni in cui non piove: in quei giorni la promessa non viene messa alla prova.

L’implicazione è falsa solo quando $p$ è vera ma $q$ è falsa: è l’unico caso in cui mi si può “cogliere in fallo”.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Implicazione

The implication $p\Rightarrow q$ is the connective that surprises the most at first, because its behaviour in the cases where the hypothesis is false does not match the intuition of everyday language.

Remark — The implication is strange only at first

The curious row of the truth table is the third: if the hypothesis is false, the implication is true. “If it rains then I take my umbrella” remains true even on the days when it does not rain: on those days the promise is not put to the test.

The implication is false only when $p$ is true but $q$ is false: it is the only case in which I can be “caught out”.

Links

Topics: Set theory
Concepts: Implication

Accanto al “vel” latino (l’OR inclusivo, che ammette anche il caso di entrambe vere) esiste un secondo “o”: l‘“aut”, che esclude il caso in cui entrambe siano vere.

Esempio — "Aut" esclusivo (XOR)

La disgiunzione esclusiva, ”$p$ oppure $q$ ma non entrambi”, si denota $p\veebar q$ e ha la seguente tavola: $(V,V)\to F,\quad (V,F)\to V,\quad (F,V)\to V,\quad (F,F)\to F.$ È l‘“aut” del latino, contrapposto al “vel”. Lo ritroveremo, sotto forma di insieme, nella differenza simmetrica $A\triangle B$.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Disgiunzione · Disgiunzione esclusiva

Alongside the Latin “vel” (the inclusive OR, which also admits the case of both being true) there exists a second “or”: the “aut”, which excludes the case in which both are true.

Example — Exclusive "aut" (XOR)

The exclusive disjunction, ”$p$ or $q$ but not both”, is denoted $p\veebar q$ and has the following table: $(V,V)\to F,\quad (V,F)\to V,\quad (F,V)\to V,\quad (F,F)\to F.$ It is the Latin “aut”, contrasted with “vel”. We shall meet it again, in the form of a set, in the symmetric difference $A\triangle B$.

Links

Topics: Set theory
Concepts: Disjunction · Exclusive disjunction

Due formule sono equivalenti ($\equiv$) se hanno la stessa tavola di verità: in ogni riga assumono lo stesso valore. Le equivalenze permettono di riscrivere una condizione complicata in una più semplice, senza cambiarne il significato.

Proprietà — Equivalenze logiche fondamentali

• Doppia negazione: $\lnot(\lnot p)\equiv p$.
• Leggi di De Morgan: $\lnot(p\land q)\equiv \lnot p\lor\lnot q$ e $\lnot(p\lor q)\equiv \lnot p\land\lnot q$.
• Implicazione come “or”: $p\Rightarrow q\equiv \lnot p\lor q$.
• Contrapposizione: $p\Rightarrow q\equiv \lnot q\Rightarrow\lnot p$ (alla base delle dimostrazioni per assurdo).
• Doppia implicazione: $p\Leftrightarrow q\equiv (p\Rightarrow q)\land(q\Rightarrow p)$.

Le leggi di De Morgan dicono che negare una congiunzione equivale a fare la disgiunzione delle negazioni, e viceversa: la negazione “scambia” $\land$ e $\lor$. Le ritroveremo, identiche, come leggi che scambiano intersezione e unione tra gli insiemi.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Contrapposizione · Equivalenza logica · Leggi di de morgan
Competenze: Dimostrare
Persone: Augustus De Morgan

Two formulae are equivalent ($\equiv$) if they have the same truth table: in every row they take the same value. Equivalences allow a complicated condition to be rewritten as a simpler one, without changing its meaning.

Property — Fundamental logical equivalences

• Double negation: $\lnot(\lnot p)\equiv p$.
• De Morgan’s laws: $\lnot(p\land q)\equiv \lnot p\lor\lnot q$ and $\lnot(p\lor q)\equiv \lnot p\land\lnot q$.
• Implication as an “or”: $p\Rightarrow q\equiv \lnot p\lor q$.
• Contraposition: $p\Rightarrow q\equiv \lnot q\Rightarrow\lnot p$ (the basis of proofs by contradiction).
• Double implication: $p\Leftrightarrow q\equiv (p\Rightarrow q)\land(q\Rightarrow p)$.

De Morgan’s laws say that negating a conjunction is equivalent to taking the disjunction of the negations, and vice versa: negation “swaps” $\land$ and $\lor$. We shall meet them again, identical, as laws that swap intersection and union between sets.

Links

Topics: Set theory
Concepts: Contraposition · Logical equivalence · De Morgan’s laws
Skills: Proving
People: Augustus De Morgan

Per stabilire se due formule sono equivalenti basta costruire le rispettive colonne nella tavola di verità e confrontarle riga per riga: se coincidono ovunque, le formule sono equivalenti.

Esempio — Verifica con la tavola di verità

Dimostriamo che $p\Rightarrow q\equiv\lnot p\lor q$ confrontando le colonne:

p & q & p\Rightarrow q & \lnot p\lor q \\ \hline V & V & V & V \\ V & F & F & F \\ F & V & V & V \\ F & F & V & V \end{array}$$ Le due colonne coincidono in tutte le righe: dunque le due formule sono equivalenti.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Equivalenza logica · Tavola di verita
Competenze: Dimostrare · Ragionare per casi

To establish whether two formulae are equivalent it is enough to build the respective columns in the truth table and compare them row by row: if they coincide everywhere, the formulae are equivalent.

Example — Checking with the truth table

Let us prove that $p\Rightarrow q\equiv\lnot p\lor q$ by comparing the columns:

p & q & p\Rightarrow q & \lnot p\lor q \\ \hline V & V & V & V \\ V & F & F & F \\ F & V & V & V \\ F & F & V & V \end{array}$$ The two columns coincide in all the rows: hence the two formulae are equivalent.

Links

Topics: Set theory
Concepts: Logical equivalence · Truth table
Skills: Proving · Reasoning by cases

Osservazione — Insight linguistico

Nelle dimostrazioni i quantificatori universale $\forall$ (“per ogni”) ed esistenziale $\exists$ (“esiste almeno uno”) si negano scambiandosi di posto, mentre la proposizione interna viene negata: $\lnot(\forall x\,P(x))\equiv \exists x\,\lnot P(x), \qquad \lnot(\exists x\,P(x))\equiv \forall x\,\lnot P(x).$ Esempio: la negazione di “ogni mattina prendo il caffè” non è “nessuna mattina prendo il caffè”, ma “esiste una mattina in cui non prendo il caffè” (Esty, cap. 3).

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Quantificatori

Remark — Linguistic insight

In proofs the universal quantifier $\forall$ (“for all”) and the existential quantifier $\exists$ (“there exists at least one”) are negated by swapping places, while the inner proposition is negated: $\lnot(\forall x\,P(x))\equiv \exists x\,\lnot P(x), \qquad \lnot(\exists x\,P(x))\equiv \forall x\,\lnot P(x).$ Example: the negation of “every morning I have a coffee” is not “no morning I have a coffee”, but “there exists a morning on which I do not have a coffee” (Esty, ch. 3).

Links

Topics: Set theory
Concepts: Quantifiers

In sintesi — Parallelo logica ↔ insiemi

La logica delle proposizioni e l’algebra degli insiemi sono lo stesso oggetto, scritto con due notazioni diverse:

Logica	Insiemi	Diagramma di Venn
$\lnot p$	complementare $\overline{A}$	esterno del cerchio
$p\land q$	intersezione $A\cap B$	sovrapposizione
$p\lor q$	unione $A\cup B$	somma dei cerchi
$p\veebar q$	differenza simmetrica $A\triangle B$	“a mezzaluna”
$p\Rightarrow q$	inclusione $A\subseteq B$	$A$ tutto dentro $B$
$V$ (sempre vero)	universo $U$	rettangolo intero
$F$ (sempre falso)	vuoto $\emptyset$	nulla

Questo dizionario è la chiave di lettura di tutto il capitolo: ogni proprietà logica ha un gemello insiemistico e viceversa.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Connettivi logici · Diagramma di venn
Persone: John Venn

In summary — Parallel logic ↔ sets

Propositional logic and the algebra of sets are the same object, written with two different notations:

Logic	Sets	Venn diagram
$\lnot p$	complement $\overline{A}$	outside of the circle
$p\land q$	intersection $A\cap B$	overlap
$p\lor q$	union $A\cup B$	sum of the circles
$p\veebar q$	symmetric difference $A\triangle B$	“crescent-shaped”
$p\Rightarrow q$	inclusion $A\subseteq B$	$A$ entirely inside $B$
$V$ (always true)	universe $U$	the whole rectangle
$F$ (always false)	empty set $\emptyset$	nothing

This dictionary is the key to reading the whole chapter: every logical property has a set-theoretic twin and vice versa.

Links

Topics: Set theory
Concepts: Logical connectives · Venn diagram
People: John Venn