Носырева ЛЛ Математическая логика и теория алго..


Министерство образования и науки РФ
НИ Иркутский государственный технический университет
МАТЕМАТИЧЕСКая ЛОГИКа
Методические указания к практическим занятиям
для студентов специальностей АСУ, ИСТИркутск 2010
«Методические указания к практическим занятиям «Математическая логика» предназначено для студентов специальностей АСУ, ИСТ факультета Кибернетики. Составитель Л.Л. Носырева.
Иркутск, 2010, 56 - с.
Содержит задания для работы на практических занятиях, а также индивидуальные контрольные задания.
Библ. 11 назв.
Рецензент: Белых Татьяна Ивановна, доцент кафедры информатики и кибернетики БГУЭП

Занятие №1
Тема: Алгебра высказываний.
Основные определения и понятия.
I.Ответьте на следующие вопросы:
Что называется высказыванием? Приведите примеры.
Какие операции можно выполнять над высказываниями? Как определяются эти операции?
Что называется формулой алгебры высказываний? Приведите примеры.
Как определить истинностное значение сложного высказывания?
Что называется подформулой формулы алгебры высказываний?
Какова последовательность выполнения операций в формуле алгебры высказываний?
Дайте определение тавтологии, противоречия, выполнимой формулы.
Какие формулы называются равносильными? Запишите основные равносильности алгебры высказываний.
II.Выполните следующие упражнения:
Какие из следующих предложений являются высказываниями и определите их истинностное значение:
Иркутск - областной город;
Москва – столица СССР;
;
;
для всякого числа x: ;
;
;
существует действительное число х такое, что .
Пусть A и B есть соответственно высказывания: «Углы α и β – вертикальные» и «Углы α и β равны». Прочитать следующие высказывания:;
;
;
;
;
.
Следующие составные высказывания расчленить на простые и записать символически, введя сокращенные обозначения для простых высказываний:
если число a делится на 2 и не делится на 3, то оно не делится на 6;
произведение двух чисел равно нулю тогда и только тогда, когда одно из них равно нулю;
если треугольник не равнобедренный и не равносторонний, то любая его медиана не является высотой и биссектрисой;
число a является корнем системы m уравнения с одним неизвестным тогда и только тогда, когда оно является корнем каждого из системы уравнений;
если мистер Джонс счастлив, то миссис Джонс несчастлива, и если мистер Джонс несчастлив, то миссис Джонс счастлива;
необходимым условием дифференцируемости функции в точке является ее непрерывность в этой точке.
Из двух данных высказываний A и B построить составное высказывание с помощью операций отрицания и конъюнкции, которое было бы:
истинным тогда и только тогда, когда оба высказывания A и B ложны;
ложно тогда и только тогда, когда оба высказывания A и B истинны;
ложно тогда и только тогда, когда A-истинно, а B – ложно.
Известно, что высказывание истинно. Можно ли утверждать, что и высказывание истинно?
Построить таблицы истинности для формул:
;
;

;
;
;
;
;
.
Определить, является ли каждая из следующих формул тавтологией, противоречием или выполнимой:
;
;
;
;
;
;
.
Доказать, что следующие формулы - тавтологии:
;
;
;
;
;
;
;
;
.
При каких значениях A, B, C, D следующие формулы ложны:
;
;
;
;
;
;
;
;
;
.
Известно, что, , , – тавтология, докажите, что тогда:
- тавтология;
- тавтология;
- тавтология;
- тавтология;
- противоречие;
- противоречие;
- тавтология;
- тавтология.
Докажите равносильность следующих формул двумя способами – посредством равносильных преобразований и с помощью таблицы истинности:
и ;
и ;
и ;
и ;
и ;
и ;
и ;
и ;
и ;
и .
Докажите справедливость следующих равносильностей:
тождества: ;идемпотентности: и ;
коммутативности: и ;
ассоциативности: и ;
дистрибутивности:
и ;
двойного отрицания:;де Моргана: и ;
, и , ;
противоречия: ;исключенного третьего: ;замены эквиваленции: ;поглощение: и ;
склеивания: и ;
контропозиции: ;силлогизма: ;прямого вывода (заключения): .
Индивидуальные задания
Задание 1.
Проверить, является ли формула тавтологией, противоречием или выполнимой:

варианта Формула:






























Задание 2
Что можно сказать об истинности высказывания A, если B и C истинные высказывания и при этом:

варианта ;

;
;
;
.
Известно, что высказывания A и B истинные, а C и D – ложные. Найдите значения истинности следующих высказываний:

варианта ;
;
;
;
;
.
Какие из следующих выражений являются формулами алгебры высказываний?

варианта ;
;
;
;
;
.
Сколькими способами и как можно расставить скобки в выражении, чтобы получилась формула:

варианта ;
;
;
;
;
.
Выписать все подформулы формулы:

варианта ;
;
;
;
.
Задание 3.
Формализовать следующие высказывания:
чтобы углы были смежными, достаточно, чтобы они имели общую сторону.
чтобы углы были смежными, необходимо и достаточно, чтобы две стороны их были противоположными лучами;
чтобы построить окружность, достаточно иметь на плоскости три различные точки, не лежащие на одной прямой;
чтобы построить окружность определенного радиуса, необходимо иметь на плоскости три точки;
чтобы треугольники были подобны, необходимо и достаточно, чтобы их углы были равны;
чтобы, достаточно, чтобы ;
чтобы , необходимо и достаточно, чтобы ;
чтобы множество A, разбить на классы, достаточно на множестве A задать отношение эквивалентности;
чтобы система n линейных уравнений была совместной, необходимо, чтобы ранги основной и расширенной матриц были равны;
Если в четырехугольнике две противоположные стороны конгруэнты и параллельны, то этот четырехугольник параллелограмм.
Если последовательность монотонна и ограничена, то она имеет предел.
Если треугольник равнобедренный, то два угла его равны.
Если каждое слагаемое суммы чисел кратно некоторому числу a, то и сумма кратна этому числу.
Если многочлен делится на , то .
Если многочлен нечетной степени с целыми коэффициентами, то он имеет хотя бы один действительный корень.
Если , , .
Если алгебраическая система группа, то операция ассоциативна.
Равные векторы имеют равные соответствующие координаты.
Диагонали квадрата равны.
если два треугольника конгруэнты, то их площади равны;
вертикальные углы равны;
в точке дифференцирования функция непрерывна;
число делится на 9, если сумма его цифр делится на 9;
параллельные прямые центрально симметричны;
если два комплексных числа равны, то равны их действительные и мнимые части соответственно;
если сумма квадратов действительных чисел a и b равна нулю, то a=0 и b= 0;
если число делится на 2 и 5, то оно делится на 10;
диагонали ромба взаимно перпендикулярны.
для того, чтобы две прямые были параллельными, необходимо, чтобы они были перпендикулярны третьей прямой;
чтобы квадратный трехчлен разлагался на множители над R, необходимо и достаточно, чтобы его дискриминант был не меньше нуля.
Занятие №2
Тема: Рассуждения. Логические задачи.
I.Ответьте на следующие вопросы:
Какие формулы логики высказываний называются логическими законами?
Дайте определение необходимых, достаточных, необходимых и достаточных условий. Приведите примеры.
Какие высказывания называются логически эквивалентными, противоречивыми, совместимыми, противоположными?
Что называется рассуждением?
Какое рассуждение называется логически корректным?
В каком случае формулу В называют логическим следствием формул (посылок) ?
Назовите законы алгебры высказываний, лежащие в основе различных методов доказательств.
Какое множество формул называется противоречивым (непротиворечивым)?
II.Выполните следующие упражнения:
Докажите, что следующие формулы являются тавтологиями (законами) алгебры высказываний:
– закон заключения;
, – закон удаления конъюнкции;
, – закон введения дизъюнкции;
– закон удаления дизъюнкции;
– закон введения двойного отрицания;
– закон удаления двойного отрицания;
– закон введения эквиваленции;
, – законы удаления эквиваленции;
– закон контропозиции;
– закон доказательства от противного;
– закон силлогизма;
– закон сложения посылок;
– закон умножения заключений.
Приведите примеры из курса школьной математики (различных курсов математики) доказательства теорем, рассуждений, основанных на правилах, соответствующих законах алгебры высказываний, которые перечислены в упражнении 1.
Сформулируйте в виде импликации или эквиваленции следующие истинные высказывания:
чтобы выполнялось A, необходимо, чтобы выполнялось B;
чтобы выполнялось A, достаточно, чтобы выполнялось B;
чтобы выполнялось A, необходимо и достаточно, чтобы выполнялось В.
Сформулируйте следующие теоремы в виде необходимого (достаточного) условия:
если два треугольника конгруэнты, то их площади равны;
вертикальные углы равны;
в точке дифференцирования функция непрерывна;
число делится на 9, если сумма его цифр делится на 9;
параллельные прямые центрально симметричны;
если два комплексных числа равны, то равны их действительные и мнимые части соответственно;
если сумма квадратов действительных чисел a и b равна нулю,
то a = 0 и b = 0;
если число делится на 2 и 5, то оно делится на 10;
диагонали ромба взаимно перпендикулярны.
Вставить пропущенные слова (необходимо, достаточно, необходимо и достаточно) так, чтобы получились верные высказывания:
для того, чтобы две прямые были параллельными, …, чтобы они были перпендикулярны третьей прямой;
чтобы квадратный трехчлен разлагался на множители над R, …, чтобы его дискриминант был не меньше нуля;
чтобы функция была непрерывной в точке, …, чтобы ее предел и значение в этой точке были равны;
чтобы дифференцируемая функция возрастала на (a,b), …, чтобы ее производная на этом промежутке была неотрицательной;
чтобы сумма двух чисел была четной, …, чтобы каждое слагаемое было нечетным числом;
чтобы четырехугольник был ромбом, …, чтобы диагонали его были взаимно перпендикулярны;
чтобы углы были равны, …, чтобы их стороны были попарно параллельны;
чтобы четырехугольник был прямоугольником, …, чтобы его диагонали были равны;
чтобы плоскость α проходила через прямую a, перпендикулярно плоскости β, …, чтобы плоскости α и β были перпендикулярными;чтобы множество A было подмножеством множества B, …, чтобы они были равны;
чтобы две плоскости были перпендикулярными, …, чтобы одна из них проходила через прямую, перпендикулярную другой плоскости;
чтобы множества A и B были равны, …, чтобы множество A было подмножеством B.
Установите, верны ли следующие высказывания:
чтобы углы были смежными, достаточно, чтобы они имели общую сторону.
чтобы углы были смежными, необходимо и достаточно, чтобы две стороны их были противоположными лучами;
чтобы построить окружность, достаточно иметь на плоскости три различные точки, не лежащие на одной прямой;
чтобы построить окружность определенного радиуса, необходимо иметь на плоскости три точки;
чтобы треугольники были подобны, необходимо и достаточно, чтобы их углы были равны;
чтобы, достаточно, чтобы ;
чтобы , необходимо и достаточно, чтобы ;
чтобы множество A, разбить на классы, достаточно на множестве A задать отношение эквивалентности;
чтобы система n линейных уравнений была совместной, необходимо, чтобы ранги основной и расширенной матриц были равны
Запишите высказывания обратные, противоположные, противоположно-обратные для следующих теорем. Укажите, какие из них верны и попарно равносильны:
Если в четырехугольнике две противоположные стороны конгруэнты и параллельны, то этот четырехугольник параллелограмм.
Если последовательность монотонна и ограничена, то она имеет предел.
Если треугольник равнобедренный, то два угла его равны.
Если каждое слагаемое суммы чисел кратно некоторому числу a, то и сумма кратна этому числу.
Если многочлен делится на , то .
Если многочлен нечетной степени с целыми коэффициентами, то он имеет хотя бы один действительный корень.
Если , , .
Если алгебраическая система группа, то операция ассоциативна.
Равные векторы имеют равные соответствующие координаты.
Диагонали квадрата равны.
Доказать, что формула В – логическое следствие посылок .
, , ;
, , ;
, , ;
, , ;
, , .

Выяснить, является ли формула В логическим следствием посылок .
, , ;
, , ;
, , ;
, , ;
, , ,;
, , ;
, , ;
, , , ;
, , ;
, , .
Найдите все следствия из посылок:
, ;
, ;
, ;
, ;
, ;
, ,
, ;
, ;
, ,;
,,.
Исследовать противоречивость следующих множеств формул.
, , ;
, ;
, ;
, ;
, , ;
, , ;
, ;
, ,;
, , ;
, , , .
Проверить, правильны ли следующие рассуждения:
Если студент много занимается, то он успешно сдает экзамен. Следовательно, студент, получивший на экзамене неудовлетворительно, занимался мало.
Если четырехугольный ромб, то его диагонали взаимно перпендикулярны.
Данный четырехугольник ABCD – ромб. Следовательно, диагонали четырехугольника ABCD взаимно перпендикулярны.
Для того, чтобы быть допущенным к экзаменам, необходимо получить зачет по логике. Я получу этот зачет, если научусь устанавливать непротиворечивость множества формул. Я этот способ не усвоил. Следовательно, я не буду допущен к экзаменам.
Если фигура есть параллелограмм, то противоположные стороны ее параллельны и заключены между другими параллельными сторонами.Если отрезки параллельных прямых заключены между другими параллельными прямыми, то они равны. Следовательно, если фигура параллелограмм, то противоположные стороны его равны.
Если из вершины прямого угла треугольника опустить перпендикуляр на гипотенузу, то образуются два треугольника, y которых два угла соответственно равны. Если в двух треугольниках два угла равны, то треугольники подобны.Если два треугольника подобны, то сходственные стороны их пропорциональны. Следовательно, если из вершины прямого угла треугольника опустить перпендикуляр на гипотенузу, то отрезки гипотенузы пропорциональны прилежащим катетам.
Если два числа равны, то равны и их кубы. Числа m и n равны. Следовательно, равно .
Если α и β – вертикальные углы, то они равны. Угла α и β – не вертикальные.
Углы α и β – противоположные углы параллелограмма. Следовательно, если α и β противоположные углы параллелограмма, то они равны.
В треугольнике ABC перпендикуляр AM, опущенный из вершины угла А на сторону ВС, делит угол А пополам. Следовательно, в треугольнике АВС АМ является высотой и биссектрисой.
Число a кратно 3 и 5. Следовательно, число а делится на 5
Число a равно , где . Следовательно, число а, натуральное и рациональное.
В рассматриваемых четырехугольниках диагонали в точке пересечения делятся пополам или взаимно перпендикулярны. Установлено, что диагонали ABCD не делятся пополам. Следовательно, диагонали четырехугольника ABCD взаимно перпендикулярны.
Число a равно 4. Следовательно, не верно, что
Неверно, что АМ не является биссектрисой угла А. Следовательно, АМ – биссектриса угла.
Параллельные прямые центрально симметричны и, обратно, центрально-симметричные прямые параллельны. Следовательно, прямые центрально симметричны в том и только том случае, когда они параллельны.
Два комплексных числа равны, если и только, если равны их действительные и мнимые части соответственно. Следовательно, если два комплексных числа равны, то равны их действительные и мнимые части соответственно.
Обозначим через А множество всех простых чисел. Предположим, что А конечно, т.е существуют такие простые числа , что . Легко видеть, что число имеет простой делитель не равный ни одному из чисел . Таким образом, . Следовательно, множество простых чисел бесконечно.
Если в треугольнике два угла равны, то треугольник равнобедренный. Кроме того, равнобедренный треугольник будет и в том случае, если две его стороны равны. Следовательно, чтобы треугольник был равнобедренным, достаточно, чтобы два угла или две его стороны были равны.
Известно, что каждый из двух персонажей А и В является рыцарем, либо лжецом. Выясните, кто есть кто, если А высказывает следующее утверждение:
«По крайней мере один из нас лжец».
«Я лжец, а В не лжец».
«Или я лжец, или В рыцарь».
Известно, что каждый из А, B, C является либо рыцарем, либо лжецом. Установите, можно ли определить, кто есть кто по следующим высказываниям.
А: «Мы все рыцари».
В: «Ровно один из нас рыцарь».
Ключ от замка спрятан в одной из трех шкатулок (черной, белой, красной), на крышках которых сделаны надписи:
на черной: « ключ не в белой шкатулке»;на белой: «ключ не в этой шкатулке»;
на красной: «ключ в этой шкатулке».
В какой шкатулке ключ, если известно, что из трех надписей на крышках, по крайней мере, одна истинна и, по крайней мере, одна ложна?
Студент после сдачи трех экзаменов: алгебры, геометрии, математического анализа высказал следующие утверждения:
Я сдал, по крайней мере, один экзамен на отлично. Если я сдал на отлично геометрию, а не алгебру, то я так же сдал на отлично и математический анализ.
Я сдал на отлично математический анализ и алгебру, либо не сдал на отлично ни одного из них. Если я сдал на отлично алгебру, то я также сдал на отлично и геометрию
Какой предмет он сдал на отлично?
Индивидуальные задания
Задание 1
Проверить корректность рассуждений:
Для того чтобы быть допущенным к экзаменам, необходимо получить зачёт по логике. Я получу этот зачёт, если научусь проверять правильность рассуждений с помощью алгебры высказываний. Я не понял этот способ.Следовательно, я не буду допущен к экзаменам.
Если человек говорит неправду, то он заблуждается или сознательно вводит в заблуждение других. Этот человек говорит неправду, но явно не заблуждается. Следовательно, он сознательно вводит в заблуждение других.
Если человек удовлетворён работой и счастлив в семейной жизни, то он не жалуется на судьбу. Этот человек жалуется на судьбу. Следовательно, либо он удовлетворён работой, но не счастлив в семейной жизни, либо счастлив в семейной жизни, но не удовлетворён работой.
Если данное явление психическое, то оно обусловлено внешним воздействием на организм. Если оно физиологическое, то оно также обусловлено внешним воздействием на организм. Данное явление не психическое и не физиологическое. Следовательно, оно не обусловлено внешним воздействием на организм.
Я пойду или в кино, на новую кинокомедию, или на занятия по логике. Если я пойду в кино, то я от всей души посмеюсь. Если я пойду на занятия по логике, то испытаю большое удовольствие от следования по путям логических рассуждений. Следовательно, или я от всей души посмеюсь, или испытаю большое удовольствие от следования по путям логических рассуждений.
Если Антон ляжет сегодня поздно, то утром он будет в нерабочем состоянии. Если он ляжет не поздно, то ему будет казаться, что он много времени теряет бесполезно. Следовательно, или Антон будет в нерабочем состоянии, или ему будет казаться, что он много времени теряет напрасно.
Если фирма B не будет выпускать новую продукцию, то и фирма A не будет её выпускать. Если же фирма B будет выпускать новую продукцию, то её же будут выпускать и фирмы A и C. Следовательно, фирма C будет выпускать новую продукцию, если это будет делать фирма A.
Для того чтобы сдать экзамен, мне необходимо достать учебник или конспект. Я достану учебник только в том случае, если мой приятель не уедет. Он уедет, только если я достану конспект. Следовательно, я сдам экзамен.
Если философ – дуалист, то он не материалист, если философ диалектик, то он не метафизик. Он материалист или метафизик.Следовательно, он не дуалист или не диалектик.
Если завтра будет снег, то я надену тёплую куртку, если рукав будет починен. Завтра будет снег, а рукав не будет починен.Следовательно, я не надену тёплую куртку.
Если кража совершена "по наводке", то у преступника был сообщник, а если был сообщник, то налицо преступная группа. Если же преступление совершено группой, то это — преступление с отягчающими обстоятельствами. Значит, если кража совершена "по наводке", то она — с отягчающими обстоятельствами.
Если N хороший адвокат, то он выиграет это дело. N выиграл это дело. Значит, он хороший адвокат.
Лекция по логике может быть содержательной или занимательной. Если лекция содержательна — ее конспектируют, но не слушают, а если занимательна — ее слушают, но не конспектируют. Значит, лекции по логике конспектируют, но не слушают или слушают, но не конспектируют.
Если лекции не интересны, то их плохо посещают. А когда лекции плохо посещают — учебная часть проверяет посещаемость. Если же учебная часть проверяет посещаемость, то ее инспектора перегружены работой. Значит, если лекции интересны, то инспектора учебной части не перегружены работой.
Человек или трус, или он протестует против незаконного обращения. Если человек не трус, то он отстаивает свои убеждения. Если человек не протестует против незаконного обращения, то он заслуживает такого обращения. Значит, или человек не отстаивает свои убеждения, или он не заслуживает незаконного обращения.
У вас может быть либо социализм, либо свободная экономика. Но вы не достигли социализма. Значит, у вас свободная экономика.
Если вы будете говорить правду, люди проклянут вас, а если будете лгать, то вас проклянут боги. Но вы можете только говорить правду или лгать. Значит, вас проклянут боги или люди.
На встрече присутствовали выпускники прошлых лет, преподаватели факультета, студенты. N — выпускник 2002 года. Значит, он не преподаватель факультета и не студент.
Чтобы быть допущенным к экзаменационной сессии, достаточно сдать все зачеты. N не допущен к экзаменационной сессии. Значит, он не сдал зачеты.
В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то государственные расходы на общественные нужды сократятся. Значит, если повысят пошлины, то государственные расходы на общественные нужды не сократятся.*
Если бы он ей не сказал, она ни за что бы не узнала. А не спроси она его, он бы и не сказал. Но она узнала. Значит, она его спросила.
Если он принадлежит к нашей компании, то он храбр и на него можно положиться. Он не принадлежит к нашей компании. Значит, он не храбр или на него нельзя положиться.
Профсоюзы штата будут продолжать поддерживать губернатора, если он подпишет данный билль. А фермеры окажут ему поддержку, если он наложит на него вето. Губернатор либо не подпишет билль, либо не наложит на него вето. Значит, губернатор потеряет либо поддержку профсоюзов, либо поддержку фермеров.
Если не знаешь весь курс логики, то экзамен не сдашь. А если пропускаешь занятия, то не знаешь весь курс. Значит, если студент сдал экзамен по логике, то он не пропускал занятия.
Если он автор этого слуха, то он глуп или беспринципен. Он не глуп и не лишен принципов. Значит, не он автор этого слуха.
Если погода будет хорошей, то мы поедем за город завтра, а в противном случае — в следующее воскресенье. Погода хорошая. Значит, в следующее воскресенье мы не поедем за город.
Или этот предмет не сложен, или экзаменатор снисходителен. Если этот предмет интересен, то он сложен. Экзаменатор не снисходителен. Значит, этот предмет неинтересен.
Если цены возрастут, то политическая ситуация обострится, а если не возрастут, увеличится дефицит. Мы не допустим обострения политической ситуации. Значит, увеличится дефицит.
Если тело движется, то либо движение происходит в том месте, где тело находится, либо оно происходит там, где тела нет. Но движение не может происходить ни там, где тело находится, ни там, где тела нет. Значит, тело не может двигаться.
Чтобы сдать экзамен по логике, достаточно знать тему "Умозаключение", а знать эту тему можно только в том случае, если знаешь предыдущие темы. М. не знает предыдущих тем. Значит, он не может сдать экзамен по логике.
Задание 2
Доказать, что формула В – логическое следствие посылок .

варианта Формулы:
, , ;
, , ;
, , ;
, , ;
, , .
Выяснить, является ли формула В логическим следствием посылок .

варианта Формулы:
, ,
, ,
, ,
, ,
, , ,
, , ;
, , ;
, , , ;
, , ;
, , .
Найдите все следствия из посылок:

варианта Формулы:
, ;
, ;
, ;
, ;
, ;
, ,
, ;
, ;
, ,;
,,.
Занятие №3
Тема: Алгебра предикатов.
I.Ответьте на следующие вопросы.Дайте определение n-местного предиката. Приведите примеры.
Что называется множеством истинности предиката?
Какие предикаты называются равносильными?
Дайте определение тождественно-ложного, тождественно-истинного, выполнимого предиката.
Дайте определения кванторов (существования , всеобщности ).
Какие операции можно выполнять в логике предикатов?
Что называется формулами алгебры предикатов?
Определите понятия связной и свободной переменных. Какие формулы называются замкнутыми?
Какие формулы логики предикатов называются равносильными? Запишите основные равносильности алгебры предикатов.
Дайте определения приведенных и предваренных нормальных формул алгебры предикатов.
II.Выполните следующие упражнения:
Установите, какие из следующих предложений являются предикатами, а какие - высказываниями:
;
, ;
, ;
;
, ;
, ;
, ;
, .
Определите, какие из следующих предикатов являются тождественно-истинными на множестве действительных чисел R:
;
;
;
;
;
;
;
;
;
.
Определить множество истинности следующих предикатов, заданных на множестве :
«x – простое число»;
«»
«»;
«»;
«»;
«».
Для следующих предикатов, определенных на множестве А, составить таблицу значений и определить множество истинности (ложности):
«», ;
«x делит y», ;
«», ;
«», ;
«», ;
«», ;
«», ;
«», ;
«», ;
« - четное число», .
Выписать все подформулы следующих формул:
;
;
;
.
Какие вхождения переменных являются свободными, а какие связными в следующих формулах:
;
;
;
.
Пусть предикаты N(x), С(x), P(x), П(x), Ч(x), Д(x, y) имеют соответственно смысл: x – натуральное число, x – целое число, x – простое число, x - положительное число, x - четное число, x делит y. Сформулировать смысл следующих формул логики предикатов и указать, являются ли они тождественно истинными:
∀x ( N(x) C(x));
∀x ( C(x) П(x) N(x) );
∀x (P(x) ( y (Ч(x) Д(x, y)) ) );
∀x ( Ч(x) ( y (P(x) Д(x, y)) ) ).
∃x ( P(x) Ч(x) ).
∀x ( С(x) Ч(x) Ч(x) )
∀x ( N(x) Ч(x) П(x) ).
Прочитайте следующие формулы (запишите на естественном языке) и установите их истинность (ложность) на соответствующих множествах:
, где «x делит y», ;
, где , «x делит y»,
«x – четное»;
, где «x – натуральное число»,
«x – простое число»;
, где «x - помидор»,
«x - овощ», «x - растение».
Запишите следующие предложения в виде формул алгебры предикатов, выделите в них субъекты и предикаты:
каждое рациональное число есть действительное число;
существует четное число, которое является простым;
для каждого числа х существует такое число у, что х < у.
любое рациональное число можно записать в виде конечной или периодической десятичной дроби;
Перед следующими предикатами поставьте соответствующие кванторы так, чтобы получились высказывания, истинные на множестве действительных чисел:
;
;
;
;
;
;
Для следующих формул установите их истинность (ложность) на множестве А, если:
«», ;
«», ;
«», ;
«», ;
«», ;
Пользуясь кванторами, запишите четыре вида высказываний относительно одних и тех же свойств P и Q, различающихся характером общности:
общеутвердительное – «все P суть Q»;
частноутвердительное – «некоторые P суть Q»;
общеотрицательное – «ни одно P не суть Q»;
частноотрицательное – «некоторые P не суть Q».
Пусть , где N – множество натуральных чисел, , .
запишите формулу с одной свободной переменной x, истинную в m тогда и только тогда, когда:
;
;
x – простое число
;
;
.
запишите формулу с двумя свободными переменными x и y, истинную в m тогда и только тогда, когда:
;
;
;
x делит y.
запишите формулу с тремя свободными переменными x, y, z, истинную в m тогда и только тогда, когда:
;
;
.
запишите замкнутую формулу
коммутативность сложения;
ассоциативность сложения;
дистрибутивность умножения относительно сложения;
коммутативность умножения;
ассоциативность умножения;
бесконечность множества простых чисел;
то, что всякое четное число, большее 2, есть сумма простых чисел;
то, что уравнение имеет в точности два различных корня;
то, что система уравнений , не имеет решения;
то, что для всякого числа существует строго большее число.
Выполнимы ли следующие формулы:
;
;
;
;
;
;
;
;
;
.
Являются ли следующие формулы тождественно истинными (ложными), выполнимыми:
;
;
;
;
;
;
;
;
;
.
Доказать тождественную истинность следующих формул:
;
;
;
;
;
;
;
;
;
;
.
Для следующих формул найти равносильную им приведенную форму:
;
;
;
;
;
;
;
;
;
.
Привести к пренексной нормальной форме следующие формулы:
;
;
;

;
;
;
;
;
.
Индивидуальные задания
Задание 1
Найти множество истинности предиката, заданного на множестве А.
«», ,
«»; ,
«x делит y», A=Z;
«y делит x», где A=N,
«x – четное»; A=Z;
«x – натуральное число»,
«x – целое число»;
«x - помидор», A={x/x - овощ}
«x - овощ», A={ x/x - растение}
«», A={1,2,…,12}
«», A={1,2,…,13}
«»,; A={1,2,…,15}
«», A={1,2,…,100}
«»,; A={1,2,…,20}
«»,; A={1,2,…,19}
«»,; A={1,2,…,12}
«»,. A={1,2,…,120}
«»,A={1,2,…,32}
«»;A={1,2,…,18}
«»,; A={1,2,…,17}
«»,; A={1,2,…,55}
«»,; A={1,2,…,16}
«»,; A={1,2,…,65}
«x делит y»,; A={1,2,…,75}
«»,; A={1,2,…,10}
«x делится на y»,; A={1,2,…,15}
«»,; A={1,2,…,10}
«»,; A={1,2,…,105}
«»,. A={1,2,…,15}
Задание 2
Изобразите на координатной прямой множества истинности
предикатов, заданных на R. Является ли данный предикат: а) тождественно
истинным; б) тождественно ложным?
х>2;
|х|=1;
|х|<1;
|х|>1;
|х—2|>1;
|х+3|<1;
х2+2х+1 =0;
х2+6х+9>0;
х2+6х—16 QUOTE 0
х2/х = х.
х = у;
х = 2у;
x2 + x/2=l;
у = |х|;
у>х2;
у = 1/х;
(х2—у2)/(х—у) = х+у.
х2+2х+3 =0;
х2+6х+3>0;
х2+6х—9 QUOTE 0
х2/х = х.
х = 2у;
х = 3у;
x2 + x/2=2;
у = |х|-1;
у>2х2;
у = 3/х;
(х2—у2)/(х—у) = х+у.
Задание 3
Прочитайте следующие формулы (запишите на естественном языке) и установите их истинность (ложность) на соответствующих множествах:
, где , «», «»;
, где «x делит y», ;
, где , «x делит y», «x – четное»;
,«x – натуральное число»,«x – целое число»;
, где «x – целое число», «x делит y»;
, где ;
, где ;
, где ;
, где ;
, где
,«x – натуральное число»,«x – целое число»;
, где «x – целое число», «x делит y»;
, где ;
, где ;
Пусть x, y, z – произвольные прямые плоскости α;
«x пересекает у»
«x параллельна у»
«x перпендикулярна у»
«x принадлежит плоскости α»
Прочитайте следующие формулы (запишите на естественном языке) и установите их истинность (ложность):
;
;
;
;
;
;
;
;
;
.
;
;
;
;
Задание 4
Запишите следующие предложения в виде формул алгебры предикатов, выделите в них субъекты и предикаты:
для любых действительных x, y, z, если и , то ;
для любых действительных x, y, если и , то ;
прямые х и у в пространстве параллельны или пересекаются, или скрещиваются;
диаметр больше хорды;
для всяких чисел x, y, z, если , то ;
для всякой прямой х плоскости α существует параллельная прямая у, лежащая в этой же плоскости;
всякое натуральное число, большее 1, простое или составное;
любое действительное число можно записать в виде бесконечной десятичной дроби;
любые две непараллельные плоскости пересекаются;
любая система линейных однородных уравнений совместна.
Используя предикаты:
- «я вижу предмет x в момент времени t»,
- «я беру предмет x в момент времени t»,
- «момент времени предшествует моменту времени » ,
Запишите в виде формул алгебры предикатов следующие высказывания:
я всегда что-то вижу;
иногда я ничего не вижу;
существуют предметы, которые я никогда не вижу;
я вижу каждую вещь в некоторый момент времени;
если я вижу предмет, то я тут же его беру;
если я вижу предмет, то я беру его спустя некоторое время;
если я беру предмет, не видя его до этого, то через некоторое время я вижу его,
но не беру;
не существует предметов, которые я никогда не беру;
я беру всякий предмет, который я еще не взял до этого;
некоторые вещи, которые я видел ранее, я всегда вижу вновь, спустя определенное время;
существуют предметы, которые я всегда вижу.
Запишите с помощью формул алгебры предикатов следующие высказывания:
существует не более чем один x такое, что F(x);
существует, по крайней мере, два элемента x и y, такие что F(x) и F(y);
существует один и только один x, такой, что F(x);
существует не более двух элементов x и y, таких, что F(x) и F(y);
существует два и только два элемента x и y, таких, что F(x) и F(y).
существует, по крайней мере, два элемента x и y, такие что F(x) и F(y);
Задание 5
Используя предикаты:
x – точка;
x - прямая;
x - плоскость;
x лежит на у,
Запишите в виде формул алгебры предикатов следующие предложения:
через каждые при точки, не лежащие на одной прямой, можно провести единственную плоскость;
через каждый две точки можно провести прямую, если эти точки различные, то прямая единственная;
определение параллельных прямых;
определение параллельных плоскостей;
через точку, не лежащую на данной прямой, можно провести на плоскости не более одной прямой, параллельной данной;
какова бы ни была прямая, существуют точки, принадлежащие этой прямой, и точки, не принадлежащие ей;
две различные прямые либо не пересекаются, либо пересекаются в одной точке;
если две различные прямые имеют общую точку, то через них можно провести плоскость, и притом только одну;
через прямую и не лежащую на ней точку можно провести плоскость, и притом только одну;
определение скрещивающихся прямых.
Запишите в подходящей сигнатуре определения:
предела числовой последовательности;
непрерывности функции на [a,b];
равномерной непрерывности функции на [a,b];
непрерывности (разрывности) функции в точке;
совместности (несовместности) системы уравнений ;
отношения эквивалентности;
равносильности уравнений и ;
пересечения (объединения) множеств;
пустого (единичного) множества;
наименьшего (минимального) элемента;
наибольшего (максимального) элемента.
полугруппы;
коммутативной группы;
кольца;
группы;
коммутативного кольца;
поля;
частично упорядоченного множества;
линейно упорядоченного множества.
Задание 6
Перед следующими предикатами поставьте соответствующие кванторы так, чтобы получились высказывания, истинные на множестве действительных чисел:
;
;
;
;
;
;
;
;
;
;
;
.
Для следующих формул установите их истинность (ложность) на множестве А, если:
«», ;
«», ;
«», ;
«», ;
«x делит y», ;
«», ;
«x делится на y», ;
«», ;
«», ;
«», .
Для следующих формул установите их истинность (ложность) на множестве А, если:
«», ;
«», ;
«», ;
«», ;
«x делит y», ;
«», ;
«x делится на y», ;
«», ;
«», ;
«», .
Занятие №4
Тема: Исчисления высказываний.
I.Ответьте на следующие вопросы:
К какому типу математических теорий относятся исчисления высказываний?
Каким образом определяется формальная аксиоматическая теория?
Какие аксиоматизации исчисления высказываний вам известны?
Дайте определение непосредственной выводимости формулы по правилу вывода.
Что называется выводом формулы в формальной теории? Что называется теоремой
Какова связь между формулами алгебры высказываний и исчисления высказываний?
Дайте определение полноты исчисления высказываний.
Какая система аксиом исчисления высказываний называется независимой?
Дайте определение непротиворечивости исчисления высказываний.
Сформулируйте теорему дедукции.
Запишите правило резолюций для исчисления высказываний
Приведите алгоритм опровержения методом резолюций.
II. Выполнить упражнения.
Рассмотрим один из возможных вариантов построения исчисления высказываний (обозначим его L1 ).
Алфавит:
- пропозициональные переменные;
- логические символы;
- технические символы.
Правило построение формул:
всякая пропозициональная переменная – формула;
если А и В – формулы, то - формулы;
других формул нет.
Аксиомы. Пусть А, В, С – произвольные формулы, тогда следующие формулы являются аксиомами:
;
;
;
;
;
;
;
;
;
;
.
Правило вывода - Modus Ponens
M.P.В данном исчислении построить вывод следующих формул:
;
;
;
Пользуясь теоремой дедукции построить вывод следующих формул:
;
;
;
Доказать, что:
А ,В |— АВ;
А |—( В→А);
А |—( В А);
¬А ¬В |— ¬(АВ) ;В |—( АВ);
А→(В→С) |— (АВ) →С (правило соединения посылок);
А→В, В→С |— А→С (правило разъединения посылок);А (В→С) |— А→(В→С) (правило силлогизма) ;А→ (В→С) |—( В →(А →С)) (правило перестановки посылок);
А, В |— А↔В;
4. Доказать методом резолюций:
(A&B →C), (C&D →¬ M), ( ¬N →D&M) |— (A&B →N) ;
(A →B)&(C →D), (D&B→ M), ¬M|—(¬A ∨¬C) ;
((¬ A ∨¬ B∨ ¬ A& ¬ B) → C), ((A ∨B ∨A&B) →¬C)|—(C →¬A).
Индивидуальные задания
Задание 1
В исчислении L1 п. II построить вывод следующих формул:
№ варианта ;
;
;
;
;
;

Пользуясь теоремой дедукции построить вывод следующих формул:
№ варианта




Доказать, что в исчислении высказываний L2.
.
№ варианта формула II + III = IIIII выводима
формула I + I = I не выводима
Доказать, что в исчислении L4 имеют место следующие утверждения:
№ варианта А → (B → C) | — B → (A → C)
А→ (B → C) ,А ,В| — C
А→В| — С∨А→С∨В
| — (А→В) →((С→А)→(С→В))
С→А, А→В| — С→В
| — ¬В→(В→С)
| — ¬В→¬¬В→С
Доказать, что в исчислении L5 справедливы утверждения.
№ варианта А→В,В→С| — ¬ (¬С&А)
| — ¬ (¬А&А)
| — ¬ ¬А→А| — ¬ (А&В)→(В→¬ А)
Доказать, что в исчислении L6 справедливы утверждения.
№ варианта | — (А→В) →((С→А)→(С→В))
С→А, А→В| — С→В
| — ¬В→(В→С)
| — ¬В→¬¬В→С
Задание 2
Проверить, используя правило резолюций
(A→B), (C→D), (B→¬D) ,C |⎯ (¬A∨¬D)
(A→B), (C→B) ,(B→D), ¬D |⎯ (¬A&¬C)
(A→B), (C→¬B), (¬C&D) |⎯ A
(A→B), (D→C), ¬B ,¬C |⎯ ¬( A∨D)
(A→B), (C→¬B), (C&¬D) |⎯ ¬ (¬A→D)
(A→B) ,(B→C) ,(C→D) ,A&B |⎯ B&D
(A→B), (D→C), ¬(B∨C) |⎯ (¬A&¬D)
(A→B), (B→C) ,(D→C) ,(A∨D) |⎯ (C∨D)
4 (A→B), (B&D →C) ,(A&D) |⎯ C
(A→B), (A→(B→C)), (A&D) |⎯ C
(A→B), (C→B) ,(D→(A∨C)) ,D |⎯ B
(A→B), (B→C), (C→D), A&B |⎯ B&D
(A→(B→C)), (¬D∨A), B |⎯ (¬D∨C)
(A→(B→C)) ,(D∨A) ,B, D |⎯ C
(A→(B→C)), (A→B) ,A&D |⎯ C&D
(A→(B→C)), (¬ D∨A) ,B |⎯ (D∨C)
(A→(B→C)), (⎤ D∨A), B |⎯ (D→C)
(A→(B→C)) ,((A→C)→D), ¬D |⎯ ¬B
(B→A), (B→(A→C)), B&D |⎯ C
(B→A), (B→(¬A∨C)), (B&D) |⎯ C&D
(B→A), (A→C), (D→C) ,(B∨D) |⎯ (C∨D)
(B→(A→C)), (B→A), (C→D), ¬D |⎯ ¬B
(¬A∨B), (C∨¬B) ,(¬С&¬D) |⎯ ¬(A∨D)
(¬A∨¬B) ,(C→A), (B∨¬D) |⎯ (¬C∨¬D)
(¬A∨B) ,(C∨¬B), (A∨D) ,¬D |⎯ C
(¬A∨¬B), (C→A), B&D|⎯D→C
(A∨B) ,(A→C), (B→D) ,¬C |⎯ D
(A∨B), (C→ B), ¬(C→B) |⎯ ¬(¬A→B)
(A↔B), (A→(B∨C)), (D∨B) |⎯ (¬C→D)
(A&B→C) ,(¬D∨¬C), D |⎯ ¬A∨¬B)
Приложение
Исчисление высказываний L2.
Список термов исчисления: {I, +, =}
Правила образования формул:
а) I - формула;
б) если - формула, то I - также формула;
в) если и - формулы, то + и = также формула.
Задана единственная аксиома I+I = II и
два правила вывода: а) если 1+I = 2 – выводимая формула, то 1I+I = 2I также выводимая формула; б) 1+2 = 3 – выводимая формула, то 1+2I = 3I – также выводимая формула.
Исчисление высказываний L3 (исчисление Лукасевича).
Множество термов состоит из бесконечного числа букв и знаков , .
Правила образования формул:
а) все буквы есть суть формулы;
б) если - формула, то - также формула;
в) если и - формулы, то также формула.
Система аксиом следующая:
(A B) ((B C) (A C));
(A A) A;
A (A B).
Справедливы правило подстановки и правило заключения.
Исчисление высказываний L4 (Гильберт и Аккерман, 1938).

Связки: , (А В := А В).
Аксиомы:
А A А,
А А В,
А В В А,
(В С) (А В А С).
Правило: Modus ponens.
Исчисление высказываний L5 (Россер, 1953).
.
Связки: &, , (А В := (А& В)).
Аксиомы:
А А & А,
А & В А,
(А В) ( (В & С) (С & А)).
Правило: Modus ponens.5. Исчисление высказываний L6 (Клини, 1952).
Связки: , &, , .
Аксиомы:
А (В А),
(А (В С)) ((А В) (А С)),
А & В А,
А & В В,
А (В (А & В)),
А (А В),
В (А В),
(А С) ((В С) ((А В) С)),
(А В) ((А В) А,А А.
Правило: Modus Ponens.
Занятие №5

Тема: Исчисление предикатов.
I.Ответьте на следующие вопросы:
Дайте определение исчисления предикатов.
Какое исчисление предикатов называется чистым (прикладным)?
Какое исчисление предикатов называется исчислением первого порядка (высших порядков)?
Что понимают под интерпретацией исчисления предикатов?
Какие формулы исчисления предикатов называются общезначимыми?
Как определяется полнота исчисления предикатов?
Дайте определения логического следствия и логической эквивалентности.
Сформулируйте задачу автоматического доказательства теорем.
Сформулируйте принцип «доказательства от противного»
Приведите алгоритм сведения формул к предложениям.
Запишите правило резолюций для исчисления предикатов.
Приведите алгоритм опровержения методом резолюций.
Рассмотрим один из возможных вариантов построения исчисления
предикатов
Алфавит:
- предметные переменные;
- предметные константы;
- символы (буквы) n-местных предикатов;
- символы (буквы) n-местных функция;
- логические символы;
- технические символы.
Слово – конечная последовательность букв алфавита.
Терм:
всякая предметная переменная и константа есть терм;
если - n-местный функциональный символ и - термы, то слово - терм;
никаких термов, кроме построенных по пп. а) и б), нет.
Атомарная формула – это слово , где - n-местный предикатный символ, а - термы.
Формула:
атомарная формула есть формула;
если А и В – формулы, то слова - формулы;
никаких формул, кроме построенных по пп. a) и б) нет.
Понятия вывода и выводимой формулы определяются аналогично соответствующим понятиям для исчисления высказываний.
Аксиомы:
;
;
;
;
;
;
;
;
;
;
;
;
.

В схемах аксиом 1-11 A, B, C – любые формулы; В схемах аксиом 12-13 A(x) – формула, t – терм, свободный для x в A(x), A(t) – формула, полученная из A(x) заменой всех свободных вхождений x на t.
Правила вывода:
(modus ponens);
(- введения);
(- удаления);
причем, в правилах (2) и (3) x не входит свободно в A, a y не входит свободно в B(x).
II.Выполните следующие упражнения:
Доказать следующие правила:
(переименование свободных переменных), где все свободные вхождения x в A(x) не содержатся в области действия квантора по y;
(переименование связных переменных);
(переименование связных переменных);
В правилах б) и в) A(x) не содержит свободного вхождения y и свободные вхождения x не входят в область действия квантора по у.
( - удаление);
( - введение);
В правилах г) и д) t – терм свободных для x в A(x), A(t) – формула, полученная из A(x) заменой всех свободных вхождений x на t.
( - введение), где x не входит свободно в формулы из Г;
( - удаление), где x не входит свободно ни в формулу из Г, ни в формулу и B;
(силлогизма);
(контропозиции).
Построить вывод следующих формул:
;
;
;
;
;
;
;
;
;
.
Доказать, что:
;
;
, для некоторого терма t свободного для x в A(x);
, для любого терма t свободного для x в A(x).
Пусть A не содержит x свободно. Доказать, что:;
;
;
;
;
;
;
;
;
;
Выводимы ли в исчислении предикатов следующие формулы:
;
;
;
;
;
;
;
;
;
.
Свести к предложениям следующие формулы:

;


;
;
;
;
Индивидуальные задания
1) Свести к предложениям следующие формулы:
2) выполнить унификацию дизъюнктов.

№варианта Формула
∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))→ A(x)
∀x(B(x)→∃z(A(z)))&∃y(A(z)→C(y))→ ¬C(y)
∀x(A(x)→∃y(B(y)))→∃y(¬A(x)∨¬C(z)∨B(y))
∀x(A(x)→∃z(C(z)))&∀y(C(z)→B(y))→(A(x)→B ∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z) ∀x(A(x)→∃y(B(y)→C(z)))→∀z(A(x)&B(y)→C(z) ∀x(A(x)→B(z))&∀y(C(y)→A(x))→∃z(C(y)→B(z) ∀x((A(x)→B(y))→∀y((C(y)∨A(x)))→C(y) ∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))→(A(x) ∀x(A(x)→B(y)&A(x)→∀y(B(y)→C(z)))→(A(x) ∀x(A(x)→∃z(B(y)→C(z)))→∀y(B(y)→(A(x)→C(x)) (∀x(A(x))→∃z(B(z)))→∀z((B(x)→C(z))→(A(x) (∃x(¬A(x))→∀z(¬B(z)))→(¬B(x)∨A(x))
(∀x(A(x))→∀y(B(y)))→∃y(C(y)&A(x)→C(y)&B ∀x(¬A(x)→∃y(B(y)))→(¬B(y)→A(x))
∀x(B(x)→∃z(A(z)))&∃y(A(z)→C(y))→(¬C(y) ∀x(A(x)→∃z(C(z)))&∀y(C(z)→B(y))→(A(x)→B ∀x(¬A(x)→∃y(¬B(y)))→(B(y)→A(x))
∀x(A(x)→B(x))&∃y(B(x)→C(y))→∃z(C(y)→D(z ∀x(A(x)→B(x))&∀z(C(z)→A(x))→∃y(C(z)→B(y ∀x(B(x)→∀y(A(y)))&∀y(B(y)→(A(x)→C(z)))→
∀x(A(x)→B(y)&A(x)→∀y(B(y)→C(z)))→(A(x) ∀x(A(x)→B(x))→(∀y(C(y)→A(x))→∃z(C(z)→B1
∀x(B(x)→A(y))&(B(x)→∀y(A(y)→C(z)))→∃z(C (∃x(A(x)→B(z))→∃y(C(y)∨A(x)))→∀z(C(y)∨B(z(∀x(B(x))→∃y(A(y)))&(A(y)→∃yC(y))→(¬A(x)
((∀x(A(x))→∃x(B(x)))→∃y(A(x)∨C(y)))→(B(x)∃x(A(x)→∀y(B(y)))&(¬A(x)→∀y(B(y)))→B(y)
∀x(A(x)→∃y(B(y)))&(¬A(x)→B(x))→B(x)
∀x(A(x)→B(x))&∀z(C(z)→A(x))→∃y(C(z)→B((∃x(B(x))→∀y(A(y)))&(¬B(x)→A(y))→A(z)
(∀x(B(x))→∃z(C(z)))→(A(y)&B(x)→A(y)&C(z)∃x(A(x)→B(y))→∀y∀z((C(z)→A(x))→(C(z)→B(∀x(A(x))→∃z(C(z)))&∀y(C(z)→B(y))→A(x)
∀x(A(x))→∃y(B(y))&∀y(C(y)→∃xD(x))→(A(x)∀x(A(x)→B(y))&∀z(C(z)→A(x))→∃y(C(z)→B(z)(∀x(A(x)→∃z(B(z)))→∃y(A(x)∨C(y)))→(B(z)∨C∀x(B(x)→∀y(A(y)))&∀y(B(x)→(A(y)→C(z)))→
∀x(B(x)→A(y))&(B(x)→∀y(A(y)→C(z)))→∃z(B∀x(A(x)→B(x))→∀y((C(y)→A(x))→(C(y)→B(x∀x(A(x)→B(y))&(A(x)→∀y(B(y)→C(z)))→(A(x(∀x(B(x))→∃z(C(z)))→(A(y)&B(x)→A(y)&C(z)∃x(A(x)→B(z))→∃y((C(y)∨A(x))→∀z(C(y)∨B(z) ∀x(A(x)→B(y))&∀z(C(z)→A(x))→∃y(C(z)→B(y) ∀x(A(x)→B(x))&∃y(B(x)→C(y))&∃z(C(y)→D(z) (∀x(B(x)→∃y(A(y))))&∃y(A(x)→C(y))→¬C(y)
(∀x(A(x))→∃z(C(z)))&∀y(C(z)→B(y))→(A(x)
∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))
Занятие №6
Тема: Теория алгоритмов. Машины Тьюринга.
I.Ответьте на следующие вопросы:
Какие типы универсальных алгоритмических моделей вы знаете?
Дайте определения: машины Тьюринга, машинного слова (конфигурации), функции вычислимой (правильно вычислимой) машиной Тьюринга.
Перечислите известные вам операции над машинами Тьюринга.
Дайте определение композиции машин Тьюринга и . Сформулируйте основные теоремы.
Дайте определение разветвления машин Тьюринга , , по внутренним состояниям . Сформулируйте основные теоремы.
Что понимают под универсальной машиной Тьюринга?
Сформулируйте тезис Тьюринга.
II.Выполните следующие упражнения:
Какую функцию от одного аргумента вычисляет машина Тьюринга со следующей программой команд:
1→ R;
0→1;
1→R;
0→1;
1→ L;
0→0. 0→R;
1→1;
0→1;
1→R.Построить машины Тьюринга в алфавите выполняющие следующие операции:
В рабочую ячейку независимо от ее содержания заносит букву и останавливается;
Примененная к произвольной позиции сдвигает рабочую ячейку на одну ячейку вправо и затем останавливается, не изменяя записи на ленте;
В случае бесконечной в обе стороны ленты, примененная к произвольной позиции, сдвигает рабочую ячейку на одну влево и затем останавливается, не изменяя записи на ленте;
Машина, которая независимо от начальной позиции сдвигает рабочую ячейку на три при ячейки вправо, печатает там букву и останавливается, не внося в запись других изменений.
Как будет вести себя машина Тьюринга из упр. 1, запускаемая из положения:
0 1 1 0 1 0;
0 1 1 1 0 1 1 1 0?
Построить машины Тьюринга правильно вычисляющие функции:
;
;
;


;
;
;

;
;
.
Построить машину Тьюринга, правильно вычисляющую функцию (где )
Пусть функции f(x) и g(x) правильно вычислимы.
Показать, что функция правильно вычислима.
Пусть функции и правильно вычислимы.
Показать, что функция правильно вычислима.
Занятие №7
Тема: Частично рекурсивные функции.
I.Ответьте на следующие вопросы:
Дайте определения примитивно-рекурсивных функций. Приведите примеры.
Дайте определения примитивно-рекурсивных операторов. Приведите примеры.
Какая функция называется функцией Аккермана? Является ли она примитивно-рекурсивной?
Дайте определения частично рекурсивных, общерекурсивных функций.
II.Выполните следующие упражнения:
Доказать примитивную рекурсивность функций:
;
;
;
;
(здесь );

(здесь );



;
;
.
Какая функция получается из и с помощью схемы примитивной рекурсии:
, ;
, .
Вычислить значение функции Аккермана от 3, если А задана следующими равенствами: , где
;
;
.
Доказать, что если функция частично рекурсивная, то следующие функции частично рекурсивны:
(перестановка аргументов);
(циклическая перестановка аргументов);
(введение фиктивного аргумента);
(отождествление первых двух аргументов).
Библиография
Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учебник для втузов.- М.: Наука.Физматлит,2000.-544с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера – М: Энергоатомиздат, 1988 – 480 с.: ил.
Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. –304 с.: ил.
Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник.- М.: ИФРА-М, Новосибирск: Изд-во НГТУ, 2002.- 280с.
Вольвачев Р.Т. Элементы математической логики и теории множеств: Учеб. Пособие для мат. спец. вузов. - Мн.: изд-во «Университетское», 1986. – 112 с.: ил.
Яблонский С.В. Введение в дискретную математику. -М:Наука. Главная редакция физико-математической литературы,1979.
Горбатов В.А. Основы дискретной математики: Учебн. пособие для студентов вузов.-Высш.шк.,1986.-311с.,ил.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М: Мир,.1980.
Х.Карри Основания математической логики-М.: Мир, 1969.
Колмогоров А.Н., ФоминС.В. Элементы теории функций и функционального анализа .-М:Наука. Главная редакция физико-математической литературы,1976.
Э. Мендельсон, Введение в математическую логику, Наука, 1984.

Приложенные файлы

  • docx 8958484
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий