Hukum De Morgan - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T14:09:39Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 25 Agustus 2026 14.09
Baris 1:		Baris 1:
	Dalam [[kalkulus proposisional\|logika proposional]] dan [[aljabar Boolean]], '''Hukum De Morgan''', '''aturan De Morgan''', atau '''teorema De Morgan''' adalah sepasang aturan penarikan kesimpulan yang menghubungkan [[logika konjungsi\|konjungsi]] dan [[logika disjungsi\|disjungsi]] melalui [[negasi]]. Aturan ini dinamai dari [[Augustus De Morgan]], seorang matematikawan abad ke-19 berkebangsaan Inggris.		Dalam [[kalkulus proposisional\|logika proposional]] dan [[aljabar Boolean]], '''Hukum De Morgan''',<ref>Irving M. Copi. [https://www.taylorfrancis.com/books/mono/10.4324/9781315510897/introduction-logic-irving-copi-carl-cohen-kenneth-mcmahon Introduction to Logic]. 2016. doi:10.4324/9781315510897. ISBN 9781315510880.</ref><ref>Patrick J. Hurley. ''A Concise Introduction to Logic''. Cengage Learning. 2015. ISBN 978-1-285-19654-1.</ref><ref>Brooke Noel Moore. [https://www.worldcat.org/oclc/689858599 Critical thinking]. McGraw-Hill. 2012. ISBN 978-0-07-803828-0.</ref> '''aturan De Morgan''', atau '''teorema De Morgan'''<ref>[http://hyperphysics.phy-astr.gsu.edu/hbase/Electronic/DeMorgan.html Teorema De Morgan]</ref> adalah sepasang aturan penarikan kesimpulan yang menghubungkan [[logika konjungsi\|konjungsi]] dan [[logika disjungsi\|disjungsi]] melalui [[negasi]]. Aturan ini dinamai dari [[Augustus De Morgan]], seorang matematikawan abad ke-19 berkebangsaan Inggris.

	Hukum De Morgan dapat dinyatakan dalam bahasa Indonesia sebagai:		Hukum De Morgan dapat dinyatakan dalam bahasa Indonesia sebagai:
Baris 22:		Baris 22:
	* <math>\cap</math> menyatakan operasi [[Irisan (teori himpunan)\|irisan]] pada himpunan		* <math>\cap</math> menyatakan operasi [[Irisan (teori himpunan)\|irisan]] pada himpunan
	* <math>\cup</math> menyatakan operasi [[Gabungan (teori himpunan)\|gabungan]] pada himpunan		* <math>\cup</math> menyatakan operasi [[Gabungan (teori himpunan)\|gabungan]] pada himpunan


	Dalam [[bahasa formal]], Hukum De Morgan dapat ditulis secara formal sebagai		Dalam [[bahasa formal]], Hukum De Morgan dapat ditulis secara formal sebagai
Baris 56:		Baris 55:

	Dalam [[aturan penarikan kesimpulan\|bentuk aturan]], ''negasi dari konjungsi'' dapat ditulis sebagai berikut :		Dalam [[aturan penarikan kesimpulan\|bentuk aturan]], ''negasi dari konjungsi'' dapat ditulis sebagai berikut :
	:		:{\| style = "text-align:center"
			\|-
			\| <math>\begin{array}{rl} & \neg \! \left( P \land Q \right) \\ \hline \therefore & \neg P \lor \neg Q \end{array}</math>
			\| <math>\phantom{Spasi}</math>
			\| <math>\begin{array}{rl} & \neg P \lor \neg Q \\ \hline \therefore & \neg \! \left( P \land Q \right) \end{array}</math>
			\|}

	Dengan cara serupa, ''negasi dari konjungsi'' dapat ditulis sebagai berikut :		Dengan cara serupa, ''negasi dari konjungsi'' dapat ditulis sebagai berikut :
	:		:{\| style = "text-align:center"
			\|-
			\| <math>\begin{array}{rl} & \neg \! \left( P \lor Q \right) \\ \hline \therefore & \neg P \land \neg Q \end{array}</math>
			\| <math>\phantom{Spasi}</math>
			\| <math>\begin{array}{rl} & \neg P \land \neg Q \\ \hline \therefore & \neg \! \left( P \lor Q \right) \end{array}</math>
			\|}

	dan saat dituliskan sebagai suatu [[teorema]] dalam logika proposisional, maka Hukum De Morgan dapat dinyatakan sebagai		dan saat dituliskan sebagai suatu [[teorema]] dalam logika proposisional, maka Hukum De Morgan dapat dinyatakan sebagai
Baris 74:		Baris 83:

	=== Teori himpunan ===		=== Teori himpunan ===
	Dalam teori himpunan, Hukum De Morgan sering kali dinyatakan sebagai "gabungan dan irisan ditukar saat dikomplemenkan", yang dapat dinyatakan secara formal sebagai berikut :		Dalam teori himpunan, Hukum De Morgan sering kali dinyatakan sebagai "gabungan dan irisan ditukar saat dikomplemenkan",<ref>''Boolean Algebra'' by R. L. Goodstein.</ref> yang dapat dinyatakan secara formal sebagai berikut :
	<math display="block">\begin{align}		<math display="block">\begin{align}
	\overline{A \cup B} &= \overline{A} \cap \overline{B} \text{, dan} \\		\overline{A \cup B} &= \overline{A} \cap \overline{B} \text{, dan} \\
Baris 160:		Baris 169:

	Argumentasi serupa juga dapat digunakan untuk membuktikan bahwa <math>\overline{A \cap B} = \overline{A} \cup \overline{B}</math>		Argumentasi serupa juga dapat digunakan untuk membuktikan bahwa <math>\overline{A \cap B} = \overline{A} \cup \overline{B}</math>

	~~== Referensi ==~~


	== Pranala luar ==		== Pranala luar ==
	*		*
	*		*
	*		*
	* [http://www.iep.utm.edu/dual-log/ Dualitas dalam Logika dan Bahasa], ''Internet Encyclopedia of Philosophy''.		* [http://www.iep.utm.edu/dual-log/ Dualitas dalam Logika dan Bahasa], ''Internet Encyclopedia of Philosophy''.

			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Hukum+De+Morgan&oldid=27509177 Wikipedia bahasa Indonesia], revisi 27509177 (2025-07-07T14:23:34Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Hukum+De+Morgan&oldid=27509177 Wikipedia bahasa Indonesia], revisi 27509177 (2025-07-07T14:23:34Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 27509177; atribusi sumber disertakan.

2026-08-25T13:49:16Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 27509177; atribusi sumber disertakan.

Halaman baru

Dalam [[kalkulus proposisional|logika proposional]] dan [[aljabar Boolean]], '''Hukum De Morgan''', '''aturan De Morgan''', atau '''teorema De Morgan''' adalah sepasang aturan penarikan kesimpulan yang menghubungkan [[logika konjungsi|konjungsi]] dan [[logika disjungsi|disjungsi]] melalui [[negasi]]. Aturan ini dinamai dari [[Augustus De Morgan]], seorang matematikawan abad ke-19 berkebangsaan Inggris.

Hukum De Morgan dapat dinyatakan dalam bahasa Indonesia sebagai:
* Negasi dari disjungsi adalah konjungsi dari negasi
* Negasi dari konjungsi adalah disjungsi dari negasi
atau
* [[Komplemen (teori himpunan)|Komplemen]] dari gabungan dua himpunan sama dengan irisan dari komplemen kedua himpunan tersebut
* [[Komplemen (teori himpunan)|Komplemen]] dari irisan dua himpunan sama dengan gabungan dari komplemen kedua himpunan tersebut
atau
* bukan (<math>A</math> atau <math>B</math>) = (bukan <math>A</math>) dan (bukan <math>B</math>)
* bukan (<math>A</math> dan <math>B</math>) = (bukan <math>A</math>) atau (bukan <math>B</math>)
dengan "<math>A</math> atau <math>B</math>" menyatakan [[logika disjungsi|disjungsi inklusif]] (yang berarti ''setidaknya'' satu dari dari <math>A</math> atau <math>B</math> bernilai benar), dan bukan [[logika disjungsi eksklusif]] (yang berarti ''tepat'' satu dari dari <math>A</math> atau <math>B</math> bernilai benar).

Dalam [[teori himpunan]] dan [[aljabar Boolean]], Hukum De Morgan dapat ditulis secara formal sebagai
<math display="block">\begin{align}
\overline{A \cup B} &= \overline{A} \cap \overline{B} \text{, dan} \\
\overline{A \cap B} &= \overline{A} \cup \overline{B}
\end{align}</math>
dengan
* <math>A</math> dan <math>B</math> adalah sembarang himpunan
* <math>\overline{A}</math> menyatakan [[Komplemen (teori himpunan)|komplemen]] dari himpunan <math>A</math>
* <math>\cap</math> menyatakan operasi [[Irisan (teori himpunan)|irisan]] pada himpunan
* <math>\cup</math> menyatakan operasi [[Gabungan (teori himpunan)|gabungan]] pada himpunan

Dalam [[bahasa formal]], Hukum De Morgan dapat ditulis secara formal sebagai
<math display="block">\begin{align}
\neg \! \left( P \lor Q \right) &\iff \left( \neg P \right) \land \left( \neg Q \right) \text{, dan} \\
\neg \! \left( P \land Q \right) &\iff \left( \neg P \right) \lor \left( \neg Q \right)
\end{align}</math>
dengan
* <math>P</math> dan <math>Q</math> merupakan proposisi
* [[Negasi|<math>\neg</math>]] menyatakan operator logika negasi (tidak)
* [[logika konjungsi|<math>\land</math>]] menyatakan operator logika konjungsi (dan)
* [[logika disjungsi|<math>\lor</math>]] menyatakan operator logika disjungsi (atau)
* [[Jika dan hanya jika|<math>\iff</math>]] adalah simbol [[metalogika]] yang berarti "dalam [[bukti formal|bukti logis]], dapat diganti dengan" dan sering kali dibaca sebagai "jika dan hanya jika". Untuk setiap kombinasi nilai benar/salah untuk <math>P</math> dan <math>Q</math>, ruas kiri dan kanan dari panahnya akan memiliki nilai kebenaran yang sama setelah diselesaikan.

Bentuk lain dari Hukum De Morgan dapat dinyatakan sebagai berikut
<math display="block">\begin{align}
A \setminus \left( B \cup C \right) &= \left( A \setminus B \right) \cap \left( A \setminus C \right) \text{, dan} \\
A \setminus \left( B \cap C \right) &= \left( A \setminus B \right) \cup \left( A \setminus C \right)
\end{align}</math>
Penerapan dari aturan ini salah satunya ialah menyederhanakan [[Ekspresi (ilmu komputer)|ekspresi]] logika pada [[program komputer]] dan desain rangkaian digital. Hukum De Morgan adalah contoh dari suatu konsep umum dari [[dualitas (matematika)|dualitas matematika]].

== Notasi Formal ==
Dengan menggunakan notasi [[sekuensi]], maka aturan ''negasi dari konjungsi'' dapat ditulis sebagai berikut :
<math display="block">\begin{align}
\neg \! \left( P \land Q \right) &\vdash \left( \neg P \lor \neg Q \right) \text{, dan} \\
\left( \neg P \lor \neg Q \right) &\vdash \neg \! \left( P \land Q \right)
\end{align}</math>
Dengan cara serupa, aturan ''negasi dari disjungsi'' dapat ditulis dalam notasi [[sekuensi]] sebagai berikut :
<math display="block">\begin{align}
\neg \! \left( P \lor Q \right) &\vdash \left( \neg P \land \neg Q \right) \text{, dan} \\
\left( \neg P \lor \neg Q \right) &\vdash \neg \! \left( P \land Q \right)
\end{align}</math>

Dalam [[aturan penarikan kesimpulan|bentuk aturan]], ''negasi dari konjungsi'' dapat ditulis sebagai berikut :
:

Dengan cara serupa, ''negasi dari konjungsi'' dapat ditulis sebagai berikut :
:

dan saat dituliskan sebagai suatu [[teorema]] dalam logika proposisional, maka Hukum De Morgan dapat dinyatakan sebagai
<math display="block">\begin{align}
\neg \! \left( P \lor Q \right) &\leftrightarrow \left( \neg P \right) \land \left( \neg Q \right) \text{, dan} \\
\neg \! \left( P \land Q \right) &\leftrightarrow \left( \neg P \right) \lor \left( \neg Q \right)
\end{align}</math>
dengan <math>P</math> dan <math>Q</math> adalah proposisi yang diekspresikan dalam suatu sistem formal.
'''Hukum De Morgan yang diperumum''' menawarkan ekuivalensi saat menegasikan konjungsi atau disjungsi yang melibatkan banyak suku. Jika <math>P_k</math> menyatakan proposisi ke-<math>k</math>, maka '''Hukum De Morgan yang diperumum''' ialah
<math display="block">\begin{align}
\neg \! \left( P_1 \lor P_2 \lor \ldots \lor P_n \right) &\leftrightarrow \neg P_1 \land \neg P_2 \land \ldots \land \neg P_n \text{, dan} \\
\neg \! \left( P_1 \land P_2 \land \ldots \land P_n \right) &\leftrightarrow \neg P_1 \lor \neg P_2 \lor \ldots \lor \neg P_n
\end{align}</math>

=== Teori himpunan ===
Dalam teori himpunan, Hukum De Morgan sering kali dinyatakan sebagai "gabungan dan irisan ditukar saat dikomplemenkan", yang dapat dinyatakan secara formal sebagai berikut :
<math display="block">\begin{align}
\overline{A \cup B} &= \overline{A} \cap \overline{B} \text{, dan} \\
\overline{A \cap B} &= \overline{A} \cup \overline{B}
\end{align}</math>
dengan
* <math>A</math> dan <math>B</math> adalah sembarang himpunan
* <math>\overline{A}</math> menyatakan [[Komplemen (teori himpunan)|komplemen]] dari himpunan <math>A</math>
* <math>\cap</math> menyatakan operasi [[Irisan (teori himpunan)|irisan]] pada himpunan
* <math>\cup</math> menyatakan operasi [[Gabungan (teori himpunan)|gabungan]] pada himpunan

Hukum De Morgan juga dapat diperumum untuk sembarang jumlah himpunan, yaitu
<math display="block">\begin{align}
\overline{\bigcup_{i \, \in \, I} A_i} &= \bigcap_{i \, \in \, I} \overline{A_i} \text{, dan} \\
\overline{\bigcap_{i \, \in \, I} A_i} &= \bigcup_{i \, \in \, I} \overline{A_i}
\end{align}</math>
dengan <math>I</math> adalah suatu [[himpunan indeks]] (bisa [[himpunan terhitung]], maupun [[himpunan tak terhitung]])

===Rekayasa===
Dalam [[aljabar Boolean]], [[teknik listrik]] dan [[teknik komputer]], Hukum De Morgan biasa ditulis sebagai berikut :
<math display="block">\begin{align}
\overline{A + B} &= \overline{A} \cdot \overline{B} \text{, dan} \\
\overline{A \cdot B} &= \overline{A} + \overline{B}
\end{align}</math>
dengan
* [[Negasi|<math>\overline{A}</math>]] menyatakan operator logika negasi (TIDAK) dari <math>A</math>
* [[logika konjungsi|<math>\cdot</math>]] menyatakan operator logika konjungsi (DAN)
* [[logika disjungsi|<math>+</math>]] menyatakan operator logika disjungsi (ATAU)

=== Pencarian teks ===
Hukum De Morgan sering digunakan dalam pencarian teks menggunakan operator Boolean DAN, ATAU, dan BUKAN (TIDAK). Misalkan terdapat beberapa dokumen yang memuat kata "merah" dan "biru". Hukum De Morgan menyatakan bahwa kedua pencarian ini akan menghasilkan dokumen-dokumen yang sama :

:Pencarian A : BUKAN (merah ATAU biru)
:Pencarian B : (BUKAN merah) DAN (BUKAN biru)

Dokumen-dokumen yang memuat kata "Merah" atau "biru" dapat dikelompokkan menjadi empat kategori, yaitu :
:Kategori 1 : Hanya memuat kata "merah"
:Kategori 2 : Hanya memuat kata "biru"
:Kategori 3 : Memuat kata "merah" dan juga "biru"
:Kategori 4 : Tidak memuat kata "merah" maupun "biru"

Di satu sisi, jelas bahwa pencarian "(merah ATAU biru)" akan menampilkan kategori 1, 2, dan 3. Akibatnya, negasi dari pencarian tersebut (yaitu hasil pencarian A) akan menampilkan dokumen-dokumen lainnya, yaitu dokumen-dokumen pada kategori 4.

Di sisi lain, pencarian "(BUKAN merah)" akan menampilkan kategori 2 dan kategori 4, dan pencarian "(BUKAN biru)" akan menampilkan kategori 1 dan kategori 4. Dengan menerapkan operator DAN pada kedua pencarian ini (yaitu pencarian B), maka hasilnya akan menampilkan hasil yang sama-sama dijumpai pada kedua pencarian ini, yaitu dokumen-dokumen pada kategori 4.

Argumentasi serupa juga dapat diterapkan pada dua pencarian berikut

:Pencarian C : BUKAN (merah DAN biru)
:Pencarian D : (BUKAN merah) ATAU (BUKAN biru)

yang sama-sama menampilkan dokumen-dokumen pada kategori 1, 2, dan 4

== Bukti formal ==
Disini, akan digunakan notasi <math>\overline{A}</math> untuk menyatakan [[Komplemen (teori himpunan)|komplemen]] dari himpunan <math>A</math>, sama seperti penggunaan pada . Untuk membuktikan bahwa <math>\overline{A \cup B} = \overline{A} \cap \overline{B}</math>, maka
=== Bagian pertama ===
Akan dibuktikan bahwa <math>\overline{A \cup B} \subseteq \overline{A} \cap \overline{B}</math>. Diambil sembarang elemen <math>x \in \overline{A \cup B}</math>. Perhatikan bahwa
<math display="block">\begin{align}
x \in \overline{A \cup B} &\implies x \not \in A \cup B & \text{definisi operasi komplemen} \\
&\implies x \not \in A \; \land \; x \not \in B & \text{lihat penjelasan dibawah} \\
&\implies x \in \overline{A} \; \land \; x \in \overline{B} & \text{definisi operasi komplemen} \\
&\implies x \in \overline{A} \cap \overline{B} & \text{definisi operasi irisan}
\end{align}</math>

Akan dibuktikan bahwa <math>x \not \in A \cup B</math> akan mengakibatkan <math>x \not \in A</math> dan <math>x \not \in B</math> melalui kontradiksi.
# Andaikan <math>x \in A</math>, maka <math>x \in A \cup B</math>. Akan tetapi, hal itu mustahil terjadi, sebab diperoleh informasi bahwasanya <math>x \not \in A \cup B</math> pada baris pertama di atas. Oleh karena terjadi kontradiksi, maka pengandaian di awal (bahwasanya <math>x \in A</math>) bernilai salah. Akibatnya, diperoleh <math>x \not \in A</math>.
# Andaikan <math>x \in B</math>, maka <math>x \in A \cup B</math>. Akan tetapi, hal itu mustahil terjadi, sebab diperoleh informasi bahwasanya <math>x \not \in A \cup B</math> pada baris pertama di atas. Oleh karena terjadi kontradiksi, maka pengandaian di awal (bahwasanya <math>x \in B</math>) bernilai salah. Akibatnya, diperoleh <math>x \not \in B</math>.
Dari dua kasus di atas, maka terbukti bahwa <math>x \not \in A \cup B</math> akan mengakibatkan <math>x \not \in A</math> dan <math>x \not \in B</math>.

sehingga terbukti bahwa <math>\overline{A \cup B} \subseteq \overline{A} \cap \overline{B}</math>.
=== Bagian kedua ===
Akan dibuktikan bahwa <math>\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}</math>. Diambil sembarang elemen <math>x \in \overline{A} \cap \overline{B}</math>. Perhatikan bahwa
<math display="block">\begin{align}
x \in \overline{A} \cap \overline{B} &\implies x \in \overline{A} \; \land \; x \in \overline{B} & \text{definisi operasi irisan} \\
&\implies x \not \in A \; \land \; x \not \in B & \text{definisi operasi komplemen} \\
&\implies x \not \in A \cup B & \text{lihat penjelasan di} \\
&\implies x \in \overline{A \cup B} & \text{definisi operasi komplemen}
\end{align}</math>

Akan dibuktikan bahwa <math>x \not \in A</math> dan <math>x \not \in B</math> akan mengakibatkan <math>x \not \in A \cup B</math> melalui kontradiksi. Andaikan <math>x \in A \cup B</math>, maka menurut definisi operasi [[Gabungan (teori himpunan)|gabungan]] pada himpunan, diperoleh <math>x \in A</math> atau <math>x \in B</math>.
# Jika <math>x \in A</math>, maka hal tersebut kontradiksi dengan hasil pada baris kedua di atas (bahwasanya <math>x \not \in A</math>)
# Jika <math>x \in B</math>, maka hal tersebut kontradiksi dengan hasil pada baris kedua di atas (bahwasanya <math>x \not \in B</math>)
Oleh karena terjadi kontradiksi pada kedua kasus di atas, maka pengandaian di awal (bahwasanya <math>x \in A \cup B</math>) bernilai salah. Akibatnya, terbukti bahwa informasi <math>x \not \in A</math> dan <math>x \not \in B</math> akan mengakibatkan <math>x \not \in A \cup B</math>.

sehingga terbukti bahwa <math>\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}</math>.

Argumentasi serupa juga dapat digunakan untuk membuktikan bahwa <math>\overline{A \cap B} = \overline{A} \cup \overline{B}</math>

== Referensi ==

== Pranala luar ==
*
*
*
* [http://www.iep.utm.edu/dual-log/ Dualitas dalam Logika dan Bahasa], ''Internet Encyclopedia of Philosophy''.

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Hukum+De+Morgan&oldid=27509177 Wikipedia bahasa Indonesia], revisi 27509177 (2025-07-07T14:23:34Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.