Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Предварённая нормальная форма
СообщениеДобавлено: 19 дек 2017, 01:25 
Не в сети
Начинающий
Зарегистрирован:
28 ноя 2017, 17:21
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте. Только начал изучать логику предикатов и столкнулся с двумя задачами, которые не понимаю как решать. Задание: привести к предварённой нормальной форме следующие формулы логики предикатов. Прошу направить в решении. В первом я раскрыл отрицание, но квантор существования нельзя из под конъюнкции выносить. Во втором раскрыл импликацию, далее - отрицание, но дальше получаются разноимённые кванторы в разном порядке которые переставлятьнельзя.
Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Предварённая нормальная форма
СообщениеДобавлено: 19 дек 2017, 03:16 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Квантор из одного члена конъюнкции или дизъюнкции можно выносить, если соответствующая переменная не входит свободно в другой член. Для того, чтобы она не входила, можно переименовать связанную переменную в первом члене. Я имею в виду эти эквивалентности.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Предварённая нормальная форма
СообщениеДобавлено: 19 дек 2017, 19:54 
Не в сети
Начинающий
Зарегистрирован:
28 ноя 2017, 17:21
Сообщений: 5
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
То есть как-то так получается?Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Предварённая нормальная форма
СообщениеДобавлено: 19 дек 2017, 23:05 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
В первом примере [math]\exists y[/math] нельзя выносить, поскольку [math]y[/math] входит свободно в правый член дизъюнкции [math]\exists x\,P(x,y)[/math]. Наоборот, [math]\exists x[/math] слева можно было вынести без переименования, поскольку [math]x[/math] не входит свободно в [math]\exists x\,P(x,y)[/math]. То есть я бы сделал так.

[math]\exists x\,\overline{P(x)}\land \exists x\,Q(x,y)=\exists x\,(\overline{P(x)}\land \exists x\,Q(x,y))=\exists x\,(\overline{P(x)}\land \exists z\,Q(z,y))=\exists x\exists z\,(\overline{P(x)}\land Q(z,y)).[/math]

Важно, чтобы множества свободных переменных в первой и последней формуле совпадали (в данном случае одна свободная переменная [math]y[/math]).

Второй пример правильный. В третьей строчке снизу скобка закрыта раньше времени. Вы переименовали переменные в первом члене дизъюнкции в ожидании вынесения кванторов из второго. Я бы вынес сначала [math]\forall x\exists y[/math] из первого члена, поскольку [math]x[/math] и [math]y[/math] не входят свободно во второй. Затем я бы переименовал второй член в [math]\exists y'\forall x'\,P(x',y')[/math] и вынес [math]\exists y'\forall x'[/math].

Заметьте, что

[math]\forall x\exists y\overline{P(x,y)}\lor\exists y\forall x\,P(x,y)=\forall x\,(\exists y\overline{P(x,y)}\lor\exists y\forall x\,P(x,y))=\forall x\exists y\,(\overline{P(x,y)}\lor\forall x\,P(x,y))[/math]

в силу тождества [math]\exists y\,A\lor\exists y\,B=\exists y\,(A\lor B)[/math]. То есть на одном кванторе можно сэкономить.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
wishermaster99
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Предваренная нормальная форма и стандартная форма Скулема

в форуме Дискретная математика, Теория множеств и Логика

vlaste

0

899

12 ноя 2016, 13:46

Предваренная нормальная форма

в форуме Дискретная математика, Теория множеств и Логика

looc26kmv

1

541

08 май 2014, 06:43

Предваренная нормальная форма для формулы

в форуме Дискретная математика, Теория множеств и Логика

Veseto555

1

286

01 фев 2021, 22:10

Жорданова нормальная форма

в форуме Линейная и Абстрактная алгебра

BUtton

6

429

12 май 2017, 18:56

Нормальная форма Сколема

в форуме Дискретная математика, Теория множеств и Логика

____aifon

1

44

13 янв 2024, 18:40

Жорданова нормальная форма матрицы

в форуме Линейная и Абстрактная алгебра

Children of Math

3

301

18 май 2019, 15:34

Квадратичная форма и полярная к ней билинейная форма

в форуме Линейная и Абстрактная алгебра

CFAS

0

449

26 дек 2018, 14:33

Гарантированная форма и форма Крылова

в форуме Численные методы

Kariaaa

1

383

04 окт 2017, 15:57

Нормальная СЛАУ

в форуме Линейная и Абстрактная алгебра

crazymadman18

1

165

23 дек 2018, 21:15

Нормальная параметризация

в форуме Дифференциальное исчисление

JULIA_BU

9

409

05 июн 2019, 03:41


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 26


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved