Исчисление высказываний и исчисление предикатов

Цель работы: Ознакомиться с исчислением высказываний. Выводимостью формул в исчислении высказываний, с понятиями предикаты, кванторы, формулами исчисления предикатов.

Порядок выполнения работы:

Практическая работа рассчитана на 2 часа аудиторных занятий, включающих в себя следующее:

1. Изучить:

- Исчисление высказываний. Аксиоматические теории. Выводимость формул в исчислении высказываний.

- Исчисление предикатов. Предикаты, кванторы.

- Формулы исчисления предикатов.

- Аксиомы исчисления предикатов. Теорема дедукции.

2. Решить упражнения к данному разделу. Выполнить каждый пункт упражнения согласно варианту. Вариант определяется как сумма двух последних цифр зачётной книжки, если количество заданий в пункте упражнения меньше, чем полученная цифра, то эта цифра делится пополам (берётся её целая часть).

3. Оформить отчет о проделанной работе в соответствии с требованиями.

4. Проработать контрольные задания СРС.

Требования к отчету:

Отчет по практической работе распечатывается в виде твердой копии и состоит из следующих пунктов:

Вариант индивидуального задания;

Результаты полученных решений заданий;

Ответы на контрольные задания СРС.

Методические указания

Под высказыванием понимают повествовательное предложение, о котором можно сказать одно из двух: истинно оно или ложно. Пусть есть множество высказываний, фраз, принимающих значение «истина» или «ложь». В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от значений «истинно» и «ложно». Высказывание – это утверждение, которое может быть только ис-

тинно или ложно. Его принято обозначать символами T (от True), или F (от

False), или соответственно, 1 (для истинного значения) или 0 (для значения

ложь). Из элементарных высказываний строятся более сложные высказывания с

помощью логических связок «НЕ», «И», «ИЛИ», «ТО ЖЕ, ЧТО»

(«ЭКВИВАЛЕНЦИЯ»), «ИЗ … СЛЕДУЕТ…». (« … ВЛЕЧЁТ…»,

«…ПОТОМУ, ЧТО…».). Эти связки называются сентенциональными. Связки

логики высказываний представляют функции истинности или функции алгебры

логики. В таб.1 представлены логические связки и их обозначения.

Таблица 1

Название Тип Обозна

чения Как читается Другие

обозначения

Отрицание Унарный не ⎯s, not, не

Конъюнкция Бинарный ∧ и &, . , and, и

Дизъюнкция Бинарный ∨ или ⎢, or, или

Импликация Бинарный → влечёт ⇒, ⊃

Эквивалентность Бинарный ⇔ ↔, ≈

эквивалентно

Отрицанием высказывания p называется высказывание p

(или ⎯p), которое истинно только тогда, когда p ложно.

Конъюнкцией высказываний p и q называется высказывание, которое истинно только тогда, когда p и q истинны., т.е. p = 1 и q = 1.

Дизъюнкцией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны, т. е. p = 0 и q =0.

Эквиваленцией высказываний p и q называется высказывание, которое истинно только и только тогда, когда значения высказываний p и q совпадают (p эквивалентно q).

Совокупность правил построения выглядит так:

• Базис. Всякое высказывание является формулой.

• Индукционный шаг. Если A и B формулы, то A, (A ∨ B), (A ∧ B),

(A→B), (A ⇔B) – формулы.

• Ограничение. Формула однозначно получается с помощью правил, опи-

санных в базисе и индукционном шаге.

Интерпретация – это отображение i, сопоставляющее каждому элементарному высказыванию p некоторое значение истинности. Интерпретацию i, заданную на множестве элементарных высказываний, можно распространить на множество формул посредством таблиц истинности.

Упражнения для выполнения:

1. Записать символически высказывания, употребляя буквы для обозначения простых высказываний. Построить таблицы истинности для каждого высказывания:

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

Необходимое и достаточное условие для жизни растений состоит в наличии питательной почвы, чистого воздуха и солнечного света.

a. Студент не может заниматься, если он устал или голоден.

b. Если Иван выиграет в лотерею, он купит компьютер и будет праздно-

вать всю ночь

c. Если он не выиграет в лотерею или не купит компьютер, то праздно-

вать всю ночь не будет

d. Если Артёму нравятся фиолетовые галстуки, то он популярен и у него

много друзей

e. Если Игорь носит желтые ботинки, то он не модный и если он не мод-

ный, то у него странные друзья.

f. Если он не удачлив, то он и не популярен

g. Он удачлив и богат, следовательно, он популярен.

h. Он читает научную литературу и любит фантастику, следовательно, он

ученый-фантаст.

i. Если он информатик, то он либо работает за компьютером, либо чита-

ет книги об ЭВМ.

j. Если он или умеет писать или читать, то он грамотный человек.

k. Для того, чтобы натуральное число a было нечётным, достаточно, что-

бы оно было простым и большим двух.

l. Необходимым условием сходимости последовательности S является

ограниченность S.

m. У меня быстродействующий компьютер и я закончу проект вовремя и

сдам экзамен.

2. Даны высказывания: p – «ему нравятся фиолетовые галстуки»; q – «он читает комиксы»; r – «у него странные друзья». Запишите высказывание, соответствующее следующему выражению: .

3. Пусть S(x) = «х – удачлив», P(x) = «х – богат». Постройте высказывание, соответствующее формуле "x(S(x) É ØP(x))?

4. Пусть S(x) = «х – удачлив», P(x) = «х – богат». Постройте высказывание, соответствующее формуле $x(S(x) & P(x))?

5. Пусть S(x) = «х – удачлив», P(x) = «х – богат». Постройте высказывание, соответствующее формуле "x(S(x) É P(x))?

6. Пусть S(x) = «х – удачлив», P(x) = «х – богат». Постройте высказывание, соответствующее формуле $x(A(x) & ØP(x))?

7. Постройте отрицание высказывания: «если стальное колесо нагреть, то его диаметр увеличится».

8. Какие из следующих формул логики предикатов являются равносильными:

"xA(x) & "xB(x) и "x(A(x)&B(x))

"xA(x) и "x(A(x))

"x$yA(x, y) и $y"xA(x, y)

"xA(x) V "xB(x) и "x(A(x) V B(x))

$xA(x) & $xB(x) и $x(A(x) & B(x))

Контрольные задания для СРС

1. Приведите пример, показывающий истинность равенств:

Ø("xA(x) = $x(ØA(x)),

"xA(x) & "xB(x) = "x(A(x)&B(x)).

2.Приведите пример, показывающий, что формулы $x"yA(x, y) и "y$xA(x, y) не равны.

3.Сформулируйте теорему дедукции, приведите пример на использование в доказательстве теоремы дедукции.

Дата добавления: 2015-07-26; просмотров: 319; Нарушение авторских прав

Мы поможем в написании ваших работ!