Set Builder Notation: POS_λ(\alpha) Explained

In summary, this set is made up of the literal λ, the unit clause κ, and the two clauses κ and κ which are the intersection of κ and κ.
  • #1
gnome
1,041
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
  • #2
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 λ.
 
  • #3
Hmmm...

It becomes surprisingly clear when you put it that way.

Thanks.
 

1. What is Set Builder Notation?

Set Builder Notation is a way to represent a set of numbers or elements using a specific rule or condition. It is written as {x | x is a member of a set and satisfies a given condition}.

2. What does POS_λ(\alpha) mean in Set Builder Notation?

In Set Builder Notation, POS_λ(\alpha) represents the power set of a set α. This means that it is the set of all subsets of α, including the empty set and the set α itself.

3. How is Set Builder Notation used in mathematics?

Set Builder Notation is commonly used in mathematics to define sets in a concise and precise way. It allows for sets to be described in terms of a specific rule or condition, making it easier to work with and understand.

4. What is the difference between Set Builder Notation and Roster Notation?

The main difference between Set Builder Notation and Roster Notation is the way they represent sets. Set Builder Notation uses a rule or condition to define a set, while Roster Notation lists all the elements of a set within braces.

5. How is Set Builder Notation used in computer science?

In computer science, Set Builder Notation is used to define sets in programming languages and database systems. It allows for efficient and logical organization of data, making it easier to manipulate and analyze large amounts of information.

Similar threads

  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Math Proof Training and Practice
6
Replies
175
Views
20K
  • General Math
4
Replies
125
Views
16K
  • Math Proof Training and Practice
4
Replies
105
Views
12K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
3
Views
257
  • Math Proof Training and Practice
2
Replies
67
Views
10K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
3K
Back
Top