Логическая функция

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Логическая функция»  -  новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2020 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

В математике и логике , А булева функция является функцией , чьи аргументы , а также сама функция, принимают значения из множества из двух элементов ( как правило , {0,1}). ^[1] В результате ее иногда называют «функцией переключения».

Логическая функция принимает форму , где называется логической областью, а является неотрицательным целым числом, называемым арностью функции. В случае , когда "функция" по существу является постоянным элементом .${\ displaystyle f: \ {0,1 \} ^ {k} \ to \ {0,1 \}}$${\ displaystyle \ {0,1 \}}$${\ displaystyle k}$${\ displaystyle k = 0}$${\ displaystyle \ {0,1 \}}$

Каждую -арную булеву функцию можно выразить как пропозициональную формулу в переменных , и две пропозициональные формулы логически эквивалентны тогда и только тогда, когда они выражают одну и ту же логическую функцию. Для каждого есть свои функции .${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle x_ {1}, ..., x_ {k}}$${\ displaystyle 2 ^ {2 ^ {k}}}$ ${\ displaystyle k}$${\ displaystyle k}$

Свойства [ править ]

Логическая функция может иметь множество свойств:

• Константа : всегда истинно или всегда ложно независимо от аргументов.
• Монотонный : для каждой комбинации значений аргументов изменение аргумента с false на true может привести только к переключению вывода с false на true, а не с true на false.
• Линейный : каждая переменная всегда влияет на значение истинности или никогда не имеет значения.
• Симметричный : значение не зависит от порядка его аргументов.
• Однократное чтение : может быть выражено с помощью соединения , дизъюнкции и отрицания с одним экземпляром каждой переменной.

Логические функции в приложениях [ править ]

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

Булевы функции часто представлены предложениями в логике высказываний , а иногда и как многомерные полиномы над GF (2), но более эффективными представлениями являются диаграммы двоичных решений (BDD), нормальные формы отрицания и пропозиционально-ориентированные ациклические графы (PDAG).

В теории кооперативных игр монотонные булевы функции называются простыми играми (играми с голосованием); это понятие применяется для решения проблем теории социального выбора .

Для оптимизации электронных схем булевы функции могут быть минимизированы с помощью алгоритма Куайна – Маккласки или карты Карно .

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Crama, Y; Хаммер, PL (2011), Булевы функции: теория, алгоритмы и приложения , Cambridge University Press, DOI : 10.1017 / CBO9780511852008 , ISBN 9780511852008.
• "Булева функция" , Энциклопедия математики , EMS Press , 2001 [1994]
• Янкович, Драган; Станкович, Радомир С .; Морага, Клаудио (ноябрь 2003 г.). «Оптимизация арифметических выражений с использованием свойства двойной полярности» (PDF) . Сербский журнал электротехники . 1 (71–80, номер 1): 71–80. DOI : 10.2298 / SJEE0301071J . Архивировано из оригинального (PDF) 05 марта 2016 года . Проверено 7 июня 2015 .
• Брэдфорд Генри Арнольд (1 января 2011 г.). Логика и булева алгебра . Курьерская корпорация. ISBN 978-0-486-48385-6.
• Мано, ММ; Силетти, доктор медицины (2013), цифровой дизайн , Pearson.