Интернет магазин китайских планшетных компьютеров

Компьютеры - Арифметико-логический способ представления троичных функций - Функциональная полнота арифметико-логического способа представления троичных функций элементов

Троичные функции являются отдельным случаем k-значной логики. Известное представление функции k-значной логики в виде так называемых Σ-Π форм:

Для получения такого представления вместе с константами 0,1,…,…, k-1, операциями вычисления суммы Σ — x+y и произведения Π — xy пользуются характеристическими функциями следующего вида:

где k∈{0,1,2}.

Если перейти от констант 0,1,2 к константам 0,1,-1, то для троичных функций получим

где А — множество наборов переменных, на которых функция принимает значение 1, то есть для , тогда

Так как, x_i ∈, о операция умножения тождественна двоичной операции И. Аналогично, как каждому набору соответствует только одно произведение, которое равняется 1, то операция добавления по mod k тождественна при указанных условиях двоичной операции ИЛИ. Откуда получаем

Эта формула даёт строгий метод записи троичных функций в алфавите −1,0,1 и полностью соответствует формуле f₃=f₁-f₂, что доводит функциональную полноту представления троичных функций в виде двух двоичных, между значениями которых выполняется арифметическая операция вычитания.

Отметим, что для доказательства полноты в данном случае использован принцип сведение задачи про полноту одной системы к задаче доказательства полноты другой системы. Для двоичных логических элементов возможны разные функционально полные системы на основе элементов, которые реализуют функции И-НЕ, ИЛИ-НЕ и т. д. Очевидно, что используя эти элементы и дополнительный элемент, который реализует функцию вычитания, можно синтезировать любой троичный элемент.

Из сигма-пи формы троичных функций непосредственно вытекает функциональная полнота системы, которая включает: характеристические функции, функции И, ИЛИ и функцию вычитания.