Logic Terms

Atoms

p, q, r, representing basic propositions

Connectives

Negation, conjunction, disjunction, implication

Formulas

Represented by schematic variables phi, psi, chi etc

Assignment

Mapping of atoms to truth variables

Truth Value

Evaluation of a formula phi under specific assignment v

Validity

Formula is valid if it evaluates to 1 under all possible assignments

Semantic Entailment

Premises semantically entail the conclusion if every assignment v it holds that each premise equates to True

Objects

State, user, value, node etc

Variables

x, y, z - Assigned objects

Predicates

Atomic sentences whose truth values depend on values of variables

Quantifiers

For all, Exists

Constants

0, 1, initial state

Functions

Take objects as inputs and return objects as outputs - f(x), g(y, x), etc

Signature

Provides the vocabulary
Function and predicate symbols with specific arities

Terms

Represent elements of the domain

Built from variables and function applications

Formulas

Built from atomic formulas (predicates) using connectives and quantifiers

Bound Variables

Variables introduced by quantifiers

Free variables

Variables not bound by quantifiers

Sentences

Formulas with no free variables

Structures and Assignment

Meaning of a language is provided by a structure and assignment

Evaluation

Interpretation maps:
- Terms to elements of carrier set
- Formulas to Truth values

Properties of Sentences

Validity

Semantic Entailment
Satisfiability

Satisfiability

Formula is satisfiable if it evaluates to 1 under at least one possible assignment v

Literals

Literal is either an atom pi or its negation ¬pi

Clause

Disjunction of literals

CNF

Conjunctive Normal Form
- Conjunction of clauses