Свободные и связанные переменные

Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:

Свободные переменные.

• Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,

• свободные переменные формулы F являются свободными переменными формулы ¬F,

• переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),

• все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.

Замкнутая формула.

• Формула без свободных переменных называется замкнутой формулой, или предложением.

Связанная переменная.

• Переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.

Связанное переименование, свободное переименование

Операции над кванторами

Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:

Билет №8

1.Декартово произведение множеств.

Если каждому элементу из множества A сопоставлен в соответствие определенный элемент из множества B, то возникает множество, составленное из пар элементов множеств A и B, - декартово произведение множеств.

Записывают декартово произведение множеств так:

A × B = {(a; b) | a ∈ A, b ∈ B}.

Это значит, что если например дано множество A = {1,2,3} и множество B = {15,25}, то их декартово произведение будет состоять из пар:

A × B = {(1;15), (1;25), (2;15), (2;25), (3;15), (3;25)}

Если во множестве A количество элементов равно m, а во множестве B — n, то их декартово произведение будет состоять из m×n элементов.

Следует иметь в виду что A×B и B×A разные множества, так как пары типа (a; b) отличаются от пар тип (b; a).

Примером декартова произведения множеств могут служить

• таблица умножения, где умножаются два множества, содержащие натуральные числа,

• множество точек плоскости с координатами (x; y), где x ∈ A, y ∈ B,

• множество дробей, в которых числитель принадлежит одному множеству, а знаменатель другому.

2.Основные логические операции.

1) Логическое умножение или конъюнкция:

Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно. Обозначение: F = A & B.

Таблица истинности для конъюнкции

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

2) Логическое сложение или дизъюнкция:

Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражение ложны. Обозначение: F = A + B.

Таблица истинности для дизъюнкции

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0