Skip to main content
Engineering LibreTexts

2.E: First Order Logic and Automated Reasoning in a Nutshell (Excercises)

  • Page ID
    6410
  • Exercise \(\PageIndex{1}\)

    What is the difference between syntax and semantics for a logic?

    Exercise \(\PageIndex{2}\)

    What is a theory?

    Exercise \(\PageIndex{3}\)

    Name the four core components for automated reasoning.

    Exercise \(\PageIndex{4}\)

    Describe the procedure for tableau reasoning in four shorts sentences.

    Exercise \(\PageIndex{1}\)

    Write in one natural language sentence what the following sentences in First-Order Logic state.

    a. \(\forall x(Lion(x)\to Mammal(x))\)

    b. \(\forall x(PC(x)\to\exists y,z(hasPart(x,y)\wedge connected(x,z)\wedge CPU(y)\wedge Monitor(z)))\)

    c. \(\forall x,y(hasProperPart(x,y)\to\neg hasProperPart(y,x))\)

    Answer

    (a) All lions are mammals.

    (b) Each PC has as part at least one CPU and at least one Monitor connected

    (c) Proper part is asymmetric.

    Exercise \(\PageIndex{2}\)

    Formalize the following natural language sentence into First-Order Logic.

    a. Each car is a vehicle.

    b. Every human parent has at least one human child.

    c. Any person cannot be both a lecturer and a student editor of the same course.

    Answer

    (a) \(\forall x(Car(x)\to Vehicle(x))\)

    (b) \(\forall x(HumanParent(x)\to\exists y(haschild(x,y)\wedge Human(y)))\)

    (c) \(\forall x,y(Person(x)\wedge Course(y)\to\neg (lecturerOf(x,y)\wedge studentOf(x,y)))\)

    Exercise \(\PageIndex{3}\)

    Consider the structures in Figure 2.3.2, which are graphs.

    a. Figures 2.3.2-A and B are different depictions, but have the same descriptions w.r.t. the vertices and edges. Check this.

    Screenshot (59).png

    Figure 2.3.1: Explanation of the tableaux in Figure 2.2.2.

    b. C has a property that A and B do not have. Represent this in a first-order sentence.

    c. Find a suitable first-order language for A (/B), and formulate at least two properties of the graph using quantifiers.

    Screenshot (60).png

    Figure 2.3.2: Graphs for Exercise 2.3.3 (figures A-C) and Exercise 2.3.4 (figure D).

    Answer

    (b) There exists a node that does not participate in an instance of \(R\), or: it does not relate to anything else: \(\exists x\forall y.\neg R(x,y)\).

    (c) \(\mathcal{L} =\langle R \rangle\) as the binary relation between the vertices. Optionally, on can add the vertices as well. Properties:

    \(R\) is symmetric: \(\forall xy.R(x,y)\to R(y,x)\).

    \(R\) is irreflexive: \(\forall x.\neg R(x,x)\).

    If you take into account the vertices explicitly, one could say that each note participates in at least two instances of \(R\) to different nodes.

    Exercise \(\PageIndex{4}\)

    Consider the graph in Figure 2.3.2, and first-order language \(\mathcal{L} =\langle R\rangle\), with \(R\) being a binary relation symbol (edge).

    a. Formalize the following properties of the graph as \(\mathcal{L}\)-sentences:

    (i) \((a, a)\) and \((b, b)\) are edges of the graph;

    (ii) \((a, b)\) is an edge of the graph;

    (iii) \((b, a)\) is not an edge of the graph. Let \(T\) stand for the resulting set of sentences.

    b. Prove that \(T\cup\{\forall x\forall yR(x,y)\}\) is unsatisfiable using tableaux calculus.

    Answer

    (a) \(R\) is reflexive (a thing relates to itself): \(\forall x.R(x,x)\) ∀x.R(x, x).

    \(R\) is asymmetric (if \(a\) relates to \(b\) through relation \(R\), then \(b\) does not relate back to \(a\) through \(R\)): \(\forall xy.R(x,y)\to\neg R(y,x)\).

    Exercise \(\PageIndex{5}\)

    Let us have a logical theory \(\Theta\) with the following sentences:

    • \(\forall xPizza(x), \forall xPizzaT(x), \forall xPizzaB(x)\), which are disjoint
    • \(\forall x(Pizza(x) \to\neg PizzaT(x))\),
    • \(\forall x(Pizza(x)\to\neg PizzaB(x))\),
    • \(\forall x(PizzaT(x)\to\neg PizzaB(x))\),
    • \(\forall x,y(hasT(x,y)\to Pizza(x)\wedge PizzaT(y))\),
    • \(\forall x,y(hasB(x,y)\to Pizza(x)\wedge PizzaB(y))\),
    • \(\forall x(ITPizza(x)\to Pizza(x))\), and
    • \(\forall x(ITPizza(x)\to\neg\exists y(hasT(x,y)\wedge FruitT(y))\), where
    • \(\forall x(VegeT(x)\to PizzaT(x))\) and
    • \(\forall x(Fruit(x)\to PizzaT(x))\).

    Task (read in full first before attempting it):

    a. A Pizza margherita has the necessary and sufficient conditions that it has mozzarella, tomato, basilicum and oil as toppings and has a pizza base. Add this to \(\Theta\). Annotate you commitments: what have you added to \(\Theta\) and how? Hint: fruits are not vegetables, categorize the toppings, and “necessary and sufficient” is denoted with \(\leftrightarrow\).

    b. We want to merge our new \(\Theta\) with some other theory \(\Gamma\) that has knowledge about fruits and vegetables. \(\Gamma\) contains, among other formulas, \(\forall x(Tomato(x)\to Fruit(x))\). What happens? Represent the scenario formally, and prove your answer.

    Actually, this is not easy to figure out manually, and there are ways to automate this, which you will do later in Chapter 4.