Can anyone tell me (formal), why
not A or (not A and B)is
not A?Best Answer
A or (A and B) == Ais 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 Xis alwaystrue). - 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.
!A || (!A && B) means :if(A = true and B = true) => false (!A)if(A = True and B = false) => false (!A)if(A = false and B = True) => True (!A)if(A = false and B = false) => True (!A)in all cases your expression is !AIt is called the truth table of the inputs of an expression.
If you have a large set of inputs and logic operations, this method is not easy to verify your expression.
what you can do in that case :
proof !A = !A || (!A && B) the same as proving A = !(!A || (!A && B))
!(!A || (!A && B)) = A && !(!A && B) = A && (A || !B) = AThe following is the proof:
A B A and B(AND gate) A or (A and B) OR gate 0 0 0 0 0 1 0 01 0 0 11 1 1 1You can see the value of A is same as the output of A or (A and B) OR gate.