Propositional Logic, Clauses, and Entailment

Vocabulary flashcards covering core concepts of propositional logic, interpretations, clauses, knowledge bases, and entailment.

Syntax

The formal rules and structure defining how logical propositions are represented.

Semantics

The interpretation and evaluation of logical propositions to determine their truth values.

De Morgan's Rule

A logical transformation rule that flips standard connectives between conjunctions and disjunctions while applying negations to both sides.

Interpretation ($\pi$)

A logical function that assigns truth values (true or false) to atomic propositions, representing a specific possible world or a single row of a truth table.

Satisfaction

The condition where an interpretation ($\pi$) evaluates a proposition or every proposition within a set to true.

Clause

A proposition formatted in a specific structural shape where a body composed of a conjunction of literals implies a head composed of a disjunction of literals.

Literal

A single atomic proposition or its negation.

Head (of a Clause)

The part of a logical clause located close to the implication arrow, formed by a disjunction of literals.

Body (of a Clause)

The part of a logical clause located on the far side of the implication arrow, formed by a conjunction of literals.

Forbidden Combination

A negated conjunction representation of a clause derived using De Morgan's rule, used by search algorithms to identify assignments that fail a clause.

Knowledge Base (KB)

A collection or set of logical clauses representing known rules and facts about a world.

Model (of a Knowledge Base)

A specific interpretation (truth table row) that satisfies all clauses contained within a Knowledge Base.

Logical Consequence (Entailment)

A relationship where a proposition $g$ is entailed by a Knowledge Base ($KB \models g$) because $g$ is true in every model of $KB$.