Artificial Intelligence - Propositional Logic

---

---

Propositional logic is a branch of logic that deals with propositions, which are statements that can be either true or false. It makes complex expressions by using logical connectives like AND, OR, NOT, and IMPLIES, and then applies rules to determine their truth values.

Propositional Logic in Artificial Intelligence

Artificial intelligence (AI) uses propositional logic as one of the major methods of knowledge representation using logical propositions. Propositions are statements that are either true or false but not both. More complex expressions are created by combining statements with logical operators like AND, OR, NOT, and IMPLIES. This enables an AI system to make better decisions using logical reasoning.

Artificial intelligence applies propositional logic in rule-based reasoning, automated theorem proving, and expert system decision-making. In machine learning, inference rules like Modus Ponens and Resolution allow machines to draw conclusions on the basis of the facts provided.

Propositions, in artificial intelligence, are sentences that are considered to state facts, situations, or claims about the world to enable the logical reasoning of the machines. The propositional logic expression consists of symbols (for these truths) and logical operators, often represented with parenthesis.

Example

Following are few examples of propositions (declarative statements) −

• The sun rises in the east.

• A triangle has four sides. (False)

• Water boils at 100C under normal atmospheric pressure.

• 2 + 2 = 5. (False)

• A self-driving car can operate without human intervention.

Facts about Propositional logic

Propositional logic is a formal system applied in mathematics, computer science, and artificial intelligence for reasoning about logical statements.

• It pays no attention to the context and content, it just determines whether propositions are true or false based on their structure.

• In propositional logic, operations are ordered according to precedence: Negation (¬) leads to conjunction (), then disjunction (), implication (→), and biconditional ().

• Truth tables are applied to determine whether a logical expression is valid, satisfiable, or equivalent.

• Propositional logic is limited because it can't express a relationship between the objects and quantifiers like "for all" or "there exists," where these are handled by First Order Logic.

• A proposition must be a declarative statement that holds a truth value of true or false, like the sky is blue. Statements like "Where is Krish?" is not a proposition because it is not declarative statement.

Key Components of Propositional Logic

Propositional logic involves basic building blocks such as propositions, logical connectives, and truth tables to form logical expressions which simplifies knowledge representation that help AI to reason and make decisions based on facts.

Propositions (Statements)

Propositional logic deals with two kinds of propositions, atomic and compound propositions which form the base for logical expressions.

• Atomic proposition: An atomic proposition is an basic statement which cannot be split into smaller units. It has a single proposition sign.

  For example, statement like "The car is parked in the garage".

• Compound Proposition: A compound proposition is formed by combining two or more atomic propositions using logical connectives like AND, OR, NOT, Implies.

  For example, "She likes coffee OR she likes tea".

Logical Connectives

Logical connectives, also known as logical operators, are symbols that connect or alter propositions in propositional logic. They help to form complex propositions and determine the relationships between the components. Below are the main types −

Conjunction

The combination of two propositions is only true if both of the propositions are true.

Example

The sun is shining AND it is a warm day.

• P = The sun is shining.

• Q = It is a warm day. → P Q.

The combination of above two statements become P Q. The statement, ("The sun is shining AND it is a warm day") is TRUE only if both the statements is true, if either P or Q is FALSE the entire statement is FALSE.

Disjunction (OR, )

The disjunction of two propositions is true if at least one of the propositions is true.

Example

"It is raining OR it is snowing." True if either condition is true, or both.

• P = It is raining.

• Q = It is snowing. → P Q.

Negation (NOT, ¬)

The negation of a proposition reverses its truth value, if the proposition is true, the negation is false, and vice versa.

For example, "The car is NOT parked in the driveway."(True if the car is not parked in the driveway.)

Implication (IF-THEN, →)

An implication says that if the first proposition is true, then the second has to be true as well. It is only false when the first statement is right and the second statement is wrong. It is sometimes called if-then rules.

For example, "If it rains, then the ground gets wet." (False only if it rains and the ground does not get wet.)

Biconditional (IF AND ONLY IF, )

A biconditional statement is true whenever the two propositions have the same truth value-both true or both false.

For example, "She is happy IF AND ONLY IF she passed the exam." (True only if she passed the exam and is happy, or neither of them is true.)

Table for Propositional Logic Connectives

The following table presents the fundamental connectives used in Propositional Logic, along with their symbols, meanings, and examples −

Connective Symbols	Words	Terms	Example
	AND	Conjunction	A B
	OR	Disjunction	A B
→	Implies	Implication	A → B
	If and only if	Biconditional	A B
	either A or B but not both	Exclusive Or	A B
¬ or ~	NOT	Negation	¬A or ~B

