KRR - Unit 2: Sets, Set Theory, Truth Tables and Logic

Overview

As per the course website, "This unit introduces the underlying principles of reasoning: that is set theory, logic, and truth tables. It also provides a number of exercises to provide practice in manipulating sets and truth tables."

My Reflection

Overall Reflection

As it is clear from its title, the unit was all about set theory, truth tables and logic. We were mainly introduced to these concepts through two readings. The first is the opening four chapters from Mathematical Methods in Linguistics by Partee, Meulen and Wall (1990), and the second is a a blog on truth tables.

However, I had to face the fact that these were new concepts for me as I had to solve the questions in the preparation booklet for next week's seminar. The booklet had excercises on propositional logic and truth tables. To solve those, the readings -or rather, what I understood from them- were not enough, so I had to look for additional resources online. Eventually, I managed to solve the excercises, and the posed questions started to make sense to me. Overall, the concepts and entailed problems were interesting to me, and I am glad that I had the chance to be exposed to them. I hope I will have the opportunity to further understand, explore and build on them in the next units, or in the future self-learning.

In addition to the readings and the excercises booklet, we also had to respond to at least two peers as part of the collaborative learning discussion that we started in Unit 1. My responses, as well as the other artefacts are detailed in the section below.

Artefacts

1. Collaborative Learning Discussion 1: Responding to Peers

In this unit, we were required to respond to at least two peers as part of the collaborative learning discussion that we started in Unit 1, on whether knowledge representation is a recent phenomenon related to computing technology, and how reasoning is related to knowledge representation. Below are the peers' posts that I responded to, along with my responses.

Peer Post 1

Dear Colleagues,

After reading the interesting articles of Professor Thijs Weststeijn and the statement, which is the base of our first discussion forum, which affirms that Knowledge Representation is a recent phenomenon is quite difficult to fully agree with the latter statement.

Knowledge Representation (shortened in KR), as defined in Brachman and Levesque (2004) “is that part of AI that is concerned with how an agent uses what it knows in deciding what to do.” If we just take this definition, we could affirm that KR is just a recent phenomenon coming together with the AI.
But, reading the article of Professor Weststeijn he also notices that Samuel Van Hoogstraten, a pupil of the painter Rembrandt, considered visual imagery serves as a more basic and essential form of communication than written language based on alphabetic systems. (Van Hoogstraten, S. in Weststeijn, T. 2011: 239-240).
Based on that, it cannot be said that the KR is just a recent phenomenon, but it looks like was object of study since centuries.

About the topic about KR being useful without reasoning, I can affirm that both KR and reasoning are not separable and, as suggested by Davis et al. (1993: 29) “representation and reasoning are inextricably intertwined: We cannot talk about one without also unavoidably discussing the other”.

I am looking forward to discussing with all of you.

Thanks,
Andrea

References:

My Response to Peer Post 1

Hi Andrea.

Your post brings up some solid points about the history and development of Knowledge Representation and Reasoning (KRR). It's clear that KR didn't just appear out of nowhere with artificial intelligence; its core ideas go back to longstanding philosophical debates about what knowledge is and how it can be structured (Brachman and Levesque, 2009).

The link between KR and reasoning is fundamental. As the research highlights, you can't really have meaningful reasoning without first figuring out how knowledge is represented, whether in human minds or in machines (Bouquet et al., 2003; Delgrande et al., 2023). The philosophical side—epistemology, ontology, logic—has laid the groundwork for these discussions much earlier (Maedche, 2002; Truncellito, 2024).

So, while the urgency of dealing with KR might have picked up alongside AI and computational systems, the basic concerns have always been there. Representing knowledge is what makes reasoning possible, and the two are pretty much joined at the hip.

References


Peer Post 2

I disagree with the statement that knowledge Representation is merely a recent computing phenomenon. As Weststeijn (2011) explains, the systematic attempt to represent knowledge through structured symbols has deep historical roots extending back centuries. The seventeenth-century Netherlands witnessed sophisticated debates about pictography, universal characters, and the philosophical encoding of concepts which were essentially early forms of knowledge representation. Thinkers such as Leibniz envisioned a characteristica universalis, a symbolic language to represent human thought systematically, anticipating modern approaches to KR in AI. This historical continuity shows that while computing has transformed KR’s scale and implementation, the underlying intellectual pursuit of codifying and structuring knowledge is far older.

Reasoning is intimately related to KR. KR provides the formal structures: ontologies, frames, predicate logic, that encode the domain knowledge, while reasoning uses those structures to derive inferences, check consistency, answer queries, or plan actions (Nilsson, 2013). Without reasoning, KR loses much of its utility: storing a knowledge base without mechanisms to interpret or act on it is like maintaining a library with no means of retrieval or comprehension. As Russell and Norvig (2022) note, reasoning enables intelligent systems to make decisions, solve problems, and adapt to new information based on encoded knowledge. Thus, reasoning operationalises KR, turning static data into actionable intelligence. In contemporary AI, embeddings extend this tradition by representing knowledge in high-dimensional vector spaces, capturing semantic relationships between concepts in a sub-symbolic yet computationally powerful way, in a way it’s a modern, data-driven realisation of Leibniz’s vision of a universal language of thought.

