Tugas 6 Lingga 1903015140 Teorema DeMorgan's

De-Morgan's Theorem

Dalam logika proposisional dan aljabar Boolean, hukum De Morgan adalah sepasang aturan transformasi yang keduanya merupakan aturan inferensi yang valid. Mereka dinamai Augustus De Morgan, seorang matematikawan Inggris abad ke-19. Aturan memungkinkan ekspresi konjungsi dan disjungsi murni dalam hal satu sama lain melalui negasi.

Aturan dapat dinyatakan dalam bahasa Inggris sebagai:

• Negasi dari disjungsi adalah konjungsi dari negasi
• Negasi dari konjungsi adalah disjungsi dari negasi

atau

• Komplemen gabungan dua himpunan sama dengan perpotongan komplemennya
• Komplemen perpotongan dua himpunan sama dengan gabungan komplemennya

atau

• not (A or B) = (not A) and (not B)
• not (A and B) = (not A) or (not B),

di mana "A or B" adalah "inklusif or" yang berarti setidaknya salah satu dari A atau B daripada "eksklusif or" yang berarti persis salah satu dari A atau B.

Dalam teori himpunan dan aljabar Boolean, ini ditulis secara formal sebagai:

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

di mana

•  dan  adalah himpunan,
•  adalah komplemen dari ,
•  adalah intersection/persimpangan, dan
•  adalah union/gabungan.

Dalam bahasa formal, aturan ditulis sebagai

$$
{\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q),}

dan

${\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)}$

dimana

• P dan Q adalah proposisi,
•  adalah operator logika negasi (NOT),
•  adalah operator logika konjungsi (AND),
•  adalah operator logika disjungsi (OR),
• adalah simbol metalogis yang artinya "dapat diganti dengan pembuktian logis dengan".

Penerapan aturan termasuk penyederhanaan ekspresi logis dalam program komputer dan desain sirkuit digital. Hukum De Morgan adalah contoh dari konsep dualitas matematika yang lebih umum.

Seorang matematikawan terkenal DeMorgan menemukan dua teorema terpenting dari aljabar boolean. Teorema DeMorgan digunakan untuk verifikasi matematis dari ekivalensi gerbang NOR dan negatif-AND dan gerbang negatif-OR dan NAND. Teorema ini memainkan peran penting dalam memecahkan berbagai ekspresi aljabar boolean. Pada tabel di bawah ini, operasi logis untuk setiap kombinasi variabel input didefinisikan.

Input variables		Output Condition
A	B	AND	NAND	OR	NOR
0	0	0	1	0	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	0	1	0

Aturan teorema De-Morgan dihasilkan dari ekspresi Boolean untuk OR, AND, dan NOT menggunakan dua variabel input x dan y. Teorema pertama Demoorgan mengatakan bahwa jika kita melakukan operasi AND dari dua variabel input dan kemudian melakukan operasi NOT hasilnya, hasilnya akan sama dengan operasi OR komplemen dari variabel tersebut. Teorema kedua DeMorgan mengatakan bahwa jika kita melakukan operasi OR dari dua variabel input dan kemudian melakukan operasi NOT hasilnya, hasilnya akan sama dengan operasi AND dari komplemen variabel tersebut.

De-Morgan's First Theorem

Menurut teorema pertama, hasil komplemen dari operasi AND sama dengan operasi OR dari komplemen variabel tersebut. Jadi, fungsi ini ekuivalen dengan fungsi NAND dan merupakan fungsi negatif-OR yang membuktikan bahwa (A.B)' = A'+B' dan kita dapat menunjukkannya menggunakan tabel berikut.

Inputs		Output For Each Term
A	B	A.B	(A.B)'	A'	B'	A'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

De-Morgan's Second Theorem

Menurut teorema kedua, hasil komplemen dari operasi OR sama dengan operasi AND dari komplemen variabel tersebut. Jadi, fungsi tersebut ekuivalen dengan fungsi NOR dan merupakan fungsi AND negatif yang membuktikan bahwa (A+B)' = A'.B' dan kita dapat menunjukkannya menggunakan tabel kebenaran berikut.

Inputs		Output For Each Term
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

Example 1: (A.B.C)'

(A.B.C)'=A'+B'+C'

Example 2: (A+B+C)'

(A+B+C)'=A'.B'.C

Example 3: ((A+BC')'+D(E+F')')'

Untuk menerapkan teorema DeMorgan pada bentuk ini, kita harus mengikuti bentuk berikut:

1) Dalam bentuk lengkap, pertama, kita temukan suku-suku di mana kita dapat menerapkan teorema DeMorgan dan memperlakukan setiap suku sebagai variabel tunggal.

Jadi,

2) Selanjutnya, kita terapkan teorema pertama DeMorgan. Jadilah,

3) Selanjutnya, kami menggunakan aturan nomor 9, yaitu, (A=(A')') untuk membatalkan bar ganda.

4) Selanjutnya, kita terapkan teorema kedua DeMorgan. Jadi,

5) Sekali lagi terapkan aturan nomor 9 untuk membatalkan bar ganda.

Sekarang, bentuk ini tidak memiliki suku di mana kita dapat menerapkan aturan atau teorema apa pun. Jadi, ini adalah bentuk terakhir.

Example 3: (AB'.(A + C))'+ A'B.(A + B + C')'

Contoh Soal & jawaban: 

