Вопросы к зачету часть1 (Вопросы к зачету (ответы)), страница 2

n-местные предикаты, содержащие символы переменных x₁,…,x_n, будем обозначать в виде

(x₁,…,x_n), q(x₁,…,x_n),…

Значение α (И или Л) высказывание, получающегося при замене в предикате (x₁,…,x_n) переменных x₁,…,x_n соответственно элементами a₁,…a_n, называют значением предиката в точке (a₁,…a_n), или при x₁=a₁,…,x_n=a_n, записывая это в виде

( a₁,…a_n) ≡ α.

Таким образом, с каждым n-местным предикатом  на М сопоставляется отображение множества Мⁿ в двухэлементное множество {И,Л}, или ,как говорят, n-местная логическая функция. Предикат  зачастую отождествляют с сопоставляемой ему логической функций, в связи с чем появляется возможность дать более строгое определение предиката, как отображения Мⁿ в . Нам в данном параграфе будет удобнее стоять на менее строгой точки зрения, понимая под предикатом предложение с переменными.

Связь n-местного предиката с n-арным отношением.

Укажем на связь между понятиями n-местного предиката и n-арного отношения на множестве М. По n-арному предикату  естественным образом определяется n-арное отношение R:

( a₁,…a_n)  R. <=>( a₁,…a_n) ≡ И.

Тем самым устанавливается взаимно однозначное соответствие между множествами всех n-арных отношений и всех n-местных предикатов на множестве М.

5. Модель М() сигнатуры . Способы получения предикатов из предикатов. Квантор всеобщности. Квантор существования.

В связи с этим множество М с системой определенных на нем предикатов  называется, как и множество М с системой отношений, моделью сигнатуры  и обозначается в виде М(). Опишем способы позволяющие получать из одних предикатов на множестве М другие предикаты на том же множестве.

1. Пусть (x₁,…,x_n) - произвольный предикат на М. Заменив в нем x₁ некоторым элементом а  М, мы получим новый, (n-1)-местный предикат на М, который будем обозначать в виде

(a,x₂,…,x_n),

или каким-либо иным образом, например

q(x₁,…,x_n).

Так, если (x, y, z) есть трехместный предикат "x+y=z" на N, то

(2, у, z) есть двухместный предикат "2+у=z", который можно записать также в виде предложения: "Число z на две единицы больше числа у".

Аналогично новые предикаты можно получать из предиката (х₁ ... ..., x_n), заменяя в нем какую-либо другую переменную или даже несколько переменных элементами из М. Ясно, что заменив k переменных, мы получим (n-k)-местный предикат.

2. Заменив в предикате (x₁,…,x_n) при n ≥ 2 х₁на х₂, (или, как говорят, отождествив переменные x₁, x₂), мы получим новый предикат который обозначим через

(x₂, x₁, …,x_n)

Ясно, что этот предикат уже содержит n—1 различных переменных, а потому является (n— 1)-местным предикатом.

Например, отождествляя в предикате "x + у=z" на М переменные x, у, получим двухместный предикат "y+у=z" или "2у=z", который можно записать также предложением: "Число z в два раза больше числа у".

Аналогично можно получать из предиката (x₁,…,x_n) новые предикаты, отождествляя какие-либо другие переменные.

3. Учитывая связь понятия предиката с понятием высказывания, можно определить логические операции для предикатов. Так, соединяя два предиката (предложения) , q союзом "или", мы получим новый предикат, который обозначим через  v q и назовем дизъюнкцией предикатов , q. Если  - n-местный, а q - m-местный предикаты, а переменные, входящие в , не входят в q, то  v q будет (n + m)-местным предикатом. Его значение при конкретных значениях переменных равно дизъюнкции соответствующих значений высказываний , q.

Аналогично определяются конъюнкция и импликация предикатов, а также отрицание предиката.

4 . Кроме операций &, v, →, для предикатов на множестве можно определить еще логические операции навешивания кванторов всеобщности и существования. Пусть (x)- одноместный предикат на М, т. е. предложение, содержащее переменную x, принимающую значения из М. Построим из него новое предложение, добавив перед ним фразу "Для всех x" и обозначив новое предложение через

 x(x). (1)

