Proof: List Contains Element Example

Let's prove the following theorem:

In this example, we prove that the list [2, [4, [6,[]]]] contains 4.

At each step, we observe the first element in the list. If the first element is 4, then we have shown that the list contains 4. If not, then pop the first element off the list and start over.

For instance, the first element of the following:

[ 2, [ 4, [ 6, [ ] ] ] ]

is 2, which is not 4. After we pop 2, the list becomes:

[ 4, [ 6, [ ] ] ]

The first element is 4, so we have found our value, and the proof is complete.

Proof:

Proof Table

#	Claim	Reason
1	not (2 = 4)	not (2 = 4) (Fixed Value Statement)
2	stack [ 2, [ 4, [ 6, [ ] ] ] ] contains 4 = stack [ 4, [ 6, [ ] ] ] contains 4	if not (2 = 4), then stack [ 2, [ 4, [ 6, [ ] ] ] ] contains 4 = stack [ 4, [ 6, [ ] ] ] contains 4 (List Contains Element Recursive Property)
3	4 = 4	4 = 4 (Reflexive Property of Equality)
4	stack [ 4, [ 6, [ ] ] ] contains 4 = True	if 4 = 4, then stack [ 4, [ 6, [ ] ] ] contains 4 = True (List Contains Element Base Property)
5	stack [ 2, [ 4, [ 6, [ ] ] ] ] contains 4 = True	if stack [ 2, [ 4, [ 6, [ ] ] ] ] contains 4 = stack [ 4, [ 6, [ ] ] ] contains 4 and stack [ 4, [ 6, [ ] ] ] contains 4 = True, then stack [ 2, [ 4, [ 6, [ ] ] ] ] contains 4 = True (Transitive Property of Equality)

Comments

Please log in to add comments