Высказывания. Операции дизъюнкции, конъюнкции и отрицания. Пропозициональные формулы, булевы функции и их количество. Класс монотонных функций. Полнота систем булевых функций, страница 5

Лемма доказана.

§ 14. Теорема Поста о полноте систем булевых

функций

Теорема Поста о полноте. Для полноты системы булевых функций необходимо и достаточно, чтобы среди них были функции

Доказательство. 1. Пусть дана полная система булевых функций. Бели в этой системе все функции сохраняют ноль, то из теоремы о замкнутости класса Ко следует, что и любая суперпозиция функций этой системы также сохраняет ноль, а это противоречит полноте данной системы. Следовательно, в системе имеется функция

Аналогично доказывается, что в этой системе имеются функции 

Это свойство объясняется тем, что при навешивании квантора по переменной х, она пробегает все значения из множества М и поэтому результат зависит не от конкретного значения x, а от всего множества М; такая переменная х является связанной.

Если дан предикат P(x₁, х₂,.. - , х_п), то после навешивания на него квантора существования или всеобщности по переменной x_i получается (п — 1)-местный предикат, зависящий от x₁, х₂,.. - , х_i-1 х_i+1... ,х_п и не зависящий от переменной X_i,которая после навешивания квантора становится связанной.

Если на п -местный предикат последовательно навесить по различным переменным т кванторов, то получится (n — т)-местный предикат при m <= п.

§ 2. Операции объединения и пересечения множеств

§ 15. Понятие предиката. Свободные и связанные

Переменные

Определение 1. п - местным предикатом называется функция у = Р(х₁,x₂,--- ,х_п), где x₁ € М₁ x₂ € М₂,... ,х_n€ M_n, а у € {0; 1}. Высказывание считается 0-местным предикатом.

Определение 2. Областью истинности предиката Р называется множество I = {(x₁, x₂,... ,х_n) | Р(x₁, x₂,... ,х_n)  = 1}.

Если I = {0}, то F — тождественно ложный, если I <> {0}, то Р называется выполнимым.

Пусть даны предикаты P(x₁, x₂,... ,х_n)  и Q(x₁, x₂,... ,х_n) . Конъюнкцией предикатов Р и Qназывается предикат

P /\Q, значение которого на любом наборе (x₁, x₂,... ,х_n)  определяется как конъюнкция высказываний

Р(x₁, x₂,... ,х_n)  /\  Q(x₁, x₂,... ,х_n) .

Если Р(x1, x2,... ,х_n) = Q(x1, x2,... ,х_n) для любых значений x₁€  M₂ , X₂€  М₂,... ,x_n € М_п, то предикаты Р и Qназываются равносильными.

Переменные, имеющиеся в данном выражении, разделяются на свободные и связанные. К свободным относятся те переменные, вместо которых можно подставлять их конкретные значения, а связанными являются переменные, не допускающие этого. Связанные переменные получаются из свободных после того, как с выражением производится операция, при которой эта переменная пробегает некоторое множество своих значений и поэтому результат зависит уже не от конкретного значения переменной, а от всего множества ее значений. Выражение не изменится, если заменить имя связанной переменной на новое, не меняя при этом множества ее значений, Опасно, однако, давать связанней переменной, имя другой переменной, имеющейся в этом выражении, тогда получается, как говорят, коллизия переменных и выражение может изменить свое значение.

ГЛАВА 2. МНОЖЕСТВА И ОТНОШЕНИЯ

§ 1. Понятие множества. Подмножество

Под множеством Апонимается совокупность объектов произвольной природы, они называются элементами множества А. Считается, что элементы множества попарно различны. Если х является элементом множества А, то пишут:означает, что х не принадлежит множеству А. Множество, не имеющее элементов, называется пустым и обозначается символом 0. Другая крайность: множество всех элементов, рассматриваемых в данный момент, называется универсумом и обозначается буквой U. Множество можно задавать либо перечислением его элементов, например, так: {a, b, с}, либо выделить его из другого множества с помощью некоторого свойства, например, {х € А | Р(х)} означает множество элементов х € А, удовлетворяющих свойству (предикату) Р(х).