Предикатни формули
Предикатните формули (предикатни логически формули) се въвеждат, както следва:
всяка елементарна формула е предикатна формула:
ако A и B са предикатни формули, то те са предикатни формули. Ако A е предикатна формула и е обектна променлива, тогава те са предикатни формули;
Един израз е предикатна формула, ако е елементарна формула или е конструиран от елементарни формули чрез последователно прилагане на правила а) и б).
Предикатни формули, които не са елементарни формули, се наричат съставни предикатни формули.
За обозначаване на формулите на логиката на предикатите ще използваме главни букви от латинската азбука, отпечатани с удебелен шрифт: A, B, C, P, Q и др.
Във формулите формулата A се нарича съответно обхват на кванторите.
Обикновено се приемат конвенции за пропускане на скоби. Освен това се счита, че кванторите се свързват по-силно от други операции. Така че формулата може да бъде написана така:
ОПРЕДЕЛЕНИЕ. Предикатна формула се нарича валидна, ако след замяна на елементарните формули в нея с всякакви предикати се получи идентично верен предикат.
ОПРЕДЕЛЕНИЕ. Предикатните формули се наричат еквивалентни, ако след замяна на съдържащите се в тях елементарни формули с предикати се получават еквивалентни предикати. Ще запишем еквивалентността на формули A и B, както следва: .
Лесно е да се докаже, че една предикатна формула е валидна тогава и само ако A и B са еквивалентни предикатни формули.
Цяла поредица от еквивалентности на логиката на предикатите могат да бъдат получени от еквивалентностите на пропозиционалната логика. Например, еквивалентите на пропозиционалната логика
отговарят на еквивалентността на предикатната логика
По същия начин, идентичниистинските формули на пропозиционалната логика служат като източник за извеждане на общовалидни формули на предикатната логика. Например тавтологията съответства на общовалидна предикатна логическа формула. Наистина, замествайки произволни предикати във всяка конкретна формула А вместо предикатните символи, включени в нея, получаваме определен предикат.В този случай формулата се превръща в предикат, който приема стойност И за всякакви допустими стойности на променливите (по силата на закона за изключената среда в пропозиционалната логика).
По същия начин могат да се обосноват и останалите общовалидни формули и еквивалентности на логиката на предикатите, пренесени от логиката на съжденията.
В допълнение към универсално валидните формули и еквивалентности на предикатната логика, получени по този начин, има специфични универсално валидни формули и еквивалентности, свързани с използването на квантори. Ще разгледаме някои от тях.