Regole di inferenza

Le regole di inferenza sono uno schema formale di regole ( o formule ) che consente di giungere a una conclusione ( proposizione finale ) a partire da un numero finito di proposizioni iniziali. Le regole di inferenza logica consentono a un algoritmo di evitare l'esplosione combinatoria di tutte le ipotesi di un problema ( es. model checking ) e di giungere alla medesima conclusione tramite il ragionamento logico. Le regole formali prescindono dal contenuto vero e proprio delle proposizioni, si limitano a rispettare la forma logica ( struttura sintattica ) dei vai enunciati. Le principali regole di inferenza sono le seguenti.

• Modus ponens. Il modus ponens ( modo che afferma ) è la regola di inferenza più nota. Date due proposizioni A e B e una formula A⇒B, se la proposizione A è vera allora anche la proposizione B è vera. Ad esempio, se ho fame ( A ) mangio ( B ). Ho fame ( la proposizione A è vera ), dunque mangio ( conclusione ).
• Eliminazione della congiunzione AND. L'eliminazione degli operatori AND è un'altra regola di inferenza. Se è vera una congiunzione, allora sono vere anche le singole proposizioni congiunte. Ad esempio, se la congiunzione ( A ∧ B ) è vera, allora anche la proposizione A è vera.
• Eliminazione del bicondizionale. L'eliminazione del bicondizionale è un'equivalenza logica. Date due proposizioni logiche A e B, se A implica B e B implica A è possibile sostituire il bicondizionale ( A ⇔ B ) con una doppia implicazione ( A ⇒ B ) ∧ ( B ⇒ A ).
  
• Eliminazione dell'implicazione. Date due proposizioni A e B e una formula A⇒B, in base alla quale A implica B, è possibile eliminare l'implicazione (⇒) sostituendola con una espressione logica. Possiamo, infatti, dire che l'espressione logica (¬A ∨ B ) è sempre vera. Se la proposizione A è falsa ( ¬A ) allora la proposizione B non può essere vera. Le due proposizioni logiche sono alternative. È quindi possibile sostituire l'implicazione con un'espressione logica in cui la negazione di A ( ¬A ) e B sono associate tra loro tramite il connettivo logico OR ( ∨ ).
  
• Eliminazione della doppia negazione. L'eliminazione della doppia negazione appartiene alle equivalenze logiche più semplici. Data una proposizione A, la negazione della negazione della proposizione A, equivale alla proposizione A stessa. Ad esempio, se A è vera, la sua negazione ¬A è falsa. La negazione della negazione ¬( ¬A ) è, quindi, vera ed è uguale alla proposizione A. Possiamo quindi scrivere l'equivalenza nel seguente modo:
  
• Regola logica della contrapposizione. La regola della contrapposizione è una equivalenza logica. Date due proposizioni A e B e una regola A⇒B in cui la proposizione A implica la proposizione B, è possibile affermare che la negazione di B implica la negazione di A, ossia ¬B⇒¬A.
  
• Teoremi di De Morgan ( o leggi di De Morgan ). Il teorema di De Morgan è un'equivalenza della logica booleana. Secondo un teorema di De Morgan il complementare dell'unione degli insiemi A e B e' uguale a l'intersezione degli insiemi complementari. Considerando A e B due proposizioni logiche, è quindi possibile scrivere nel seguente modo.
  
  Il teorema di De Morgan è duale. È quindi possibile affermare che il complementare dell'intersezione degli insiemi A e B e' uguale all'unione degli insiemi complementari. Considerando A e B due proposizioni logiche, è quindi possibile scrivere nel seguente modo.
  
• Distributività. Date tre proposizioni logiche ( A, B, C ) è sempre possibile dimostrare la distributività dell'intersezione rispetto all'unione.
  
  Allo stesso modo, è sempre possibile dimostrare la distributività dell'unione rispetto all'intersezione. Le seguenti espressioni logiche sono equivalenti.
  
• Associatività. Date tre proposizioni logiche ( A, B, C ) è sempre possibile dimostrare l'associatività dell'intersezione. Le seguenti espressioni logiche sono equivalenti.
  
  Allo stesso modo, è sempre possibile dimostrare l'associatività dell'unione. Le seguenti espressioni logiche sono equivalenti.
  
• Commutatività. Date due proposizioni logiche ( A, B ) è sempre possibile dimostrare la commutatività dell'intersezione delle proposizioni. Le due espressioni logiche sono equivalenti.
  
  Allo stesso modo è possibile dimostrare la commutatività dell'unione delle proposizioni logiche. Le due espressioni logiche sono equivalenti.
  

Regola di inferenza corretta. Una regola di inferenza è corretta ( regola valida o regola logica ) quando la conclusione finale è una conseguenza logica delle proposizioni iniziali ( premesse ). Se tutte le premesse sono vere, allora anche la conclusione è vera. Le regole di inferenza trasmettono il medesimo grado di verità dalle premesse alla conclusione. Quando la regola di inferenza non rispetta la conseguenza logica è detta regola scorretta o regola non valida.