|
:<math>x + yz = (x + y)(x + z)\,</math>
''Prenez quelques momentmoments pour réfléchir pourquoi chacune de ces lois peuvent être vraies.''
La dernière loi n'est pas évidente mais nous pouvons démontrer qu'elle est vraie en utilisant les autres lois :
====Simplification====
Une fois que nous avons ces lois, nous voulons simplifier les expressions booléennes comme nous le faisons avec l'algèbre ordinaire. Nous pouvons simplifier l'exemple avec facilité :
Once we have those laws, we will want to simplify Boolean expressiosn just like we do in ordinary algebra. We can all simplify the following example with ease:
:<math>
\begin{matrix}
</math>
La même chose peut être dite à propos de :
the same can be said about:
:<math>
\begin{matrix}
</math>
A partir de ces deux exemples, nous pouvons voir que les expressions qui semblent complexes peuvent être réduites très significativement. Les expressions de la forme ''somme de produit'' ont un intérêt particulier, par exemple :
From those two examples we can see that complex-looking expressions can be reduced very significantly. Of particular interest are expressions of the form of a ''sum-of-product'', for example:
:xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z
WeNous canpouvons factorisefactoriser andet simplify thesimplifier l'expression ascomme followssuit
:<math>
xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z
</math>
C'est un peu plus difficile d'aller plus avant, mais nous le pouvons. Nous utilisons l'identité :
It is only hard to go any further, although we can. We use the identity:
:x + yz = (x + y)(x + z)
''Si l'étape suivante n'est pas claire, essayer de construire des tables de vérité comme une aide à la compréhension.''
''If the next step is unclear, try constructing truth tables as an aid to understanding.''
:<math>
</math>
Et ceci est le plus loin que nous pouvons aller en utilisant l'approche algébrique (ou par tout autre approche). L'approche algébrique pour la simplication est liée au principe d'élimination. Considéront en algebre ordinaire :
And this is as far as we can go using the algebraic approach (or any other approach). The algebraic approach to simplication relies on the priniciple of elimination. Consider, in ordinary algebra:
:x + y - x
WeNous simplifysimplifions bypar rearrangingle theréarrangement de l'expression ascomme followssuit
:(x - x) + y = y
AlthoughBien weque onlynous gofaisons throughseulement thele processprocessus inpar ourla headpensée, thel'idée ideaest isclaire clear: wenous ''bringmettons'' togetherensemble termsles thattermes cancelqui themselvess'annulent outeux-mêmes andet so theainsi, l'expression isest simplifiedsimplifiée.
====Théorèmes de De Morgan====
SoJusque farlà, wenous haven'avons seulement onlytraité dealtque withles expressions inde thela form of aforme ''sumsomme ofde productsproduits'' ec.ga.d. xyz + x'z + y'z'. DeLes Morgan'sthéorèmes theoremsde helpDe usMorgan tonous dealaident withavec anotherun autre type of Boolean d'expressions booléennes. WeNous revisitrevisitons theles ANDtables andde ORvérité truthET et OU tables:
<center><table border="1" cellpadding="2">
<tr>
<th>x</th> <th>y</th> <th>x ×X y</th> <th>x + y</th>
</tr>
<tr>
</table></center>
Vous auriez raison de soupçonner que les deux opérations sont connectées d'une façon ou d'une autre en raison des ressemblances entre les deux tables. En fait, si vous inversez l'opération ET, i.e. vous exécutez l'opération NON sur x ET y. Les sorties des deux opérations sont presque les mêmes :
You would be correct to suspect that the two operations are connected somehow due to the similarities between the two tables. In fact, if you invert the AND operation, i.e. you perform the NOT operations on x AND y. The outputs of the two operations are almost the same:
<center><table border="1" cellpadding="2">
<tr>
<th>x</th> <th>y</th> <th>(x ×X y)'</th> <th>x + y</th>
</tr>
<tr>
</table></center>
TheLa connectionconnexion betweenentre ANDET, OROU andet NOTNON isest revealedrévélée bypar la ''reversingréciprocité'' thede outputla ofsortie x + y byen replacingla itremplaçant withpar x' + y'.
<center><table border="1" cellpadding="2">
<tr>
<th>x</th> <th>y</th> <th>(x ×X y)'</th> <th>x' + y'</th>
</tr>
<tr>
</table></center>
Maintenant, les deux sorties coïncident et ainsi, nous pouvons les égaliser :
Now the two outputs match and so we can equate them:
:(xy)' = x' + y'
ceci est une des lois de De Morgan. L'autre qui peut être dérivée en utilisant un procédé similaire est :
this is one of de Morgan's laws. The other which can be derived using a similar process is:
:(x + y)' = x'y'
Nous pouvons appliquer ces deux lois pour simplifier les équations:
We can apply those two laws to simplify equations:
'''ExampleExemple 1'''<br>
ExpressExprimer ''x'' insous la forme de ''sumsomme ofde productproduit'' form
:<math>
\begin{matrix}
</math>
'''ExampleExemple 2'''<br>
ExpressExprimer ''x'' insous la forme de ''sumsomme ofde productproduit'' form
:<math>
\begin{matrix}
&=& a'b'c'\\
\end{matrix}
</math>ThisCeci pointsindique toune aextension possible extensiondes oflois de De Morgan's laws topour 3 orvariables moreou variablesplus.
'''ExampleExemple 3'''<br>
ExpressExprimer ''x'' insous la forme de ''sumsomme ofde productproduit'' form
:<math>
\begin{matrix}
'''Example 4'''<br>
ExpressExprimer ''x'' insous la forme de ''sumsomme ofde productproduit'' form
:<math>
\begin{matrix}
</math>
AnotherUne thingautre ofchose interestintéressante weque learntnous isavons thatapprise weest canque nous pouvons ''reverserenverser'' the truthla table ofde anyvérité de n'importe quelle expression byen replacingremplaçant eachchacune ofde itsses variables bypar theirson oppositesopposée, i.e. replaceremplacer x bypar x' andet y' bypar y etc. ThisCe resultrésultat shouldn'tne havedevrait beenpas aêtre supriseune at allsurprise, try aessayez fewquelques examplesexemples yourselfvous-mêmes.
'''Lois de De Morgan'''
====Exercice====
# Exprimer sous la forme somme de produit simplifiée :
# Express in simplified sum-of-product form:
## z = ab'c' + ab'c + abc
## z = ab(c + d)
## z = a'c(a'bd)' + a'bc'd' + ab'c
## z = (a' + b)(a + b + d)d'
# ShowMontrer thatque x + yz isest equivalentéquivalent toà (x + y)(x + z)
==Propositions==
WeNous havenous beensommes dealingoccupés withde propositions sincedepuis thele startdébut ofde thisce chapterchapitre, althoughbien weque arenous notn'ayons toldpas theydit areque propositionscela en était. AUne proposition isest simplysimplement aun statementénoncé (orou sentenceune phrase) thatqui isest eithersoit TRUEVRAIE orou FALSEFAUSSE. Hence,Nous wepouvons canutiliser usel'algèbre Booleanbooléenne algebrapour tomanipuler handleles propositions.
ThereIl areexiste two specialdeux types ofspéciaux de propositions -- les tautologytautologies andet contradictionles contradictions. AUne tautologytautologie isest aune proposition thatqui isest alwaystoujours TRUEVRAIE, ec.ga.d. "1 + 1 = 2". AUne contradiction isest thel'opposée opposited'une of a tautologytautologie, itc'est is aune proposition thatqui isest alwaystoujours FALSEFAUSSE, ec.ga.d. "1 + 1 = 3". AsComme usuald'habitude, wenous useutilisons 1 topour representreprésenter TRUEVRAI andet 0 topour representreprésenter FALSEFAUX. PleaseNotez notes'il thatvous plaît que les opinions arene notsont pas des propositions, ec.a.gd. "George W. Bush starteda débuté thela warguerre onen IraqIrak forpour itsson oilpétrole." isest justsimplement anune opinion, itssa truthvéracité orou falsitysa isfausseté notn'est pas universaluniverselle, meaningvoulant somedire thinkque itcertains pensent que c'sest truevrai, some docertains notnon.
'''Exemples'''<br>
"ItIl ispleut raining todayaujourd'hui" isest aune proposition.
"Sydney isest inen AustraliaAustralie" isest aune proposition
"1 + 2 + 3 + 4 + 5 = 16" isest aune proposition
"EarthLa isTerre aest perfectune spheresphère parfaite" isest aune proposition
"HowComment doallez-vous you do?" isn'est ''notpas'' aune proposition - itc'sest aune question.
"GoNettoie cleanta yourchambre room!" isn'est ''notpas'' aune proposition - itc'sest aun commandordre.
"MartiansLes existmartiens existent" isest aune proposition
SincePuisque eachchaque proposition canne onlypeut takeseulement twoprendre valuesque deux valeurs (TRUEVRAI orou FALSEFAUX), wenous canpouvons representreprésenter eachchacune byd'elles par aune ''variable'' andet decidedécider whethersi compoundles propositions arecomposées truesont byvraies usingen Booleanutilisant algebral'algèbre booléenne, justcomme likece weque havenous beenavons doingfait. ForPar exampleexemple "ItIl isfait alwaystoujours hotchaud inen AntarcticaAntarctique OROU 1 + 1 = 2" will besera evaluatedévaluée ascomme truevraie.
===Implications===
PropostitionsLes ofpropostitions thedu type ifsi ''somethingquelque chose'' ''somethingquelque chose'' thenalors ''somethingquelquechose'' ''somethingquelque chose'' aresont calledappelées des implications. TheLa logiclogique ofdes implications areest widelylargement applicable inen mathematicsmathématiques, computerinformatique et dans le sens sciencecommun andgénéral generalde everydaytous commonles sensejours reasoning!
Let'sCommençons startavec withun aexemple simple example
:"'''IfSi''' 1 + 1 = 2 '''thenAlors''' 2 - 1 = 1"
isest anun example ofexemple d'implication, itil simplydit sayssimplement thatque 2 - 1 = 1 isest aune consequenceconséquence ofde 1 + 1 = 2. It'sIl likey a causeun andlien effectde relationshipcause à effet. ConsiderConsidérons cet thisexemple example:
:JohnMarc dit says: "''IfSi'' Ije becomedeviens a millionairemillionnaire, ''thenAlors'' Ije willdonnerai donate $500, 000 to€ à thela RedCroix CrossRouge."
ThereIl arey foura quatre situations :
:#Marc devient millionnaire et donne 500 000 € à la Croix Rouge
:#John becomes a millionaire and donates $500,000 to the Red Cross
:#JohnMarc becomesdevient amillionnaire millionaireet andne doesdonne notpas donate $500, 000 to€ à thela RedCroix CrossRouge
:#Marc ne devient pas millionnaire et donne 500 000 € à la Croix Rouge
:#John does not become a millionaire and donates $500,000 to the Red Cross
:#JohnMarc doesne notdevient becomepas amillionnaire millionaireet andne doesdonne notpas donate $500, 000 to€ à thela RedCroix CrossRouge
Dans lequel des quatre cas Marc ne remplit-il pas sa promesse ? Clairement, si et seulement si la seconde situation se produit. Donc, nous disons que la proposition est FAUSSE si et seulement si Marc devient millionnaire et ne donne pas. Si Marc ne devient pas millionnaire alors il ne se dédit pas, puisque le préalable n'est pas réalisé, par conséquent cela doit être évalué comme VRAI.
In which of the four situations did John NOT fulfill his promise? Clearly, if and only if the second situation occured. So, we say the proposition is FALSE if and only if John becomes a millionaire and does not donate. If John did not become a millionaire then he can't break his promise, because his promise is now claiming nothing, therefore it must be evaluated TRUE.
IfSi ''x'' andet ''y'' aresont twodeux propositions, ''x'' impliesimplique ''y'' (ifsi ''x'' thenalors ''y''), orou symbolicallysymboliquement
:<math>x \Rightarrow y</math>
possède la table de vérité suivante :
has the following truth table:
<table border="1" cellpadding="3">
<tr>
</table>
For emphasis, <math>x \Rightarrow y</math> isest FALSEFAUX ifsi andet onlyseulement ifsi ''x'' isest truevrai andet ''y'' falsefaux. IfSi ''x'' isest FALSEFAUX, itil doesn'y nota matterpas whatde valueproblème sur la valeur prise par ''y'' takes, thela proposition isest automaticallyautomatiquement TRUEVRAIE. OnLes a side note, the twodeux propostions ''x'' andet ''y'' needn'ont notpas havebesoin anythingd'avoir toquelque dochose withà eachvoir otherl'une avec l'autre, ec.a.gd. "1 + 1 = 2 impliesimplique AustraliaL'Australie isest indans thel'hémisphère southern hemisphereSud" evaluatesest évaluée comme toVRAI TRUE!
Si
If
:<math>(x \Rightarrow y) \ \mbox{ANDET} \ (y \Rightarrow x)</math>
alors nous exprimons ceci symboliquement comme
then we express it symbolically as
:<math>x \Leftrightarrow y</math>.
C'est une implication à deux sens qui traduit ''x'' est VRAI si et seulement si ''y'' est vrai. Autrement dit, '''si''' correspond à l'implication <math>(x \Rightarrow y)\,</math>, '''seulement si'' à l'implication <math>(y \Rightarrow x)\,</math>. L'opération ''si et seulement si'' possède la table de vérité suivante :
It is a two way implication which translates to ''x'' is TRUE if and only if ''y'' is true. The ''if and only if'' operation has the following truth table:
<table border="1" cellpadding="3">
<tr>
</table>
Les deux nouvelles opérations que nous avons introduites ne sont pas réellement nouvelles, elles sont simplement des combinaisons de ET, OU et NON. Par exemple :
The two new operations we have introduced are not really new, they are just combinations of AND, OR and NOT. For example:
:<math>x \Rightarrow y = x' + y</math>
''CheckVérifier itceci withavec a truthune table de vérité''. BecauseComme wenous canpouvons expressexprimer thel'opération d'''implication'' operationsen intermes terms ofde ANDET, OROU andet NOTNON, wenous havepouvons opendorénavant themla tomanipuler manipulationavec byl'algèbre Booleanbooléenne algebraet andles loi de Morgan'sDe lawsMorgan.
'''Exemple 1'''<br>
IsLa theproposition followingsuivante propositionest-elle aune tautologytautologie ? (aune proposition that'squi est alwaystoujours truevraie)
:<math>[(x \Rightarrow y)(y \Rightarrow z)] \Rightarrow (x \Rightarrow z)</math>
'''Solution 1'''<br>
:<math>=\ y' + y + x' + z</math>
:<math>=\ 1</math>
Par conséquent, c'est une tautologie.
Therefore it's a tautology.
'''Solution 2'''<br>
A somewhat easierUne solution isplus tofacile drawest up ad'établir truthune table ofde thevérité de la proposition, andet notenoter thatque thela outputcolonne columndes aresorties alln'a 1sque des 1. ThereforePar theconséquent, la proposition isest aune tautologytautologie, becauseparceque thela outputsortie isest 1 regardless ofindépendamment thedes ''inputsentrées'' (i.e. x, y andet z).
'''Exemple 2'''<br>
ShowMontrer thatque thela propostion z isest aune contradiction ( aune proposition thatqui isest alwaystoujours falsefausse) :
:z = xy(x + y)'
\end{matrix}
</math>
ThereforePar itconséquent, c'sest aune contradiction.
BackRevenons toà Examplel'exemple 1, :<math>[(x \Rightarrow y)(y \Rightarrow z)] \Rightarrow (x \Rightarrow z)</math>. ThisCeci isnn'test justpas asimplement slabun ofassemblage symbolsde symboles, youvous shoulddevriez beêtre ablecapable translatede ittraduire intoceci everydayen languagelangage andde understandtous intuitivelyles whyjours it'set comprendre intuitivement pourquoi cela est truevrai.
====Exercices====
# Décider si les propositions suivantes sont vraies ou fausses :
# Decide whether the following propostions are true or false:
## IfSi 1 + 2 = 3, thenalors 2 + 2 = 5
## IfSi 1 + 1 = 3, thenalors fishle can'tpoisson swimne peut pas nager
# ShowMonter thatque thela followingpaire pair ofde propositions aresuivante est equivalentéquivalente
## <math>x \Rightarrow y</math> : <math>y' \Rightarrow x'</math>
| 