PENYEDERHANAAN LOGIKA

BAB I PENDAHULUAN

1.1  Latar Belakang

Logika berasal dari bahasa yunani logos yang berarti ilmu untuk berfikir dengan benar. Dan manusia mampu mengembangkan pengetahuan karena mempunyai bahasa dan kemampuan. Untuk dapat menarik konklusi yang tepat, diperlukan kemampuan menalar. Kemampuan menalar adalah kemampuan untuk menarik yang tepat dari bukti-bukti yang ada, dan menurut aturan-aturan tertentu. Informatika adalah disiplin ilmu yang mempelajari transpormasi fakta berlambang yaitu data maupun informasi pada mesin berbasis komputasi.

1.2  Rumusan Masalah

1.      Apa yang dimaksud dengan operasi penyederhanaa?

2.      Bagaimana cara menghilangkan perangkai implikasi dan ekuivalensi menjadi perangkai dasar?

3.      Bagaimana cara penggunaan perangkai dasar?

1.3  Tujuan

Ø  Agar dapat memahami apa itu operasi penyederhanaan.

Ø  Agar dapat memahami bagaimana cara menghilangkan perangkai implikasi dan ekuivalensi menjadi perangkai dasar.

Ø  Agar dapat memahami bagaimana cara penggunaan perangkai dasar.

BAB II Pembahasan

            Makalah ini akan membahas penggunaan hukum-hukum logika pada operasi logika yang dinamakan penyederhanaan (simplifying). Sebenarnya berbagai macam ekuivalensi dari berbagai ekspresi logika memberikan kemudahan bagi penyederhanaan karena bentuk ekspresi logika yang rumit dapat disederhanakan.

Tabel Hukum-hukum Pokok Logika

HUKUM	NAMA
A˄1≡A	Identity of ˄ (Identity Laws)
A˅0≡A	Zero of ˅ (Identity Laws)
A˅1≡1	Identity of ˅ (Dominition Laws)
A˄0≡0	Zero of  ˄ (Dominiton Laws)
A˅¬A≡1	Tautology (Excluded Middle Laws)
A˄¬A≡0	Law of Contradiction
A˅A≡A	Idempotence Laws
A˄A≡A	Idempotence Laws
¬¬A≡A	Law of Double Negation
A˄B≡B˄A	Commutativity (Commutative Laws)
A˅B≡B˅A	Commutativity (Commutative Laws)
(A˄B)˄C≡A˄(B˄C)	Associativity (assosiative Laws)
(A˅B)˅C≡A˅(B˅C)	Associativity (assosiative Laws)
A˄(B˅C)≡(A˄B)˅(A˄C)	Distributivity (Distributive Laws)
A˅(B˄C)≡(A˅B)˄(A˅C)	Distributivity (Distributive Laws)
A˄(A˅B)≡A	Absorption
A˅(A˄B)≡A	Absorption
A˄(¬A˅B)≡A˄B	Absorption
A˅(¬A˄B)≡A˅B	Absorption
¬(A˄B)≡¬A˅¬B	De Morgan's Law
¬(A˅B)≡¬A˄¬B	De Morgan's Law
(A˄B)˅(A˄¬B)≡A
A→B≡ ¬A˅B
A→B≡ ¬(A˄¬B)
A↔B≡(A˄B)˅(¬A˄¬B)
A↔B≡(A→B)˄(B→A)

2.1            Operasi Penyederhanaan

Operasi penyederhanaan merupakan penyederhanaan ekspresi logika atau bentuk-bentuk logika yang dibuat sesederhana mungkin dan sudah tidak dimungkinkan dimanipulasi lagi. Operasi menggunakan hukum-hukum ekuivalensi logis. Selanjutnya perhatikan operasi penyederhanaan berikut dengan hukum yang digunakan tertulis di sisi kanannya.

Contoh

1.      (AÚ0) Ù ( AÚØA)

º A Ù ( AÚØA)                                               Zero of ˅        

º A Ù1                                                            Tautology

º A                                                                  Identity of ˄

2.      AÚ(AÙB)

