Контрольная работа по «Информатике и информационно-коммуникационным технологиям»

Логическими высказываниями являются утвердительные предложения, о которых можно судить, истинны они или ложны. Причем они не могут быть истинными и ложными одновременно. Логика высказываний рассматривает эти предложения не с точки зрения их смысла, содержания, а только с точки зрения их истинности или ложности. Вопросительные, повелительные и бессмысленные предложения не являются логическими высказываниями.

Говорят, что если предложение  истинно, то его значение истинности равно 1, если ложно – то 0 . По аналогии с элементарной алгеброй, где любое число является константой, высказывание является логической константой, величина которой равна 1 или 0

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

Отрицание (логическая связка «не»)

Отрицанием (инверсией) высказывания А называется высказывание, которое истинно, если высказывание А ложно, и ложно, когда А истинно. Записывается: или ¬A . Читается: «не А » («не верно, что А»). Отметим, что отрицание является логической операцией, выполняемой над одним аргументом.

Логическое умножение (конъюнкция)

Конъюнкция двух высказываний А и В — это сложное логическое высказывание, которое истинно только в случае истинности всех составляющих высказываний, в противном случае оно ложно. Обозначения: A&B, . Читается: «А и В ».

Логическое сложение (дизъюнкция)

Дизъюнкция двух высказываний А и В — это сложное логическое высказывание, которое ложно только в случае ложности всех составляющих высказываний, в противном случае оно истинно. Таким образом, это высказывание считается истинным, когда истинно хотя бы одно из составляющих высказываний. Обозначается: A∨B. Иногда встречается обозначение A+B . Читается: А «или » В

Логическое следование (импликация)

В математических доказательствах  часто пользуются сложными высказываниями, образованными с помощью слов «если…, то…». Здесь высказывание, расположенное после слова «если», называется основанием или посылкой, а высказывание, расположенное после слова «то», называется следствием или заключением. Импликацией двух высказываний и называется высказывание, обозначаемое символом A→В, которое ложно тогда и только тогда, когда А истинно, а В ложно. Иногда встречается обозначение . A⊃В . Читается: «если А , то В» («А влечет В», «из А следует В »).

Логическое тождество (эквиваленция)

Эквиваленцией (эквивалентностью, равнозначностью) двух высказываний А и В называется высказывание, обозначаемое символом А~В (или А ↔В) , которое истинно когда истинностные значения А и В высказываний и совпадают, и ложно — в противном случае

Исключающее «или» (неравнозначность)

Неравнозначностью двух высказываний А и В называется высказывание, истинное, когда истинностные значения А и В не совпадают, и ложное — в противном случае. Обозначается: . Читается: «либо А, либо В» (понимается — в разделительном смысле).

Формулы алгебры  высказываний

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

Предикаты

Это понятие обобщает понятие «высказывание». Иначе говоря, предикат — это высказывание, содержащее неизвестную (или несколько неизвестных), т. е. в него можно подставлять аргументы. Если аргумент один - то предикат выражает свойство аргумента, если больше - то отношение между аргументами.

Одноместным предикатом называется функция одной переменной, значениями которой являются высказывания об объектах, представляющих значения аргумента. Следовательно, одноместный предикат Р(x) – это произвольная функция переменной x, определенная на некотором множестве М и принимающая (логические) значения из множества {0,1} .

Областью истинности предиката Р(x), заданного на множестве М называется совокупность всех х из М, при которых данный предикат обращается в истинное высказывание.

Кванторы

Функциональная природа предиката  влечет за собой введение еще одного понятия — квантора. Квантор — это общее название для логических операций, ограничивающих область истинности какого-либо предиката. В математической логике наиболее употребительны квантор всеобщности и квантор существования . Пусть Р(x) – одноместный предикат, определенный на множестве М. Под выражением xP(x) понимают высказывание, истинное, если Р(x) истинно для каждого элемента x М и ложное в противном случае. Иными словами, истинность высказывания xP(x) означает, что область истинности предиката Р(x) совпадает с областью изменения переменной х. Читается это высказывание: «для всякого х истинно Р(x)».

