Логику предикатов можно рассматривать как компоненту естественного языка, имеющую в соответствии со сложностью синтаксических правил иерархическую структуру, которую образуют предикаты первого порядка, второго и так далее. Для логики предикатов определено множество значений и на его основе определены слова как последовательности знаков. Функцией языка предикатов является задание слов двух типов:
1. Слова, задающие сущности изучаемого мира.
2. Слова, задающие атрибуты / свойства этих сущностей, а также их поведение и отношения.
Первый тип слов называется термами, второй – предикатами.
Некие сущности и переменные определяются упорядоченными последовательностями конечной длины из букв и символов, исключая зарезервированные. Константы и переменные определяют отдельные объекты рассматриваемого мира. Последовательность из n констант или переменных (1 £ n < ¥), заключенная в круглые скобки, следующие за символом функции, имя которой задано некоторой конечной последовательностью букв, называется функцией.
Например, функция f(x, y) принимает некоторые значения, которые определяются значениями констант и переменных (аргументов функции), содержащимися под знаком функции. Эти значения, так же как и аргументы, являются некоторыми сущностями рассматриваемого мира. Поэтому все они объединяются общим названием терм (константы, переменные, функции).
Атомарным предикатом (атомом) называется последовательность из n (1 £ n <¥) термов, заключенных в круглые скобки, следующие за предикатным символом, имя которого выражается конечной последовательностью букв. Предикат принимает одно из двух значений true или false в соответствии со значениями, входящих в него термов.
Предикат @ Нераспространенное простое предложение
Из атомов с помощью, выполняющих функции союзов, символов составляются логические формулы, соответствующие сложным предложениям. В логике предикатов используются два класса символов. Первый класс соответствует союзам и включает операции дизъюнкции, конъюнкции, отрицания, импликации и эквивалентности.
Символы первого класса позволяют определять новый составной предикат, используя уже определенные предикаты. Различие между символами первого класса лежит в правилах, в соответствии с которыми определяются значения истинности или ложности составного предиката в зависимости от истинности или ложности элементарных предикатов. Символы ® и », вообще говоря избыточны так, как:
но используются т.к. ® эквивалентен фразе «Если А, то В», а » - «А и В эквивалентны».
В качестве символов второго класса используются " и $. Эти символы называются кванторами общности и существования, соответственно. Переменная, которая квантифицирована, т.е. к ней применен один из кванторов 
, называется связанной. Квантор общности является обобщением, аналогом конъюнкции, а квантор существования – обобщением, аналогом дизъюнкции на произвольное, не обязательно конечное множество.
Действительно, пусть 
Тогда для любого предиката U выполняется:
Аналогом законов Де Моргана для кванторов являются:
Часто возникает ситуация, когда некоторые переменные связываются кванторами ", а все другие - $. В этом случае может возникнуть неоднозначность при интерпретации кванторов.
Пусть задан некоторый предикат U(x, y). Очевидно, что возможно восемь случаев связывания его кванторами существования и общности:
Необходимо дать интерпретацию этим восьми случаям.
Рассмотрим, например, предикат подсистема(x, y), который задает отношение x подсистема y. Пусть переменная x связана квантором общности, а y – квантором существования. В этом случае существует две интерпретации: 1. «Для всех x, существует y, для которых x подсистема», 2. «Существует y, что все x его подсистемы».
Порядок следования связанных квантором переменных определяется при чтении предиката слева направо. Дадим интерпретацию для других значимых случаев, которые можно выразить этим предикатом и кванторами:
- ("x)($y)подсистема(x, y) – все объекты являются подсистемами;
- ($x)("y)подсистема(x,y) – существует объект, который является подсистемой любого объекта;
- ("y)($x)подсистема(x, y) – для всякого объекта существует объект, являющийся его подсистемой;
- ("x)($y)подсистема(x, y) – существует объект, который является чей-то подсистемой.
Сделаем некоторые важные обобщения.
1.Чтобы найти отрицание выражения, начинающегося с кванторов, надо каждый квантор заменить на его двойственный и перенести знак отрицания за кванторы. Отсюда:
2.Одноименные кванторы можно переставлять. Разноименные кванторы можно переставлять только в одну сторону. Отсюда:
Если 
то 
Действительно, если существует объект, который является чьей-то подсистемой, то для каждого объекта будет существовать объект, являющийся его подсистемой.
Если 
то 
Действительно, если существует y, что все x его подсистемы, то для всех x существует y, для которого x подсистемы. Однако, перестановка в обратную сторону неверна. Например:
Если 
то 
необязательно.
Действительно, если для каждого объекта существует объект, являющийся его подсистемой, то это не означает, что существует объект, который является чьей-то подсистемой.
3. 
Докажем эту равносильность.
В этой выкладке мы опирались на следующее утверждение:
Определение ППФ и семантика логики предикатов
Комбинируя два типа символов, можно рекурсивно определить составную формулу логики предикатов, называемую правильно построенной формулой (ППФ) или логической формулой.
1. Атомарный предикат является ППФ.
2. Если F и G являются ППФ, то 
также ППФ.
3. Если F(x) – ППФ, то ("x)F(x) и ($x)F(x) – ППФ.
4. Все результаты, полученные применением конечного числа раз (1) – (3) являются ППФ. Ничто другое не является ППФ.
Формулы логики предикатов строятся безотносительно к понятиям задаваемой предметной области. Если решено, что этими формулами будет описываться конкретная предметная область, то должно быть установлено соответствие между понятиями предметной области и этими формулами. Это предполагает следующие действия:
1. Устанавливаются соответствия между константами логики предикатов и сущностями этой области. Константы º Имена объектов.
2. Устанавливаются соответствия между формулами и функциональными отношениями предметной области.
3. Устанавливаются соответствия между атомарными предикатами и концептуальными отношениями предметной области.
Таким образом, в язык приносится конкретное смысловое содержание, то есть семантика логики предикатов. Обычно такая интерпретация формально представляется следующим образом:
1. Задается непустое множество D, определяющее сущности рассматриваемой предметной области, и элементы из D определяются как константы или переменные.
2. Для функций (функциональные отношения), определенных на множестве аргументов от 
до D назначаются функциональные символы.
3. Каждому предикату n переменных назначается отношение, определенное на Dn, и его значение – True или False.
Множество D, рассматриваемое с позиций логики предикатов, называется областью переменных.
Значения ППФ оцениваются следующим образом:
1. Если известны значения логических формул F и G, то значения 
оцениваются по таблице истинности.
2. Если для всех xÎM F оценивается как истина, то истиной является ("x)F(x).
3. Если хотя бы для одного xÎM F оценивается как истина, то ($x)F(x) тоже истина.
Предложения
Когда все переменные предиката являются связанными, то такой предикат называется предложением. Различие между ППФ, являющимися и не являющимися предложениями, состоит в том, что предложениям можно однозначно поставить в соответствие значение True или False, в то время как во втором случае нельзя непосредственно по виду формулы вынести суждение об ее истинности или ложности. Например, предикатная формула подсистема (x, y) не является предложением. Если в нее подставлены определенные значения, например, x = процессор, y = ЭВМ, то выражение подсистема (процессор, ЭВМ) принимает значение True, а при подстановке x = человек, выражение подсистема(человек, ЭВМ) является False. То есть истинность или ложность предикатной формулы можно оценить тогда и только тогда, когда в переменные подставлены некоторые конкретные сущности (в этом случае формула называется высказыванием). Отметим, что значение предикатных формул со связанными переменными можно определить, и не производя такого рода подстановки.
Например, 
- у каждого человека имеется отец – является истиной, а 
- любой является чьим-то отцом – является ложью.
Предположим, что имеется некоторое множество логических формул S. Если существует такая интерпретация, что все эти формулы принимают значение истина, то подобная интерпретация называется моделью. Например, рассмотрим множество:
Тогда интерпретация вида (человек (Сократ) = True) и (смертен (Сократ) = True) – является моделью так как все логические формулы S есть истина. Не обязательно, что такая модель единственна.
Пусть имеется некоторая группа S логических формул. Если для всех моделей S некоторая логическая формула s есть истина, то принято говорить, что s является логическим заключением (консеквентом) в S. Факт реализации логического консеквента записывается в виде S½=s.
Правила вывода логики предикатов
Вывод представляет собой процедуру, которая из заданной группы выражений выводит, отличное от заданного выражение. Когда группа выражений, образующих посылку, является истиной, то должно гарантироваться, что выражение, выведенное из них в соответствии с правилом вывода, также является истиной.
В логике предикатов в качестве такого правила вывода используется правило, которое из двух выражений A и A®B выводит новое выражение B. Это правило называется правилом дедуктивного вывода.
Для описаний правил вывода во многих случаях используется нотация (как это указывалось выше), при которой над чертой записывается группа выражений, принимаемых за посылку, а под чертой – выражение, которое выводится:
Такой тип правила вывода носит название modus ponens.
Можно многократно использовать одно и тоже правило вывода. Например, если помимо выражений A, A®B существует выражение B®C, то можно вывести C, дважды использовав приведенное правило. Получение выражения s применением конечного числа раз правила вывода к заданной группе выражений S будем записывать в виде: 
При этом говорят, что s дедуктивно выводится из S. Очевидно, что из вышеуказанного, легко выводится еще одно правило:
Практические задания
Задание 1. Задан предикат выполнение(x, y), который задает отношение «y является результатом выполнения программы x». Дать интерпретацию утверждений:
("x)($y)выполнение(x,y);
($x)("y) выполнение(x,y);
("x)("y) выполнение(x,y);
($x)("y) выполнение(x,y);
("y)($x) выполнение(x,y);
($x)($y) выполнение(x,y).
Задан предикат реализация(x, y), который означает «программа x реализована на языке y». Записать утверждения:
А) Существует программа, реализованная на Паскале, имеющая в качестве результата 1000.
Б) Любая программа, написанная на C, дает результат.