��

​

Eng. Suleiman Sead Ibrahim

Artificial Intelligence

Chapter 8�Propositional & Predicate logic

Chapter outline

• What is Logic?
• Logical Operators
• Translating between English and Logic
• Truth Tables
• Complex Truth Tables
• Tautology
• Equivalence
• Propositional Logic

​

​

Cont.…

• Deduction
• Predicate Calculus
• Quantifiers ∀ and ∃
• Properties of logical systems
• Abduction and inductive reasoning
• Modal logic

​

3

What is Logic?

• Reasoning about the validity of arguments.
• An argument is valid if its conclusions follow logically from its premises – even if the argument doesn’t actually reflect the real world:
• All lemons are blue
• Mary is a lemon
• Therefore, Mary is blue.

4

Logical Operators

• And Λ
• Or V
• Not ¬
• Implies → (if… then…)
• Iff ↔ (if and only if)

​

5

What is a Logic?�

• What is a Logic?
• _ A logic consists of three components:

​

• 1. Syntax: A language for stating
• propositions/sentences.

​

• 2. Semantics: A way of determining whether a
• given proposition/sentence is true or false.
• (Model theory)
• 3. Inference system: Rules for
• inferring/deducing theorems from other
• theorems.

6

Translating between English and Logic

• Facts and rules need to be translated into logical notation.
• For example:
• It is Raining and it is Thursday:
• R Λ T
• R means “It is Raining”, T means “it is Thursday”.

7

Translating between English and Logic

• More complex sentences need predicates. E.g.:
• It is raining in New York:
• R(N)
• Could also be written N(R), or even just R.
• It is important to select the correct level of detail for the concepts you want to reason about.

8

Truth Tables

• Tables that show truth values for all possible inputs to a logical operator.
• For example:

​

9

• A truth table shows the semantics of a logical operator.

Complex Truth Tables

• We can produce truth tables for complex logical expressions, which show the overall value of the expression for all possible combinations of variables:

10

Tautology

• The expression A v ¬A is a tautology.
• This means it is always true, regardless of the value of A.
• A is a tautology: this is written

╞ A

• A tautology is true under any interpretation.
• Example: A A
• A V ¬A
• An expression which is false under any interpretation is contradictory.
• Example: A Λ ¬ A

​

​

11

Equivalence

• Two expressions are equivalent if they always have the same logical value under any interpretation:
• A Λ B ≡ B Λ A
• Equivalences can be proven by examining truth tables.

12

Some Useful Equivalences

• A v A ≡ A
• A Λ A ≡ A
• A Λ (B Λ C) ≡ (A Λ B) Λ C
• A v (B v C) ≡ (A v B) v C
• A Λ (B v C) ≡ (A Λ B) v (A Λ C)
• A Λ (A v B) ≡ A
• A v (A Λ B) ≡ A

​

• A Λ true ≡ A A Λ false ≡ false
• A v true ≡ true A v false ≡ A

​

13

Propositional Logic

• Propositional logic is a logical system.
• It deals with propositions.
• Propositional Calculus is the language we use to reason about propositional logic.
• A sentence in propositional logic is called a well-formed formula (wff).

​

14

Propositional Logic

• The following are wff’s:
• P, Q, R…
• true, false
• (A)
• ¬A
• A Λ B
• A v B
• A → B
• A ↔ B

​

​

15

Deduction

• The process of deriving a conclusion from a set of assumptions.
• Use a set of rules, such as:

A A → B

B

If A is true, and A implies B is true, then we know B is true.

• (Modus Ponens)
• If we deduce a conclusion C from a set of assumptions, we write:
• {A₁, A₂, …, A_n} ├ C

​

​

16

Deduction - Example

17

Predicate Logic

• The first of these, predicate logic, involves using standard forms of logical symbolism which have been familiar to philosophers and mathematicians for many decades.

18

• Most simple sentences,
• for example, ``Peter is generous'' or ``Jane gives a painting to Sam,''
• can be represented in terms of logical formulae in which a predicate is applied to one or more arguments

19

Predicate Calculus

• Predicate Calculus extends the syntax of propositional calculus with predicates and quantifiers:
• P(X) – P is a predicate.
• First Order Predicate Calculus (FOPC) allows predicates to apply to objects or terms, but not functions or predicates.

​

20

Quantifiers ∀ and ∃

• ∀ - For all:
• ∀xP(x) is read “For all x’es, P (x) is true”.
• ∃ - There Exists:
• ∃x P(x) is read “there exists an x such that P(x) is true”.
• Relationship between the quantifiers:
• ∃xP(x) ≡ ¬(∀x)¬P(x)
• “If There exists an x for which P holds, then it is not true that for all x P does not hold”.

​

