布爾代數(shù)
布爾代數(shù)是代數(shù)的一個(gè)分支幼东，其中的變量和常數(shù)的值正好有兩個(gè)：真和假顿乒，通常分別表示為1和0削樊。
內(nèi)容
1 運(yùn)算符
2 為什么布爾代數(shù)對(duì)ACSL學(xué)生很重要青团？
3 法則
3.1 先后次序
3.2 基本特征
4 示例問題
4.1 問題1：簡(jiǎn)化表達(dá)式
4.2 問題2：尋找解決方案
5 在線資源
5.1 網(wǎng)站
5.2 視頻
運(yùn)算符
布爾代數(shù)的基本運(yùn)算符是AND, OR, 和NOT。次要的運(yùn)算符是eXclusive OR（通常稱為XOR）和eXclusive NOR（XNOR蹄梢，有時(shí)稱為等價(jià)）疙筹。它們是次要的，因?yàn)樗鼈兛梢杂苫具\(yùn)算符組成禁炒。
兩個(gè)值的AND只有在兩個(gè)值都是真的時(shí)候才是真的而咆。它被寫成xy或x?y。所有可能的輸入的和的值顯示在下面的真值表中幕袱。
x y xy
0 0 0
0 1 0
1 0 0
1 1 1
只要其中一個(gè)或兩個(gè)值都是真的暴备，兩個(gè)值的OR就是真的。它被寫成x+y们豌。所有可能的輸入的or值顯示在下面的真值表中涯捻。
x y x+y
0 0 0
0 1 1
1 0 1
1 1 1
一個(gè)值的NOT是它的反面；也就是說望迎，一個(gè)真值的NOT是假的障癌，而一個(gè)假值的NOT是真的。它被寫成xˉˉ或?x辩尊。所有可能的輸入的not值顯示在下面的真值表中涛浙。
x xˉˉ
0 1
1 0
兩個(gè)值的XOR是真的，只要這兩個(gè)值是不同的摄欲。它使用⊕運(yùn)算符轿亮，并且可以從基本運(yùn)算符中建立。x⊕y=xyˉˉ+xˉˉy 對(duì)于所有可能的輸入胸墙，xor的值顯示在下面的真值表中我注。
x y x⊕y
0 0 0
0 1 1
1 0 1
1 1 0
兩個(gè)數(shù)值的XNOR在數(shù)值相同時(shí)為真。它是XOR函數(shù)的NOT迟隅。它使用⊙運(yùn)算符：x⊙y=x⊕yˉ但骨。xnor可以由基本運(yùn)算符建立励七。x⊙y= xy + xˉˉyˉˉ 對(duì)于所有可能的輸入，xnor的值顯示在以下真值表中嗽冒。
x y x⊙y
0 0 1
0 1 0
1 0 0
1 1 1
就像代數(shù)有簡(jiǎn)化和評(píng)估表達(dá)式的基本規(guī)則一樣呀伙，布爾代數(shù)也有补履。
為什么布爾代數(shù)對(duì)ACSL的學(xué)生很重要添坊？
布爾代數(shù)對(duì)程序員、計(jì)算機(jī)科學(xué)家和普通人都很重要箫锤。
對(duì)于程序員來說贬蛙，布爾表達(dá)式用于條件反射和循環(huán)。例如谚攒，下面這段代碼對(duì)不是3的倍數(shù)的偶數(shù)進(jìn)行求和阳准，當(dāng)和達(dá)到100時(shí)停止。
s = 0
x = 1
while (s < 100):
if (x % 2 == 0) 和 (x % 3 != 0)
else s = s + x
x = x + 1
條件語句s < 100和布爾表達(dá)式的2個(gè)條件語句(x % 2 == 0)和(x % 3 != 0)都會(huì)評(píng)估為真或假馏臭。
對(duì)于計(jì)算機(jī)科學(xué)家來說野蝇，布爾代數(shù)是構(gòu)成計(jì)算機(jī)硬件的數(shù)字電路的基礎(chǔ)。數(shù)字電子學(xué)類別涉及一個(gè)電路的圖形表示括儒。該電路通常是最容易理解和評(píng)估的绕沈，將其轉(zhuǎn)換為布爾代數(shù)表示。
一般人在互聯(lián)網(wǎng)搜索引擎中輸入搜索詞時(shí)帮寻，都會(huì)使用布爾代數(shù)乍狐，而他們可能并不知道自己正在這樣做。例如固逗，搜索表達(dá)式j(luò)aguar speed -car被搜索引擎解析為布爾表達(dá)式 "jaguar "和 "car"浅蚪，而不是 "speed"；它返回有關(guān)jaguar動(dòng)物速度的網(wǎng)頁烫罩，而不是jaguar汽車惜傲。
定律
布爾代數(shù)的定律是兩個(gè)布爾項(xiàng)之間的同一性，如x+(y+z)=(x+y)+z贝攒，其中布爾項(xiàng)被定義為由變量盗誊、常數(shù)0和1，以及運(yùn)算和饿这、或浊伙、非、xor和xnor構(gòu)成的表達(dá)式长捧。
像普通的代數(shù)一樣嚣鄙，小括號(hào)被用來分組術(shù)語。當(dāng) "不 "用高架橫線表示時(shí)串结，橫線下的項(xiàng)就隱含了一個(gè)分組哑子。也就是說舅列，x?y+zˉˉ 被評(píng)估為寫成x?(y+z)ˉˉ
優(yōu)先權(quán)的順序
操作符的優(yōu)先級(jí)順序是：不是；然后是and卧蜓；然后是xor和xnor帐要；最后是or。具有相同優(yōu)先級(jí)的運(yùn)算符從左到右進(jìn)行計(jì)算弥奸。
基本特征
交換律--兩個(gè)獨(dú)立項(xiàng)的應(yīng)用順序并不重要榨惠，x+y=y+x x?y=y?x
關(guān)聯(lián)法則--在一個(gè)表達(dá)式中重新組合項(xiàng)并不改變表達(dá)式的值。
(x+y)+z=x+(y+z) x?(y?z)=(x?y)?z
同位素定律--一個(gè)與自身或'或'和'的項(xiàng)等于該項(xiàng)盛霎。
消滅定律--與1相接的項(xiàng)為1赠橙；與0相接的項(xiàng)為0。
相同法則--一個(gè)被0或與1相配的項(xiàng)總是等于該項(xiàng)愤炸。
補(bǔ)碼法則--一個(gè)被補(bǔ)碼的項(xiàng)等于1期揪，一個(gè)被補(bǔ)碼的項(xiàng)等于0。
吸收法 - 復(fù)雜的表達(dá)式可以通過吸收同類項(xiàng)而簡(jiǎn)化為簡(jiǎn)單的表達(dá)式规个。
x+xy=x
x+xˉˉy=x+y
x(x+y)=x
分布式定律--可以用乘法或因數(shù)--來計(jì)算凤薛。
分布式定律--將一個(gè)表達(dá)式相乘或因式分解是可以的。
x?(y+z)=xy+xz
(x+y)?(p+q)=xp+xq+yp+yq
(x+y)(x+z)=x+yz
DeMorgan定律--一個(gè)被否定的或（和）表達(dá)式等于每個(gè)項(xiàng)的否定的和（或）诞仓。
x+yˉˉ=xˉˉ?yˉˉ x?yˉˉ=xˉˉ+yˉˉ
雙重否定--被顛倒兩次的項(xiàng)等于原來的項(xiàng)缤苫。xˉ ˉ=x
XOR和XNOR的關(guān)系 x⊙y=x⊕yˉ =x⊕yˉˉ=xˉˉ⊕y
樣本問題
這類問題的典型形式是 "給定一個(gè)布爾表達(dá)式，盡可能地簡(jiǎn)化它 "或 "給定一個(gè)布爾表達(dá)式狂芋，找出所有可能的輸入值榨馁，使表達(dá)式為真"。簡(jiǎn)化意味著用最少的運(yùn)算符寫出一個(gè)等價(jià)的表達(dá)式帜矾。
問題1：簡(jiǎn)化表達(dá)式
問題：盡可能地簡(jiǎn)化以下表達(dá)式翼虫。
A(A+B)ˉˉˉ+BAˉˉˉ
解決方案。
簡(jiǎn)化的過程如下屡萤。
A(A+B)ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ+BAˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
=(A(A+B)ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ)?(BAˉˉˉˉˉˉˉˉˉˉˉˉ) (德摩根法則)
=(A(A+B))?(Bˉˉˉˉ+Aˉˉˉˉˉˉˉˉ) (雙重否定珍剑；DeMorgan定律)
=A?(Bˉˉˉˉ+A)(吸收；雙重否定)
=A(吸收)
問題2：尋找解決方案
問題：找出使下列表達(dá)式為真的所有順序?qū)Γˋ,B）：(A+B)ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ+AˉˉˉˉBˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
解決方案死陆。
通常有兩種方法來解決這類問題招拙。一種方法是盡可能地簡(jiǎn)化表達(dá)式，直到顯而易見地找到解決方案措译。另一種方法是為所有可能的輸入創(chuàng)建一個(gè)真值表别凤，并為每個(gè)子表達(dá)式設(shè)置列。
簡(jiǎn)化的方法如下领虹。
(A+B)ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ+AˉˉˉˉBˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
=A+Bˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ?AˉˉˉˉBˉˉˉˉˉˉˉˉ
=(A+B)?(Aˉˉˉˉˉˉˉˉ+Bˉˉˉˉ)
=(A+B)?(A+Bˉˉˉˉ)
=AA+ABˉˉˉˉ+BA+BBˉˉˉˉ
=A+A(Bˉˉˉˉ+B)+0
=A+A(1)
=A+A
=A
這意味著只要A為真规哪，所有輸入都有效：(1,0)和(1,1)
真值表的方法如下。每一列是對(duì)另外兩列進(jìn)行基本運(yùn)算的結(jié)果塌衰。
1 #2 #3 #4 #5 #6 #7 #8
第1列诉稍、第2列的OR 第3列的NOT 第1列的ADD 第1列蝠嘉、第2列的OR 第4列、第6列的NOT 第7列的OR
a b a+b a+bˉˉˉˉˉˉˉˉˉˉˉˉˉˉ aˉˉˉˉ aˉˉˉˉb a+bˉˉˉˉˉˉˉˉˉˉˉˉˉˉ+aˉˉˉˉb a+bˉˉˉˉˉˉˉˉˉˉˉˉˉˉ+aˉˉˉˉbˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
0 0 0 1 1 0 1 0
0 1 1 0 1 1 1 0
1 0 1 0 0 0 0 1
1 1 1 0 0 0 0 1
最右邊的一列是我們要解決的表達(dá)式杯巨；對(duì)于第3和第4行蚤告，輸入是(1,0)和(1,1)，它是真的服爷。
在線資源
網(wǎng)站
Ryan's Tutorials的一部分是關(guān)于布爾代數(shù)的一個(gè)很好的在線教程杜恰。有許多在線布爾計(jì)算器。這個(gè)給出了真值表的計(jì)算器层扶。這個(gè)有廣告的鏈接也簡(jiǎn)化了NOT計(jì)算器箫章，并使用了！镜会。
視頻
下面的YouTube視頻顯示了ACSL的學(xué)生和顧問在解決以前的一些問題。要訪問帶有視頻的YouTube頁面终抽，請(qǐng)點(diǎn)擊圖標(biāo)中的視頻標(biāo)題戳表。(你也可以通過點(diǎn)擊圖片中間的箭頭直接播放視頻；但是昼伴，你可能想在更大的范圍內(nèi)觀看視頻匾旭，因?yàn)樗诎装迳系臅鴮憽? 有些視頻包含廣告；ACSL對(duì)這些廣告不負(fù)責(zé)任圃郊，也不接受任何形式的廣告補(bǔ)償价涝。
