Арифметические операции в восьмеричной и шестнадцатеричной системах счисления

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

 

14.Основные понятия математической логики. Основные логические операцию. Аксиомы и законы алгебры логики.

 

Понятия:

· Суждение - это некоторое высказывание, которое может быть истинным или ложным.

· Утверждение - это суждение, которое требуется доказать или опровергнуть.

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

· Логика- это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений.

· Высказывание - это повествовательное предложение, о котором можно сказать, истинно оно или ложно.

 

Основные логические операции:

· Конъюнкция – логическое умножение.

· Дизъюнкция– логическое сложение

· Инверсия –логическое отрицание.

· Импликация –логическое следование. Из истины следует ложь равно ложь. В остальных случаях истина.

· Эквивалентность – равноценность.

Аксиомы и законы:

1. , закон снятия двойного отрицания.

2.

3.

4.

5.

6.

7.

8.

9.

 

15.Логические функции двух переменных. Таблица истинности логических функций.

 

 

Представленные 16 функций называются элементарными. Функции и являются константами соответственно 0 и 1.

- есть конъюнкция (логическое умножение)

альтернатива (сложение по модулю 2)

дизъюнкция

функция Вебба (или-не)

эквивалентность (равнозначность)

функция Шеффери (и-не)

 

16.Совершенные нормальные формы логических функций.

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

· в ней нет одинаковых элементарных конъюнкций

· в каждой конъюнкции нет одинаковых пропозициональных букв

· каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФпропозициональных букв, причём в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причём единственная.

 

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

· в ней нет одинаковых элементарных дизъюнкций

· в каждой дизъюнкции нет одинаковых пропозициональных переменных

· каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

 

17.Совершенные нормальные формы логических функций двух переменных.

18.Элементы НЕ, И, ИЛИ. Функциональные схемы в элементах НЕ, И, ИЛИ.

 

Схема И.

Схема И реализует конъюнкцию двух или более логических значений.

Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис. 1. Таблица истинности — в таблице 1.

Рис. 1

Таблица 1 X Y X×Y

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x×y (читается как "x и y").

Операция конъюнкции на функциональных схемах обозначается знаком “&” (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.

 

Схема ИЛИ

Схема ИЛИ реализует дизъюнкцию двух или более логических значений.

Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.

Условное обозначение схемы ИЛИ представлено на рис. 2. Знак “1” на схеме — от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y"). Таблица истинности — в табл. 2.

Рис. 2

Таблица 2 X Y X v Y

Схема НЕ

Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z = x, где x читается как "не x" или "инверсия х".

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение инвертора — на рисунке 3, а таблица истинности — в табл. 3.

Рис. 3

Таблица 3 x x

 

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

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

 

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

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

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

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

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

 

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

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

 

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

 

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

 

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

 

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

 

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

 

22.Машина Тьюринга.

 

Маши́на Тью́ринга (МТ) — aбстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

 

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

 

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

 

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

 

23.Нормальные алгоритмы Маркова.

 

НормальныйалгоритмМаркова— один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.

 

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

 

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.

 

Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам из символов которого алгорифм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где и — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где и — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

 

24.Способы композиции алгоритмов.

 

Способы композиции нормальных алгоритмов:

 

I. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов слово первого алгоритма рассматривается как входное слово второго алгоритма B, результат суперпозиции C может быть представлен в виде C(p) и B(A(p)).

II. Объединение алгоритмов. Объединением алгоритмов А и B в одном и том же алфавите называется алгоритм Св том же алфавите, преобразующий любое слово p содержащееся в пересечении областей определения алгоритмов Аи В, в записаныe рядом слова А(р) и В(р).

III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов A,В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмовА, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если C(p) = е, где е - пустая строка.

IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую суперпозицию С двух алгоритмовА и В, что для любого входного слова p соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом B.