Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

37 Тема 3. Полнота и замкнутость систем логических функций 8. Основные определения. Основные замкнутые классы Основные определения Определение. Система функций {f 1 ,f 2 ,…,f n } из P 2 называется функционально полной, если любая логическая функция может быть записана в виде формулы через функции этой системы. Примеры полных систем: а) P 2 – полная система, б) система {  ,  ,  } – полная система. Не каждая система является полной. Так {0,1} не является, очевидно, полной. Теорема 8.1. Пусть даны две системы функций из P 2 : F={f 1 ,…,f n }, G={g 1 ,…,g m }. Пусть система F –полна и каждая ее функция выражается в виде формулы через функции системы G . Тогда система G – полна. Доказательство. Пусть h –произвольная функция из P 2 . В силу полноты F ее можно представить в виде h=u(f 1 ,…,f n ) . По условию теоремы f 1 =u 1 (g 1 ,…,g m ) ………………… f n =u n (g 1 ,…,g m ) Тогда h=u(f 1 ,…,f n )=u(u 1 (g 1 ,…,g m ),…,u n (g 1 ,…,g m ))=u  (g 1 ,…,g m ). Из теоремы, например, вытекает: а) система {  ,  } является полной, что следует из полноты системы {  ,  ,  } и равенства 1 2 1 2 x x x x   .