Теория:

Логической функцией или, по-другому, предикатом на множестве \(M\) называют такую функцию от нескольких аргументов, которая при любом наборе значений этих аргументов из множества \(M\) принимает только одно из двух значений.
Обычно одно из этих значений называют Истина, другое — Ложь.
В языках программирования часто используются английские слова того же смысла True и False. Нередко предикат называют еще высказывательной формой, поскольку после подстановки вместо переменных элементов множества получается некое утверждение об этом наборе элементов, которое является либо истинным, либо ложным. Например, предикат «сумма \(x\) и \(y\) равна \(z\)» от трех аргументов \(x, y и z\), рассматриваемый на множестве натуральных чисел, принимает значение Истина при \(x = 3, y = 4, z = 7\) и значение Ложь при \(x = 2, y = 2, z = 5\). По аналогии с общим обозначением в математике функции как fx1,x2,...,xn в качестве общего обозначения предиката мы будем использовать запись Px1,x2,...,xn. Впрочем, вместо \(P\) можно использовать любую букву латинского алфавита.
В приведенном примере переменные \(x, y\) и \(z\) свободны в том смысле, что могут принимать любые значения из множества натуральных чисел. Поэтому данная логическая функция имеет три аргумента. Но не всегда число аргументов логической функции совпадает с числом фигурирующих в ее описании переменных. Рассмотрим, такой предикат: «существует \(x\), для которого сумма \(x\) и \(y\) равна \(z\)». Хотя в описании фигурируют три переменные \(x, y\) и \(z\), подставлять числа можно только вместо двух из них — \(y\) и \(z\). Так что здесь только два аргумента:  \(y\) и \(z\).  В таблице \(1\) приведены значения данной логической функции для некоторых наборов значений аргументов  \(y\) и \(z\) (этот предикат мы рассматриваем на множестве натуральных чисел).
 
Таблица 1
 
2.png
 
Обрати внимание!
Переменная \(x\) в такой функции называется связанной. При этом говорят, что переменная \(x\) связана квантором существования. Для него есть специальное обозначение: .
Происхождение этого знака простое: в английском слове «Exist» — существовать — взята первая буква и симметрично отражена относительно вертикальной оси. С помощью этого символа рассматриваемый нами предикат записывается так: x(x+y=z).
Впрочем, переменная может быть связанной и по-другому. Рассмотрим, для примера, на множестве натуральных чисел предикат «для любого \(y\) выполнено неравенство \(x+y>z\)». Здесь связанной переменной является \(y\). Примеры значений этого предиката приведены в таблице \(2\).
 
Таблица 2
 
3.png
 
Обрати внимание!
В этом случае говорят, что переменная связана квантором всеобщности, который обозначают символом .
Его происхождение аналогично: от слова «All» (все) взята первая буква и симметрично отражена относительно горизонтальной оси. С помощью этого квантора данный предикат запишется так: yx+y>z.
В предикате могут оказаться связанными не одна, а несколько переменных. Например, можно рассматривать предикат yxx+y=z — для любого \(y\) существует \(x\), такой, что выполняется равенство \(x+y=z\). Или другой предикат: xyx+y=z — существует \(x\), такой, что для любого \(y\) выполняется равенство \(x+y=z\). Каждый из них является логической функцией от одного аргумента \(z\), но это разные функции. Например, на множестве целых чисел первая из этих функций при любом значении аргумента \(z\) принимает значение Истина, в то время как вторая функция на том же множестве при любом значении аргумента \(z\) принимает значение Ложь. Как видите, порядок, в котором употреблены кванторы, имеет принципиальное значение.
Если в предикате все переменные оказались связанными, то такой предикат является высказыванием.
Например, предикат zyxx+y=z — это высказывание, утверждающее, что для любых чисел \(z\) и \(y\) существует их разность (она обозначена пере-менной \(x\)). Это высказывание истинно на множестве целых чисел, но ложно на множестве натуральных чисел. Поэтому, обсуждая свойства того или иного предиката, надо всегда указывать множество, на котором он рассматривается. Впрочем, и для числовых функций, которые вы уже много лет изучаете на уроках математики, самое первое, о чем идет речь, — это их область определения.
Чтобы вычислить значение такой «составной» функции, достаточно знать логические значения функций, из которых она составлена. Например, логическая функция Px1,x2,...,xn¯ принимает значение Истина тогда и только тогда, когда логическая функция Px1,x2,...,xn принимает значение Ложь.
При словесном описании логической функции построение отрицания к какому-либо утверждению можно выполнить добавлением словосочетания «Неверно, что...», после чего следует исходное утверждение. Например, отрицание высказывания «Я пошел в кино» можно выразить так: «Неверно, что я пошел в кино». IIpaвда, таким образом свою мысль выражают крайне редко. Обычно говорят: «Я не пошел в кино». Но заметьте, что ни одна из фраз «Не я пошел в кино» и «Я пошел не в кино» не является отрицанием исходного высказывания. А теперь рассмотрим, как строится отрицание высказывания, полученного связыванием переменной при помощи квантора. Вот пример высказывания: «Все ученики нашего класса имеют дома компьютер». Его отрицанием является высказывание «Неверно, что все ученики нашего класса имеют дома компьютер». Но каждому ясно, что это высказывание равносильно такому: «Существует ученик нашего класса, у которого дома нет компьютера». Как видите, при построении отрицания квантор всеобщности преобразуется в квантор существования. Более точно, если через \(P(x)\) обозначить предикат «ученик \(x\) имеет дома компьютер», то исходное высказывание запишется так: xP(x). А его отрицание запишется как xP(x)¯. Аналогично можно объяснить, почему при построении отрицания квантор существования заменяется квантором всеобщности. Итак, для логических функций, имеющих вид Q1x1Q2x2...QkxkPx1,x2,...,xk,y1,y2,...,yk, где Q1,Q2,...Qk — символы  или , x1,x2,...,xk — связанные переменные, y1,y2,...,yk — свободные переменные предиката \(P\), справедливо следующее правило построения отрицания. Чтобы получить отрицание логической функции, надо каждый квантор всеобщности заменить квантором существования и наоборот, а предикат \(P\) заменить его отрицанием.
Источники:
Гейн А. Г., Ливчак А. Б., Сенокосов А. И. Информатика и ИКТ.  10 класс. М. : Просвещение, 167 с.