Search code examples
logic

Propositional logic: why is "not A or (not A and B) = not A"

Can anyone tell me (formal), why

not A or (not A and B)

is

not A?
Solution 
  • A or (A and B) == A

    is always a tautology (where A here can be replaced by "not A" or any other boolean expression, similarly for B).

    You don't need to consider the whole truth table as the others have done, just consider the values of A itself (i.e., just two cases) and apply the rules of Boolean logic to simplify:

    • if A is true, then we have: true or (true and B) which is trivially true (by definition of or - true or X is always true).
    • if A is false, then we have false or (false and B) == (false and B) == false (by definition of or (false or X == X) and or (false and X == false)).

    Depending on your personal taste, it might be more intuitive to recall that or relates to UNION in set theory, and "and" relates to INTERSECTION. In this case, clearly. A UNION (A INTERSECTION B) is equal to A, as (A INTERSECTION B) is a strict subset of A.