5

As I recall in propositional logic, it was possible to draw truth tables for the arguments such as for:

(P ∨ R)   [I live in Paris or I live in Rome]
Therefore, (~P ⊃ R)  [If I don't live in Paris then I live in Rome]

You have a truth table given as:

   +---+----+---------+------------+
   | P | R  | (P ∨ R) |  (~P ⊃ R) |
   +---+----+---------+------------+
   | 1 | 1  |    1    |     1      |
   | 1 | 0  |    1    |     1      |
   | 0 | 1  |    1    |     1      |
   | 0 | 0  |    0    |     0      |
   +---+----+---------+------------+

But when you have argument in predicate logic such as:

~(∃x)Fx
Therefore, (x)~(Fx • Gx)

Can the similar form of truth table be derived to test for validity rather than a proof solving approach?

And, one of my other quick question is: Is it possible to convert the above argument (with P and R) given in Propositional logic into Predicate logic or it can only be written in propositional logic?

7

NO, because validity for predicate logic means true in all interpretations, and thus we have to take into account also interpretations with infinite domains, like the set N of natural numbers.


Every tautology of propositional logic, like P ∨ ¬P, can produce an unlimited supply of valid predicate logic formulae through uniform substitution, i.e. by replacing every occurrence of a propositional letter by an atom of predicate logic language.

For example, from P ∨ ¬P we can produce the valid formulae :

∀xP(x) ∨ ¬∀xP(x)

∃xP(x) ∨ ¬∃xP(x)

and so on.

With your example, from P ∨ R ⊨ ¬P ⊃ R we can derive e.g. :

∀xP(x) ∨ ∃xQ(x) ⊨ ¬∀xP(x) ⊃ ∃xQ(x).


But not all valid formulae of predicate logic are "substitution instances" of tautology; the formula ∀x(x=x) is valid but we can get it by uniform substitution only from the propositional logic formula P, that is not a tautology.


Note

As per Owen's answer, we have to note that Monadic predicate calculus is a fragment of first-order logic that is decidable.

  • How can I read the translation? For example: Does (∃x)Q(x) here means For some x, x lives in Rome and ∀x I suppose means For all x? – cpx Oct 2 '15 at 17:00
  • @cpx - Yes : ∀xP(x) ∨ ∃xQ(x) can be read as : "every x lives in Paris or some x lives in Rome". – Mauro ALLEGRANZA Oct 2 '15 at 18:43
  • +1 for Mauro's excellent answer. I also want to add however, that there there is a procedure similar to truth tables for predicate logic, called a truth tree. Truth tress are like truth tables in that they provide an algorithmic way to check for the validity of an argument. Here is a primer: tellerprimer.ucdavis.edu/pdf/2ch7.pdf – shane Mar 19 '16 at 13:08
1

Does predicate logic have truth tables?

Yes! If we assume there are 4 function values (1,2,3,0) of Fx then monadic truth functions have truth tables to resolve expressions such as ~∃xFx -> ~∃x(Fx & Gx).

~1=0, ~2=3, ~3=2, ~0=1.

∃1=T, ∃2=T, ∃3=T, ∃0=F.

∀xFx =def ~∃x~Fx.

∀1=T, ∀2=F, ∀3=F, ∀0=F.

∀xFx -> ∃xFx, is tautologous.

Proof:

(∀1 -> ∃1) & (∀2 -> ∃2) & (∀3 -> ∃3) & (∀0 -> ∃0).

ie. (T -> T) & (F -> T) & (F -> T) & (F -> F).

(T) & (T) & (T) & (T).

That is ∀xFx -> ∃xFx, is true for all function values of Fx.

In the same way we can show that ~∃xFx -> ~∃x(Fx & Gx) is a tautology.

  • 1&1=1, 1&2=2, 1&3=3, 1&0=0, 2&1=2, 2&3=0, 2&0=0, 3&1=3, 3&2=0, 3&3=3, 3&0=0, 0&1=0, 0&2=0, 0&3=0, 0&0=0. – Owen Mar 19 '16 at 12:03
  • 1
    Within predicate logic how could we possibly assume the function's output is restricted to "4 function values" ??? – virmaior Mar 19 '16 at 12:07
  • Eliran H 3, can you provide an example that fails? – Owen Mar 19 '16 at 12:16
  • @Owen I'm fixing my comment: you have showed that '∀xFx -> ∃xFx' is true in the given model but not that it is true in every possible model and therefore it can't be taken as a proof for being a tautology. There's a big difference. So no, you can't use truth table for deciding validity in predicate logic – Eliran Mar 19 '16 at 12:27
  • 1
    My claim is that all monadic expressions are shown to be valid or invalid by this method. – Owen Mar 19 '16 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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