Propositional logic, First order logic and Higher order logic

Propositional logic

In Propositional logic symbols represent Facts (Propositions).
for example:

W - the person is a woman.

Syntactic elements

AND, OR, IMPLIES, EQUIVALENCE, NOT

First order logic (First order predicate calculus)

First-order logic represents the world in terms of objects and predicates. It uses the relations between objects and their properties. It also uses quantifiers and connectives.

syntactic examples

Objects - door, house, dog, ...
Relation - employer, sister, inside, ...
Properties - black, free, empty, hot, ...
Functions - first in, father of, friend of, ...

Syntactic elements

terms - objects
Quantifiers - UNIVERSAL (for all),  and EXISTENTIAL (there exists)
EQUALITY symbol (=)

Syntax

In propositional logic every expression is a sentence and every sentence expresses a fact. In addition to sentences First order logic also has terms that represent objects.

Higher-order logic

First order logic is so called because it works with the first order objects of the world. Higher-order logic enables us to quantify not only objects, but relations as well. What that can mean in practice is that two objects can be thought of as equal if and only if all of their properties are equivalent . We could say that two functions are equal when their arguments have the same value.

I'm not too sure of the value of HOL and it seems a bit contentious. 

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).