Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
1  
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... –  sdcvvc Oct 17 '11 at 22:23
1  
$\{(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\}$. –  sdcvvc Oct 17 '11 at 22:39

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.
share|improve this answer
    
This works if the number of variables is finite. –  Zirui Wang Oct 17 '11 at 10:09
    
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. –  Zirui Wang Oct 17 '11 at 10:16

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.