Propositional logic in Artificial intelligence

Propositional logic (PL) is the simplest form of logic where all the statements are made by propositions. A proposition is a declarative statement that is either true or false. It is a technique of knowledge representation in logical and mathematical form.

Propositional logic in Artificial intelligence

Example:

  1. a) It is Sunday.  
  2. b) The Sun rises from West (False proposition)  
  3. c) 3+3= 7(False proposition)  
  4. d) 5 is a prime number.   

Following are some basic facts about propositional logic:

  • Propositional logic is also called Boolean logic as it works on 0 and 1.
  • In propositional logic, we use symbolic variables to represent the logic, and we can use any symbol for a representing a proposition, such A, B, C, P, Q, R, etc.
  • Propositions can be either true or false, but it cannot be both.
  • Propositional logic consists of an object, relations or function, and logical connectives.
  • These connectives are also called logical operators.
  • The propositions and connectives are the basic elements of the propositional logic.
  • Connectives can be said as a logical operator which connects two sentences.
  • A proposition formula which is always true is called tautology, and it is also called a valid sentence.
  • A proposition formula which is always false is called Contradiction.
  • A proposition formula which has both true and false values is called
  • Statements which are questions, commands, or opinions are not propositions such as “Where is Rohini“, “How are you“, “What is your name“, are not propositions.

Syntax of propositional logic:

The syntax of propositional logic defines the allowable sentences for the knowledge representation. There are two types of Propositions:

  1. Atomic Propositions
  2. Compound propositions
  • Atomic Proposition: Atomic propositions are the simple propositions. It consists of a single proposition symbol. These are the sentences which must be either true or false.

Example:History of Java

  1. a) 2+2 is 4, it is an atomic proposition as it is a true fact.  
  2. b) “The Sun is cold” is also a proposition as it is a false fact.   
  • Compound proposition: Compound propositions are constructed by combining simpler or atomic propositions, using parenthesis and logical connectives.

Example:

  1. a) “It is raining today, and street is wet.”  
  2. b) “Ankit is a doctor, and his clinic is in Mumbai.”   

Logical Connectives:

Logical connectives are used to connect two simpler propositions or representing a sentence logically. We can create compound propositions with the help of logical connectives. There are mainly five connectives, which are given as follows:

  1. Negation: A sentence such as ¬ P is called negation of P. A literal can be either Positive literal or negative literal.
  2. Conjunction: A sentence which has ∧ connective such as, P ∧ Q is called a conjunction.
    Example: Rohan is intelligent and hardworking. It can be written as,
    P= Rohan is intelligent,
    Q= Rohan is hardworking. → P∧ Q.
  3. Disjunction: A sentence which has ∨ connective, such as P ∨ Q. is called disjunction, where P and Q are the propositions.
    Example: “Ritika is a doctor or Engineer”,
    Here P= Ritika is Doctor. Q= Ritika is Doctor, so we can write it as P ∨ Q.
  4. Implication: A sentence such as P → Q, is called an implication. Implications are also known as if-then rules. It can be represented as
                If it is raining, then the street is wet.
            Let P= It is raining, and Q= Street is wet, so it is represented as P → Q
  5. Biconditional: A sentence such as P⇔ Q is a Biconditional sentence, example If I am breathing, then I am alive
                P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q.

Following is the summarized table for Propositional Logic Connectives:

Propositional logic in Artificial intelligence

Truth Table:

In propositional logic, we need to know the truth values of propositions in all possible scenarios. We can combine all the possible combination with logical connectives, and the representation of these combinations in a tabular format is called Truth table. Following are the truth table for all logical connectives:

Propositional logic in Artificial intelligence
Propositional logic in Artificial intelligence

Truth table with three propositions:

We can build a proposition composing three propositions P, Q, and R. This truth table is made-up of 8n Tuples as we have taken three proposition symbols.

Propositional logic in Artificial intelligence

Precedence of connectives:

Just like arithmetic operators, there is a precedence order for propositional connectors or logical operators. This order should be followed while evaluating a propositional problem. Following is the list of the precedence order for operators:

PrecedenceOperators
First PrecedenceParenthesis
Second PrecedenceNegation
Third PrecedenceConjunction(AND)
Fourth PrecedenceDisjunction(OR)
Fifth PrecedenceImplication
Six PrecedenceBiconditional

Note: For better understanding use parenthesis to make sure of the correct interpretations. Such as ¬R∨ Q, It can be interpreted as (¬R) ∨ Q.

Logical equivalence:

Logical equivalence is one of the features of propositional logic. Two propositions are said to be logically equivalent if and only if the columns in the truth table are identical to each other.

Let’s take two propositions A and B, so for logical equivalence, we can write it as A⇔B. In below truth table we can see that column for ¬A∨ B and A→B, are identical hence A is Equivalent to B

Propositional logic in Artificial intelligence