º (AÙ1)Ú(AÙB)                                              Identity of ˄

º AÙ(1ÚB)                                                      Distributivity

º AÙ1                                                             Identity of Ú

º A                                                                  Identity of Ù

Operasi penyederhanaan dengan menggunakan hukum-hukum logika dapat digunakan untuk membuktikan suatu ekspresi logika Tautologi, Kontradiksi, maupun Contingent. Jika hasil akhir penyederhanaan ekspresi logika adalah 1, maka ekspresi logika tersebut adalah tautologi. Jika hasil yang diperoleh adalah 0, berarti ekspresi logika tersebut kontradiksi. Jika hasilnya tidak 0 ataupun 1, maka ekspresi logikanya adalah contingent.

Contoh :

1.   [(AÞB)ÙA]ÞB

º [(ØAÚB)ÙA] Þ B                   ingat pÞq º ØpÚq

º Ø[(ØAÚB)ÙA] Ú B                  ingat pÞq º ØpÚq

º [(AÙØB)ÚØA] Ú B                  Law of Double Negation and De Morgan’s Law

º [(AÚØA)Ù(ØBÚØA)] Ú B       Distributivity

º [1Ù(ØAÚØB)] Ú B                   Idempotence

º (ØAÚØB)ÚB                            Identity of Ù

º ØAÚ(ØBÚB)                            Associativity

º ØAÚ1                                       Idempotence Laws

º 1                                               Identity of Ú

Karena hasil akhirnya 1, maka ekspresi logika diatas adalah tautologi.

2.   (AÚB) Ù [(ØA) Ù (ØB)]

º (AÚB)Ù(ØAÙØB)                                                       

º [(AÚB)ÙØA]Ù[(AÚB)ÙØB]                            Distributivity

º [(AÙØA)Ú(BÙØA)]Ù[(AÙØB)Ú(BÙØB)]       Distributivity

º [0Ú(BÙØA)]Ù[(AÙØB)Ú0]                              Negation

º (ØAÙB)Ù(AÙØB)                                            Idempotence Laws

º (ØAÙA)Ù(BÙØB)                                            Assosiativity

º 0Ù0                                                                   Negation

º 0                                                                       Idempotence Laws

Hasil akhir 0, maka ekspresi logika diatas adalah kontradiksi.

3.   [(AÚB)ÙØA] Þ ØB

º [(AÙØA)Ú(BÙØA)] Þ ØB                              Distributivity

º [0 Ú (BÙØA)] Þ ØB                                       Negation

º (BÙØA) Þ ØB                                                Identity of Ù

º Ø(BÙØA) Ú ØB                                               ingat AÞB º ØAÚB

º (ØBÚA) Ú ØB                                                  De Morgan’s Laws

º (ØBÚØB)ÚA                                                    Assosiativity

º ØBÚA                                                              Idempotence Laws

Hasilnya bukan 0 atau 1,  ekspresi logika di atas adalah contingent.

2.2            Menghilangkan Perangkai Implikasi dan Ekuivalensi menjadi Perangkai Dasar

Untuk penyederhanaan pertama kali yang harus dihilangkan adalah perangkai implikasi dan perangkai ekuivalensi dan dijadikan kombinasi dari perangkai alamiah yaitu konjungsi, disjungsi, dan negasi. Jadi semua perangkai dapat dijelaskan hanya dengan perangkai dasar atau perangkai alamiah tersebut.

Ø  Dalam penyederhanaan,untuk menghilangkan perangkai implikasi dapat digunakan hukum logika, yaitu:

AÞB ≡ ¬A˅B

Ø  Dalam penyederhanaan untukmenghilangkan perangkai ekuivalensi dapat digunakan ekuivalensi logis berikut:

A⟺B ≡ (A˄B)˅(¬A˄¬B)

A⟺B ≡ (AÞB)˄(BÞA)

Contoh:

1.      ¬A→¬(A→~B)                            A→B≡¬A˅B

= ¬(¬A)˅¬(A→¬B)                A→B≡¬A˅B

= ¬(¬A)˅¬(¬A˄¬B)               De Morgan Law

