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,