6
$\begingroup$

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$.

How complicated is $\mathcal T$? Is it a context-free language?

Does the answer depend on the fixed number of variables? I guess not... If one removes the limitation of the number of variables (and somehow adapts the notions of context-freeness to play nice with this...), does the answer change? I guess it does...

This question is a natural outcome of Doug's recent question here.

$\endgroup$
8
  • $\begingroup$ I am pretty sure it is not context-free... Anyhow: how hard is it to generate them all? $\endgroup$
    – Mariano Suárez-Álvarez
    Oct 17, 2011 at 7:30
  • 2
    $\begingroup$ $\Rightarrow$ is usually used for logical implication, while $\rightarrow$ is commonly used as a connective in propositional calculus. $\endgroup$
    – Asaf Karagila ♦
    Oct 17, 2011 at 7:42
  • 2
    $\begingroup$ Feel free to correct it to your preferred notation, Asaf. I doubt it matters here. $\endgroup$
    – Mariano Suárez-Álvarez
    Oct 17, 2011 at 7:45
  • $\begingroup$ I will when I have access to a real keyboard. Editing from iPhone is such a drag :-) $\endgroup$
    – Asaf Karagila ♦
    Oct 17, 2011 at 9:06
  • $\begingroup$ One way to allow infinitely many variables without changing the notion of context-freeness is to just name the variables $S, SS, SSS, SSSS, ...$. $\endgroup$
    – Qiaochu Yuan
    Oct 17, 2011 at 21:31

3 Answers 3

Reset to default
4
$\begingroup$

For a fixed number of variables, it's context free, regardless of the exact connectives used. To show this, we will construct a context-free grammar for the set of tautologies.

Let the number of variables be $n$. For each $f\colon \{0,1\}^n \rightarrow \{0,1\}$, there corresponds a non-terminal $S_f$ generating all formulas with truth table $f$. The starting symbol is $S_1$, where $1$ is the constant $1$ function.

For your connectives, here is the construction. For each projection function $p_i$, we add the production $$S_{p_i} \rightarrow x_i$$ ($x_i$ is a variable). For each $f$, we add the production $$S_f \rightarrow \lnot S_{1-f}.$$ For each $f_1,f_2$, we add the production $$S_{1-f_1(1-f_2)} \rightarrow S_{f_1} \Rightarrow S_{f_2}.$$

Now consider the case of an infinite number of variables. If there were a CFG for the set of all tautologies (with some fancy encoding), then you could decide whether a particular formula is a tautology in polynomial-time, so P=NP.

More to the point, suppose that the encoding we wish to use is strings in some appropriate (finite alphabet). If the language of all tautologies were context-free, then so would $\{ x_i \Rightarrow x_i : i \in \mathbb{N} \}$ (intersect with an appropriate regular language). It follows that the language of squares in the digits is context-free, which is false.

