https://sibwiki.org/index.php?action=history&feed=atom&title=%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 2026-06-01T03:29:20Z Revision history for this page on the wiki MediaWiki 1.43.5 https://sibwiki.org/index.php?title=%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9&diff=85195&oldid=prev 2026-05-28T23:53:27Z

<p>Bot: Automated import of articles</p> <p><b>Нова сторонка</b></p><div>{{YouTube|ZKkI_pH9UcI|width=300|height=250}}<br /> <br /> == Общие сведения ==<br /> Математическое описание функций требует нахождения оптимальных способов их записи, что подразумевает создание максимально простых формул с минимальным количеством операторов. Базовым принципом работы с логическими формулами является то, что при замене всех вхождений одной переменной на другую формулу результирующее выражение сохраняет свои базовые свойства. В рамках преобразований допускается осуществлять отождествление и переименование переменных. Данные процессы приводят к фундаментальному понятию подстановки, которое широко применяется в теории алгоритмов и математической логике. Совокупность всех булевых функций, определенных на множестве чисел ноль и один, обозначается как класс P2.<br /> <br /> == Теоретические основы ==<br /> Операция подстановки носит структурно-лингвистический характер, при котором одни фрагменты выражения заменяются другими, при этом исходные логические связки остаются неизменными. Класс функций называется замкнутым, если любая функция, полученная путем подстановки, отождествления или переименования переменных из исходных функций этого класса, также принадлежит данному классу. Множество функций является полным и порождает замкнутый класс, если оно содержит те и только те функции, которые могут быть получены из него с помощью подстановок. Основная теоретическая задача заключается в том, чтобы определить, какими минимальными системами можно заменить все множество булевых функций без потери выразительной способности системы.<br /> <br /> == Основные определения и свойства ==<br /> В дискретной математике выделяются несколько фундаментальных замкнутых классов булевых функций. Функции, сохраняющие ноль, возвращают нулевое значение при исключительно нулевых аргументах, а функции, сохраняющие единицу, возвращают единицу при единичных аргументах. Множества всех булевых функций, сохраняющих ноль или единицу, образуют самостоятельные замкнутые классы. Двойственная функция образуется путем инвертирования всех переменных внутри исходной функции с последующим инвертированием результата самой функции. Если функция тождественно равна своей двойственной функции, она называется самодвойственной, и такие функции также формируют замкнутый класс. Монотонная булева функция определяется тем, что при возрастании значений аргументов значение самой функции не убывает, что образует еще один замкнутый класс. Линейные функции могут быть представлены в виде полинома Жегалкина, в котором полностью отсутствуют конъюнкции переменных, и совокупность таких функций образует замкнутый класс линейных функций.<br /> <br /> == Практическое применение ==<br /> Концепции замкнутых классов и подстановок имеют прямое практическое применение в алгоритмической обработке данных и компьютерных вычислениях. Любую логическую функцию из класса P2 можно выразить через базовые операции конъюнкции, дизъюнкции и отрицания. Существуют еще более компактные полные системы, позволяющие свести все операции исключительно к конъюнкции и отрицанию либо к дизъюнкции и отрицанию. Минимальной полной системой является штрих Шеффера, представляющий собой единственный оператор, способный самостоятельно выразить любую булеву функцию. В то же время системы, состоящие только из одной конъюнкции, не являются полными и не могут описать все возможные логические выражения.<br /> <br /> == Особенности и характеристики ==<br /> Ключевым критерием полноты системы булевых функций является теорема Поста. Согласно данной теореме, система порождает полный класс P2 тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую ноль, функцию, не сохраняющую единицу, несамодвойственную функцию, немонотонную функцию и нелинейную функцию. Штрих Шеффера удовлетворяет всем пяти перечисленным условиям теоремы Поста, что строго математически обосновывает его полноту. Базисом называется такое полное множество функций из замкнутого класса, из которого удаление любой функции приводит к потере полноты всей системы. Доказано, что любой базис для пространства булевых функций содержит не более четырех функций.<br /> <br /> == См. также ==<br /> <br /> [[Исчисление высказываний]]<br /> <br /> [[Category:Математическая логика]]<br /> <br /> [https://www.youtube.com/watch?v=ZKkI_pH9UcI Смотреть видео]</div>

Yaroslav