Bentuk SOP dan POS Fungsi Boolean

Kami menggambarkan prinsip-prinsip yang mewakili fungsi dalam SOP (= Sup-of-produk) dan POS (= Produk-of-Sums) terbentuk pada contoh F mayoritas tiga-masukan fungsi. Fungsi ini mengambil nilai 1 jika dan hanya jika jumlah orang dalam vektor masukan melebihi jumlah nol.

ABC	F
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 1 0 1 1 1

Secara umum bentuk SOP dari fungsi Boolean terdiri dari koleksi variabel anded (disebut istilah) yang ORed bersama-sama. Misalnya, bentuk SOP dari F fungsi

Setiap fungsi f Boolean (x _1, ..., x _n) dapat direpresentasikan dalam bentuk SOP. Kami jelaskan di bawah cara untuk membangun salah satu representasi tersebut, yang disebut kanonik. Untuk ini mempertimbangkan entri dalam tabel kebenaran di mana fungsi f mengambil nilai 1. Untuk setiap string seperti bentuk SOP akan berisi istilah melibatkan semua n variabel, beberapa di antaranya dinegasikan. Lebih tepatnya, jika f (a _1, ..., _n)= 1 maka dalam jangka sesuai dengan entri (a _1, ..., _n) variabel x _i menegasikan suatu _i = 0 dan tidak dinegasikan sebaliknya. Oleh karena itu, jumlah istilah dalam bentuk SOP kanonik sama dengan jumlah "orang" dari fungsi f, yaitu jumlah entri dari tabel kebenaran di mana f mengambil nilai 1.
Bentuk SOP dari suatu fungsi tidak unik pada umumnya. Misalnya, fungsi mayoritas juga dapat direpresentasikan dalam bentuk berikut (non-kanonik) SOP

(1)

Sebuah ganda dengan bentuk SOP adalah bentuk POS. Bentuk POS terdiri dari koleksi variabel ORed (disebut maxterms) yang ANDed bersama-sama. Salah satu metode untuk mendapatkan bentuk POS adalah mulai dengan pelengkap dari bentuk SOP, dan kemudian menerapkan teorema DeMorgan.
Sebagai contoh, perhatikan fungsi mayoritas di atas, dan merupakan komplemen dalam bentuk POS:

(2)

Melengkapi kedua sisi (2), dan menerapkan hasil Involusi properti

(3)

Menerapkan ke (3) Teorema DeMorgan dalam bentuk  menyediakan

(4)

Akhirnya, berlaku untuk (4) teorema DeMorgan dalam bentuk  hasil dalam bentuk POS untuk F

Metode ini diterapkan pada hasil bentuk kanonik SOP dalam bentuk POS disebut kanonik. Jumlah maxterms dalam bentuk kanonik POS sama dengan jumlah dari angka nol dari fungsi. Selain itu, dalam setiap maxterm setiap variabel muncul tepat satu kali baik dalam bentuk benar atau ditiadakan. Setiap maxterm memiliki 0 nilai hanya satu entri dalam tabel kebenaran.
Salah satu motivasi untuk menggunakan formulir POS adalah bahwa hal itu dapat mengakibatkan formula Boolean sederhana. Dengan demikian, jika jumlah yang dari fungsi Boolean melebihi jumlah nol, maka jumlah istilah dalam POS kanonik dari melebihi satu dalam bentuk kanonik POS.
Bentuk SOP dari suatu fungsi tidak unik pada umumnya. Misalnya, menerapkan metode di atas untuk bentuk SOP fungsi mayoritas (1) hasil sebagai berikut (non-kanonik) bentuk POS

Hal ini dapat ditunjukkan bahwa jumlah SOP yang berbeda (dan juga POS) bentuk n variabel sama dengan 2 ^{3 n.} Namun, karena jumlah fungsi Boolean hanya 2 ^{2 n,} maka tidak semua bentuk-bentuk sesuai dengan fungsi yang berbeda. Dengan kata lain, fungsi dapat memiliki banyak SOP (resp. POS) bentuk yang berbeda. Oleh karena itu, masuk akal untuk meminta yang paling sederhana, dalam arti.