References

My Response to Peer Post 2

I agree that knowledge representation (KR) is not simply a recent product of computing. In reality, KR has its foundations in philosophy. Take Leibniz, for example. As early as the seventeenth century, he was considering a universal language for reasoning, with the hope that disputes could be resolved through calculation (Brachman and Levesque, 2009). These historical examples show that the fundamental questions of KR—such as what qualifies as knowledge, how it is structured, and how it relates to reasoning—have always existed, even if they were known by different names (Truncellito, 2024; Maedche, 2002).

What shifted with the digital age was the urgency and specificity of these questions. Once we began to construct machines capable of processing information, it became necessary to reshape longstanding philosophical challenges into forms that machines could work with. As you mentioned, this is when the abstract issue of 'representation' became practical: we needed to articulate and encode our understanding for entities that do not share our cognitive history (Bouquet et al., 2003). The connection between KR and reasoning is close. It is not possible to have reasoning, in minds or machines, without some form of structured knowledge to employ (Delgrande et al., 2023).

So, the field of KRR in AI is not a break from history but an extension of a long-standing intellectual tradition, now with new technical tools and challenges. Artificial intelligence encourages us to revisit and sharpen these questions, but the basic sequence remains: first, create representations; second, enable reasoning. What we are doing now is less about inventing KR and more about adapting old ideas for a new context.

Reference list

Artefacts

2. Seminar 2 Excercises

  1. For each clause (a) - (f) below, create truth tables for each to answer the question of when each statement is false.
    • ~P
      P~P
      TF
      FT
    • P ∧ Q
      PQP ∧ Q
      TTT
      TFF
      FTF
      FFF
    • P ∨ Q
      PQP ∨ Q
      TTT
      TFT
      FTT
      FFF
    • P → Q
      PQP → Q
      TTT
      TFF
      FTT
      FFT
    • P ↔ Q
      PQP ↔ Q
      TTT
      TFF
      FTF
      FFT
    • P → (~Q)
      PQ~QP → (~Q)
      TTFF
      TFTT
      FTFT
      FFTT
  2. Consider the statement (~Q) → (~P).
    • When is it false?
      QP~Q~P(~Q) → (~P)
      TTFFT
      TFFTT
      FTTFF
      FFTTT

      It is false when ~Q is true and ~P is false (i.e., Q is false and P is true).

  3. Now consider P → Q. When is it false?
    • PQP → Q
      TTT
      TFF
      FTT
      FFT

      It is false when P is true and Q is false.

  4. Do you believe these two compound statements mean the same thing?
    • Since:
      • In the first statement, it is only false when not Q (~Q) is true (meaning that P is true), and not P (~P) is false (meaning that Q is false).
      • In the second statement, it is only false when P is true and Q is false.
      Therefore, the two compound statements mean the same thing.

  5. Construct the truth table for the statement (~Q) → (~P). Then revisit your answer to (c).
    • QP~Q~P(~Q) → (~P)
      TTFFT
      TFFTT
      FTTFF
      FFTTT
  6. Construct the truth table for P XOR Q.
    • PQP XOR Q
      TTF
      TFT
      FTT
      FFF
  7. Construct truth tables for the following statements:
    • ~ (P ∧ Q)
      PQP ∧ Q~ (P ∧ Q)
      TTTF
      TFFT
      FTFT
      FFFT
    • P ∨ (Q ∧ R)
      PQRQ ∧ RP ∨ (Q ∧ R)
      TTTTT
      TTFFT
      TFTFT
      TFFFT
      FTTTT
      FTFFF
      FFTFF
      FFFFF
    • P ∨ (Q ∨ R)
      PQRQ ∨ RP ∨ (Q ∨ R)
      TTTTT
      TTFTT
      TFTTT
      TFFFT
      FTTTT
      FTFTT
      FFTTT
      FFFFF
    • (P ∨ Q) ∨ R (Compare to the previous statement.)
      PQRP ∨ Q(P ∨ Q) ∨ R
      TTTTT
      TTFTT
      TFTTT
      TFFTT
      FTTTT
      FTFTT
      FFTFT
      FFFFF

      Similar to the previous statement; only if P, Q, and R are all false, the result is false.

    • (P → Q) ∧ (Q → P)
      PQP → QQ → P(P → Q) ∧ (Q → P)
      TTTTT
      TFFTF
      FTTFF
      FFTTT

Artefacts

3. Additional Reading Resources

To help myself solve the seminar preparation excercises, I found this short video very useful:

I also started this series of lectures on KRR. It looks detailed, and I hope to be able to go through it in the near future: