# Quantified Statement: Prime

Quantified Statement: Prime is the important topic of the Subject Theory Of Computation.

# For any integers a and b, if a and b are odd, then ab is odd.

**Proof: Quantified Statement: Prime**

An integer n is odd if there exists an integer x so that n=2x+1.

Now let a and b be any odd integers. Then according to this definition, there is an integer x so that a=2x+1, and there is an integer y so that b=2y+1.

We wish to show that there is an integer z so that ab=2z+1. Let us, therefore, calculate ab:

=(2x+1)(2y+1)

=4xy+2x+2y+1

=2(2xy+x+y)+1

##### Since we have shown that is a z, namely, 2xy+x+y, so that ab=2z+1, the proof is complete.

##### Example: Quantified Statement: Prime

X=45 & y= 11

xy= 2(2xy+x+y)+1

= 2(2(45)(11)+45+11)+1

= 2(1046)+1

xy=2093

Hence proved.

# Give quantified statement saying that p is prime.

Let us consider that statement “P is prime” involving the free variable p over the universe N of natural number.

We take our definition of a prime number, a number greater than 1 whose only divisor are itself and 1.

The first statement is now to express the fact that one number is a divisor of another.

The statement “k is a divisor of p” means that p is a multiple of k or there is an integer m with p = m * k

Next saying that the only divisors of p are p and 1 is the same as saying that every divisor of p is either p or 1.

Adapting the statement that “for every k, if k is a divisor of p, then k is either p or 1”.

Considering all these together we get that “p is prime”.{ ( p > 1 ) ∀ k (∃m ( p = m * k ) )→ (k = 1) (k = p ) }

# What is Proof?

A proof of a statement is essentially just a convincing argument that the statement is true.

There are several methods for establishing a proof, some of them are :

- Direct Proof
- By Contradiction
- Contrapositive
- By Mathematical Induction

**Related Terms**

Theory of Computation, Basic Terms of TOC, TOC Functions

## Leave a Reply