Matematica discreta - Logica proposizionale
Le regole della logica matematica specificano i metodi di ragionamento delle affermazioni matematiche. Il filosofo greco, Aristotele, è stato il pioniere del ragionamento logico. Il ragionamento logico fornisce la base teorica per molte aree della matematica e di conseguenza dell'informatica. Ha molte applicazioni pratiche in informatica come la progettazione di macchine informatiche, l'intelligenza artificiale, la definizione di strutture dati per linguaggi di programmazione ecc.
Propositional Logicsi occupa di affermazioni alle quali possono essere assegnati i valori di verità "vero" e "falso". Lo scopo è analizzare queste affermazioni individualmente o in modo composito.
Logica preposizionale - Definizione
Una proposizione è una raccolta di affermazioni dichiarative che ha un valore di verità "vero" o un valore di verità "falso". Una proposizione consiste di variabili proposizionali e connettivi. Indichiamo le variabili proposizionali con lettere maiuscole (A, B, ecc.). I connettivi collegano le variabili proposizionali.
Di seguito vengono forniti alcuni esempi di proposizioni:
- "L'uomo è mortale", restituisce il valore di verità "VERO"
- "12 + 9 = 3 - 2", restituisce il valore di verità "FALSE"
Quanto segue non è una proposta:
"A è minore di 2". È perché, a meno che non diamo un valore specifico di A, non possiamo dire se l'affermazione è vera o falsa.
Connettivi
Nella logica proposizionale generalmente usiamo cinque connettivi che sono:
OPPURE ($ \ lo $)
AND ($ \ land $)
Negazione / NOT ($ \ lnot $)
Implicazione / if-then ($ \ rightarrow $)
Se e solo se ($ \ Leftrightarrow $).
OR ($\lor$) - L'operazione OR di due proposizioni A e B (scritte come $ A \ lo B $) è vera se almeno una qualsiasi delle variabili proposizionali A o B è vera.
La tabella della verità è la seguente:
| UN | B | A ∨ B |
|---|---|---|
| Vero | Vero | Vero |
| Vero | Falso | Vero |
| Falso | Vero | Vero |
| Falso | Falso | Falso |
AND ($\land$) - L'operazione AND di due proposizioni A e B (scritte come $ A \ land B $) è vera se entrambe le variabili proposizionali A e B sono vere.
La tabella della verità è la seguente:
| UN | B | A ∧ B |
|---|---|---|
| Vero | Vero | Vero |
| Vero | Falso | Falso |
| Falso | Vero | Falso |
| Falso | Falso | Falso |
Negation ($\lnot$) - La negazione di una proposizione A (scritta come $ \ lnon A $) è falsa quando A è vera ed è vera quando A è falsa.
La tabella della verità è la seguente:
| UN | ¬ A |
|---|---|
| Vero | Falso |
| Falso | Vero |
Implication / if-then ($\rightarrow$)- Un'implicazione $ A \ rightarrow B $ è la proposizione "se A, allora B". È falso se A è vero e B è falso. Gli altri casi sono veri.
La tabella della verità è la seguente:
| UN | B | A → B |
|---|---|---|
| Vero | Vero | Vero |
| Vero | Falso | Falso |
| Falso | Vero | Vero |
| Falso | Falso | Vero |
If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ è connettivo logico bi-condizionale che è vero quando peq sono uguali, cioè entrambi sono falsi o entrambi sono veri.
La tabella della verità è la seguente:
| UN | B | A ⇔ B |
|---|---|---|
| Vero | Vero | Vero |
| Vero | Falso | Falso |
| Falso | Vero | Falso |
| Falso | Falso | Vero |
Tautologie
Una tautologia è una formula che è sempre vera per ogni valore delle sue variabili proposizionali.
Example - Dimostrare che $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ è una tautologia
La tabella della verità è la seguente:
| UN | B | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| Vero | Vero | Vero | Vero | Vero |
| Vero | Falso | Falso | Falso | Vero |
| Falso | Vero | Vero | Falso | Vero |
| Falso | Falso | Vero | Falso | Vero |
Come possiamo vedere ogni valore di $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ è "True", è una tautologia.
Contraddizioni
Una contraddizione è una formula che è sempre falsa per ogni valore delle sue variabili proposizionali.
Example - Dimostrare che $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ è una contraddizione
La tabella della verità è la seguente:
| UN | B | A ∨ B | ¬ A | ¬ B | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Vero | Vero | Vero | Falso | Falso | Falso | Falso |
| Vero | Falso | Vero | Falso | Vero | Falso | Falso |
| Falso | Vero | Vero | Vero | Falso | Falso | Falso |
| Falso | Falso | Falso | Vero | Vero | Vero | Falso |
Come possiamo vedere ogni valore di $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ è "False", è una contraddizione.
Contingenza
Una contingenza è una formula che ha valori sia veri che falsi per ogni valore delle sue variabili proposizionali.
Example - Dimostra che $ (A \ lor B) \ land (\ lnon A) $ una contingenza
La tabella della verità è la seguente:
| UN | B | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| Vero | Vero | Vero | Falso | Falso |
| Vero | Falso | Vero | Falso | Falso |
| Falso | Vero | Vero | Vero | Vero |
| Falso | Falso | Falso | Vero | Falso |
Come possiamo vedere ogni valore di $ (A \ lo B) \ land (\ lnot A) $ ha sia "Vero" che "Falso", è una contingenza.
Equivalenze proposizionali
Due affermazioni X e Y sono logicamente equivalenti se sussiste una delle due condizioni seguenti:
Le tabelle di verità di ogni affermazione hanno gli stessi valori di verità.
L'affermazione bi-condizionale $ X \ Leftrightarrow Y $ è una tautologia.
Example - Dimostrare che $ \ lnot (A \ lor B) e \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ sono equivalenti
La sperimentazione per 1 ° metodo (tabella di verità di corrispondenza)
| UN | B | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Vero | Vero | Vero | Falso | Falso | Falso | Falso |
| Vero | Falso | Vero | Falso | Falso | Vero | Falso |
| Falso | Vero | Vero | Falso | Vero | Falso | Falso |
| Falso | Falso | Falso | Vero | Vero | Vero | Vero |
Qui, possiamo vedere i valori di verità di $ \ lnot (A \ lo B) e \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ sono gli stessi, quindi le affermazioni sono equivalenti.
Test con il 2 ° metodo (Bi-condizionalità)
| UN | B | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| Vero | Vero | Falso | Falso | Vero |
| Vero | Falso | Falso | Falso | Vero |
| Falso | Vero | Falso | Falso | Vero |
| Falso | Falso | Vero | Vero | Vero |
Poiché $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ è una tautologia, le affermazioni sono equivalenti.
Inverse, Converse e Contra-positive
Implicazione / if-then $ (\ rightarrow) $ è anche chiamata dichiarazione condizionale. Ha due parti:
- Ipotesi, p
- Conclusione, q
Come accennato in precedenza, è indicato come $ p \ rightarrow q $.
Example of Conditional Statement- "Se fai i compiti, non sarai punito." Qui, "fai i compiti" è l'ipotesi, p, e "non sarai punito" è la conclusione, q.
Inverse- Un inverso dell'affermazione condizionale è la negazione sia dell'ipotesi che della conclusione. Se l'affermazione è "Se p, allora q", l'inverso sarà "Se non p, allora non q". Quindi l'inverso di $ p \ rightarrow q $ è $ \ lnot p \ rightarrow \ lnot q $.
Example - L'inverso di "Se fai i compiti, non sarai punito" è "Se non fai i compiti, sarai punito".
Converse- Il contrario dell'istruzione condizionale viene calcolato scambiando l'ipotesi e la conclusione. Se l'affermazione è "Se p, allora q", il contrario sarà "Se q, allora p". Il contrario di $ p \ rightarrow q $ è $ q \ rightarrow p $.
Example - Il contrario di "Se fai i compiti, non sarai punito" è "Se non sarai punito, fai i compiti".
Contra-positive- Il contro-positivo del condizionale si calcola scambiando l'ipotesi e la conclusione dell'enunciato inverso. Se l'affermazione è "Se p, allora q", il contro-positivo sarà "Se non q, allora non p". Il contro-positivo di $ p \ rightarrow q $ è $ \ lnot q \ rightarrow \ lnot p $.
Example - Il contro-positivo di "Se fai i compiti, non sarai punito" è "Se sei punito, non hai fatto i compiti".
Principio di dualità
Il principio di dualità afferma che per ogni affermazione vera, è vera anche l'affermazione duale ottenuta scambiando le unioni in intersezioni (e viceversa) e scambiando l'insieme universale in un insieme Null (e viceversa). Se il duale di qualsiasi affermazione è l'affermazione stessa, si diceself-dual dichiarazione.
Example - Il duale di $ (A \ cap B) \ cup C $ è $ (A \ cup B) \ cap C $
Forme normali
Possiamo convertire qualsiasi proposizione in due forme normali:
- Forma normale congiuntiva
- Forma normale disgiuntiva
Forma normale congiuntiva
Un'istruzione composta è in forma normale congiuntiva se si ottiene operando AND tra variabili (negazione delle variabili inclusa) connesse con OR. In termini di operazioni sugli insiemi, è un'istruzione composta ottenuta per intersezione tra variabili connesse con le unioni.
Examples
$ (A \ lor B) \ land (A \ lo C) \ land (B \ lo C \ lo D) $
$ (P \ cup Q) \ cap (Q \ cup R) $
Forma normale disgiuntiva
Un'istruzione composta è in forma normale disgiuntiva se è ottenuta operando OR tra variabili (negazione delle variabili inclusa) connesse con AND. In termini di operazioni sugli insiemi, è un'istruzione composta ottenuta dall'unione tra variabili legate alle intersezioni.
Examples
$ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $
$ (P \ cap Q) \ cup (Q \ cap R) $