Prop Logic Metatheorems

b/c they come up all the time:

Deduction Theorem: Δ |- (φ ⇒ ψ) if and only if
Δ∪{φ} |- ψ.

Substitution Theorem: Δ |- (φ ⇔ ψ) and Δ |- χ, then it
is the case that Δ |- χφ←ψ.

ChainingTheorem: IfΔ|-(φ⇒ψ)andΔ|-(ψ⇒χ), then Δ |- (φ ⇒ χ).

ShareThis

ShareThis

Posted using ShareThis

C++ STL

http://www.dinkumware.com/manuals/default.aspx
http://www.sgi.com/tech/stl

Pumping Lemma

What is the importance of the Pumping Lemma?

Automata & Complexity Theory

Review the following:

  • DFA
  • NFA
  • Regular Expressions
  • Inductive proofs
  • Constructive proofs
  • CFGs
  • Turing Machines
  • Undecidability
  • Computational Complexity

 

Eclipse & JDK Downloads

Eclipse 3.2

JDK 1.5

NFA vs. DFA

Theorem:  \forall NFA, \exists a DFA that recognizes the same language.

 Of course iff proofs require bi-direction, even when one direction is trivial.

Has it really been that long ago???  Just give me a state and a symbol so I can union it with the existing states…

 Don’t forget about \epsilon transitions.