Контрольная работа: Математическая логика

1) не сохраняющую ноль;

2) не сохраняющую единицу;

3) нелинейную;

4) немонотонную;

5) несамодвойственную.

Примерами функционально полных систем являются, например, системы:

.

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

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

К базису относятся системы функций:

базис 1: ;

базис 2: ;

базис 3: ;

базис 4: функция Шеффера: x ₁ | x ₂ ;

базис 5: функция Пирса (Вебба): x ₁ ↓ x ₂ .

Базис 1 – избыточный, базисы 4 и 5 – минимальные (удаление хотя бы одной функции превращает систему ФАЛ в неполную).

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

Пример.

Является ли система булевых функций полной? Если является, то выписать все возможные базисы.

Рассмотрим функцию .

1. Исследуем ее принадлежность к классу К ₀ :

.

Следовательно, .

2. Исследуем принадлежность функции к классу К ₁ :

.

Следовательно, .

3. Установим, является ли функция f ₁ линейной. Используем метод неопределенных коэффициентов. Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:

.

Найдем коэффициенты , исходя из предположения линейности этой функции. Зафиксируем набор 000: