Matematika Diskrit : Logika Ekuivalensi

📋 Daftar Isi

Ekuivalen

Dua proposisi majemuk disebut Ekuivalen (secara logika) jika keduanya mempunyai nilai kebenaran yang identik.

Jika p dan q adalah proposisi majemuk yang ekuivalen, maka dituliskan 𝒑 ⟺ 𝒒 atau 𝒑 ≡ 𝒒. Jika 𝒑 ≡ 𝒒, maka 𝒒 ≡ 𝒑.

Tabel kebenaran dapat digunakan untuk menyelidiki apakah dua kalimat ekuivalen.

Contoh 1

Tentukan apakah ~(p ∧ q) dengan ~p ∧ ~q ekuivalen!

Penyelesaian

p	q	p ∧ q	~(p ∧ q)	~p	~q	~p ∧ ~q
T	T	T	F	F	F	F
T	F	F	T	F	T	F
F	T	F	T	T	F	F
F	F	F	T	T	T	T

Nilai kebenaran ~ 𝑝 ∧ 𝑞 dan ∼𝑝 ∧ ∼𝑞 tidak selalu sama. Maka ~𝑝 ∧ 𝑞 tidak ekuivalen dengan ∼ 𝑝 ∧∼ q

Contoh 2

Tentukan apakah 𝑝 → 𝑞 dengan ∼ 𝑝 ∨ 𝑞 ekuivalen.

Penyelesaian

p	q	p → q	~p	~p ∨ q
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

Karena untuk tiap-tiap baris, nilai kebenaran 𝑝 → 𝑞 dan ∼ 𝑝 ∨ 𝑞 sama, maka disimpulkan bahwa 𝑝 → 𝑞 ≡ ∼ 𝑝 ∨ 𝑞.

Hukum Ekuivalensi Logika

Hukum Identitas

𝑝 ∧ 𝑇 ≡ 𝑝 ( Identitas dari ∧ adalah T)
𝑝 ∨ 𝐹 ≡ 𝑝 ( Identitas dari ∨ adalah F)

Hukum Idempoten

𝑝 ∨ 𝑝 ≡ 𝑝
𝑝 ∧ 𝑝 ≡ 𝑝

Hukum Komutatif

𝑝 ∧ 𝑞 ≡ 𝑞 ∧ 𝑝
𝑝 ∨ 𝑞 ≡ 𝑞 ∨ 𝑝

Hukum Asosiatif

(𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)
(𝑝 ∨ 𝑞) ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟)

Negasi T dan F

∼ 𝑇 ≡ 𝐹
∼ 𝐹 ≡ 𝐹

Hukum Negasi Ganda

∼ (∼ 𝑝) ≡ 𝑝

Hukum Ikatan/Dominasi

𝑝 ∨ 𝑇 ≡ 𝑇 (Dominasi dari ∨ )
𝑝 ∧ 𝐹 ≡ 𝐹 (Dominasi dari ∧)

Hukum De Morgan

∼ (𝑝 ∧ 𝑞) ≡ ∼ 𝑝 ∨∼ 𝑞
∼ (𝑝 ∨ 𝑞) ≡∼ 𝑝 ∧∼ 𝑞

Hukum Distributif

𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)

Hukum Absorbsi

𝑝 ∨ 𝑝 ∧ 𝑞 ≡ 𝑝
𝑝 ∧ 𝑝 ∨ 𝑞 ≡ 𝑝

Hukum Negasi

𝑝 ∨∼ 𝑝 ≡ 𝑇
𝑝 ∧∼ 𝑝 ≡ 𝐹

Hukum Ekuivalensi Logika yang Melibatkan Implikasi

𝑝 → 𝑞 ≡ ∼ 𝑝 ∨ 𝑞

𝑝 → 𝑞 ≡ ∼ 𝑞 → ∼p

𝑝 ∨ 𝑞 ≡∼ 𝑝 → 𝑞

