Logic

Logical Connectives

NOR and NAND gates are sufficient to express any Boolean function, i.e., they are functionally complete. If you want to verify that a set of operators is functionally complete, show that can be expressed with either NOR or NAND. Read Stackoverflow for more detail.

alternate text

< Logical connectives Venn diagram >


Logical Reasoning

alternate text

< The illustration of declarative problem solving. The logical approach provides the foundation for it. [1] >


Language of Propositional Logic

Syntax for Propositional Formulas

  • negation \(\neg\) (“not”)
  • conjunction \(\land\) (“and”)
  • disjunction \(\lor\) (“or”)
  • implication \(\rightarrow\) (“if … then”)
  • equivalence \(\leftrightarrow\) (“if and only if” or “bi-implication”)

Examples

  • rainy \(\rightarrow\) wet: If it rains, then it’s wet.
  • \(\neg\) dry \(\lor\) \(\neg\) swim: One can’t be dry while he is swimming and vice versa.

Definition – formula

  1. Every atomic formula is a formula.
  2. \(\text{If $\alpha$ and $\beta$ are formulas, then also $(\neg\alpha), (\alpha\lor\beta), (\alpha\land\beta), (\alpha\rightarrow\beta), (\alpha\leftrightarrow\beta) $ are}\) formulas.

Definition – subformula

The subformulas of a formula are defined recursively as follows.

  1. The only subformula of an atomic proposition a is a it self.
  2. The subformulas of \(\not \alpha\) are \(\not \alpha\) and all the subformulas of \(\alpha\).
  3. If \(*\) is any of the connectives \(\lor,\land,\rightarrow,\leftrightarrow,\) the subformulas of \((\alpha * \beta)\) are \((\alpha * \beta)\) and all the subformulas of \(\alpha\) and \(\beta\).

Examples

The subformulas of the formula \(swim \rightarrow \neg dry\) are the formula itself, \(swim\), \(\neg dry\) and \(dry\).

Example – Formulas from natural language

Consider the following statement in natural language:

If the file is too big, then it is compressed or removed.

For the sake formalization, we can identify the following atomic statements/formulas:

  1. b: The file is too big.
  2. c: The file is compressed.
  3. r: The file is removed.

By substituting these statements into the original statement, we may derive a preliminary formalization that mixes natural language with the formal one:

\[\text{If b, then c or r}\]

Finally the formula is obtained by identifying the connectives and by incorporating them into the expression:

\[b \rightarrow c \lor r\]

Example for Terminologies

alternate text

< 2x2 sudoku example [1] >

We can study the above sudoku and reason that <2,1> can only contain 2. This can be expressed in a formal logical calculus as a disjunction

\[ \begin{align}\begin{aligned}\begin{split}{val}(1,1,2)\lor {val}(1,2,2)\lor {val}(2,1,2)\lor {val}(2,2,2) \\\end{split}\\\text{(i.e., 2 has to be in either in one of the 2x2 grid.)}\end{aligned}\end{align} \]

The clue 2 at coordinates ⟨1,3⟩ and constraints for the first column (where x=1) contribute the following formulas

\[ \begin{align}\begin{aligned}\begin{split}\begin{array}{ccc} {val}(1,3,2), & \neg{val}(1,2,2)\lor\neg{val}(1,3,2), & \neg{val}(1,1,2)\lor\neg{val}(1,3,2). \end{array} \\\end{split}\\ \text{(i.e., 2 cannot be placed simultaneously in the cells ⟨1,2⟩ and ⟨1,3⟩.)}\end{aligned}\end{align} \]

Truth tables

\[\begin{split}\begin{array}{|c|c|c|} \hline \alpha & \beta & (\alpha\land\beta) \\ \hline \hline F & F & F \\ \hline F & T & F \\ \hline T & F & F \\ \hline T & T & T \\ \hline \end{array}\end{split}\]
\[\begin{split}\begin{array}{|c|c|c|} \hline \alpha & \beta & (\alpha\lor\beta) \\ \hline \hline F & F & F \\ \hline F & T & T \\ \hline T & F & T \\ \hline T & T & T \\ \hline \end{array}\end{split}\]
\[\begin{split}\begin{array}{|c|c|c|} \hline \alpha & \beta & (\alpha\rightarrow\beta) \\ \hline \hline F & F & T \\ \hline F & T & T \\ \hline T & F & F \\ \hline T & T & T \\ \hline \end{array}\end{split}\]
\[\begin{split}\begin{array}{|c|c|c|} \hline \alpha & \beta & (\alpha\leftrightarrow\beta) \\ \hline \hline F & F & T \\ \hline F & T & F \\ \hline T & F & F \\ \hline T & T & T \\ \hline \end{array}\end{split}\]
\[\begin{split}\begin{array}{|c|c|c|} \hline \alpha & \beta & (\alpha\oplus\beta) \\ \hline \hline F & F & F \\ \hline F & T & T \\ \hline T & F & T \\ \hline T & T & F \\ \hline \end{array}\end{split}\]

Models, Satisfiability and Unsatisfiability

Satisfaction is a relationship between specific sentences and specific truth assignments. [2]

  • A sentence is valid if and only if it is satisfied by every truth assignment.
    • e.g. \((p \lor \neg p)\)
    • satisfiable
  • A sentence is unsatisfiable if and only if it is not satisfied by any truth assignment.
    • e.g. \((p \land \neg p)\)
    • falsifiable
  • A sentence is contingent if and only if there is some truth assignment that satisfies it and some truth assignment that falsifies it.
    • e.g. \((p \land q)\)
    • satisfiable AND falsifiable.

Definition – model

Let \(\alpha\) be a formula and \(\Sigma\) a set of formulas. A truth assignment \(v\) is called

  1. a model of \(\alpha\), if \(v \vDash \alpha\), and
  2. a model of \(\Sigma\), if \(v \vDash \Sigma\), i.e., \(v \vDash \beta\) for every formula \(\beta \in \Sigma\)

Logical entailment

We say that a sentence \(\phi\) logically entails a sentence \(\psi\) (written \(\phi\)\(\psi\)) if and only if every truth assignment that satisfies \(\phi\) also satisfies \(\psi\). For example, the sentence \(p\) logically entails the sentence \((p \lor q)\). Since a disjunction is true whenever one of its disjuncts is true, then \((p \lor q)\) must be true whenever \(p\) is true.

Logical consistency

A sentence \(\phi\) is consistent with a sentence \(\psi\) if and only if there is a truth assignment that satisfies both \(\phi\) and \(\psi\). For example, the sentence \((p \lor q)\) is consistent with the sentence \((p \land q)\). However it is NOT consistent with \((\neg p \land \neg q)\) [3]

While consistency and entailment are very similar they don’t entail each other.

Transformation Rules

\[\begin{split}\begin{align} \text{1. } & \alpha\leftrightarrow\beta \Longrightarrow (\alpha\rightarrow \beta)\land(\beta\rightarrow \alpha) \Longrightarrow (\neg\alpha\lor\beta)\land(\neg\beta\lor\alpha) \\ \text{2. } & \alpha\rightarrow \beta \Longrightarrow \neg\alpha\lor\beta \\ \text{3. } & \neg(\alpha\lor\beta) \Longrightarrow \neg\alpha\land\neg\beta \\ \text{4. } & \neg(\alpha\land \beta) \Longrightarrow \neg\alpha\lor\neg\beta \\ \text{5. } & \neg\neg\alpha \Longrightarrow \alpha \\ \text{6. } & \alpha\lor(\beta\land \gamma) \Longrightarrow (\alpha\lor\beta)\land(\alpha\lor\gamma) \\ \text{7. } & (\alpha\land \beta)\lor\gamma \Longrightarrow (\alpha\lor\gamma)\land(\beta\lor\gamma) \\ \text{8. } & \alpha\land(\beta\lor\gamma) \Longrightarrow (\alpha\land\beta)\lor(\alpha\land\gamma) \\ \text{9. } & (\alpha\lor\beta)\land\gamma \Longrightarrow (\alpha\land\gamma)\lor(\beta\land\gamma) \\ \end{align}\end{split}\]

To transform a propositional formula into a CNF or DNF, follow the below steps:

  1. Remove equivalences \((\leftrightarrow)\)
  2. Remove implications \((\rightarrow)\)
  3. Push negations inside until negations \((\neg)\) occur as parts of negative literals only.
  4. Organize conjunctions outside disjunctions (CNF) or disjunctions outside conjunctions (DNF).

Conjunctive Normal Form(CNF)

A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more literals. Examples of conjunctive normal forms include [4]

\[\begin{split}A \\ (A \lor B) \land (\neg A \lor C) \\ A \lor B \\ A \land (B \lor C) \\\end{split}\]

Example

Transform the formula \(\neg(p\land q)\leftrightarrow(r\land s)\) into CNF.

\[\begin{split}\begin{gather} \text{1. Replace the equivalance using, $P \leftrightarrow Q \Longleftrightarrow (P \lor \neg Q) \land (\neg P \lor Q)$.} \\ \big[ \neg(p\land q) \lor \neg (r\land s) \big] \land \big[ p\land q) \lor (r\land s) \big] \\ \text{2. Applythe distributed law} \\ \big[ \neg(p\land q) \lor \neg (r\land s) \big] \land \big[ (p\lor r) \land (p\lor s) \land (q\lor r) \land (q \lor s) \big] \\ \text{3. Apply De Morgan's law} \\ \big( \neg p \lor \neg q \lor \neg r\lor \neg s \big) \land \big( (p\lor r) \land (p\lor s) \land (q\lor r) \land (q \lor s) \big) \\ \end{gather}\end{split}\]

Disjunctive normal form (DNF)

A formula \(\alpha\) is in disjunctive normal form (DNF) if and only if has the form \({\beta_1}{\lor}\cdots{\lor}{\beta_n}\) where \(n\geq 0\) and each disjunt \(\beta_i\) is a cube. Example:

\[(\neg {fire}\land\neg {alarm})\lor( {fire}\land {alarm})\]


Reference

[1](1, 2) https://mycourses.aalto.fi/course/view.php?id=16956
[2]http://intrologic.stanford.edu/sections/section_03_01.html
[3]http://intrologic.stanford.edu/sections/section_03_05.html
[4]http://mathworld.wolfram.com/ConjunctiveNormalForm.html