Логика и исчисление высказываний

Часть I. Логика и исчисление высказываний.

Задание 1. Записать высказывания в виде формул и логики высказываний:

1.1. «Сегодня мы пойдем в кино или поедем кататься на лыжах».

A – пойдем в кино.

B – поедем кататься на лыжах.

Ответ:

Задание 2. Построить таблицы истинности для формул.

2.1.

Ответ:

2.2.

Ответ:

Задание 3. Доказать, что формулы являются тавтологиями.

3.1.

Ответ:

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

Задание 4. Доказать полноту (неполноту) систем булевых функций.

4.1.

Решение.

Проверим принадлежность функций классам Поста.

1.  Принадлежность классу функций, сохраняющих 0

, потому что

, потому что

2.  Принадлежность классу функций, сохраняющих 1

,потому что

,потому что

3.  Принадлженость классу функций самодвойсвеннх функций

, потому что

, потому что ,

4.  Принадлежность классу монотонных функций

, потому что не выполняется условие монотонности:

, потому что не выполняется условие монотонности:

5.  Принадлежность классу линейных функций

, потому что уже разложена в полином Жегалкина и не содержит коньюнкций.

, потому что разложение данной функции в полином Жегалкина не содержит коньюнкций:

Полученные результаты сведем в таблицу:

Так как в последнем столбце таблицы нет ни одного минуса, то согласно теореме Поста система функций не является полной.

Ответ: система — не полная.

Задание 5. Получить СДНФ для формул, затем перейти к СКНФ:

5.1.

Ответ:

1)   

2)  СДНФ =

3) 

4) 

5)  СКНФ =

Задание 6. Получить СКНФ, а затем перейти к СДНФ:

6.1.

Ответ:

1) 

2)  СКНФ =

3) 

4) 

5)  СДНФ =

Задание 7. Получить МДНФ для формулы:

7.1.

Ответ:

1)Таблица истинности для функции:

2)СДНФ =

3) Получим СкДНФ из ДНФ. Для этого пронумеруем конъюнкции и произведем их склейку:

I-II: (1)

I-III: (2)

I-IV: (3)

III-V: (4)

IV-V: (5)

(2)-(5):

(3)-(5):

СкДНФ =

4) Импликационая матрица:

Минимальное покрытие включает все конъюнкции из СкДНФ, следовательно МДНФ = и совпадает с СкДНФ

Часть I. Логика и исчисление предикатов. Автоматическое доказательство теорем.

Задание 1. Записать на языке предикатов:

1.1. Все студенты учатся.

Ответ:

— множество студентов

— множество учащихся.

Задание 2. Получить множество дизъюнктов.

2.5.

Ответ:

Избавимся от импликаций:

Перенесем знак отрицания через квантор и переименуем связанные переменные:

=

Вынесем все кванторы в начало формулы:

Проведем сколемизацию. Левее кванторов существования нет кванторов всеобщности, поэтому отбросим эти кванторы, заменив соответствующие связанные переменные константами Сколема:

Получаем множество дизъюнктов:

Задание 3. Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюций.

3.1.

A1: Все, что обладает свойством P, имеет свойство R.

A2: Все, что обладает свойством R, имеет свойство Q

Вопрос: Существует ли нечто, что не обладает свойством P или обладает свойством Q?

Решение.

Запишем аксиомы и вопрос на языке предикатов и сформулируем вопрос в форме теоремы:

A1:

A2:

Т:

Получим множество дизъюнктов из аксиом и вопроса. В первой и второй избавимся от импликации и отбросим кванторы всеобщности:

Д1:

Д2:

Применим отрицание к теореме, перенесем его за квантор и применим правило де Моргана:

=

Отбросив квантор, получим два новых дизъюнкта:

Д3:

Д4:

Сделаем вывод при помощи метода резолюций. Все дизъюнкты содержат только переменные, поэтому унификация не требуется.

Резольвента Д1 и Д3 равна , обозначим её через Д5.

Резольвента Д2 и Д4 равна , обозначим её через Д6.

Резольвента Д5 и Д6 дает пустой дизъюнкт, который является противоречием. Таким образом теорема — верна, что является положительным ответом на исходный вопрос.

Задание 4. Для данной системы аксиом доказать теорему.

4.5.

А1:

A2:

A3:

A4:

T:

Решение.

Получим дизъюнкты из аксиом:

Д1:

Д2:

Д3:

Д4:

Применим отрицание к теореме:

=

Отбросим квантор существования, заменив переменные константами сколема (слева от квантора нет кванторов всеобщности):

Получили новый дизъюнкт:

Д5:

Применим метод резолюций. Некоторые дизъюнкты содержат константы, проведем унификацию.

Унифицируем Д2 и Д3: , получаем:

Резольвента Д2 и Д3 равна – обозначим её как Д6

Унифицируем Д1 и Д6: , получаем

Резольвента Д1 и Д6 равна , обозначим её как Д7

Унифицируем Д7 и Д4:

Резольвента Д7 и Д4 равна , обозначим её через Д8

Унифицируем Д5 и Д8: , получим

Резольвента Д5 и Д8 равна .

Резолюция всех дизъюнктов множества дает дизъюнкт , который не является противоречием. Таким образом, теорема не верна.

Часть III. Теория алгоритмов.

1.1, 2.4, 3.1

Задание 1. Построить машину Тьюринга (результат представить в форме таблицы):

1.1. Прибавить 1 к целому неотрицательному числу (вычислить функцию F(x) = x + 1).
Рассмотреть задачу для машины Тьюринга с алфавитом A = {0, 1, λ} (операции выполняются в двоичной системе);

Решение.

Программа (П – переход маркера вправо, Л – переход влево, С – маркер остается на месте):

1) (начальное состояние: сканируем ленту слева направо, пропуская пустые символы)

2) (начальное состояние: если в ячейке 0 или 1 значит, встретили конец слова, переходим в состояние 2)

3) (см п. 2)

4) (состояние 2: пропускам ячейки, пока в них записано 0 или 1 и передвигаемся вправо, к началу слова)

5) (см п.4)

6) (состояние 2: пустой символ в ячейке, значит найдено начало слова, переходим состояние 3 и передвигаемся влево.)

7) (состояние 3: если в ячейке содержится 0, записываем в ячейку 1, работа МТ завершена)

8) (состояние 3: если в ячейке содержится 1, записываем в ячейку 0, передвигаемся влево.)

9) (состояние 3: если в ячейке содержится пустой символ, записываем 1, работа МТ завершена.)

Построим таблицу состояний:

Задание 2. Доказать, что функция примитивно-рекурсивна:

2.4.

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

Так и не врубился в эту хуйню. Делать не буду.

Задание 3. Построить нормальный алгоритм Маркова, который:

3.1. добавляет две единицы к входному слову, состоящему из последовательности единиц.

Решение:

Входной алфавит состоит из одного символа А = {1}. Алгоритм будет состоять из одной подстановки:

Подстановка заменяет первую встреченную в слове единицу тремя, и завершает работу. Таким образом, слово становиться длиннее на две единицы.