𝑝 ∧ 𝑞 ≡∼(𝑝 →∼ 𝑞)

∼ (𝑝 → 𝑞) ≡ 𝑝 ∧∼ 𝑞

(𝑝 → 𝑞) ∧ (𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∧ 𝑟)

(𝑝 → 𝑟) ∧ (𝑞 → 𝑟) ≡ (𝑝 ∨ 𝑞) → 𝑟

(𝑝 → 𝑞) ∨ (𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∨ 𝑟)

(𝑝 → 𝑟) ∨ (𝑞 → 𝑟) ≡ (𝑝 ∧ 𝑞) → 𝑟

Hukum Ekuivalensi yang Melibatkan Biimplikasi

𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)
𝑝 ↔ 𝑞 ≡ ∼ 𝑝 ↔ ∼ 𝑞
𝑝 ↔ 𝑞 ≡ (𝑝 ∧ 𝑞) ∨ (∼ 𝑝 ∧∼ 𝑞)
∼ (𝑝 ↔ 𝑞) ≡ 𝑝 ↔ ∼𝑞

Pembuktian Ekuivalensi dengan Menyederhanakan Proposisi

Hukum-hukum tersebut digunakan untuk menyederhanakan proposisi-proposisi yang kompleks dan untuk membuktikan ekuivalensi.

Dalam membuktikan ekuivalensi 𝒑 ⟺ 𝒒, ada 3 macam cara yang bisa dilakukan:

𝒑 diturunkan terus menerus dengan menggunakan hukumhukum yang ada, sehingga akhirnya didapat 𝒒.
𝒒 diturunkan terus menerus dengan menggunakan hukumhukum yang ada, sehingga akhirnya didapat 𝒑.
𝒑 dan 𝒒 masing-masing diturunkan secara terpisah sehingga
akhirnya didapat 𝒓.

Biasanya bentuk yang lebih kompleks yang diturunkan ke bentuk yang lebih sederhana.

Contoh 1

Sederhanakan bentuk ~ (~𝑝 ∧ 𝑞) ∧ (𝑝 ∨ 𝑞)

Penyelesaian

~ (~𝑝 ∧ 𝑞) ∧ (𝑝 ∨ 𝑞) ≡ (~(~𝑝) ∨ ~𝑞) ∧ (𝑝 ∨ 𝑞)

≡ (𝑝 ∨ ~𝑞) ∧ (𝑝 ∨ 𝑞)

≡ 𝑝 ∨ (~𝑞 ∧ 𝑞)

≡ 𝑝 ∨ 𝐹

≡ 𝑝

Contoh 2

Tunjukkan bahwa 𝑝 ∨∼ (𝑝 ∨ 𝑞) dan 𝑝 ∨∼ 𝑞 keduanya ekuivalen secara logika.

Penyelesaian

𝑝 ∨∼ (𝑝 ∨ 𝑞) ⟺ 𝑝 ∨ (~𝑝 ∧∼ 𝑞)

⟺ (𝑝 ∨ ~𝑝) ∧ (𝑝 ∨∼ 𝑞)

⟺ 𝑇 ∧ (𝑝 ∨∼ 𝑞)

⟺ (𝑝 ∨∼ 𝑞)

Contoh 3

Tunjukkan bahwa∼ (𝑝 ∨ (~𝑝 ∧ 𝑞))dan ~𝑝 ∧∼ 𝑞 keduanya ekuivalen secara logika.

Penyelesaian

∼(𝑝 ∨ (~𝑝 ∧ 𝑞)) ≡∼ 𝑝 ∧∼ (~𝑝 ∧ 𝑞)

≡∼ 𝑝 ∧ (𝑝 ∨ ~𝑞)

≡ (∼ 𝑝 ∧ 𝑝) ∨ (∼ 𝑝 ∧ ~𝑞)

≡ 𝐹 ∨ (∼ 𝑝 ∧ ~𝑞)

