Week 3 - Mathematical Statements - Applications
Logic Puzzle 1
An island has two inhabitants: knights, who always tell the truth, and knaves, who always lie. You go to the island and meet A and B. A says, “At least one of us is a Knave”. B is silent.
- P: A is a Knight
- Q: B is a Knight
| P | Q | ¬P | ¬Q | ¬P ∨ ¬Q | P⟺(¬P ∨ ¬Q) |
|---|---|---|---|---|---|
| T | T | F | F | F | F |
| T | F | F | T | T | T |
| F | T | T | F | T | F |
| F | F | T | T | T | F |
Answer: A is a Knight, and B is a Knave.
Logic Puzzle 2
A says, “At least one of us is a Knave”. B says, “A is a Knave”.
- P: A is a Knight
- Q: B is a Knight
| P | Q | ¬P | ¬Q | ¬P ∨ ¬Q | P⟺(¬P ∨ ¬Q) | Q⟺¬P | (P⟺(¬P ∨ ¬Q)) ∧ (Q⟺¬P) |
|---|---|---|---|---|---|---|---|
| T | T | F | F | F | F | F | F |
| T | F | F | T | T | T | T | T |
| F | T | T | F | T | F | F | F |
| F | F | T | T | T | F | T | F |
Answer: A is a Knight, and B is a Knave.
Logic Puzzle 3
A says, “B is a knight”. B says, “The two of us are of opposite types”.
- P: A is a Knight
- Q: B is a Knight
| P | Q | P⟺Q | ¬P⟺Q | P⟺(P⟺Q) | Q⟺(¬P⟺Q) | (P⟺(P⟺Q)) ∧ (Q⟺(¬P⟺Q)) |
|---|---|---|---|---|---|---|
| T | T | T | F | T | F | F |
| T | F | F | T | F | T | F |
| F | T | F | T | F | F | F |
| F | F | T | F | T | T | T |
Answer: A is a Knight, and B is a Knave.
Boolean Search
- Developed by George Boole
- Search keywords are combined by operators: AND, OR, NOT
- Use parentheses () to group keywords
- Use quotation marks to search for exact phrases
- Use an asterisk * as a wildcard to search for variations of a word
Natural Language Processing (NLP)
Semantics and Meaning Representation
- NLP focuses on understanding human language.
- Semantics: study of meaning in language.
- Meaning Representation: uses propositional and predicate logic to represent the meaning of natural language sentences.
Propositional Logic
- Represents simple statements and relationships between them.
- Example: P: “It is raining.” Q: “I will use an umbrella.” P → Q (If it is raining, I will use an umbrella.)
Predicate Logic
- Also known as First-Order Logic.
- Extension of propositional logic.
- Introduces predicates and quantification.
Example:
- Predicate: E(x): “x is even”
- Quantifiers: ∀ (universal) and ∃ (existential)
- ∀x E(x): “All numbers are even.”
- ∃x E(x): “There exists an even number.”
First-Order Logic
- An extension of propositional logic that introduces predicates and quantifiers.
- More expressive than propositional logic.
Quantifiers
- Quantifiers express the extent to which a predicate holds.
- There are two types of quantifiers in FOL:
- Universal Quantifier (∀): Indicates that a predicate holds for all elements in the domain.
- Existential Quantifier (∃): Indicates that a predicate holds for at least one element in the domain.
Examples
- ∀x L(x, y): “Everyone loves y.”
- ∃x L(x, y): “There is someone who loves y.”
- ∀x ∃y L(x, y): “Everyone loves at least one person.”
- ∃x ∀y L(x, y): “There is someone who loves everyone.”
In summary, First-Order Logic allows for more complex and detailed relationships compared to propositional logic using predicates with arguments and quantifiers.
Syntactic Analysis
- Breaking down a sentence into its components (nouns, verbs, etc.)
- Example:
Context-Free Grammar
- Uses production rules to generate valid strings in a language.
- Example: Arithmetic expressions.
Start symbol: <expression>
Terminal symbols: {+, -, *, /, (, ), number}
Production rules:
<expression> → number
<expression> → (<expression>)
<expression> → <expression> + <expression>
<expression> → <expression> - <expression>
<expression> → <expression> * <expression>
<expression> → <expression> / <expression>
Example: (2 + 3) * 5 is a valid string according to the grammar rules.
