11. Полнота ив

Здесь мы рассмотрим 3 вида полноты:

• в широком смысле;

• в узком смысле;

• абсолютная.

Df. 3.7: ИВ называется полным в широком смысле, если в нем выводимы все тавтологии. Покажем, что рассматриваемое ИВ является полным в широком смысле.

Лемма .3.11: Пусть дана формула А и пусть В₁В₂,…В_n – совокупность всех символов 1-ой группы алфавита, входящих в формулу А. Придадим В₁В₂,…В_n соответственно значения v₁ ,v₂ , …, v_n и значение, которое при этом примет формула А обозначим через V. Тогда: Ⱶ (1).

Лемма 3.12: Каждая тавтология является выводимой формулой.

Д-во: Пусть формула А – тавтология и пусть В₁В₂,…В_n - совокупность символов одной группы алфавита, входящих в формулу А. Тогда по лемме 3.11 получаем Ⱶ (2). Применим к (2) теорему дедукции: (3) получаем:

А = ;

Кроме того, по Лемме3.6 будем иметь

Применим к (4), (6) правила вывода МР. Наконец, применив к (5),(7) правила вывода МР мы получим, что: (8). Таким образом, имея (2), мы получим (8). Тогда, применив еще (n-1) описанную процедуру, мы получим Чтд.

Следств: Рассматриваемое ИВ является в широком смысле.

Df. 3.8: ИВ называется полным в узком смысле, если присоединив его схему аксиом любую не выводимую формулу, мы получаем противоречивую теорию.

Зам: Можно показать, что рассматриваемое выше ИВ является полным в узком смысле.

Df. 3.9: ИВ называется абсолютно полным, если в нем из каждой пары формул вида В и , выполнимой является хотя бы одна.

12. Правило суммы, произведения

Основная задача комбинаторики: пересчет и перечисление элементов в конечных множествах.

Df. 4.18: Пересчет – это определение числа элементов данного конечного множества, обладающих каким-либо свойством или группой свойств.

Df. 4.19: Перечисление – это выделение всех элементов данного конечного множества, обладающих некоторым свойством или группой свойств.

Правило суммы. Правило Х₁, Х₂, …,Х_к – попарно непересекающиеся мн-ва, т.е. .

Тогда мощность

Зам: Если , то говорят, что хХ может быть выбран n-способами

Зам: Если k=2, то правило суммы для этого случая формулируется след. образом: Если хХ может быть выбран n-способами, а объект yY может быть выбран m-способами, то выбран либо х, либо у может быть выполнен (m+n) различными способами.

Правило произведения: Если объект х может быть выбран m-способами и после каждого и таких выборов объект у может быть выбран n различными способами, то выбор упорядоченной пары <x,y> может быть выполнен mn различными способами.

Д-во: Пусть объект ч выбирается из множества {a₁,a₂,…,a_m}. Через Х_i (1im) обозначим множество упорядоченных пар, в каждой из которых первым элементом является a_i.

Очевидно, множества Х₁, Х₂, …,Х_m – попарно не пересекаются и объединение этих множеств дает нам искомое множество. Кроме того,

Тогда по правилу суммы получаем . Чтд

Зам: В общем случае правило произвед. формулируется след. образом: Пусть объект х₁ может быть выбран m₁-способами. Пусть после каждого из таких выборов объект х₂ может быть выбран m₂­-разл. Спб-ми и т.д. Пусть после выбора х₁,х₂, … , х_n-1 объект x_n может быть выбран m_n – различными способами. Тогда выбор упоряд последовательности <x₁,x₂, … , x_n> может быть выполнен m₁,m₂, … , m_n – различными способами.