Pourquoi ?

22

Je voudrais savoir s'il existe une règle pour le prouver. Par exemple, si j'utilise la loi distributive, je n'obtiendrai que .(AA)(A¬B)

user78333
la source
2
Bienvenue en informatique! Qu'as-tu essayé? Où êtes-vous resté coincé? Nous ne voulons pas simplement vous remettre la solution; nous voulons que vous gagniez en compréhension. Cependant, comme nous ne savons pas quel est votre problème sous-jacent, nous ne pouvons donc pas commencer à vous aider. Voir ici pour des conseils sur la façon de poser des questions sur les problèmes d'exercice. Si vous ne savez pas comment améliorer votre question, pourquoi ne pas demander autour de Computer Science Chat ?
Raphael
Un être vrai est nécessaire dans les deux conditions et il suffit pour celui de gauche.
Millie Smith

Réponses:

55

Je trouve que les images sont parfaites pour tout ce qui est assez simple pour les utiliser, ce qui est le cas.

Diagramme rendu

Rappelles toi:

ET signifie la zone occupée par les deux choses. Donc, celui du milieu est ce qui est repris à l'extérieur de B, mais aussi à l'intérieur de A. Leur jonction n'est pas comptée car elle est à l'intérieur de A mais pas à l'extérieur de B.

OU signifie qu'il est couvert par l'un ou les deux. Les deux couvrent la partie de A qui est en dehors de B, et la jonction est couverte par A (première image) donc elle est également comptée. Dans l'ensemble, vous avez à nouveau un A.

Désolé si c'est trop simpliste, je ne sais pas à quel niveau vous êtes.

