Pohon Sintaks

Kadang-kadang untuk menentukan kolom dalam tabel kebenaran dapat agak sulit, terutama ketika jumlah konektor dan tanda kurungnya banyak.

Untuk menganalisis kalimat, kita bisa menggunakan bantuan pohon sintaks. Sebagai contoh, pohon sintaks untuk kalimat rumit \neg (p \land q) \lor \neg(p \veebar q) adalah:

Bagaimana menguraikannya?

Pohon sintaks dasar

Kita akan mencoba mulai dari kasus sederhana. Misalnya untuk kalimat berikut:

p \land q

Pertama tuliskan kalimat simbolik tersebut dalam sebuah kotak.

Karena rangkaian simbol ini terdiri dari 2 komponen kalimat yang lebih sederhana, maka tuliskan masing-masing kalimatnya sebagai cabang.

Dengan menggunakan pohon sintaks, kita dapat menentukan kolom-kolom yang diperlukan dalam tabel kebenaran. Didaftarkan mulai dari simbol paling sederhana pada ranting terujung (tidak harus terbawah). Diagram di bawah ini menunjukkan urutan kolomnya.

Kolom yang digunakan adalah:

p	q	p \land q

Tanda kurung berisi kalimat majemuk

Jika ada tanda kurung, berarti cabangnya tidak boleh langsung dibuka.

p \land (q \lor r)

Jadi pertama-tama sedikan kotak untuk kalimat lengkapnya:

Konektor pertama adalah konjungsi, bukan disjungsi.

p \boxed{\land} (q \lor r)

Berarti komponen yang dipisahkan konjungsi tersebut adalah p dan (q \lor r).

\boxed{p} \land \boxed{(q \lor r)}

Dengan demikian kita bisa membuat keduanya menjadi cabang tingkat pertama.

Cabang sebelah kiri sudah paling sederhana, yaitu p. Namun cabang sebelah kanan masih bisa diuraikan lagi, karena ada konektor disjungsi di sana.

\boxed{q} \lor \boxed{r}

Dengan demikian q dan r dituliskan sebagai cabang tingkat kedua.

Untuk membentuk kolomnya, kita bisa mulai mengurutkan dari yang paling sederhana.

Kolom yang dihasilkan adalah:

p	q	r	q \lor r	p \land (q \lor r)

Negasi sederhana

Bagaimana jika ada negasi?

\neg p

Seperti sebelumnya, buat kotak untuk kalimat tersebut.

Kalimat \neg p bukanlah kalimat dalam bentuk paling sederhana. Kalimat penyusun yang lebih sederhana adalah p.

\neg \boxed{p}

Karena itu kita perlu membuat cabang yang hanya berisi p.

Negasi yang lebih kompleks

\neg (p \land q)

Dalam contoh ini, kita perlu melihat penyusun pertamanya adalah yang ada dalam tanda kurung.

\neg (\boxed{p \land q})

Dengan demikian kita membuat cabang yang hanya berisi p \land q, dan kemudian baru menguraikannya menjadi p dan q.

Contoh lain

\neg (p \lor q) \veebar r

Contoh yang lebih rumit

(p \land \neg q) \veebar \neg (r \lor \neg q)

Mendaftar kolom

Sekarang, bagaimana mendaftarkan kolom yang akan dipakai? Mulailah dari yang paling sederhana hingga yang paling rumit.

Misalnya untuk contoh ini:

Berarti akan ada kolom p, q, p ∧ q dan ¬(p ∧ q).

p	q	p \land q	\neg(p \land q)

Latihan

Berikutnya: Negasi dari konjungsi