# 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. < Logical connectives Venn diagram >

## Logical Reasoning¶ < The illustration of declarative problem solving. The logical approach provides the foundation for it.  >

## 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¶ < 2x2 sudoku example  >

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. 

• 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)$$ 

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 

$\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