วันพุธที่ 22 กุมภาพันธ์ พ.ศ. 2555

พีชคณิตบูลีน

หลักการเบื้องต้นของพีชคณิตบูลีน
ตัวคงที่ (Switching Constant) จะประกอบด้วย 2 สภาวะ คือ 0 และ 1 ซึ่งจะใช้แทนระดับของลอจิก

ตัวแปร (Switching Variable) คือ ตัวอักษร หรือสัญลักษณ์ใด ๆ ที่ใช้แทนการเปลี่ยนแปลงทางลอจิก เช่น A, B, C, D,… , , , , ,… ซึ่งการเปลี่ยนแปลงของตัวแปรเหล่านี้จะมีการเปลี่ยนแปลงได้เพียงสองสภาวะเท่านั้น เช่น ให้ A เป็นตัวแปรใด ๆ ของพีชคณิตบูลีน

ถ้า A ¹ 0 แสดงว่าค่า A เป็น 1

ถ้า A ¹ 1 แสดงว่าค่า A เป็น 0

ซึ่งค่าดังกล่าวนี้จะเรียกว่า ค่าความจริงของตัวแปร A หรือเรียกสั้น ๆ ว่า ค่าของ A”

ตัวกระทำ (Operators) หรือเรียกว่าตัวดำเนินการ ซึ่งมีพื้นฐานหลัก ๆ เพียง 3 ตัว คือ

1. AND ใช้สัญลักษณ์คือ จุด ( × ) หรืออาจไม่มีจุดก็ได้ เมื่อตัวคงที่ 2 ตัว AND กัน ผลของการกระทำ AND จะเป็น 1 ได้ก็ต่อเมื่อตัวคงที่ทั้งสองต้องเป็น 1 นั่นคือ

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

2. OR ใช้สัญลักษณ์คือ บวก ( + ) เมื่อตัวคงที่ 2 ตัว OR กัน ผลของการกระทำ OR จะเป็น 1 ได้ก็ต่อเมื่อตัวคงที่ตัวใดตัวหนึ่งเป็น 1 หรือทั้งสองตัวเป็น 1 นั่นคือ

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

3. NOT หรือ INVERTER ใช้สัญลักษณ์คือ พราม ( prime : ¢ ) หรือ บาร์ (bar : ) แต่ส่วนใหญ่จะนิยมใช้สัญลักษณ์ bar เมื่อตัวคงที่ ถูก NOT ผลของการ NOT จะทำให้ตัวคงที่ตัวมีค่าตรงกันข้ามกับค่าเดิม นั่นคือ

1 หรือ 1¢ = 0

0 หรือ 0¢ = 1

เทอม (Terms) หมายถึง กลุ่มของตัวแปรที่ถูกกระทำกันด้วยตัวกระทำ เช่น A × B , ( A + B + C) , X × Y × Z เป็นต้น

นิพจน์ (Expression) หมายถึง กลุ่มเทอมที่ถูกกระทำกันด้วยตัวกระทำ เช่น

A × B + C × D เป็นต้น ปกติเรามักจะเรียกว่า Logic Expression หรือ Boolean Expression โดยมีหลักการตีค่าของลำดับความสำคัญของการกระทำในนิพจน์ (Expression) ต่าง ๆ ดังนี้

1. ถ้าไม่มีวงเล็บให้ถือการกระทำของ “AND” ก่อน “OR” เช่น

A × B + C × D

อันดับแรกให้ทำ A × B และ C × D ก่อน

อันดับที่สอง ให้เอาผลของ (A × B) มา OR กับ ผลของ (C × D)

2. ถ้ามีวงเล็บ ให้กระทำในวงเล็บก่อน โดยถ้ามีวงเล็บซ้อนกันหลาย ๆ ชั้น ให้กระทำในวงเล็บชั้นในที่สุดก่อนตามลำดับออกมา เช่น

(A + B) ×{A×(B+C)+D}

อันดับแรก ให้ทำ (B+C) ก่อน แล้วมา AND กับ A ผลลัพธ์ที่ได้จึงมา OR กับ D

อันดับที่สอง ให้ทำ (A+B) แล้วจึงนำผลลัพธ์ มา AND กับผลลัพธ์ของวงเล็บปีกกา

3. ตัวแปรหรือสัญลักษณ์ตัวอักษรที่อยู่ในแต่ละเทอมของ Expression ที่เหมือนกัน จะถือว่าเป็นตัวแปรตัวเดียวกัน โดยจะคิดให้เหลือเพียงตัวแปร 1 ตัวเท่านั้น

4. สำหรับตัวกระทำ “NOT” จะกระทำก่อนหรือหลัง “AND” และ “OR” นั้น ขึ้นอยู่กับ ความยาวของ Bar ว่าครอบคลุมเพียงตัวแปรเดียวหรือทั้งหมด เช่น

A × B หรือ A × B¢ ให้ NOT B ก่อน แล้วจึง AND กับ A





A × (B+C) หรือ (A × (B+C) ¢) ¢ ให้ทำ (B+C) ก่อน แล้วจึงเอาผลลัพธ์ไป NOT ผลลัพธ์ที่ได้นำไป AND กับ A จากนั้นจึงผ่าน NOT อีกครั้งเป็นครั้งสุดท้าย

ฟังค์ชัน (Function) หมายถึง สมการที่แสดงให้ทราบถึงผลการถูกกระทำกันของเทอมและนิพจน์ต่าง ๆ ปกติ เรียกว่า Logic Function หรือ Boolean Function เช่น

F = A × B + C

f(X,Y,Z) = X × Y + X¢× Z

ฝั่งทางด้านซ้ายมือ เป็นผลลัพธ์ที่ได้ เรียกว่า Output or Logic output

ฝั่งทางด้านขวามือ เป็นกลุ่มของตัวแปรที่ประกอบด้วย Term หรือ Expression เป็นตัวถูกกระทำ เรียกว่า Input หรือ Logic input

ตารางความจริง (Truth Table) หมายถึง ารางที่แสดงผลของค่าความจริงของนิพจน์หรือ Logic output เมื่อค่าตัวแปรต่าง ๆใน Function มีค่าเปลี่ยนแปลงไปต่าง ๆ กัน เช่น

A
B
A×B
A
B
A+B
A
A
0
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
1


ตัวอย่างที่ 4.1 จงเขียนตารางความจริงของ F = X × Y + X × Z

X
Y
Z
X×Y
X
X × Z
F
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
0
1
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
1
1
1
1
1
0
0
1



4.3 สูตรและกฎของพีชคณิตบูลีน

ทฤษฎีบทที่ 1 กฎการสลับที่ (Commutative law)

a) A + B = B + A

b) A × B = B ×A

ทฤษฎีบทที่ 2 กฎการจัดหมู่ (Associative law)

a) (A + B) + C = A + (B + C)

b) (A × B) × C = A × (B × C)

ทฤษฎีบทที่ 3 กฎการกระจาย (Distributive law)

a) A × (B + C) = A × B + A × C

b) A + (B × C) = (A + B) × (A + C)

ทฤษฎีบทที่ 4 กฎเอกลักษณ์ (Identity law)

a) A + A = A

b) A × A = A

ทฤษฎีบทที่ 5 กฎการนิเสธ (Negation law)

a) A = A

b) A = A

ทฤษฎีบทที่ 6 กฎการลดรูปเยิ่นเย้อหรือการดูดกลืน (Redundance law or Absorption law)

a) A + A×B = A

b) A × (A + B) = A

ทฤษฎีบทที่ 7 คุณสมบัติเกี่ยวกับการกระทำระหว่างตัวคงที่กับตัวแปรใด ๆ

a) 0 + A = A

b) 1 × A = A

c) 1 + A = 1

d) 0 × A = 0

ทฤษฎีบทที่ 8

a) A + A = 1

b) A × A = 0

ทฤษฎีบทที่ 9

a) A + A×B = A + B

b) A × ( A + B) = A×B


ทฤษฎีบทที่ 10 ทฤษฎีของเดอมอร์แกน (De Morgan’s Theorem)

a) (A + B) = A× B

b) (A ×B) = A + B

ทฤษฎีบทเพิ่มเติม คุณสมบัติการกลืนหายหรือความสอดคล้องกัน (Consensus law)

a) A ×B + A × C + B × C = A × B + A × C

b) (A + B) × (A + C) × (B + C) = (A + B) × (A + C)


การพิสูจน์ทฤษฎีบทของพีชคณิตบูลีนนั้น เราสามารถพิสูจน์ได้หลายวิธี แต่มีวิธีหนึ่งที่ง่ายและเห็นได้ชัดเจนที่สุด คือการใช้ตารางความจริงในการพิสูจน์

ตัวอย่างที่ 4.2 จงพิสูจน์ว่าทฤษฎีของเดอมอร์แกนเป็นความจริง

a) (A + B) = A× B

b) (A ×B) = A + B

พิสูจน์ โดยใช้ตารางความจริง

a) (A + B) = A× B

=

A
B
A + B
A + B
A
B
A× B
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0


b) (A ×B) = A + B

=

A
B
A × B
A × B
A
B
A+ B
0
0
0
1
1
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
1
0
0
0
0


การพิสูจน์ทฤษฎีบทของพีชคณิตบูลีนอีกวิธีหนึ่งนั้น เป็นการนำเอาทฤษฎีบทอื่น ๆ ที่เรายอมรับแล้วมาใช้ในการพิสูจน์

ตัวอย่างที่ 4.3 จงพิสูจน์ว่าคุณสมบัติการกลืนหายเป็นความจริง

a) A ×B + A × C + B × C = A × B + A × C

b) (A + B) × (A + C) × (B + C) = (A + B) × (A + C)

พิสูจน์ โดยใช้ทฤษฎีบทอื่น ๆ

A ×B + A × C + B × C = A × B + A × C + B × C × 1 (บท 7a)

= A × B + A × C + B × C × (A + A) (บท 8a)

= A × B + A × C + A ×B × C + A ×B × C (บท 3a)

= (A×B + A×B× C) + (A ×C + A ×B × C)

= A×B×(1 + C) + A ×C × (1 + B) (บท 3a)

= A×B×1 + A ×C × 1 (บท 7c)

= A×B + A ×C (บท 7b)

ไม่มีความคิดเห็น:

แสดงความคิดเห็น