Erin
la source
Pour être complet, il pourrait être bon de montrer le cas où B et A sont disjoints et un autre cas où B est A.
Eric Duminil
11
@EricDuminil Je ne suis pas d'accord. La grande chose à propos de ce travail de diagramme de Venn est qu'il est valide que les régions soient vides ou non.
Mark S.
3
+1 à la réponse de Mark S. La chose à propos des diagrammes de Venn, et la raison pour laquelle ils sont encore (j'espère!) Enseignés dans les classes de mathématiques du collège, c'est qu'ils fonctionnent réellement . Si vous (Eric) vous demandez "mais que se passe-t-il si B et A sont disjoints? ..." alors vous n'avez pas encore compris ce que représente réellement un diagramme de Venn. Il représente les quatre possibilités logiques sous la forme de quatre régions géométriques: (A&B) [le coin central], (A & ~ B) [croissant gauche], (~ A & B) [croissant droit] et (~ A & ~ B) [le reste de la page]. Les colorier comme Erin nous aide à visualiser un problème logique comme un problème géométrique .
Quuxplusone
@EricDuminil (destiné à tous ceux qui liront ceci à l'avenir) s'ils sont disjoints, celui du milieu sera juste A (aucune partie de A à l'intérieur de B) donc vous avez A ou A = A, et si A = B, le milieu sera vide (aucune partie de A n'est en dehors de B), vous aurez donc A ou rien = A
Erin
1
@djechlin: J'étais fatigué. Si A est B, vous pouvez ignorer les parties gauche et droite.
Eric Duminil
48

Il y a plusieurs façons de voir cela. L'un est une table de vérité. Une autre consiste à utiliser la règle de répartition:

A(A¬B)=(A)(A¬B)=A(¬B)=A=A.
Yuval Filmus
la source
Dans la deuxième étape, ce signe égal ne devrait-il pas signifier une relation d'équivalence?
KumarAnkit
J'utilise = dans son sens habituel, comme dans 2 + 2 = 4.
Yuval Filmus
ok, pouvez-vous expliquer la transition de la deuxième étape à la troisième étape?
KumarAnkit
9

J'utiliserais ma règle d'inférence la moins préférée: l' élimination des disjonctions . Fondamentalement, il dit que si découle de et découle de , alors doit être vrai si :P R Q R P Q ( P R ) , ( Q R ) , ( P Q ) RRPRQRPQ

(PR),(QR),(PQ)R

Supposons donc . Définissez , , et appliquez la règle:P = AA(A¬B)P=AR = AQ=A¬BR=A

  • Si ( ), nous avons terminé.= AP=A
  • Si alors (par élimination de conjonction, )A S T SQ=A¬BASTS
  • Par élimination de disjonction .A(A¬B)A

L'inverse est trivial: supposons , puis par l'une des variantes d'introduction de conjonction ( pour tout ) .S S T T A A ( )ASSTTAA()

Voici un schéma de cette preuve:

Preuve rendue

CompuChip
la source
4
Je suis désolé, comment avez-vous dessiné ce diagramme? Je sens la plus faible odeur de Coq.
Tobia Tesan
1
@TobiaTesan C'est moi qui ai "dessiné" le diagramme. Pour ce faire, j'ai utilisé un logiciel appelé slate .
Sriotchilism O'Zaic
1
@EpsilonNeighborhoodWatch: merci beaucoup. Excusez-moi d'avoir abusé de votre patience, mais est-ce que ce logiciel peut être obtenu de quelque façon que ce soit? Le lien sur l'en-tête (www.cogsci.rpi.edu/slate) semble mort
Tobia Tesan
@TobiaTesan Visio de Microsoft peut également être utilisé pour dessiner des diagrammes de ce genre. Si vous êtes affilié à une université ou à une grande entreprise qui propose des logiciels Microsoft aux étudiants / employés, ou si vous avez un abonnement MSDN, vous pouvez y avoir déjà un accès payant.
Nat
@Nat Sure (ou vous pouvez le faire et le faire dans TikZ: P), mais j'avais l'impression que la chose utilisée par EpsilonNeighborhoodWatch avait des fonctionnalités d'assistant de preuve, d'où mon intérêt :) FWIW Proof General peut faire quelque chose comme ça, mais la visualisation de l'arbre de preuve est beaucoup plus laide.
Tobia Tesan
5

Notez que, quand on sait que implique , nous avons . Ceci est analogue à la prise de l'union d'un ensemble (correspondant à ) et d'un de ses sous-ensembles ( ): on récupère le plus grand ensemble ( ).D C D = D D C DCDCD=DDCD

Dans votre cas, et , et l'implication est triviale.D = AC=A¬BD=A

chi
la source
3

Un look plus intuitif:

Aest toujours vrai quand Aest vrai.

A & -Bn'est vrai que quand Aest vrai.

Intuitivement, appliquer OR à ces deux éléments produirait un résultat Cqui est toujours vrai quand il Aest vrai. En tant que tel, Cc'est toujours vrai quand Ac'est vrai.

(Arrêtez de lire ici si cette explication vous convient.)

Voilà comment je pense à ce problème. Cependant, cette explication n'est pas complète puisque tout ce que nous avons montré est cela A -> Cet non A <-> C.

Alors, montrons aussi cela C -> A.

Aest toujours faux quand Aest faux.

A & -Best toujours faux quand Aest faux.

Intuitivement, appliquer OR à ces deux éléments produirait un résultat Cqui est toujours faux quand il Aest faux. En tant que tel, Cest toujours faux quand Aest faux; -A -> -C, ce qui est la même chose que C -> A.

Donc A -> Cet C -> Aainsi A <-> C.

Quelklef
la source
3

Parfois, les gens sont déroutés par les lettres. Les gens aiment la nourriture, car il est facile d'y penser.

Imaginez que je vous demande de lancer une pièce pour choisir entre l'une ou l'autre des deux options suivantes:

  • Une pomme, OU ...
  • Une pomme, et certainement pas de banane.

[Le premier est égal à "A", le second "A et non B". Mais ne pensez pas aux lettres. Pensez à la pomme, et si vous obtenez également une banane.]

Ce premier signifie vraiment "une pomme de fersure, et peut-être vous obtiendrez une banane."

Donc, laisser quelque chose de côté revient à dire "peut-être".

En les regardant comme une paire, peu importe ce que vous obtenez, il y aura certainement une pomme impliquée. Yay. Et si votre coinflip choisit le bon, vous pourriez obtenir une banane.

Mais n'est-ce pas la même chose que de dire "peut-être que vous obtiendrez une banane"? Juste avec la moitié de la probabilité?

Donc, tout ce que vous pouvez certainement dire, c'est que vous obtiendrez un Apple. Vous ne pouvez pas dire si vous obtiendrez une banane.

Dewi Morgan
la source
3

Similaire à la réponse de Yuval Filmus. Utilisation de l'algèbre booléenne, dans la notation technique, et factorisation (ou factorisation) de A.

A+AB¯=A(1+B¯)=A1=A

Onur
la source
3

Il semble que personne ne l'ait encore mentionné, je vais donc continuer.

La loi pour traiter ces types de problèmes est la loi d'absorption qui stipule que pv (p ^ q) = p et aussi que p ^ (pvq) = p. Si vous essayez d'utiliser la loi distributive à ce sujet, cela vous fera tourner en rond pour toujours:

(A v A) ^ (A v ~ B) = A ^ (A v ~ B) = (A ^ A) v (A ^ ~ B) = A v (A ^ ~ B) = (A v A) ^ (A v ~ B)

J'ai utilisé le mauvais symbole pour non et égal mais le point ici est que lorsque vous faites des cercles / quand il y a un décalage et-ou généralement vous devriez regarder la loi d'absoprtion.

B n'est pas pertinent pour le résultat, comme vous le remarquerez si vous le mettez dans une table de vérité.

Arthur
la source
Cela va bien avec la réponse aux pommes et aux bananes
Erin
1
@Erin +1 De plus, il fournit une règle, alors que la réponse pomme et banane ne faisait appel qu'à l'intuition, et l'OP demandait une règle, pas l'intuition.
Rosie F
2

Une autre façon intuitive de voir cela:

Si A est un ensemble, alors nous pouvons dire que tout objet donné est (en A) ou (pas en A).

Regardez maintenant S = A ou (A et non B) :

  • Si un objet est en A, alors "A ou n'importe quoi" contient tous les éléments en A, donc l'objet sera également en S.

  • Si un objet n'est pas dans A, alors "A et n'importe quoi" exclut tous les éléments qui ne sont pas dans A, donc l'objet n'est ni dans A ni dans (A et pas B), donc ce n'est pas dans S.

Donc, le résultat est que tout objet dans A est dans S, et tout objet qui n'est pas dans A n'est pas dans S. Donc, intuitivement, les objets dans S doivent être exactement ceux de A, et pas d'autres objets.

Lorsque deux ensembles ont des éléments identiques, ils sont définis comme étant le même ensemble. Alors A = S.

Stilez
la source
2

Une méthode simple que vous pouvez toujours utiliser si vous êtes coincé est l'analyse de cas.

A

A

A

John Doe le Juste
la source
0
lets consider: 
  1) A as 1 and B as 0. 
  2) A as 0 and B as 1. 
  3) A as 1 and B as 1.
  4) A as 0 and B as 0.

using the first scenario : A or (A and !B) => 1 or ( 1 and 1) => 1 0r 1 => 1
using the second scenario: A or (A and !B) => 0 or ( 0 and 0) => 0 or 0 => 0
using the third scenario : A or (A and !B) => 1 or ( 1 and 0) => 1 or 0 => 1
using the fourth scenario: A or (A and !B) => 0 or ( 0 and 1) => 0 or 0 => 0

From the above four cases, the result always depends on A not on B, so the result is A.
prudhvi seeramreddi
la source