Technical notes‎ > ‎

Predicate Logic

posted Sep 3, 2015, 10:50 PM by Le Tuan Anh   [ updated Aug 16, 2016, 11:34 PM ]
This weird stuff (predicate logic) is for HG2002 and HG4049. I know it can be really tough for you guys. Don't give up, just read the book and solve the problems after each chapter. If you have any problem solving them just email me what you have done and we'll look into it together.

To be able to solve these problems in quizzes or exams here are few hints for you (it's not an exhausted list, feel free to ask me and I'll update this):

  • Read the book:
    • Focus on 309-327 pp, scan through the text and read the examples.
    • Try your best to solve all 10.x problems. You MUST be able to solve 10.1 to 10.4 by yourself to be ready for quizzes and exams. 
  • Skill check list
    • Be able to build truth tables instead of citing them from memory
    • Be able to identify predicates, relations, constant value, variables, quantifiers, etc.
    • Be able to solve any logical sentence

Build truth table

For more information, see this page: https://en.wikipedia.org/wiki/List_of_logic_symbols

 Symbol Usage
 How to remember
  Examples
¬ Negation
 Reverse the given value
 ¬True ≡ False
¬False ≡ True
¬(¬False) ≡ True
∧ Conjunction (AND relation)
 True iff both given values are true
  
∨ Disjunction (OR relation)
 True as long as one given value is true
  
≡ If and only if
True iff both values are the same
 (True≡True) is True
 ⊕ Exclusive disjunction (XOR, Exclusive OR)
 True if two given values are different
True ⊕ False = True
True ⊕ True   = False
→ Implication (if ... then ...)
P → Q
Antecedent (P) IMPLIES consequent (Q)
Hypothesis
 True iff either we have consequent (Q≡True) or we don't have antedecent (P≡False)  

[TO BE UPDATED]

Derive logical sentences from English sentences 

WARNING: Read Saeed 2003, section 10.3: Translating English into a Logical Metalanguage. This is a MUST if you want to solve question 6 in tutorial 4.

Hints on how to translate from English sentences to predicate logic sentences

  1. Identify variables, predicates and individual constants. Just list them first, then we will form sentences later.
    1. Variables: place-holder elements, can take quantifiers (universal quantifiers every or existential quantifiers some)
    2. Individual constant: A single individual obviously
    3. Predicates: relations, mostly verbs
  2. Combine what we have listed down to form a sentence. Be careful about scoping.

Examples:

Bill sleeps.

 Bill sleeps.
 N  V
 b (invididual)
 S( )
predicate

Answer: S(b)

Dogs sleep.

 Dogs sleep.
 N  V
 x
(variable)
 S( )
predicate

This is tricky because we have to scope variable d properly here. There are two ways.

1) For every x which is a dog, that particular x sleeps.
If you go this way, you have:

[∀(x): Dog(x)] Sleep(x)

2) For every individual x, if that individual x is a dog, it sleeps.

Answer: ∀x [ Dog(x) → Sleep(x) ]

Choose the types that you feel easier to remember. And don't worry about the predicate name, what I have wrote and the short form is the same. For example [∀(x): D(x)] S(x) is perfectly fine. I prefer the verbose version because when we have to deal with long sentences, it's hard to remember which is which. It's up to you to decide.

Everybody loves HG2002.

Everybody loves HG2002
N  V N
all person
variable
 love( )
predicate
HG2002
individual

Use the same approach as above, we have:

[∀(x): Person(x)] Love(x, hg2002) or if you want to show off as a hardcore logician and confuse people, write: [∀(x): P(x)] L(x, h) and it's perfectly fine.

Every dog chases a cat.

There are two interpretations. If you want to express There is a specific cat that every dog chase, you write

Sane Human Hardcore Logicians    
[∃(x): Cat(x)] ∀y ( Dog(y) → Chase(y,x) )
  [∃(x): C(x)] ∀y ( D(y)→ Ch(y,x) )
[∃(x): Cat(x)] [∀y: Dog(y)] Chase(y,x)
 [∃(x): C(x)] [∀y: D(y)] Ch(y,x)

Now it's your turn, what if you want to express For every dog there must be a cat which that particular dog chases. Solve this and show me your answer so I know that you are understood these problems.

Scope Ambiguity

Many students find that this is very difficult to understand. This slide may help.

Comments