Варианты заданий

1. Доказать полноту систем операций сведение системы к ₀.

а) ₁= { , ^}; b) ₂= { , ^};

c) ₃ =   ; d) ₄ =  ;

e) ₅ = {, }; f) ₆ = {, }.

2. Представить формулу в виде полинома Жегалкина:

a) x₁  x₃; b) x₁ x₂  ;

c) ; d) .

3. Доказать полноту систем операций задания 1, используя необходимое и достаточное условие полноты.

4. Доказать неполноту систем операций:

а) ₁ = {, , }; б) ₂ = {};

в) ₃ = {,,,}.

5. Покажите, что система функций F = { f₁, f₂}, f₁(x₁, x₂) = = x₁~x₂ , f₂(x₁, x₂) = x₁  x₂ не является полной. Укажите все способы сделать эту систему полной добавлением одной не более чем двухместной функции.

4. Формулы алгебры предикатов

Напомним, что строго предикат можно определить как отображение n-ной степени предметного множества M, называемой местностью или арностью предиката в двухэлементное множество B = {1, 0}

.

Например, предикат простого числа задаётся правиломи может быть определён на произвольном числовом множестве. Всюду в дальнейшем для краткости будем определять предикаты записью.

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

Например, для предиката делимости D(x,y): “x нацело делится на y”, определённого на множестве натуральных чисел , можно построить формулы алгебры предикатов, являющиеся высказываниями, так как обе предметные переменные в них связаны.

1. Высказывание читается, как “для любогоx существует y, такое, что x делится на y”, и является истинным высказыванием, так как любое натуральное x делится на себя и на 1, т.е. y = x или y =1;

2. Высказывание читается, как “существуетy, на который делится любой x ”, и является истинным высказыванием, так как на значение y =1 делится любое натуральное x;

3. Высказывание читается, как “существуетx, который делится на любое y”, и является ложным высказыванием, так как нет ни одного натурального числа, которое делится на любое натуральное число;

4. Высказывание читается, как “для любогоy существует такой x, что x делится на y”, и является истинным высказыванием, так как для любого натурального y можно указать множество значений  , которые делятся на y.

Ряд важнейших понятий алгебры предикатов основывается на понятии модели.

Моделью  называется любое множество M с заданными на нем предикатами :

 = < M ; >.

Любое утверждение в некоторой предметной области можно записать в виде формулы алгебры предикатов сигнатуры , выбрав соответствующее предметное множество и набор предикатов, определённых на нём, называемый сигнатурой модели. В качестве примера рассмотрим теоремы и определения из евклидовой геометрии. Предметным множеством M здесь является множество точек, прямых и плоскостей трёхмерного пространства.

Задание. Записать в виде формулы на модели  = < M ; > , где

, ,

, ,

,

следующие утверждения:

1. Через каждые 2 точки можно провести прямую.

2. Если 2 точки различны, то проходящая через них прямая единственна.

3. Через каждые 3 точки, не лежащие на одной прямой, можно провести единственную плоскость.

4. Определение параллельных прямых на плоскости.

Решение.

1. Данное утверждение можно сформулировать с использованием предикатов модели следующим образом: для произвольных двух точек существует прямая, на которой лежат эти точки. Запишем его в виде формулы

2. В дополнении к предыдущему утверждению здесь говорится, что если произвольные точки не совпадают, то построенная по ним прямая является единственной, т.е. любая другая прямая, проходящая через эти точки, совпадает с ней. Таким образом, получим формулу

3. Данное утверждение гласит, что если 3 точки не лежат на одной прямой, то существует плоскость, на которой лежат эти точки, причём любая другая такая плоскость совпадает с ней. Введём для краткости записи итоговой формулы вспомогательные формульные предикаты:

: “x, y, z не лежат на одной прямой“;

: “ x, y, z лежат на плоскости v“.

Запишем с их помощью утверждение задания

.

4. Напомним, что параллельными называются те прямые, которые лежат на одной плоскости и не имеют общих точек, либо совпадают, т.е.

.

Заметим, что в предыдущих формулах все переменные – связанные, т.е. формулы являются высказываниями, принимающими значение 1. Данная формула является формульным предикатом от переменных , который может принимать различные значения для конкретных значений переменных.

Математическая логика описывает общие методы умозаключений, применяемые к утверждениям, записанным в виде формул. Поэтому от символов предикатов фиксированной сигнатуры в формулах алгебры предикатов сигнатуры  перейдём к предикатным переменным. Например, формула

U= (*)

является формулой алгебры предикатов, в которой - произвольные предикаты арности 3 и 2 соответственно. Для определения же свойств таких формул рассматриваются формулы сигнатуры, полученные замещением предикатных переменных на предикаты некоторой заданной сигнатуры .

Задание. Является ли модель арифметики натуральных чисел  = <  ; E⁽²⁾, S⁽³⁾, P⁽³⁾ >, где

допустимой для формулы (*)? Определить является ли формула (*) выполнимой на модели, просто выполнимой, тождественно истинной на модели, общезначимой?

Решение. Модель арифметики натуральных чисел является допустимой для формулы U, так как можно построить сигнатурное отображение множества предикатных переменных формулыв сигнатуру модели = < E⁽²⁾, S⁽³⁾, P⁽³⁾ >. Вариантов такого отображения два:

1. , ;

2. , .

Проверим, является ли формула выполнимой на допустимой модели  . Рассмотрим формулу

₁U=,

полученную подстановкой в формулу U предикатов сигнатурного отображения ₁. Легко проверить, что ₁U= 1 для любых значений , так как

, является истинным утверждением.

Это означает, что формула U выполнима на модели  и, более того, она истинна на этой модели. Выполнимость формулы следует из её выполнимости на модели  .

Для проверки тождественной истинности формулы на модели нужно проверить истинность U при любом сигнатурном отображении. Аналогично предыдущему случаю получим, что формула ₂U=истинна на модели , а следовательно U тождественно истинна на этой модели.

Данная формула не является общезначимой, чтобы доказать это достаточно привести пример допустимой модели, на которой формула не будет тождественно истинной.

Для доказательства общезначимости формулы нужно показать её тождественную истинность на любой допустимой модели, т. е. для любого предметного множества и любых предикатов соответствующей арности.

Задание. Доказать общезначимость формулы

.

Решение. Так как единственная переменная в обеих частях эквиваленции связана, то обе они являются высказываниями. Поэтому для доказательства общезначимости формулы, покажем, что истинностные значения левой и правой части совпадают для любых одноместных предикатов , определённых на произвольном множестве M.

Пусть , тогда по определению операции утверждения общностиM, откуда следует, что M, это означает, что и , а, следовательно, истинна и их конъюнкция . Те же рассуждения справедливы и в обратную сторону.

Задание. Построить ПН-форму для формулы

Решение. Воспользовавшись общезначимостью из предыдущего задания, получим



.

В первом дизъюнкте переменные x и y – связанные, а z – свободная, а во втором – наоборот. Переобозначив связанные переменные 

,

получим, что первый дизъюнкт не зависит от w, а второй – от u и v. Поэтому, вынеся соответствующие им кванторы в начало формулы 

получим её ПН-форму.