1. Sebagai gerbang universal, gerbang NOR dapat diubah menjadi gerbang AND dengan membalik input.....

A. sebelum diterapkan ke gerbang NOR

B. setelah diterapkan ke gerbang NOR

C. sebelum diterapkan ke gerbang AND

D. sebelum diterapkan ke gerbang AND

Jawaban: A.

2. NAND & NOR dianggap sebagai gerbang Universal karena mereka mampu melakukan fungsi logis yang berkaitan dengan.....

A. gerbang AND

B. gerbang ATAU

C. gerbang BUKAN

D. Semua jawaban Benar

Jawaban: D.

3. Manakah di antara ekspresi boolean di bawah ini yang tidak mematuhi teorema De-Morgan?

A. X+Y = X . Y

B. X.Y = X + Y

C. X.Y = X+Y

D. Semua jawaban salah

Jawaban: C.

4. Salah satu teorema De Morgan menyatakan bahwa X+Y = X . Y, yang tidak memiliki perbedaan diantaranya adalah.....

A. Gerbang NOR dan gerbang AND dengan input terbalik 

B. Gerbang NAND dan gerbang OR dengan input terbalik 

C. Gerbang AND dan gerbang NOR dengan input terbalik 

D. Gerbang NOR dan gerbang NAND dengan input terbalik

Jawaban: A.

5. Untuk rangkaian logika yang ditunjukkan pada gambar, output Y diberikan oleh.....

A. (A B + C) DE

B. (A + B) C + DE

C. AB + C(D + E)

D. (A + B) C + D + E

Jawaban: B.

6. Dalam aljabar boolean, operasi OR dilakukan menggunakan sifat?

A. Sifat asosiatif

B. Sifat komutatif

C. Sifat distributif

D. Semua yang Disebutkan

Jawaban: D.

7. Bentuk untuk Absorbtion Law diberikan oleh.....

A. A + AB = A

B. A + AB = B

C. AB + AA’ = A

D. A + B = B + A

Jawaban: A.

8. Menurut hukum boolean: A + 1 = 

A. 1

B. A

C. 0

D. A’

Jawaban: A.

9. Aljabar logika disebut sebagai.....

A. Logika numerik

B. Aljabar Boolean

C. Logika aritmatika

D. Bilangan Boolean

Jawaban: C.

10. Aljabar Boolean dapat digunakan.....

A. Untuk merancang komputer digital

B. Dalam membangun simbol logika

C. Teori sirkuit

D. Membangun fungsi aljabar

Jawaban: A.

11. 5. Nilai ..... diwakili oleh ekspresi Boolean.

A. Positif

B. Rekursif

C. Negatif

D. Boolean

Jawab: D.

12. Apa bentuk canonical dari Ekspresi Boolean?

A. OR and XOR

B. NOR and XNOR

C. MAX and MIN

D. SOM and POM

Jawab: D.

13. Manakah dari berikut ini yang merupakan gerbang logika universal?

A. OR and NOR

B. AND

C. NAND and NOR

D. NOT

Jawaban: C.

14. Gerbang logika yang memberikan output tinggi untuk input yang sama.....

A. NOT

B. X-NOR

C. AND

D. XOR

Jawaban: B.

15. A + B = B + A; AB = BA mewakili hukum yang mana?

A. Commutative

B. Associative

C. Distributive

D. Idempotence

Jawaban: A.

16. (A + B) + C = A + (B + C); (AB)C = A(BC) mewakili hukum yang mana?

A. Commutative

B. Associative

C. Distributive

D. Idempotence

Jawaban: B.

17. A(B + C) =AB + AC; A + BC = (A + B)(A + C) mewakili hukum yang mana?

A. Commutative

B. Associative

C. Distributive

D. Idempotence

Jawaban: C.

18. A + AB = A; A(A + B) = A mewakili hukum yang mana?

A. Idempotence

B. Absorption

C. Associative

D. Commutative

Jawaban: B.

19. Aljabar Boolean, (A.A̅) + A =?

A. A

B. 0

C. A̅

D. 1

Jawaban: A.

20. Aljabar Boolean mematuhi.....

A. hukum komutatif saja

B. hukum distributif saja

C. hukum asosiatif saja

D. hukum asosiatif, distributif, dan komutatif

Jawaban: D.

Sumber: 

    > https://onlinelearning.uhamka.ac.id

    > https://www.javatpoint.com/de-morgans-theorem-of-boolean-algebra-in-digital-electronics

    > https://en.wikipedia.org/wiki/De_Morgan%27s_laws

    > https://www.careerride.com/view/universal-gates-de-morgans-theorem-mcqs-with-answers-

        22495.aspx

    > https://testbook.com/objective-questions/mcq-on-demorgans-theorem--5eea6a0d39140f30f369e1f4

    > https://www.studocu.com/row/document/aljamaa%D8%A9-aleslamy%D8%A9/logical-

        design/mcqs-chapter-3-multiple-choice-questions-for-gate-level-minimization/11354840

    > https://engineeringinterviewquestions.com/mcqs-on-boolean-algebra-answers/

    > https://engineeringinterviewquestions.com/mcqs-on-boolean-logic-operations-answers/

    > https://mcq.electronics-club.com/boolean-algebra-mcq/

    > https://testbook.com/objective-questions/mcq-on-boolean-algebra--5eea6a1439140f30f369f286