– F, где F – формула;

– F₁ F₂ , F₁ F₂ , F₁ ↔ F₂ , F₁ → F₂ , где F₁ и F₂ – формулы, в которых общие переменные являются одновременно свободными или одновременно связанными;

– "x_i P(x₁ , x₂ ,…, x_{i -1} , x_{i +1} ,…, x_n ) и $x_i P(x₁ , x₂ ,…, x_{i -1} , x_{i +1} ,…, x_n ), где P(x₁ , x₂ ,…, x_n ) – формула, в которой x_i – свободная переменная

Определение истинности формул алгебры предикатов вводится с помощью интерпретации . В классическом случае интерпретация определяется следующими данными

1) предметная область;

2) всякой предметной константе ставится в соответствие некоторый предмет, определенный в области;

3) каждому пропозициональному символу ставится в соответствие некоторое значение 1 (истина) или 0 (ложь);

4) каждому предикатному символу языка ставится в соответствие некоторая характеристическая функция.

Классификация формул:

Формула называется

а) выполнимой (опровержимой) на множестве М , если существует ее истинная (ложная) интерпретация на этом множестве;

б) тождественно-истинной (тождественно-ложной) на множестве М, если любая ее интерпретации на этом на этом множестве истина (ложна);

в) выполнимой (опровержимой) , если существует предметная область, на которой она выполнима (опровержима);

г) общезначимой (противоречием) , если на любой предметной области она тождественно-истинная (тождественно-ложная).

Множеством истинности предиката P(x₁ , x₂ ,…, x_n ), заданного на множестве M₁ ЧM₂ Ч…ЧM_n , называется совокупность всех упорядоченных систем (a ₁ , a ₂ ,… a _n ), в которых a ₁ е M₁ a ₂ е M₂ ,…, a _n е M_n , таких, что данный предикат обращается в истинное высказывание Р(a ₁ , a ₂ ,… a _n ) при подстановке x₁ = a ₁ x₂ = a ₂ ,…, x_n = a _{n .} Обозначается P⁺ .

Два n-местных предиката Р(x₁ , x₂ ,…, x_n ) и Q(x₁ , x₂ ,…, x_n ), заданных на одном и том же множестве M₁ ЧM₂ Ч…ЧM_n называются равносильными , если набор предметов a ₁ е M₁ a ₂ е M₂ ,…, a _n е M_n превращает первый предикат в истинное высказывание Р(a ₁ , a ₂ ,… a _n ) тогда же, когда этот набор предметов превращает второй предикат в истинное. Переход от предиката Р(x₁ , x₂ ,…, x_n ) к равносильному ему предикату Q(x₁ , x₂ ,…, x_n ) называется равносильным преобразованием первого.

Предикат Р(x₁ , x₂ ,…, x_n ), заданный на множестве M₁ ЧM₂ Ч…ЧM_n называется следствием предиката Q(x₁ , x₂ ,…, x_n ), если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Q(x₁ , x₂ ,…, x_n ).

3. Понятие машины Тьюринга

Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы.

Машины Тьюринга – это совокупность следующих объектов

1) внешний алфавит A={a ₀ , a ₁ , …, a _n };

2) внутренний алфавит Q={q ₁ , q ₂ ,…, q _m } – множество состояний;

3) множество управляющих символов {П, Л, С}

4) бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;

5) управляющее устройство, способное находиться в одном из множества состояний

Символом пустой ячейки является буква внешнего алфавита а ₀ .

Среди состояний выделяются два – начальное q ₁ , находясь в котором машина начинает работать, и заключительное (или состояние остановки) q ₀ , попав в которое машина останавливается.

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

q _i a _j →a _p Xq _k

Запись означает следующее: если управляющее устройство находится в состоянии q _i , а в обозреваемой ячейке записана буква a _j , то (1) в ячейку вместо a _j записывается a _p , (2) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходит в состояние q _{k .}