Из смысла полученного предложения видно, что оно является высказыванием, которое истинно, если предикат (x) принимает значение "и" при любом значении переменной x из М, и ложно, если  принимает значение "л", хотя бы при одном значении x из М. Символ  называют квантором всеобщности и говорят, что высказывание (1) получено из предиката (x) навешиванием квантора всеобщности по переменной x.

Рассмотрим теперь n-местный предикат (x₁,…,x_n) на множестве М. Добавив к нему фразу "Для всех x₁" или "Для всякого x₁", получим новое предложение, которое обозначим в виде

 x₁ (x₁,…,x_n) (2)

Из построения этого предложения видно, что при замене в нем переменных x₁,…,x_n соответственно элементами a₁,…a_n  М получится высказывание

 x₁ (x₁, a₂,…a_n),

которое истинно в том и только том случае, когда высказывание

 (а, a₂,…,a_n) истинно при любом а  М. Таким образом, (2) является (n- 1)-местным предикатом. Говорят, что он получен из предиката  навешиванием квантора всеобщности по переменной x Понятно, что квантор  можно навешивать и по другим переменным.

Добавляя перед предикатом ( x₁,…,x_n ), как предложением с переменными x₁,…,x_n фразу "Существуют такое x что", мы получим новое предложение, которое обозначают в виде

 x₁ ( x₁,…,x_n) (3)

Подставив в него элементы a₂,…a_n вместо x₂,…,x_n, получим высказывание

 x₁ ( x₁, a₂,…,a_n)

которое истинно в том и только том случае, когда высказывание (a,a₂,…,a_n) истинно хотя бы при одном а из И, Следовательно, предложение (3) есть (n- 1)-местный предикат на М.

Символ  называется квантором существования, а о предложении (3) говорят, что оно получено из предиката (x₁,…,x_n) навешиванием квантора существования по переменной x₁. Квантор существования можно навешивать и по другим переменным.

Приведем примеры. Пусть (x, у) есть предикат на множестве N: "x делит у". Тогда предложение  у (x,у) зависит только от переменной x. При x=1 оно принимает значение "и", поскольку 1 делит любое натуральное число. При любом другом значении x из N оно принимает значение "л".

Предложение  x (x,у) зависит только от переменной у и принимает значение "л" при любом значении у, поскольку в N не существует чисел, делящихся на все натуральные числа.

Нетрудно видеть, что предложения

x r(x,у) у (x,у)

зависящие соответственно от у и x, принимают значения "и" при любых значениях указанных переменных.

С помощью рассмотренных выше способов можно из некоторой исходной системы предикатов на множестве М получать все новые и новые предикаты, записываемые в виде различных выражений через исходные предикаты, символы переменных, элементов из М, логических связок &, v, →, ┐, ,  и служебных символов — скобок и запятых. Такие выражения называются формулами. Ниже будет дано точное (индуктивное) определение формулы

6. Термы. Формула на алгебраической системе М() (на предикатах). Свободные и связные переменные в формулах предикатов.

Формулы будут определяться как строчки некоторых символов, или, как говорят, слова в некотором алфавите.

Алфавитом называют произвольное множество попарно различных символов, допускающих такую запись, по которой однозначно восстанавливаются сами символы. Обычно символ отождествляется с любой своей записью, в связи, с чем символы, алфавита называют также его буквами. В математике в качестве символов зачастую используются изображения букв латинского и других алфавитов, изображения цифр, изображения букв с индексами, символы операций +, * , - ,  и др.

Если А={a₁,a₂,…a_n} —алфавит, то любая конечная последовательность

a_i1,a_i2,…,a_im

его букв называется, словом в алфавите А. При этом число m называется длиной слова. Длина слова P обозначается в виде L(P). Для удобства в рассуждениях вводится еще символ  для обозначения пустого слова, т. е. слова, не содержащего ни одной буквы. По определению L() = 0.

Так как слово есть конечная последовательность букв, то можно все буквы в слове естественным образом занумеровать и говорить о 1-й, 2-й и т. д. буквах слова. Обычно слова записывают в строчки, а буквы в них нумеруют слева направо. Два слова называются равными, или графически равными, если они имеют одинаковую длину и соответствующие их буквы равны. Равенство слов будем обозначать знаком =. Множество всех слов и всех слов длины m в алфавите А обозначим соответственно через W(А) и W_m(A).

