mùlù jí “ luó ji dài shù ” (645 yè )。 fā xiàn zhě hé fā xiàn guò chéng booleanalgebra
yīng guó shù xué jiā g. bù 'ěr wèile yán jiū sī wéi guī lǜ （ luó ji xué 、 shù lǐ luó ji ) yú 1847 hé 1854 nián tí chū de shù xué mó xíng 。 cǐ hòu r. dài dé jīn bǎ tā zuò wéi yī zhǒng tè shū de gé 。 suǒ wèi yī gè bù 'ěr dài shù ， shì zhǐ yī gè yòu xù de sì yuán zǔ 〈 b， ∨ ， ∧ ， * 〉 ， qí zhōng b shì yī gè fēi kōng de jí hé ，∨ yǔ ∧ shì dìng yì zài b shàng de liǎng gè 'èr yuán yùn suàn ， * shì dìng yì zài b shàng de yī gè yī yuán yùn suàn ， bìng qiě tā men mǎn zú yī dìng de tiáo jiàn 。
bù 'ěr dài shù yóu yú quē fá wù lǐ bèi jǐng ， suǒ yǐ yán jiū huǎn màn ， dào liǎo 20 shì jì 30 ～ 40 nián dài cái yòu yòu liǎo xīn de jìn zhǎn ， dà yuē zài 1935 nián ， m.h. sī tōng shǒu xiān zhǐ chū bù 'ěr dài shù yǔ huán zhī jiān yòu míng què de lián xì ， tā hái dé dào liǎo xiàn zài suǒ wèi de sī tōng biǎo shì dìng lǐ ： rèn yì yī gè bù 'ěr dài shù yī dìng tóng gòu yú mǒu gè jí shàng de yī gè jí yù ； rèn yì yī gè bù 'ěr dài shù yě yī dìng tóng gòu yú mǒu gè tuò pū kōng jiān de bì kāi dài shù děng ， zhè shǐ bù 'ěr dài shù zài lǐ lùn shàng yòu liǎo yī dìng de fā zhǎn 。 bù 'ěr dài shù zài dài shù xué （ dài shù jié gòu ）、 luó ji yǎn suàn 、 jí hé lùn 、 tuò pū kōng jiān lǐ lùn 、 cèduó lùn 、 gàilǜ lùn 、 fàn hán fēn xī děng shù xué fēn zhī zhōng jūn yòu yìng yòng ； 1967 nián hòu ， zài shù lǐ luó ji de fēn zhī zhī yī de gōng lǐ huà jí hé lùn yǐ jí mó xíng lùn de lǐ lùn yán jiū zhōng yě qǐ zhe yī dìng de zuò yòng 。 jìn jǐ shí nián lái ， bù 'ěr dài shù zài zì dòng huà jì shù 、 diàn zǐ jì suàn jī de luó ji shè jì děng gōng chéng jì shù lǐng yù zhōng yòu zhòng yào de yìng yòng 。
nián ， 20 suì de qiáo zhì · bù 'ěr kāi bàn liǎo yī suǒ sī rén shòu kè xué xiào 。 wèile gěi xué shēng men kāi shè bì yào de shù xué kè chéng ， tā xīng qù nóng hòu dì dú qǐ liǎo dāng shí yī xiē jiè shào shù xué zhī shí de jiào kē shū 。 bù jiǔ ， tā jiù gǎn dào jīng yà ， zhè xiē dōng xī jiù shì shù xué má ？ shí zài lìng rén nán yǐ zhì xìn 。 yú shì ， zhè wèi zhǐ shòu guò chū bù shù xué xùn liàn de qīng nián zì xué liǎo jiān shēn de 《 tiān tǐ lì xué 》 hé hěn chōu xiàng de 《 fēn xī lì xué 》。 yóu yú tā duì dài shù guān xì de duìchèn hé měi yòu hěn qiáng de gǎn jué ， zài gū dú de yán jiū zhōng ， tā shǒu xiān fā xiàn liǎo bù biàn liàng ， bìng bǎ zhè yī chéng guǒ xiě chéng lùn wén fā biǎo 。 zhè piān gāo zhì liàng de lùn wén fā biǎo hòu ， bù 'ěr réng rán liú zài xiǎo xué jiāoshū , dàn shì tā kāi shǐ hé xǔ duō dì yī liú de yīng guó shù xué jiā jiāo wǎng huò tōng xìn ， qí zhōng yòu shù xué jiā 、 luó ji xué jiā dé · mó gēn 。 mó gēn zài 19 shì jì qián bàn yè juàn rù liǎo yīcháng zhù míng de zhēng lùn ， bù 'ěr zhī dào mó gēn shì duì de ， yú shì zài 1848 nián chū bǎn liǎo yī běn báobáo de xiǎo cè zǐ lái wéi péng yǒu biàn hù 。 zhè běn shū shì tā 6 nián hòu gèng wěi dà de dōng xī de yù gào ， tā yī wèn shì ， lì jí jī qǐ liǎo mó gēn de zàn yáng ， kěn dìng tā kāipì liǎo xīn de 、 jí shǒu de yán jiū kē mù 。 bù 'ěr cǐ shí yǐ jīng zài yán jiū luó ji dài shù ， jí bù 'ěr dài shù 。 tā bǎ luó ji jiǎn huà chéng jí wèiróng yì hé jiǎn dān de yī zhǒng dài shù 。 zài zhè zhǒng dài shù zhōng ， shìdàng de cái liào shàng de “ tuī lǐ ”， chéng liǎo gōng shì de chū děng yùn suàn de shì qíng ， zhè xiē gōng shì bǐ guò qù zài zhōng xué dài shù dì 'èr nián jí kè chéng zhōng suǒ yùn yòng de dà duō shù gōng shì yào jiǎn dān dé duō 。 zhè yàng ， jiù shǐ luó ji běn shēn shòu shù xué de zhī pèi 。 wèile shǐ zì jǐ de yán jiū gōng zuò qū yú wán shàn ， bù 'ěr zài cǐ hòu 6 nián de màn cháng shí jiān lǐ ， yòu fù chū liǎo bù tóng xún cháng de nǔ lì 。 1854 nián ， tā fā biǎo liǎo 《 sī wéi guī lǜ 》 zhè bù jié zuò ， dāng shí tā yǐ 39 suì ， bù 'ěr dài shù wèn shì liǎo ， shù xué shǐ shàng shù qǐ liǎo yī zuò xīn de lǐ chéng bēi 。 jīhū xiàng suǒ yòu de xīn shēng yī yàng ， bù 'ěr dài shù fā míng hòu méi yòu shòu dào rén men de zhòng shì 。 ōu zhōu dà lù zhù míng de shù xué jiā miè shì dì chēng tā wéi méi yòu shù xué yì yì de ， zhé xué shàng xī qí gǔ guài de dōng xī ， tā men huái yí yīng lún dǎo guó de shù xué jiā néng zài shù xué shàng zuò chū dú tè gòng xiàn 。 bù 'ěr zài tā de jié zuò chū bǎn hòu bù jiǔ jiù qù shì liǎo 。 20 shì jì chū ， luó sù zài 《 shù xué yuán lǐ 》 zhōng rèn wéi ，“ chún shù xué shì bù 'ěr zài yī bù tā chēng zhī wéi 《 sī wéi guī lǜ 》 de zhù zuò zhōng fā xiàn de 。” cǐ shuō yī chū ， lì kè yǐn qǐ shì rén duì bù 'ěr dài shù de zhù yì 。 jīn tiān ， bù 'ěr fā míng de luó ji dài shù yǐ jīng fā zhǎn chéng wéi chún shù xué de yī gè zhù yào fēn zhī 。
zài lí sàn shù xué zhōng ， bù 'ěr dài shù ( yòu shí jiào bù 'ěr gé ) shì yòu bǔ fēn pèi gé （ kě cān kǎo gé de dìng yì ) kě yǐ 'àn gè zhǒng fāng shì qù rèn wéi yuán sù shì shénme ； zuì cháng jiàn de shì bǎ tā men dāng zuò yī bān huà de zhēn zhí 。 zuò wéi yī gè jiǎn dān de lì zǐ ， jiǎ shè yòu sān gè tiáo jiàn shì dú lì de wéi zhēn huò wéi jiǎ 。 bù 'ěr dài shù de yuán sù kě yǐ jiē zhe jīng què zhǐ dìng nà xiē wéi zhēn ； nà me bù 'ěr dài shù zì shēn jiāng shì suǒ yòu bā zhǒng kě néng xìng de yī gè sōu jí ， hé yǔ zhī zài yī qǐ de zǔ hé tā men de fāng shì 。
yòu shí yě bèi chēng wéi bù 'ěr dài shù de yī gè xiāng guān zhù tí shì bù 'ěr luó ji ， tā kě yǐ bèi dìng yì wèishì suǒ yòu bù 'ěr dài shù suǒ gōng yòu de dōng xī 。 tā yóu zài bù 'ěr dài shù de yuán sù jiān yǒng yuǎn chéng lì de guān xì zǔ chéng ， ér bù guǎn nǐ jù tǐ de nà gè bù 'ěr dài shù 。 yīn wéi luó ji mén hé mǒu xiē diàn zǐ diàn lù de dài shù zài xíng shì shàng yě shì zhè yàng de ， suǒ yǐ tóng zài shù lǐ luó ji zhōng yī yàng ， bù 'ěr luó ji yě zài gōng chéng hé jì suàn jī kē xué zhōng yán jiū 。
zài bù 'ěr dài shù shàng de yùn suàn bèi chēng wéi and( yǔ )、 or( huò ) hé not( fēi )。 dài shù jié gòu yào shì bù 'ěr dài shù ， zhè xiē yùn suàn de xíng wéi jiù bì xū hé liǎng yuán sù de bù 'ěr dài shù yī yàng ( zhè liǎng gè yuán sù shì true( zhēn ) hé false( jiǎ ))。 bù 'ěr dài shù shì yī gè jí hé a， tí gōng liǎo liǎng gè 'èr yuán yùn suàn <math>land</math>( luó ji yǔ )、 <math>lor</math>( luó ji huò )， yī gè yī yuán yùn suàn <math>lnot</math>/~( luó ji fēi ) hé liǎng gè yuán sù 0( luó ji jiǎ ) hé 1( luó ji zhēn )， cǐ wài ， duì yú jí hé a de suǒ yòu yuán sù a、 b hé c， xià liè gōng lǐ chéng lì :
jié hé lǜ
jiāo huàn lǜ
xī shōu lǜ
fēn pèi lǜ
hù bǔ lǜ
shàng miàn de qián sān duì gōng lǐ : jié hé lǜ 、 jiāo huàn lǜ hé xī shōu lǜ ， yì wèi zhe (a,<math>land</math>,<math>lor</math>) shì yī gè gé 。 suǒ yǐ bù 'ěr dài shù yě kě yǐ dìng yì wéi yī gè fēn pèi de yòu bǔ gé 。
cóng zhè xiē gōng lǐ ， nǐ kě yǐ zhǎn shì chū zuì xiǎo yuán sù 0、 zuì dà yuán sù 1 hé rèn hé yuán sù a de bǔ ¬a dōushì wéi yī què dìng de 。 duì yú a zhōng de suǒ yòu de a hé b， xià liè héng děng shì yě chéng lì :
mì děng lǜ
yòu jiè lǜ
hé 1 shì hù bǔ de
dìng lǜ
duì hé lǜ zuì jiǎn dān de bù 'ěr dài shù zhǐ yòu liǎng gè yuán sù 0 hé 1， bìng tōng guò rú xià guī zé dìng yì :
tā yìng yòng yú luó ji zhōng ， jiě shì 0 wéi jiǎ ， 1 wéi zhēn ，∧ wéi yǔ ，∨ wéi huò ， ¬ wéi fēi 。 shè jí biàn liàng hé bù 'ěr yùn suàn de biǎo dá shì dài biǎo liǎo chén shù xíng shì ， liǎng gè zhè yàng de biǎo dá shì kě yǐ shǐ yòng shàng miàn de gōng lǐ zhèng shí wéi děng jià de ， dāng qiě jǐn dāng duì yìng de chén shù xíng shì shì luó ji děng jià de 。
liǎng yuán sù de bù 'ěr dài shù yě shì zài diàn zǐ gōng chéng zhōng yòng yú diàn lù shè jì ； zhè lǐ de 0 hé 1 dài biǎo shù zì diàn lù zhōng yī gè wèi de liǎng zhǒng bù tóng zhuàng tài ， diǎn xíng de shì gāo hé dī diàn yā 。 diàn lù tōng guò bāo hán biàn liàng de biǎo dá shì lái miáo shù ， liǎng gè zhè zhǒng biǎo dá shì duì zhè xiē biàn liàng de suǒ yòu de zhí shì děng jià de ， dāng qiě jǐn dāng duì yìng de diàn lù yòu xiāng tóng de shū rù - shū chū xíng wéi 。 cǐ wài ， suǒ yòu kě néng de shū rù - shū chū xíng wéi dōukě yǐ shǐ yòng hé shì de bù 'ěr biǎo dá shì lái jiàn mō 。
liǎng yuán sù bù 'ěr dài shù zài bù 'ěr dài shù de yī bān lǐ lùn zhōng yě shì zhòng yào de ， yīn wéi shè jí duō gè biàn liàng de děng shì shì zài suǒ yòu bù 'ěr dài shù zhōng pǔ biàn zhēn shí de ， dāng qiě jǐn dāng tā zài liǎng gè yuán sù de bù 'ěr dài shù zhōng shì zhēn shí de ( zhè zǒng shì kě yǐ tōng guò píng fán de mán lì suàn fǎ zhèng shí )。 bǐ rú zhèng shí xià liè dìng lǜ ( hé yì (consensus) dìng lǐ ) zài suǒ yòu bù 'ěr dài shù zhōng shì pǔ biàn yòu xiào de :
≡ (a∨ b)∧ (¬a∨ c)
rèn hé gěi dìng jí hé s de mì jí ( zǐ jí de jí hé ) xíng chéng yòu liǎng gè yùn suàn ∨ := ∪ ( bìng ) hé ∧ := ∩ ( jiāo ) de bù 'ěr dài shù 。 zuì xiǎo de yuán sù 0 shì kōng jí 'ér zuì dà yuán sù 1 shì jí hé s zì shēn 。
yòu xiàn de huò zhě cofinite de jí hé s de suǒ yòu zǐ jí de jí hé shì bù 'ěr dài shù 。
duì yú rèn hé zì rán shù n， n de suǒ yòu zhèng yuē shù de jí hé xíng chéng yī gè fēn pèi gé ， rú guǒ wǒ men duì a|b xiě a ≤ b。 zhè gè gé shì bù 'ěr dài shù dāng qiě jǐn dāng n shì wú píng fāng yīn zǐ de 。 zhè gè bù 'ěr dài shù de zuì xiǎo de yuán sù 0 shì zì rán shù 1； zhè gè bù 'ěr dài shù de zuì dà yuán sù 1 shì zì rán shù n。
bù 'ěr dài shù de lìng yī gè lì zǐ lái zì tuò pū kōng jiān : rú guǒ x shì yī gè tuò pū kōng jiān ， tā jì shì kāi fàng de yòu shì bì hé de ， x de suǒ yòu zǐ jí de sōu jí xíng chéng yòu liǎng gè yùn suàn ∨ :=∪ ( bìng ) hé ∧ :=∩ ( jiāo ) de bù 'ěr dài shù 。
rú guǒ r shì yī gè rèn yì de huán ， bìng qiě wǒ men dìng yì zhōng xīn mì děng yuán (centralidempotent) de jí hé wéi
∈ r:e2=e,ex=xe,∀x∈ r}
zé jí hé a chéng wéi yòu liǎng gè yùn suàn e∨ f:=e+f+ef hé e∧ f:=ef de bù 'ěr dài shù 。 image:hasse diagram of powerset of 3.png
zǐ jí de bù 'ěr gé tóng rèn hé gé yī yàng ， bù 'ěr dài shù (a,<math>land</math>,<math>lor</math>) kě yǐ yǐn chū piān xù jí (a,≤ )， tōng guò dìng yì
dāng qiě jǐn dāng a=a<math>land</math>b( tā yě děng jià yú b=a<math>lor</math>b)。
shì shí shàng nǐ hái kě yǐ bǎ bù 'ěr dài shù dìng yì wèiyòu zuì xiǎo yuán sù 0 hé zuì dà yuán sù 1 de fēn pèi gé (a,≤ )( kǎo lǜ wéi piān xù jí hé )， zài qí zhōng suǒ yòu de yuán sù x dōuyòu bǔ ¬x mǎn zú
bìng qiě x<math>lor</math>¬x=1
zhè lǐ de <math>land</math> hé <math>lor</math> yòng lái zhǐ shì liǎng gè yuán sù de xià què jiè ( jiāo ) hé shàng què jiè ( bìng )。 hái yòu ， rú guǒ shàng shù yì yì shàng de bǔ cún zài ， zé tā men shì kě wéi yī què dìng de 。
dài shù de hé xù lǐ lùn de guān diǎn tōng cháng kě yǐ jiāo tì de shǐ yòng ， bìng qiě 'èr zhě dōushì yòu zhòng yào yòng chù de ， kě cóng fàn dài shù hé xù lǐ lùn yǐn rù jiēguǒ hé gài niàn 。 zài hěn duō shí jì lì zǐ zhōng cì xù guān xì 、 hé qǔ ( luó ji yǔ )、 xī qǔ ( luó ji huò ) hé fǒu dìng ( luó ji fēi ) dōushì zì rán de kě huò dé de ， suǒ yǐ kě zhí jiē lì yòng zhè zhǒng lián xì 。 nǐ hái kě yǐ bǎ lái zì xù lǐ lùn de duì 'ǒu xìng de pǔ biàn rèn shí yìng yòng yú bù 'ěr dài shù 。 tè bié shì ， suǒ yòu de bù 'ěr dài shù de cì xù duì 'ǒu ， huò zhě děng jià de shuō tōng guò duì huàn <math>land</math> yǔ <math>lor</math> suǒ huò dé de dài shù ， yě shì bù 'ěr dài shù 。 yī bān de shuō ， bù 'ěr dài shù de rèn hé yòu xiào de guī lǜ dōukě yǐ biàn huàn chéng lìng yī gè yòu xiào de duì 'ǒu guī lǜ ， tōng guò duì huàn 0 yǔ 1， <math>land</math> yǔ <math>lor</math>， hé ≤ yǔ ≥ 。 bù 'ěr dài shù de yùn suàn fú kě yǐ yòng gè zhǒng fāng shì biǎo shì 。 tā men jīng cháng jiǎn dān xiě chéng and、 or hé not。 zài miáo shù diàn lù shí ， hái kě yǐ shǐ yòng nand(notand)、 nor(notor) hé xor( pái chì de or)。 shù xué jiā 、 gōng chéng shī hé chéng xù yuán jīng cháng shǐ yòng + biǎo shì or hé · biǎo shì and( yīn wéi zài mǒu xiē fāng miàn zhè xiē yùn suàn lèi sì yú zài qí tā dài shù jié gòu zhōng de jiā fǎ hé chéng fǎ ， bìng qiě zhè zhǒng yùn suàn yì yú duì pǔ tōng dài shù shú xī de rén dé dào jī zhī hé fàn shì )， hé bǎ not biǎo shì wéi zài yào fǒu dìng de biǎo dá shì dǐng shàng huà yī tiáo héng xiàn 。
zhè lǐ wǒ men shǐ yòng lìng yī zhǒng cháng jiàn jì hào ， " jiāo "<math>land</math> biǎo shì and， " bìng "<math>lor</math> biǎo shì or， hé ¬ biǎo shì not。 ( shǐ yòng zhǐ yòu wén běn de liú lǎn qì de dú zhě jiāng jiàn dào latex dài mǎ 'ér bù shì tā men biǎo shì de xiē xíng fú hào 。 ) zài bù 'ěr dài shù a hé b zhī jiān de tóng tài shì yī gè hán shù f:a → b， duì yú zài a zhōng suǒ yòu de a,b dōuyòu :
jiē zhe duì yú zài a zhōng suǒ yòu de a， f(¬a)=¬f(a) tóng yàng chéng lì 。 suǒ yòu bù 'ěr dài shù de lèi ， hé yǔ zhī zài yī qǐ de tài shè (morphism) de gài niàn ， xíng chéng liǎo yī gè fàn chóu 。 cóng a dào b de tóng gòu shì shuāng shè de cóng a dào b de tóng tài 。 tóng tài de nì yě shì tóng tài ， wǒ men chēng liǎng gè bù 'ěr dài shù a hé b wéi tóng tài de 。 cóng bù 'ěr dài shù lǐ lùn de lì chǎng shàng ， tā men shì bù néng qū fēn de ； tā men zhǐ zài tā men de yuán sù de fú hào shàng yòu suǒ bù tóng 。 bù 'ěr de huán 、 lǐ xiǎng hé lǜ zǐ měi gè bù 'ěr dài shù (a,<math>land</math>,<math>lor</math>) dū yǐn chū yī gè huán (a,+,*)， tōng guò dìng yì a+b=(a<math>land</math>¬b)<math>lor</math>(b<math>land</math>¬a)( zhè gè yùn suàn zài jí hé lùn zhōng jiào zuò " duìchèn chā " zài luó ji zhōng jiào zuò xor( yì huò )) hé a*b=a<math>land</math>b。 zhè gè huán de líng yuán sù fú hé bù 'ěr dài shù de 0； huán de chéng fǎ dān wèi yuán sù shì bù 'ěr dài shù de 1。 zhè gè huán yòu duì yú a zhōng de suǒ yòu de a bǎo chí a*a=a de xìng zhì ； yòu zhè zhǒng xìng zhì de huán jiào zuò bù 'ěr huán 。
fǎn guò lái ， rú guǒ gěi chū bù 'ěr huán a， wǒ men kě yǐ bǎ tā zhuǎn huàn chéng bù 'ěr dài shù ， tōng guò dìng yì x<math>lor</math>y=x+y+xy hé x<math>land</math>y=xy。 yīn wéi zhè liǎng gè yùn suàn shì hù nì de ， wǒ men kě yǐ shuō měi gè bù 'ěr huán yǐn fā yī gè bù 'ěr dài shù ， huò fǎn zhī 。 cǐ wài ， yìng shè f:a→ b shì bù 'ěr dài shù de tóng tài ， dāng qiě jǐn dāng tā shì bù 'ěr huán de tóng tài 。 bù 'ěr huán hé dài shù de fàn chóu shì děng jià de 。
bù 'ěr dài shù a de lǐ xiǎng shì yī gè zǐ jí i， duì yú zài i zhōng de suǒ yòu x,y wǒ men yòu x<math>lor</math>y zài i zhōng ， bìng qiě duì yú zài a zhōng de suǒ yòu a wǒ men yòu a<math>land</math>x zài i zhōng 。 lǐ xiǎng de gài niàn fú hé zài bù 'ěr huán a zhōng huán lǐ xiǎng de gài niàn 。 a de lǐ xiǎng i jiào zuò sù lǐ xiǎng ， rú guǒ i ≠ a； bìng qiě rú guǒ a<math>land</math>b zài i zhōng zǒng shì yùn hán a zài i zhōng huò b zài i zhōng 。 a de lǐ xiǎng i jiào zuò jí dà lǐ xiǎng ， rú guǒ i≠ a bìng qiě zhēn zhèng bāo hán i de wéi yī de lǐ xiǎng shì a zì shēn 。 zhè xiē gài niàn fú hé bù 'ěr huán a zhōng de sù lǐ xiǎng hé jí dà lǐ xiǎng de huán lǐ lùn gài niàn 。
lǐ xiǎng de duì 'ǒu shì lǜ zǐ 。 bù 'ěr dài shù a de lǜ zǐ shì zǐ jí p， duì yú zài p zhōng de suǒ yòu x,y wǒ men yòu x<math>land</math>y zài p zhōng ， bìng qiě duì yú zài a zhōng de suǒ yòu a， rú guǒ a<math>lor</math>x=a zé a zài p zhōng 。 kě yǐ zhèng shí suǒ yòu de yòu xiàn de bù 'ěr dài shù dū tóng gòu yú zhè gè yòu xiàn jí hé de suǒ yòu zǐ jí de bù 'ěr dài shù 。 cǐ wài ， suǒ yòu de yòu xiàn de bù 'ěr dài shù de yuán sù shù mù dōushì 'èr de mì 。
de zhù míng de bù 'ěr dài shù de biǎo shì dìng lǐ chén shù liǎo suǒ yòu de bù 'ěr dài shù a dōuzài mǒu gè ( jǐn còu de wán quán bù lián tōng de hausdorff) tuò pū kōng jiān zhōng tóng gòu yú suǒ yòu bì kāi jí de bù 'ěr dài shù 。 gōng lǐ huà bù 'ěr dài shù zài 1933 nián ， měi guó shù xué jiā edwardvermilyehuntington(1874-1952) zhǎn shì liǎo duì bù 'ěr dài shù de rú xià gōng lǐ huà :
jiāo huàn lǜ :x+y=y+x。
jié hé lǜ :(x+y)+z=x+(y+z)。
děng shì :n(n(x)+y)+n(n(x)+n(y))=x。
yī yuán hán shù fú hào n kě yǐ dú zuò ' bǔ '。
jiē zhe bǎi chū xià liè wèn tí :huntington děng shì néng fǒu suō duǎn wéi xià shù de děng shì ， bìng qiě zhè gè xīn děng shì yǔ jié hé lǜ hé jiāo huàn lǜ yī qǐ chéng wéi bù 'ěr dài shù de jī chǔ ? tōng guò yī zǔ jiào zuò robbins dài shù de gōng lǐ ， wèn tí jiù biàn chéng liǎo : shì fǒu suǒ yòu de robbins dài shù dōushì bù 'ěr dài shù ?
dài shù de gōng lǐ huà :
jiāo huàn lǜ :x+y=y+x。
jié hé lǜ :(x+y)+z=x+(y+z)。
děng shì :n(n(x+y')+n(x+n(y)))=x。
zhè gè wèn tí zì cóng 1930 nián dài yī zhí shì gōng kāi de ， bìng chéng wéi alfredtarski hé tā de xué shēng zuì xǐ hǎo de wèn tí 。
zài 1996 nián ， williammccune zài argonne guó jiā shí yàn shì ， jiàn zào zài larrywos、 stevewinker hé bobveroff de gōng zuò zhī shàng ， kěn dìng de huí dá liǎo zhè gè cháng qī cún zài de wèn tí : suǒ yòu de robbins dài shù dōushì bù 'ěr dài shù 。 zhè xiàng gōng zuò shì shǐ yòng mccune de zì dòng tuī lǐ chéng xù eqp wán chéng de 。 bù 'ěr dài shù de jī běn guī zé dài rù fǎ zé tā kě miáo shù wéi luó ji dài shù shì zhōng de rèn hé biàn liàng a， dōukě yòng lìng yī gè hán shù z dài tì ， děng shì réng rán chéng lì 。
duì 'ǒu fǎ zé tā kě miáo shù wéi duì rèn hé yī gè luó ji biǎo dá shì f， rú guǒ jiāng qí zhōng de “ +” huàn chéng “ *”，“ *” huàn chéng “ +”“ 1” huàn chéng “ 0”，“ 0” huàn chéng “ 1”， réng bǎo chí yuán lái de luó ji yōu xiān jí ， zé kě dé dào yuán hán shù f de duì 'ǒu shì g， ér qiě f yǔ g hù wéi duì 'ǒu shì 。 wǒ men kě yǐ kàn chū jī běn gōng shì shì chéng duì chū xiàn de ， èr dū hù wéi duì 'ǒu shì 。
fǎn yǎn fǎ zé yòu yuán hán shù qiú fǎn hán shù jiù chēng wéi fǎn yǎn （ lì yòng mó gēn dìng lǜ ），
wǒ men kě yǐ bǎ fǎn yǎn fǎ zé zhè yàng miáo shù ： jiāng yuán hán shù f zhōng de “ *” huàn chéng “ +”，“ +” huàn chéng “ *”，“ 0” huàn chéng “ 1”，“ 1” huàn chéng “ 0”； yuán biàn liàng huàn chéng fǎn biàn liàng ， fǎn biàn liàng huàn chéng yuán biàn liàng ， cháng fēi hào jí liǎng gè huò liǎng gè yǐ shàng biàn liàng de fēi hào bù biàn ， jiù dé dào yuán hán shù de fǎn hán shù 。 fā xiàn zhě hé fā xiàn guò chéng Boolean algebra
yīng guó shù xué jiā G. bù 'ěr wèile yán jiū sī wéi guī lǜ （ luó ji xué 、 shù lǐ luó ji ) yú 1847 hé 1854 nián tí chū de shù xué mó xíng 。 cǐ hòu R. dài dé jīn bǎ tā zuò wéi yī zhǒng tè shū de gé 。 suǒ wèi yī gè bù 'ěr dài shù ， shì zhǐ yī gè yòu xù de sì yuán zǔ 〈 B，∨，∧， *〉， qí zhōng B shì yī gè fēi kōng de jí hé ，∨ yǔ ∧ shì dìng yì zài B shàng de liǎng gè 'èr yuán yùn suàn ， * shì dìng yì zài B shàng de yī gè yī yuán yùn suàn ， bìng qiě tā men mǎn zú yī dìng de tiáo jiàn 。
bù 'ěr dài shù yóu yú quē fá wù lǐ bèi jǐng ， suǒ yǐ yán jiū huǎn màn ， dào liǎo 20 shì jì 30～ 40 nián dài cái yòu liǎo xīn de jìn zhǎn ， dà yuē zài 1935 nián ， M.H. sī tōng shǒu xiān zhǐ chū bù 'ěr dài shù yǔ huán zhī jiān yòu míng què de lián xì ， tā hái dé dào liǎo xiàn zài suǒ wèi de sī tōng biǎo shì dìng lǐ ： rèn yì yī gè bù 'ěr dài shù yī dìng tóng gòu yú mǒu gè jí shàng de yī gè jí yù ； rèn yì yī gè bù 'ěr dài shù yě yī dìng tóng gòu yú mǒu gè tuò pū kōng jiān de bì kāi dài shù děng ， zhè shǐ bù 'ěr dài shù zài lǐ lùn shàng yòu liǎo yī dìng de fā zhǎn 。 bù 'ěr dài shù zài dài shù xué （ dài shù jié gòu ）、 luó ji yǎn suàn 、 jí hé lùn 、 tuò pū kōng jiān lǐ lùn 、 cèduó lùn 、 gàilǜ lùn 、 fàn hán fēn xī děng shù xué fēn zhī zhōng jūn yòu yìng yòng ； 1967 nián hòu ， zài shù lǐ luó ji de fēn zhī zhī yī de gōng lǐ huà jí hé lùn yǐ jí mó xíng lùn de lǐ lùn yán jiū zhōng ， yě qǐ zhe yī dìng de zuò yòng 。 jìn jǐ shí nián lái ， bù 'ěr dài shù zài zì dòng huà jì shù 、 diàn zǐ jì suàn jī de luó ji shè jì děng gōng chéng jì shù lǐng yù zhōng yòu zhòng yào de yìng yòng 。
nián ， 20 suì de qiáo zhì · bù 'ěr kāi bàn liǎo yī suǒ sī rén shòu kè xué xiào 。 wèile gěi xué shēng men kāi shè bì yào de shù xué kè chéng ， tā xīng qù nóng hòu dì dú qǐ liǎo dāng shí yī xiē jiè shào shù xué zhī shí de jiào kē shū 。 bù jiǔ ， tā jiù gǎn dào jīng yà ， zhè xiē dōng xī jiù shì shù xué má ？ shí zài lìng rén nán yǐ zhì xìn 。 yú shì ， zhè wèi zhǐ shòu guò chū bù shù xué xùn liàn de qīng nián zì xué liǎo jiān shēn de 《 tiān tǐ lì xué 》 hé hěn chōu xiàng de 《 fēn xī lì xué 》。 yóu yú tā duì dài shù guān xì de duìchèn hé měi yòu hěn qiáng de gǎn jué ， zài gū dú de yán jiū zhōng ， tā shǒu xiān fā xiàn liǎo bù biàn liàng ， bìng bǎ zhè yī chéng guǒ xiě chéng lùn wén fā biǎo 。 zhè piān gāo zhì liàng de lùn wén fā biǎo hòu ， bù 'ěr réng rán liú zài xiǎo xué jiāoshū , dàn shì tā kāi shǐ hé xǔ duō dì yī liú de yīng guó shù xué jiā jiāo wǎng huò tōng xìn ， qí zhōng yòu shù xué jiā 、 luó ji xué jiā dé · mó gēn 。 mó gēn zài 19 shì jì qián bàn yè juàn rù liǎo yīcháng zhù míng de zhēng lùn ， bù 'ěr zhī dào mó gēn shì duì de ， yú shì zài 1848 nián chū bǎn liǎo yī běn báobáo de xiǎo cè zǐ lái wéi péng yǒu biàn hù 。 zhè běn shū shì tā 6 nián hòu gèng wěi dà de dōng xī de yù gào ， tā yī wèn shì ， lì jí jī qǐ liǎo mó gēn de zàn yáng ， kěn dìng tā kāipì liǎo xīn de 、 jí shǒu de yán jiū kē mù 。 bù 'ěr cǐ shí yǐ jīng zài yán jiū luó ji dài shù ， jí bù 'ěr dài shù 。 tā bǎ luó ji jiǎn huà chéng jí wèiróng yì hé jiǎn dān de yī zhǒng dài shù 。 zài zhè zhǒng dài shù zhōng ， shìdàng de cái liào shàng de “ tuī lǐ ”， chéng liǎo gōng shì de chū děng yùn suàn de shì qíng ， zhè xiē gōng shì bǐ guò qù zài zhōng xué dài shù dì 'èr nián jí kè chéng zhōng suǒ yùn yòng de dà duō shù gōng shì yào jiǎn dān dé duō 。 zhè yàng ， jiù shǐ luó ji běn shēn shòu shù xué de zhī pèi 。 wèile shǐ zì jǐ de yán jiū gōng zuò qū yú wán shàn ， bù 'ěr zài cǐ hòu 6 nián de màn cháng shí jiān lǐ ， yòu fù chū liǎo bù tóng xún cháng de nǔ lì 。 1854 nián ， tā fā biǎo liǎo 《 sī wéi guī lǜ 》 zhè bù jié zuò ， dāng shí tā yǐ 39 suì ， bù 'ěr dài shù wèn shì liǎo ， shù xué shǐ shàng shù qǐ liǎo yī zuò xīn de lǐ chéng bēi 。 jīhū xiàng suǒ yòu de xīn shēng shì wù yī yàng ， bù 'ěr dài shù fā míng hòu méi yòu shòu dào rén men de zhòng shì 。 ōu zhōu dà lù zhù míng de shù xué jiā miè shì dì chēng tā wéi méi yòu shù xué yì yì de 、 zhé xué shàng xī qí gǔ guài de dōng xī ， tā men huái yí yīng lún dǎo guó de shù xué jiā néng zài shù xué shàng zuò chū dú tè gòng xiàn 。 bù 'ěr zài tā de jié zuò chū bǎn hòu bù jiǔ jiù qù shì liǎo 。 20 shì jì chū ， luó sù zài 《 shù xué yuán lǐ 》 zhōng rèn wéi ，“ chún shù xué shì bù 'ěr zài yī bù tā chēng zhī wéi 《 sī wéi guī lǜ 》 de zhù zuò zhōng fā xiàn de 。” cǐ shuō yī chū ， lì kè yǐn qǐ shì rén duì bù 'ěr dài shù de zhù yì 。 jīn tiān ， bù 'ěr fā míng de luó ji dài shù yǐ jīng fā zhǎn chéng wéi chún shù xué de yī gè zhù yào fēn zhī 。
zài lí sàn shù xué zhōng ， bù 'ěr dài shù ( yòu shí jiào bù 'ěr gé ) shì yòu bǔ fēn pèi gé （ kě cān kǎo gé de dìng yì ) kě yǐ 'àn gè zhǒng fāng shì qù rèn wéi yuán sù shì shénme ； zuì cháng jiàn de shì bǎ tā men dāng zuò yī bān huà de zhēn zhí 。 zuò wéi yī gè jiǎn dān de lì zǐ ， jiǎ shè yòu sān gè tiáo jiàn shì dú lì de wéi zhēn huò wéi jiǎ 。 bù 'ěr dài shù de yuán sù kě yǐ jiē zhe jīng què zhǐ dìng nà xiē wéi zhēn ； nà me bù 'ěr dài shù zì shēn jiāng shì suǒ yòu bā zhǒng kě néng xìng de yī gè sōu jí ， hé yǔ zhī zài yī qǐ de zǔ hé tā men de fāng shì 。
yòu shí yě bèi chēng wéi bù 'ěr dài shù de yī gè xiāng guān zhù tí shì bù 'ěr luó ji ， tā kě yǐ bèi dìng yì wèishì suǒ yòu bù 'ěr dài shù suǒ gōng yòu de dōng xī 。 tā yóu zài bù 'ěr dài shù de yuán sù jiān yǒng yuǎn chéng lì de guān xì zǔ chéng ， ér bù guǎn nǐ jù tǐ de nà gè bù 'ěr dài shù 。 yīn wéi luó ji mén hé mǒu xiē diàn zǐ diàn lù de dài shù zài xíng shì shàng yě shì zhè yàng de ， suǒ yǐ tóng zài shù lǐ luó ji zhōng yī yàng ， bù 'ěr luó ji yě zài gōng chéng hé jì suàn jī kē xué zhōng yán jiū 。
zài bù 'ěr dài shù shàng de yùn suàn bèi chēng wéi AND( yǔ )、 OR( huò ) hé NOT( fēi )。 dài shù jié gòu yào shì bù 'ěr dài shù ， zhè xiē yùn suàn de xíng wéi jiù bì xū hé liǎng yuán sù de bù 'ěr dài shù yī yàng ( zhè liǎng gè yuán sù shì TRUE( zhēn ) hé FALSE( jiǎ ))。 bù 'ěr dài shù shì yī gè jí hé A， tí gōng liǎo liǎng gè 'èr yuán yùn suàn land( luó ji yǔ )、 lor( luó ji huò )， yī gè yī yuán yùn suàn lnot/~( luó ji fēi ) hé liǎng gè yuán sù 0( luó ji jiǎ ) hé 1( luó ji zhēn )， cǐ wài ， duì yú jí hé A de suǒ yòu yuán sù a、 b hé c， xià liè gōng lǐ chéng lì :
jié hé lǜ
jiāo huàn lǜ
xī shōu lǜ
fēn pèi lǜ
hù bǔ lǜ
shàng miàn de qián sān duì gōng lǐ : jié hé lǜ 、 jiāo huàn lǜ hé xī shōu lǜ ， yì wèi zhe (A,land,lor) shì yī gè gé 。 suǒ yǐ bù 'ěr dài shù yě kě yǐ dìng yì wéi yī gè fēn pèi de yòu bǔ gé 。
cóng zhè xiē gōng lǐ ， nǐ kě yǐ zhǎn shì chū zuì xiǎo yuán sù 0、 zuì dà yuán sù 1 hé rèn hé yuán sù a de bǔ ¬a dōushì wéi yī què dìng de 。 duì yú A zhōng de suǒ yòu de a hé b， xià liè héng děng shì yě chéng lì :
mì děng lǜ
yòu jiè lǜ
hé 1 shì hù bǔ de
dìng lǜ
duì hé lǜ bù 'ěr dài shù de jī běn guī zé dài rù fǎ zé tā kě miáo shù wéi luó ji dài shù shì zhōng de rèn hé biàn liàng A， dōukě yòng lìng yī gè hán shù Z dài tì ， děng shì réng rán chéng lì 。
duì 'ǒu fǎ zé tā kě miáo shù wéi duì rèn hé yī gè luó ji biǎo dá shì F， rú guǒ jiāng qí zhōng de “ +” huàn chéng “ *”，“ *” huàn chéng “ +”“ 1” huàn chéng “ 0”，“ 0” huàn chéng “ 1”， réng bǎo chí yuán lái de luó ji yōu xiān jí ， zé kě dé dào yuán hán shù F de duì 'ǒu shì G， ér qiě F yǔ G hù wéi duì 'ǒu shì 。 wǒ men kě yǐ kàn chū jī běn gōng shì shì chéng duì chū xiàn de ， èr dū hù wéi duì 'ǒu shì 。
fǎn yǎn fǎ zé yòu yuán hán shù qiú fǎn hán shù jiù chēng wéi fǎn yǎn （ lì yòng mó gēn dìng lǜ ），
wǒ men kě yǐ bǎ fǎn yǎn fǎ zé zhè yàng miáo shù ： jiāng yuán hán shù F zhōng de “ *” huàn chéng “ +”，“ +” huàn chéng “ *”，“ 0” huàn chéng “ 1”，“ 1” huàn chéng “ 0”； yuán biàn liàng huàn chéng fǎn biàn liàng ， fǎn biàn liàng huàn chéng yuán biàn liàng ， cháng fēi hào jí liǎng gè huò liǎng gè yǐ shàng biàn liàng de fēi hào bù biàn ， jiù dé dào yuán hán shù de fǎn hán shù 。
bù 'ěr dài shù dìng lǜ ：
hù bǔ lǜ ：
dì yī hù bǔ lǜ ： ruò A=0， zé ~A=1, ruò A=1， zé ~A=0 zhù ： ~A= Ｎ Ｏ Ｔ Ａ
dì 'èr hù bǔ lǜ ： A*~A=0
dì sān hù bǔ lǜ ： A+~A=1
shuāngchóng hù bǔ lǜ ： /<~A>=//A=A
jiāo huàn lǜ ：
jiāo huàn lǜ ： A*B=B*A
jiāo huàn lǜ ： A+B=B+A
jié hé lǜ ：
jié hé lǜ ：Ａ ＜ Ｂ * Ｃ ＞ ＝ Ｃ *＜Ａ *Ｂ＞
Ｒ jié hé lǜ ： Ａ ＋ ＜Ｂ＋Ｃ＞＝Ｃ＋＜Ａ＋Ｂ＞
fēn pèi shuài ：
dì yī fēn pèi shuài ： Ａ *＜Ｂ＋Ｃ＞＝＜Ａ *Ｂ＞＋＜Ａ *Ｃ＞
dì 'èr fēn pèi shuài ： Ａ＋＜Ｂ *C>=<A+B>*<A+C>
zhòng yán lǜ ：
dì yī zhòng yán lǜ ： A*A=A ruò A=1， zé A*A=1； ruò A=0， zé A*A=0。 yīn cǐ biǎo dá shì jiǎn huà wéi A
dì 'èr zhòng yán lǜ ： A+A=A ruò A=1， zé 1+1=1； ruò A=0， zé 0+0=0。 yīn cǐ biǎo dá shì jiǎn huà wéi A
dài cháng shù de zhòng yán lǜ ：
xī shōu shuài ：
dì yī xī shōu shuài ： A*<A+B>=A
dì 'èr xī shōu shuài ： A+<A*B>=A Bu ’ er daishu
bù 'ěr dài shù
shǒu xiān shì G. bù 'ěr wèile yán jiū sī wéi guī lǜ （ luó ji xué 、 shù lǐ luó ji ） yú 1847 nián hé 1854 nián tí chū de 。 tā zuò wéi yī zhǒng tè shū de gé zé shì J.W.R. dài dé jīn zhī hòu de shì qíng 。 suǒ wèi yī gè bù 'ěr dài shù ， shì zhǐ yī gè yòu xù de sì yuán zǔ 〈 □ ,∨ ,∧ ,□〉 , qí zhōng □ shì yī gè fēi kōng de jí hé ，∨ yǔ ∧ shì dìng yì zài □ shàng de liǎng gè 'èr yuán yùn suàn ,□ shì dìng yì zài □ shàng de yī gè yī yuán yùn suàn , bìng qiě tā men mǎn zú yǐ xià tiáo jiàn :A1.□∨□ =□∨□ ,□∧□ =□∧□； A2.(□∨□ )∨□ =□∨ (□∨□ ),(□∧□ )∧□ =□∧ (□∧□ );A3.(□∧□ )∨□ =□ ,(□∨□ )∧□ =□ ;A4.□∧ (□∨□ )=(□∧□ )∨ (□∧□ )，□∨ (□∧□ )=(□∨□ )∧ (□∨□ );A5.(□∧□□ )∨□ =□ ,(□∨□□ )∧□ =□ , duì yú rèn yì de □、□、□□□□□ jūn chéng lì 。 huò zhě , bù 'ěr dài shù dìng yì wéi jù yòu zuì dà yuán hé zuì xiǎo yuán de yòu yú （ yòu bǔ ） de fēn pèi gé 。
shè □□ ={0,1} shì yóu liǎng gè yuán sù 0 yǔ 1 suǒ zǔ chéng de jí hé 。 tā de liǎng gè 'èr yuán yùn suàn hé yī gè yī yuán yùn suàn dìng yì rú xià ： 0∨ 0=0,0∨ 1=1∨ 0=1∨ 1=1； 0∧ 0=0∧ 1=1∧ 0=0， 1∧ 1=1； 0□ =1,1□ =0。 kě yǐ yàn zhèng ，□□ shì yī gè bù 'ěr dài shù 。
shè □ ={1,2,3,5,6,10,15,30} shì 30 de zhèng yīn zǐ de jí hé 。 guī dìng ∨ shì qǔ tā men de zuì xiǎo gōng bèi shù ，∧ shì qǔ tā men de zuì dà gōng yīn shù :□ shì ： 1□ =30,2□ =15,3□ =10,5□ =6,6□ =5,10□ =3,15□ =2,30□ =1， róng yì yàn zhèng □ duì yú suǒ dìng yì de yùn suàn chéng wéi yī bù 'ěr dài shù 。
rú guǒ yī gè huán □＝〈□ ,+,□〉 jù yòu dān wèi yuán 1, bìng qiě duì rèn yì de □□□□□， yòu □□ =□， nà me □ chēng wéi bù 'ěr huán 。 lìng □ shì bù 'ěr huán , ruò dìng yì □∨□ =□ +□ +□ ·□ ,□∧□ =□ ·□ ,□□ =1+□， zé □ zài suǒ dìng yì de yùn suàn xià chéng wéi yī gè bù 'ěr dài shù 。
shè □ shì yóu suǒ yòu de shí shù zǔ chéng de jí hé 。 yóu dān yuán jí hé qū jiān de yòu xiàn bìng suǒ zǔ chéng de jí hé □ , zài jí hé de bìng (∪ )、 jiāo (∩ )、 yú (□ ) yùn suàn zhī xià shì yī gè bù 'ěr dài shù 。 suǒ wèi dān yuán jí , shì zhǐ jǐn yóu yī gè shí shù suǒ zǔ chéng de jí hé 。 qū jiān kě yǐ shì yòu jiè de huò wú jiè de ， bì de huò kāi de huò bàn kāi （ bì ） de 。
lìng □ shì yī gè gù dìng de jí hé 。□ de suǒ yòu zǐ jí zǔ chéng de jí hé chēng wéi □ de mì jí , jì wéi □ (□ )={□ │ □□□ }。 shè □ shì □ (□ ) de zǐ jí , bìng qiě {□ ,□ }□□□□ (□ )。 rú guǒ □ zài jí hé lùn de bìng (∪ )、 jiāo (∩ )、 yú (□ ) yòu xiàn cì yùn suàn xià shì fēng bì de ， nà me zhè yàng de □ zài bǎ yòu xiàn cì bìng 、 jiāo 、 yú zuò wéi ∨、∧、□ yùn suàn shí , shì yī gè bù 'ěr dài shù 。 zhè zhǒng bù 'ěr dài shù , cháng cháng chēng wéi jí yù （ jí chǎng ）。 tè shū dì ， qǔ □ =□□ ={□ ,□ },□ =□ (□ ),□ ={□□□□□ (□ )│□ wèiyòu xiàn jí huò yòu xiàn jí de yú jí }, … … , jūn wéi jí yù 。 dāng □ ={□□ ,□□ ,… ,□□ } shì yòu xiàn jí shí ， zé □ (□ )={□│□□□ }={{□□ 1,□□ 2,… ,□□□ }│□□ ,□□ ,… ,□□ shì 1,2,… ,□ zhōng qǔ □ gè de zǔ hé ， 0□□□□ }=2□ =2□ yě shì yī gè jí yù 。 tā shì yóu yòu xiàn gè yuán sù suǒ zǔ chéng de bù 'ěr dài shù （ yòu xiàn bù 'ěr dài shù ）。
lìng 〈□ ,□〉 shì yī gè tuò pū kōng jiān ，□ shì X shàng de yī gè tuò pū ，□ ={□□□│□ jì shì kāi jí ,□ tóng shí yòu shì bì jí }。 zài jí hé lùn de bìng 、 jiāo 、 yú yùn suàn xià □ shì yī gè bù 'ěr dài shù , bìng chēng zhī wéi bì kāi dài shù 。 ruò qǔ □ B={□□□│□ de biān jiè shì wú chù chóu mì de ｝ ， zé cǐ shí □ yě shì yī gè bù 'ěr dài shù 。
lìng 〈□ ,□〉 shì yī gè tuò pū kōng jiān ,□ de zǐ jí □ shì zhèng guī de bì jí ， dāng qiě jǐn dāng □ de nèi bù de bì bāo děng yú □， jí □。 ruò □ ={□□□│□ shì zhèng guī de bì jí ｝， èr yuán yùn suàn ∨ shì zhǐ jí hé de bìng yùn suàn ， èr yuán yùn suàn ∧ shì zhǐ jīng jí hé de jiāo yùn suàn hòu zài qǔ qí nèi bù de bì bāo ， jí □ ,□□、□□□□□。 yī yuán yùn suàn □ shì zhǐ jīng jí hé de yú yùn suàn hòu zài qǔ bì bāo ， jí □， zé □ shì yī gè bù 'ěr dài shù , yě chēng wéi tuò pū kōng jiān 〈□ ,□〉 de zhèng guī bì jí dài shù 。 lèi sì dì ， dāng qǔ □ ={□□□│□ shì zhèng guī de kāi jí }。 suǒ wèi zhèng guī de kāi jí □ , shì zhǐ □。 zài dìng yì yùn suàn :□ ,□∧□ =□∩□；□， zé cǐ shí □ yě shì yī gè bù 'ěr dài shù , yě chēng wéi zhèng guī kāi jí dài shù 。
zài gàilǜ lùn zhōng , shè □ = ｛ □│□ shì suí jī shì jiàn ｝ , jí suǒ yòu suí jī shì jiàn de quán tǐ 。 bù kě néng shì jiàn jí bì rán shì jiàn jūn shì zuò suí jī shì jiàn 。 zhè : Boolean algebra, Boolean Algebra (BA) bù 'ěr dài shù dìng lǜ biǎo shì bù 'ěr dài shù guǎng yì bù 'ěr dài shù gōng lǐ huà bù 'ěr dài shù ruò fēn pèi bù 'ěr dài shù fàn bù 'ěr dài shù gōng lǐ tǐ xì bù 'ěr dài shù de jī běn guī zé