Comparing propositional and first-order logic in AI
The purpose of this paper is to explain the concept of Knowledge Representation and its importance in Artificial Intelligence.

Table of contents

  • Introduction 
  • Part 1 
  • Different types of knowledge representation 
  • Part 2 
  • Propositional logic 
  • First-order logic 
  • Comparison between propositional logic and first-order logic 
  • Usages for AI
  • Conclusion
  • References


Introduction


The purpose of this paper is to explain the concept of Knowledge Representation and its importance in Artificial Intelligence (Part 1) and to provide a comparative study between Propositional Representation and First Order Logic (Part 2). 


AI knowledge cycle


A knowledge-based agent or an AI agent takes perception of the world or data given as input and returns an action as output. The planning and execution of the action depends on analysis from the Knowledge Representation and Reasoning.


Part 1


Knowledge representation and reasoning(KKR) is essential for artificial intelligence because it is concerned with how information is represented to enable AI to solve problems and to take action. KKR has to do with the representation of information in AI systems. KKR affects how an AI agent behaves, solves problems and completes useful tasks, such as system diagnostics and communicating with humans in natural language.


In order to give an AI agent “intelligence” and enable it to make decisions and take actions autonomously , we need to represent information i.e. knowledge, in such a way that an agent can understand and interpret. This is so the agent can make decisions based on that knowledge and the information it is given. The knowledge is the basis for the decisions an agent makes. 

  

The more we can effectively represent our knowledge, the more “intelligent”(McCarthy, 2007) our AI agent will be. A collection of knowledge an AI agent has is called a knowledge-base.


A knowledge base(KB) is a set of sentences written in formal language which tell an AI agent what it needs to know in order to perform a useful task. A knowledge base uses declarative language in the form of propositional logical and first-order logic. They also use algorithms to manipulate data structures.

For example; imagine somebody is given the geolocation coordinates of a building. They would need to understand how to apply that information in the real world i.e. how to navigate a place to get to that building, turn left - right etc. The same applies for AI agents, an AI agent needs to take data and use an algorithm in order to do a useful task, like navigate to a building. This knowledge would be a part of the AI agents knowledge base. It is necessary to automate knowledge processing in our AI systems. An AI agent  needs to take information as input and use knowledge to make the best action possible.


For the knowledge base, an AI engineer can use a variety of ways to represent knowledge for example: databases, programming languages(mostly Python, SQL and R), graphs, images, sounds, video, tables of information, logic representation, syntax, and basic human language.


Different types of knowledge representation


Presented below are different types of Knowledge Representation, including examples: 


Declarative knowledge is what we know about something which normally includes concepts, facts that are true in the world and facts about objects. events are also considered to be declarative knowledge. Declarative knowledge uses simple language. Declarative knowledge is important for things we need to represent.


Examples:

The number of unread emails we have, the amount of dog food in a bowl  and even the amount of data we have in a database, are all examples of declarative knowledge.

An online business may record in the database if a transaction is completed, what item was purchased, the customer ID and the date of the transaction. All of these would be considered to be declarative knowledge. An AI agent might use these pieces of declarative knowledge to predict when customers are most likely to buy certain products.


Meta-knowledge is knowledge on things we know. It is similar to declarative knowledge. Search Engine Optimisation(SEO) uses meta-tags to describe pages to search engines like Google. Meta-tags are meta-knowledge. Using hashtags in social media posts is a more commonly used example of meta knowledge. Epistemology is the philosophy of knowledge and is also an example of meta-knowledge.

To put it simply, meta-knowledge is the “knowledge of knowledge”(Spacey, 2016). 


Procedural knowledge is related to the type of knowledge used to perform tasks. It can include rules, strategies, procedures and agendas. It is relative to the type task we are doing and can be directly applied to any similar task. Procedural knowledge may also be known as imperative knowledge. Procedural knowledge may come in the form of discrete and completed rules(Pew, 1988).


Example:

If an engineer decides to create a messaging app, first the program stores the title and body of a message. Then it verifies if the email exists. If the email is verified as valid, the program then sends the body of the message. The script used to send the message is the procedural knowledge in this case.


Heuristic knowledge are “rules of thumb” from experts in particular subjects and are based on previous experiences. These are widely known to work sometimes but are not always guaranteed to be successful. Heuristic knowledge may be considered to be less scientific and more subjective than other types of knowledge.


Examples:

It is often said that the best way to make friends is to be yourself, although this may not work in every situation like turning up to a job interview in pyjamas.

While AI agents can be developed in a number of different computer languages like R, Lisp and JavaScript; Python is the unofficial standard in the software industry for AI and data-science. While an engineer may create an AI agent in any computer language,  heuristic knowledge would suggest that Python is the choice.  


Structural knowledge connects the declarative and procedural knowledge together and thus becomes the basic knowledge of problem solving. It represents knowledge using logical arguments, like predicate logic and SQL. It helps us understand the relationships between concepts, objects and groups.


Example:

If we know that customers over the age of eight-five are getting vaccinated, the structural knowledge can be represented like so: customer.age >= 85.


