2

If we have a sequent such as $$ \sim\left ( P\Rightarrow Q \right )\Rightarrow R$$it is always possible to find the truth table by slowly working through the columns. Doing this is standard bookwork for a first course in logic theory.

However, I was wondering if the converse necessarily true. In other words, given a truth table with 1's and 0's placed randomly in the $2^n$ rows, will there always exist a sequent that satisfies it?

If so, I was thinking that a method to deduce it would be via trial and error, though this of course impractical. Would there be a better way of constructing it? I can see that it would not be unique as an equivalent sequent would of course yield the same truth table.

Trogdor
  • 10,331
  • 1
    You seem to be using the term "sequent" with a different meaning than Wikipedia. Could you please define it? – joriki Apr 19 '16 at 19:22
  • Ah, I am referring to general statements like the example I have above. I am actually not too sure what the proper term for these are, unless the word 'formula' suffices. – Trogdor Apr 19 '16 at 19:24
  • 2
    For each $P,Q,R,\dots$ take either $P$ or $\neg P$ and $\land$ your choices together. That gives you something which is only 1 for a single combination of the $P,Q,R,\dots$. Then $\lor$ an appropriate collection of these things together. – almagest Apr 19 '16 at 19:25

3 Answers3

2

Given an WFF $w(X_1, \dots, X_n)$, we can write $$w = (w_0(X_1, \dots, X_{n-1}) \wedge \sim\!\!X_n)\, \vee\, (w_1(X_1, \dots, X_{n-1}) \wedge X_n)$$ for some WFFs $w_p(X_1, \dots, X_n) = w(X_1, \dots, X_{n-1}, p)$. Induct on $n$.

anomaly
  • 25,364
  • 5
  • 44
  • 85
2

Yes, given a truth table with $2^n$ rows, we could produce a proposition $P_i(a_1,\ldots,a_n)$ that has the truth value of the $i$th row, e.g. if $n=3$ and we have that $P_3(a_1,a_2,a_3)=P_3(1,0,1)=1$, then we could take $P_3=a_1\overline{a_2}a_3$. The disjunction of all the $P_i\,$s will produce a formula with the desired truth table.

Workaholic
  • 6,763
1

Example

$\begin{array}{c|c|c|c|c} \ A&B&P(A,B)&\space\\\hline T&T&T&A\land B\\ T&F&F&\neg (A\land \neg B)\\ F&T&F&\neg(\neg A \land B)\\ F&F&T&\neg A \land \neg B \end{array}$

$P(A,B) \iff (A\land B) \lor\neg (A\land \neg B)\lor \neg(\neg A \land B)\lor (\neg A \land \neg B)$

Dan Christensen
  • 14,529