Logic

sentence: a boolean-valued formula with no free variables, generally assumed to have correct syntax
syntax: proper formatting of sentence
semantics: meaning of sentence, defines truth according to the model
truth: in standard logic, the property of being either strictly TRUE or strictly FALSE, i.e., boolean (fuzzy logic allows for degrees of truth)
model (possible world): the environment in which the sentence exists, i.e., the assignment of values to the variables in the sentence
satisfaction: if a sentence \(\alpha\) is true in model \(m\), then \(m\) satisfies \(\alpha\) and \(M(\alpha)\) represents the set of all models of \(\alpha\)
inference procedure: deriving , generally by reasoning then entailment
entailment: the idea that a sentence \(\beta\) follows logically from another sentence or sentences \(\alpha\) (the knowledge base), denoted as \(\alpha \models \beta\)
resolution: a single inference rule, resolution is sound when it only derives entailed sentences, it is complete when it can derive any entailed sentence

Propositional Logic

Logical Connectives, in descending order of precedence
Negation \(\neg\) "not"
Conjunction \(\land)\ "and"
Disjunction \(\lor\) "or"
Implication \(\Rightarrow\) "if...then"
Biconditional \(\Leftrightarrow\) or \(\equiv\) "if and only if"

Truth Table for Logical Connectives
P Q \(\neg\)P P \(\land\) Q P \(\lor\) Q P \(\Rightarrow\) Q P \(\Leftrightarrow\) Q
F F T F F T T
F T T F T T F
T F F F T F F
T T F T T T T

Logical Equivalences
Commutativity of \(\land\) \(\alpha \land \beta \equiv \beta \land \alpha\)
Commutativity of \(\lor\) \(\alpha \lor \beta \equiv \beta \lor \alpha\)
Associativity of \(\land\) \((\alpha \land \beta) \land \gamma \equiv \alpha \land (\beta \land \gamma)\)
Associativity of \(\lor\) \((\alpha \lor \beta) \lor \gamma \equiv \alpha \lor (\beta \lor \gamma)\)
Double-negation elimination \(\neg(\neg \alpha) \equiv \alpha\)
Contraposition \(\alpha \Rightarrow \beta \equiv \neg \beta \Rightarrow \neg \alpha\)
Implication elimination \(\alpha \Rightarrow \beta \equiv \neg \alpha \lor \beta\)
Implication elimination \(\alpha \Leftrightarrow \beta \equiv (\alpha \Rightarrow \beta) \land (\beta \Rightarrow \alpha)\)
deMorgan's \(\neg (\alpha \land \beta) \equiv \neg \alpha \lor \neg \beta\)
deMorgan's \(\neg (\alpha \lor \beta) \equiv \neg \alpha \land \neg \beta\)
Distributivity of \(\land\) over \(\lor\) \(\alpha \land (\beta \lor \gamma) \equiv (\alpha \land \beta) \lor (\alpha \land \gamma)\)
Distributivity of \(\lor\) over \(\land\) \(\alpha \lor (\beta \land \gamma) \equiv (\alpha \lor \beta) \land (\alpha \lor \gamma)\)

Conjunctive Normal Form (CNF)

A statement is in CNF if it is a conjunction (sequence of ANDs) of one or more disjunctions (sequences of ORs) of literals (variables or negation of variables)

CNF Conversion

  1. Replace all \(\Leftrightarrow\) using biconditional elimination
  2. Replace all \(\Rightarrow\) using implication elimination
  3. Move all negations inward using double-negation elimination and/or deMorgan's rule
  4. Apply distributivity of \(\lor\) over \(\land\)

Resolution

First-Order Logic