Programar em Prolog é bem diferente de programar em uma linguagem procedimental. Em Prolog se fornecem fatos e regras para uma base de dados; então se executam consultas ou (queries) a essa base de dados. A unidade básica do Prolog é o predicado, que é postulado verdadeiro. Um predicado consiste de uma cabeça e um número de argumentos. Por exemplo:

gato(tom).

Isso informa à base de dados o fato que 'tom' é um 'gato'. Deve-se notar que esta interpretação é absolutamente flexível, não existe nenhuma obrigatoriedade de interpretar gato(tom). como significando que tom é um gato. Nada impede, por exemplo, que a base de dados tenha a seguinte estrutura:

 tom(gato).
 jerry(rato).
 spike(cachorro).
 butch(gato).

Voltando ao exemplo gato(tom)., formalmente, 'gato' é a cabeça e 'tom' é o único argumento do predicado. Alguns exemplos de consultas que podem ser feitas ao interpretador Prolog baseado nesse fato. Para saber se tom é um gato, escrevemos:

?- gato(tom).  
     yes.

Para saber que coisas (conhecidas) são gatos:

?- gato(X).  
     X = tom;
     yes.

É importante notar que, sendo a base de dados apenas formada pelo predicado gato(tom)., temos os seguintes resultados:

?- rato(tom).
     No.
?- gato(jerry).
     No.
?- rato(jerry).
     No.
?- gato(butch).
     No.

Note-se que No significa não sei. A negação em Prolog é um assunto delicado, e o seu tratamento requer um cuidado especial.

Predicados são normalmente definidos para expressar algum fato sobre o mundo que o programa deve conhecer. Na maioria dos casos, o uso de predicados requer uma certa convenção. Por exemplo, qual das duas versões abaixo significaria que José é o pai de Ana?

pai(ana,jose).
pai(jose,ana).

Em ambos os casos 'pai' é a cabeça e 'ana' e 'jose' são argumentos. Entretanto, no primeiro caso Ana vem primeiro na lista de argumentos, e no segundo, quem vem primeiro é José (a ordem nos argumentos é importante). O primeiro caso é um exemplo de definição na ordem Verbo Sujeito Objeto, e o segundo, na ordem Verbo Objeto Sujeito. Como Prolog não entende português, ambas as versões estão corretas de acordo com seu escopo; no entanto é uma boa prática de programação escolher uma única convenção para ser usada no mesmo programa, para evitar escrever algo como

pai(jose,ana).
pai(maria,joao).

De novo, nada impede que os predicados sejam escritos como:

ana(mae,maria).
joao(pai,jose).

Alguns predicados são pre-definidos na própria linguagem, permitindo que os programas Prolog desempenhem atividades rotineiras (como entrada/saída, uso de gráficos e outros tipos de comunicação com o sistema operacional). Por exemplo, o predicado write pode ser usado para saída na tela. Então,

 write('Olá'). 

vai exibir a palavra 'Olá' na tela.