Под выражением xP(x) понимают высказывание, истинное, если существует x М для которого Р(x) истинно, и ложное в противном случае.

Иными словами, истинность высказывания xP(x)означает, что область истинности предиката Р(x) непуста. Читается это высказывание: «существует х при котором истинно Р(x)».

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

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

 

Конспект 12. Элементы теории алгоритмов⁵

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

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

Алгоритмом называется общий единообразный, точно определенный способ решения любой задачи из данной массовой проблемы.

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

Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм говорят, что он «вычисляет функцию f », коль скоро его область применимости совпадает с областью определения f, и он перерабатывает всякий х из своей области применимости в f(х).

Проблема построения алгоритма, обладающего  теми или иными свойствами, называется алгоритмической проблемой.

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

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

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

Машина Тьюринга – абстрактное устройство, состоящее из бесконечной в обе стороны ленты, считывающей и печатающей головки, способной перемещаться вправо и влево, и управляющего устройства. Лента разбита на ячейки (клетки). Считывающая и печатающая головка перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. В ячейках могут быть записаны символы некоторого конечного алфавита А={a₀,a₁,……a_k}

Устройство обладает некоторым конечным набором состояний Q={q₀,q₁,……q_n}

Программа для машины Тьюринга представляет собой конечный список команд вида: qa→q′a′D, где a, a′ A, q, q′ Q, D {R,L,S}; R,L,S − вправо, влево, стоп.

Команда расшифровывается так: если машина находится в состоянии q и считанный с ленты символ a равен, то машина переходит в состояние q′, печатает в текущей клетке символ a′ и затем выполняет одно из трех действий D. Если D=R, то машина смещается на одну клетку вправо, если D=L, то на одну клетку влево, а если D=S, то машина никуда не смещается.

Необходимо, чтобы в  программе не было разных команд с  одинаковыми входами вида qa→q′a′D; qa→q″a″D″ – это противоречит однозначности алгоритма.

Алгоритмически неразрешимые проблемы

Пусть алфавит машины Тьюринга содержит символы 1 и *. В этом случае можно предложить машине в качестве исходной записи на ленте ее код. Если при работе над собственным кодом машина Тьюринга М останавливается, то она называется самоприменимой. Если она не останавливается, она называется несамоприменимой.

Возникает вопрос: существует ли машина М_S , которая по коду любой машины определяет, самоприменима ли она? Если она существует, она должна быть применима к коду любой машины M и должна останавливаться на клетке с 1 в случае самоприменимости M, и на клетке с 0 в противном случае.

Теорема. М_S не существует, то есть проблема самоприменимости алгоритмически неразрешима.

Рекурсивные функции. Тезис  Чёрча 

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

Частичными числовыми функциями f(x₁,….,x_n), x_i (1≤i≤n), называют функции, определенные не на всех наборах (x₁,….,x_n), x_i x……x = .

Назовем простейшими следующие всюду определенные функции:

0(x)=0 – нулевая функция; s(x)=x+1 – функция следования; (x1,….,xn)=x_m , 1≤m≤n – функция выбора аргумента.

Все простейшие функции могут быть вычислены на машине Тьюринга:

Функции, которые могут быть получены из простейших функций с помощью  конечного числа применений операций суперпозиции, примитивной рекурсии и минимизации называются частично рекурсивными. Общерекурсивные функции – это подмножество частично рекурсивных функций, определенных для всех значений аргументов. Легко понять, что множество общерекурсивных функций включает в себя множество примитивно рекурсивных функций, а частично рекурсивные функции включают в себя общерекурсивные функции. Известно, что не всякая общерекурсивная функция является примитивно рекурсивной. В то же время существуют частично рекурсивные функции, которые не могут быть продолжены до общерекурсивных. Заметим, что частично рекурсивные функции иногда называют просто рекурсивными функциями. Для любой частично рекурсивной функции можно указать алгоритм вычисления ее значений, т. е. все частично рекурсивные функции суть вычислимые функции. Обращение этого высказывания носит название тезиса Чёрча.

Тезис Чёрча. Всякая вычислимая частичная числовая функция является частично рекурсивной функцией.

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