Passa al tema normale
Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Quali sono i passaggi sottointesi per trovare questa formula?[logica proposizionale]

14/01/2019, 14:15

Ho un esercizio svolto in cui è richiesto di trovare una formula da questa tavola:

ABCformula
1111
1100
1011
1000
0111
0101
0010
0000


Io di mio solo guardando le somiglianze in tabella ho ricavato la formula $(A^^C)vv(notA^^B)$.
Quello che non capisco è un passaggio della soluzione; c'è scritto:

$(notAvvnotBvvC)^^(notAvvBvvC)^^(AvvBvvnotC)^^(AvvBvvC)-=(notAvvC)^^(AvvnotC)$

La prima è la forma normale congiuntiva e ok, ma il secondo pezzo non riesco a capire come sia stato trovato, se sono rimaneggiamenti della formula con regole varie allora sono stati saltati un pò troppi passaggi credo, per cui mi chiedo a come ci si arriva al secondo pezzo, quale ragionamento è stato fatto; forse solo guardando la tabella? Ma allora perchè mettere la forma congiuntiva?

Re: Quali sono i passaggi sottointesi per trovare questa formula?[logica proposizionale]

14/01/2019, 18:23

Dalla proprietà distributiva della disgiunzione logica con la cogiunzione logica hai che:
\begin{align*}(\neg A \vee C \vee \neg B ) \wedge (\neg A \vee C \vee \neg B ) &\equiv (\neg A \vee C ) \vee ( \neg B \wedge B ) \\ &\equiv (\neg A \vee C ) \end{align*}

Similmente, dalla seconda parte si ricava \( (A \vee B ) \).

Re: Quali sono i passaggi sottointesi per trovare questa formula?[logica proposizionale]

15/01/2019, 17:43

ciao, ho capito come hai usato la distributiva, nella seconda parte evidentemente c'è un errore; mi diresti come è stata fatta questa invece?Anche qui non riesco a trovare passaggi intermedi, mi viene il dubbio che ci sia un errore

$(notAvvnotBvvnotC)^^(notAvvBvvC)^^(AvvnotBvvnotC)^^(AvvBvvnotC)-=
(notBvvnotC)^^(notAvvBvvC)^^(AvvnotC)$

"numerando" le parentesi della cnf vedo che $AvvnotC$ lo posso ricavare dalla 3^ e 4^, mentre $notBvvnotC$ dalla 1^ e 3^ parentesi, come fanno ad esserci scritte entrambi dopo? non riesco ad applicare la distributiva 2 volte sulla terza

Re: Quali sono i passaggi sottointesi per trovare questa formula?[logica proposizionale]

18/01/2019, 02:24

wattbatt ha scritto:ciao, ho capito come hai usato la distributiva, nella seconda parte evidentemente c'è un errore; mi diresti come è stata fatta questa invece?Anche qui non riesco a trovare passaggi intermedi, mi viene il dubbio che ci sia un errore

$(notAvvnotBvvnotC)^^(notAvvBvvC)^^(AvvnotBvvnotC)^^(AvvBvvnotC)-=
(notBvvnotC)^^(notAvvBvvC)^^(AvvnotC)$

"numerando" le parentesi della cnf vedo che $AvvnotC$ lo posso ricavare dalla 3^ e 4^, mentre $notBvvnotC$ dalla 1^ e 3^ parentesi, come fanno ad esserci scritte entrambi dopo? non riesco ad applicare la distributiva 2 volte sulla terza


La $^^$ gode della proprietà di idempotenza (anche la $vv$) cioé

$E -= E ^^ E$

qualsiasi sia l'espressione $E$. In particolare...

$(AvvnotBvvnotC)-=(AvvnotBvvnotC)^^(AvvnotBvvnotC)$

quindi duplicando il terzo congiunto tramite l'idempotenza (sostituzione di formule equivalenti) e poi spostandolo per la proprietà commutativa di $^^$ (commutandolo col secondo congiunto)

$(notAvvnotBvvnotC)^^(notAvvBvvC)^^(AvvnotBvvnotC)^^(AvvBvvnotC) -=$
$(notAvvnotBvvnotC)^^(notAvvBvvC)^^(AvvnotBvvnotC)^^(AvvnotBvvnotC)^^(AvvBvvnotC) -=$
$(notAvvnotBvvnotC)^^(AvvnotBvvnotC)^^(notAvvBvvC)^^(AvvnotBvvnotC)^^(AvvBvvnotC)-=$
$(notBvvnotCvvnotA)^^(notBvvnotCvvA)^^(notAvvBvvC)^^(AvvnotCvvnotB)^^(AvvnotCvvB)-=$
$((notBvvnotC)vv(notA^^A))^^(notAvvBvvC)^^((AvvnotC)vv(notB^^B))-=$
$(notBvvnotC)^^(notAvvBvvC)^^(AvvnotC)$

ottieni i raggruppamenti che ti servono per applicare la proprietà distributiva due volte come volevi fare.
Ma immagino si possa mostrare in più modi che sono equivalenti quelle formule (al limite anche con le tavole di verità), questo diciamo che completa quel che avevi già costruito tu.

La prima equivalenza da te riportata

$(notAvvnotBvvC)^^(notAvvBvvC)^^(AvvBvvnotC)^^(AvvBvvC)-=(notAvvC)^^(AvvnotC)$

è falsa.

Se $A = 0$ e $B = 0$ e $C = 0$ otteniamo

$(not0vvnot0vv0)^^(not0vv0vv0)^^(0vv0vvnot0)^^(0vv0vv0)-=(not0vv0)^^(0vvnot0)$
$(1vv1vv0)^^(1vv0vv0)^^(0vv0vv1)^^(0vv0vv0)-=(1vv0)^^(0vv1)$
$1^^1^^1^^0-=1^^1$
$0-=1$
Rispondi al messaggio