Part 2


In this section I provide a comparative study between Propositional Logic and First Order Logic. Note: The question asks us to compare Propositional Representation and First-order Logic, but for the purposes of this paper and in line with the module I present a comparison using Propositional Logic not Propositional Representation.  


Propositional logic


Propositional logic(PL) is a statement made by propositions. It is a simple form of logic. Propositions are declarative statements which are either true or false. PL is a technique often used in logical and mathematical form. When we study PL, we usually start with informal natural language arguments, but they can also be expressed mathematically.


Atomic propositions are single stand-alone statements. Compound propositions are made of two or more atomic propositions. Questions are not propositions. Propositions that are not true are called false propositions.

Examples:


Don is the administrator.

5 + 3 = 8.

2 + 2 = 7 and “I am writing in Italian” are false propositions.


Propositional logic is based on formal logic, deductive reason and Boolean logic. We use symbolic variables to represent the logic. Often true and false can be symbolised by 1 and 0. Propositional logic also consists of an object, relations or function, and logical connectives.


Inference is when we create new logical statements from previous logical statements. For artificial intelligence, we use machines to create logical conclusions from facts and evidence. In natural human language, inference is also known as deductive reasoning. 

Example:

It is cold and wet outside. I am outside. I am wet.

Propositional logic can use symbols to represent statements and their relationship between them. Some of these symbols are called conjunction, disjunction, implication and assertion.

Examples of propositional logic symbols:  




First-order logic


First-order logic(FOL), Predicate logic or First-order predicate logic is an extension to propositional logic. First-order logic expresses information about objects and expresses relationships between those objects in a more functional way in comparison to propositional logic. First-order logic is more concise than propositional logic.


In First-order logic, the statements are divided into two parts: the subject and the predicate. The predicate is not a proposition. It is neither true nor false. Predicates use variables and objects like people, colours, numbers, letters or ideas. They can also represent relationships and functions


Examples of First-order logic statements:

The pepper(subject) is beside(predicate) the salt.

Mary(subject) is the mother(predicate)  of John.

X + Y(subject)  = 42(predicate) 


Both syntax and semantics are important to first-order logic. Symbols are the basic syntax of FOL and can be written in shorthand. Syntax is the structure of the logical statements. Semantics gives meaning to the statements.


Examples;

Predicate(Subject)

Mother(Mary, John)

Beside(Pepper, Salt.)


First-order logic uses quantifiers to distinguish if the proposition applies to all instances of the predicates or just one instance. The Universal quantifier uses an inverted A symbol, ∀. This indicates for all instances of the predicates, everything or everyone. The existential quantifier resembles a backwards E, ∃. This means that the proposition is true for at least one or more instances of something, but not every instance.


Examples:

Every man has a heart = ∀x man(x) → have (x, heart).

Some men are mean = ∃x: man(x) ∧ mean(x).


Comparison between propositional logic and first-order logic


Propositional logic uses symbols to represent entire statements, whereas first-order logic symbolises the subject and predicate separately.


X  =  the coffee is hot.

Hot(Coffee).


Propositional logic does not use any quantifiers. Unlike first-order logic, it is not able to imply one or all instances of the proposition.


Propositional logic is an analytical statement which is either true or false. First-order logic can contain both objects, variables and numbers.


Propositional logic can be expressed more clearly using natural language, whereas First-order logic uses syntax and semantics.



Usages for AI


Propositional logic is essential for artificial intelligence. Boolean logic is essential for creating if statements, for and while loops in computer programming. On a fundamental level, all computer programming is essentially a series of ones and zeros, however it would be far too complicated to write all of the code in binary. Not all problems that an AI agent needs to solve can be reduced to a proposition that is true or false.


First-order logic is effectively a more advanced form of propositional logic. Its biggest strength lies in using symbols as the main syntax of the propositions. This is a far more efficient way of writing logical statements. In addition, first-order logic allows us to use variables, numbers, objects and functions. This gives us the ability to store vital information in a database and write complicated code and functions.


In some situations, the simplicity of propositional logic is perfect, in other situations it would require a more detailed answer using variables. This would require the heuristic knowledge of the human engineer to determine if either propositional logic or first-order logic is better.


Conclusion


For AI, it is essential to represent knowledge in a way that an agent can interpret so that it can solve problems and make decisions based on that knowledge. We can use tools and structures like  propositional logic and first-order logic to represent knowledge for an AI to interpret. 


Using the variables from first-order logic, allows us to create a more accurate knowledge representation for an AI agent.




References


McCarthy, J. (2007). What is artificial intelligence? Stanford University.


Spacey, J (2016). What is meta-knowledge? [online] Simplicable. Available

at: https://simplicable.com/new/meta-knowledge [Accessed Day Feb, 2021].


Pew, R. (1988). Handbook of Human-Computer Interaction. Elsevier.


Diorey, P., Helaryn D . (2013). An Expert System for Prescribing Herbal Remedies To Common Health Concerns using Android Phones. Mindanao State University - Iligan Institute of Technology.