Truth Table

A truth table is a systematic representation of all possible truth values of propositions and their logical combinations in propositional logic, particularly in artificial intelligence.

It helps to determine the validity of logical statements by showing how the truth value of a compound proposition changes with respect to the truth values of its individual components.

Conjunction

The AND operation of P Q is true if both the propositional variable P and Q are true.

The truth table is as follows −

P	Q	P Q
True	True	True
True	False	False
False	True	False
False	False	False

Disjunction

The OR operation of two Propositional variable P Q is true if atleast any of the propositional variable p or q is true.

The truth table is as follows −

P	Q	P Q
True	True	True
True	False	True
False	True	True
False	False	False

Implication

An implication P → Qrepresents if P then Q. It is false if P is true and Q is false. The rest cases are true.

The truth table is as follows −

P	Q	P → Q
True	True	True
True	False	False
False	True	True
False	False	True

Bi-conditional

P Q is Bi-conditional if both P and Q have both truth value i.e, both are false or both are true.

The truth table is as follows −

P	Q	P Q
True	True	True
True	False	False
False	True	False
False	False	True

Exclusive OR

P Q is said to be exclusive OR if exactly one of the propositions is true but not both.

The truth table is as follows −

P	Q	P Q
True	True	False
True	False	True
False	True	True
False	False	False

Negation

The logical operation which reverses the truth value of a proposition. For example if P is true the negation of P is false, and vice versa.

The truth table is as follows −

P	¬P
True	False
False	True

Tautologies, Contradictions, and Contingencies

Tautologies: A tautology is a proposition that is true regardless of the truth values assigned to its component propositions. In other words, no matter what we assign to the components of this statement, the final result will always be true.

Example: P ¬P (P OR NOT P) is always true since either P is true or P is false, which means that one part of the OR conditions is always true.

Contradiction: A contradiction is a proposition that is always wrong, no matter which truth values are assigned to its components. It represents a statement that simply cannot be true.

Example: P ¬P (P AND NOT P) is always false because P cannot be simultaneously true and false.

Contingency: A contingency is a proposition that may not be necessarily true or false. The truth value of the entire statement is determined by the truth value of the propositions. That is, it may be true in some situations but false in others.

Example: P Q (P AND Q) is true if both P and Q are true, but false otherwise.

Precedence of connectives

In propositional logic, the order of operations (precedence) is as follows −

Precedence	Operators
First preference	Parenthesis
Second preference	Negation
Third preference	Conjunction(AND)
Fourth preference	Disjunction(OR)
Fifth preference	Implication
Sixth preference	Biconditional

Note: Operators with the same precedence are evaluated from left to right.

Example: Shopping Decision

Statement: "If the item is on sale AND I have a coupon, I will buy it OR I will wait for a better deal."

Propositions: A proposition is a declarative statement that might be true or false, but not both.

• P = The item is on sale.

• Q = I have a coupon.

• R = I will buy it.

• S = I will wait for a better deal.

Propositional Logic Expression: A propositional logic expression is the set of propositions joined together by logical connectives to form a meaningful statement. We write the logical expression using symbols and connectives.

(P Q) → (R S)

Step-by-Step Evaluation −

Here we follow the logical reasoning step by step.

• Conjunction: Evaluate (P Q) and see whether the two conditions that have to be satisfied, sale and coupon, are met.

• Disjunction: Consider (R S ) to determine whether the decision is to buy or wait.

• Implication: If P and Q are true, then the conclusion must be R or S, so the AI system will make the right decision.

This is how we implement the precedence rules in propositional logic, first evaluating the parentheses, then conjunction, followed by disjunction, and finally implication (IF-THEN) to reach a logical decision.

Logical equivalence

Logical equivalence in propositional logic means that two statements, or propositions, always have the same truth value regardless of the truth values assigned to the individual components.

• Symbols: "" or "" represents logical equivalence. P Q means "P is logically equivalent to Q".

• It simplifies complex logical phrases, which makes the AI system understand and interpret more effectively.

• Logical equivalence lets AI draw new conclusions from preceding knowledge. If two propositions are true and the AI knows one is true, then it can conclude that the other proposition is also true.

• In some AI systems like expert systems, uses logical equivalence to reduce the complexity of search or reasoning by replacing complex phrases with simpler, equivalent phrases.

Properties of Operators

Commutation: The order of variables in AND () and OR () does not affect the result. ( swapping positions doesnt change meaning.). Following are examples of commutation.

• P Q Q P

• P Q Q P