$\endgroup$
2
  • 1
    $\begingroup$ Last argument doesn't work with unary encoding: if $x_i$ is encoded as $S^i$ it gives language $\{S^i \Rightarrow S^i\}$ which is context-free. Should be fixable somehow... $\endgroup$
    – sdcvvc
    Oct 17, 2011 at 22:23
  • 1
    $\begingroup$ $\{(x_i \Rightarrow x_j) \Rightarrow (x_k \Rightarrow x_l)$ should work since it gives the language $\{a^i b^j a^i b^j\} \cup \{a^i b^j a^k b^k\}$. $\endgroup$
    – sdcvvc
    Oct 17, 2011 at 22:39
4
$\begingroup$

Yes, it's context-free. A formula is a tree, which can be traversed with a stack. As we traverse, we are evaluating four things:

  • x = 0, y = 0;
  • x = 0, y = 1;
  • x = 1, y = 0;
  • x = 1, y = 1.

In effect, we are evaluating four "substantiated formulas" in parallel. A substantiated formula is one with variables replaced by 0 or 1.

Let's get more precise and define the transition table. We assume that the formula is in pre-order, that is, operator before operands.

  • The initial state:
    • If the current symbol is "$\lnot$", push onto the stack the symbol "($\lnot$, operator, ?, ?, ?, ?)" and go to the initial state.
    • If the current symbol is "$\to$", push onto the stack the symbol "($\to$, operator, ?, ?, ?, ?)" and go to the initial state.
    • If the current symbol is "x", go to the (0, 0, 1, 1) state.
    • If the current symbol is "y", go to the (0, 1, 0, 1) state.
  • The (a, b, c, d) state:
    • If the top symbol of the stack is "($\lnot$, operator, ?, ?, ?, ?)", pop the stack and go to the ($\lnot$a, $\lnot$b, $\lnot$c, $\lnot$d) state.
    • If the top symbol of the stack is "($\to$, operator, ?, ?, ?, ?)", pop the stack, push "($\to$, first operand, a, b, c, d)", go to the initial state.
    • If the top symbol of the stack is "($\to$, first operand, e, f, g, h)", pop the stack, go to the (e $\to$ a, f $\to$ b, g $\to$ c, h $\to$ d) state.

The (a, b, c, d) state is a template. There are actually 16 such states: the (0, 0, 0, 0) state, the (0, 0, 0, 1) state, the (0, 0, 1, 0) state, the (0, 0, 1, 1) state and so on.

Similarly, the third rule in the generic (a, b, c, d) state is a generic rule. There are 16 such rules, with (e, f, g, h) = (0, 0, 0, 0), (0, 0, 0, 1), and so forth.

The (1, 1, 1, 1) state has one extra rule:

  • If the stack is empty, go to the accepting state.

OK, this program has a weak point as discussed in the second comment. Now let's define a perfect version.

Assume two things: 1) The formula is in pre-order, and 2) there is a pair of parenthesis around each sub-formula.

Now, the transition table:

  • start:
    • if read = (, go to operator.
  • operator:
    • if read = ~, push (~, ?, ?, ?, ?), go to start.
    • if read = ->, push (->, ?, ?, ?, ?), go to start.
    • if read = x, push (ret, 0, 0, 1, 1), go to eval.
    • if read = y, push (ret, 0, 1, 0, 1), go to eval.
  • eval:
    • if read = ), let the top element be (ret, a, b, c, d), pop, go to (a, b, c, d).
  • (a, b, c, d):
    • if read = ) and top = (~, ?, ?, ?, ?), pop, go to (~a, ~b, ~c, ~d).
    • if read = ) and top = (->, e, f, g, h), pop, go to (e -> a, f -> b, g -> c, h -> d).
    • if read = ( and top = (->, ?, ?, ?, ?), pop, push (->, a, b, c, d), go to operator.
  • (1, 1, 1, 1) has one extra rule:
    • if the stack is empty, accept.
$\endgroup$
2
  • $\begingroup$ This works if the number of variables is finite. $\endgroup$
    – Zirui Wang
    Oct 17, 2011 at 10:09
  • $\begingroup$ One weak point is that I allowed $\epsilon$-transitions as well as transitions that pop the stack but do not read the input symbol. There is a way to eliminate the second kind of transitions, that is, we put a pair of parenthesis around each sub-formula. $\endgroup$
    – Zirui Wang
    Oct 17, 2011 at 10:16
3
$\begingroup$

Generalization of Yuval's answer:

For any finite set $A$ and operations $o_i \colon A^2 \to A$ the language of expressions using elements of $A$ and infix operators $o_i$ that evaluate to fixed $a \in A$ is context-free. Here $A = \{0,1\}^n \to \{0,1\}$.

If you regard the expressions as trees not words, it will be a regular tree language (recognizable with finite tree automaton).

I remember an exercise in automata theory: the set of Boolean formulas (as words) using 0,1,$\vee$,$\wedge$,$\neg$,(,) evaluating to 1 is regular, provided that arbitrary answer is allowed when input has mismatched brackets.

As a consequence of this there should exist a regular language $L$ such that the set of tautologies is $L \cap R$ where $R$ is the context-free language of all well-formed formulas (tautologies or not).

$\endgroup$

You must log in to answer this question.

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