Properties of Operators:

  • Commutativity:
    • P∧ Q= Q ∧ P, or
    • P ∨ Q = Q ∨ P.
  • Associativity:
    • (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
    • (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
  • Identity element:
    • P ∧ True = P,
    • P ∨ True= True.
  • Distributive:
    • P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
    • P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
  • DE Morgan’s Law:
    • ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
    • ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
  • Double-negation elimination:
    • ¬ (¬P) = P.

Limitations of Propositional logic:

  • We cannot represent relations like ALL, some, or none with propositional logic. Example:
    1. All the girls are intelligent.
    2. Some apples are sweet.
  • Propositional logic has limited expressive power.
  • In propositional logic, we cannot describe statements in terms of their properties or logical relationships.

Next TopicRules

Rules of Inference in Artificial intelligence

Inference:

In artificial intelligence, we need intelligent computers which can create new logic from old logic or by evidence, so generating the conclusions from evidence and facts is termed as Inference.

Inference rules:

Inference rules are the templates for generating valid arguments. Inference rules are applied to derive proofs in artificial intelligence, and the proof is a sequence of the conclusion that leads to the desired goal.

In inference rules, the implication among all the connectives plays an important role. Following are some terminologies related to inference rules:

  • Implication: It is one of the logical connectives which can be represented as P → Q. It is a Boolean expression.
  • Converse: The converse of implication, which means the right-hand side proposition goes to the left-hand side and vice-versa. It can be written as Q → P.
  • Contrapositive: The negation of converse is termed as contrapositive, and it can be represented as ¬ Q → ¬ P.
  • Inverse: The negation of implication is called inverse. It can be represented as ¬ P → ¬ Q.

From the above term some of the compound statements are equivalent to each other, which we can prove using truth table:https://imasdk.googleapis.com/js/core/bridge3.476.0_en.html#goog_1446371546Hello Java Program for Beginners

Rules of Inference in Artificial intelligence

Hence from the above truth table, we can prove that P → Q is equivalent to ¬ Q → ¬ P, and Q→ P is equivalent to ¬ P → ¬ Q.

Types of Inference rules:

1. Modus Ponens:

The Modus Ponens rule is one of the most important rules of inference, and it states that if P and P → Q is true, then we can infer that Q will be true. It can be represented as:

Rules of Inference in Artificial intelligence

Example:

Statement-1: “If I am sleepy then I go to bed” ==> P→ Q
Statement-2: “I am sleepy” ==> P
Conclusion: “I go to bed.” ==> Q.
Hence, we can say that, if P→ Q is true and P is true then Q will be true.

Proof by Truth table:

Rules of Inference in Artificial intelligence

2. Modus Tollens:

The Modus Tollens rule state that if P→ Q is true and ¬ Q is true, then ¬ P will also true. It can be represented as:

Rules of Inference in Artificial intelligence

Statement-1: “If I am sleepy then I go to bed” ==> P→ Q
Statement-2: “I do not go to the bed.”==> ~Q
Statement-3: Which infers that “I am not sleepy” => ~P

Proof by Truth table:

Rules of Inference in Artificial intelligence

3. Hypothetical Syllogism:

The Hypothetical Syllogism rule state that if P→R is true whenever P→Q is true, and Q→R is true. It can be represented as the following notation:

Example:

Statement-1: If you have my home key then you can unlock my home. P→Q
Statement-2: If you can unlock my home then you can take my money. Q→R
Conclusion: If you have my home key then you can take my money. P→R

Proof by truth table:

Rules of Inference in Artificial intelligence

4. Disjunctive Syllogism:

The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true, then Q will be true. It can be represented as:

Rules of Inference in Artificial intelligence

Example:

Statement-1: Today is Sunday or Monday. ==>P∨Q
Statement-2: Today is not Sunday. ==> ¬P
Conclusion: Today is Monday. ==> Q

Proof by truth-table:

Rules of Inference in Artificial intelligence

5. Addition:

The Addition rule is one the common inference rule, and it states that If P is true, then P∨Q will be true.

Rules of Inference in Artificial intelligence

Example:

Statement: I have a vanilla ice-cream. ==> P
Statement-2: I have Chocolate ice-cream.
Conclusion: I have vanilla or chocolate ice-cream. ==> (P∨Q)

Proof by Truth-Table:

Rules of Inference in Artificial intelligence

6. Simplification:

The simplification rule state that if P∧ Q is true, then Q or P will also be true. It can be represented as:

Rules of Inference in Artificial intelligence

Proof by Truth-Table:

Rules of Inference in Artificial intelligence

7. Resolution:

The Resolution rule state that if P∨Q and ¬ P∧R is true, then Q∨R will also be true. It can be represented as

Rules of Inference in Artificial intelligence

Proof by Truth-Table:

Rules of Inference in Artificial intelligence

Next TopicThe 

Inference in First-Order Logic

Inference in First-Order Logic is used to deduce new facts or sentences from existing sentences. Before understanding the FOL inference rule, let’s understand some basic terminologies used in FOL.

Substitution:

Substitution is a fundamental operation performed on terms and formulas. It occurs in all inference systems in first-order logic. The substitution is complex in the presence of quantifiers in FOL. If we write F[a/x], so it refers to substitute a constant “a” in place of variable “x“.

Note: First-order logic is capable of expressing facts about some or all objects in the universe.

Equality:History of Java

First-Order logic does not only use predicate and terms for making atomic sentences but also uses another way, which is equality in FOL. For this, we can use equality symbols which specify that the two terms refer to the same object.

Example: Brother (John) = Smith.

As in the above example, the object referred by the Brother (John) is similar to the object referred by Smith. The equality symbol can also be used with negation to represent that two terms are not the same objects.

Example: ¬(x=y) which is equivalent to x ≠y.

FOL inference rules for quantifier:

As propositional logic we also have inference rules in first-order logic, so following are some basic inference rules in FOL:

  • Universal Generalization
  • Universal Instantiation
  • Existential Instantiation
  • Existential introduction

1. Universal Generalization:

  • Universal generalization is a valid inference rule which states that if premise P(c) is true for any arbitrary element c in the universe of discourse, then we can have a conclusion as ∀ x P(x).
  • It can be represented as: Inference in First-Order Logic.
  • This rule can be used if we want to show that every element has a similar property.
  • In this rule, x must not appear as a free variable.

Example: Let’s represent, P(c): “A byte contains 8 bits“, so for ∀ x P(x) “All bytes contain 8 bits.”, it will also be true.

2. Universal Instantiation:

  • Universal instantiation is also called as universal elimination or UI is a valid inference rule. It can be applied multiple times to add new sentences.
  • The new KB is logically equivalent to the previous KB.
  • As per UI, we can infer any sentence obtained by substituting a ground term for the variable.
  • The UI rule state that we can infer any sentence P(c) by substituting a ground term c (a constant within domain x) from ∀ x P(x) for any object in the universe of discourse.
  • It can be represented as:Inference in First-Order Logic.

Example:1.

IF “Every person like ice-cream”=> ∀x P(x) so we can infer that
“John likes ice-cream” => P(c)

Example: 2.

Let’s take a famous example,

“All kings who are greedy are Evil.” So let our knowledge base contains this detail as in the form of FOL:

∀x king(x) ∧ greedy (x) → Evil (x),

So from this information, we can infer any of the following statements using Universal Instantiation:

  • King(John) ∧ Greedy (John) → Evil (John),
  • King(Richard) ∧ Greedy (Richard) → Evil (Richard),
  • King(Father(John)) ∧ Greedy (Father(John)) → Evil (Father(John)),

3. Existential Instantiation:

  • Existential instantiation is also called as Existential Elimination, which is a valid inference rule in first-order logic.
  • It can be applied only once to replace the existential sentence.
  • The new KB is not logically equivalent to old KB, but it will be satisfiable if old KB was satisfiable.
  • This rule states that one can infer P(c) from the formula given in the form of ∃x P(x) for a new constant symbol c.
  • The restriction with this rule is that c used in the rule must be a new term for which P(c ) is true.
  • It can be represented as:Inference in First-Order Logic

Example:

From the given sentence: ∃x Crown(x) ∧ OnHead(x, John),

So we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the knowledge base.

  • The above used K is a constant symbol, which is called Skolem constant.
  • The Existential instantiation is a special case of Skolemization process.

4. Existential introduction

  • An existential introduction is also known as an existential generalization, which is a valid inference rule in first-order logic.
  • This rule states that if there is some element c in the universe of discourse which has a property P, then we can infer that there exists something in the universe which has the property P.
  • It can be represented as: Inference in First-Order Logic
  • Example: Let’s say that,
    “Priyanka got good marks in English.”
    “Therefore, someone got good marks in English.”

Generalized Modus Ponens Rule:

For the inference process in FOL, we have a single inference rule which is called Generalized Modus Ponens. It is lifted version of Modus ponens.

Generalized Modus Ponens can be summarized as, ” P implies Q and P is asserted to be true, therefore Q must be True.”

According to Modus Ponens, for atomic sentences pi, pi’, q. Where there is a substitution θ such that SUBST (θ, pi’,) = SUBST(θ, pi), it can be represented as:

Inference in First-Order Logic

Example:

We will use this rule for Kings are evil, so we will find some x such that x is king, and x is greedy so we can infer that x is evil.

  1. Here let say, p1′ is king(John)        p1 is king(x)  
  2. p2′ is Greedy(y)                       p2 is Greedy(x)  
  3. θ is {x/John, y/John}                  q is evil(x)  
  4. SUBST(θ,q).                                                        

Next TopicUnification in First-order logic

Related Articles

Responses