19. Минимальный элементный базис. Функциональные схемы в элементах или-не, и-не.

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

При записи правых частей приведённых функций учтено:

• для Y₁ — тождество хх...х = х,

• для Y₂ и Y₆ — тождество х =,

• для Y₃ и Y₅ — теорема Моргана.

• для Y₄ — тождество х +х +....х = х

Таким образом, в соответствии с правой частью приведённых равенств операции И, ИЛИ, НЕ могут быть выполнены элементами И — НЕ, а также элементами ИЛИ — НЕ, что показано на рисунке: 

20. Понятие алгоритма.

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

21. Машина Поста.

Маши́на По́ста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом(англ. Emil Leon Post), которая отличается от машины Тьюринга большей простотой. Обе машины алгоритмически «эквивалентны» и были придуманы для уточнения понятия «алгоритм». В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима также в форме последовательности команд для машины Поста.

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (см. пример ниже). Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0, либо помеченной меткой 1. За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку.