Упражнение по теме практического занятия

⇐ ПредыдущаяСтр 27 из 32Следующая ⇒

1. Приведите к КНФ и ДНФ следующие формулы:

а) ;

б) ;

в) ;

г) ;

д) .

2. Найдите СДНФ следующих формул, применяя соответствующие эквивалентные преобразования и (или) таблицы истинности:

а) ;

б) ;

в) ;

г) ;

д) .

Пример. Приведем к СДНФ формулу . Сначала необходимо найти ДНФ данной формулы.
В соответствии с правилами эквивалентных преобразований получаем формулу . Характерными признаками СДНФ являются: 1) в ней нет двух одинаковых элементарных конъюнкций; 2) ни одна элементарная конъюнкция не содержит двух одинаковых переменных; 3) ни одна конъюнкция не содержит свою переменную одновременно со своим отрицанием; 4) каждая элементарная конъюнкция должна содержать все переменные исходной формулы либо их отрицания. Таким образом, полученная ДНФ соответствует условиям
1–3, но не соответствует последнему условию. Для получения СДНФ добавим к левой части формулу , а к правой части – . Полученная формула будет иметь вид: . Применяя закон дистрибутивности, мы получаем: . В заключении применим закон идемпотентности: .

3. Найдите более простой вид формул, имеющих следующую СДНФ:

Пример. Дана формула . Согласно закону дистрибутивности преобразуем исходную формулу: . Затем устраним истинный член конъюнкции: . Применим закон дистрибутивности: . Наконец, устраним истинный член конъюнкции
и получим формулу .

4. Найдите СКНФ для следующих формул с помощью эквивалентных преобразований и (или) таблиц истинности:

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

Пример. Дана формула . Приведем данную формулу к КНФ. Для этого необходимо преобразовать ее таким образом, чтобы она представляла собой конъюнкцию дизъюнкций. Исключив импликацию, получим формулу . Применим к подформуле закон де Моргана, чтобы удалить отрицание: (данная формула является ДНФ). Применив к этой формуле дистрибутивный закон, получим КНФ: . СКНФ должна удовлетворять следующим требованиям: 1) в ней нет двух одинаковых дизъюнкций; 2) ни одна элементарная дизъюнкция не содержит двух одинаковых переменных; 3) ни одна элементарная дизъюнкция не содержит какую-либо переменную вместе со своим отрицанием;
4) каждая элементарная дизъюнкция должна содержать все переменные исходной формулы либо их отрицания.

Полученная КНФ соответствует всем требованиям, за исключением четвертого. Трансформируем КНФ, добавив к каждой подформуле недостающую переменную вместе с ее отрицанием: .

Применим закон дистрибутивности: . Упростим выражение, применив закон идемпотентности: . Полученная формула и является СКНФ.

5. Найдите более простой вид формулы, имеющую СКНФ:

Пример. Дана СКНФ . Применим к ней закон дистрибутивности: . Устраним ложный член дизъюнкции: . Применим закон дистрибутивности: . Устраняем ложный член дизъюнкции: .

6. Для каждой из следующих формул определите, является ли она тождественно-истинной, или тождественно-ложной, или выполнимой приведением формулы
к СДНФ и СКНФ:

а) ;

б) ;

в) ;

г) ;

д) .

Примечание.Необходимо помнить, что тождественно-истинные формулы не имеют СКНФ, а тождественно-ложные не имеют СДНФ.

Список литературы по теме практического занятия

Основная литература

1. Бочаров, В.А. Введение в логику: учебник / В.А. Бочаров, В.И. Маркин. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008. – С. 115–124.

2. Войшвилло, Е.К. Логика: учебник для студентов высших учебных заведений / Е.К. Войшвилло, М.Г. Дегтярев. – М.: ВЛАДОС-ПРЕСС, 2001. – С. 97–103.

3. Войшвилло, Е.К. Символическая логика (классическая и релевантная): философско-методологические аспекты: учебное пособие. – Изд. 2-е. – М.: Книжный дом «ЛИБРОКОМ», 2011. – С. 31–38.

4. Гетманова, А.Д. Учебник логики. Со сборником задач / А.Д. Гетманова. –
6-е изд., перераб. – М.: КНОРУС, 2006. – С. 155–177.

5. Попов, Ю.П. Логика: учебное пособие / Ю.П. Попов. – 3-е изд., перераб.
и доп. – М.: КНОРУС, 2009. – С. 216–240.

Дополнительная литература

6. Гладкий, А.В. Введение в современную логику / А.В. Гладкий. – М.: МЦНМО, 2001. – С. 27–71.

7. Жоль, А.А. Логика: учебное пособие для вузов. – М.: ЮНИТИ-ДАНА, 2004. – С. 136–174.

8. Ивлев, Ю.В. Логика: учебник / Ю.В. Ивлев. – Изд. 3-е, перераб. и доп. – М.: ООО «ТК Велби», 2002. – С. 71–88.

9. Непейвода, Н.Н. Прикладная логика: учебное пособие / Н.Н. Непейвода. – Ижевск, 2002. – С. 60–72.

10. Светлов, В.А. Современная логика: учебное пособие. – СПб.: Питер, 2006. – С. 227–246.

11. Формальная логика: учебник / отв. ред. И.Я. Чупахин, И.Н. Бродский. – Л.: ЛГУ, 1977. – С. 241–266.

12. Хаггард, Г. Дискретная математика для программистов: учебное пособие /
Г. Хаггард, Дж. Шлипф, С. Уайтсайдс; пер. с англ. – М.: БИНОМ. Лаборатория знаний, 2010.

13. Шуман, А.Н. Современная логика: теория и практика / А.Н. Шуман. – Мн.: Экономпресс, 2004. – С. 113–125.

Монографии, статьи, словари, сборники задач

14. Гильберт, Д. Основы теоретической логики / Д. Гильберт, В. Аккерман; под ред., с предисл. и коммент. С.А. Яновской; пер. с нем. – Изд. 2-е, испр. – М.: КомКнига, 2010. – С. 19–67.

15. Ивин, А. А. Словарь по логике / А.А. Ивин, А.Л. Никифоров. – М.: Гуманит. изд. центр «ВЛАДОС», 1997.

16. Клини, С.К. Введение в метаматематику / С.К. Клини; под ред. В.А. Успенского; пер.с англ. – Изд. 2-е, испр. – М.: Книжный дом «ЛИБРОКОМ», 2009. – С. 67–99.

17. Коэн, М. Введение в логику и научный метод / М. Коэн, Э. Нагель; пер. с англ. П.С. Куслия. – Челябинск: Социум, 2010. – С. 150–220.

18. Мельников, В.Н. Логические задачи / В.Н. Мельников. – К.; Одесса: Выща шк., 1989. – С. 154–193.

19. Смирнова, Е.Д. Логика и философия / Е.Д. Смирнова. – М.: РОССПЭН, 1996.

20. Чёрч, А. Введение в математическую логику. Т. 1 / А. Чёрч; под ред. и с предисл. В.А. Успенского; пер. с англ. – Изд. 2-е. – М.: Книжный дом «ЛИБРОКОМ», 2009. – С. 65–111.

Исчисление высказываний

План

1. Аксиоматические исчисления высказываний:

а) аксиомы, правила вывода и доказательство в аксиоматическом исчислении;

б) исчисление высказываний со схемами аксиом;

в) теорема дедукции.

2. Натуральные исчисления высказываний:

а) правила вывода в натуральном исчислении;

б) вывод и доказательство в натуральном исчислении;

в) эвристики (способы отбора высказываний).

3. Метатеоретические свойства аксиоматического и натурального исчисления высказываний:

а) дедуктивная эквивалентность натурального и аксиоматического исчислений высказываний;

б) непротиворечивость натурального и аксиоматического исчислений высказываний;

в) полнота натурального и аксиоматического исчислений высказываний;

г) разрешимость натурального и аксиоматического исчислений высказываний.

⇐ Предыдущая 22 23 24 25 262728 29 30 31 Следующая ⇒