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

Similarities b/w \(\iff and \equiv\)

Substitution

[[Graph Theory Module 1]]