First Order Logic

This stuff is great fun.
There are a number of differeing styles of notation and my logic, how I still think, started in electronics and then early Computer Science lessons so I might be a bit wrong in places. It's something I enjoy and I hope to apply it more.

A Predicate

A predicate is a statement that is TRUE or FALSE
An example could be:
A dog is a mammal.
A dog is a fish. Both of the above are predicates but the second one is false.

We can write those in psudo computer speak as:
IsaMammal(dog)
IsaFish(dog)
Both of the above would return a Boolean.

Symbols we use all the time

→ - Implies

¬ - Not

These two are quantifiers, for obvious reasons 
∃ - There exists. This means that there is one or more, there is at least one value that makes the predicate true.
∀- For all

Inference

This stuff is basic, but interesting if you've not seen it before.
(1) ¬(a and b) = ¬a or ¬b
(2) ¬(a or b) = ¬a and ¬b

(1) Not (a and b), is the same as (not a) or (not b)
(2) Not(a or b) is the same as saying,  (not a) and (not b)

In electronics we used to use "+" for OR, "." for AND and a bar across the letter for NOT.
_   _
a + b  Not a OR Not b  

_____
a + b Not (a or b)

We used to say "break the bar change the sign" to remember the following:
 ___   _ _
 a.b = a+b
 ___   _ _

 a+b = a.b

Not sure if that's of any use but it's true none the less.  DeMorgan's Theorem.

We can use them thus:

If someone says that something is ¬(a and b) 

then to prove them wrong, we have to prove  ¬a or it is ¬b

Two more

(1) This is nearly, or pretty obvious I think: 

If we know that a implies b,
a→b and we know a, then we also know b

(2) This one probably isn't so obvious:

If we know that a implies b,
a→b and we know it is ¬b, then we also know ¬a

Notice that the two rules have a reversal. The first one is Modus Ponens and the second is Modus Tollens. We don't really need to know that but it's posh.

Using modus Ponens:

If we know the creature is a Dog, then we know it is a mammal.
Dog(creature) → Mammal(Creature) 

Using Modus Tollens,

If we know the creature is not a dog, then we know it is not a mammal
¬Mammal(Creature), therefore ¬Dog(Creature)

There are two more, similar

a → b = ¬b → a
¬(a→b) = a and ¬b

Using first order logic to define a Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

We can write two predicates:

Divisible(a, b) - the integer a is divisible by b.

Greater(a, b) - the integer a is greater than b.

So we can create a predicate for Prime numbers.

Prime(n) returns true if n is a prime, otherwise false if it is not.

Prime(n) = ∀i Greater(i,1) → ¬Divisible(n, i)
Prime(n) = ∀i Greater(i,1) and ¬Divisible(n, i)

The above says, n is a prime number

if for all numbers, i, i is Greater than 1, and n is not divisible by i

Prolog

Just for interest. here's the Prolog code to check if a number is a prime number

Example:  isprime(3).

code:

divisible(X,Y):-
      N is Y*Y, 

      N =< X, 

      X mod Y =:= 0.

divisible(X,Y):- 

      Y < X, 

      Y1 is Y+1, 

      divisible(X,Y1).

isprime(X):- 

     Y is 2, 

     X > 1, 

     \+divisible(X,Y).