Суперпозиція і формули

Суперпозиція функцій f₁…f_n це функція F отримана за допомогою підстановки функцій одна в одну в якості аргументу и перейменування даного аргументу. Формулою називається вираз який описує дану суперпозицію.

Поняття суперпозиції дуже важливе в матлогіці. Нехай є множина (скінченна чи безмежна) функцій {f₁…f_n…}=å. Символи стартових змінних будемо називати «0» глибини. Тобто стартові аргументи х₁…х_n… - формули «0» глибини. Формула F має глибину «к+1» тоді коли F= f_i(F₁,…,F_ni), і якщо F₁,…,Fn_i мають «к» глибину.

Формули (аргументи функції F) F₁,…,F_ni називаються підформулами F_. f_i – називаються зовнішньою або ж головною операцією формули F.

Такі назви використовуються для всіх виразів, що входять в суперпозицію. Наприклад f₁(x₁,x₂)– формула «1» глибини, f₂(f₁ (x₁,x₂))– формула «2» глибини і т.д.

Приклад: нехай f₁ – диз’юнкція f₂– кон’юнкція, f₃ – додавання по модулю 2.

Тоді:

f₃(f₁(х₁,х₂), f₂(х₁, f₃(х₁,х₂)))=(х₃ х₁) Å(х₁ (х₁ Åх₂))

Форма запису функцій, коли використовуються символи ù, , ,Å,®,~, дії між аргументами називається інфіксною.

Принцип обчислення значення функції при заданих значеннях аргументів.

Нехай х₁=1, х₂=1, х₃=0

Тоді:

Зрозуміло, що усі обчислення, при невеликому числі аргументів, можна представити за допомогою таблиці істинності.

Ще раз звертаємо увагу, що довільні функції матлогіки можна виразити через інші з глибиною 1 або 2. Наприклад штрих Шеффера

х₁| х₂= або ж .

Функцію “стрілка Пірса”

х₁¯х₂= або .

Формули, які по різному представляють одну і ту ж функцію називаються еквівалентними або ж рівносильними.

Щоб перевірити чи є дані представлення функцій еквівалентними необхідно порівняти їх таблиці істинності.

Наприклад: =

Останні два стовпці стверджують еквівалентність відповідних функцій.