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

Messaggioda wattbatt » 14/01/2019, 13: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?
wattbatt
Junior Member
Junior Member
 
Messaggio: 17 di 116
Iscritto il: 20/09/2016, 16:22

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

Messaggioda vict85 » 14/01/2019, 17: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 ) \).
vict85
Moderatore
Moderatore
 
Messaggio: 9460 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

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

Messaggioda wattbatt » 15/01/2019, 16: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
wattbatt
Junior Member
Junior Member
 
Messaggio: 18 di 116
Iscritto il: 20/09/2016, 16:22

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

Messaggioda bub » 18/01/2019, 01: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$
bub
Junior Member
Junior Member
 
Messaggio: 120 di 389
Iscritto il: 29/12/2006, 23:10


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite