Logic for Computer Scientists/Predicate Logic/Predicate Logic

Predicate Logic

When we introduced propositional logic we argued in treating the electrical circuit example (circuit), that a string like $high(inv1,o)$ can be read intuitively as "the output of inverter 1 is high", but then we abstracted from this internal structure of the proposition and further on we represented the proposition by a simple string like "the_output_of_inverter_1_ is_high". In the formal parts of the calculus we even assumed more abstract just a given countable set of propositions $\{P_{1},\cdots ,P_{i},\cdots \}$ . Until now, we investigated a logical language that was able to deal with connecting these propositions, In this section we will have a closer look into the structure of propositions. We will be able to explicitly refer to objects like the inverter $inv1$ or its output $o$ in the sentences of our language,. Besides this domain, we will introduce the new concept of a variable, which stands for an arbitrary object of our domain. Hence, we will be able to write e.g. $high(x,o)$ to denote the fact that the output of a $x$ is high. As a consequence of this concept we will have quantifiers, which allow for sentences like $\exists x\;high(x,o)$, with an intended meaning that there exists an object $x$, whose output $o$ is high, or $\forall x\;high(x,o)$ with an intended meaning that for all objects $x$ output $o$ is high,

Together with these new concepts it will be possible to express rather abstract properties of elements from the domain. Assume, e.g. that we want to introduce the concept of elements in a circuit to be connected. We could say $connected(inv1,inv2)$ and $connected(inv2,inv3)$. Now, with the intended meaning of being connected, we can assume, that $inv1$ and $inv3$ are connected as well. Of course, we could introduce the new sentence $connected(inv1,inv3)$ to express this; but the disadvantage is obvious: this have to be done for all objects from our domain. In predicate logic this property of transitivity of connectedness can be expressed without referring to explicit objects by the following sentence:

$\forall x\forall y\forall z((connected(x,y)\land connected(y,z))\to connected(x,z))$