Ответы пользователя по тегу Информатика
  • Как реализовать И-НЕ в базисе Исключающего ИЛИ-НЕ и возможно ли это?

    @AlfrigZverg
    Вы уверены, что задача решаема? Логический элемент "И-НЕ" реализует функцию, имеющую название "штрих Шеффера":
    https://en.wikipedia.org/wiki/Sheffer_stroke

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

    Вы хотите реализовать логический элемент "И-НЕ" в базисе "Исключающего ИЛИ-НЕ". У этой функции следующая таблица истинности:
    https://en.wikipedia.org/wiki/XNOR_gate

    Поскольку функция принадлежит к функциональному классу Поста T_1 сохраняющего константу 1, (это следует из того, что на единичном наборе она принимает значение единицы), то система функций из одной только функции "Исключающего ИЛИ-НЕ" не будет полной согласно теореме Поста (1).

    Предположим, что выполнить задачу возможно, и существует способ выразить функцию "И-НЕ" в базисе "Исключающего ИЛИ-НЕ". Тогда в силу полноты функции "И-НЕ", следует, что возможно выразить все функции в базисе "Исключающего ИЛИ-НЕ", но это невозможно, что мы доказали ранее по теореме Поста (1). Мы пришли к противоречию, следовательно, задачу выполнить невозможно.

    Единственное, проверьте таблицу истинности XNOR, совпадает ли она с таблицей истинности вашего элемента. В остальном выкладки, я думаю, справедливы.

    P.S. Если вас интересуют именно вопросы связанные с теоремой Поста и функциональной полнотой систем логических функций, то я знаю, что вам посоветовать. Напишите EMail - вышлю.
    Ответ написан
    1 комментарий