Полные системы

1. P₂ – полная система.

2. Система M={x₁&x₂, x₁Úx₂, } – полная система, т.к. любая функция алгебры логики может быть записана в виде формулы через эти функции.

Пример 1. Неполные системы: {}, {0,1}.

 

Лемма (достаточное условие полноты)

 

Пусть система U = {f₁, f₂, ..., f_s, ...} полна в Р₂. Пусть B = {g₁, g₂, ..., g_k, ...} – некоторая система из Р₂, причем любая функция f_i Î U может быть выражена формулой над B, тогда система B полна в Р₂.