Математическая логика и теория алгоритмов

Размещено на http://www.allbest.ru/

Задание 1.

Доказать или опровергнуть умозаключение по заданному модусу путём построения диаграмм Эйлера.

Варианты заданий в формате: (номер фигуры силлогизма, название фигуры).

4-Ferison.

Ferison соответствует модусу силлогизма EIO (E - общеотрицательное суждение, I - частноутвердительное суждение, O - частноотрицательное суждение). При этом структура Ferison такая:

Ни одно M не есть P.

Некоторые M есть S.

Некоторые S не есть P.

Например:

E: Ни одно дерево не съедобно.

I: Некоторые деревья зелёные.

O: Некоторые зелёные вещи не съедобны.

Здесь “деревья” - M (средний термин), “съедобны” - P (больший термин), “зелёные” - S (меньший термин).

Диаграмма Эйлера для построенного нами силлогизма Ferison:

Видим, что часть объёма S исключена из объема P (по крайней мере часть, содержащаяся в M, но в нашем примере объём шире этой части - соответствующая область затемнена на диаграмме), что свидетельствует о правильности заключения.

Однако построенный силлогизм имеет 3-ю фигуру:

Здесь P - больший термин, это предикат заключения, M - средний термин, S - меньший термин, это субъект заключения. M служит в посылках для связывания S и P и отсутствует в заключении.

Таким образом, умозаключение вида “4-Ferison ” не является верным, поскольку четвёртая фигура силлогизма имеет вид:

Задание 2.

Формализовать высказывание. Получить СДНФ, СКНФ, ДНФ, КНФ.

«Неверно, что если мёд есть, то горшок становится пустым, а Винни-Пух - сытым».

Обозначим:

{есть мёд}

{горшок становится пустым}

{Винни-Пух становится сытым}

Формализуем высказывание: оборот “если …, то …” - это импликация “”, “не” или “неверно” - это отрицание высказывания ””, “а” - это конъюнкция ”” . Получаем высказывание вида:

Последовательно заполняем таблицу истинности полученной формулы (или функции ). Учитываем, что отрицание меняет истинность, импликация ложна только тогда, когда из истины следует ложь, а конъюнкция истинна только в том случае, когда оба операнда истинны. Истину обозначаем единицей, ложь - нулём.

Каждый набор переменных, на котором функция принимает значение 1, определяет член (логическое произведение переменных) в СДНФ (слагаемое), причём переменная входит в этот член с инверсией (отрицанием), если в наборе она имеет значение 0. Знак логического произведения (конъюнкции ?) будем опускать для удобства, а отрицание будем помечать чертой над переменной.

Получаем СДНФ:

Каждый набор переменных, на котором функция принимает значение 0, определяет член в СКНФ (сомножитель), причём переменная входит в этот член с инверсией, если в наборе она имеет значение 1. В нашем случае функция принимает значение 0 на пяти наборах, поэтому в СКНФ будет 5 членов.

Получаем СКНФ:

Составим дизъюнктивную нормальную форму (ДНФ) из СДНФ. ДНФ может существовать не одна.

Получаем ДНФ:

Составим конъюнктивную нормальную форму (КНФ) из СКНФ. КНФ может существовать не одна.

СКНФ:

Берём 1-й и 2-й члены:

Берём 4-й и 5-й члены:

Получаем:

Теперь:

Получаем: .

Эта форма допускает ещё одно упрощение:

Окончательно, КНФ:

Задание 3.

эйлер диаграмма логика математический

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

Используем формулу для импликации: :

Обозначим:

Тогда

Получаем:

Видим, что заданная формула является общезначимой.

К этому же результату приходим, построив таблицу истинности для заданной формулы :

Докажем общезначимость формулы c помощью логического дерева. При этом пользуемся методом от противного. Пусть принимает значение “ложь” , это может быть только при:

Получили противоречие, которое доказывает что принимает только значение “истина”, т.е. заданная формула является общезначимой.

Задание 4.

Проверить аргумент методом резолюций. Получить все следствия из данных посылок.

«Если неверно, что или , то и . Не . Следовательно, или ».

Заданные посылки:

Вывод:

Пытаемся доказать истинность вывода методом от противного: пусть

Для удобства введём:

Тогда посылки: и предположение:

1. Избавляемся от импликации в первой посылке и преобразуем её:

= [снимаем двойное отрицание] =

2. Составляем КНФ:

3. Применяем метод резолюций:

Тогда: - истинно, значит - ложно, но , а входит в КНФ как истинная дизъюнкция.

Получили противоречие: одновременное выполнение противоположных событий: . Следовательно, предположение неверно. Значит вывод верный.

Получим все следствия из данных посылок. Уже учитывая, что истинно, получаем, что ложно. Тогда из первой посылки нельзя сделать никакого вывода, так как из лжи может следовать и ложь, и истина. Остаётся только вторая посылка: (“не ). Её можно переформулировать в виде : ”Неверно, что ”.

Размещено на Allbest.ru