9. Propositional Logic Flashcards
What is logic?
A formal way to represent knowledge and reason about the world.
What are the key components of a formal logic system?
Syntax, semantics, and inference procedures.
What are the main types of logic?
Propositional logic, first-order logic, temporal logic, probability theory, fuzzy logic, and Markov logic.
What is propositional logic?
A type of logic where sentences represent facts that are either true or false.
What are the basic logical connectives?
AND (∧), OR (∨), IMPLIES (→), BICONDITIONAL (⇔), and NOT (¬).
What is a literal?
A symbol or its negation (e.g., 𝑝 or ¬p).
What is a clause?
A disjunction (OR) of literals (e.g., p∨q).
What is a unit clause?
A clause with only one literal (e.g., p).
What is a term?
A conjunction (AND) of literals (e.g., p∧q).
What is the operator precedence in propositional logic?
¬,∧,∨,→,⇔ (in order of decreasing precedence).
What is a tautology?
A sentence that is always true regardless of interpretation (e.g., p∨ ¬p).
What is a contradiction?
A sentence that is always false regardless of interpretation (e.g., p∧ ¬p).
What are De Morgan’s Laws?
¬(p∨q)≡¬p∧¬q and ¬(p∧q) ≡¬p∨¬q
What is entailment (⊨) in propositional logic?
Sentence p is entailed by s (s ⊨ p) if p is true whenever s is true.
What is a model in propositional logic?
A world (truth assignment) in which a sentence is true.
What is conjunctive normal form (CNF)?
A conjunction (AND) of disjunctions (OR) of literals (e.g., (p∨q)∧(¬p∨r)).
What is proof by refutation?
A method of proving entailment by assuming the negation of the query and deriving a contradiction.
How does proof by refutation work?
Convert knowledge base (KB) into CNF, add ¬p (negation of the query), and derive a contradiction.
What is the difference between evaluation and satisfaction?
Evaluation determines the truth value of a sentence in a specific world, while satisfaction finds all models where a sentence is true.
What is syntax in logic?
The set of symbols and rules used to express knowledge.
What is semantics in logic?
The meaning of sentences and how they relate to the world.
What are inference procedures?
Rules for deriving new sentences (facts) from existing ones.
What is an example of a propositional sentence?
o∧h→r (hot AND humid IMPLIES it is raining).
What is the identity law in logic?
p∧T=p, p∨F=p.
What is the domination law?
p∨T=T, p∧F=F.
What is the contrapositive equivalence?
p→q≡¬q→¬p.
How can a non-CNF sentence be converted into CNF?
Using logical equivalences and transformation rules (e.g., distributing disjunctions over conjunctions).
What is a knowledge base (KB)?
A set of sentences that lists all the rules an agent knows about the world.
