Set Builder Notation: POS_λ(\alpha) Explained

Click For Summary
SUMMARY

The discussion focuses on the set-builder notation \text{POS}_\lambda(\alpha) as defined in the context of propositional logic and CNF formulas. It clarifies that \text{POS}_\lambda(\alpha) represents the union of the set of \lambda-neutral clauses and the \lambda-positive clauses, explicitly excluding all instances of the literal \lambda from those clauses. The notation is derived from the work in "Computability, Complexity and Languages" by Davis, Sigal, and Weyuker, specifically addressing the Davis-Putnam rules for manipulating CNF formulas.

PREREQUISITES
  • Understanding of propositional logic and CNF (Conjunctive Normal Form) formulas
  • Familiarity with set-builder notation and its applications in logic
  • Knowledge of positive, negative, and neutral clauses in propositional logic
  • Basic concepts of algorithms related to CNF formula manipulation
NEXT STEPS
  • Study the Davis-Putnam algorithm for CNF formula manipulation
  • Learn about the implications of \lambda-positive and \lambda-negative clauses in propositional logic
  • Explore advanced set theory concepts relevant to logic and computation
  • Review the terminology and definitions in "Computability, Complexity and Languages" by Davis, Sigal, and Weyuker
USEFUL FOR

This discussion is beneficial for students and professionals in computer science, particularly those focusing on logic, algorithm design, and computational complexity. It is especially relevant for individuals working with CNF formulas and propositional logic.

gnome
Messages
1,031
Reaction score
1
How would you describe this set in plain English:
[tex]\text{POS}_\lambda(\alpha) = \alpha_\lambda^0 \cup \{\kappa - \{\lambda\}|\kappa \in \alpha_\lambda^+\}[/tex]

where:
[itex]\lambda[/itex] is a literal
[itex]\kappa[/itex] is an [itex]\vee[/itex] clause with the set [itex]\kappa = \vee_{j\leq m}\;\lambda_j[/itex] represented as [itex]\kappa = \{\lambda_j|j \leq m \}[/itex]
[itex]\{\lambda\}[/itex] is a unit clause consisting of just a single literal [itex]\lambda[/itex]
a CNF formula [itex]\alpha[/itex] is a set [itex]\alpha = \wedge_{i\leq n}\;\kappa_i[/itex] represented as [itex]\alpha = \{\kappa_i|i \leq n \}[/itex]

a clause [itex]\kappa[/itex] is called [itex]\lambda-positive[/itex] if [itex]\lambda \in \kappa[/itex]
a clause [itex]\kappa[/itex] is called [itex]\lambda-negative[/itex] if [itex]\neg \lambda \in \kappa[/itex]
a clause [itex]\kappa[/itex] is called [itex]\lambda-neutral[/itex] if [itex]\kappa[/itex] is neither [itex]\lambda-positive[/itex] nor [itex]\lambda-negative[/itex]
if [itex]\alpha[/itex] is a set of clauses, [itex]\alpha_\lambda^+[/itex] is the set of [itex]\lambda-positive[/itex] clauses of [itex]\alpha[/itex], [itex]\alpha_\lambda^-[/itex] is the set of [itex]\lambda-negative[/itex] clauses of [itex]\alpha[/itex], and [itex]\alpha_\lambda^0[/itex] is the set of [itex]\lambda-neutral[/itex] clauses of [itex]\alpha[/itex].


At first, I was reading [itex]\text{POS}_\lambda(\alpha)[/itex] as the union of the [itex]\lambda-neutral[/itex] clauses of [itex]\alpha[/itex] with the [itex]\lambda-positive[/itex] clauses of [itex]\alpha[/itex] but excluding the unit clause [itex]\{\lambda\}[/itex]. But apparently it is intended to be read as the union of the [itex]\lambda-neutral[/itex] clauses of [itex]\alpha[/itex] with the [itex]\lambda-positive[/itex] clauses of [itex]\alpha[/itex] but with ALL of the [itex]\lambda[/itex] terms EXCLUDED from those clauses.

WHY is it read that way? Or, to put it another way, why was it not written as [itex]\text{POS}_\lambda(\alpha) = \alpha_\lambda^0 \cup \{\kappa - \lambda|\kappa \in \alpha_\lambda^+\}[/itex]. (Why did they put their [itex]\lambda[/itex] in brackets {}?) And how would you write set-builder notation for "the [itex]\lambda-positive[/itex] clauses of [itex]\alpha[/itex] but excluding just the unit clause [itex]\{\lambda\}[/itex]."

This comes from Computability, Complexity and Languages by Davis, Sigal and Weyuker, section 12.4, discussion of the Davis-Putnam rules for algorithms to manipulate CNF formulas.
 
Physics news on Phys.org
Bleh, one day I'll learn this terminology.

The expression A - B is the set formed from everything in the set A that is not in the set B. Thus, to "remove" the element λ from the set κ, you have to subtract off the singleton set containing λ.
 
Hmmm...

It becomes surprisingly clear when you put it that way.

Thanks.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
4K
  • · Replies 42 ·
2
Replies
42
Views
12K
  • · Replies 175 ·
6
Replies
175
Views
28K
  • · Replies 125 ·
5
Replies
125
Views
21K
  • · Replies 105 ·
4
Replies
105
Views
15K
  • · Replies 67 ·
3
Replies
67
Views
17K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 4 ·
Replies
4
Views
5K