Recently on #logic via twitter Pete Lewis asked:-

a || b -> !(!a || !b)) ? #logic makes my brain hurt

I did a quick truth table on paper and said yes but turns out I was wrong as I had looked at the wrong columns. Doh! Here’s the truth table and you can see for yourself

A | B | A || B | !A | !B | (!A || !B) | !(!A || !B) |

FALSE | FALSE | FALSE | TRUE | TRUE | TRUE | FALSE |

FALSE | TRUE | TRUE | TRUE | FALSE | TRUE | FALSE |

TRUE | FALSE | TRUE | FALSE | TRUE | TRUE | FALSE |

TRUE | TRUE | TRUE | FALSE | FALSE | FALSE | TRUE |

The colums A || B and !(!A || !B) are not equivalent.

Advertisements

!x flips everything in x, so && becomes || and x becomes !x.

!(!a || !b) => !(!a) && !(!b) => a && b