= ¬ ¬A˅¬ ¬(A˄B)                  Law Of Double Negation

= A˅ (A˄B)                            Absorption

= A

2.      ((A→B)˄C)˅((C↔D)˄(B˅D))

=((¬A˅B)˄C)˅((C↔D)˄(B˅D))                                A→B=¬A˅B

=((¬A˅B)˄C)˅(((C→D)˄(D→C))˄(B˅D))               A↔B

=((¬A˅B)˄C)˅(((¬C˅D)˄(¬D˅C))˄(B˅D))              A→B=¬A˅B

=((¬A˅B)˄C)˅((¬C˅D)˄(¬D˅C)˄B˅D))                  hapus kurung

2.3      Penggunaan Perangkai Dasar

Perangkai dasar atau perangkai alamiah hanya ada 3, yakni ˅,˄, dan¬. Ketiga perangkai ini mampu menggantikan semua perangkai lainnya dengan mengkombinasikan ketiga perangkai tersebut. Oleh karena itu, perangkai dasar dapat juga disebut perangkai cukup. Ketiga perangkai dasar inilah yang membentuk gerbang-gerbang yang menjadi dasar sistem digital, yakni gerbang dan, gerbang atau, dan gerbang tidak.Peragkai cukup sebenarnya hanyaingin menunjukkan bahwa ekspresi atau bentuk logika yang merangkai aapasaja dapat diubah bentuknya menjadi ekspresi logika dengan memakai perangkai dasar atau perangkai alamiah. Yakni ˄, ˅ ,¬ bahkan ekspresologika dengan perangkai ˄ dapat diubah menjadi ˅ dan ¬, sedangkan bentuk logika dengan perangkai ˅ dapat diubah dengan memakai perangkai ˄ dan ¬. 

Perhatikan contoh berikut:

1.      ¬(A˄¬A)

≡ ¬A˅¬¬A                  De Morgan’s Law

                   ≡ ¬A˅A                      Law of Double Negation

                   ≡ 1                               Tautology

2.      ¬(A˅¬A)

≡¬A˄¬¬A                   De Morgan’s Law

≡¬A˄A                       Law of Double Negation

≡ 0                               Law of Contradiction

Sekarang bagaimana dengan perangkai Nand dan Nor. Apakah kedua perangkai tersebut perangkai cukup, dan dapat dijelaskan dengan ˄,˅, dan ¬. Sekarang dimulai dengan perangkai Nand yang sebenarnya dapat ditulis ¬(A˄B) dengan membuat table kebenaran sebagai berikut:

A	A	A|A		¬A
F	F	T		T
T	T	F		F

Perhatikan table kebenaran tersebut, hasilnya ternyata:

A|A ≡ ¬A

Perhatikan table kebenaran berikut ini:

A	B	A|B	(A|B)|(A|B)		A˄B
F	F	T	F		F
F	T	T	F		F
T	F	T	F		F
T	T	F	T		T

Jadi (A|B)|(A|B) ≡ A˄B

      Dengan demikian perangkai Nand tergolong perangkai cukup karena ia dapat dijelaskan dengan perangkai dasar. Sekarang bagaimana dengan perangkai Nor, yang sebenarnya dapat ditulis ¬(A˅B), apakah benar ia juga merupakan perangkai cukup. Lihatlah table kenenaran berikut:

A	A	A↓A		¬A
F	F	T		T
T	T	F		F

Perhatikan table kebenaran tersebut, hasilnya ternyata:

A↓A ≡ ¬A

Selanjutnya lihat table kebenaran berikut :

A	B	A↓B	(A↓B)↓(A↓B)		A˅B
F	F	T	F		F
F	T	F	T		T
T	F	F	T		T
T	T	F	T		T

Ternyata (A↓B)↓(A↓B) ≡ A˅B

      Jadi sebenarnya perangkai Nor juga perangkai cukup karena ia juga dapat dijelaskan dengan perangkai dasar. Selain itu ternyata perangkai Nand ekuivalen dengan perangkai Nor seperti yang dibuktikan dengan table kebenaran berikut:

