Lecture 3. Formal languages

Slides

∀I

Logical methods for AI

Lecture 3

Formal languages

This work is licensed under CC BY 4.0

https://forms.gle/JiXXM9eysAZaJMja9

Formal languages

Ideas

Formal language = mathematical model of language
Logic: model of logical form

mathematical rigor

AI (KR): talk to computer

programming languages
knowledge bases (KBs) and ontologies

low level (code) vs high level (NLP)

Set theory

Notation

Set = abstract collection of elements

$x\in X$
$x\notin X$
$X=\Set{a_1,\dots,a_n}$
$X=\Set{x:x\text{ is \dots}}$

$\mathcal{L}$ is a set

Alphabets

Strings

Members of $\mathcal{L}$ are strings of symbols
Constructed from alphabet $\Sigma$

$\Sigma=\Set{0,1,2,3,4,5,6,7,8,9}$
Numerals: $0, \dots, 9,10, \dots, 19, 20, \dots$
Strings are "meaningless"

Non-logical

Propositional variables:
$p,q,r,\dots,RAINY,SUNNY,\dots$
Constants:
$a,b,c,\dots,Jim, Jane, \dots$

Non-logical

Functions:
$f,g,h,\dots,FatherOf, \dots$
Predicates:
$P,Q,R,\dots,BLUE, GREATER,\dots$

Logical

Propositional connectives:

$\neg,\sim$		not
$\land,\&$		and
$\lor$		or
$\to,\Rightarrow,\supset$		if …, then …
$\leftrightarrow,\Leftrightarrow,\equiv$		iff

Logical

More propositional connectives:

$\square,\lozenge$		necessity, possibility
$K,B$		knowledge, belief
$G,F,H,P$		past, future
$P,O$		permission, obligation
$!$		announcements
$?$		questions

Logical

Quantifiers:

$\forall$		(for) all
$\exists$		(for) some, there exists
$(\forall:P)$		(for) all $P$'s
$\exists_3$		there are 3

Auxilliaries

Commas, parentheses, ...

Grammar

Induction

Propositional language: $$\Sigma=\Set{p_1,\dots,p_n,\neg,\land,\lor,\to,\leftrightarrow,(,)}$$
Stepwise definition of $\mathcal{L}$-formulas

$p_1,\dots,p_n\in \mathcal{L}$
$A,B\in \mathcal{L}\Rightarrow \neg A,(A\land B),(A\lor B),(A\to B),(A\leftrightarrow B)\in \mathcal{L}$
Nothing else is in $\mathcal{L}$

BNF

$$A::= p_i\mid\neg A\mid (A\land A)\mid (A\lor A)\mid (A\to A)\mid (A\leftrightarrow A)$$ $$\langle prop\rangle ::= p_1 \mid \dots\mid p_n $$ $$\langle unop\rangle ::= \neg$$ $$\langle binop\rangle ::= \land\mid\lor\mid\to\mid\leftrightarrow$$ $$\langle fml\rangle::=\langle atom\rangle\mid\langle unop\rangle\langle fml\rangle\mid (\langle fml\rangle\langle binop\rangle \langle fml\rangle)$$

Examples

Formalization

The letter isn’t in the left drawer $\leadsto$ $\neg p$

The letter is in the left and in the right drawer $\leadsto$ $(p\land q)$

The letter isn't in the left drawer, but also not in the right $\leadsto$ $(\neg p\land \neg q)$

The letter is in the left or in the right drawer $\leadsto$ $(p\lor q)$

The letter is neither in the left nor in the right drawer $\leadsto$ $(\neg p\land \neg q)$

If the letter is in the left drawer, it’s not in the right $\leadsto$ $(p\to \neg q)$

The letter is in the left drawer, if it’s not in the right one $\leadsto$ $(\neg q\to p)$

The letter's only in the left drawer, if it’s not in the right $\leadsto$ $(p\to \neg q)$

The letter is in the left drawer just in case it’s not in the right one $\leadsto$ $(p\leftrightarrow \neg q)$

FOL

$\langle const\rangle ::= a \mid b\mid \dots \qquad$ $\qquad\langle var\rangle ::= x \mid y\mid \dots $

$\langle unop\rangle ::= \neg\qquad $ $\qquad\langle binop\rangle ::= \land\mid\lor\mid\to\mid\leftrightarrow$

$$\langle quant\rangle ::= \forall\mid\exists$$ $$\langle term\rangle::= \langle const\rangle\mid\langle variable\rangle\mid f^n(\langle term\rangle_1,\dots,\langle term\rangle_n)$$ $$\langle pred\rangle ::= P \mid Q\mid \dots $$ $$\langle atom\rangle::= P^n(\langle term\rangle_1,\dots\langle term\rangle_n)$$ $$\langle fml\rangle::=\langle atom\rangle\mid\langle unop\rangle\langle fml\rangle\mid (\langle fml\rangle\langle binop\rangle \langle fml\rangle)\mid \langle quant\rangle \langle var\rangle\langle fml\rangle$$