Formula

A polynomial that indicates whether a clause is satisfied

Let L1, ..., Ls be the zero-one values of the literals in one clause. Its satisfaction indicator is Phi = 1 - (1-L1)...(1-Ls), where adjacent parentheses are multiplied. If all literals are false, every factor is 1 and Phi = 0. If any literal is true, its factor is 0 and Phi = 1. For p OR NOT q, Phi(x,y) = 1 - (1-x)y. On assignments (x,y) = (0,0), (0,1), (1,0), (1,1), the outputs are 1, 0, 1, 1. This zero-one interpretation is guaranteed only for Boolean inputs.

0

1

Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math

Related
Related