A	A	A↓A	A|A
F	F	T	T
T	T	F	F

    Jadi  A↓A ≡ A|A

Tetapi bagaimana jika A↓B ≡ A|B, apakah memang benar terbukti dengan table kebenaran

A	B	A↓B	A|B
F	F	T	T
F	T	F	T
T	F	F	T
T	T	F	F

Ternyata tidak sama. Jadi perhatikan dengan baik variable proposisional yang melekat pada perangkai tersebut. Kelihatannya hasilnya sama, padahal ternyata tidak. 

Latihan Soal

1.      (A˄¬B)˅(A˄B˄C)

2.      ¬A→¬(A→¬B)

3.      A˅(A˄B)

4.      A˄(A˅B)

Penyelesaian terlampir

BAB III Penutup

3.1 Simpulan

                    Berbagai macam ekuivalensi dari berbagai ekspresi logika memberikan kemudahan bagi penyederhanaan karena bentuk ekspresi logika yang rumit dapat disederhanakan.  Operasi penyederhanaan merupakan penyederhanaan ekspresi logika atau bentuk-bentuk logika yang dibuat sesederhana mungkin dan sudah tidak dimungkinkan dimanipulasi lagi. Operasi menggunakan hukum-hukum ekuivalensi logis untuk membuktikan suatu ekspresi logika Tautologi, Kontradiksi, maupun Contingent. Untuk penyederhanaan pertama kali  yang harus dihilangkan adalah perangkai implikasi dan perangkai ekuivalensi dan dijadikan kombinasi dari perangkai alamiah yaitu konjungsi, disjungsi, dan negasi. Perangkai dasar atau perangkai alamiah ada 3, yakni ˅,˄, dan¬. Perangkai dasar dapat juga disebut perangkai cukup. Ketiga perangkai dasar inilah yang membentuk gerbang-gerbang yang menjadi dasar sistem digital, yakni gerbang dan (˄), gerbang atau (˅), dan gerbang tidak (¬).

3.2 Saran

      Menurut kami dari makalah yang kami buat, kami sarankan untuk pembaca dapat memahami bagaimana cara menyelesaikan materi operasi penyederhanaan logika, bagaimana cara menghilangkan perangkai implikasi dan ekuivalensi menjadi perangkai dasar, serta dapat memahami bagaimana cara penggunaan perangkai dasar dengan mengkombinasikan ketiga perangkai dasar tersebut.

Daftar Pustaka

http://dokumen.tips/documents/6-logika-komputer.html (28 Oktober 2016)

Soesianto,F dan Djoni Dwijana.2003.”Logika Proposisional”.Yogyakarta:Andi

Soesianto,F dan Djini Dwijono.2006.”Logika Matematika Untuk Ilmu Komputer”.Yogyakarta:Andi

Penyelesaian

1)      (A˄¬B)˅(A˄B˄C)

≡  (A˄¬B)˅(A˄(B˄C))                    Tambah Kurung

≡  A˄(¬B˅(B˄C))                            Distributif

≡  A˄((¬B˅B)˄(¬B˅C))                  Distributif

≡  A˄(1˄(¬B˅C))                            Tautology

≡ A˄(¬B˅C)                                                Identity of ˄

2)      ¬A→¬(A→¬B)

≡ ¬¬A˅¬(A→¬B)                           A→B≡¬A˅B                         

≡ ¬¬A˅¬(¬A˅¬B)                           A→B≡¬A˅B

≡ ¬¬A˅(¬¬A˄¬¬B)                         De Morgan’s Law

≡  A˅(A˄B)                                     Law of Double Negation

≡  A                                                  Absorption

3)      A˅(A˄B)

≡ (A˄1)˅(A˄B)                               Identity of ˄

≡   A˄(1˅B)                                     Distributivity

≡  A˄1                                              Identity of ˅

≡  A                                                  Identity of ˄

4)      A˄(A˅B)

≡ (A˅0)˄(A˅B)                               Identity of ˅

≡ A˅(0˄B)                                       Distributivity

≡ A˅0                                               Zero of  ˄

≡ A                                                   Zero of  ˅