21

Existential Quantifier� ∃ -”there exists”

• There are times when, rather than claim that something is true about all things, we only want to claim that it is true about at least one thing.
• For example, we might want to make the claim that "some politicians are honest," but we would probably not want to claim this universally.

22

∃

• A way that mathematicians often phrase this is "there exists a politician who is honest."
• Our abbreviation for "there exists" is " ", which is called the existential quantifier because it claims the existence of something.
• If we use P for the predicate "is a politician" and H for the predicate "is honest," we can write "some politicians are honest" as:
• ∃x[Px Hx].

23

Properties of Logical Systems

• Soundness: Is every theorem valid?
• Completeness: Is every tautology a theorem?
• Decidability: Does an algorithm exist that will determine if a wff is valid?
• Monotonicity: Can a valid logical proof be made invalid by adding additional premises or assumptions?

24

Abduction and Inductive Reasoning

• Abduction:

B A → B

A

• Not logically valid, BUT can still be useful.
• In fact, it models the way humans reason all the time:
• Every non-flying bird I’ve seen before has been a penguin; hence that non-flying bird must be a penguin.
• Not valid reasoning, but likely to work in many situations.

​

25

Inductive Reasoning

• Inductive Reasoning enable us to make predictions based on what has happened in the past.
• Example: “The Sun came up yesterday and the day before, and everyday I know before that, so it will come up again tomorrow.”

​

26

Three Kinds of Reasoning

• Broadly speaking there are 3 kinds of reasoning:
• deductive – Based on the use of modus ponens and other deductive rules and reasoning.
• abductive – Based on common fallacy.
• inductive – Based on history (what has happened in the past)

27

Examples

• A deductive argument consists of n premisses and a conclusion.
• If the argument is valid, then if the premisses are true the conclusion must be true:
• Premiss 1: If it's raining then the streets are wet �Premiss 2: It's raining �----------------- �Therefore the streets are wet

28

• All horses have brains �Herman is a horse �-------------- �Therefore Herman has a brain

29

When Conclusion Does Not Follow From the Premisses

• The following are invalid:
• If it's raining then the streets are wet �The streets are wet �--------------- �Therefore it's raining
• All horses have brains �Herman has a brain �--------------- �Therefore Herman is a horse

30

Examples of Invalid Arguments

• The following two arguments are invalid:
• If it's raining then the streets are wet �The streets are wet �-------------- �Therefore it's raining
• All horses have brains �Herman has a brain �-------------- �Therefore Herman is a horse

31

More on Deductive Reasoning

• An argument can have any number of premisses:
• If p then q �If q then r �If r then s �If s then t �p �-------
• Therefore t

32

Abductive reasoning

• Abduction is "reasoning backwards". We start with some facts and reason back to a hypothesis. E.g.
• If someone has measles they have spots and a sore throat �Jimmy has spots and a sore throat �------------------------ �Therefore Jimmy has measles
• This isn't formally valid, of course. In fact it is a famous fallacy, called "confirming the consequent".

33

An Earlier Example

• If it's raining then the streets are wet �The streets are wet �-------------- �Therefore it's raining
• Nevertheless this does seem to be how doctors work.
• They use abduction to generate hypotheses, which they then test (for instance, by doing a blood test).

34

Inductive reasoning�

• Inductive reasoning is reasoning from particular cases or facts to a general conclusion:
• raven 1 is black �raven 2 is black �. �. �raven n is black �----------- �Therefore all ravens are black

35

More Examples

• horse 1 has a brain �horse 2 has a brain �. �. �horse n has a brain �------------- �Therefore all horses have brains
• These go from SOME to ALL:
• All observed (i.e. some) Xs have property P �------------------------------- �Therefore all Xs have P

36

Limitations

• This isn't formally valid.
• The conclusion does not formally follow from the observed facts.
• At one time people believed that all observed swans are white, therefore all swans are white.
• This is false, of course, because there are black swans in Western Australia!

37

Modal logic

• Modal logic is a higher order logic.
• Allows us to reason about certainties, and possible worlds.
• If a statement A is contingent then we say that A is possibly true, which is written:

◊A

• If A is non-contingent, then it is necessarily true, which is written:

•A

​

​

38

Reasoning in Modus Logic

• The following rules are examples of the axioms that can be used to reason in modus logic:
• •A ◊A
• • ¬A ¬◊A
• ◊A ¬•A
• We cannot draw truth tables to prove them; however, you can reason by your understanding of the meaning of the operators.

​

39

Class Exercise

• Draw a truth table for the following expressions:
• 1. ¬AΛ(AVB)Λ(BVC)

​

• 2. ¬AΛ(AVB)Λ(BVC)Λ¬D

​

40

​

Thank you