I sensori PNP, semplificando, possono essere considerati come interruttori collegati alla tensione di alimentazione (12V nel tuo caso, se non ricordo male). Quindi quando il sennsore non è impegnato, si comporta come un interruttore aperto, quando il sensore è impegnato si comporta (grossomodo) come un interruttore chiuso e sul pin di uscita troverai latensione di alimentazione del sensore (12V).
Probabilmente, il modo migliore per collegare il circuito è quello di utilizzare un fotoaccoppiatore (come nel circuito pubblicato sul sito di gbrl).
Facendo riferimento al circuito che ho allegato, in alto a sinistra trovi i due sensori relativi ad un asse. Essi sono collegati in parallelo all'ingresso del fotoaccoppiatore.
Quando entrambi i sensori non sono impegnati, non scorre corrente sul fotodiodo del fotoaccoppiatore, quindi il fotoaccoppiatore è "spento" e, lato arduino, troverai 5V (imposti dalla resistenza di pullup) sul pin di ingresso.
E' sufficiente che uno dei due sensori venga impegnato per avere 12V in uscita. A questo punto il fotoaccoppiatore si abilita e ti ritroverai 0V in ingresso al pin di arduino.
I due diodi messi in serie alle uscite dei sensori non sono obbligatori. Ma non fanno male. Ad esempio impedisce che i 12V in uscita ad un sensore "rientrino" nel pin del secondo sensore. Per questi sensori, solitamente, non c'è problema. Ma meglio essere dalla parte della ragione...
[ad esempio, per alcuni sensori può succedere che si illumini il led di segnalazione solitamente presente per indicare lo stato]
Oggi non riesco a disegnare una versione con il relé, ma è essenzialmente identica a quella del fotoaccoppiatore, solo più ingombrante.
P.S. per i diodi, viste le basse correnti in gioco, vanno bene anche i piccoli 1N4148. Se vuoi un diodo più grosso, c'è il 1N4007