Logic Cookbook

This page contains syntax for propositional logic and definitions of commonly used terms 🍜 📔

General Logic

• Disjunction == or == $\vee$

• Conjunction == and == $\wedge$

• Negation == not == $\mathrm{\neg }$

• logical connectives:

  • and $\wedge$
  • or $\vee$
  • if $⟹$
  • if and only if $⟺$

• Modus ponens: the rule of logic which states that if a conditional statement ($p⟹q$) is accepted, and the antecedent ($p$) holds, then the consequent ($q$) may be inferred.

Propositional Logic

Composed Of:

• atomic sentences (atoms): p, q, juice
• complex sentence: constructed from atomic sentences + logical connectives.
• proposition == sentence.
• compound proposition == complex sentence.
• logical connectives.
• literals: $p,q,\mathrm{\neg }q$ (positive and negative atoms).

Equivalence

• $(\alpha \wedge \beta )\equiv (\beta \wedge \alpha )$ commutativity
• " " same for $\vee$.
• $((\alpha \wedge \beta )\wedge \iota )\equiv (\beta \wedge \alpha \wedge \iota )$ associativity
• " " same for $\vee$
• $\mathrm{\neg }(\mathrm{\neg }\alpha )\equiv \alpha$ double-negation elimination
• $\alpha ⟹\beta \equiv \mathrm{\neg }\beta ⟹\mathrm{\neg }\alpha$ contraposition.
• $\alpha ⟹\beta \equiv \mathrm{\neg }\alpha \vee \beta$ implication elimination.
• $\alpha ⟺\beta \equiv (\alpha ⟹\beta )\wedge (\beta ⟹\alpha )$ biconditional elimination.
• $\mathrm{\neg }(\alpha \wedge \beta )\equiv \mathrm{\neg }\alpha \vee \mathrm{\neg }\beta$ de morgan's law
• $\mathrm{\neg }(\alpha \vee \beta )\equiv \mathrm{\neg }\alpha \wedge \mathrm{\neg }\beta$ de morgan's law

CNF

Conjunctive Normal Form

A sentence is in CNF iff it is of the form:

$$S_1\wedge S_2\wedge \cdots \wedge S_n$$

In which each $S_i$ is of the form:

$$(l_1\vee l_2\vee \cdots \vee l_k)$$

With each l_i a literal.

Every correct (syntax) sentence in propositional logic can be written in CNF

Predicate Logic

Composed Of:

• Constants: People, objects
  • e.g: John, Mary, 2, UT, AI
• Predicates: Describe relations.
  • e.g: Parent, Daughter, Neighbor, >, Student, Takes, Smart
• Functions: Takes input, Returns a value
  • e.g: Sqrt, Mother, Father, Teacher
• Variables:
  • e.g x, y, z
• Logical Connectives
  • $\wedge ,\vee ,\mathrm{\neg },⟹,⟺$
• Equality
  • =
• Quantifiers
  • for all $\mathrm{\forall }$
  • exists $\mathrm{\exists }$

Predicate Logic Atomic Sentence:

• $predicate(ter{m}_1,...,ter{m}_n)$ or
• $ter{m}_1=ter{m}_2$

A Term can be:

• function(term, ..., term)
• constant
• variable.

Quantifier Equivalence

• $\mathrm{\forall }x\mathrm{\neg }P\equiv \mathrm{\neg }\mathrm{\exists }xP$
• $\mathrm{\neg }\mathrm{\forall }xP\equiv \mathrm{\exists }\mathrm{\neg }P$
• $\mathrm{\forall }xP\equiv \mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }P$
• $\mathrm{\exists }xP\equiv \mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }P$