将布尔可满足性问题(Boolean satisfiability problem)叫做SAT:
给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,问存在满足的真值赋值吗?
例如,设有3个子句:(x_1 \vee \overline {x_2} ),(\overline {x_1} \vee \overline {x_3} ),(x_2 \vee \overline {x_3} ),那么如果让所有的变量都为1,则不能够满足所有的子句,因为第二个子句的值为0。
给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,每一个子句的长度为3,问存在满足的真值赋值吗?


15 thoughts on “SAT和3-SAT

  1. This design is steller! You obviously know how to keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job. I really enjoyed what you had to say, and more than that, how you presented it. Too cool!

  2. I simply couldn’t leave your web site before suggesting that I really loved the usual information an individual provide in your guests? Is going to be back continuously in order to check for new posts, thanks!

  3. Thank you for another informative site. Where else may just I get that type of info
    written in such an ideal manner? I’ve a mission that I am simply now operating on, and I
    have been on the look out for such info.

  4. Hello would you mind sharing which blog platform you’re using?

    I’m going to start my own blog soon but I’m having a hard time choosing between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design seems different then most blogs and I’m looking for something unique.
    P.S Sorry for getting off-topic but I had to ask!


Leave a Reply

Your email address will not be published.