Can any memory-less computer operation be represented in propositional logic?
Well you can just make a giant truth table for $f$ and then convert that to a Boolean formula. Boolean formulas are propositional formulas, are they not?