命题演算、集合论和布尔代数之间的关系是什么？
命题逻辑中的连接词∧（连接）与集合论中的∩（交集）本质上是相同的，如果我们认为“假”是“非成员”，“真”是“成员”。德摩根定律、交换定律、幂等定律适用于其中的三种。真值表存在于命题逻辑和布尔代数中——隶属表存在于集合论中。为什么？
是不是因为这些系统中的变量是二进制的（真或假，在集合中而不是在集合中，0-1），并且在给定定义运算符的情况下，只有两个可能值的变量之间的关系是相同的，而不管这两个选择是什么？
如果我在命题逻辑中证明了一个表达式，那么它对应的布尔表达式也同样成立吗？卡诺图对简化逻辑表达式也有效吗？
这些系统是否共享公理？
答案是响亮的“是”！它们都是同一事物的影子，那就是“它们都是”布尔代数。
更清楚一点：如果你有一个集合X，那么幂集P（X）（所有子集的集合）是一个布尔代数，其中∧由。然后你可以检查最基本的规则，或者布尔代数的公理。从某种意义上说，这是“必须手工完成的”，但这几乎是微不足道的。一旦你做到了这一点，任何你能从布尔代数公理中证明的公式都适用于集合X的子集，即隶属关系。
类似地，如果你有一组命题变量，看看基于这些变量的命题公式集Frm，那么它不是一个布尔代数，但它几乎是一个布尔代数。事实上，如果你用关系φ～ψφ与ψ相等，那么所有的∧，∨，∨都传递给商，然后你就得到了布尔代数。再说一次，你只需要检查公理。
如何做到这一点取决于你所说的“等价”是什么意思（在语法上等价，即有φ的正式证明）ψ、或者在语义上等价，也就是说，对V的任何解释，φ和ψ的结果都是一样的-结果证明“等价”的这两个意思是等价的[不是双关语]，但这是一个定理，如果你不知道，那么根据你的定义，证明会有所不同），但不管怎样，它都会起作用。因此，你能从布尔代数公理中证明的任何公式，都必须（达到等价）适用于公式。
这两个结果被称为“稳健性”。
然而，你的问题实际上是反方向的，问“如果我能证明命题逻辑中的某些东西，那么它是否适用于布尔表达式？”；我把布尔表达式解释为“它是否适用于所有布尔代数？”（事实证明，这和要求有语法证据是一样的）。现在这个问题在某种程度上是健全性的“反面”：你要求的是完整性。但幸运的是，这些语义是完整的！
这是什么意思？这里还有两件事，所以有两个定理：
如果p=q形式的定律仅能用∩，∪，（-）c表示，则当你用∧转换它时，它适用于所有的动力装置p（X）∩,∨∪,（）c，它适用于所有布尔代数，因此也适用于“布尔表达式”。
如果你能证明两个命题公式φ和ψ是等价的，那么它们在布尔表达式中的明显转换就可以用布尔公理来证明是相等的（这与说它对所有布尔代数都成立一样）
还有更好的（或更糟的，取决于你的观点）：如果你有两个布尔表达式p（x1，…，xn），q（x1，…xn），那么它们可以从布尔代数公理中证明相等当且仅当所有赋值xi0或1，它们给出相同的结果：这是证明使用真值表的结果，因为要检查两个表达式是否相同，只要对0,1的每个赋值进行检查就足够了。
我将更进一步，并注意到这一切都取决于使用经典逻辑，特别是排除中间法则，即x∨x始终成立。如果你去掉这个定律，你就进入了直觉逻辑的领域，我刚才说的很多东西都失效了：你可以通过改变一些东西来挽救一些部分，但是你完全失去了使用真值表的能力。
Whatistherelationshipbetweenpropositionalcalculus,settheory,andBooleanalgebra
Theconnective∧(conjunction)inpropositionallogicisessentiallythesameas∩(intersection)insettheoryifonethinksof'false'as'notamember'and'true'as'amember'.DeMorgan'slaws,commutativelaws,idempotentlaws,etcapplyinthreeofthem.TruthtablesexistinbothpropositionallogicandBooleanalgebra--membershiptablesexistinsettheory.Why
Isitbecausethevariablesinthesesystemsarebinary(true-false,intheset-notintheset,0-1)andtherelationshipbetweenvariablesthathaveonlytwopossiblevaluesgiventhedefinedoperatorsisthesameregardlessofwhatthetwochoicesare
IfIprovesomethingaboutanexpressioninpropositionallogic,isitvalidtoconcludethatthesameholdsforitscorrespondingBooleanexpressionIsKarnaughmapvalidforsimplifyinglogicalexpressionstoo
Dothesesystemsshareaxioms
Theanswerisaresounding"yes"!They'reallshadowsofthesamething,whichisthat"they'reall"booleanalgebras.
Tomakeitclearer:ifyouhaveasetX,thenthepowersetP(X)(setofallsubsets)isabooleanalgebrawith∧givenby∩,∨givenby∪,givenby()c(complementinX).Thenyoucancheckthemostbasicrules,oraxiomsofbooleanalgebras.Thisyou"havetodobyhand"inasense,butit'sprettymuchtrivial.Onceyouhavedonethis,anyformulayoucanprovefromtheaxiomsofbooleanalgebrasholdsforsubsetsofasetX,thatis,forthemembershiprelation.
Similarly,ifyouhaveasetVofpropositionalvariablesandlookatthesetFrmofpropositionalformulasbasedonthesevariables,thenit'snotquiteabooleanalgebra,butit'salmostone.Indeed,ifyouquotientitbytherelationφ～ψφisequivalenttoψ,thenalltheoperations∧,∨,passtothequotient,andthenyoudogetabooleanalgebra.Again,youonlyhavetochecktheaxioms.
Howyoudothatwilldependonwhatyoumeanbyequivalent(syntacticallyequivalent,i.e.thereisaformalproofofφψ;orsemanticallyequivalent,i.e.anyinterpretationofVgivesthesameresultforφandψ-itturnsoutthatthesetwomeaningsof"equivalent"areequivalent[nopunintended],butit'satheorem,andifyoudon'tknowit,thendependingonyourdefinitiontheproofswilllookdifferent),butitwillworknomatterwhat.Thereforeagain,anyformulayoucanprovefromtheaxiomsofbooleanalgebraswillnecessarilyhold(uptoequivalence)forformulas.
Thesetworesultsarecalled"soundness".
Howeveryourquestionactuallygoesinthereversedirectionandasks"ifIcanprovesomethinginpropositionallogic,doesitthenholdforbooleanexpressions";Iinterpretbooleanexpressionstomean"doesitthenholdforallbooleanalgebras"(itturnsoutthatthisisthesameasaskingthatthereisasyntacticalproofofit).Nowthisquestionissomehowthe"converse"ofsoundness:you'reaskingforcompleteness.Butluckyyou,itturnsoutthatthesesemanticsarecomplete!
WhatdoesthismeanWellagaintherearetwothingsathandhere,sotwotheorems:
Ifalawoftheformp=qexpressibleonlywith∩,∪,()choldsforallpowersetsP(X),thenwhenyoutranslateitwith∧∩,∨∪,()c,itholdsforallbooleanalgebrasandthereforeholdsfor"booleanexpressions".
Ifyoucanprovethattwopropositionalformulasφandψareequivalent,thentheirobvioustranslationinbooleanexpressionscanbeprovedtobeequalusingthebooleanaxioms(whichisthesameastosayitholdsforallbooleanalgebras)
Thereisevenbetter(orworse,dependingonyourpointofview):ifyouhavetwobooleanexpressionsp(x1,...,xn),q(x1,...xn),thentheycanbeprovedequalfromthebooleanalgebraaxiomsifandonlyifforallassignmentsxi0or1,theygivethesameresult:thisistheresultthatjustifiestheuseoftruthtables,becausetocheckthattwoexpressionsarethesameitsufficestocheckitagainsteveryassignmentto0,1.
I'llgoabitfurtherandnotethatthisalldependscruciallyonusingclassicallogicandsospecificallythelawofexcludedmiddle,thatstatesthatx∨xalwaysholds.Ifyouremovethatlaw,youentertherealmofintuitionisticlogic,andalotofwhatIjustsaidbreaksdown:youcansalvagesomepartsbychangingsomestuff,butyoucompletelylosetheabilitytousetruthtablesforinstance.