Knowledge Flashcards
agents that reason by operating on internal representations of knowledge.
Knowledge-Based Agents
an assertion about the world in a knowledge representation language
Sentence
based on propositions, statements about the world that can be either true or false
Propositional Logic
letters that are used to represent a proposition.
Propositional Symbols
logical symbols that connect propositional symbols in order to reason in a more complex way about the world.
Logical Connectives
List all logical connectives:
Not (¬)
And (∧)
Or (∨)
Implication (→)
Biconditional (↔)
inverses the truth value of the proposition.
Not
connects two different propositions
And
is true as as long as either of its arguments is true.
Or
represents a structure of “if P then Q.”
Implication
In the case of P implies Q (P → Q), P is the ____
Antecedent
In the case of P implies Q (P → Q), Q is the ____
Consequent
an implication that goes both directions
Biconditional
an assignment of a truth value to every proposition.
Model
set of sentences known by a knowledge-based agent.
Knowledge Base (KB)
a relation that means that if all the information in α is true, then all the information in β is true.
Entailment (⊨)
the process of deriving new sentences from old ones.
Inference
Define the Model Checking algorithm
To determine if KB ⊨ α
* Enumerate all possible models.
* If in every model where KB is true, α is true as well, then KB entails α (KB ⊨ α).
the process of figuring out how to represent propositions and logic in AI
Knowledge Engineering
What makes the Model Checking algorithm inefficient?
It has to consider every possible model before giving the answer
allows the generation of new information based on existing knowledge without considering every possible model.
Inference Rules
if we know an implication and its antecedent to be true, then the consequent is true as well.
Modus Ponens
If an And proposition is true, then any one atomic proposition within it is true as well
And Elimination
A proposition that is negated twice is true
Double Negation Elimination
An implication is equivalent to an Or relation between the negated antecedent and the consequent
Implication Elimination
A biconditional proposition is equivalent to an implication and its inverse with an And connective.
Biconditional Elimination
It is possible to turn an And connective into an Or connective
De Morgan’s Law
A proposition with two elements that are grouped with And or Or connectives can be distributed, or broken down into, smaller units consisting of And and Or
Distributive Property
inference rule that states that if one of two atomic propositions in an Or proposition is false, the other has to be true
Resolution
two of the same atomic propositions where one is negated and the other is not
Complementary Literals
disjunction of literals
Clause
consists of propositions that are connected with an Or logical connective
disjunction
consists of propositions that are connected with an And logical connective
conjunction
conjunction of clauses
Conjunctive Normal Form (CNF)
Steps in Conversion of Propositions to Conjunctive Normal Form
- Eliminate biconditionals
Turn (α ↔ β) into (α → β) ∧ (β → α). - Eliminate implications
Turn (α → β) into ¬α ∨ β. - Move negation inwards until only literals are being negated (and not clauses), using De Morgan’s Laws.
Turn ¬(α ∧ β) into ¬α ∨ ¬β
Process used when a case where a clause contains the same literal twice is encountered
Factoring
process to remove a duplicate literal
Factoring
Result after resolving a literal and its negation
empty clause ()
Why is an empty clause always false?
it is impossible that both P and ¬P are true
Define the resolution algorithm
- To determine if KB ⊨ α:
- Check: is (KB ∧ ¬α) a contradiction?
- If so, then KB ⊨ α.
- Otherwise, no entailment.
- Check: is (KB ∧ ¬α) a contradiction?
If our knowledge base is true, and it contradicts ¬α, it means that ¬α is false, and, therefore, α must be true.
Proof by Contradiction
Define the proof by contradiction algorithm
To determine if KB ⊨ α:
* Convert (KB ∧ ¬α) to Conjunctive Normal Form.
* Keep checking to see if we can use resolution to produce a new clause.
* If we ever produce the empty clause (equivalent to False), congratulations! We have arrived at a contradiction, thus proving that KB ⊨ α.
* However, if contradiction is not achieved and no more clauses can be inferred, there is no entailment.
logic that allows us to express more complex ideas more succinctly than propositional logic
First Order Logic
Types of symbols used by first order logic:
Constant Symbols & Predicate Symbols
these symbols represent objects
Constant Symbols
these symbols are like relations or functions that take an argument and return a true or false value
Predicate Symbols
tool that can be used in first order logic to represent sentences without using a specific constant symbol
Universal Quantification
used to create sentences that are true for at least one x
Existential Quantification
