Лабораторная работа №4. Машина Тьюринга

Эта лабораторная работа рассчитана на использование программной системы – интерпретатора машины Тьюринга. Порядок действий при этом следующий. Чтобы приступить к выполнению работы необходимо запустить систему с помощью кнопки «Алго»; выбрать в главном меню пункт "Интерпретатор"; затем выбрать пункт "Машина Тьюринга". Вся информация о работе с системой может быть получена нажатием кнопки «Помощь».

Контрольные задания по курсу "Математическая логика и теория алгоритмов"

1. Раздел «Логика высказываний»

Задание

1. Установить, является ли данная формула тождественно-истинной.

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

3. Установить, является ли данное рассуждение правильным, (проверить, следует ли заключение из конъюнкции посылок).

Варианты индивидуальных заданий

Вариант №1

1. (P É Q) É ((Q É R) É (P É R)).

2. Он и жнец, и швец, и на дуде игрец.

3. Если человек принял какое-то решение, и он правильно воспитан, то он преодолеет все конкурирующие желания. Человек принял решение, но не преодолел конкурирующих желаний. Следовательно, он неправильно воспитан.

Вариант №2

1. (P É Q) É ((P É (Q É R)) É (P É R)).

2. Идет дождь, и идет снег.

3. Если данное явление психическое, то оно обусловлено внешним воздействием на организм. Если оно физиологическое, то оно тоже обусловлено внешним воздействием на организм. Данное явление не психическое и не физиологическое. Следовательно, оно не обусловлено внешним воздействием на организм.

Вариант №3

1. (P É R) É ((Q É R) É ((P Ú Q) É R)).

2. Он хороший студент или хороший спортсмен.

3. Если подозреваемый совершил кражу, то, либо она была тщательно подготовлена, либо он имел соучастников. Если бы кража была тщательно подготовлена, то, если бы были соучастники, украдено было бы много. Украдено мало. Значит, подозреваемый невиновен.

Вариант №4

1. (Q É R) É ((P Ú Q) É (P Ú R)).

2. Если стальное колесо нагреть, то его диаметр увеличится.

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

Вариант № 5

1. ((Q Ú (R ~ Ø P)) É (R & (P É Q))) Ú Ø R.

2. Если воду охлаждать, то объем ее будет уменьшаться.

3. Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель был запуган, то Генри не покончил жизнь самоубийством. Записка была найдена. Следовательно, Генри покончил жизнь самоубийством.

Вариант №6

1. ((P É Q) É (Q É R))& P É R.

2. Он учится в институте или на курсах иностранных языков.

3. Если философ – дуалист, то он не материалист. Если он не материалист, то он диалектик или метафизик. Он не метафизик. Следовательно, он диалектик или дуалист.

Вариант №7

1. (Q Ú (R É P)) É (R & (P É Q)).

2. Он способный и прилежный.

3. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возрастет. Безработица не возрастет. Следовательно, правительственные расходы возрастут.

Вариант №8

1. (P É Q) É ((Q É R) É (P É R)).

2. Эта книга сложная и неинтересная.

3. Если исходные данные корректны и программа работает правильно, то получается верный результат. Результат неверен. Следовательно, исходные данные некорректны или программа работает неправильно.

Вариант №9

1. (P É Q) É ((Q É R) É (P É R)).

2. Он и жнец, и швец, и на дуде игрец.

3. Если цены высоки, то и заработная плата высока. Цены высоки или применяется регулирование цен. Если применяется регулирование цен, то нет инфляции. Наблюдается инфляция. Следовательно, заработная плата высока..

Вариант №10

1. ((Q Ú (R ~ Ø P)) É (R & (P É Q))) Ú Ø R.

2. Если воду охлаждать, то объем ее будет уменьшаться.

3. Если я устал, я хочу вернуться домой. Если я голоден, я хочу вернуться домой или пойти в ресторан. Я устал и голоден. Поэтому я хочу вернуться домой.

Вариант №11

1. (P É Q) É ((Q É R) É (P É R)).

2. Если число оканчивается нулем, оно делится на 5.

3. Если завтра будет холодно, то я надену теплую куртку, если рукав будет починен. Завтра будет холодно, и рукав не будет починен. Значит, я не надену теплую куртку.

Вариант №12

1. (P É Q) É ((P É (Q É R)) É (P É R)).

2. Тело, лишенное опоры, падает на землю.

3. Если будет идти снег, машину будет трудно вести. Если будет трудно вести машину, я опоздаю, если не выеду пораньше. Идет снег, и я выеду пораньше. Значит, я не опоздаю.

Вариант №13

1. (P É R) É ((Q É R) É ((P Ú Q) É R)).

2. Иван и Петр знают Федора.

3. Если человек говорит неправду, то он заблуждается или сознательно вводит в заблуждение других. Этот человек говорит неправду и явно не заблуждается. Значит, он сознательно вводит в заблуждение других.

Вариант №14

1. (Q É R) É ((P Ú Q) É (P Ú R)).

2. Эта книга полезная и интересная.

3. Если бы он был умен, то он увидел бы свою ошибку. Если бы он был искренен, то он признался бы в ней. Однако, он не умен и не искренен. Следовательно, он или не увидит свою ошибку, или не признается в ней.

Вариант № 15

1. ((Q Ú (R ~ Ø P)) É (R & (P É Q))) Ú Ø R.

2. Этот актер играет в театре и не играет в кино.

3. Если человек является материалистом, то он признает познаваемость мира, Если человек признает познаваемость мира, то он не является агностиком. Следовательно, если человек не является последовательным материалистом, то он – агностик.

Вариант №16

1. ((P É Q) É (Q É R))& P É R.

2. Если собаку дразнить, она укусит

3. Если в мире есть справедливость, то злые люди не могут быть счастливы. Если мир есть создание злого гения, то злые люди могут быть счастливы. Значит, если в мире есть справедливость, то мир не может быть созданием злого гения

Вариант №17

1. (Q Ú (R É P)) É (R & (P É Q)).

2. Если вы владеете английским языком, вы справитесь с этой работой.

3. Если Иванов работает, то он получает зарплату. Если же Иванов учится, то он получает стипендию. Но Иванов не получает зарплату или не получает стипендию. Следовательно, он не работает или не учится.

Вариант №18

1. (P É Q) É ((Q É R) É (P É R)).

2. Если функция нечетная, то ее график симметричен относительно начала координат.

3. Если я лягу спать, то не сдам экзамен. Если я буду заниматься ночью, то тоже не сдам экзамен. Следовательно, я не сдам экзамен.

Вариант №19

1. (P É Q) É ((Q É R) É (P É R)).

2. Если число делится на 3, то сумма его цифр делится на 3.

3. Если я пойду завтра на первую лекцию, то должен буду встать рано. Если я пойду вечером на дискотеку, то лягу спать поздно. Если я лягу спать поздно, а встану рано, я буду плохо себя чувствовать. Следовательно, я должен пропустить первую лекцию или не ходить на дискотеку.

Вариант №20

1. ((Q Ú (R ~ Ø P)) É (R & (P É Q))) Ú Ø R.

2. Если слово ставится в начале предложения, то оно пишется с большой буквы.

3. Если x 0 и y 0, то x ² + y ² > 0. Если x = 0 и y = 0, то выражение (x – y):(x + y) не имеет смысла. Неверно, что x ² + y ² > 0. Следовательно, не имеет смысла выражение (x – y):(x + y).

Вариант №21

1. (P É Q) É ((Q É R) É (P É R)).

2. Иван и Марья любят друг друга.

3. Если книга, которую я читаю, бесполезная, то она несложная. Если книга сложная, то она неинтересная. Эта книга сложная и интересная. Значит, она полезная.

Вариант №22

1. (P É Q) É ((P É (Q É R)) É (P É R)).

2. Плох тот солдат, который не мечтает стать генералом.

3. Если завтра будет дождь, я надену плащ. Если будет ветер, я надену куртку. Следовательно, если не будет дождя и ветра, я не надену ни плаща, ни куртки.

Вариант №23

1. (P É R) É ((Q É R) É ((P Ú Q) É R)).

2. Если ряд сходится, то его общий член стремится к нулю.

3. Если он не трус, то он поступит в соответствии с собственными убеждениями. Если он честен, то он не трус. Если он не честен, то он не признает своей ошибки. Он признал свою ошибку. Значит, он не трус.

Вариант №24

1. (Q É R) É ((P Ú Q) É (P Ú R)).

2. Ни Иван, ни Федор не отличники.

3. Если он упрям, то он может ошибаться. Если он честен, то он не упрям. Если он не упрям, то он не может одновременно не ошибаться и быть честным. Значит, он не упрям.

Вариант № 25

1. ((Q Ú (R ~ Ø P)) É (R & (P É Q))) Ú Ø R.

2. Либо Иван, либо Петр знают Федора.

3. Если зарплату выдают вовремя, то ожидаются либо выборы, либо акция протеста. Зарплату выдали вовремя. Выборы не ожидаются. Значит, ожидается акция протеста.

Вариант № 26

1. (R É P) É ((P É Q) É (R É Q)).

2. Если составить алгоритм и написать программу, то можно решить эту задачу.

3. Если человек занимается спортом, то он здоров. Если человек здоров, то он счастлив, Этот человек занимается спортом. Значит, он счастлив.

Вариант № 27

1. ((P É Q) É (Q É R)) Ú Ø R.

2. Вечером мы пойдем на хоккей или будем смотреть его по телевизору.

3. Антон переутомился или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, он болен.

Вариант № 28

1. (P & Q É R) Ú (Q & R É Ø P).

2. Если я не выспался или голоден, я не могу заниматься.

3. Если фирма ориентирована на усиление маркетинга, то она намерена получить крупную прибыль на выпуске новых товаров. Если фирма предусматривает расширение торговой сети, то она намерена получить крупную прибыль от увеличения продаж. Фирма предусматривает усиление маркетинга или собирается расширить торговую сеть, Следовательно, она намерена получить крупную прибыль.

Вариант № 29

1. ((P ~ Q) É (Q ~ R)) Ú Ø R.

2. Если налоги не будут снижены, то мелкие производители разорятся и оставят производство.

3. Контракт будет выполнен тогда и только тогда, когда дом будет закончен в феврале. Если дом будет закончен в феврале То мы можем переехать в марте. Контракт будет выполнен, Следовательно, мы можем переехать в марте.

Вариант № 30

1. Ø (P&Q É Ø R) É Q.

2. Если наша команда не займет первое место, мы останемся дома и будем тренироваться.

3. Намеченная программа удастся, если застать противника врасплох или если его позиции плохо защищены. Захватить его врасплох можно, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Значит, программа не удастся.

2. Раздел «Логика предикатов»