67607

Полнота и замкнутость

Лекция

Математика и математический анализ

Система функций из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы

Русский

2014-09-12

131.5 KB

1 чел.

Лекция № 16  (11.04.00)

Полнота и замкнутость

Опр || система функций  из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Пример: 1) Само множество ;

2);

3) - не полна.

Теорема || Пусть даны две системы функций из

, (I)

. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство || Пусть . В силу полноты сист. I функцию h можно выразить в виде формулы . По условию теоремы

Поэтому

ч. и т.д.

Примеры ||

1)  - полная.

2)  - тоже полная, так как .

3)  - тоже полная.

4)  - тоже полная, так как

,

,

. ((2) – I)

5)  - неполная. Докажем это от противного.

Предположим, что .

Но . Противоречие.

6)  - неполная (сохраняет константу 0 – см. след лекц.).

7)  - неполная (сохраняет константу 1 – см. след лекц.).

6)  -  полная

8)  

тогда взяв в качестве сист. I сист. 2) можно заключить, сист. функций 8) – полная. Тем самым, справедлива

Теорема Жегалкина || Каждая функция из  может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина):

.

Имеем: число разных сочетаний  равно числу подмн-в мн-ва из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}. Тогда число разных пол. Жег. равно , т.е. равно числу различных булевых функций.

Т. о. получаем единственность представления функций через пол. Жег.

Примеры

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

Пока опустим

2 способ T-преобразов. вектора функции

X1

x2

x3

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

3 способ – алгебраических преобразований

Опр. Пусть M – некоторое подмножество функций из P2. Замыканием M называется мн-во всех булевых функций, представимых в виде формул через функции мн-ва M. Обозначается [M].

Замечание. Замыкание инвариантно относ. операций введения и удаления фиктивных перем.

Примеры.

1) M=P2, [M]=P2.

2) M={1,x1x2}, [M] – мн-во L всех линейных ф-й вида

,   (ci{0,1}).

Свойства замыкания:

  1.  [M]=M;
  2.  [[M]]=[M];
  3.  M1M2  [M1][M2];
  4.  [M1M2][M1][M1].

Опр. Класс (мн-во) M называется (функционально) замкнутым, если [M]=M.

Примеры.

  1.  Класс M=P2 функционально замкнут;
  2.  Класс {1,x1x2} не замкнут;
  3.  Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

Новое определение полноты. M – полная система, если [M]=P2.


 

А также другие работы, которые могут Вас заинтересовать

84542. Артеріальний пульс, його походження СФГ, її аналіз 43.09 KB
  При аналізі СФГ враховують перш за все стан стінок крупних артеріальних судин. Про це можна судити за конфігурацією СФГ вираженості окремих її хвиль. Розрахунок тривалості серцевого циклу проводять по полікардіограмі синхронно зареєстровані ЕКГ ФКГ СФГ.
84543. Регуляція діяльності серця. Міогенні та місцеві нервові механізми регуляції діяльності серця 40.8 KB
  Міогенні та місцеві нервові механізми регуляції діяльності серця. Баланс притоку та відтоку крові притік крові до серця по венозних судинах; відтік за рахунок активного вигнання крові шлуночками серця; 2. Рівний хвилинний обєм крові ХОК правого та лівого відділів серця; 3.
84544. Місцеві міогенні механізми регуляції серцевої діяльності 48.71 KB
  Залежність ССС від вихідної довжини КМЦ. Залежність ССС від опору вигнанню рівня артеріального тиску. Залежність ССС від ЧСС. Тому суть цього механізму можна викласти так: чим більше крові притікає до серця під час діастоли тим більша вихідна довжина КМЦ тим більша ССС СО.
84545. Характер і механізми впливів симпатичних нервів на діяльність серця. Роль симпатичних рефлексів в регуляції серцевої діяльності 44.58 KB
  Характер впливів симпатичної нервової системи на серце: позитивний інотропний вплив посилює силу серцевих скорочень; позитивний хронотропний вплив посилює ЧСС; позитивний дромотропний вплив посилює швидкість проведення збудження по елементам провідної системи серця особливо по передсердношлуночковому вузлу структурам провідної системи шлуночків; позитивний батмотропний вплив збільшення збудливості. Медіатор норадреналін взаємодіє переважно з βадренорецепторами оскільки αадренорецепторів тут майже немає при цьому...
84546. Характер і механізми впливів парасимпатичних нервів на діяльність серця. Роль парасимпатичних рефлексів в регуляції серцевої діяльності 44.78 KB
  Механізм впливів блукаючого нерва на серце повязаний із дією медіатора ацетилхоліну на мхолінорецептори КМЦ типових і атипових. В результаті підвищується проникність мембран КМЦ для йонів калію посилення виходу йонів із клітини за градієнтом концентрації що в свою чергу веде до: розвитку гіперполяризації мембран КМЦ; найбільше цей ефект виражений в клітинах з низьким вихідним рівнем мембранного потенціалу найбільше в вузлах АКМЦ: пазуховопередсердному та передсердношлуночковому де МПС = 60мВ; менше в КМЦ передсердь; найменше ...
84547. Гуморальна регуляція діяльності серця. Залежність діяльності серця від зміни йонного складу крові 44.41 KB
  Залежність діяльності серця від зміни концентрації йонів в плазмі крові. Найбільше клінічне значення має вплив йонів калію. При гіпокаліємії зниження концентрації йонів калію в плазмі крові нижче 1ммоль л розвиваються різноманітні електрофізіологічні зміни в КМЦ. Характер змін в КМЦ залежить від того що переважає: втрата йонів калію клітинами чи міжклітинною рідиною.
84548. Особливості структури і функції різних відділів кровоносних судин у гемодинаміці. Основний закон гемодинаміки 52.71 KB
  При такому підході видно що кровоносна система є замкненою системою в яку послідовно входять два насоси і судини легень і паралельно судини решти областей. Судини у системі крові виконують роль шляхів транспорту. Рух крові по судинам описує основний закон гемодинаміки: де Р1 тиск крові на початку судини Р2 в кінці судини R тиск який здійснює судина току крові Q обємна швидкість кровотоку обєм який проходить через поперечний переріз судини за одиницю часу. Отже рівняння можна прочитати так: обєм крові що проходить...
84549. Значення в’язкості крові для гемодинаміки. Особливості структури та функції різних відділів судинної системи 44 KB
  Вязкість крові залежить від таких 2ох факторів. Від зміни лінійної швидкості руху крові. Вязкість крові складає 45 50 умовних одиниць а плазми 17 23 гривні.
84550. Лінійна і об’ємна швидкості руху крові у різних ділянках судинного русла. Фактори, що впливають на їх величину 41.83 KB
  Обємна швидкість руху крові той обєм крові котрий проходить через поперечний переріз судини за одиницю часу. Замкнута система кровообігу може нормально функціонувати лише при умові що обємна швидкість кровотоку в будьякій ділянці однакова. Лінійна швидкість руху крові швидкість руху частинок крові відносно стінок судини. Оскількм ХОК в різних ділянках однаковий лінійна швидкість кровотоку визначається площею поперечного перерізу.