Association: The way propositions are grouped in AND () and OR () does not matter. ((Parentheses can be rearranged without changing meaning.). Following are examples of association.

• (P Q) R P (Q R)

• (P Q) R P (Q R)

Distribution: AND () can be distributed over OR (), and OR () can be distributed over AND (). ((Like multiplying over addition in algebra.). Following are examples of distribution.

• P (Q R) (P Q) (P R)

• P (Q R) (P Q) (P R)

De Morgan's Law: Describes how negation interacts with both conjunction and disjunction. Following are examples of De Morgan's Law.

• ¬(P Q) ¬P ¬Q

• ¬(P Q) ¬P ¬Q

Double Negation: A negation of a negation is the same proposition. Following are examples of double negation.

• ¬(¬P)P

Implication (→): Implication can be rewritten using NOT (¬) and OR (). Following are examples of Implication.

• P → Q ¬P Q

Idempotence: An operation is idempotent if repeating it a number of times yields the same result as doing it once. Following are examples of Idempotence.

• P P P

• P P P

Syntax of Propositional Logic

The syntax of propositional logic specifies rules and symbols required to construct valid logical propositions. It consists of propositions, logical connectives, and parentheses that assist in representing knowledge in a structured way.

• Propositions (Atomic Statements): These are simple statements that may be either true or false. They are usually represented by capital letters like P, Q, R, etc.

• Logical Connectives (Operators): The symbols that can be used to connect or transform propositions in a way that combines or alters their truth values such as , , ¬, →,

• Parentheses: are used to group propositions and order operations properly e.g, (P Q) → R

• Compound Propositions: It is a logical statement which is obtained by combining several atomic propositions through logical connectives like , , ¬, →, and . For example, (P Q) (¬R).

Applications of Propositional Logic in AI

Following are the applications of propositional logic −

• Automated Reasoning: Automated reasoning uses propositional logic which enables machine to deduce new knowledge from existing facts. This helps in problem-solving and decision making.

  For example, let the known facts be "The room is dark" and "The lights turn on". If AI detects darkness, it automatically turn on lights. This way it can use or infer the existing knowledge.

• Knowledge Representation: AI uses propositional logic to represent facts and relationships using propositions (statements that are either true or false) and logical connectivities such as , , ¬ and →. This logical representation helps AI to make decisions and answer queries quicker by simplifying complex representation into a structured form.

  For example, let the statements be "The customer buys a smartphone." and "The system recommends a phone case". The logical representation for this would be P → Q meaning if the customer buys a smartphone, the AI system will recommend to buy a phone case.

• Decision Making: AI uses propositional logic to make decisions based on conditions.

  For example, "If the car is low on fuel (P), and the fuel station is nearby (Q), then the car will stop for refueling" (P Q → Refuel).

• Planning and problem-solving: These are fundamental activities of AI, where machines process a situation, establish objectives, and decide a sequence of steps to achieve a desired outcome. Propositional logic helps the AI describe goals, constraints, and conditions in a structured way, so that systems can logically determine what actions to take next.

  For example, "If a meeting room is available (P) and all the participants are free (Q), the AI schedules the meeting" (P Q) → R.

• Expert System: Expert Systems uses propositional logic to represent facts and apply rule-based reasoning to draw conclusions.

  For example, "The applicant has a stable job (P) , The applicant has a good credit score (Q), The loan is approved" (P Q) → R here we use logical representation to draw conclusions.

• Game Playing: In games like chess, AI uses propositional logic to make decisions.

  For example, ""If the queen is near the king (P) and we can block it (Q), then we will move the piece" (P Q → Move Piece).

• Natural Language Processing: Propositional logic enables AI to evaluate language patterns, extract meaning, and make logical conclusions in chatbots, virtual assistants, machine translation, and automated text processing.

  For example, for the sentence "If it rains (P), take an umbrella (Q)", the AI learns that if it is raining, it should take an umbrella.

Limitations of Propositional Logic

Following are the limitations of propositional logic

• Propositional logic handles declarative statements as true or false however it can't show objects and how they relate to each other. For example, "The sun is hot" propositional logic only tells whether this statement is true or false, but it cannot tell the relationship between sun and other objects like cloud.

• It can't express ideas like "All humans are mortal" or "Some students passed the exam" because it doesn't have universal () or existential () quantifiers.

• We can't represent complex statements with variables such as "If a person is a student then they have an ID card."

• As the number of facts increases propositional logic, requires too many individual propositions, making it inefficient for large AI systems.

• It struggles with incomplete or uncertain data, which many real-world AI applications need.

• Since propositional logic has these drawbacks, we use First-Order Logic (FOL) to overcome them. FOL adds objects, relationships, and quantifiers, increasing its usefulness for AI reasoning.