patternMinor
What are predicates of a sentence?
Viewed 0 times
arepredicatessentencewhat
Problem
I am reading Handbook of Satisfiability in which they say:
An algebraic structure, or simply structure, consists of a non-empty set of
objects existing in the world $w$, called the domain and denoted below by $D$, and
a function, called an interpretation and denoted below by $R$, that assigns to each
constant an entity in $D$, to each predicate a relation among entities in $D$, and to
each functor a function among entities in $D$.
A sentence $p$ is said to be true in $w$
if the entities chosen as the interpretations of the sentence’s terms and functors
stand to the relations chosen as the interpretation of the sentence’s predicates.
In this context, could you help me with some example of predicates of a sentence? And what does "stand to" mean here?
I am not a native English speaker, maybe this is why I can not understand this claim.
An algebraic structure, or simply structure, consists of a non-empty set of
objects existing in the world $w$, called the domain and denoted below by $D$, and
a function, called an interpretation and denoted below by $R$, that assigns to each
constant an entity in $D$, to each predicate a relation among entities in $D$, and to
each functor a function among entities in $D$.
A sentence $p$ is said to be true in $w$
if the entities chosen as the interpretations of the sentence’s terms and functors
stand to the relations chosen as the interpretation of the sentence’s predicates.
In this context, could you help me with some example of predicates of a sentence? And what does "stand to" mean here?
I am not a native English speaker, maybe this is why I can not understand this claim.
Solution
Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be
$$
{\sf eats}({\sf cat}, {\sf head}({\sf tuna}))
$$
Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.
A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows:
$$
\mbox{World $w$: }\qquad\qquad
\begin{array}{l}
[\![ {\sf cat} ]\!]^c = 5 \\
[\![ {\sf tuna} ]\!]^c = 4 \\
[\![ {\sf squirrel} ]\!]^c = 2 \\
\ldots \\
[\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\
\ldots \\
[\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \}
\end{array}
$$
(A structure can define more symbols than those used in the formula, hence
the $\sf squirrel$ above.)
Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$.
Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$.
Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.
The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have
$$
[\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c))
$$
which is
$$
< (5, g(4))
$$
i.e.
$$
5 < \pi \cdot 4
$$
which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.
$$
{\sf eats}({\sf cat}, {\sf head}({\sf tuna}))
$$
Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.
A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows:
$$
\mbox{World $w$: }\qquad\qquad
\begin{array}{l}
[\![ {\sf cat} ]\!]^c = 5 \\
[\![ {\sf tuna} ]\!]^c = 4 \\
[\![ {\sf squirrel} ]\!]^c = 2 \\
\ldots \\
[\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\
\ldots \\
[\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \}
\end{array}
$$
(A structure can define more symbols than those used in the formula, hence
the $\sf squirrel$ above.)
Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$.
Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$.
Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.
The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have
$$
[\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c))
$$
which is
$$
< (5, g(4))
$$
i.e.
$$
5 < \pi \cdot 4
$$
which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.
Context
StackExchange Computer Science Q#53610, answer score: 5
Revisions (0)
No revisions yet.