57. Функции k-значной логики и их задание с помощью таблицы истинности и с помощью таблицы Кэли. Примеры k-значных логик.

Алгебра, образованная k-элементным множеством вместе со всеми операциями на нем, называется алгеброй k-значной логики, а n-арные операции на k-элементном множестве называются k-значными логическими функциями n переменных; множество всех k-значных логических функций обозначается Pk.

Способы задания логических функций

• Таблица истинности: в левой части — перечислены все 2n наборов значений переменных, в правой части — значения функции на этих наборах.

• Наборы, на которых функция f = 1, часто называют единичными наборами функции f, а множество единичных наборов — единичным множеством f. Соответственно наборы, на которых f = 0, называют нулевыми наборами f , а множество нулевых наборов — нулевым множеством f.

• Число |P2(n)| различных функций n переменных равно числу различных двоичных векторов длины 2n, т.е.

58. Предикат: n-местный (n=0, n>0), тождественно истинный, тождественно ложный, выполнимый. Область истинности предиката. Связь между n-местными предикатами и n-местными отношениями.

Предикат (от позднелат. рraedicatum — сказанное) — высказывательная функция, определенная на некотором множестве M, т.е. такая n-местная функция P, которая каждому упорядоченному набору элементов множества M сопоставляет некоторое высказывание, обозначаемое ; P называется n-местным предикатом на M. Под 0-местным предикатом понимается произвольное высказывание.

В математической логике высказывание обычно отождествляется с его истинностным значением 1 («истина») или 0 («ложь»). При этом понятие предиката получает следующее, наиболее общее определение: n-местным предикатом на множестве M называется произвольная n-местная функция, определенная на M и принимающая значения 0 и 1. Если на наборе значений аргументов предикат P принимает значение 1, то есть , то говорят, что этот набор значений аргументов удовлетворяет предикату P, а предикат P выполняется для набора . Предикат называется тождественно истинным, если он выполняется для любого набора значений своих аргументов, и тождественно ложным, если никакой набор не удовлетворяет этому предикату. Предикат называется выполнимым, если он выполняется хотя бы для одного набора значений аргументов.

Множество тех наборов значений аргументов, которые удовлетворяют данному предикату, называется областью истинности этого предиката. Если P есть n-местный предикат на множестве M, то его область истинности является n-местным отношением на M. И наоборот, каждому n-местному отношению на множестве M однозначно соответствует n-местный предикат на M. Поэтому изучение предикатов и отношений тесно связано между собой.