Homework 3 CLARIFICATIONS Due Feb 27

CLARIFY problem 1:

1) TYPO:

I had written:

It is possible that a Boolean formula has $n$ variables, but just setting two of the variables a certain way makes the entire formula true, independent of the other variables (e.g., $(x\wedge \neg z) \vee (y_1 \wedge \cdots \wedge y_{n-1})$ is true if $x=T$ and $y=F$).

TYPO: should be x=T and z=F

2) EXAMPLES

$A$ is the set of all formulas where there are 100 variables so that if you set THOSE you get it to be TRUE independent of how you set the other vars.

EXAMPLE:

let $\phi(x_1,\ldots,x_{20000})$ be any boolean formula in 3-CNF form and let $\psi(x_1,\ldots,x_{20000})$ be the formula

$( \neg(x_{10}) \wedge x_{20} \wedge \neg(x_{30}) \wedge x_{40} \wedge \neg... ...\wedge etc \neg(x_{990})\wedge x_{1000} ) \vee \phi(x_1,\ldots,x_{20000})$

This formula $\psi$ IS in the set $A$ since it is in 3-CNF form (I am allowing a clause to have $\le 3$ literals, Note that many clauses here have 1 literal.) AND there is a way to set 100 of the vars to make psi true:

$x_{10}=F, x_{20}=T, x_{30}=F, x_{40}=T, \ldots, x_{1000}=T.$

The formula $\psi$ is TRUE nomatter how the rest of the vars are set.

EXAMPLE

The formula

$(x_1 \wedge \cdots \wedge x_{101})$ is NOT in $A$ since no matter which 100 variables I set to values I cannot gurantee that the formula is true.

Note that this formula is in SAT but NOT in $A$