На множестве W(А) можно ввести операцию умножения (или приписывания) слов, взяв в качестве произведения слов P, Q слово РQ, полученное приписыванием слова Q справа к слову Р.

Говорят, что слово Р является подсловом слова Q, если существуют такие слова L, R (возможно пустые), что

Q=LPR.

В этом случае говорят также, что слово Р входит, или имеет вхождение, в слово Q. Может оказаться, что указанная выше пара слов L, R находится по словам Р и Q неоднозначно. Выпишем все такие различные пары слов (L_i, R_i) и упорядочим их по возрастанию длины слова L_i. Получим:

Q=L₁PR₁= L₂PR₂=…= L_sPR_s

В этом случае говорят, что имеется s вхождений слова Р в слово Q и все эти вхождения упорядочивают по возрастанию длины слова L_i. В соответствии с этим говорят о 1-м, 2-м и т. д. вхождениях олова Р в Q. Например, слово "арарат" содержит два вхождения слова "ара". В следующей записи 1-е и 2-е вхождения слово "ара" подчеркнуты соответственно одной и двумя черточками снизу:

" арарат".

Перейдем теперь к определению формул алгебры предикатов на алгебраической системе М(). Сигнатуру  представим в виде объединения  = ₁₂, где ₁, — множестве символов операций, а ₂— непустое множество символов предикатов на М. В частности, множество s₁, может быть и пустым. Обозначим через s₀ подмножество из s₁, обозначений всех нуль-арных операций, т. е. выделенных элементов множества М. Оно может быть любым подмножеством из М. При определении формулы в качестве обозначений будут использоваться различные буквы (возможно, с индексами): а, b, с для элементов из s₀; ƒ, , ψ для элементов из s₁; , q для элементов из s₂. Кроме того, будут использоваться: множество X символов предметных переменных со значениями из М, обозначаемых буквами x, y, z, u, v (возможно, с индексами); множество О логических операций &, v, →, ┐, ,  и служебных символов-скобок и запятых. Таким образом, алфавитом при построении формул будет служить множество

=   X  O

В конкретных примерах для операций и предикатов будут использоваться также общепринятые обозначения: +, , *, =,  и т.д. Определим предварительно понятие терма на системе М ( ).

Определение

1. Каждый символ переменного из Х или константы из s₀ есть терм.

7. Формула над классом (множеством) логических функций. Примеры эквивалентных преобразований формул, в частности, правила поглощения, склеивания, вычеркивания.

Задание логических функций

1.1.1. Таблицы. Функция f(x₁, …, x_n) называется логической или (булевой), если она принимает значения 0 и 1 и ее аргументы также принимают значения 0 и 1. Логическая функция от n аргументов может быть задана таблицей, в которой перечислены всевозможные наборы из 0 и 1 длины n и для каждого из них указано значение функции. Наборы обычно перечисляются в порядке возрастания чисел, двоичными записями которых они являются. В таблице 1.1 приведен пример логической функции от 3 аргументов.

Таблица 1.1

Таблицы для функций от n аргументов x₁, ..., х_n имеют 2 ⁿ строк (по числу двоичных наборов длины n). Различные таблицы отличаются лишь последним столбцом и, поскольку количество различных двоичных столбцов длины 2ⁿ составляет 2² , число функций от n аргументов x₁, ..., х_n равно 2² . Заметим, что в это число включены и функции, зависящие от некоторых из аргументов x₁, ..., х_n фиктивно*), т. е. функции, фактически зависящие от меньшого числа аргументов. Величина 2² чрезвычайно быстро растет (так, 2² =4, 2 =16, 2 = 256. 2 >6•10⁴, 2 >4•10⁹).

Приведем примеры функций, которые будут широко использоваться в дальнейшем. При n=1 имеются 4 логические функции (см. табл. 1.2).

Таблица 1.2.

Ими являются константы 0 и 1, значения которых не зависят от значений аргумента, тождественная функция x, повторяющая значение аргумента, и функция х, принимающая значение, противоположное значению аргумента. Функция x носит название отрицания или инверсии. Заметим, что константы 0 и 1 фактически не зависят от аргумента, и их иногда будем считать «функциями от нуля аргументов