Pagina 1 di 1

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

MessaggioInviato: 14/01/2019, 13:15
da wattbatt
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]

MessaggioInviato: 14/01/2019, 17:23
da vict85
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]

MessaggioInviato: 15/01/2019, 16:43
da wattbatt
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]

MessaggioInviato: 18/01/2019, 01:24
da bub
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$