1. ## Structural Induction

Hi everyone

Im studying boolean algebra and one question is about checking functionally complete
Ive search a lot on the internet but still cant figure out how to do this.

Show { AND , <=> } is functionally incomplete

Can anyone give me some hints?

My idea is if we have a proposition which value is True

P | NOT P | P AND P | P<=> P
T F T T T T

we cant build a false using these operations, so it is not a functionally complete set

But how to do this in induction? Thank you

2. ## Re: Structural Induction

You have the right idea: all four connectives in the set are truth-preserving. See also Post's characterization of functional completeness.

Do you know the inductive definition of propositional formulas? The induction principle for formulas is the flip side of the definition. The definitions says that strings of symbols built using certain rules are well-formed formulas. The induction principle says that if a certain property is true for strings of symbols built using those rules, then the property holds for all well-formed formulas. Essentially, the first part (the definition) approximates the set of formulas from below by saying which strings are considered formulas. The second part (the induction principle) limits the set of formulas by saying that only strings built using those rules are formulas.

Formally, the induction principle for formulas built from AND, OR, => and <=> is the following. Let P be a property. If P holds of atoms and if the fact that P holds of x and y implies that P holds of x AND y, x OR y, x => y, x <=> y, then P holds of all formulas built from AND, OR, => and <=>.