Logique propositionnelle : pourquoi "pas A ou (pas A et B) = pas A" ?

Question

Quelqu'un peut-il me dire (formel), pourquoi

not A or (not A and B)

est

not A?

Answer 1

!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)

dans tous les cas, votre expression est !A On appelle cela la table de vérité des entrées d'une expression.

Si vous avez un grand nombre d'entrées et d'opérations logiques, cette méthode n'est pas facile pour vérifier votre expression.

ce que vous pouvez faire dans ce cas :

preuve !A = !A || (!A && B) la même chose que de prouver A = !(!A || (!A && B))

!(!A || (!A && B)) = A && !(!A && B) = A && (A || !B) = A

Answer 2

A or (A and B) == A

est toujours une tautologie (où A peut ici être remplacé par "pas A" ou toute autre expression booléenne, de même pour B).

Il n'est pas nécessaire de considérer toute la table de vérité comme l'ont fait les autres, il suffit de considérer les valeurs de A lui-même (c'est-à-dire seulement deux cas) et d'appliquer les règles de la logique booléenne pour simplifier :

• si A est vrai, alors on a : true or (true and B) ce qui est trivialement vrai (par définition de ou - true or X est toujours true ).
• si A est faux, alors nous avons false or (false and B) == (false and B) == false (par définition, ou ( false or X == X ) et ou ( false and X == false )).

Selon vos goûts personnels, il peut être plus intuitif de rappeler que ou se rapporte à UNION en théorie des ensembles, et que "et" se rapporte à INTERSECTION. Dans ce cas, c'est clair. Une UNION (A INTERSECTION B) est égale à A, car (A INTERSECTION B) est un sous-ensemble strict de A.