I'm reading the book Mathematical logic by Cori and Lascar and, though I understand now what is a canonical disjunctive normal form, I can't understand what is written here:

Let $X$ be a non-empty subset of $\{0,1\}^n$ and let $F_X$ be the formula: \begin{equation} \bigvee_{(\varepsilon_1,...,\varepsilon_n) \in X }\left(\bigwedge_{1\leq i \leq n}\varepsilon_i A_i\right)\ \end{equation}

Then the formula $F_X$ is satisfied by those distributions of truth values $\delta_{\varepsilon_1 ... \varepsilon_n}$ for which $(\varepsilon_1, ..., \varepsilon_n) \in X$ and only by these.


1 Answer 1


We can read the formula inside the parentheses as a sort of algebraic multiplication : $0A_1 ∧ 1A_2 ∧ \ldots ∧ 0A_n$, that corresponds to formula :

$¬A_1 ∧ A_2 ∧ \ldots ∧ ¬A_n$.

See page 34 :

an element $(\varepsilon_1, \varepsilon_2,\ldots, \varepsilon_n)$ of $\{ 0,1 \}^n$ is an $n$-uple of booleans (aka : truth values).

And $\delta_{\varepsilon_1, \varepsilon_2,\ldots, \varepsilon_n}$ is the distribution of truth values that assigns to propositional variable $A_i$ the truth value $\varepsilon_i$.

For each propositional variable $A$ and for each $\varepsilon \in \{ 0,1 \}$ we have that :

$\varepsilon A$ denotes $A$ if $\varepsilon =1$ and $\lnot A$ if $\varepsilon =0$.

  • $\begingroup$ Thanks. But that's not where i'm stuck: $\varepsilon_i A_i$ can only be defined in $X$ which can have less elements than $\{0,1\}^n$, so I don't get how we can intersect from $i$ to $n$. $\endgroup$
    – oyster
    Dec 10, 2019 at 11:18
  • $\begingroup$ @ZeD --- not clear... Presumably we have a formula $F$ which is a truth-function of $n$ prop variables $A_1,\ldots, A_n$. Thus, we need a corresponding $(\varepsilon_1,\ldots, \varepsilon_n) \in \{ 0,1 \}^n$. The value of $n$ is the same. $\endgroup$ Dec 10, 2019 at 11:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .