Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека icon

Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека



НазваниеПосылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека
страница1/4
Дата конвертации14.07.2012
Размер0,5 Mb.
ТипМетодические указания
скачать >>>
  1   2   3   4


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


Посылки: Для любых объектов x, y и z если x есть часть y и y есть часть z, то x есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека.

Заключение: Палец есть часть человека.

Министерство общего и профессионального образования РФ

_________

Санкт-Петербургский государственный


электротехнический университет

_______________________________


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

к практическим занятиям по дисциплине

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


Санкт-Петербург

1997 г.

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1
Основы логики высказываний


Цель занятия: Получение практических навыков построения формул логики высказываний, анализа их свойств и преобразования в КНФ.


Теоретические сведения

Высказыванием в логике считается любое утверждение, относительно которого можно судить о его истинности или ложности [1]. Например, утверждение "Москва - столица России" является истинным высказыванием, а "Пингвины живут в Африке" - ложное высказывание. Вместе с тем, утверждение "В созвездии Кассиопеи существует жизнь", в соответствии с приведенным определением, высказыванием не является, т.к. мы не можем в настоящее время судить о его истинности или ложности.

Высказывание, не допускающее расчленения на более простые, называется элементарным. Для обозначения элементарных высказываний принято использовать символы p, q, r, s, t, которые в логике называют пропозициональными переменными. Составные высказывания строятся из элементарных с использованием пяти логических связок:

 - отрицание, соответствует отрицательной частице «не» в утверждениях естественного языка;

& - конъюнкция, соответствует союзу «и»;

 - дизъюнкция соответствует союзу «или»;

 - импликация, соответствует союзу «если ..., то ...» ;

 - эквивалентность, соответствует слову «эквивалентно», а также часто используемым в математике словосочетаниям «тогда и только тогда» или «необходимым и достаточным условием является».

С использованием пропозициональных переменных и логических связок высказывания представляются формулами. Например, утверждение «Если идет дождь и нет зонта, то поход в кино не состоится» записывается в виде формулы (p & q)  r . Здесь пропозициональные переменные соответствуют следующим элементарным утверждениям: p - «идет дождь»; q - «есть зонт»; r - «поход в кино состоится».

Формально синтаксис логических формул определяется следующими правилами:

1. Базис: всякая пропозициональная переменная является формулой.

2. Индукционный шаг: если X и Y - формулы, то X, (X & Y), (X  Y), (X  Y), (X  Y) - также формулы.

3. Ограничение: других формул нет.

В данном определении символы X и Y являются метасимволами, они не принадлежат языку логики высказываний, а используются для обозначения произвольных формул. Если при построении формулы X формула Y используется как элемент в индуктивном правиле, то Y называется подформулой формулы X. Например, в формуле (p & q)  (r  t) можно последовательно выделить следующие подформулы: (p & q), (r  t), p, q, r, t, r. Скобки используются для указания порядка выполнения операций и могут опускаться с учетом принятого старшинства операций: , &, , , . Например, приведенная выше формула может быть записана в виде p&q  rt, а формула p  ((q & r)  s) - в виде p  q&rs.

Семантика формул определяется их свойством быть истинными или ложными, то есть принимать значение T (true) - истина, или F(false) - ложь. Интерпретировать формулу логики высказываний, значит приписать значения истинности составляющим ее элементарным высказываниям и вычислить истинностное значение всей формулы. При этом логические связки рассматриваются как функции на множестве истинностных значений (булевы функции), определенные в соответствии с табл. 1.

Интерпретация, при которой формула принимает значение Т, называется моделью этой формулы.

Формула  выполнима (непротиворечива), если она допускает хотя бы одну модель, т.е. ее можно интерпретировать со значением Т. Например, формула р & q является выполнимой.

Таблица 1

X

Y

X

X & Y

X  Y

X  Y

X  Y

F

F

T

T

F

T

F

T

T

T

F

F

F

F

F

T

F

T

T

T

T

T

F

T

T

F

F

T


Формула  невыполнима (противоречива, тождественно ложна), если она не имеет ни одной модели, то есть при всех интерпретациях является ложной. Например, формула (р&р) невыполнима.

Формула  общезначима (является тавтологией), если она истинна в любой интерпретации. Например, формула (р  р) общезначима.

Формулы равносильны (логически эквивалентны), если они имеют одинаковые таблицы истинности.

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

«Студент не допускается к экзамену тогда и только тогда, когда у него не сдана курсовая работа или есть задолженности по лабораторным работам».

Решение. Обозначим все встретившиеся элементарные высказывания пропозициональными переменными:

p - «студент допущен к экзамену»;

q - «курсовая работа сдана»;

r - «есть задолженность по лабораторным работам».

Тогда формула запишется в следующем виде: p  (q  r). Построим таблицу истинности, вычисляя сначала значения подформул (Табл. 2).

Таблица 2

p

q

r

p

q

q  r

p  (q  r)

F

F

F

F

T

T

T

T

F

F

T

T

F

F

T

T

F

T

F

T

F

T

F

T

T

T

T

T

F

F

F

F

T

T

F

F

T

T

F

F

T

T

F

T

T

T

F

T

T

T

F

T

F

F

T

F

Т. о., данная формула выполнима, т.к. имеет модели и не общезначима, т.к. имеются интерпретации, при которых она ложна. Формула имеет 4 модели.

Литерой (литералом) в логике высказываний называется любая пропозициональная переменная с отрицанием или без него. Дизъюнкт - дизъюнкция конечного числа литер. Следующие формулы являются примерами дизъюнктов: (p  q  r), t, (s  q). Любой дизъюнкт, содержащий хотя бы одну литеру, является выполнимой формулой. Единственным невыполнимым дизъюнктом является пустой дизъюнкт, то есть дизъюнкт не содержащий ни одной литеры. Поэтому его принято обозначать логической константой F.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов. Приведенной нормальной формой называется нормальная форма, в которой опущены дизъюнкты, содержащие контрарные пары (тавтологии) и повторения литер в пределах одного и того же дизъюнкта.

Любая формула может быть преобразована в логически эквивалентную ей КНФ с использованием следующего алгоритма:

1. Исключить из формулы все связки импликации и эквивалентности, используя следующие тождества:

A  B  A  B ;

A  B  (A  B) & (B  A)  (A  B) & (B  A).

2. Сузить области действия отрицаний и исключить двойные отрицания. Для этого используются законы де Моргана и снятия двойных отрицаний:

(A & B)  A  B ;

(A  B)  A & B ;

A  A.

3. Применить необходимое число раз правило дистрибутивности дизъюнкции относительно конъюнкции:

(A & B)  C  (A  C) & (B  C).

Пример. Преобразовать в КНФ следующую формулу логики высказываний: (p & q)  (q  s).

Решение. Выполним преобразования в соответствии с приведенным выше алгоритмом.

1. Исключение связки эквивалентности:

[(p & q)  (q  s)] & [(q  s)  (p & q)] =

[(p & q)  (q  s)] & [(q  s)  (p & q)].

2. Сужение области действия отрицаний и снятие двойных отрицаний:

[(p  q)  (q  s)] & [(q & s)  (p & q)] =

[(p  q  q  s)] & [(q & s)  (p & q)] =

[(p  q  s)] & [(q & s)  (p & q)].

3. Применение дистрибутивности, исключение тавтологий:

[(p  q  s)] & [(q  p&q) & (s  p &q)] =

[(p  q  s)] & [(q  p) & (q  q) & (s  p) & (s q)] =

(p  q  s) & (q  p) & (s  p) & (s q).

Получили приведенную КНФ.


Упражнения

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

а) s  (t  r);

б) q  (p  rs);

в) p  ((q & p)  (p  r));

г) p & (q  p) & ((q  p)  q);

д) (r & q  p)  t;

е) (p & q)   q;

ж) (r & t)  (p  q);

з) (q  (p & t))  ((q & t).

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

а) Если Сидоров поедет на автобусе, то его уволят с работы, если автобус опоздает.

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

в) Если «Торпедо» или «Динамо» проиграют, а «Локомотив» выиграет, то «Спартак» потеряет первое место.

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

д) Если вечером будет туман или снег, то Джон или останется дома или должен будет взять такси.

е) Либо рост инфляции эквивалентен снижению уровня жизни, либо рост производства влечет то, что уровень жизни не снижается.

ж) Если будет идти дождь или снег, то футбольный матч либо не состоится, либо его результат не будет отражать соотношение сил.

з) Если животное млекопитающее и имеет острые зубы и имеет клыки и не ест траву, то это хищник.


3. Преобразовать следующие формулы в КНФ:

а) (r & t)  (p  q);

б) (r & q & t)  (t  q  r);

в) ((p  q)  (r  p))  (q  r);

г) (q  (p  t))  ((q  t)  (q  p));

д) (r  q  p)  (t  s);

е) (p & q)  (r  q);

ж) (r & t)  (p  q).


  1   2   3   4




Нажми чтобы узнать.

Похожие:

Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека icon«Углубление лингвистических знаний. Культура речи. Фразеология.»
В текстах егэ есть задание на определение фразеологического оборота (часть А), на нахождение фразеологизма (часть В)
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconОсобенности родительской любви в исламе и христианстве
Как в христианской, так и в мусульманской религиозной литературе отмечается, что рождение детей – значительнейшая часть супружеских...
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconПлан Введение кто есть кто и что есть где, или информационное пространство бизнеса
...
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconЗакон республики татарстан
Зрт) (Ведомости Государственного Совета Татарстана, 2003, n 1, n 9 (II часть); 2005, n 10 (II часть); 2006, n 12 (I часть); 2007,...
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconКонтрольная работа 1 часть 2 часть (1) 2 часть (2) 2 часть (3) 2 часть (4) Просмотр рабт Итог Ацканов Исуф Алимович

Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconЦитатник
Цита́та это часть одного текста, вставленная, скопированная без изменений в другой текст с какой-либо целью. При этом важно, что...
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconСодержание: Первая часть
Вы, как частное лицо хотите приобрести себе компьютер для создания анимационной графики, у вас есть 950$
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconОригинал Любить и быть любимыми, наверное, в жизни, это самое главное. Есть 21 способов
Есть 21 способов \ 21 способов есть способов как показать свою любовь близким и средь них есть один! Подарочный домик магазин на...
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconСилантьева Наталья Валерьевна 21 век… Человечество вступило в третье тысячелетие, ознаменовав его блестящими открытиями науки в части постижения мира, его закон
Этому есть свое объяснение. Человек это, прежде всего, неотъемлемая часть природы. Другое дело, что эта часть имеет ряд особенностей,...
Посылки: Для любых объектов X, y и z если X есть часть y и y есть часть z, то X есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека iconЕсли у вас есть яблоко и у меня есть яблоко, и если мы обменяемся яблоками, то у вас и у меня останется по одному яблоку, а если у вас есть идея и у меня есть идея, и мы обменяемся этими идеями, то у каждого из нас будет по две идеи

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы