Вывод: все животные в этом дворе грызут кости.

 

Представим все высказывания в дизъюнктивной форме.

 

- что и требовалось доказать

 

Задача 2.Сформулировать представленную выше задачу на языке логики предикатов и упростить полученную систему используя теоремы и тождества логики предикатов.

Тождество доказано.

 

Задача 3.Сконструировать машину Тьюринга (написать соответствующую программу) для решения следующей задачи.

На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

 

 

В состоянии q1 машина ищет правый конец числа, в состоянии q2 — пропускает знак “+”, при достижении конца последовательности — останавливается. В состоянии q3машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается.

 

 

Задача 4.Записать логическую функцию, соответствующую высказыванию:

А – «Допоздна работаешь с компьютером», В – «Пьешь много кофе», С – «Утром встаешь в дурном расположении духа», D – «Утром встаешь с головной болью». Составное высказывание «Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в дурном расположении духа или с головной болью».

 

Задача 5.Записать сложное высказывание «Если компьютер при запуске выдает ошибку при проверке оперативной памяти (A) и память установлена правильно (B), то оперативная память дефектна (C) и дефектна материнская плата (D)» логической формулой и минимизировать его, используя карту Карно.

 

 

 

В нашем случае: , , .

Значит .

 

 

Задача 6.Каждой пропозициональной форме, содержащей n различных пропозициональных букв, соответствует таблица истинности с 2n строками.

 


Составить таблицу истинности для следующей формы:

 

 

 

Задача 7.Составить рекуррентное выражение для вычисления функции (n +1)! + 2, представив функции h(n, m) и g(n).

 

 

 

 


Задача 8. Представить на языке ГСА (операторные вершины обозначить буквами А1, А2, …, Аn, а логические – буквами α1, α2, …, αm), используя рекомендуемые ГОСТом обозначения, алгоритм решения следующей задачи.

 

Найти максимальное из четырех представленных чисел A, B, C и D, не используя понятие массива.

 

Введем обозначения:

A0 – «начало»

А1 – «x = A»

А2 – «x = В»

А3 – «x = С»

А4 – «x = D»

А5 – «конец»

α1 – «x < В»

α2 – « x < С»

α3 – « x < D»

 

 

Задача 9. Представленный в предыдущем задании алгоритм перевести с языка ГСА на язык ЛСА (используя обозначения предыдущей задачи).

 

А0А1 α11А21α22А32α33А43А7


Библиографический список

 

1. Игошин В.И. Задачи и модели по математической логике и теории алгоритмов. – 2-е изд. – М.: Академия, 2006. – 304 с.

2. Тимофеева, И.Л. Математическая логика: курс лекций: учеб. пособие. – 2-е изд. – М.: КДУ, 2007.

3. Гладкий А.В. Математическая логика и теория алгоритмов. – М.: МЦНМО, 2001.

4. Зюзьков В.М, Шелупанов А.А. Математическая логика и теория алгоритмов: Учебное пособие для вузов. – 2-е изд. – М.: Горячая линия–Телеком, 2007. – 176 с.

5. Игошин В.И. Задачник-практикум по математической логике: уч. пособие. – М.: Академия, 2006.

6. Галиев Ш.И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ им. А.Н. Туполева. 2002. – 270 с.