6

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?

3 Answers 3

9

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.

4
  • 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, 2015 at 17:00
  • @cpx - Yes : ∀xP(x) ∨ ∃xQ(x) can be read as : "every x lives in Paris or some x lives in Rome". Oct 2, 2015 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
    – user5172
    Mar 19, 2016 at 13:08
  • @MauroALLEGRANZA, I have a similar question, but with a finite domain of discourse. I tried to create a truth table to check the validity of the argument in my question, but one of the premises involves the universal quantifier and I'm not sure if I have expressed it correctly in the table. If possible, could you please take a look at the question here at your convenience?
    – user51462
    Sep 17 at 1:39
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.

7
  • 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, 2016 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, 2016 at 12:07
  • Eliran H 3, can you provide an example that fails?
    – Owen
    Mar 19, 2016 at 12:16
  • 1
    @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, 2016 at 12:27
  • 1
    My claim is that all monadic expressions are shown to be valid or invalid by this method.
    – Owen
    Mar 19, 2016 at 13:16
-1

Answer. I guess that most of the time philosophers reason about properties and relations of variables that have finite number of possible values. For that specific case there is something very similar to truth tables for first order logic. So maybe you are looking for languages that are describing databases like ER-model, EER-model, relational model, relational algebra, UML and ORM. These languages essentially are first order logic for discrete variables. Databases feels somewhat like truth-tables-2.0.

Connection between databases, first order logic and truth tables. You may be unsatisfied with thing that these languages deal with tables that are filled with text. If you like You can assign numbers to table names, field names and number all possible values in the table. So you'll get tables filled with natural numbers. If you like you can obtain tables that contain the same information, but are filled with zeros or ones. Aggregation ( in EER model) is somewhat similar to conjunction and disjunction, and arrow drawn from one table to other (in database schemas) somewhat similar to implication. Types of arrows somewhat resemble quantifiers. When you reason about database, concepts from Relational algebra are very useful. Using Cartesian product and taking subset of it you can form relations.

Similarity between truth tables and databases. Lets consider propositional logic example. You have some formula α(A,B,C). It has truth table. All formulas that have the same truth table are equivalent. Now imagine that all rows in truth table of α(A,B,C) that corresponds to α(A,B,C)=0 were deleted. This truth table without zero values of formula carries the same information as the original.

Similarly, imagine there are two database schemas, there is corresponding data base. If two schemas are equivalent than thy have the same database. Database schema consists of "tables" that are connected with arrows. These "tables" consist of name and list of fields (e.g. variables). So arrows connect fields of these "tables". So there is net of these tables connected with arrows. It is possible to obtain unique table for database. This can be done (if I remember correctly) by natural join operator.

Literature. You might be interested in Peters Chens work "English sentence structure and entity-relationship diagrams" and Sven Hartmanns work "English sentence structures and EER modeling". I also like https://www.tutorialspoint.com/dbms/er_model_basic_concepts.htm. I like Therrys Halpins book "Information modeling and relational databases". These languages may seem mystic to you, but they are very easy if you find proper enterance point, so I suggest to start with data bases shemas, for example MS acess or LO base databases. I Like tutorials that are on https://www.thefrugalcomputerguy.com/ website. Than you can start learning ER-model, than UML.

You must log in to answer this question.

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