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`\)
- On right of \(\to\) is \(p \therefore p\)
- Then to root of \(p\) , ie \(\to\) , on right of it is \(q\) . This becomes \(p \to q\)
- Coming back to root gives us \(\iff\)
- Going to the right of tree gives us \(\to\) first.
- Then on this tree we move left(recursive)
- we get \(\neg\) first and p which gives us \(\neg p\)
- We go to root which gives us \(\to\)
- On going we get \(\neg\) and \(q\)
- Thus we get from this tree \(\neg p \to \neg q\)
- 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
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
Similarities b/w \(\iff and \equiv\)
Substitution
[[Graph Theory Module 1]]