# Module 1

Created: Sep 11, 2020 10:54 AM

• Formulas can be implemented as Binary Trees

👉 Inorder → LEFT → Root → Right

Preorder → ROOT → Left → Right

• Inorder Traversal can be used to reduce ambiguity.
• The formula for above tree is $$( p \rightarrow q ) \iff (\neg p \rightarrow \neg q)$$
• First check left of root ⇒ $$\rightarrow$$
1. On right of $$\to$$ is $$p \therefore p$$
2. Then to root of $$p$$ , ie $$\to$$ , on right of it is $$q$$ . This becomes $$p \to q$$
3. Coming back to root gives us $$\iff$$
4. Going to the right of tree gives us $$\to$$ first.
1. Then on this tree we move left(recursive)
2. we get $$\neg$$ first and p which gives us $$\neg p$$
3. We go to root which gives us $$\to$$
4. On going we get $$\neg$$ and $$q$$
5. Thus we get from this tree $$\neg p \to \neg q$$
5. This Gives us $$(p \to q) \iff (\neg p \to \neg q)$$

12/09/2020

• Polish Notation
• Congruence or $$\equiv$$
• Atoms - Indivisible Units in a statement Eg: $$p,q$$
• Grammar
• $$a \to a\ op\ b$$ ; $$op = +, -, *, /$$
• $$fml$$ is any propositional formula

$fml \iff fml \\ fml \space op\space fml \iff fml\\ \\ ... \\ ... \\ p \to q \iff \neg p \to \neg q$

Sep 16, 2020

## Interpretations

• $$p \to q \iff \neg p \to \neg q$$

### Definition

• $$A \in \digamma$$

## Boolean Operators

Inclusice OR: $$\lor$$

eXclusive OR: $$\oplus$$

Sep 17, 2020

Def 1:

Let S = $${A_1,...}$$ be a set of formulas and let $$\mathscr{P}_S =\cup_i \mathscr{P}_{A_i}$$ that is, $$\mathscr{P}_S$$ is the set of all the atoms that appear in the formulas of $$S$$. An interpretation for $$S$$ is a function $$\mathscr{I}_S:\mathscr{P}_S\mapsto\{T,F\}$$. For any $$A_i\in S,v_{\mathscr{I}_S}(A_i)$$

### Logical Equivalence

Def 1: Let $$A_1, A_2 \in \mathscr{F}$$ . If $$v_\mathscr{I}(A_1) = v_\mathscr{I}(A_2)$$ for all interpretations $$\mathscr{I}$$, then $$A_1$$ is logiclally equivalent to $$A_2$$, denoted by $$A_1 \equiv A_2$$8

### Substitution

[[Graph Theory Module 1]]