≡ (∼ 𝑝 ∧ ~𝑞) ∨ 𝐹

≡ (∼ 𝑝 ∧ ~𝑞)

Contoh 4

Tunjukkan bahwa (𝑝 ∧ 𝑞) → (𝑝 ∨ 𝑞) adalah tautologi.

Penyelesaian

(𝑝 ∧ 𝑞) → (𝑝 ∨ 𝑞) ≡∼ (𝑝 ∧ 𝑞) ∨ (𝑝 ∨ 𝑞)

≡ (∼ 𝑝 ∨∼ 𝑞) ∨ (𝑝 ∨ 𝑞)

≡ (∼ 𝑝 ∨ 𝑝) ∨ (∼ 𝑞 ∨ 𝑞)

≡ 𝑇 ∨ 𝑇

≡ 𝑇

Contoh 5

Tunjukkan bahwa (𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝) adalah tautologi.

Penyelesaian

(𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝)

≡ ((𝑝 → 𝑞) → (∼ 𝑞 →∼ 𝑝)) ∧ ((∼ 𝑞 →∼ 𝑝) → (𝑝 → 𝑞))

≡ ((∼ 𝑝 ∨ 𝑞) → (𝑞 ∨∼ 𝑝)) ∧ ((𝑞 ∨∼ 𝑝) → (∼ 𝑝 ∨ 𝑞))

≡ (∼ (∼ 𝑝 ∨ 𝑞) ∨ (𝑞 ∨∼ 𝑝)) ∧ (∼ (𝑞 ∨∼ 𝑝) ∨ (∼ 𝑝 ∨ 𝑞) )

≡ ((𝑝 ∧∼ 𝑞) ∨ (𝑞 ∨∼ 𝑝)) ∧ ((∼ 𝑞 ∧ 𝑝) ∨ (∼ 𝑝 ∨ 𝑞))

≡ ((𝑝 ∧∼ 𝑞) ∨ (𝑞 ∨∼ 𝑝)) ∧ ((𝑝 ∧∼ 𝑞) ∨ (𝑞 ∨∼ 𝑝))

≡ ((𝑝 ∧∼ 𝑞) ∨ (𝑞 ∨∼ 𝑝))

≡ (∼ (∼ 𝑝 ∨ 𝑞) ∨ (𝑞 ∨∼ 𝑝))

≡ (∼ (∼ 𝑝 ∨ 𝑞) ∨ (∼ 𝑝 ∨ 𝑞))

≡∼ 𝑟 ∨ 𝑟

≡ 𝑇

Konvers, Invers, dan Kontraposisi

Misal diketahui implikasi (𝑝 → 𝑞)

Konversnya adalah (𝑞 → 𝑝)

Inversnya adalah (~𝑝 → ~𝑞)

Kontraposisinya adalah (~𝑞 → ~𝑝)

Suatu implikasi selalu ekuivalen dengan kontraposisinya. Artinya, pada tabel kebenaran, nilai kebenaran 𝑝 → 𝑞 selalu sama dengan nilai kebenaran ~𝑞 → ~𝑝. Akan tetapi tidak demikian dengan invers dan konvers.

Contoh 1

Jika A merupakan suatu bujursangkar, maka A merupakan suatu 4 persegi panjang.

Konvers: Jika A merupakan 4 persegi panjang, maka A merupakan suatu bujursangkar.

Invers: Jika A bukan bujursangkar, maka A bukan 4 persegi panjang.

Kontraposisi: Jika A bukan 4 persegi panjang, maka A bukan bujursangkar.

Contoh 2

Jika n adalah bilangan prima > 2, maka n adalah bilangan ganjil.

Konvers: Jika n adalah bilangan ganjil, maka n adalah bilangan prima > 2.

Invers: Jika n bukan bilangan prima > 2, maka n bukan bilangan ganjil.

Kontraposisi: Jika n bukan bilangan ganjil, maka n bukan bilangan prima > 2